Venendo con i token per un lexer

La tua domanda (come i tuoi suggerimenti finali del paragrafo) non riguarda proprio il lexer, ma riguarda il corretto design dell'interfaccia tra il lexer e il parser. Come puoi immaginare ci sono molti libri sulla progettazione di lexer e parser. Mi è piaciuto il parser book di Dick Grune , ma potrebbe non essere un buon libro introduttivo. A me non piace molto il libro basato su C di Appel , perché il codice non è estensivamente utile nel proprio compilatore (a causa dei problemi di gestione della memoria inerenti alla decisione di far finta che C sia come ML). La mia introduzione era il libro di PJ Brown , ma non è un buona introduzione generale (anche se abbastanza buono per gli interpreti in particolare). Ma torniamo alla tua domanda.

La risposta è, fai il più possibile nel lexer senza dover usare i vincoli in avanti o indietro.

Ciò significa che (a seconda dei dettagli della lingua) dovresti riconoscere una stringa come un "carattere seguito da una sequenza di non-" e quindi un altro "carattere. Restituiscilo al parser come una singola unità. Ci sono diversi motivi per questo, ma quelli importanti sono

1. Riduce la quantità di stato che il parser deve mantenere, limitando il consumo di memoria.
2. Ciò consente all'attuazione del lexer di concentrarsi sul riconoscimento dei blocchi fondamentali e libera il parser per descrivere come vengono utilizzati i singoli elementi sintattici per costruire un programma.

Molto spesso i parser possono intraprendere azioni immediate quando ricevono un token dal lexer. Ad esempio, non appena viene ricevuto IDENTIFIER, il parser può eseguire una ricerca nella tabella dei simboli per scoprire se il simbolo è già noto. Se il parser analizza anche le costanti di stringa come QUOTE (IDENTIFIER SPACES) * QUOTE eseguirai molte ricerche di tabelle di simboli irrilevanti, o finirai per sollevare la ricerca della tabella dei simboli più in alto nell'albero degli elementi di sintassi del parser, perché puoi fare solo al punto sei sicuro che non stai guardando una stringa.

Per riaffermare ciò che sto cercando di dire, ma in modo diverso, il lexer dovrebbe occuparsi dell'ortografia delle cose e del parser con la struttura delle cose.

Potresti notare che la mia descrizione di come appare una stringa sembra molto simile a un'espressione regolare. Questa non è una coincidenza. Gli analizzatori lessicali sono spesso implementati nelle piccole lingue (nel senso di Jon Bentley è un eccellente programma Pearls di programmazione ) che utilizza espressioni regolari. Sono abituato a pensare in termini di espressioni regolari quando riconosco il testo.

Per quanto riguarda la tua domanda sugli spazi bianchi, riconoscila nel lexer. Se la tua lingua è destinata a essere abbastanza libera, non restituire i token WHITESPACE al parser, perché dovrà solo buttarli via, quindi le regole di produzione del parser saranno spammate con rumore essenzialmente - cose da riconoscere solo per lanciare lontano.

Per quanto riguarda ciò che significa su come dovresti gestire gli spazi bianchi quando è sintatticamente significativo, non sono sicuro di poterti esprimere un giudizio che funzioni davvero bene senza saperne di più sulla tua lingua. Il mio giudizio istantaneo è quello di evitare casi in cui lo spazio bianco è talvolta importante e talvolta no, e utilizzare una sorta di delimitatore (come le virgolette). Ma se non puoi progettare la lingua in qualsiasi modo preferisci, questa opzione potrebbe non essere disponibile per te.

Esistono altri modi per realizzare sistemi di analisi del linguaggio di progettazione. Certamente ci sono sistemi di compilazione che ti permettono di specificare un sistema combinato di lexer e parser (penso che la versione Java di ANTLR lo faccia) ma Non ne ho mai usato uno.

Ultima nota storica. Decenni fa, era importante che il lexer facesse il più possibile prima di passare al parser, perché i due programmi non si sarebbero adattati alla memoria nello stesso momento. Fare di più nel lexer ha lasciato più memoria disponibile per rendere il parser intelligente. Ho usato il Whitesmiths C Compiler per un certo numero di anni, e se ho capito bene , funzionerebbe solo con 64 KB di RAM (era un programma MS-DOS di piccolo modello) e anche così ha tradotto una variante di C che era molto molto vicina a ANSI C.

Affronterò la tua ultima domanda, che in realtà non è stupida. I parser possono creare e costruire costrutti complessi su base carattere per carattere. Se ricordo, la grammatica di Harbison e Steele ("C - Un manuale di riferimento") ha produzioni che usano caratteri singoli come terminali e costruisce identificatori, stringhe, numeri, ecc. Come non-terminali dai singoli caratteri.

