Come avvicinarsi alla scrittura di un interprete da zero

Alcuni dicono che "tutto si riduce a uno e zero", ma capiamo davvero come i nostri programmi vengono tradotti in quei bit?

Sia i compilatori che gli interpreti prendono una stringa grezza che rappresenta un programma, la analizzano e ne danno un senso. Sebbene gli interpreti siano i più semplici dei due, scrivere anche un interprete molto semplice (che fa solo addizioni e moltiplicazioni) sarà istruttivo. Ci concentreremo su ciò che compilatori e interpreti hanno in comune: leggere e analizzare l'input.

Le cose da fare e da non fare per scrivere il proprio interprete

I lettori potrebbero chiedersi cosa c'è che non va in una regex? Le espressioni regolari sono potenti, ma le grammatiche del codice sorgente non sono abbastanza semplici da poter essere analizzate da esse. Nemmeno i linguaggi specifici del dominio (DSL) e un client potrebbe aver bisogno di un DSL personalizzato per le espressioni di autorizzazione, ad esempio. Ma anche senza applicare direttamente questa abilità, scrivere un interprete rende molto più facile apprezzare lo sforzo dietro molti linguaggi di programmazione, formati di file e DSL.

Scrivere correttamente i parser a mano può essere difficile con tutti i casi limite coinvolti. Ecco perché ci sono strumenti popolari, come ANTLR, che possono generare parser per molti linguaggi di programmazione popolari. Esistono anche librerie chiamate parser combinators , che consentono agli sviluppatori di scrivere parser direttamente nei loro linguaggi di programmazione preferiti. Gli esempi includono FastParse per Scala e Parsec per Python.

Raccomandiamo che, in un contesto professionale, i lettori utilizzino tali strumenti e librerie per evitare di reinventare la ruota. Tuttavia, comprendere le sfide e le possibilità di scrivere un interprete da zero aiuterà gli sviluppatori a sfruttare tali soluzioni in modo più efficace.

Panoramica dei componenti dell'interprete

Un interprete è un programma complesso, quindi ci sono più fasi:

1. Un lexer è la parte di un interprete che trasforma una sequenza di caratteri (testo normale) in una sequenza di token.
2. Un parser , a sua volta, prende una sequenza di token e produce un albero sintattico astratto (AST) di un linguaggio. Le regole con cui opera un parser sono solitamente specificate da una grammatica formale.
3. Un interprete è un programma che interpreta al volo l'AST del sorgente di un programma (senza prima compilarlo).

Non costruiremo qui un interprete integrato specifico. Invece, esploreremo ciascuna di queste parti e i loro problemi comuni con esempi separati. Alla fine, il codice utente sarà simile a questo:

 val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res")

Dopo le tre fasi, ci si aspetta che questo codice calcoli un valore finale e stampi il Result is: 19 . Questo tutorial utilizza Scala perché è:

• Molto conciso, adatta molto codice in una schermata.
• Orientato all'espressione, senza necessità di variabili non inizializzate/null.
• Digita sicuro, con una potente libreria di raccolte, enumerazioni e classi di case.

In particolare, il codice qui è scritto nella sintassi delle parentesi facoltative Scala3 (una sintassi simile a Python, basata sull'indentazione). Ma nessuno degli approcci è specifico di Scala e Scala è simile a molti altri linguaggi: i lettori troveranno semplice convertire questi esempi di codice in altri linguaggi. A parte ciò, gli esempi possono essere eseguiti online utilizzando Scastie.

Infine, le sezioni Lexer, Parser e Interpreter hanno grammatiche di esempio diverse . Come mostra il repository GitHub corrispondente, le dipendenze negli esempi successivi cambiano leggermente per implementare queste grammatiche, ma i concetti generali rimangono gli stessi.

Interprete Componente 1: Scrivere un Lexer

Diciamo che vogliamo leggere questa stringa: "123 + 45 true * false1" . Contiene diversi tipi di token:

• Letterali interi
• Operatore A +
• Un * operatore
• Un true letterale
• Un identificatore, false1

Gli spazi bianchi tra i token verranno saltati in questo esempio.

In questa fase, le espressioni non devono avere senso; il lexer converte semplicemente la stringa di input in un elenco di token. (Il compito di "dare un senso ai token" è lasciato al parser.)

Useremo questo codice per rappresentare un token:

 case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOF

Ogni token ha un tipo, una rappresentazione testuale e una posizione nell'input originale. La posizione può aiutare gli utenti finali del lexer con il debug.

Il token EOF è un token speciale che segna la fine dell'input. Non esiste nel testo di partenza; lo usiamo solo per semplificare la fase del parser.

Questo sarà l'output del nostro lexer:

 Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )

