Qual è la responsabilità o il vantaggio di un Tokenizer?

Sembra che tu non capisca cosa dovrebbe fare un tokenizer. In questo esempio, renderei il tokenizer riconoscere sei token: { , } , : , string , number . Il tokenizzatore produce una stringa / sequenza di token, non un albero. E invece della grammatica scritta in termini di singoli caratteri ( char , digit ), ora è scritta in termini di token.

Il vantaggio è che questo semplifica grammatica e parser: non è più necessario descrivere come analizzare stringhe e numeri (si noti che i valori letterali stringa e numerici delle lingue reali sono molto più complicati, il che aumenta questo vantaggio). Per quanto riguarda il parser, la grammatica diventa

object 
    '{' members '}'
members 
    pair
pair
    string ':' value 
value 
    number
    string

Non è più semplice scrivere un parser, ma è anche più utile per comprendere la struttura sintattica dei programmi. So cos'è una stringa letterale, la parte interessante è come posso combinare stringhe letterali e altre unità atomiche per formare programmi.

Il file sorgente originale, in qualsiasi linguaggio di programmazione o di markup che stai analizzando, è solo una lunga sequenza di caratteri. Le "parole" che compongono la lingua possono essere opportunamente separate da spazi, o non possono.

Ad esempio in C, le sequenze di caratteri "foo = bar < < 2;" e "foo = bar < < 2;" dovrebbe essere considerato equivalente Il primo passo per analizzare un documento è quindi analizzare la sequenza di caratteri e capire dove finisce un token ("parola") e inizia il prossimo.

Nel mio piccolo esempio C, i token sono "foo", "=", "bar", "< <", "2" e ";" in entrambi i casi. Nota la sottigliezza in questo caso che è "< <" e non "<" seguito da "<". I tokenenator devono conoscere la sintassi del linguaggio, ma non il suo significato.

Solo dopo aver tokenizzato la stringa puoi iniziare a pensare a cosa significa il documento.

Esponi un punto eccellente. Non sono d'accordo con le altre risposte qui e dico che l'obiettivo principale di un tokenizzatore è ottenere prestazioni migliori durante l'analisi , ovvero i tokenizer sono un'ottimizzazione: un dettaglio di implementazione di parsing, ma non fondamentale. Gran parte del tempo dedicato all'analisi è la rottura della stringa di input in pezzi. Ottimizzando questo, le prestazioni del parser possono essere notevolmente aumentate.

Quindi questa è una definizione piuttosto vaga che ho appena dato, ed è per questo che è difficile definire con precisione cosa dovrebbe fare un tokenizer.

Molte lingue sono definite utilizzando due grammatiche separate: una per i token e una per gli elementi di sintassi gerarchica. Si potrebbe sostenere che lo scopo di un tokenizzatore è implementare la grammatica del token, ma questo non ha senso: dividere una grammatica in token e grammatiche gerarchiche è arbitrario e non necessario dal punto di vista dell'espressività (anche se, ancora una volta, utile come performance ottimizzazione).

È perfettamente ragionevole e pratico implementare i parser senza tokenizer separati, sebbene sia probabile che le prestazioni siano peggiori.

È importante notare che ci sono degli svantaggi nell'usare un tokenizzatore separato. Uno è che la grammatica del token può essere limitata ( esempio , un altro esempio ). Nella mia esperienza personale, evitare la tokenizzazione separata riduce la complessità complessiva (LOC, interfacce tra sottosistemi, ecc.) Di un parser.

Lessing e Parsing si prestano a diversi formalismi. L'obiettivo è rendere entrambe le attività più facili da programmare e gestire, oltre che più veloci in fase di runtime.

Se si guarda a (f) lex, il solito generatore di lexer, usa espressioni regolari per esprimere le regole lessicali. Questo è notazionalmente molto più compatto di una grammatica espressa come BNF o alcune specifiche del parser simili.

In fase di esecuzione, un lexer può essere trasformato in un automa finito. Un parser non può. Quindi suddividere il lavoro accelera il processo. Un parser deve essere qualcosa come LR (k) o LL (1) o LALR per gestire l'ambiguità.

Il "libro dei draghi" è stato il classico testo di livello universitario sulle tecniche di compilazione per quasi 30 anni.