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

Question

Estoy tratando de aprender cómo 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 son: Bottom-Up Parsing, Top-Down Parsing, Formal Grammars. La imagen que se muestra proviene de: Miscellanous Parsing. Todos provienen de la clase CS143 de Stanford.

Aquí están los puntos:

0) ¿Cómo (ambigua/sin ambigüedades) y (izquierda-recursivo/derecha-recursivo) influyen en 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 sintáctico. 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: Respuestas a here]

2.1) Pero aún así, es la ambigüedad de la gramática 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 es así, 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 (*), por lo que se pueda imaginar, 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, las gramáticas ambiguas conducen a reducir-reducir y reducir-reducir conflictos. 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?

[EDIT: si. ]

5) Dar G1:

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

5,1) G1 se dejó tanto recursivo, derecha recursiva, 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 ambiguo G2? ¿Un analizador para G2 necesita dos lookaheads?Por factorización tenemos:

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

5,3) Ahora, hace un analizador para G3 necesitan sólo una búsqueda hacia delante? ¿Cuáles son las contrapartes para hacer estas transformaciones? ¿Es LR (1) el analizador mínimo requerido?

5.4) G1 se deja recursiva, con el fin de analizarlo con un analizador LL, una necesidad de transformarlo en un derecho gramática recursiva:

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

continuación

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

5,5) ¿El 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 pidiendo mucho, y realmente no espero una respuesta completa, de todos modos cualquier ayuda sería muy apreciada.

Thx for reading!

Answer 1

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

Por lo general, usted puede elegir la que cumpla los siguientes criterios:

• conceptualmente tan simple como usted puede hacerlo (implicación: más pequeño que otros)
• pistas de la terminología en el manual de referencia langauge cuando sea posible
• menor cantidad de flexión para cumplir con las limitaciones de su generador de análisis

Esto último puede hacer un lío de 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 totalmente libres de contexto. GLR parsing tiene esta ventaja muy significativa. Lo he usado durante 15 años y he hecho docenas de lenguajes reales con él.