generacion de matriz predictiva

6.6 GENERACION DE MATRIZ PREDICTIVA (CALCULO FIRST Y FOLLOW)

FIRST: Sea G := (V; ∑; Q0; P) una gramática libre de contexto. Para cada forma sentencial α Є (V U ∑)* y para cada k Є N definiremos la función.


En otras palabras, el operador F IRST k asocia a cada forma sentencial los primeros k símbolos de cualquier forma terminal alcanzable desde α mediante derivaciones “masa laizquierda". 

FOLLOW: Con las mismas notaciones anteriores, para cada forma sentencial α Є (V U ∑)*  definiremos la función FOLLOWG GK (α) del modo siguiente.

De nuevo nos ocuparemos solamente de FOLLOW: = FOLLOW1. Obsérvese que FOLLOW k (α) ⊂ ∑* y que para cada x Є FOLLOW (α), Ixl ≤ k. Obsérvese que para cada variable A Є V, FOLLOW(A) son todos los símbolos terminales que pueden aparecer a la derecha deA en alguna forma sentencial de la gramática.
Una Gramática LL1 es aquella gramática que no tiene recursión izquierda y no tiene ambigüedad, existen técnicas para eliminar la recursión izquierda y con eso convertirla a una gramática LL1 Cuando tienes una Gramática LL1 entonces utilizas lo que denominas como First y Follow. Lo que haces es sacar con una serie de reglas (siguiendo un algoritmo)todos los first y follows de la gramática.
Los First y Follows son significados para verificar y construir parsers predictivos, son un conjunto de tokens que se encuentran en el tope de la pila.
Pseudocódigo y algoritmo para calcular los First de una gramática:

1.-Si X es un terminal FIRST (X) = {X}

2.-Si X -> e es una producción e (pertenece) FIRST(X) 3.-Si X -> Y1Y2....Yn es unaproducción.
a.FIRST(Y1) (es subconjunto de) FIRST(X)
b.Si e (pertenece) FIRST(YK) (para todo) k< i
FIRST(Yi) (es subconjunto de) FIRST(X)
c.Si e (pertenece) FIRST(YK) (para todo) I ≤ n e
(pertenece a) FIRST(X)

Nota (a, b y c pertenecen al paso 3 y solo se toma uno dependiendo el caso)
Algoritmo para calcular los follows:

1.-Si S es el axioma $ (pertenece) FOLLOW(S)2.-Si A-> αBβ es una producción
FIRST(β)- { e } (es subconjunto de) FOLLOW(S)
1.- Si hay una producción A -> αB o A -> αBβ
Con e (pertenece) FIRST(β)
FOLLOW(A) (es subconjunto de) FOLLOW(B)

Te pongo un ejemplo:
E -> TE’
E’ -> +TE’ | e
T -> FT’
T’ -> *FT’ | e
F -> (E) | id

FIRST(E) = FIRST(T) = FIRST(F) = {(, id}.
FIRST(E’) = {+, e }
FIRST(T’) = {*, e }
FOLLOW(E) =FOLLOW(E’) = {), $}
FOLLOW(T) = FOLLOW(T’) = {+,), $}
FOLLOW(F) = {+,*,), $}


Una vez que tienes los first y follows entonces puedes crear una tabla de símbolos y con ella puedes construir un compilador que te reconozca y la sintaxis de las instrucciones son correctas o no con las reglas de tu lenguaje definido en la gramática.
Se utiliza Flex y Bison para poder hacer los reconocedoresléxicos y sintácticos, insertándolos en programas en C para que generes las reglas provenientes de tus tablas y finalmente hacer tu compilador.


Predictivo se menciona porque los reconocedores son predicitivos, es decir si tú tienes un if, ya sabes que puedes o no tener un else y puedes tener reconocedores predictivos botton-up (de abajo hacia arriba), o top-down (de arriba hacia abajo).Pseudocódigo pues solamente es una serie de instrucciones para representar un algoritmo pero de una forma informal, es decir, no con un lenguaje de programación. Comúnmente se hacen en inglés y todas las reglas para sacar first, follows y tabla de símbolos te vienen en un pseudocódigo para que lo sigas y obtengas todo.

Finalmente, la notación BNF es una forma de escribir las gramáticas deuna manera formal, te pongo un ejemplo de una sencilla:
1. ::= |
|
2. ::=

3. ::= |

4. ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |




FIRST
Si α es cualquier cadena de símbolos gramaticales, se considera FIRST (α) como el conjunto de
terminales que encabezan las cadenas derivadas de α. Si α =
*
=> λ, entonces λ también está en
FIRST (α).
Para calcular...