Problema di implementazione del generatore di parser LALR

Question

Attualmente sto cercando di implementare un generatore di parser LALR come descritto in "tecniche e strumenti dei compilatori" (chiamato anche "libro del drago").

Molto già funziona. Il generatore di parser è attualmente in grado di generare il goto-graph completo.

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

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

Il goto-grafico:

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 . , $ |<-----+ 
      +---------------+ 

devo trubbles con l'attuazione del algoritmo per generare le azioni-tavola! mio algoritmo calcola il seguente output:

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 ... passare a stato x
rx ... ridurre allo stato x

Il r? significa che non so come ottenere lo stato (il?) a cui il parser dovrebbe ridurre. Qualcuno conosce un algoritmo da ottenere? usando il goto-grafo sopra?

Se qualcosa non viene descritto abbastanza chiaramente, si prega di chiedere e cercherò di spiegarlo meglio! Grazie per il vostro aiuto!

Answer 1

Una voce di spostamento viene attribuita dallo stato successivo, ma una voce di riduzione indica una produzione.

Quando si sposta, si preme un riferimento di stato nello stack e si passa allo stato successivo.

Quando si riduce, questo è per una produzione specifica. La produzione era responsabile dello spostamento di n stati sul tuo stack, dove n è il numero di simboli in quella produzione. Per esempio. uno per S ', due per S e due o uno per C (vale a dire per la prima o la seconda alternativa per C).

Dopo che n voci sono state estratte dallo stack, si ritorna allo stato in cui è stata avviata l'elaborazione di quella produzione. Per quello stato e il non terminale risultante dalla produzione, si cerca la tabella goto per trovare lo stato successivo, che viene poi premuto.

Quindi le voci di riduzione identificano una produzione. In effetti può essere sufficiente conoscere il non terminale risultante e il numero di simboli da far apparire.

La tabella in tal modo dovrebbe leggere

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 |  | 

dove rx indica ridurre di produzione di x.

Answer 2

È necessario fare lo stack e trovare lo stato successivo da lì.

Answer 3

Il rx significa: ridurre l'utilizzo della produzione con il numero x!
Quindi tutto diventa chiaro! Semplicemente apri il corpo della produzione e sposta la testa in alto!