Come trasformare un flusso di token in un albero di analisi [chiuso]

Question

Ho costruito un lexer che emette token dall'input ma non sono sicuro di come costruire il prossimo passo nel processo: l'albero di analisi. Qualcuno ha buone risorse o esempi su come raggiungere questo obiettivo?

Answer 1

Consiglierei davvero http://www.antlr.org/ e ovviamente il classico Drago Libro dei compilatori.

Per un linguaggio semplice come JavaScript non è difficile eseguire manualmente un parser di discesa ricorsivo, ma è quasi sempre più facile utilizzare uno strumento come yacc o antlr.

Penso di tornare alle basi della tua domanda, vuoi davvero studiare la sintassi grammaticale in stile BNF e scegliere una sintassi per il tuo obiettivo. Se lo hai, l'albero di analisi dovrebbe cadere, essendo la manifestazione "istanza" di quella grammatica.

Inoltre, non provare a trasformare la creazione del tuo albero di analisi nella tua soluzione finale (come generare codice o no). Potrebbe sembrare fattibile e più efficace; ma invariabilmente arriverà un momento in cui vorresti davvero avere quell'albero di analisi "così com'è" in giro.

Answer 2

È necessario esaminare gli strumenti del generatore di parser per la propria piattaforma. Un generatore di parser ti consente di specificare una grammatica senza contesto per la tua lingua. La lingua è costituita da una serie di regole che "riducono" una serie di simboli in un nuovo simbolo. Di solito è anche possibile specificare la precedenza e l'associatività per regole diverse per eliminare l'ambiguità nella lingua. Ad esempio, un linguaggio di calcolatrice molto semplice potrebbe assomigliare a questo:

%left PLUS, MINUS           # low precedence, evaluated left-to-right
%left TIMES, DIV            # high precedence, left-to-right

expr ::= INT
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIV expr
| LEFT_PAREN expr RIGHT_PAREN

Di solito, è possibile associare un po 'di codice a ciascuna regola per costruire un nuovo valore (in questo caso un'espressione) dagli altri simboli di quella regola. Il generatore di parser prenderà in esame la grammatica e produrrà codice nella tua lingua che traduce un flusso di token in un albero di analisi.

La maggior parte dei generatori di parser sono specifici della lingua. ANTLR è ben noto e supporta C, C ++, Objective C, Java e Python. Ho sentito che è difficile da usare però. Ho usato bison per C / C ++, CUP per Java e ocamlyacc per OCaml, e sono tutti abbastanza buoni. Se stai già utilizzando un generatore di lexer, dovresti cercare un generatore di parser che sia specificamente compatibile con esso.

Answer 3

Credo che un approccio comune sia quello di utilizzare un Finite State Machine . Ad esempio, se leggi un operando vai in uno stato in cui ti aspetti un operatore, e di solito usi l'operatore come nodo principale per gli operandi e così via.

Answer 4

Come descritto sopra da Marcos Marin, una macchina a stati che utilizza le regole della lingua in BNF per analizzare l'elenco dei token farà il trucco se si desidera farlo da soli. Solo, come detto nel commento di Paul Hollingsworth sopra, il modo più semplice è usare un Pushdown-Automaton che ha un semplice stack di memoria FiFo. Ogni classe di token ha un prossimo token atteso nella tua grammatica, che è anche rappresentato nella tua macchina a stati. Lo stack viene utilizzato per " ricordare " quale era la precedente classe token, per ridurre gli stati richiesti (poteva essere fatto senza stack, ma sarebbe necessario un nuovo stato per ogni classe e sottoclasse divisa nella struttura grammaticale). Lo / gli stato / i accettante / i sarebbe (nei linguaggi naturali e anche nella maggior parte dei linguaggi di programmazione) lo stato iniziale, e forse qualche altro stato in casi particolari.

Antlr sarebbe il mio suggerimento se si desidera utilizzare uno strumento (waaay più veloce e meno esteso). Buona fortuna!