| 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.4.2 Análisis Sintáctico LL(1)

> Las gramáticas LL(1), forman parte del analizador sintáctico que para entenderlas se toma como base algunos ejemplos.

> En la introducción al análisis sintáctico descendente (ASD) se ve como las implementaciones de los analizadores sintácticos recursivos con retroceso (ASDRR) podían producir programas sumamente ineficientes por el carácter no determinista de la solución subyacente.

> Por ejemplo, en la siguiente gramática:
> A → BC
> B → e
> B → DB
> C → abb
> D → a
> D → b

> Observamos que, ante una configuración: (w$, Ba$) para hacer el análisis eficiente debíamos hacer la sustitución B → e solo si los siguientes cuatro símbolos en la entrada eran abb$, y la sustitución B → DB de lo contrario.

> Es posible transformar la gramática en una equivalente de manera que el analizador recursivo resultante sea eficiente:

> A → abb$
> A → DA
> D → a
> D → b

> Ante esta situación, debemos preguntarnos:

> ¿Es siempre posible decidir cual es la producción (substitución) correcta mirando los siguientes k símbolos de la secuencia entrada?
> ¿Cómo sabemos cuántos símbolos debemos mirar (el valor de k)?

> Gramáticas LL(k)

> En general no es posible (no sabemos como) construir analizadores sintácticos eficientes para cualquier gramática. A pesar de eso, dada una gramática independiente del contexto y un entero k específico, si podemos hacer lo siguiente:

> Determinar si para dicha gramática es posible decidir la producción correcta en casa paso de una derivación mirando solo los k símbolos siguientes en lo que resta de la secuencia de entrada.

> Si la respuesta a lo anterior es si, podemos construir de manera sistemática una analizador sintáctico descendente determinista para esa gramática.

> Las gramáticas para las cuales podemos decidir de manera inambigua la producción a utilizar en cada paso de una derivación mirando solo k símbolos de entrada se llaman gramáticas LL(k) y los lenguajes generados por esas gramáticas se llaman lenguajes LL(k). El nombre LL(k) significa lo siguiente:

> L: La entrada se examina de izquierda a derecha (Left to right).
> L: El análisis produce una derivación izquierda (Left derivation).
> k: El análisis se hace mirando a lo sumo k símbolos de lo que resta de la secuencia de entrada.

> La mayoría de los lenguajes de programación de uso común se describen mediante gramáticas LL(1).

> Se puede demostrar que para que una gramática G sea LL(k), G debe ser:

> No-ambigua
> Carente de recursión por la izquierda.
> Determinar el valor de k es No-Decidible

> Desafortunadamente, dada una gramática G no es posible en general darle respuesta a la pregunta: ¿Es G una gramática LL(k) para algún k? Más formalmente, la pregunta es no-decidible; es decir, la única manera de contestarla es probar (tal vez indefinidamente) con distintos valores de k hasta encontrar uno para el cual la gramática sea LL(k).

> Ambigüedad, Recursión Izquierda, Prefijos Comunes, y LL(k)

> A pesar de que el problema LL(k) es en general no-decidible, es fácil demostrar que ninguna gramática que posea alguna de las siguientes características es LL(k):

> - La gramática es ambigua.

> - La gramática es recursiva por la izquierda.

> - La gramática posee prefijos comunes de longitud mayor o igual a k.

> Por eso, antes de tratar de comprobar si una gramática es LL(k), primero eliminamos la recursión izquierda, y examinamos los prefijos comunes para decidir si debemos eliminarlos.

> # Definición formal de LL(k)

> #

> Sea G = (N, S, P, S) una gramática inambigua y w = a1a2...an una sentencia o frase en L(G) (el lenguaje generado por G). Entonces (por la definición de ambigüedad) existe una secuencia única de formas sentenciales izquierdas α0, α1,.., αn tal que:

> La derivación izquierda de w es entonces p0, p1,..., pn, donde pi es la producción con el número i. Deseamos encontrar dicha derivación conociendo solo:

> - La secuencia de símbolos de entrada que ya hemos leído.

> - La forma sentencial actual.

> - Los siguientes k símbolos en la secuencia de entrada, para un k pequeño.

