parsing - sintactico - ¿Qué hay de estas gramáticas y el analizador mínimo para reconocerlo?

qué es un analizador lexico

Question

Estoy tratando de aprender a hacer un compilador. Para hacerlo, leo mucho sobre el lenguaje sin contexto. Pero hay algunas cosas que aún no puedo resolver.

Como es mi primer compilador, hay algunas prácticas que no conozco. Mis preguntas se tienen en cuenta para construir un generador de analizadores, no un compilador ni un lector. Algunas preguntas pueden ser obvias ..

Entre mis lecturas están: Análisis ascendente , Análisis descendente , Gramáticas formales . La imagen que se muestra proviene de: Análisis misceláneo . Todos provienen de la clase CS143 de Stanford.

Aquí están los puntos:

0) ¿Cómo influyen (ambiguo / no ambiguo) y (recursivo a la izquierda / recursivo a la derecha) las necesidades de un algoritmo u otro? ¿Hay otras formas de calificar una gramática?

1) Una gramática ambigua es aquella que tiene varios árboles de análisis. Pero, ¿no debería la elección de derivación más a la izquierda o derivación a la derecha conducir a la unicidad del árbol de análisis sintáctico?

[EDIT: respondido aquí ]

2.1) Pero aún así, ¿la ambigüedad de la gramática está relacionada con k? Me refiero a dar una gramática LR (2), ¿es ambiguo para un analizador LR (1) y no ambiguo para un LR (2) uno?

[EDITAR: No, no lo es, una gramática LR (2) significa que el analizador necesitará dos tokens de anticipación para elegir la regla correcta para usar. Por otro lado, una gramática ambigua es aquella que posiblemente conduzca a varios árboles de análisis sintáctico. ]

2.2) Entonces, un analizador LR (*), mientras puedas imaginarlo, no tendrá ninguna gramática ambigua y luego podrá analizar todo el conjunto de idiomas libres de contexto.

[EDITAR: Respondido por Ira Baxter, LR (*) es menos poderoso que GLR, ya que no puede manejar múltiples árboles de análisis sintáctico. ]

3) Dependiendo de las respuestas anteriores, lo que sigue puede ser contradictorio. Teniendo en cuenta el análisis de LR, ¿las gramáticas ambiguas desencadenan un conflicto de desplazamiento-reducción? ¿Puede una gramática inequívoca activar uno también? De la misma manera, ¿qué pasa con los conflictos de reducción-reducción?

[EDITAR: esto es todo, las gramáticas ambiguas llevan a los conflictos reducir-reducir y reducir-reducir. Por contrapositivo, si no hay conflictos, la gramática es unívoca. ]

4) La capacidad de analizar la gramática recursiva a la izquierda es una ventaja del analizador LR (k) sobre LL (k), ¿es la única diferencia entre ellos?

[EDITAR: sí. ]

5) Dar G1:

G1 :
S -> S + S
S -> S - S
S -> a

5.1) G1 es a la vez recursivo a la izquierda, recursivo a la derecha y ambiguo, ¿estoy en lo cierto? ¿Es una gramática LR (2)? Uno lo haría inequívoco:

G2 :
S -> S + a
S -> S - a
S -> a

5.2) ¿Sigue siendo G2 ambiguo? ¿Un analizador para G2 necesita dos lookaheads? Por factorización tenemos:

G3 :
S -> S V
V -> + a
V -> - a
S -> a

5.3) Ahora, ¿un analizador para G3 necesita solo un vistazo anticipado? ¿Cuáles son las contrapartes para hacer estas transformaciones? ¿Es LR (1) el analizador mínimo requerido?

5.4) G1 se deja recursivo, para analizarlo con un analizador LL, hay que transformarlo en una gramática recursiva correcta:

G4 :
S -> a + S
S -> a - S
S -> a

entonces

G5 :
S -> a V
V -> - V
V -> + V
V -> a

5.5) ¿G4 necesita al menos un analizador LL (2)? G5 solo es analizable por un analizador LL (1), G1-G5 define el mismo idioma, y ​​este es (a (+/- a) ^ n). Es verdad ?

5.6) Para cada gramática G1 a G5, ¿cuál es el conjunto mínimo al que pertenece?

6) Finalmente, dado que muchas gramáticas distintas pueden definir el mismo idioma, ¿cómo se elige la gramática y el analizador asociado? ¿Es el árbol de análisis resultante imortante? ¿Cuál es la influencia del árbol de análisis sintáctico?

Estoy preguntando mucho, y realmente no espero una respuesta completa, de todos modos cualquier ayuda sería muy apreciada.

Thx para leer!

Answer 1

"Muchas gramáticas pueden definir el mismo idioma, ¿cómo se elige ...?"

Generalmente, eliges el que cumple con los siguientes criterios:

• conceptualmente tan simple como usted puede hacerlo (implicación: más pequeño que otros)
• rastrea la terminología en el manual de referencia de idioma siempre que sea posible
• menor cantidad de flexión para cumplir con las restricciones de su generador de analizadores

Ese último puede arruinar su simplicidad conceptual, y su tabla de varios estilos de analizador muestra la cantidad de problemas diferentes que enfrenta dependiendo de su elección de generador. Esto se ve agravado por el hecho de que la elección a menudo se realiza mucho antes de que realmente elijas la gramática.

Una forma de minimizar la flexión gramatical es elegir un generador de analizador que maneje gramáticas completamente libres de contexto. El análisis de GLR tiene esta ventaja muy significativa. Lo he usado durante 15 años y he hecho docenas de lenguajes reales con él.