Skip to main content
Version: 2021_2

Analizadores Sintácticos LL(1)

El análisis sintáctico LL(1) utiliza una pila explicita en vez de llamadas recursivas para efectuar el análisis sintáctico. Una gramática LL(1) no tiene recursividad por la izquierda y no es ambigua.

Entonces antes de armar el parser se debe verificar que la gramática sea LL(1) o se transforma la gramática con la que se está trabajando en LL(1) mediante la aplicación de las siguientes técnicas:

  • Eliminación de la recursividad por Izquierda

  • Eliminación de ambigüedad

  • Un analizador sintáctico descendente comienza a insertar el símbolo inicial sobre la pila. Acepta una cadena de entrada, si, después de una serie de acciones, la pila y la entrada se quedan vacías.

  • Un analizador sintáctico descendente realiza su análisis al reemplazar un no terminal en la parte superior de la pila por una de las elecciones en la regla gramatical (en BNF) para ese no terminal. Realiza esto con miras a producir el token de entrada actual en la parte superior de la pila de análisis sintáctico, de donde ha reconocido el token de entrada y puede descartarlo tanto de la pila como de la entrada. Estas dos acciones,

    1. Reemplazar un no terminal A en la parte superior de la pila mediante una cadena α utilizando la selección de la regla gramatical A->alpha, y

    2. Hacer concordar un token en la parte superior de la pila con el siguiente token de entrada.

Son las dos acciones básicas de un analizador sintáctico descendente.

  • La primera acción se llama generar.
  • La segunda acción hace concordar a un token en la parte superior de la pila con el siguiente token en la entrada (y los desecha a ambos sacándolos de la pila y avanzando a la entrada); indicamos esta acción indicando la palabra match.

Es importante advertir que en la acción generar, la cadena de reemplazo α se debe insertar en reversa en la pila (ya que eso asegurara que la cadena α arribara a la parte superior de la pila en el orden de izquierda a derecha).

  1. Ejemplo

    Sea la gramática:

S->(S)S | ε

pilaentradaacción
1$S()$S->(S)S
2$S)S(()$match
3$S)S)$S->ε
4$S))$match
5$S$S->ε
6$$aceptar

Lo que se realizó, es justamente la derivación:

S -> ( S ) S -> ( ) S [S -> ε] -> ( ) [S -> ε]

Tabla de parsing:

M[N,T]()S
SS->(S)SS->εS->ε

El Algoritmo#

Para armar un parser LL(1) es necesario cumplir con un conjuntos de pasos. Dado una gramática libre de contexto a la que se quiere construir un analizador sintáctico LL(1), es necesario:

  • Eliminar la recursión por izquierda de la gramática
  • Factorizar por la Izquierda la gramática
  • Construir el conjunto de PRIMEROS
  • Construir el Conjunto de SIGUIENTES
  • Construir la tabla de Parsing

Eliminación por recursión por la izquierda y factorización por la izquierda#

¿Que es la recursión por izquierda en una gramática?

A → A α | β

Donde α y β son cadenas de terminales y no terminales , y β no comienza con A. Entonces A → β es el caso base, mientras que A → A α es el caso recursivo.

  • La eliminación de recursión a la izquierda no cambia el lenguaje que se está reconocienndo.

  1. Eliminación de recursión por la Izquierda simple

    Para eliminar la recursión por izquierda se reescriben las reglas gramaticales divididas en dos

    Sea la gramática:

    ​ A → Aα | β

    una que primero genera β y la otra que genere las repeticiones de α utilizando recursividad por derecha :

    ​ A → β A'

    ​ A' → α A' | ε

    Otro ejemplo :

Sea la gramática :

​ exp → exp opsuma term | term

Se genera según la regla la siguiente gramática:

​ exp → term exp'

​ exp' → opsuma term exp' | ε

​

  1. Eliminación Recursión por la Izquierda Inmediata General

Sean las siguientes producciones:

​ A → A α1| A α2 |… | A αn | β1 | β2 | … | βm

Donde ninguna de la β comienza con A. En este caso la solución es semejante al caso simple:

​ A → β1 A'| β2A' | … | βmA'

​ A' → α1A'| α2A' |… | αn A' | ε

Ejemplo:

​ exp → exp + term | exp - term | term

Aplicando la regla general inmediata:

​

​ exp → term exp'

​ exp' → + term exp' | - term exp' | ε

​

  1. Eliminación de Recursión por Izquierda General:

A continuación se propone un algoritmo que elimina de forma sistemática la recursividad por la izquierda de una gramática. Esto se garantiza si la gramática no tiene ciclos ( derivaciones de A → +A) o producciones ε. Si los hubiera estos pueden eliminarse de la gramatica.

  • El algoritmo:
  • ENTRADA: La gramática G sin ciclos ni producciones ε().
  • SALIDA: Una gramática equivalente sin recursividad por la izquierda.
  • MÉTODO:

