De reducción por desplazamiento: cuando parar reducir?

Question

Estoy tratando de aprender acerca de desplazamiento y reducción de análisis. Supongamos que tenemos la siguiente gramática, utilizando reglas recursivas que hacen cumplir el orden de operaciones, inspirado en el ANSI C Yacc gramática :

S: A;

P
    : NUMBER
    | '(' S ')'
    ;

M
    : P
    | M '*' P
    | M '/' P
    ;

A
    : M
    | A '+' M
    | A '-' M
    ;

Y queremos analizar 1 + 2 con desplazamiento y reducción de análisis. En primer lugar, el 1 se desplaza como un número. Mi pregunta es, ¿es entonces reducido a P, entonces M, A, S, finalmente? ¿Cómo sabe dónde parar?

Supongamos que reduce todo el camino a S, entonces turnos '+'. ahora tendríamos una pila que contiene:

S '+'

Si cambiamos '2', las reducciones podrían ser:

S '+' NUMBER
S '+' P
S '+' M
S '+' A
S '+' S

Ahora, a cada lado de la última línea, S podría ser P, M, A, o número, y todavía sería válido en el sentido de que cualquier combinación sería una representación correcta del texto. ¿Cómo funciona el programa de análisis "saber" para que sea

A '+' M

Así que puede reducir toda la expresión a A, entonces S? En otras palabras, ¿cómo sabe en dejar de reducir antes de pasar al siguiente token? ¿Es esta una de las principales dificultades en la generación de analizador sintáctico LR?

---

Editar:. Una adición a la pregunta sigue

Ahora supongamos 1+2*3 de análisis. Algunos de desplazamiento / reducción operaciones son las siguientes:

Stack    | Input | Operation
---------+-------+----------------------------------------------
         | 1+2*3 | 
NUMBER   | +2*3  | Shift
A        | +2*3  | Reduce (looking ahead, we know to stop at A)
A+       | 2*3   | Shift
A+NUMBER | *3    | Shift (looking ahead, we know to stop at M)
A+M      | *3    | Reduce (looking ahead, we know to stop at M)

Es esto correcto (de acuerdo, no es analizada completamente todavía)? Por otra parte, no lookAhead por 1 símbolo también decirnos no reducir A+M a A, ya que al hacerlo daría lugar a un error de sintaxis inevitable después de leer *3?

Answer 1

El problema que describes es un problema con la creación de programas de análisis LR(0) - es decir, programas de análisis de abajo hacia arriba que no hacen ninguna búsqueda hacia delante a los símbolos más allá de la actual que se está analizando. La gramática que has descrito no parece ser una gramática LR(0), por lo que se ejecuta en problemas al tratar de analizarlo w / o búsqueda hacia delante. Es no aparecerá para ser LR(1), sin embargo, así que mirando 1 símbolo por delante de la entrada que puede fácilmente determinar si se debe trasladar o reducir. En este caso, un analizador LR(1) sería mirar hacia adelante cuando se tuvo la 1 en la pila, ver que el siguiente símbolo es un +, y darse cuenta de que no debería reducir A pasado (ya que es la única cosa que podría reducir a la seguiría siendo coincidir con una regla con + en la segunda posición).

Una propiedad interesante de las gramáticas LR es que para cualquier gramática que es LR(k) para k>1, es posible construir una gramática LR(1) que es equivalente. Sin embargo, la misma no se extiende todo el camino hasta LR(0) -. Hay muchas gramáticas que no se pueden convertir en LR(0)

Vea aquí para más detalles sobre LR(k)-dad:

http://en.wikipedia.org/wiki/LR_parser

Answer 2

No estoy exactamente seguro de la Yacc / Bison análisis de algoritmo y cuando se prefiere el desplazamiento sobre la reducción, sin embargo sé que soporta bisonte LR (1) análisis que significa que tiene una búsqueda hacia delante token. Esto significa que las fichas no se pasan a la pila de inmediato. Sino que esperan hasta que no hay más reducciones pueden suceder. Entonces, si el desplazamiento de los siguientes marcas simbólicas sienten que se aplica esa operación.

En primer lugar, en su caso, si usted está evaluando 1 + 2, que se desplazará 1. Se reducirá esa señal a una A porque el '+' lookahead símbolo indica que el curso de su única válida. Puesto que no hay más reducciones, que se desplazará el signo '+' de token en la pila y mantenga 2 como la búsqueda hacia delante. Será desplazar el 2 y reducir a un M desde A + M produce una A y la expresión es completa.