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

gramatica para compiladores

Question

¿Hay una manera simple de determinar si una gramática es LL (1), LR (0), SLR (1) ... solo al mirar la gramática sin hacer ningún análisis complejo?

Por ejemplo: para decidir si una Gramática BNF es LL (1), debe calcular los conjuntos Primero y Seguir, lo que puede llevar mucho tiempo en algunos casos.

Alguien tiene una idea de cómo hacer esto más rápido? ¡Cualquier ayuda realmente sería apreciada!

Answer 1

Directamente del libro "Compiladores: Principios, técnicas y herramientas" por Aho, et. Alabama.

Página 223:

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

1. Para ninguna terminal "a", las cadenas alfa y beta derivan cadenas que comienzan con "a"
2. Como máximo, uno de alfa y beta puede derivar la cadena vacía
3. Si beta puede alcanzar la transición vacía mediante cero o más transiciones, entonces alfa no deriva ninguna secuencia que comience con un terminal en SEGUIR (A). Del mismo modo, si alfa puede alcanzar la transición vacía a través de cero o más transiciones, entonces beta no deriva ninguna secuencia que comience con un terminal en SEGUIMIENTO (A)

Esencialmente, se trata de verificar que la gramática pase la Prueba de disociación por pares y que no involucre la recursividad izquierda. O, de forma más sucinta, una gramática G que es recursiva a la izquierda o ambigua no puede ser LL (1).

Answer 2

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 | un

no es LL (1), mientras

A → a | segundo

es.

Pero cuando te vuelves más complejo que eso, necesitarás hacer un análisis.

A → B | un
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 {''+'' término}
término → factor {''*'' factor}
factor → número | ''('' expr '')''

Esta gramática solo maneja la multiplicación y la suma, y ​​ya no está claro si la gramática es LL (1). Todavía es posible evaluarlo mirando 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 completo, es casi seguro que va a tomar algún análisis complejo.

Dicho esto, hay algunas señales reveladoras obvias de que la gramática no es LL (1), como la A → A + A anterior, y si puede encontrar algo de esto en su gramática, sabrá que debe ser reescrito si estás escribiendo un analizador de descenso recursivo. Pero no hay atajos para verificar que la gramática sea LL (1).

Answer 3

Primero, un poco de pedantería. No puede determinar si un idioma es LL (1) al inspeccionar una gramática, solo puede hacer afirmaciones sobre la gramática en sí. Es perfectamente posible escribir gramáticas que no sean LL (1) para los idiomas para los cuales existe una gramática LL (1).

Con eso fuera del camino:

• Puede escribir un analizador para la gramática y hacer que un programa calcule primero y seguir los conjuntos y otras propiedades por usted. Después de todo, esa es la gran ventaja de las gramáticas BNF, son máquinas comprensibles.

• Inspeccione la gramática y busque violaciones de las restricciones de varios tipos de gramática. Por ejemplo: LL (1) permite la recursión correcta pero no la izquierda, por lo tanto, una gramática que contiene la recursividad a la izquierda no es LL (1). (Para otras propiedades gramaticales, vas a tener que pasar un buen rato con las definiciones, porque no puedo recordar nada más en este momento :).

Answer 4

Un aspecto, "es el lenguaje / gramática ambigua", es una pregunta indecidible conocida, como la correspondencia postal y los problemas de halting .

Answer 5

Verifica 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).

Answer 6

ya hay atajos para ll (1) gramática

1) si A-> B1 | B2 | ....... | Bn luego primero (B1) intersección primero (B2) intersección .primero (Bn) = conjunto vacío entonces es ll (1) gramática

2) si A-> B1 | epsilon, entonces la intersección B1 sigue (A) es un conjunto vacío

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

Answer 7

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

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