Esaminiamo l'implementazione:

 class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toList

Iniziamo con un elenco vuoto di token, quindi esaminiamo la stringa e aggiungiamo i token man mano che arrivano.

Usiamo il carattere lookahead per decidere il tipo del gettone successivo . Si noti che il carattere lookahead non è sempre il carattere più avanti da esaminare. Sulla base del lookahead, sappiamo che aspetto ha il token e utilizziamo currentPos per scansionare tutti i caratteri previsti nel token corrente, quindi aggiungere il token all'elenco:

Se il lookahead è uno spazio bianco, lo saltiamo. I gettoni con una sola lettera sono banali; li aggiungiamo e incrementiamo l'indice. Per gli interi, dobbiamo solo occuparci dell'indice.

Ora arriviamo a qualcosa di un po' complicato: identificatori contro letterali. La regola è che prendiamo la corrispondenza più lunga possibile e controlliamo se è un letterale; se non lo è, è un identificatore.

Prestare attenzione quando si maneggiano operatori come < e <= . Lì devi guardare avanti un altro carattere e vedere se è = prima di concludere che è un operatore <= . Altrimenti, è solo un < .

Con ciò, il nostro lexer ha prodotto un elenco di token.

Interprete Componente 2: scrittura di un parser

Dobbiamo dare una struttura ai nostri token: non possiamo fare molto con una sola lista. Ad esempio, dobbiamo sapere:

Quali espressioni sono nidificate? Quali operatori vengono applicati in quale ordine? Quali regole di scoping si applicano, se presenti?

Una struttura ad albero supporta la nidificazione e l'ordinamento. Ma prima dobbiamo definire alcune regole per la costruzione degli alberi. Vorremmo che il nostro parser non fosse ambiguo, restituendo sempre la stessa struttura per un dato input.

Si noti che il seguente parser non usa l'esempio precedente di lexer . Questo serve per aggiungere numeri, quindi la sua grammatica ha solo due token, '+' e NUM :

 expr -> expr '+' expr expr -> NUM

Un equivalente, utilizzando un carattere pipe ( | ) come simbolo "o" come nelle espressioni regolari, è:

 expr -> expr '+' expr | NUM

In ogni caso, abbiamo due regole: una che dice che possiamo sommare due expr e un'altra che dice che expr può essere un token NUM , che qui significherà un numero intero non negativo.

Le regole sono solitamente specificate con una grammatica formale . Una grammatica formale è composta da: Le regole stesse, come mostrato sopra Una regola di partenza (la prima regola specificata, per convenzione) Due tipi di simboli per definire le regole con: Terminali: le “lettere” (e altri caratteri) della nostra lingua— i simboli irriducibili che compongono i token Non terminali: costrutti intermedi usati per l'analisi (cioè simboli che possono essere sostituiti)

Solo un non terminale può trovarsi sul lato sinistro di una regola; il lato destro può avere sia terminali che non terminali. Nell'esempio sopra, i terminali sono '+' e NUM e l'unico non terminale è expr . Per un esempio più ampio, nel linguaggio Java, abbiamo terminali come 'true' , '+' , Identifier e '[' , e non terminali come BlockStatements , ClassBody e MethodOrFieldDecl .

Ci sono molti modi in cui potremmo implementare questo parser. Qui useremo una tecnica di analisi di "discesa ricorsiva". È il tipo più comune perché è il più semplice da comprendere e implementare.

Un parser discendente ricorsivo usa una funzione per ogni non terminale nella grammatica. Si parte dalla regola di partenza e da lì si scende (da qui “discesa”), cercando di capire quale regola applicare in ogni funzione. La parte "ricorsiva" è vitale perché possiamo annidare ricorsivamente i non terminali! Le espressioni regolari non possono farlo: non possono nemmeno gestire parentesi bilanciate. Quindi abbiamo bisogno di uno strumento più potente.

Un parser per la prima regola sarebbe simile a questo (codice completo):

 def expr() = expr() eat('+') expr()

La funzione eat() controlla se il lookahead corrisponde al token previsto e quindi sposta l'indice lookahead. Sfortunatamente, questo non funzionerà ancora perché dobbiamo risolvere alcuni problemi con la nostra grammatica.

Ambiguità grammaticale

Il primo problema è l'ambiguità della nostra grammatica, che potrebbe non essere evidente a prima vista:

 expr -> expr '+' expr | NUM

