Corretta separazione tra lexing e analisi

La distinzione tra lexing e parsing è solo una questione di convenienza. Come tale, fai tutto ciò che è conveniente per il tuo problema.

In particolare, non è mai necessario per usare un lexer. In linea di principio, un parser potrebbe anche funzionare su una base per carattere anziché su una base per-token. Esistono linguaggi che non possono essere analizzati con un lexer ordinario (ad esempio, qualsiasi cosa con parole chiave contestuali), ma se è possibile utilizzarne uno, l'utilizzo della memoria del parser tende ad essere più basso (poiché vi sono meno token rispetto ai caratteri), e la grammatica tende ad essere più semplice (dal momento che la grammatica del token è gestita dal lexer, e i commenti, gli spazi bianchi insignificanti, ecc. sono di solito eliminati dal lexer).

Riguardo alla conversione di valori letterali, ciò dipende dalla lingua. Esistono lingue in cui i letterali non hanno un tipo intrinseco (ad esempio in Haskell 2 può essere di qualsiasi tipo numerico, a seconda del contesto). Esistono linguaggi con analisi letterale definita dall'utente (ad esempio C ++). Esistono lingue in cui le stringhe possono contenere codice interpolato o operatori di alloggiamento sensibili alle impostazioni internazionali. Tutti questi sono problemi che non possono essere risolti dal lexer e dovranno essere gestiti in un altro stadio del parser.

Per un semplice linguaggio simile a C, tutti questi problemi non esistono e un lexer potrebbe convertire direttamente i valori. Ma dovremmo?

Un token è in genere una tupla o un record (type, location, value) , in cui il valore è la stringa lessicata corrispondente. Il valore può essere vuoto dove la stringa è inutile, ad es. per parole chiave o operatori. Se il valore è una stringa per alcuni tipi di token e un intero per altri tipi di token, la manipolazione di questi diversi tipi può diventare scomoda e soggetta a errori, specialmente se il parser è implementato in una lingua come C (dovresti usare union s!). Sarebbe quindi meglio convertire i valori nel parser, immediatamente prima della costruzione di AST. Ovviamente questo non è un problema quando la lingua dell'host utilizza la digitazione dinamica o se i tipi di token sono rappresentati come tipi distinti nella lingua dell'host.

Un'altra considerazione è la qualità dei messaggi di errore. Immagina che, per qualche ragione, un utente scriva 0.5E3 . Durante l'analisi, si verifica un problema, poiché i numeri in virgola mobile non sono consentiti in quel contesto sintattico. Il tuo messaggio di errore segnalerebbe il token incriminato come 0.5E3 o 500.0 ? Simile ai numeri in esadecimale, ottale o binario. Molto importante anche quando stringhe / caratteri contengono caratteri non stampabili, trattini morbidi o sosia Unicode (omografi). Convertendo in anticipo i valori letterali, si stanno gettando informazioni sulla formattazione esatta, ma queste informazioni potrebbero essere molto utili per un utente confuso. Questo non è un grosso problema (specialmente quando il tuo messaggio di errore riporta la riga contenente l'errore e indica la posizione esatta dell'errore), ma è qualcosa da considerare. Idealmente puoi mostrare entrambi - la formattazione originale e un modulo normalizzato.

Per il primo punto - è un compromesso tra semplicità e potere. Nella maggior parte delle lingue, un letterale intero intero esadecimale e un letterale intero decimale sono esattamente equivalenti, quindi tradurre entrambi in un token intero generale nella fase di lexing consente di mantenere il numero di token in basso e semplificare la grammatica.

D'altra parte, un IDE elaborato potrebbe mostrare valori letterali esadecimali decimali con colori diversi e avere opzioni come "convertire il decimale in esadecimale" e viceversa. Ciò richiede che la distinzione sia presente nell'AST, quindi devi mantenerli come tipi di token distinti.

Per il secondo punto, dipenderà dalla lingua, dal momento che ci sono diversi modi di gestire gli escape. In Java gli escape di unicode (sia all'interno che all'esterno di stringhe) devono essere risolti con prima della tokenizzazione , quindi

int\u0020x 

dovrebbe essere analizzato allo stesso modo di:

 int x 

Tuttavia, per dire JavaScript, devono essere risolti dopo tokenizzazione (e sono consentiti solo all'interno di stringhe letterali).

In alcune lingue, il significato dei caratteri all'interno di una stringa dipende dalla citazione usata. Per esempio. Python r"\n" è una stringa diversa da "\n" . Poiché le virgolette stesse non fanno parte della stringa che si passa, la soluzione più semplice è quella di risolvere gli escape nella fase di lexing in cui si conoscono le virgolette utilizzate, quindi è sufficiente un solo tipo di token di stringa. Ma ancora, potresti voler mantenere la distinzione nell'AST per il supporto degli strumenti.

Non direi che è una distinzione arbitraria come dice la risposta accettata.

Lessing o tokenizing non riconosce la semantica o le relazioni. Fornisce tutti gli elementi (token) per te, per un facile accesso, filtrando le cose irrilevanti. In un linguaggio informatico le cose irrilevanti potrebbero essere lo spazio bianco o la differenza nell'involucro o la scelta di una serie di affermazioni equivalenti. Riconosce parole chiave e costrutti ma non convalida.

Puoi eseguire il lex in parallelo, ogni file indipendente dal successivo. Non puoi analizzare in parallelo, dovresti sapere da dove iniziare e riconoscere le dipendenze. Quando analizzi dovresti sapere dove sei e cosa stai facendo.

La tokenizzazione potrebbe riuscire, trovando solo costrutti validi e quindi il tuo parser potrebbe scoprire che è tutto falso.

Lexing raccoglie, analizzando gli interpreti.