| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV Introducción 4.1 Frases, formas sentenciales, Handles (Mangos), Prefijo Viable 4.2 Eliminación de Recursión inmediata y no inmediata 4.3 Factorización de Gramáticas

4.4 Analizador Top-Down

4.4.1 Análisis Sintáctico por Descenso Recursivo sin Retroceso y con Retroceso

4.4.2 Análisis Sintáctico LL(1)

4.4.2.1 Cálculo de First y Follow

4.4.2.2 Definición de Gramáticas LL(1) con reglas Épsilon

4.4.2.3 Algoritmo de análisis sintáctico LL(1)

4.5 Analizador Bottom-UP

4.5.1 Análisis Sintáctico por Precedencia de Operadores

4.5.1.1 Definición de Gramáticas de Operadores

4.5.1.2 Definición Formal de las Relaciones de Precedencia de Operadores

4.5.1.3 Funciones Firstop y Lastop

4.5.1.4 Obtención de la tabla de precedencia de Operadores

4.5.1.5 Algoritmo de análisis Sintáctico por Precedencia de Operadores

4.5.2 Análisis Sintáctico LR

4.5.2.1 Algoritmo de Análisis Sintáctico LR

4.5.2.2 Análisis Sintáctico LR(0)

4.5.2.2.1 Construcción de la Máquina LR(0)

4.5.2.2.2 Construcción de la Tabla LR(0)

4.5.2.2.3 Análisis Sintáctico SLR

4.5.2.2.4 Obtención de Estados SLR

4.5.2.2.5 Construcción de la Máquina de Estados SLR

4.5.2.2.6 Construcción de la Tabla SLR

4.5.2.2.7 Análisis Sintáctico LR(1)

4.5.2.2.8 Definición de elementos LR(1)

4.5.2.2.9 Construcción de conjuntos de elementos

4.5.2.2.10 Construcción de Máquina de estados LR(1)

4.5.2.2.11 Construcción de la Tabla LR(1)

UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

4.5.2 Algoritmo de Análisis Sintáctico LR

> Informalmente, una gramática LR(k) (Knuth, 1965) permite analizar de forma determinista, de izquierda a derecha, una cadena de entrada, observando a lo sumo los siguientes elementos:

> El contexto izquierdo (ya analizado).

> La parte de la cadena que se va a reducir.
> Un máximo de k símbolos del contexto derecho.

> Los analizadores basados en gramáticas LR(k) presentan características comunes con los analizadores "top-down" y "bottom-up".

> Configuración

> Es una producción con un marcador, que indica hasta donde hemos llegado en el análisis de la parte derecha. Por ejemplo, sea la gramática parcial

> 1: <Bloque> ::= begin <Decs> ; <Ejecs> end
> 2: <Decs> ::= <Dec>
> 3: | <Decs> ; <Dec>
> 4: <Ejecs> ::= <Ejec>
> 5: | <Ejec> ; <Ejecs>

> Son configuraciones válidas las siguientes:
> (1,0)
> (2,1)
> (3,3)

> Donde (a,b) indica que estamos analizando la posición b (en origen 0) de la parte derecha de la regla de producción número a.

> Estado

> Se representa mediante un conjunto de configuraciones. Indica las configuraciones posibles en la situación actual del análisis. Su número es finito.

> Supongamos que estamos en la configuración representada por (a,b), y que el símbolo siguiente a la posición b en la parte derecha de la regla a es el símbolo no terminal U. Sean c,...,d las reglas cuya parte izquierda es U. Entonces, de la configuración (a,b) se podrá pasar a las configuraciones (c,0),...,(d,0). Si aplicamos el mismo procedimiento indefinidamente, hasta que no aparezcan configuraciones nuevas, tendremos la "clausura" de la configuración (a,b): el conjunto de estados que han ido apareciendo, incluido el (a,b). Si partimos de un conjunto de configuraciones (un estado), la clausura correspondiente será igual a la unión de las clausuras de las configuraciones del estado.

> Estado inicial

> Para preparar el análisis LR(k) de una gramática hacemos inicialmente dos cosas:

> Añadimos a la gramática la regla nueva:
> S' ::= S -|

> Donde S' es un símbolo no terminal nuevo (nuevo axioma), S es el axioma de la gramática original, y -| es un símbolo terminal nuevo (símbolo final de cadena) que, además, añadimos al final de la cadena de entrada. Esta regla pasa a ser la regla número 0 de la nueva gramática. Las demás reglas quedan como estaban.

> El estado inicial del análisis es la clausura de {(0,0)}.

> Operación corrimiento

> Dado un estado, se puede pasar al estado sucesor mediante la operación "corrimiento", que consiste en avanzar un símbolo sobre la cadena de entrada, pasando además del estado actual a otro nuevo, que se obtiene así:

