È appropriato che un tokenizzatore usi la regex per raccogliere token?

I regex funzionano alla grande per lexing / tokenization.

TL; DR

Usare le espressioni regolari per tokenize è del tutto appropriato. L'approccio predefinito, davvero. Per quanto riguarda l'efficienza, le regex si riferiscono tradizionalmente direttamente alle macchine a stati finiti . Sono tanto semplici ed efficienti quanto è possibile ottenere per definizioni di sintassi di qualsiasi generalità.

ImodernimotoriregexnonsonopureimplementazionimatematichediFSM,essendostatiestesiconfunzionalitàcomelook-ahead,look-behindebacktracking.Mahannounstrongfondamentoteorico,einpraticasonoaltamenteottimizzatiedestremamentebencontrollati.

Granpartedegliultimicinquantaepiùannidianalisidellinguaggioinformaticosiriduconoatrovaretecnicheperdistricareilprocessoerenderlopratico.Dividereeconquistare/stratificareècomune.Quindil'ideadidividereilproblemadicomprensionedellinguaggioinunlivelloinferiore"lexing" e "analizzare" il livello superiore.

Lo stesso con la ricerca di approcci che riducono la forza come l'utilizzo di solo sottoinsiemi di senza contesto e grammatiche prive di ambiguità . Pascal era limitato a ciò che poteva essere analizzato ricorsivo-discendente , e Python è notoriamente limitato a LL(1) . Ci sono zuppe alfabetiche complete di LL, LR, SLR, LALR, ecc. Grammatiche linguistiche / famiglie di parser. Quasi tutti i progetti linguistici implementati sono attentamente limitati dalle tecniche di analisi che usano. Perl è l'unica lingua principale che posso pensare che non sia così limitata. Questa danza è descritta nel "Libro dei draghi" che erano i più comuni "come lingua" libri di testo per generazioni .

Il rigoroso scomporre lexing / parsing e 'usare solo sottoinsiemi di regole grammaticali prive di ambiguità, che si attenuano. A volte la comprensione lessicale non è suddivisa in uno strato completamente diverso e la maggior parte dei sistemi ha abbastanza potenza e memoria della CPU per renderla fattibile. Un'altra risposta menzionata PEG parser. Ciò inizia a rompere l'ortodossia delle famiglie linguistiche. Ancora più lontano puoi vedere un rinnovato interesse per parser / grammatiche più generali come il parser Earley che va oltre le limitate previsioni delle aristocrazie LL / LR. Recenti implementazioni e perfezionamenti (ad esempio Marpa ) mostrano che , su hardware moderno, non c'è davvero alcuna barriera all'analisi generalizzata.

Tutto ciò che ha detto, tuttavia, la libertà infinita (o anche molta più grande libertà) non è necessariamente una buona cosa. Le restrizioni meccaniche, pratiche e tecniche di qualsiasi forma d'arte - scrittura, pittura, scultura, produzione cinematografica, codifica, ecc. - richiedono spesso una disciplina di approccio che è utile al di là delle corrispondenti tecniche di implementazione disponibili. Python, ad esempio, potrebbe essere notevolmente migliorato generalizzando oltre l'analisi di LL (1)? Non è chiaro che lo sarebbe. Certo, ci sono alcune incoerenze e limitazioni sfortunate, e ha bisogno di uno spazio vuoto significativo. Ma rimane anche pulito e coerente, attraverso un vasto numero di sviluppatori e usi, parzialmente come conseguenza di tali restrizioni. Non fare l'equivalente in lingua di ciò che è accaduto quando diversi tipi di facce, dimensioni, colori, colori di sfondo, variazioni e decorazioni sono diventati ampiamente disponibili nei word processor e nelle e-mail. Non utilizzare tutte le opzioni in modo profuso e indiscriminato. Non è un buon design.

Quindi, mentre grandi generalità e persino ambiguità sono ora aperte a te mentre implementa il tuo linguaggio giocattolo, e mentre puoi sicuramente usare uno dei nuovi approcci PEG o Earley, a meno che tu non stia scrivendo qualcosa che imita il linguaggio naturale umano, probabilmente non è necessario. Sarebbe sufficiente l'approccio standard di lessering e parsing. Oppure, per farla breve, le regex vanno bene.

L'uso di espressioni regolari per tokenize è un approccio classico. Gli approcci più moderni all'analisi dovrebbero utilizzare un parser basato su PEG ( "parser di espressioni di analisi" ).

In entrambi i casi funziona, ma avere la capacità di lasciare "ciò che è stato analizzato finora" guida ciò che costituisce un token dà una certa flessibilità. In sostanza, un parser in stile PEG intreccia la tokenizzazione e l'analisi, mentre un approccio rigoroso "tokenize parse stream of token" offre meno flessibilità nella progettazione della lingua, ma di solito non è un problema.

Per quanto riguarda le "espressioni regolari che richiedono più tempo per valutare", si tratta più di un problema di qualità di implementazione rispetto a un problema fondamentale con le espressioni regolari. Tuttavia, essi sono limitati in ciò che possono esprimere, ma per il compito di tokenizzazione questi limiti non sono tipicamente un problema (i RE hanno problemi nell'esprimere concetti come "parentesi arbitrariamente annidate", che è ben oltre la tokenizzazione).