domingo, 4 de noviembre de 2012

Analizador sintáctico LL : Guía


La siguiente guía es para realizar lo que vendría siendo sintaxis para un compilador.

Estos pasos son los que realicé en mi materia de Programación de Sistemas. Espero que te sea de ayuda.

Si deseas compartir este contenido, agradecería que me dieras los debidos créditos con un enlace a mi Blog :) ¡Muchas gracias!



Paso 1: Producciones.



Tenemos las siguientes producciones:

E -> E + T
E -> T
T -> T * F
T -> F
F -> id
F -> ( E )

Debemos observar con detenimiento lo que tenemos. 

Para poder avanzar con nuestro analizador LL primero debemos checar que estas producciones no caigan en ambigüedad ni en recursividad. Entendiendo por ambiguo que la producción pueda tener diferentes interpretaciones y prestarse a dudas, incertidumbre o confusión; y por recursividad que en algún momento se pueda repetir la producción.

Las producciones que podemos ver que caen en recursividad (señalado en negritas) son E y T. Si nos fijamos bien, E produce a E y T produce a T. En pocas palabras, se producen así mismas.

E -> E + T
E -> T
T -> T * F
T -> F
F -> id
F -> ( E )
.
En este caso no se presenta ambigüedad. En otro ejemplo lo veremos.

Lo que procede ahora es eliminar ésta recursividad (por su lado izquierdo) siguiendo ésta regla desarrollada en dos ejemplos:

Gramática recursiva
Gramática sin recursión
A -> A a | β


A -> β A’
A’ -> a A’
A’ -> є
Z -> float Z | int
Z -> int Z’
Z’ -> float Z’ | є

Retomando el primer ejemplo de la regla. Tenemos A y como podemos observar, se produce así misma. Para eliminar la recursividad tomaremos la producción que no la contiene (En este caso sería A -> β) y la pasaremos tal cual, agregándole que produce a A’.

Entonces, la otra producción con recursividad (A -> A a) será cambiada, siendo A’ quien la produzca; cuyo primer elemento a producir será a seguida por A’.   

Por último, para cerrar este ciclo, se agregará épsilon (є) a A’.

Aplicando la anterior regla a nuestras producciones iniciales, quedaría lo siguiente:

Producciones Iniciales
Producciones Finales
E -> E + T
E -> T
T -> T * F
T -> F
F -> id
F -> ( E )
E -> T E’
E’ -> + T E’
E’ -> є
T -> F T’
T’ -> * F T’
T’ -> є
F -> id
F -> ( E )



Paso 2: First y Follows.

Ahora tenemos que sacar los First y los Follows de las producciones.

Las reglas son las siguientes:

Reglas de los First

  • Es el primer elemento terminal que produce la producción y si este produce épsilon, también.
  • Si el primer elemento es no terminal, se tomara el First de ese elemento no terminal.
  • Si el primer elemento es un no terminal y este en su First tiene un épsilon, se toma todo el Fist de este excepto el épsilon y se pasa al siguiente elemento a la derecha. 

                                                                                                            

Reglas de los Follows                  

  • Es el siguiente elemento terminal a la derecha
  • Si el siguiente elemento a la derecha es un no terminal, es el First de ese elemento y en caso de que tenga épsilon se aplicara la regla 3 de los First.
  • Si es el último elemento de la producción, su Follow es el Follow de quien lo produce.
  • Existe una primera producción que no se toma en cuenta, la cual es P0 -> x$ por tal motivo el Follow de x también debe de tener el elemento $ y este solo se puede heredar a cada uno de sus elementos no terminales.            



Nuestra producción inicial será E.

Entonces tenemos que:
FIRST
FOLLOWS
F(E): id (
F(E): ) $
F(E’): + є
F(E’): ) $
F(T): id (
F(T): +  ) $
F(T’): * є
F(T’): +  ) $
F(F): id (
F(F): * + ) $
                                                                      
Cabe remarcar que en los Follows nunca debe de ir épsilon.   



                                                                   
Paso 3: Matriz.


Debemos tener en cuenta que en la matriz se puede reflejar un estado, épsilon, error de sincronización y un error común.

Para hacer la matriz, tenemos que colocar los elementos terminales contra los no terminales. También enumeraremos las producciones finales que teníamos.
Producciones Finales Enumeradas:

  1. E -> T E’
  2. E’ -> + T E’
  3. E’ -> є
  4. T -> F T’
  5. T’ -> * F T’
  6. T’ -> є
  7. F -> id
  8. F -> ( E )

Matriz

+
*
Id
(
)
$
E






E’






T






T’






F






           
Para llenar la matriz, nos basaremos en los First. Se pondrá el número de la producción (estado) en cada columna que cumpla con lo dicho. 

Por ejemplo, si la producción 1 (E) su First es T << id ( >>, colocaremos en la fila E, en las columnas id y paréntesis abierto ( ( ) el número 1.

La tabla con todos los First queda así: 

                                                                                                                         

+
*
Id
(
)
$
E


1
1


E’
2





T


4
4


T’

5




F


7
8



Después le siguen los Follows. Si en el First de la producción se encuentra un épsilon, los Follows de dicha producción tendrán el número designado a los épsilon (en este caso será el número 3).

Si no hay épsilon en el First de la producción, los Follows tendrán designados un número que simbolice el error de Sincronización (En este caso, el 500).

La tabla con todos los Follows quedaría de la siguiente manera:


+
*
Id
(
)
$
E


1
1
500
500
E’
2



3
3
T
500

4
4
500
500
T’
3
5


3
3
F
500
500
7
8
500
500

Los espacios en blanco serán los errores comunes. Se hacen a partir de los First.

Número de Error
Descripción
501
Se esperaba id (
502
Se esperaba +
503
Se esperaba *

Con esta información terminamos de llenar la Matriz.


+
*
Id
(
)
$
E
501
501
1
1
500
500
E’
2
502
502
502
3
3
T
500
501
4
4
500
500
T’
3
5
503
503
3
3
F
500
500
7
8
500
500

Y con esto ya podríamos comenzar a hacer la sintaxis de un compilador. Sólo tendrías que adaptarlo a tus producciones.

¡Saludos!
@Marceline


Share

Twitter Delicious Facebook Digg Stumbleupon Favorites More