È un approccio praticabile alla risoluzione di più corrispondenze in un lexer?

Question

È un approccio praticabile alla risoluzione di più corrispondenze in un lexer?

#1 da (5 voti)
#2 da (3 voti)
#3 da (0 voti)

4

Sto scrivendo un lexer in JavaScript. È piuttosto tipico: le regole sono specificate con espressioni regolari e producono un token.

Non sono sicuro del modo migliore per gestire quando più regole sono abbinate. I lexer esistenti che ho guardato gestiscono questo selezionando la regola con la corrispondenza più lunga.

Sembra anche una strategia praticabile, tuttavia, per usare semplicemente la prima regola che corrisponde. Questa è la mia strategia attuale.

Ecco un esempio:

Input:

:=

Regole:

: -> COLON
= -> EQUALS
:= -> ASSIGN

La regola della corrispondenza più lunga restituirebbe ASSIGN , dove la regola della prima corrispondenza restituirebbe COLON e poi EQUALS .

Ovviamente questo non è auspicabile, quindi sotto la mia implementazione vorrei solo riordinare le regole per mettere la regola ASSIGN prima come segue:

:= -> ASSIGN
: -> COLON
= -> EQUALS

È un approccio fattibile per utilizzare solo la prima regola di corrispondenza? Quali sono i vantaggi e gli svantaggi di ciascun approccio?

programming-languages lexer

posta jhewlett 02.06.2013 - 03:23

fonte

3 risposte

3

Non lo vedrei come "primo" match, ma avere il lexer ha priorità definite non è raro. Il vantaggio di analizzare i due punti prima è sbagliato, elimina due percorsi. Se ti manca il compito, devi comunque controllare i due punti.

risposta data 02.06.2013 - 03:43

fonte

0

Quando scrivo un lexer uso una grammatica, non le espressioni regolari. La grammatica non ha ambiguità di progettazione. L'effetto è esattamente equivalente alla tua proposta di usare le espressioni regolari, ordinandole per lunghezza decrescente e accettando la prima corrispondenza. La mia strada è più efficiente (più veloce e meno spazio) ma un po 'più difficile da scrivere.

L'oggetto sollevato per quanto riguarda gli identificatori e le parole riservate non si applica. I token var e variant vengono analizzati esattamente nello stesso modo. Il lexer è strettamente associato a una tabella dei simboli e la differenza è che le parole riservate (e in effetti ogni tipo di token) sono precaricate nella tabella dei simboli. La tabella dei simboli dice che tipo di token è.

Quindi la tua strategia (prima corrispondenza) è perfettamente fattibile se sei pronto a cercare token in una tabella dei simboli per scoprire cosa sono invece di costruire quella conoscenza nel lexer.

risposta data 12.07.2014 - 13:35

fonte

Leggi altre domande sui tag programming-languages lexer

Modelli di layer di accesso ai dati di Fowlers Come posso migliorare questo design in modo che non sia necessario eseguire la scansione dinamica delle classi in fase di runtime?

score 5 · Accepted Answer

No, non è una strategia valida, almeno non se vuoi avere identificatori e parole chiave nella tua lingua.

Supponiamo che tu abbia due regole: una per gli identificatori costituita da una o più lettere arbitrarie e una per una parola chiave costituita da lettere. Prendiamo ad esempio la parola chiave var . Ora consideriamo la stringa di input var variant . Se la regola dell'identificatore viene prima nella definizione del lexer, questa verrà tokenizzata come due identificatori. Chiaramente non è quello che vogliamo, quindi mettiamo prima la regola della parola chiave. Ma ora è tokenizzato come due% parole chiave% di%, seguito dall'identificatore var . Anche questo non è quello che vogliamo.

Quindi non c'è modo di ordinare le regole, in modo da poter ottenere ciò che vogliamo qui. Tuttavia la regola del munch massimo ci darebbe esattamente quello che vogliamo in casi come questo. Pertanto è preferibile.