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:
- E -> T E’
- E’ -> + T E’
- E’ -> є
- T -> F T’
- T’ -> * F T’
- T’ -> є
- F -> id
- 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
:D Muy bien Cynthia buena guia
ResponderEliminarMuchas gracias Edith :D!
ResponderEliminarGracias! justo lo que buscaba!!
ResponderEliminar