la conversión de una gramática en LL (1) gramática: algunos problemas

Question

Esto no es exactamente la tarea, sino que está relacionado con mis estudios:

Una gramática, por ejemplo, es como:

E -> E + E | E * E | -E | (E) | Identificación del

Después de la eliminación de la ambigüedad se convierte en (a partir de menor precedencia del operador)

E->-F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

Y después de la eliminación de la recursión por la izquierda y factoring izquierda (no es necesario en este caso) la gramática última LL1 es:

E->-F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

que da una tabla analizador libre de errores, que trabaja muy bien. Ahora sobre el problema que estoy enfrentando, supongamos que la gramática es la siguiente:

E -> E + E | E * E | id = E | (E) | Identificación del

Ahora no puedo generar una tabla de análisis sin conflictos, lo que significa que mi gramática final no es LL1. Estos son los pasos:

después de la eliminación de la ambigüedad:

E->id=F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

y después de la eliminación de la recursión por la izquierda y factoring izquierda, la gramática se convierte en:

E->id=F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

Pero hay un conflicto en la tabla de Analizador que no puedo eliminar, lo que significa que hay algún paso que me he perdido, o hay algún error en los pasos que no puedo encontrar. Por favor, dime qué he hecho mal y cómo solucionarlo. He estado trabajando en este problema desde hace mucho tiempo.

Answer 1

Digamos que:

E -> E+E|E*E|id=E|(E)|id 

se convertirá en:

E -> E+E|E*E|(E)|E' 
E' -> id=E|id 

entonces usted puede ir con la eliminación de la ambigüedad y la izquierda recursividad y obtener:

E -> GF  FIRST(E) = FIRST(G) 
F -> +GF|e 
G -> HG'  FIRST(G) = FIRST(H) 
G' -> *HG'|e 
H -> (E)|E' FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE'' FIRST(E') = {id} 
E'' -> =E|e FIRST(E'') = {=} + {#} 

Por supuesto, el problema es que pierdes la precedencia dada por el operador.

El gramática no será LL (1) si para cualquier no terminal N, habrá cualesquiera elementos comunes en FIRST(N -> a) y FIRST(N -> b) para N -> a, N -> b ser diferentes producciones de N.

Como ve, agregar una producción N -> id= en en cualquier otro lugar rompería esa regla.

Puede crear una gramática LL(2) (pero probablemente esto no es lo que quiere), que puede tener producción id=E en cualquier lugar. (Los conjuntos FIRST2 constan de cadenas de 2 elementos).

Además, si nos fijamos en la gramática se presenta una vez más:

E -> E+E|E*E|id=E|(E)|id 

Es una alta probabilidad, que la prioridad de los operadores que hice en la solución anterior es el más adecuado para su aplicación real. ¡Echale un vistazo!