Universidad: aztecaprofesor: ing. Gabriel

nombre del alumno: fabian enrique dominguez morales

fecha de entrega: 16/05/2014

3.3.2 ANALISIS SINTacTICO LRtambién conocidos como Parser LR, son un tipo de analizadores para algunas gramáticas libres de contexto.

Un analizador LR consta de:

1. Un programa conductor

2. Una entrada

3. Una salida

4. Una tabla de análisis sintáctico, compuesta de 2 partes (ACCIÓN Y GOTO)

Cabe aportar que el programa conductor es siempre igual, solo variando para cada lenguaje la tabla de análisis sintáctico.

El algoritmo

para reconocer cadenas es el siguiente:

dado el primer carácter de la cadena y el estado inicial de la tabla, buscar qué acción corresponde en la tabla de acción.

Si el estado es shift n (n ∈ N), se coloca el carácter y el número de estado n en la pila, se lee el siguiente carácter y repite el procedimiento, solo que esta vez buscamos en el estado correspondiente.

En la tabla acción también encontraremos ACEPTAR que se toma la cadena como valida y se termina el análisis o ERROR que se rechaza la cadena.

Algoritmo para generar un autómata LR(0)

Para generar un autómata LR(0) en base a una gramática G, primero se debe definir:

Gramática ampliada: Dado una gramática G, se define la gramática ampliada G'a:

1. Se agrega una producción S'->S# donde S es el símbolo inicial.(el # representa el fin de cadena)

2. Se pasan todas las producciones a ítems de configuración (veremos este concepto en un instante) con el punto al principio de la cola

3. Se define S' como el símbolo inicial de la gramática.

Ítem de configuración: un ítem de configuración es una producción que tiene un carácter especial (generalmente un punto) en algún lugar de la cola. Por ejemplo: la producción S->ABC genera los siguientes ítems,{ S->.ABC, S->A.BC, S->AB.C S->ABC.}. Como veremos en un instante, y hablando informalmente el punto representa el lugar actual en donde me puedo encontrar en un momento en el parseo en una producción.

Clausura de un ítem: se define a la clausura de un ítem (y de forma informal) a: dado un ítem S->A.cB (A, B e V*, c e Vt unión VN) al conjunto formado por

1. S->A.cB 2. Si c es un no terminal, se agregan todos

los ítems que tengan a c como cabeza de la producción y el punto al principio de la cola,

3. Si p es un ítem que pertenece a la clausura, la clausura de p pertenece a la clausura, siempre y cuando ya no este agregada.

Finalmente, la construcción del autómata es así:

1. Se amplía la gramática

2. Dado el símbolo inicial de la gramática ampliada, se calcula su clausura y este se define como un estado inicial.

3. Para cada estado: se agrupan las producciones según el carácter que está después del punto, si todavía no se definió el estado, se corre el punto un carácter a la derecha, se crea el nuevo estado con esta producciones, y la clausura de cada una de ellas, se define el carácter que estaba después del punto en el estado de origen como el carácter de la transición.

4. Si el estado tiene en alguna producción el punto al final, este estado se marca como un estado final del autómata.

5. Se sigue hasta que ya no se tenga más estados nuevos posibles.

3.3.3 Analizador sintáctico ascendente ( Bottom-Up-Parser ): Parten de la sentencia de entrada,y van aplicando

derivaciones inversas (desde el consecuente hasta el antecedente), hastallegar al axioma inicial.

De gramáticas LR(1)En este epígrafe se introducirá una técnica eficiente de análisis sintácticoascendente que se puede utilizar para procesar una amplia clase de gramáticasde contexto libre. La técnica se denomina análisis sintáctico LR(k).

La abreviaturaLR obedece a que la cadena de entrada es examinada de izquierda a derecha (eninglés, Left-to-

right), mientras que la “R” indica que el proceso proporciona el árbolsintáctico mediante la secuencia de derivaciones a

derecha (en inglés, Rightmostderivation) en orden inverso. Por último, la “k” hace referencia al número de tokens de pre-búsqueda utilizados para tomar las decisiones sobre

si reducir o desplazar.Cuando se omite, se asume que k, es 1.El análisis LR es atractivo por varias razones.

