Lexing: un token per operatore o un token operatore universale?

3

Durante il lexing, quale sarebbe il modo migliore per tokenizzare gli operatori? Crei solo un token BinaryOperator o un token separato per ogni singolo operatore binario? Esempi: PlusOperator , MinusOperator , DivisionOperator ...

Sono teso ad avere uno universale, ma passando dalle documentazioni e alle fonti di progetto che ho letto la stragrande maggioranza dei lexer usano un token per operatore. C'è una ragione particolare per questo? Ha importanza? Ti dà qualche vantaggio?

    
posta Jeroen Bollen 02.05.2014 - 15:30
fonte

4 risposte

7

Una volta ho scritto un programma che utilizzava un tipo di operatore universale. È stata un'idea orribile, perché il numero di assegni è esploso. Per verificare se avessi un operatore di addizione, dovrei controllare che il token corrente sia un token operatore e contiene la stringa "+" come valore.

Quando si utilizzano token diversi per operatori diversi, si ottengono numerosi vantaggi:

  • Se si utilizza un generatore di parser, l'utilizzo di un diverso tipo di token per ciascun operatore semplifica notevolmente la gestione degli operatori. A seconda del generatore, potrebbe essere effettivamente impossibile gestire la precedenza degli operatori a meno che ciascun operatore non abbia un diverso tipo di token.

    In particolare, un parser senza contesto è limitato a considerare solo il tipo di ciascun token. Altrimenti, sbarcheremo rapidamente nel territorio "ricorsivamente enumerabile".

  • Non è necessario memorizzare la stringa lessata di un operatore, poiché tutte le informazioni necessarie sono già memorizzate nel tipo di token.

risposta data 02.05.2014 - 15:54
fonte
5

La maggior parte dei generatori di parser richiede che diversi operatori siano distinti nella fase di analisi lessicale. Se stai scrivendo il parser a mano, allora l'opzione va bene.

Se utilizzi un tipo di token universale per l'operatore, sarai (probabilmente) in grado di scrivere un parser di espressioni generali con i tuoi operatori (comprese le informazioni sulla precedenza) definiti in una struttura di dati (piuttosto che cablati nel codice del parser ), che potrebbe essere più utile se disponi di molti operatori e sarebbe essenziale se stai analizzando una lingua che consenta agli operatori definiti dall'utente.

L'utilizzo di un tipo di token separato per ciascun operatore consente di mantenere una distinzione più chiara tra gli stadi di analisi lessicale e sintattica (tradizionali) e può rendere più semplice per le altre persone (che hanno familiarità con lesseri e parser separati) per capire il tuo sistema.

In generale, penso che questa sia solo una scelta stilistica nella maggior parte dei casi.

    
risposta data 02.05.2014 - 15:50
fonte
5

Poiché i token significano qualcosa di letteralmente diverso, rendili unici. Se hai bisogno di capire il set di essi come un singolo elemento, il posto per farlo è nella grammatica del parser:

operator := PlusOperator | MinusOperator | DivisionOperator

Ricorda che il compito del lexer è di dividere l'input e non prendere decisioni semantiche sul suo significato. Questa è la faccenda del parser e io preferirei non inserire alcun tipo di significato nei nomi dei token:

operator := PLUS | MINUS | DIVIDE
    
risposta data 02.05.2014 - 15:53
fonte
0

Se hai un supporto linguistico che può sfruttare, token più grandi possono aiutare a migliorare l'efficienza.

Dalla mia esperienza personale di scrittura di un lexer in Objective-C, ho sfruttato la funzionalità che un oggetto Objective-C può cambiare classe. Ho definito tutti i token binari come un token, ma in AST ho usato una classe per ogni operatore binario, condividendo una classe base. Quando lexing il lexer emette un oggetto della classe base, BinaryOperator , che successivamente si modifica in oggetto della classe specifica dell'operatore utilizzando la ricerca di tabelle più semplice.

    
risposta data 02.05.2014 - 19:56
fonte

Leggi altre domande sui tag