Dal punto di vista dei linguaggi formali, tutto ciò che un lexer basato su espressioni regolari può riconoscere e categorizzare come "string letterale", "identificatore", "numero", "parola chiave" e così via, anche un parser LL (1) può riconoscere. Quindi non c'è alcun problema teorico nell'usare un generatore di parser per riconoscere tutto.

Da un punto di vista algoritmico, un riconoscitore di espressioni regolari può essere eseguito molto più velocemente di qualsiasi parser. Da un punto di vista cognitivo, è probabilmente più facile per un programmatore interrompere il lavoro tra un lexer di espressioni regolari e un parser scritto con parser-generator.

Direi che le considerazioni pratiche inducono le persone a prendere la decisione di avere lessici e parser separati.

Sembra che tu stia tentando di scrivere un lexer / parser senza veramente capire le grammatiche. In genere, quando le persone scrivono un lexer e un parser, li stanno scrivendo per conformarsi ad alcune grammatiche. Il lexer dovrebbe restituire i token nella grammatica mentre il parser utilizza quei token per abbinare le regole / i non-terminali . Se si potesse facilmente analizzare il proprio input andando semplicemente byte per byte, un lexer e un parser potrebbero essere eccessivi.

I lessici rendono le cose più semplici.

Panoramica grammatica : una grammatica è un insieme di regole per il modo in cui dovrebbero apparire alcuni sintassi o input. Ad esempio, ecco una grammatica di giocattoli (simple_command is start symbol):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

Questa grammatica significa che -
Un simple_command è composto da o A) WORD seguito da DIGIT seguito da AND_SYMBOL (questi sono "token" che definisco)
B) "addizione_expression" (questa è una regola o "non-terminale")

Un addition_expression è composto da:
NUM seguito da un "+" seguito da un NUM (NUM è un "token" che definisco, "+" è un segno più letterale).

Pertanto, dal momento che simple_command è il "simbolo iniziale" (il punto di partenza), quando ricevo un token, controllo per vedere se si adatta a simple_command. Se il primo token nell'input è un WORD e il token successivo è un DIGIT e il token successivo è un AND_SYMBOL, allora ho abbinato alcuni simple_command e posso intervenire. Altrimenti proverò ad abbinarlo all'altra regola di simple_command che è addition_expression. Quindi, se il primo token era un NUM seguito da un '+' seguito da un NUM, allora ho trovato un semplice comando e ho fatto qualche azione. Se non è uno di questi, allora ho un errore di sintassi.

Questa è un'introduzione alle grammatiche molto, molto semplice. Per una comprensione più approfondita, consulta questo articolo wiki e cerca in tutto il Web per esercitazioni grammaticali senza contesto.

Usando un arrangiamento di lexer / parser, ecco un esempio di come potrebbe apparire il tuo parser:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Ok, in modo che il codice sia un po 'brutto e non consiglierei mai le dichiarazioni triple annidate. Ma il punto è, immagina di provare a fare quella cosa sopra carattere per carattere invece di usare le tue funzioni modulari "get_next_token" e "peek_next_token" . Seriamente, dagli un colpo. Non ti piacerà il risultato. Ora tieni presente che la grammatica di cui sopra è circa 30 volte meno complessa di quasi qualsiasi grammatica utile. Vedi il vantaggio di usare un lexer?

Onestamente, i lexer e parser non sono gli argomenti più basilari del mondo. Consiglierei di leggere prima e capire le grammatiche, quindi di leggere un po 'di lesseri / parser, quindi di immergermi.

My final question is the stupidest one: why is a lexer even necessary? It seems to me that the parser could go character-by-character and figure out where it is and what it expects.

Questo non è stupido, è solo la verità.

Ma la praticabilità in qualche modo dipende un po 'dai tuoi strumenti e obiettivi. Ad esempio, se si utilizza yacc senza un lexer e si desidera consentire le lettere unicode negli identificatori, è necessario scrivere una regola grande e brutta che enumera esplicitamente tutti i caratteri validi. Mentre, in un lexer, potresti chiedere una routine di libreria se un personaggio è un membro della categoria letter.

Usare o non usare un lexer è questione di avere un livello di astrazione tra la tua lingua e il livello del personaggio. Nota che il livello del personaggio, al giorno d'oggi, è un'altra astrazione sopra il livello del byte, che è un'astrazione sopra il livello del bit.

Quindi, finalmente, potresti persino analizzare a livello di bit.

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

No, non può. Che dire di "(" ? Secondo te, quella non è una stringa valida. E fughe?

In generale, il modo migliore per trattare gli spazi bianchi è ignorarlo, oltre a delimitare i token. Molte persone preferiscono spazi bianchi molto diversi e l'applicazione delle regole degli spazi bianchi è controversa al meglio.