β : representa el trozo de la cadena de

entrada (secuencia de tokens) por consumir: â 0 T .Coincidirá siempre con algún trozo de la parte derecha de * la cadena de entrada. Comopuede suponerse, inicialmente â coincide con la cadena a reconocer al completo (incluido elEOF del final).

3.4 Rutinas de Manejo de Errores

Ocupan gran parte de los compiladores

Objetivos

Informar con claridad, exactitud

Recuperación rápida

recuperación no es corrección

No debe retrasar el procesamiento de programas sin errores

No generar errores en cascada (ej. eliminar identificador)

Acciones posibles

Detectar errores

Informar de los errores

Recuperar de los errores

Corregir errores

¿Necesidad actual de recuperación?

Más rápido re-compilar que leer.

Tipos de Errores

Tipos de errores Léxicos: escribir mal un

identificador, número, ... Sintácticos: no poner un “;” al

final de una sentencia, estructura incorrecta Semánticos: multiplicar por una

variable booleana Lógicos: bucle infinito Herramientas para disminuir el

número de errores ...

Léxicos Si se utiliza alguna herramienta

que complete palabras Sintácticos Si se utiliza algún editor basado

en sintaxis (colores) Semánticos Busca funciones/clases e in dica tipos especificados  

Recuperación Errores Sintácticos ∑ᶰ 

a b c d

S aAS

bA    

A     cA d

Ejemplo 1: análisis descendenteGramática:S::=a A S | b AA::=c A | dTabla:  Entrada: a b ...Estado del análisis cuando detecta el error:Pila Entrada

$S a b ...$SAa a b ...$SAb ...Error: Se ha encontrado una b, cuando se esperaba una co dPodría eliminarse 

Estrategias de Recuperación

No hay una estrategia de aceptación universalAbundan técnicas heurísticas y ad hocPrincipio general de recuperaciónMinimizar tokens eliminados/modificadosDejar el analizador listo para continuar procesandoPrincipales estrategias de recuperación son:Modo de pánico/alarmaNivel de fraseProducciones de errorCorrección Global

Corrección GlobalCaracterísticas