ordenar los nodos no terminales de cierta forma A1, … An

for ( cada i de 1 a n){ for ( cada j de 1 a i-1) { sustituir cada producción de la forma Ai → Ajγ por las producciones Ai -> δ1 γ() | …..| δkγ en donde Aj → delta1 | δ2 | ….. | δk sean todas producciones Aj actuales } Eliminar la recursividad inmediata por la izquierda entre la producciones Ai }

  1. Ejemplo

Intentar aplicar el algoritmo general:

S → Aa | b A → Ac | Sd | ε

Factorización#

La factorización por izquierda se requiere cuando dos o más opciones de reglas gramaticales comparten una cadena de prefijo común:

A → αβ | αγ

Un analizador sintáctico LL(1) no puede distinguir entre las opciones de producción en una sustitución de esta clase. Para solucionar esto es factorizar la α por la izquierda y volver a escribir la regla como dos reglas:

A → α A'

A' → β | γ

Otros ejemplos:

secuencia-sent → sent ; secuencia-sent | sent

sent → s

Al aplicar la factorización se obtiene dos reglas:

secuencia-sent → sent secuencia-sent'

secuencia-sent' → ; | ε

La gramática resultante :

secuencia-sent → sent secuencia-sent'

secuencia-sent' → ; | ε

sent → s

PRIMERO y SIGUIENTE#

(Aho:p221, lou:p168, Coo:p )

Si una gramática posee un conjunto de producciones en la cual no es posible determinar a ciencia cierta cual es la producción seleccionada por la cual se está derivando entonces, en la construcción de analizadores sintácticos descendientes ( y también ascendentes) se utilizan dos funciones auxiliares asociadas con la gramática G, PRIMERO() y SIGUIENTE():

Primero o First#

PRIMERO(α), donde α es cualquier cadena de símbolos gramaticales, como el conjunto de terminales que empiezan las cadenas derivadas a partir de α. Cómo se calcula el conjunto PRIMERO o First:

