Informazioni sulla costruzione di AST nel parser LL1 non ricorsivo

Question

Informazioni sulla costruzione di AST nel parser LL1 non ricorsivo

#1 da (3 voti)

3

Ho implementato un parser LL1 in un approccio non ricorsivo con uno stack esplicito.

Il seguente algoritmo è tratto dal Libro del Drago:

set zp to point to the first symbol of w;
set X to the top stack symbol;
while ( X != $ ) { /* stack is not empty */
    if ( X is a ) 
       pop the stack and advance zp;
    else if ( X is a terminal )
       error();
    else if ( M[X, a] is an error entry )
       error();
    else if ( M[X,a] = X -+ Y1Y2 Yk ) {
       output the production X -+ YlY2 - . Yk;
       pop the stack;
       push Yk, Yk-1,. . . , Yl onto the stack, with Yl on top;

    set X to the top stack symbol;
}

Il libro dice:

The parser is controlled by a program that considers X, the symbol on top of the stack, and a, the current input symbol. If X is a nonterminal, the parser chooses an X-production by consulting entry M[X, a] of the parsing table IM. (Additional code could be executed here, for example, code to construct a node in a parse tree.) Otherwise, it checks for a match between the terminal X and current input symbol a.

Tuttavia ho bisogno di maggiori informazioni su come costruire i nodi dell'albero dell'espressione con questo approccio. Ho una gerarchia di nodi di UnaryOperator, BinaryOperator, ecc ma non so dove installarlo.

Tuttavia non ho trovato alcun esempio semplice di questo (con ad esempio il linguaggio aritmetico).

java syntax parsing trees

posta Wyvern666 02.03.2014 - 17:55

fonte

1 risposta

Leggi altre domande sui tag java syntax parsing trees

Autenticazione social dall'app mobile connessa al server API Design orientato agli oggetti e corretta architettura Java per il mio programma

score 3 · Accepted Answer

Succede proprio come il testo citato dal libro spiega: quando espandi un non-terminale usando la sua regola grammaticale (data da M[X, a] ), puoi creare un nodo corrispondente.

Supponiamo che tu abbia le regole del seguente modulo:

Term -> Factor Term'
Term' -> * Term | / Term | ε

Factor -> x | y | ... (simplified for individual numbers, letters, what-have-you)

Quindi, dopo aver espanso Term -> Factor Term' , puoi creare un nodo Term con due nodi figlio. Quando analizzi correttamente il primo numero tramite la regola Factor -> ... (questo è il primo if nel tuo codice di esempio ora) puoi attribuire questo numero al nodo Factor già creato.

Successivamente, espandi ad esempio Term' -> * Term tramite M[Term',*] e crea un nuovo nodo Term .

Proseguendo, analizzerete * e annotatelo al vostro nodo Term' , espandete Term -> Factor Term' ancora una volta, creando così altri due nodi, analizzerete con successo Factor e annotate il suo numero al secondo Factor node e infine, alla fine dell'input, analizzerai Term' tramite la produzione epsilon ( M[Term',$] = ε ), che ti dice che puoi rimuovere quel nodo Term' (anche se potrebbe essere facoltativo).

Ciò che si finisce con una stringa di input come 3 * 4 è quindi un albero come questo:

Term ( Factor(3), Term' (*, Term ( Factor(4) ) ) )

In una fase di post-elaborazione, è possibile semplificare l'albero risultante, poiché non-minuti come Term' derivano dal rendere la grammatica non-sinistra-ricorsiva, ma sono altrimenti inadatti per l'AST risultante, quindi si vorrebbe invertire trasformazione della grammatica sull'albero risultante per ottenere qualcosa di simile a questo:

Mult (Number(3), Number(4))