Dato l'input 1 + 2 + 3 , il nostro parser potrebbe scegliere di calcolare prima l' expr di sinistra o l' expr di destra nell'AST risultante:

Ecco perché dobbiamo introdurre una certa asimmetria :

 expr -> expr '+' NUM | NUM

L'insieme di espressioni che possiamo rappresentare con questa grammatica non è cambiato dalla sua prima versione. Solo ora è inequivocabile : il parser va sempre a sinistra. Proprio quello di cui avevamo bisogno!

Questo rende la nostra operazione + associativa a sinistra , ma questo diventerà evidente quando arriveremo alla sezione Interprete.

Regole ricorsive a sinistra

Sfortunatamente, la correzione di cui sopra non risolve l'altro nostro problema, la ricorsione a sinistra:

 def expr() = expr() eat('+') eat(NUM)

Abbiamo una ricorsione infinita qui. Se dovessimo entrare in questa funzione, alla fine otterremmo un errore di overflow dello stack. Ma la teoria dell'analisi può aiutare!

Supponiamo di avere una grammatica come questa, dove alpha potrebbe essere qualsiasi sequenza di terminali e non terminali:

 A -> A alpha | B

Possiamo riscrivere questa grammatica come:

 A -> BA' A' -> alpha A' | epsilon

Lì, epsilon è una stringa vuota: niente, nessun token.

Prendiamo l'attuale revisione della nostra grammatica:

 expr -> expr '+' NUM | NUM

Seguendo il metodo di riscrittura delle regole di analisi descritto sopra, con alpha come token '+' NUM , la nostra grammatica diventa:

 expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilon

Ora la grammatica è OK e possiamo analizzarla con un parser discendente ricorsivo. Vediamo come un tale parser cercherà quest'ultima iterazione della nostra grammatica:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head

Qui utilizziamo il token EOF per semplificare il nostro parser. Siamo sempre sicuri che ci sia almeno un token nella nostra lista, quindi non abbiamo bisogno di gestire un caso speciale di una lista vuota.

Inoltre, se passiamo a un lexer in streaming, non avremmo un elenco in memoria ma un iteratore, quindi abbiamo bisogno di un marker per sapere quando arriviamo alla fine dell'input. Quando arriviamo alla fine, il token EOF dovrebbe essere l'ultimo token rimasto.

Scorrendo il codice, possiamo vedere che un'espressione può essere solo un numero. Se non è rimasto nulla, il token successivo non sarebbe un Plus , quindi smetteremmo di analizzare. L'ultimo token sarebbe EOF e avremmo finito.

Se la stringa di input ha più token, questi dovrebbero apparire come + 123 . È qui che entra in gioco la ricorsione su exprOpt() !

Generazione di un AST

Ora che abbiamo analizzato con successo la nostra espressione, è difficile farci qualcosa così com'è. Potremmo inserire alcuni callback nel nostro parser, ma sarebbe molto ingombrante e illeggibile. Invece, restituiremo un AST, un albero che rappresenta l'espressione di input:

 case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case Epsilon

Questo assomiglia alle nostre regole, usando semplici classi di dati.

Il nostro parser ora restituisce una struttura dati utile:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon

Per eat() , error() e altri dettagli di implementazione, consulta il repository GitHub allegato.

Regole semplificative

Il nostro ExprOpt non terminale può ancora essere migliorato:

 '+' NUM exprOpt | epsilon

È difficile riconoscere il modello che rappresenta nella nostra grammatica solo guardandolo. Si scopre che possiamo sostituire questa ricorsione con un costrutto più semplice:

 ('+' NUM)*

Questo costrutto significa semplicemente che '+' NUM ricorre zero o più volte.

Ora la nostra grammatica completa si presenta così:

 expr -> NUM exprOpt* exprOpt -> '+' NUM

E il nostro AST sembra più bello:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int)

Il parser risultante ha la stessa lunghezza ma è più semplice da capire e da usare. Abbiamo eliminato Epsilon , che ora è implicito nell'iniziare con una struttura vuota.

Non avevamo nemmeno bisogno della classe ExprOpt qui. Avremmo potuto semplicemente inserire case class Expr(num: Int, exprOpts: Seq[Int]) , o in formato grammaticale, NUM ('+' NUM)* . Allora perché non l'abbiamo fatto?

Considera che se avessimo più operatori possibili, come - o * , avremmo una grammatica come questa:

 expr -> NUM exprOpt* exprOpt -> [+-*] NUM

In questo caso, l'AST necessita di ExprOpt per adattarsi al tipo di operatore:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int)

Nota che la sintassi [+-*] nella grammatica significa la stessa cosa delle espressioni regolari: "uno di quei tre caratteri". Lo vedremo presto in azione.