Algoritmos que eligen una secuencia mínima de cambios para obtener una corrección global de menor costo Ej.: x=a(p+q(-b(r-s); ->

a(p+q)-b(r-s); ifa=b then sum=0; -> if a

=b then sum=0; Inconvenientes Técnicas costosas en

tiempo y espacio: métricas de distancias, búsqueda,

optimización.  

3.4.1 Last error (informática)

en computación, específicamente en el campo de la programación en Windows se conoce como Last Error al último error sucedido al utilizar una de las API de Windows. Los códigos de error son particulares de cada Thread que esté en ejecución.

3.4.2 Errores personalizados

Una función propia o de un programa por defecto de Windows puede hacer uso de la Api SetLastError para informar que error ha ocurrido o en el caso de no haber error puede usarse para poner en cero el último error ocurrido. Una vez hecho esto, el error de la función anteriormente utilizada no se podrá determinar.

Estos errores son enteros de 32 bits. Si se quiere usar SetLastError para "nuevos" errores propios de la aplicación se debe de activar el bit 29 ya que el sistema no usa errores con ese bit activado. ↓ Bit 29 ↓ 00100000 00000000 00000000 00000000↑

↑↑ Bit 31, el más significativo ↑ Bit 0, el menos significativo

Una vez activado los números serán mayores o iguales que 20000000H (en hexadecimal) o 536870912D (en decimal).

En DELPHI

function MuestraError(error: DWORD): String;var pString: array[0..MAX_PATH] of char;begin FormatMessage(FORMAT_MESSAGE_FROM_SYSTEM, Nil, error, 0, pString,

MAX_PATH, Nil); Result := pString;end;

3.5 Tabla de símbolos (compilador)

una tabla de símbolos es una estructura de datos que usa el proceso de traducción de un lenguaje de programación, por un compilador o un intérprete, donde cada símbolo en el código fuente de un programa está asociado con información tal como la ubicación, el tipo de datos y el ámbito de cada variable, constante o procedimiento.

Una implementación común de una tabla de símbolos puede ser una tabla hash, la cual será mantenida a lo largo de todas las fases del proceso de compilación de ticses.

Los símbolos en la tabla de símbolos pueden referirse a constantes, a funciones o a tipos de datos en el código fuente de un programa.

La tabla de símbolos forma parte de cada fichero que contiene el código objeto durante el enlazado o linking de los diferentes ficheros; recae en la responsabilidad del linker o enlazador resolver cualquier referencia no resuelta.

La siguiente representa una serie de atributos que no es necesaria para todos los compiladores, sin embargo cada uno de ellos se puede utilizar en la implementación de un compilador particular.

nombre del identificador. dirección en tiempo de ejecución a partir del cual se almacenara el

identificador si es una variable. tipo del identificador. Si es una función, el tipo que devuelve la

función. número de dimensiones del array (arreglo), o número de miembros

de una estructura o clase, o números de parámetros si se trata de una función.

tamaño máximo o rango de cada una de las dimensiones de los array, si tiene dimensión estática.

etc.

Al definir un lenguaje de programación, también hay

que diseñar la tabla de símbolos

que permite almacenar la información expresable

mediante declaraciones Especificando estructura en abstracto Especificando operaciones de acceso y

modificación Especificando algoritmo de construcción Precisamente el algoritmo de construcción (que mientras analiza la sección de

declaraciones va rellenando la tabla) utiliza una

gramática de atrib utos

3.5.1 Tablas en árbol binario

Usan árboles binarios. Se compara la clave k con la del elemento. Si es mayor, se va a la derecha, si es menor a la izquierda. El tiempo de búsqueda depende del orden de inserción de los elementos y sólo es calculable si el árbol está equilibrado. Si no, se convierte en una lista ordenada, reordenando. Ej: G D M E A B F H. Secuencias aparentemente aleatorias pueden producir el mismo resultado.

3.5.2 OPERACIÓN CON TABLAS DE SIMBOLOS

A cada clave se le asocia biunívocamente un elemento de la tabla mediante una función I(k) biyectiva. Ejemplo: identificadores de una sola letra. La tabla tendrá 26/52 elementos como máximo. I(k) = k-'A'; // (26 elementos) I(k) = (k<'a') ? k-'A' : 26+k-'a'; //

(52 elementos) Búsqueda: dado k, se halla I(k) y se tiene el elemento. Li = Lm = LM = 1

Tablas Hash o de entrada calculada

Es el método más usado. Se trata de trasformar la clave en un índice de entrada aplicándole una función Hash, I(k), que puede no ser biyectiva.

Es equivalente a una tabla de acceso directo mientras no aparezcan dos claves tales que I(k1) = I(k2): colisión.

Tablas Hash abiertas (con rehash)

Búsqueda de la clave k. Se calcula h = I(k). Se compara k con T(h). Si es

igual, encontrado. Si hay colisión (k!

=T(h)&&T(h)!=NULL) se compara k con T(mod(h+p1,N)).

Si hay nueva colisión se compara k con T(mod(h+p2,N)).

...

Si hay nueva colisión se compara k con T(mod(h+pi,N)).

hasta que se encuentre la clave buscada, un lugar vacío o se vuelva a T(h). En el primer caso, se ha encontrado. En el segundo, no está en la tabla. En el tercero, tampoco está, y la tabla está llena para ese valor de la función Hash.

Rehash lineal

pi = i Se comparan elementos sucesivos.

Problema: apiñamiento de elementos. La longitud de búsqueda es difícil de calcular

(depende del grado de apiñamiento, y éste del orden en que se definen los identificadores).

3.5.3 Estructuras de datos para tablas de símbolos.

La tabla de símbolos es una estructura de datos que nos permite realizar operaciones de inserción, búsqueda y eliminación de información en varias construcciones del lenguaje fuente, la cual es analizada por el compilador originándose un código objeto.

Interfaz de la tabla de símbolosLas principales operaciones de la tabla de símbolos las definimos asi:

inserción:almacena información proporcionada por las declaraciones de nombre cuando estas son procesadas.

Búsqueda:recupera la inaformacion asociada con un nombre cuando este se utiliza en una declaración o el código asociado.

Eliminacion:elimina la informcion proporcionada por una declaración cuando esta ya no se aplica.