> Se extraen del estado las configuraciones (a,b) en las que el símbolo siguiente a la posición b en la parte derecha de la regla a es el próximo símbolo de la cadena de entrada. El estado sucesor es la clausura del conjunto de configuraciones {(a,b+1)}.

> Obsérvese que en la cadena de entrada podemos encontrar símbolos terminales o no terminales, como veremos a continuación.

> Operación reducción

> Cuando una configuración representa el final de la parte derecha de una regla, se puede aplicar esa regla, añadiendo su parte izquierda a la izquierda de la cadena de entrada, eliminando de la lista de estados por los que se ha pasado los que corresponden a la parte derecha de la regla aplicada, y volviendo al estado anterior al comienzo del análisis de dicha regla.

> Tabla de análisis

> La tabla del análisis tiene tantas filas como estados accesibles a partir del inicial, y tantas columnas como símbolos del vocabulario.

> Para construir la tabla del análisis, partimos del estado inicial y calculamos los estados accesibles a partir de él, los estados accesibles a partir de éstos, etc., hasta que no salgan estado nuevo, utilizando únicamente la operación corrimiento. A continuación, rellenamos algunas casillas con la operación reducción, utilizando para ello una regla que veremos después.

> Además, pondremos "Fin" en la casilla cuya fila es el estado inicial y cuya columna es el axioma. Esto sólo podremos hacerlo en algunas gramáticas, en aquéllas en las que el axioma no puede aparecer en ninguna forma sentencial. Más adelante veremos cómo se actúa cuando esto no es cierto.

> Reglas para la operación reducción

> Dependiendo de la regla utilizada para rellenar algunas casillas de la tabla con la operación reducción, tendremos distintos tipos de familias de analizadores LR(k).

> Analizadores LR(0)

> La regla es: "si un estado contiene configuraciones de final de regla, reduciremos esa regla en todas las casillas correspondientes a un símbolo terminal".

> La aplicación de la regla anterior puede provocar conflictos de dos tipos:

> Si un estado contiene una configuración final de regla y otra que no lo es, situada delante de un símbolo terminal, deberíamos poner dos transiciones en la misma casilla, lo que la haría no determinista. Este es un conflicto corrimiento-reducción.

> Si un estado contiene dos configuraciones finales de regla, también deberíamos poner dos transiciones en la misma casilla. Este es un conflicto reducción-reducción.

> Analizadores SLR(1)

> La regla es: "si un estado contiene configuraciones de final de regla, reduciremos esa regla en todas las casillas correspondientes a un símbolo terminal que aparezca detrás de la parte izquierda de esa regla (directamente o después de alguna derivación) en la parte derecha de otra".

> Si al aplicar la regla anterior no hay ningún conflicto, decimos que la gramática está en forma SLR(1). Para cualquier lenguaje independiente del contexto determinista existe una gramática SLR(1) que lo representa.

> En las gramáticas LR(1), cada configuración se incrementa con información sobre los símbolos de entrada que pueden venir a continuación. Esto complica los estados y las transiciones, pero en general no es necesario. Se demuestra que todo lenguaje representable mediante una gramática LR(1) también puede representarse mediante una gramática SLR(1).

> Relaciones entre lenguajes

> Independientes del contexto (Chomsky-tipo 2)
> Ind. contexto deterministas = SLR(1) = LR(1)
> -------------------------------------
> LL(k) Precedencia simple
> LL(1) Precedencia operadores

> Análisis

> Para realizar el análisis, aplicaremos el siguiente algoritmo:

> 1. Se construye la tabla del análisis, como se ha indicado.
> 2. Se añade a la cadena de entrada el símbolo final.
> 3. Se construye una pila de estados, inicializada al estado inicial.
> 4. En cada paso, el estado actual en que se encuentra el análisis es el que está en lo alto de la pila. Se indexa la tabla del análisis, por filas por el estado actual, por columnas por el primer símbolo de la cadena de entrada, para hallar la acción a realizar.
> 5. Si es un corrimiento, eliminamos el primer símbolo de la cadena de entrada, introducimos el nuevo estado en lo alto de la pila y volvemos al paso 4.
> 6. Si es una reducción, eliminamos de la pila tantos estados como símbolos haya en la parte derecha de la regla a aplicar, añadimos la parte izquierda de la regla a la izquierda de la cadena de entrada y volvemos al paso 4.
> 7. Si es Fin, la cadena de entrada estará constituida por el axioma de la gramática, seguido por el símbolo final de cadena. La cadena inicial ha sido aceptada (es correcta).
> 8. Si está en blanco, la cadena inicial de entrada es errónea.

Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello