È possibile creare un singolo tokenizzatore per analizzarlo?

La tua grammatica ha delle ambiguità che rendono impossibile sapere cosa fare con, diciamo, la lettera a senza contesto. Nel tuo caso, la stringa abc può avere due interpretazioni: può essere un identificatore (presumo che sia ciò che la tua prima m// definisce), oppure può far parte di una stringa letterale citata nella notazione { ... } (Lo chiamerò "elenco quotato"). Gli analizzatori lessicali (tokenizer) non sono abbastanza intelligenti per gestire questo tipo di ambiguità, perché il loro concetto di contesto è molto semplicistico. I parser, d'altra parte, possono comprendere il contesto a livelli molto profondi. *

I progettisti di linguaggi a volte aggiungono sigilli ai loro identificatori (ad esempio $abc ) per renderli più facili da tokenizzare. Questo è il motivo per cui è possibile avere una variabile Perl denominata $for anche se% nudo nudofor ha un significato speciale. Per ragioni simili, i lexer C rendono token /"[^"]*"/ in un letterale stringa perché ha una sintassi indipendente dal contesto che non appare da nessun'altra parte nella lingua.

Torna al tuo problema: un tokenizzazione precoce di una stringa di caratteri alfanumerici in IDENTIFIER significherebbe che l'elenco quotato { abc[1]xyz } verrebbe inviato al parser come { IDENTIFIER [ NUMBER ] IDENTIFIER } . Ciò è utile se questi fossero i blocchi in cui ne hai avuto bisogno, ma altrimenti dovresti incorporare la possibilità di gestire combinando tutte le combinazioni di quei token nella grammatica per il tuo elenco quotato. Quindi dovresti gestirli riassemblandoli in stringhe letterali. Se non l'hai indovinato, diventerebbe molto complesso e brutto molto rapidamente. Ma dal momento che i parser comprendono il contesto, la sua saggezza lo rende semplice e pulito.

Per quello che stai facendo, non ci dovrebbe essere molto di un tokenizer perché gran parte di esso è sensibile al contesto, e questo è tutto il territorio del parser. Gli spazi bianchi non sembrano avere importanza se non nel contesto di un elenco quotato, in modo che tu possa riconoscere ciò e anche le cose che non sono ambigue come LETTER e DIGIT .

// NOTE:  This code doesn't handle the case where whitespace is 
// interspersed with the tokens.  See the comments.

quoted-list ::= '{' quoted-list-item-set '}'

quoted-list-item-set ::=
    <nothing>
    | string-of-non-whitespace-characters
    | string-of-non-whitespace-characters WHITESPACE quoted-list-item-set

// This ends up being things you have to put together and return,
// so that eventually you end up with a single string.
string-of-non-whitespace-characters ::=
    non-whitespace-character
    | non-whitespace-character string-of-non-whitespace-characters

non-whitespace-character ::= <anything in the set '!'..'~'>

identifier ::= LETTER alphanumeric-string

alphanumeric-string ::= 
    <nothing>
    | alphanumeric alphanumeric-string

alphanumeric ::= LETTER | DIGIT

// ...etc...

// This prevents the parser from barfing on whitespace in any other context.
things-that-get-ignored ::= WHITESPACE

* Ecco perché dovresti usare un parser per interpretare qualcosa di complesso come XML e non cadere nella trappola di cercare di capirlo con espressioni regolari.

Sì, è certamente possibile creare un singolo tokenizer che può analizzarlo. Posso facilmente creare un tokenizer regolare context-free che analizzerà correttamente la tua lingua.

Tuttavia, molti strumenti popolari potrebbero rendere difficile e / o impossibile codificare i tuoi input come vuoi, anche se il tuo tokenizzatore potrebbe essere descritto da una grammatica regolare. Usando diversi strumenti, potresti trovare estremamente facile tokenizzare i tuoi input come preferisci.

Quale approccio tu possa adottare per risolvere questo problema può essere in gran parte dettato dalla scelta dello strumento.

Da quello che vedo basta mettere il lexer in grado di riconoscere la parentesi di apertura e passare allo stato avido . In tale stato definisci una nuova serie di modelli, che sono, beh, avidi tranne che per gli spazi bianchi. E la sola parentesi destra ha l'effetto di far scattare lo stato e tornare a ciò che era prima.

L'approccio descritto giustamente renderà noti i tuoi esempi.

A quanto ho capito, i lexer non sono discriminatori. Rompono i token senza contesto. Pertanto, il primo esempio non può essere analizzato utilizzando tale tokenizer poiché la parentesi di chiusura non è strettamente vincolata alla virgola. Il secondo esempio non può essere analizzato in questo modo, anche se si tenta di incollare i token insieme al parser (aggiungendo overhead e complessità), perché non ci sarebbe un modo per sapere quando finisce il primo token e inizia il prossimo.

Entrambi potrebbero essere raggiunti se gli spazi bianchi non fossero ignorati, ma aggiungerebbero più complessità alla grammatica / parser per tutte le altre regole grammaticali.

Quindi sì, può essere fatto. Ma dipende se il sovraccarico e la complessità aggiunti valgono la pena.