> Dada una [forma sentencial izquierda] α = xβ, donde x Σ* y β comienza por un no terminal o es ε, decimos que x es la parte cerrada de α y que β es la parte abierta de α.

> El analizador sintáctico es el proceso de determinar si una cadena de componentes léxicos puede ser generada por una gramática. Un analizador sintáctico construye un árbol (de análisis sintáctico) ascendente o descendente según sea el método usado.

> (*). Donde recordemos que el método descendente va de la raíz hasta llegar a las ultimas hojas (de arriba hacia abajo) y el método ascendente va de las ultimas hojas hasta la raíz (abajo-arriba).

> Los métodos ascendentes y descendentes (*) mas eficientes trabajan solo con clases de gramáticas LL y LR. Significa lo siguiente:

> - L: La entrada se examina de izquierda a derecha (Left to right).

> - L: El análisis produce una derivación izquierda (Left derivation).

> - R: El análisis produce una derivación derecha (Right derivation).

> La mayoría de los lenguajes de programación de uso común se describen mediante gramáticas LL(1).

> Los analizadores sintácticos implantados a mano a menudo trabajan con gramáticas LL1.

> Lenguajes LL(1)

> Son gramáticas en forma normal de Greibach en las que no existen dos reglas con la misma parte izquierda, cuya parte derecha empiece por el mismo símbolo terminal.

> Conversión: si existen reglas de la forma:

>        U ::= aV | aW

>        V ::= bX | cY

>        W ::= dZ | eT

> Tratamos de sustituir las dos reglas de parte izquierda U por:

>        U ::= aK

>        K ::= bX | cY | dZ | eT

> Y aplicamos la misma sustitución a las nuevas reglas formadas.
> La gramática se llama LL(1) de Knuth porque basta estudiar en cada momento un carácter de la cadena objetivo para saber qué regla se debe aplicar.

> Análisis "top-down" selectivo

> Se llama también "sin vuelta atrás" o "descenso recursivo". Se basa en poner la gramática en la forma normal de Greibach (LL(1)) y marchar directamente por el único camino permisible. Si en algún momento no se encuentra regla que aplicar, se puede generar directamente un mensaje de error.

> Ejemplo: sea la gramática:

> E := T + E | T - E | T
> T := F * T | F / T | F
> F ::= i | (E)

> En forma normal de Greibach queda:

