L'analisi separata e il lexing passano una buona pratica con i combinatori di parser?

Durante l'analisi, capiamo molto spesso l'analisi dei linguaggi liberi dal contesto. Un linguaggio context free è più potente di un normale, quindi il parser può (molto spesso) fare subito il lavoro dell'analizzatore lessicale.

Ma, questo è un) abbastanza innaturale b) spesso inefficiente.

Per a), se penso a come appare per esempio un'espressione if , penso IF expr THEN expr ELSE expr e non "i" "f", forse alcuni spazi, quindi qualsiasi carattere con cui un'espressione può iniziare, ecc. hai un'idea.

Per b) ci sono strumenti potenti che fanno un ottimo lavoro nel riconoscere entità lessicali, come identificatori, letterali, parentesi di tutti i tipi, ecc. Faranno il loro lavoro praticamente in pochissimo tempo e ti daranno una bella interfaccia: una lista di gettoni. Non preoccuparti più di saltare gli spazi nel parser, il tuo parser sarà molto più astratto quando si tratta di token e non di caratteri.

Dopo tutto, se pensi che un parser debba essere occupato con elementi di basso livello, perché quindi elaborare i caratteri? Si potrebbe scrivere anche a livello di bit! Vedete, un parser simile che funziona a livello di bit sarebbe quasi incomprensibile. È lo stesso con personaggi e token.

Solo i miei 2 centesimi.

Tutti suggeriscono che separare il lexing e l'analisi è una "buona pratica" - non sono d'accordo - in molti casi eseguire lexing e parsing in un singolo passaggio dà molta più energia e le implicazioni sulla performance non sono così negative come sono presentato nelle altre risposte (vedi Packrat ).

Questo approccio brilla quando si deve mescolare un certo numero di lingue diverse in un singolo flusso di input. Questo non è solo richiesto dagli strani linguaggi orientati alla metaprogrammazione come Katahdin e alike , ma anche per molte altre applicazioni mainstream, come la programmazione letterale (mixaggio del lattice e, per esempio, C ++), l'uso di HTML nei commenti, il riempimento di Javascript in HTML e così via on.

Un analizzatore lessicale riconosce un linguaggio normale e un parser riconosce un linguaggio privo di contesto. Poiché ogni lingua regolare è anche libera dal contesto (può essere definita da una cosiddetta grammatica lineare-destra ), un parser può anche riconoscere un linguaggio regolare e la distinzione tra parser e analizzatore lessicale sembra aggiungere alcune complessità non necessarie: una singola grammatica context-free (parser) potrebbe fare il lavoro di un parser e di un analizzatore lessicale.

D'altra parte, può essere utile catturare alcuni elementi di un linguaggio privo di contesto attraverso un linguaggio regolare (e quindi un analizzatore lessicale) perché

1. Spesso questi elementi appaiono così spesso da poter essere trattati in un modo standard: riconoscere numeri e stringhe letterali, parole chiave, identificatori, saltare lo spazio bianco e così via.
2. La definizione di una lingua normale di token semplifica la grammatica contestuale libera risultante, ad es. si può ragionare in termini di identificatori, non in termini di singoli caratteri, oppure si può ignorare completamente lo spazio bianco se non è rilevante per quel particolare linguaggio.

Quindi separare l'analisi dall'analisi lessicale ha il vantaggio di poter lavorare con una grammatica semplice e senza contesti e incapsulare alcune attività di base (spesso di routine) nell'analizzatore lessicale (divide et impera).

Modifica

Non ho familiarità con i combinatori di parser quindi non sono sicuro di come le considerazioni di cui sopra si applicano in quel contesto. La mia impressione è che anche se con parser combinatori uno ha solo una grammatica context-free, distinguendo tra due livelli (analisi lessicale / analisi) potrebbe aiutare a farlo grammatica più modulare. Come detto, lo strato di analisi lessicale inferiore potrebbe contenere parser riutilizzabili di base per identificatori, letterali e così via.

Semplicemente, il lexing e l'analisi dovrebbero essere separati perché sono diverse complessità. Lexing è un DFA (automa finito deterministico) e un parser è un PDA (automa push-down). Ciò significa che l'analisi consuma in modo intrinseco più risorse rispetto al lexing e sono disponibili tecniche di ottimizzazione specifiche solo per DFA. Inoltre, scrivere una macchina a stati finiti è molto meno complesso ed è più facile da automatizzare.

Sei sprecato usando un algoritmo di analisi per lex.

Uno dei principali vantaggi dell'analisi separata / lex è la rappresentazione intermedia - il flusso di token. Questo può essere elaborato in vari modi che altrimenti non sarebbero possibili con un lex / parse combinato.

Detto questo, ho trovato che un buon decadimento ricorsivo può essere meno complicato e più facile da usare con l'apprendimento di qualche generatore di parser e dover capire come esprimere la debolezza del grammatico all'interno delle regole del generatore di parser .