Si X es un símbolo de la gramática ( un terminal o un no terminal) o ε, entonces el conjunto Primero(X), compuesto de terminales, y posiblemente de ε, se define de la siguiente manera:

  1. Si X es un terminal o ε, entonces Primero(X)={X}.
  2. Si X es no terminal, entonces para cada selección de producción X -> X1 X2 … Xn, Primero(X) contiene Primero{X1} - ε.
  • Si también para cualquier i<n, todos los conjuntos Primeros(X1) -> Primero(xi, contienen ε, entonces Primero(X)=Primero(X1) -ε.
  • Si todos los conjuntos Primer(Xi) contiene ε, entonces Primero(X) contiene ε.

  1. El conjunto de PRIMEROS son aquellos caracteres que van a identificar en que producción estoy de las varias producciones de una gramática.

    Algunos ejemplos de la aplicación de estas reglas :

    A → tB entonces PRIMERO(A)={t}

    A → Bβ  entonces también PRIMERO(A)=PRIMERO(B)

  1. Ejemplo

    A → aC

    B → ε | m

    C → ε | s | y

​

Otra opción de ver la gramatica:

A → aC

B → ε

B → m

C → ε

C→ s

Nota: siempre conviene primero obtener los consjuntos primeros de las derivaciones con no terminales:

Paso 1: Obtengo las producciones que derivan en no terminales

no terminalPrimero
A{a}
B{m, ε }
C{s, ε}

Paso 2: De las producciones que derivan en no terminales elijo el primer no terminal y voy a su producción, hasta alcanzar a un terminal

  • En este caso no hay, es el caso más fácil

  1. Ejemplo

    S → ABCDE

    A → a | ε

    B → b | ε

    C → c

    D → d | ε

    E → e | ε

    Nota: siempre conviene primero obtener los conjuntos primeros de las derivaciones con no terminales:

    Paso 1: Obtengo las producciones que derivan en no terminales

    no terminalPrimero
    S{}
    A{a,ε}
    B{b,ε}
    C{c}
    D{d,ε}
    E{e,ε}

    Paso 2: De las producciones que derivan en no terminales elijo el primer no terminal y voy a su producción, hasta alcanzar a un terminal

    no terminalPrimero
    S{a,b,c}
    A{a,ε}
    B{b,ε}
    C{c}
    D{d,ε}
    E{e,ε}

  2. Ejemplo

    exp -> exp opsuma term | term

    opsuma -> + | -

    term -> term opmult term | factor

    opmult -> *

    factor -> ( exp ) | numero

    es conveniente separar las producciones que queden de a una:

nproducción
1exp -> exp opsuma term
2exp -> term
3opsuma -> +
4opsuma -> -
5term -> term opmult term
6term -> factor
7opmult -> *
8factor -> ( exp )
9factor -> numero

Nota: siempre conviene primero obtener los conjuntos primeros de las derivaciones con no terminales:

Paso 1: Obtengo las producciones que derivan en no terminales

no terminalPrimero
exp{}
opsum{+,-}
term{}
opmult{*}
factor{}

Paso 2: De las producciones que derivan en no terminales elijo el primer no terminal y voy a su producción, hasta alcanzar a un terminal

no terminalPrimero
exp{(,numero}
opsum{+,-}
term{(,numero}
opmult{*}
factor{(,numero}

  1. Ejemplo

    E → T E'

    E' → + T E' | ε

    T → F T'

    T' → * F T' | ε

    F → ( E ) | id

Nota: siempre conviene primero obtener los conjuntos primeros de las derivaciones con terminales:

Paso 1: Obtengo las producciones que derivan en no terminales

no terminalPrimero
E
E'{+, ε
T
T'{\*, ε}
F{ (, id}

Paso 2: De las produccciones que derivan en no terminales elijo el primer no terminal y voy a su producción, hasta alcanzar a un terminal

no terminalPrimero
E{ (, id}
E'{+, ε}
T{ (, id}
T'{\*, ε}
F{ (, id}

SIGUIENTE o Follow#

Se define SIGUIENTE(A), para el no terminal A, como el conjunto de terminales b que pueden aparecer de inmediato a la derecha de A en cierta forma de frase. Cómo se calcula:

Dado un nodo no terminal, el conjunto Siguiente(A), compuesto de terminales, y posiblemente de $ (fin de pila), se define de la siguiente manera:

  1. Si A es el símbolo inicial, entonces $ está en Siguiente(A).

  2. Si hay una producción B → α A γ, entonces Primero(γ) - {ε} está en Siguiente(A).

  3. Si hay una producción B → α A γ tal que ε está en Primero(γ), entonces Siguiente(A) contiene Siguiente(B).

  4. En otras palabras, el siguiente me indica que terminé con una producción, es decir cual es el terminal que se encuentra al finalizar esa producción

    Algunos ejemplos:

    B → AC entonces SIG(A)=PRIMERO(C)

    S → α entonces SIG(S)={$}

    B → Ac entonces el SIG(A)={c}

    B → cA entonces el SIG(A)= SIG(B) ya que A está al final de lo

    ​ que se reemplaza por B

    B → ε entonces SIG(P)={d}

    C → PBd

  1. Ejemplo 1

    S → ABCDE

    A → a | ε

    B → b | ε

    C → c

    D → d | ε

    E → e | ε

Nota: Se buscan los caracteres que indiquen que una producción ha terminado.

Paso 1: El siguiente del símbolo inicial es $

no terminalPrimeroSiguiente
S{a,b,c}{$}
A{a,ε}
B{b,ε}
C{c}
D{d,ε}
E{e,ε}

Paso 2: Se busca en cada aparicion del no terminal cual es el terminal que lo precede:

no terminalPrimeroSiguiente
S{a,b,c}{$}
A{a,ε()}{b,c}
B{b,ε()}{c}
C{c}{d,e,$}
D{d,ε()}{e,$}
E{e,ε()}{$}

  1. Ejemplo 2

    Otro Approach

    exp → exp opsuma term | term

    opsuma → + | -

    term → term opmult factor | factor

    pomult → *

    factor → ( exp ) | numero

Paso 1: Se obtiene el conjunto siguiente de la regla inicial

no terminalPrimeroSiguiente
exp{(,numero}{$}
opsum{+,-}{}
term{(,numero}{}
factor{(, numero}{}
opmult{* }{}

Paso 2: Por cada no terminal se analiza en que producciones aparece y se busca el primer terminal

no terminalPrimeroSiguiente
exp{(,numero}{$,+,-,)}{$}∪ PRIM(opsum) ∪ {)}
opsum{+,-}{(,numero}{PRIM(term)
term{(,numero}{*,$,+,-}{*} ∪ {PRIM(exp)
factor{*}{(, numero)}{SIG(term)}
opmult{(,numero}{*}{PRIM(facto)

  1. La tabla de analisis sintactico LL(1)

    Al utilizar el método sintáctico descripto, cuando un no terminal A esta en la parte superior de la pila de análisis sintáctico, debe tomarse una decisión, basada en el token de entrada actual (la búsqueda hacia adelante), que selecciona la regla gramatical que va a utilizar para A cuando se reemplaza en la pila.

    En contraste no es necesario tomar una decisión cuando el token esta en la parte superior de la pila, puesto que es el mismo que el token de entrada actual, y se presenta una coincidencia, o no lo es y se presenta un error.

    Se pueden expresar las selecciones posibles construyendo una tabla de análisis sintáctico LL(1) :

    • Una tabla de esta naturaleza es esencialmente un arreglo bidimensional indexado por no terminales y terminales que contienen opciones de producción a emplear en el paso apropiado del análisis sintáctico (incluyendo $ para representar el final de la entrada).

    • Se Llama a esta tabla M[N,T]. Se supone que la tabla M[N,T] inicia con todas sus entradas vacías. Cualquier entrada que permanezca vacía después de la construcción representa errores potenciales que se pueden presentar durante el análisis sintáctico. Se agrega selecciones u opciones de producción de acuerdo con las reglas siguientes:

      1. Si A->α es una opción de producción, y existe una derivación α =>aβ, donde a es un token, entonces se agrega A->α a la entrada en la tabla M[A,a].

      2. Si A->α es una opción de producción, y existen derivaciones α=>*ε, y S $=>*βAa γ, donde S es el símbolo inicial y a es un token (o $), entonces se agrega A->α a la entrada de la tabla M[A,a].

    • La idea de la primera regla es, dado un token a en la entrada, se desea seleccionar la regla S->α si α puede producir una a para comparar.

    • La idea de la segunda regla, es que si A deriva la cadena vacia ε , y si a es un tolken que puede venir legalmente después de A en una derivación, entonces se desea seleccionar A-> α para Hacer que A desaparezca.

    Nota: La tabla es una tabla dimensional , en la cual las columnas son los terminales, las filas son los no terminales. Y se llenan siempre PRI(dela parte derecha de la producción) a menos que A produzca un ε por ende se usa el siguiente.

  2. Algoritmo de Análisis Sintáctico LL(1) basado en Tabla

      while ()    {   if (tope_pila == terminal && siguite_token ==a)   {       //concuerda       pila_extraer();       avanzar_entrada();   }else if ( tope_pila == no_terminal_A && siguiente_token==a && M[A,a]== A->X1X2X3..Xn )   {      //generar      pila_extraer();      for(i=n; i>=1 ; n--) pila_insertar(xi);    }else error();      if (tope_pila ==$ && siguiente_token==$) aceptar();   else error;   }

Ejemplo integrado:#

Sea la gramática:

E → (L) | id

L → L;E | int E

Para construir un analizador sintáctico LL(1) hay que seguir los 5 pasos

  • Eliminar recursión a izquierda:

    ​ L→ L;E | int E hay recursión interna, se elimina de la siguiente forma:

    ​ L→ int E L' | int E

    ​ L'→ ;_EL' | ;_E

  • Factorizar a Izquierda

    L→ int E L' | int E

    L'→ ;EL' | ;E

    Factorizar la producción L→ int E L' | int E

    L→ int E W

    W→ L' | ε

    Factorizar la producción L'→ ;EL' | ;E

    L'→ ;E V

    V → L' | ε

    Al final nos queda

    E → (L) | id

    L→ int E W

    W→ L' | ε

    L'→ ; E W

  • PRIMEROS y SIGUIENTES

Primeros

NTPRIMEROSIGUIENTE
E{(,id}
L{int}
L'{;}
W{;, epsilon}

Siguientes

NTPRIMEROSIGUIENTE
E{( , id}{$, ; , ) }{$}∪{PRIM(W)}∪{SIG(L}
L{int}{)}SIG(L)={)}
L'{;}{)}SIG(L')=SIG(W)
W{;}{)}SIG(W)= SIG(L)

  • Armar la tabla de Parsing

    ()id;int$
    E
    L
    W
    L'

    Como se arma, recordar que en se toma la producción , se busca el PRIM(produc) ahí se escribe la regla

    Se toma la primera regla E→ (L) | id

    ()id;int$
    EE→ (L)E→ id
    L
    W
    L'

    Se toma la próxima regla L → int EW

    ()id;int$
    EE→ (L)E→ id
    LL→ int E W
    W
    L'

    Así sucesivamente

    ()id;int$
    EE→ (L)E→ id
    Lsyntax errorL→ int E W
    Ww→ εW→ L'
    L'L'→ ; E W
(int id ; id )$$
($)L(consumo
(int$)W E intconsumo
(int id$)W idconsumo
(int id ;$)L'reemplazo
(int id ;$)WE;consumo
(int id ; id$)Widconsumo
(int id ; id )$)Wreemplazo
(int id ; id )$)consumo
(int id ; id )$$ acepto