> E ::= iPTME | (ECPTME | iDTME | (ECDTME | iME | (ECME |
> iPTSE | (ECPTSE | iDTSE | (ECDTSE | iSE | (ECSE |
> iPT | (ECPT | iDT | (ECDT | i | (EC
> T ::= iPT | (ECPT | iDT | (ECDT | i | (EC
> F ::= i | (EC
> M ::= +
> S ::= -
> P ::= *
> D ::= /
> C ::= )

> En forma LL(1) queda:
> E ::= iV | (ECV
> V ::= *TX | /TX | +E | -E | ^
> X ::= +E | -E | ^
> T ::= iU | (ECU
> U ::= *T | /T | ^
> F ::= i | (EC
> C ::= )

> Paso automático de la gramática LL(1) al analizador.
> Dada una gramática LL(1), formada por un conjunto de reglas de la forma:

> U ::= x X1 X2 ... Xn | y Y1 Y2 ... Ym | ... | z Z1 Z2 ... Zp

> Generamos la siguiente función C:

> Si las reglas tienen la forma

> U ::= x X1 X2 ... Xn | ... | z Z1 Z2 ... Zp | ^

> Ejemplo: la gramática anterior se reduce a:

> La cadena x se analiza invocando
> Axioma (x, 0);

> En nuestro ejemplo:
> E (x, 0);

> Si devuelve strlen(x), la cadena x es correcta. En caso contrario, devolverá un número negativo que indica el error detectado.

> Ejemplo: análisis de "i+i*i".
> E ("i+i*i", 0) = V ("i+i*i", 1) =
> = E ("i+i*i", 2) =
> = V ("i+i*i", 3) =
> = X ("i+i*i", T ("i+i*i", 4)) =
> = X ("i+i*i", U ("i+i*i", 5)) =
> = X ("i+i*i", 5) =
> = 5

> Ejemplo: análisis de "i+i*".
> E ("i+i*", 0) = V ("i+i*", 1) =
> = E ("i+i*", 2) =
> = V ("i+i*", 3) =
> = X ("i+i*", T ("i+i*", 4)) =
> = -2

> Análisis "bottom-up"

> Parte del objetivo y trata de reconstruir las producciones para llegar a reducir al axioma.

> Ejemplo: sea la gramática
> E ::= E + T | E - T | T
> T ::= T * F | T / F | F
> F ::= i | (E)

> Y la expresión (reducida por el analizador morfológico) i+i*i. Colocamos un puntero sobre la cadena a analizar.
> Meta: E

> i + i * i
> ^
> La única regla que empieza por "i" es F::= i. La aplicamos:
> Meta: E

> F
> i + i * i
> ^

> La cadena a obtener (subobjetivo), vista desde arriba, es F+i*i. La única regla aplicable (que empiece por F) es T::=F. La aplicamos:
> Meta: E

> T
> F
> i + i * i
> ^

> La cadena a obtener (subobjetivo), vista desde arriba, es T+i*i. Hay dos reglas cuya parte derecha empieza por T, E::=T y T::=T*F. Probamos la de parte derecha más larga (la segunda): regla aplicable (que empiece por F) es T::=F. La aplicamos:
> Meta: E

> T
> |----
> T * F
> F
> i + i * i
> ^

> Y avanzamos el puntero para comprobar. La submeta a encontrar es *F y la subcadena a generar es +i*i. Como comienzan por distinto símbolo terminal, no es posible hacerlo. Retrocedemos a la situación anterior y aplicamos la otra regla,

> E::=T.
> Meta: E

> E
> T
> F
> i + i * i
> ^

> El objetivo actual es E+i*i. Ha aparecido el axioma, pero queda cadena por reducir. Sólo hay una regla cuya parte derecha empiece por E, E::=E+T. La aplicamos:

> Meta: E

> E
> |----
> E + T
> T
> F
> i + i * i
> ^

> Ahora tenemos el subobjetivo +T que debe producir +i*i. Los dos símbolos terminales iniciales coinciden. Los identificamos y avanzamos el puntero.

> Meta: E

> E
> |----
> E | T
> | | Submeta: T
> T |
> F |
> i + i * i
> ^

> Partiendo de i*i hay que comprobar la submeta T. La única regla que empieza por "i" es F::= i. La aplicamos:

> Meta: E

> E
> |----
> E | T
> | | Submeta: T
> T |
> F | F
> i + i * i
> ^

> La única regla que empieza por F es T::= F. La aplicamos:
> Meta: E

> E
> |----
> E | T
> | | Submeta: T
> T | T
> F | F
> i + i * i
> ^

> Hemos encontrado la submeta T. Pero aún queda cadena. Miramos si hay alguna regla cuya parte derecha empiece por T. Hay dos, E ::= T y T ::= T*F. Probamos la de parte derecha más larga (la segunda).

> Meta: E

> E
> |----
> E | T
> | | Submeta: T
> | | T
> | | |----
> T | T * F
> F | F
> i + i * i
> ^

> Avanzamos el puntero y comprobamos la subcadena *F con la subcadena *i. Los dos símbolos terminales iniciales coinciden. Los identificamos y avanzamos:

> Meta: E

> E
> |----
> E | T
> | | Submeta: T
> | | T
> | | |----
> T | T | F
> | | | | submeta: F
> F | F |
> i + i * i
> ^

> Partiendo de i hay que comprobar la submeta F. La única regla que empieza por "i" es F::=i. La aplicamos:

> Meta: E

> E
> |----
> E | T
> | | Submeta: T
> | | T
> | | |----
> T | T | F
> | | | | Submeta: F
> F | F | F
> i + i * i
> ^

> Todas las metas y submetas coinciden. Luego ésta es la reducción al axioma buscada. El árbol de análisis queda:

> E
> |----
> E | T
> | | |----
> T | T | F
> F | F | |
> i + i * i

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