Edificio Parse Alberi con analisi del turno-riduzione

Question

Sto sperimentando l'analisi sul mio tempo libero, e volevo implementare un parser di riduzione del cambio per una grammatica molto semplice. Ho letto molti articoli online ma sono ancora confuso su come creare alberi antigas. Ecco un esempio di quello che voglio fare:

---

.

Grammatica:

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

.

Ecco un ingresso di esempio:

1 + 1 + 1 + 1

.

che, dopo il tokenization, diventa:

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

.

---

.

Capisco che:

.
1. spostamento significa spingere il primo token di ingresso sullo stack e rimuoverlo dall'input
2. riduzione significa sostituire uno o più elementi sullo stack con un elemento grammaticle

Quindi, in pratica, questo dovrebbe accadere:

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

.

Oltre a "cosa ridurre?" dubbio, non ho idea di come costruire correttamente un albero antigas. Probabilmente l'albero dovrebbe assomigliare a questo:

1    +    o
          |
     1    +    o
               |
          1    +    1

.

Dovrei creare un nuovo nodo sulla riduzione?

E quando dovrei aggiungere bambini al nuovo nodo / quando dovrei creare un nuovo nodo root?

Answer 1

La cosa semplice e ovvia da fare è creare un nodo dell'albero su ogni riduzione e aggiungere i nodi dell'albero dagli elementi di grammatica ridotti a quel nodo dell'albero.

Questo è facilmente gestibile con uno stack nodo che funziona in parallelo allo stack "Toster token" che utilizza il parser grezzo. Per ogni riduzione per una regola di lunghezza n, lo stack del token del cambio è abbreviato da n e il token non più elettronico viene spinto sullo stack del turno. Allo stesso tempo, accorciare lo stack del nodo rimuovendo i nodi N. in alto, creare un nodo per il nonterminale, allegato i nodi n rimossi n come bambini e spingere quel nodo sulla pila del nodo.

Questa politica funziona anche con regole con lato destro a destra zero: creare un nodo albero e collegare il set vuoto dei bambini ad esso (ad esempio, creare un nodo foglia).

Se si ritiene a un "turno" su un nodo terminale come una riduzione (dei caratteri che formano il terminale) al nodo del terminale, quindi i spostamenti del nodo del terminale si adattano a destra. Creare un nodo per il terminale e spingerlo su la pila.

Se lo fai, ottieni un "calcestruzzo sintassi / albero parse" che corrisponde alla grammatica isomorfica. (Lo facciamo per uno strumento commerciale che offro). Ci sono molte persone che non piacciono tali alberi concreti, perché contengono nodi per parole chiave, ecc., Che non aggiungono davvero molto valore. Vero, ma tali alberi sono estremamente facili da costruire e supremamente facile da capire perché la grammatica è la struttura ad albero. Quando hai 2500 regole (come facciamo per un parser completo Cobol), questo è importante. Questo è anche conveniente perché tutto il meccanismo può essere costruito completamente nell'infrastruttura antigas.. L'ingegnere di grammatica scrive semplicemente le regole, il parser funziona, voilà, un albero. È anche facile cambiare la grammatica: basta cambiarlo, voilà, hai ancora alberi antigas.

Tuttavia, se non si desidera un albero di calcestruzzo, ad esempio, vuoi un "albero di sintassi astratto", allora ciò che devi fare è lasciare che il controllo dell'ingegnere della grammatica che riduce genera i nodi; Di solito aggiungendo un attaccamento procedurale (codice) a ciascuna regola grammaticale da eseguire su una fase di riduzione. Quindi se tale attacco procedurale produce un nodo, viene mantenuto su una pila di nodo. Qualsiasi attaccamento procedurale che produce un nodo deve allegare i nodi prodotti dagli elementi della mano destra. Se qualcuno è ciò che lo Yacc / Bison / ... la maggior parte dei motori del parser riducono il turno. Vai a leggere su Yacc o Bison ed esamina una grammatica. Questo schema ti dà un sacco di controllo, al prezzo di insistere di prendere quel controllo. (Per quello che facciamo, non vogliamo questo sforzo molto ingegneristico nella costruzione di una grammatica).

In caso di produzione di CSTS, è concettualmente semplice per rimuovere i nodi "inutili" dagli alberi; Lo facciamo nel nostro strumento. Il risultato è molto simile a un AST, senza lo sforzo manuale per scrivere tutti quegli allegati procedurali.

Answer 2

Il motivo del tuo problema è che hai un conflitto di spostamento / riduce nella tua grammatica:

expr: expr OP expr
    | number

.

È possibile risolvere questo in 2 modi:

expr: expr OP number
    | number

.

per gli operatori associativi di sinistra o

expr: number OP expr
    | number

.

per quelli associativi giusti. Questo dovrebbe anche determinare la forma del tuo albero.

La riduzione viene solitamente eseguita quando viene rilevata una clausola completa. Nel caso destro associativo, inizieresti in uno stato 1 che si aspetta un numero, lo prevedete sullo stack value e si sposta sullo stato 2. In stato 2, se il token non è un op, è possibile ridurre un numero a un expr . In caso contrario, premere l'operatore e passare allo stato 1. Una volta completato lo stato 1, è possibile ridurre il numero, l'operatore ed espressione a un'altra espressione. Nota, è necessario un meccanismo per "ritorno" dopo una riduzione. Il parser generale avrebbe quindi iniziato nello stato 0, ad esempio, che va immediatamente sullo stato 1 e accetta dopo la riduzione.

Nota che gli strumenti come Yacc o Bison rendono questo tipo di roba molto più facile perché portano tutti i macchinari di basso livello e le pile.