Interprete Componente 3: Scrivere un interprete

Il nostro interprete utilizzerà il nostro lexer e parser per ottenere l'AST della nostra espressione di input e quindi valuterà quell'AST nel modo desiderato. In questo caso si tratta di numeri e si vuole valutare la loro somma.

Nell'implementazione del nostro esempio di interprete, useremo questa semplice grammatica:

 expr -> NUM exprOpt* exprOpt -> [+-] NUM

E questo AST:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)

(Abbiamo spiegato come implementare un lexer e un parser per grammatiche simili, ma tutti i lettori che si bloccano possono esaminare le implementazioni lexer e parser per questa grammatica esatta nel repository.)

Ora vedremo come scrivere un interprete per la grammatica di cui sopra:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp

Se abbiamo analizzato il nostro input in un AST senza riscontrare un errore, siamo sicuri che avremo sempre almeno un NUM . Quindi prendiamo i numeri opzionali e li aggiungiamo (o li sottraiamo) al nostro risultato.

La nota dall'inizio sull'associatività a sinistra di + è ora chiara: partiamo dal numero più a sinistra e ne aggiungiamo altri, da sinistra a destra. Questo può sembrare poco importante per l'addizione, ma considera la sottrazione: l'espressione 5 - 2 - 1 viene valutata come (5 - 2) - 1 = 3 - 1 = 2 e non come 5 - (2 - 1) = 5 - 1 = 4 !

Ma se vogliamo andare oltre l'interpretazione degli operatori più e meno, c'è un'altra regola da definire.

Precedenza

Sappiamo come analizzare un'espressione semplice come 1 + 2 + 3 , ma quando si tratta di 2 + 3 * 4 + 5 , abbiamo un po' di problemi.

La maggior parte delle persone concorda sulla convenzione secondo cui la moltiplicazione ha la precedenza sull'addizione. Ma il parser non lo sa. Non possiamo semplicemente valutarlo come ((2 + 3) * 4) + 5 . Invece vogliamo (2 + (3 * 4)) + 5 .

Ciò significa che dobbiamo prima valutare la moltiplicazione . La moltiplicazione deve essere più lontana dalla radice dell'AST per forzarne la valutazione prima dell'addizione. Per questo, dobbiamo introdurre ancora un altro livello di indirizzamento.

Correggere una grammatica ingenua dall'inizio alla fine

Questa è la nostra grammatica originale, ricorsiva a sinistra, che non ha regole di precedenza:

 expr -> expr '+' expr | expr '*' expr | NUM

Innanzitutto, gli diamo regole di precedenza e rimuoviamo la sua ambiguità :

 expr -> expr '+' term | term term -> term '*' NUM | NUM

Quindi ottiene regole non ricorsive a sinistra :

 expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUM

Il risultato è un AST meravigliosamente espressivo:

 case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)

Questo ci lascia con un'implementazione concisa dell'interprete:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmp

Come prima, le idee nel lesser e nella grammatica richiesti sono state trattate in precedenza, ma i lettori possono trovarle nel repository, se necessario.

I prossimi passi nella scrittura di interpreti

Non ne abbiamo parlato, ma la gestione e la segnalazione degli errori sono caratteristiche cruciali di qualsiasi parser. Come sviluppatori, sappiamo quanto può essere frustrante quando un compilatore produce errori confusi o fuorvianti. È un'area che ha molti problemi interessanti da risolvere, come fornire messaggi di errore corretti e precisi, non dissuadere l'utente con più messaggi del necessario e recuperare con grazia dagli errori. Spetta agli sviluppatori scrivere un interprete o un compilatore per garantire che i loro futuri utenti abbiano un'esperienza migliore.

Nell'esaminare i nostri esempi di lexer, parser e interpreti, abbiamo solo scalfito la superficie delle teorie alla base di compilatori e interpreti, che trattano argomenti come:

• Scopi e tabelle dei simboli
• Tipi statici
• Ottimizzazione del tempo di compilazione
• Analizzatori di programmi statici e linter
• Formattazione del codice e stampa graziosa
• Lingue specifiche del dominio

Per ulteriori letture, ti consiglio queste risorse:

• Modelli di implementazione del linguaggio di Terence Parr
• Un libro online gratuito, Crafting Interpreters , di Bob Nystrom
• Introduzione alla grammatica e all'analisi di Paul Klint
• Scrittura di buoni messaggi di errore del compilatore di Caleb Meredith
• Gli appunti del corso della East Carolina University “Program Translation and Compiling”