Memorizzazione di token durante la fase di lexing

Question

Memorizzazione di token durante la fase di lexing

#1 da (3 voti)
#2 da (0 voti)

0

Attualmente sto implementando un lexer che interrompe i file XML in token, sto considerando modi per trasferire i token su un parser per creare una struttura dati più utile da detti token - il mio piano attuale è di memorizzarli in un arraylist e passare questo al parser, sarebbe una lista di link dove ogni token punta al prossimo sarà più adatto? O è in grado di accedere a token per indice più facile da fare un parser? O è tutta una strategia terribile?

Anche se qualcuno ha usato antlr, so che usa un flusso di token per passare l'input token al parser, come può il parser prendere decisioni se l'input è valido / creare una struttura di dati se non ha tutti i token dall'input ancora?

language-design compiler parsing lexer

posta The_Neo 17.04.2014 - 01:50

fonte

2 risposte

Leggi altre domande sui tag language-design compiler parsing lexer

Come scegliere tra diverse librerie open-source? [chiuso] Come implementare i backup differenziali senza conservare copie dei file originali su disco?

score 3 · Answer 1

Le tecniche di analisi comune si basano sull'ispezione di un singolo token "corrente" da un flusso di tali token. In alcune varianti è richiesta una certa quantità di lookahead, ma di solito è fornita dal parser e non dall'indicizzazione avanti e indietro attraverso il flusso del lexer.

In altre parole, la struttura dei dati di cui avrai probabilmente bisogno è una specie di stream. Il solito modo di implementarlo è con un'API basata sulle funzioni, con funzioni come peek() e movenext() .

Dato un "flusso di token", i dettagli di come lo strutturate internamente sono relativamente poco importanti. Potresti usare una coda in memoria, una coda produttore-consumatore, un rendimento / generatore o una qualsiasi molteplicità di altre tecniche.

La mia raccomandazione strong sarebbe quella di fare la "cosa più semplice che potrebbe funzionare". Le parti interessanti e impegnative del tuo problema devono ancora venire.

score 0 · Answer 2

Se riesci ad accedere a token con un indice, c'è la tentazione di saltare in avanti o indietro, e puoi farlo, ma in genere finisci con un codice molto difficile da capire. I buoni parser hanno una grammatica che determina cosa dovrebbero cercare in base a dove si trovano nella grammatica, e se la grammatica è fatta bene, non dovresti mai trovarti di fronte all'ambiguità (non sapere quale tipo di token ci si aspetta dopo).

Facendolo in questo modo è più semplice scrivere e condensare il problema nella creazione di una buona grammatica piuttosto che scrivere un buon parser. Non importa se stai usando liste collegate o un array (a meno che non stiate analizzando molto file XML di grandi dimensioni, nel qual caso le liste collegate potrebbero essere più sicure). Tuttavia, il parser dovrebbe generalmente considerare questo input come una coda, anche se potrebbe saltare avanti altrimenti con un indice. I lookheadhead esistono, ma non dovrebbero essere richiesti per la grammatica XML.

Spero che ti aiuti.