Construyendo árboles de análisis con retroceso.

Question

Estoy experimentando para analizar mi tiempo libre, y quería implementar un analizador de reducción de turnos para una gramática muy muy simple. He leído muchos artículos en línea, pero todavía estoy confundido sobre cómo crear árboles de análisis. Aquí hay un ejemplo de lo que quiero hacer:

---

gramática:

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

Aquí hay una entrada de ejemplo:

1 + 1 + 1 + 1

que, después de la tokenización, se convierte en:

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

---

Entiendo que:

1. cambiando significa empujar el primer token de entrada en la pila y eliminarla de la entrada
2. reduciendo significa sustituir uno o más elementos en la pila con un elemento gramático

Entonces, básicamente, esto debería suceder:

Step 1:
    Stack:
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Stack is empty. Shift.

Step 2:
    Stack: TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.

Step 3:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 4:
    Stack: Expr TKN_Op 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 5:
    Stack: Expr TKN_Op TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.
    // What should I check for reduction? 
    // Should I try to reduce incrementally using 
    // only the top of the stack first, 
    // then adding more stack elements if I couldn't
    // reduce the top alone?

Step 6:
    Stack: Expr TKN_Op Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: Expr TKN_Op Expr can be reduced to Expr. Reduce.

Step 7:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: ...
    // And so on...

Aparte de la "¿Qué para reducir?" duda, no tengo ni idea de cómo construir correctamente un árbol de parse. El árbol probablemente debería parecer esto:

1    +    o
          |
     1    +    o
               |
          1    +    1

¿Debo crear un nuevo nodo en la reducción?

¿Y cuándo debo agregar a los niños al nodo recién creado / cuándo debo crear un nuevo nodo raíz?

Answer 1

Lo simple y obvio que debe hacer es crear un nodo de árbol en cada reducción, y agregar los nodos de los árboles de los elementos de la gramática que se redujeron a ese nodo de árbol.

Esto se administra fácilmente con una pila de nodos que se ejecuta en paralelo a la pila de "token de cambio" que utiliza el analizador en bruto. Para cada reducción de una regla de longitud n, la pila de token de turno se acorta por N, y se empuja el token antieminal en la pila de cambios. Al mismo tiempo, acorte la pila de nodos Extracción de los nodos principales N, cree un nodo para el antiérmino, se adjuntan los nodos N (los niños, y empuje ese nodo en la pila del nodo.

Esta política incluso funciona con reglas que tienen un lado derecho de longitud cero: cree un nodo de árbol y adjunte el conjunto vacío de niños (por ejemplo, cree un nodo de hoja).

Si piensa en un "cambio" en un nodo terminal como una reducción (de los caracteres que forman el terminal) al nodo terminal, luego los cambios de nodo terminal se ajustan a la derecha. Cree un nodo para el terminal y presúnelo hacia arriba. la pila.

Si lo hace, obtiene un "árbol de sintaxis / sintaxis de concreto" que coincide con la gramática isomórfica. (Hacemos esto por una herramienta comercial que ofrezco). Hay mucha gente que no le gustan los árboles tan concretos, porque contienen nodos para palabras clave, etc., que realmente no agregan mucho valor. Es cierto, pero tales árboles son sumamente fáciles de construir, y supremamente fácil de entender porque la gramática es la estructura del árbol. Cuando tengas 2500 reglas (como lo hacemos para un parser COBOL completo), esto importa. Esto también es conveniente porque todo el mecanismo se puede construir completamente en la infraestructura de análisis. El ingeniero de gramática simplemente escribe reglas, el analizador corre, Voila, un árbol. También es fácil cambiar la gramática: simplemente cambiarla, Voila, todavía obtienes árboles de análisis.

Sin embargo, si no desea un árbol de concreto, por ejemplo, desea un "árbol de sintaxis abstracto", entonces lo que tiene que hacer es dejar que el ingeniero de gramática sea controle qué reducciones generan nodos; Por lo general, agregue algún accesorio de procedimiento (código) a cada regla de la gramática que se ejecutará en una etapa de reducción. Luego, si hay algún accesorio de procedimiento, produce un nodo, se conserva en una pila de nodos. Cualquier accesorio de procedimiento que produce un nodo debe adjuntar nodos producidos por los elementos de la mano derecha. Si es así, esto es lo que YACC / BISON / ... la mayoría de los motores de analizador de reducción de turnos lo hacen. Ve a leer sobre yacc o bisonte y examina una gramática. Este esquema le da mucho control, al precio de insistir en que tome ese control. (Para lo que hacemos, no queremos este esfuerzo de ingeniería en la construcción de una gramática).

En el caso de producir CSTS, es conceptualmente sencillo eliminar los nodos "inútiles" de los árboles; Hacemos eso en nuestra herramienta. El resultado es mucho como un AST, sin el esfuerzo manual para escribir todos esos archivos adjuntos de procedimiento.

Answer 2

La razón de su problema es que tiene un cambio / reducir el conflicto en su gramática:

expr: expr OP expr
    | number

Puede resolver esto de 2 maneras:

expr: expr OP number
    | number

para operadores asociativos izquierdos, o

expr: number OP expr
    | number

para los asociativos derechos. Esto también debe determinar la forma de su árbol.

La reducción generalmente se realiza cuando se detecta una cláusula completa. En el caso asociativo adecuado, comenzaría en un estado 1 que espera un número, lo empuja a la pila de valor y se desplaza a estado 2. En estado 2, si el token no es un OP, puede reducir un número a un expr. . De lo contrario, presione el operador y cambie a estado 1. Una vez que se complete el estado 1, puede reducir el número, el operador y la expresión a otra expresión. Nota, necesita un mecanismo para "volver" después de una reducción. El analizador general comenzaría entonces en estado 0, por ejemplo, que inmediatamente va al estado 1 y acepta después de la reducción.

Tenga en cuenta que las herramientas como YACC o Bison hacen que este tipo de cosas sea mucho más fácil porque traen todas las maquinarias de bajo nivel y las pilas.