Problema de implementación del generador de parásitos LALR

Question

Actualmente estoy tratando de implementar un generador de analizadores LALR como se describe en "principios y herramientas de los compiladores" (también llamado "libro de dragones").

Mucho ya funciona. El generador de analizador actualmente puede generar el goto-gráfico completo.

Example Grammar: 
        S' --> S 
        S --> C C 
        C --> c C 
        C --> d 

Nonterminals: S', S, C 
Terminals: c, d 
Start: S' 

El goto-gráfico:

I[0]---------------+  I[1]-------------+ 
| S' --> . S , $ |--S-->| S' --> S . , $ | 
| S --> . C C , $ |  +----------------+ 
| C --> . c C , c | 
| C --> . c C , d |  I[2]--------------+ 
| C --> . d , c |  | S --> C . C , $ |  I[3]--------------+ 
| C --> . d , d |--C-->| C --> . c C , $ |--C-->| S --> C C . , $ | 
+------------------+  | C --> . d , $ |  +-----------------+ 
    | |     +-----------------+ 
    | |   +--c--+ |  | 
    | |   |  | c  | 
    | |   |  v v  | 
    | |  I[4]--------------+ | 
    | c  | C --> c . C , c | | 
    | |  | C --> c . C , d | | 
    | |  | C --> c . C , $ | d 
    | |  | C --> . c C , c | | 
    | +---->| C --> . c C , d | | 
    |  | C --> . c C , $ | | 
    d  | C --> . d , c |--+ | 
    | +-----| C --> . d , d | | | 
    | |  | C --> . d , $ | | | 
    | |  +-----------------+ | | 
    | C       | | 
    | |  I[6]--------------+ | | 
    | |  | C --> c C . , c | d | 
    | +---->| C --> c C . , d | | | 
    |  | C --> c C . , $ | | | 
    |  +-----------------+ | | 
    |        | | 
    |  I[5]------------+ | | 
    |  | C --> d . , c |<---+ | 
    +------->| C --> d . , d |  | 
      | C --> d . , $ |<-----+ 
      +---------------+ 

que tienen Trubbles con la implementación del algoritmo para generar la tabla de acciones-! Mi algoritmo calcula el siguiente resultado:

state | action  
     | c | d | $ 
------------------------ 
    0 | s4 | s5 | 
------------------------ 
    1 |  |  | acc 
------------------------ 
    2 | s4 | s5 | 
------------------------ 
    3 |  |  | r? 
------------------------ 
    4 | s4 | s5 | 
------------------------ 
    5 | r? | r? | r? 
------------------------ 
    6 | r? | r? | r? 

sx ... a cambiar de estado x
rx ... reducir al estado x

El r? significa que no sé cómo obtener el estado (¿el?) al cual el analizador debe reducir. ¿Alguien sabe un algoritmo para obtener? usando el goto-gráfico de arriba?

Si algo no se describe con suficiente claridad, por favor pregunte e intentaré explicarlo mejor! ¡Gracias por su ayuda!

Answer 1

Una entrada de turno se atribuye al siguiente estado, pero una entrada de reducción indica una producción.

Cuando cambia, inserta una referencia de estado en su pila y pasa al siguiente estado.

Cuando reduce, esto es para una producción específica. La producción fue responsable de cambiar n estados a su pila, donde n es el número de símbolos en esa producción. P.ej. uno para S ', dos para S, y dos o uno para C (es decir, para la primera o segunda alternativa para C).

Después de que se quiten n entradas de la pila, regresa al estado donde comenzó a procesar esa producción. Para ese estado y el no terminal resultantes de la producción, busca la tabla goto para encontrar el siguiente estado, que luego se presiona.

Por lo tanto, las entradas de reducción identifican una producción. De hecho, puede ser suficiente conocer el resultado no terminal y la cantidad de símbolos que se mostrarán.

Su mesa por lo tanto debe leer

state | action  | goto 
     | c | d | $ | C | S 
------------------------------------ 
    0 | s4 | s5 |  | 2 | 1 
------------------------------------ 
    1 |  |  | acc |  | 
------------------------------------ 
    2 | s4 | s5 |  | 3 | 
------------------------------------ 
    3 |  |  | r0 |  | 
------------------------------------ 
    4 | s4 | s5 |  |  | 6 
------------------------------------ 
    5 | r3 | r3 | r3 |  | 
------------------------------------ 
    6 | r2 | r2 | r2 |  | 

donde rx indica a reducir la producción x.

Answer 2

Debe abrir la pila y buscar el siguiente estado desde allí.

Answer 3

El rx significa: reducir el uso de la producción con el número x!
¡Entonces todo se aclara! ¡Haga estallar el cuerpo de la producción y vuelva a colocar la cabeza en la parte superior!