Cómo determinar si un idioma es LL(1) LR(0) SLR(1)

En respuesta a su pregunta principal: Para una gramática muy simple, puede ser posible determinar si es LL(1) sin construir PRIMERO y SEGUIR conjuntos, por ejemplo,

A → A + A / a

No es LL (1), mientras que

A → a / b

Es.

Pero cuando usted consigue más complejo que eso, usted necesitará hacer un cierto análisis.

A → B / a
B → A + A

Esto no es LL (1), pero puede no ser inmediatamente obvio

Las reglas gramaticales para la aritmética se vuelven rápidamente muy complejas:

Expr → term {'+'term }
término → factor {'*'factor }
factor → número / '('expr') '

Esta gramática solo maneja la multiplicación y la suma, y ya no está claro de inmediato si la gramática es LL(1). Todavía es posible evaluarlo mirando a través de la gramática, pero a medida que la gramática crece se vuelve menos factible. Si estamos definiendo una gramática para un lenguaje de programación, es casi seguro que va a tomar algún análisis complejo.

Dicho esto, hay algunos signos reveladores obvios de que la gramática no es LL(1) - como la A → A + A anterior - y si puedes encontrar cualquiera de estos en tu gramática, sabrás que necesita ser reescrita si estás escribiendo un analizador de descenso recursivo. Pero no hay atajo para verificar que la gramática es LL(1).

Un aspecto, "es el lenguaje/gramática ambiguo", es una pregunta indecidible conocida como el Correo correspondencia y detener problemas.

Directamente del libro "Compilers: Principles, Techniques, & Tools" por Aho, et. al.

Página 223:

Una gramática G es LL(1) si y solo si siempre que A - > alfa | beta son dos producciones distintas de G, se cumplen las siguientes condiciones:

1. Para ninguna terminal "a", ambos alpha y beta derivan cadenas que comienzan con " a "
2. A lo sumo uno de alfa y beta puede derivar el vacío string
3. Si beta puede alcanzar la transición vacía a través de cero o más transiciones, entonces alpha no deriva ninguna cadena que comience con un terminal en FOLLOW(A). Del mismo modo, si alpha puede alcanzar la transición vacía a través de cero o más transiciones, entonces beta no deriva ninguna cadena que comience con un terminal en FOLLOW (A)

Esencialmente, esto es una cuestión de verificar que la gramática pase la Prueba de Incongruencia de Pares y también no implica Recursión izquierda. O más sucintamente una gramática G que es recursiva a la izquierda o ambigua no puede ser LL (1).

Compruebe si la gramática es ambigua o no. Si lo es, entonces la gramática no es LL(1) porque ninguna gramática ambigua es LL(1).

Ya hay atajos para la gramática ll(1)

1) si A->B1|B2|......./ Bn entonces primero (B1) intersección primero (B2) intersección .first(Bn)=empty set then it is ll (1) grammar

2) si A- > B1 / epsilon entonces B1 intersección seguir (A)está vacío conjunto

3) si G es cualquier gramática tal que cada no terminal deriva solo una producción entonces la gramática es LL (1)

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id

• Construya el DFA LR(0), el SIGUIENTE conjunto para E y las tablas de acción/goto SLR.
• ¿Es esto una gramática LR(0)? Prueba tu respuesta.
• Usando las tablas SLR, muestra los pasos (cambios, reducciones, aceptar) de un analizador LR parsing:
  id ( id + id )