Come viene implementato maximal-munch?

Question

Sto studiando compilatori e sto imparando sull'analisi lessicale. Capisco che si specifica ogni lessema come espressione regolare, e usando flex, un lexer può essere generato automaticamente. Sto imparando ulteriormente come l'espressione regolare viene convertita in un NFA che viene poi convertito in un DFA, dove può essere rapidamente valutato.

Tuttavia, la mia domanda è: come è implementata la regola maximal-munch? Internamente, come fa il lexer a sapere "andare avanti" per trovare il lessema più lungo possibile?

Grazie!

Answer 1

L'algoritmo Maximal Munch è implementata aggiungendo una piccola quantità di stato mutabile all'esecutore DFA, e aggiungendo la capacità dell'esecutore DFA per "riavvolgere" l'ingresso: in effetti, dotandolo di funzioni come tell() e seek().

Vale anche la pena notare che il DFA non è completo, nel senso che la funzione di transizione non è completa. Alcune coppie {state, input} non hanno un risultato definito. [Nota 2]

Con questo in mente, l'algoritmo è il seguente:

Set Accepted NFA State to ⊥ 
Set Accepted Position to Tell(Input Stream) 
Set State to Starting State 
Repeat: 
    If State ∈ Accepting: 
    Set Accepted NFA State to Accepting NFA State for State [Note 1] 
    Set Accepted Position to Tell(Input Stream) 
    Read one symbol from Input Stream into Next Symbol 
    If there is a transition from {State, Next Symbol} to New State: 
    Set State to New State 
    Continue the loop 
    Otherwise: 
    Rewind Input Stream to Accepted Position 
    Return Accepted NFA State 

Se l'algoritmo ritorna e inferiore ;, quindi senza gettone è stato riconosciuto e il flusso di input saranno stati riavvolto nella posizione iniziale .

---

Note:

1. La NFA ha in genere un omomorfismo univoca tra gli stati e le azioni di accettare, ma l'algoritmo di costruzione DFA può combinare due accettare stati NFA con diverse azioni. In questo caso, l'algoritmo flex deve dare priorità alla prima azione nel file di input. Nell'algoritmo sopra riportato, rappresentiamo questo mappando ogni stato DFA accettante al componente che accetta lo stato NFA che ha la priorità.

2. È facile completare il DFA aggiungendo uno stato aggiuntivo (e unico) sink che non accetta e che ha solo transizioni su se stesso. Quindi possiamo aggiungere lo stato sink come transizione per qualsiasi transizione altrimenti non specificata. Se chiamiamo lo stato sink e il fondo; allora sarà chiaro come modificare l'algoritmo fornito; in pratica, questo non è affatto necessario perché nella pratica non ci interessa che il DFA sia incompleto. Tuttavia, ha un qualche impatto sugli algoritmi di minimizzazione dello stato.