Cum să abordați scrierea unui interpret de la zero

Unii spun că „totul se reduce la unu și la zero” – dar înțelegem cu adevărat cum se tradus programele noastre în acele biți?

Compilatorii și interpreții preiau atât un șir brut care reprezintă un program, îl analizează și îi dau sens. Deși interpreții sunt cei mai simpli dintre cei doi, scrierea chiar și a unui interpret foarte simplu (care face doar adunări și înmulțiri) va fi instructiv. Ne vom concentra pe ceea ce au în comun compilatorii și interpreții: lexarea și analizarea intrării.

Ce trebuie și ce nu trebuie să-ți scrii propriul interpret

Cititorii se pot întreba Ce este în neregulă cu o expresie regex? Expresiile regulate sunt puternice, dar gramaticile codului sursă nu sunt suficient de simple pentru a fi analizate de ele. Nici limbajele specifice domeniului (DSL) nu sunt, iar un client ar putea avea nevoie de un DSL personalizat pentru expresiile de autorizare, de exemplu. Dar chiar și fără aplicarea directă a acestei abilități, scrierea unui interpret face mult mai ușor să apreciezi efortul din spatele multor limbaje de programare, formate de fișiere și DSL-uri.

Scrierea corectă manuală a analizatorilor poate fi o provocare cu toate cazurile marginale implicate. De aceea, există instrumente populare, cum ar fi ANTLR, care pot genera parsere pentru multe limbaje de programare populare. Există, de asemenea, biblioteci numite combinatoare de parser , care permit dezvoltatorilor să scrie parsere direct în limbajele lor de programare preferate. Exemplele includ FastParse pentru Scala și Parsec pentru Python.

Recomandăm ca, într-un context profesional, cititorii să folosească astfel de instrumente și biblioteci pentru a evita reinventarea roții. Totuși, înțelegerea provocărilor și posibilităților de a scrie un interpret de la zero va ajuta dezvoltatorii să folosească astfel de soluții mai eficient.

Prezentare generală a componentelor interpretului

Un interpret este un program complex, deci are mai multe etape:

1. Un lexer este partea unui interpret care transformă o secvență de caractere (text simplu) într-o secvență de jetoane.
2. Un parser , la rândul său, ia o secvență de jetoane și produce un arbore de sintaxă abstractă (AST) al unui limbaj. Regulile prin care funcționează un parser sunt de obicei specificate de o gramatică formală.
3. Un interpret este un program care interpretează AST-ul sursei unui program din mers (fără a-l compila mai întâi).

Nu vom construi aici un interpret specific, integrat. În schimb, vom explora fiecare dintre aceste părți și problemele lor comune cu exemple separate. În final, codul utilizatorului va arăta astfel:

 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")

Urmând cele trei etape, ne așteptăm ca acest cod să calculeze o valoare finală și să imprimăm Result is: 19 . Acest tutorial se întâmplă să folosească Scala deoarece este:

• Foarte concis, încadrând o mulțime de cod într-un singur ecran.
• Orientat spre expresie, fără a fi nevoie de variabile neinițializate/nule.
• Tastați sigur, cu o bibliotecă puternică de colecții, enumerări și clase de cazuri.

Mai exact, codul de aici este scris în sintaxă Scala3 opțional-acolade (o sintaxă Pythonlike, bazată pe indentare). Dar niciuna dintre abordări nu este specifică Scala, iar Scala este similar cu multe alte limbi: cititorii vor găsi simplu să convertească aceste mostre de cod în alte limbi. Cu excepția asta, exemplele pot fi rulate online folosind Scastie.

În cele din urmă, secțiunile Lexer, Parser și Interpreter au exemple de gramatică diferite . După cum arată repo-ul GitHub corespunzător, dependențele din exemplele ulterioare se modifică ușor pentru a implementa aceste gramatici, dar conceptele generale rămân aceleași.

Interpret Componenta 1: Scrierea unui Lexer

Să presupunem că vrem să lexăm acest șir: "123 + 45 true * false1" . Conține diferite tipuri de jetoane:

• Literale întregi
• operator A +
• Un operator *
• Un true literal
• Un identificator, false1

Spațiul alb dintre jetoane va fi omis în acest exemplu.

În această etapă, expresiile nu trebuie să aibă sens; lexerul convertește pur și simplu șirul de intrare într-o listă de jetoane. (Slujba de a „a da sens jetoanelor” este lăsată în sarcina analizorului.)

Vom folosi acest cod pentru a reprezenta un simbol:

 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

Fiecare jeton are un tip, o reprezentare textuală și o poziție în intrarea originală. Poziția poate ajuta utilizatorii finali ai lexerului cu depanarea.

Jetonul EOF este un jeton special care marchează sfârșitul introducerii. Nu există în textul sursă; îl folosim doar pentru a simplifica etapa parserului.

Aceasta va fi rezultatul lexerului nostru:

 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) )

Să examinăm implementarea:

 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

Începem cu o listă goală de jetoane, apoi trecem prin șir și adăugăm jetoane pe măsură ce vin.

Folosim caracterul lookahead pentru a decide tipul următorului jeton . Rețineți că caracterul lookahead nu este întotdeauna cel mai îndepărtat caracter care este examinat. Pe baza anticipării, știm cum arată jetonul și folosim currentPos pentru a scana toate caracterele așteptate din jetonul curent, apoi adăugăm jetonul în listă:

Dacă perspectiva este spațiu alb, îl omitem. Jetoanele cu o singură literă sunt banale; le adăugăm și creștem indicele. Pentru numere întregi, trebuie să avem grijă doar de index.

Acum ajungem la ceva un pic complicat: identificatori versus literali. Regula este că luăm cea mai lungă potrivire posibilă și verificăm dacă este un literal; dacă nu este, este un identificator.

Aveți grijă când manipulați operatori precum < și <= . Acolo trebuie să priviți înainte încă un caracter și să vedeți dacă este = înainte de a concluziona că este un operator <= . Altfel, este doar un < .

Cu asta, lexerul nostru a produs o listă de jetoane.

Interpret Componenta 2: Scrierea unui parser

Trebuie să dăm o structură jetoanelor noastre — nu putem face mare lucru doar cu o listă. De exemplu, trebuie să știm:

Ce expresii sunt imbricate? Ce operatori sunt aplicați în ce ordine? Ce reguli de acoperire se aplică, dacă există?

O structură de arbore sprijină cuibărirea și ordonarea. Dar mai întâi, trebuie să definim câteva reguli pentru construirea copacilor. Ne-am dori ca analizatorul nostru să fie clar – să returneze întotdeauna aceeași structură pentru o intrare dată.

Rețineți că următorul parser nu folosește exemplul de lexer anterior . Acesta este pentru a adăuga numere, deci gramatica are doar două simboluri, '+' și NUM :

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

Un echivalent, folosind un caracter pipe ( | ) ca simbol „sau” ca în expresiile regulate, este:

 expr -> expr '+' expr | NUM

În orice caz, avem două reguli: una care spune că putem aduna două expr și alta care spune că expr poate fi un token NUM , ceea ce aici va însemna un întreg nenegativ.

Regulile sunt de obicei specificate cu o gramatică formală . O gramatică formală constă din: Regulile în sine, așa cum se arată mai sus O regulă de început (prima regulă specificată, conform convenției) Două tipuri de simboluri pentru a defini regulile cu: Terminale: „literele” (și alte caractere) ale limbii noastre— simbolurile ireductibile care alcătuiesc jetoanele Nonterminale: constructe intermediare utilizate pentru parsare (adică simboluri care pot fi înlocuite)

Numai un nonterminal poate fi pe partea stângă a unei reguli; partea dreaptă poate avea atât terminale cât și neterminale. În exemplul de mai sus, terminalele sunt '+' și NUM , iar singurul nonterminal este expr . Pentru un exemplu mai larg, în limbajul Java, avem terminale precum 'true' , '+' , Identifier și '[' , și nonterminale precum BlockStatements , ClassBody și MethodOrFieldDecl .

Există multe moduri în care am putea implementa acest parser. Aici, vom folosi o tehnică de analizare a „coborârii recursive”. Este cel mai comun tip, deoarece este cel mai simplu de înțeles și implementat.

Un parser de coborâre recursiv folosește o funcție pentru fiecare nonterminal din gramatică. Pornește de la regula de pornire și coboară de acolo (de aici „coborâre”), dându-și seama ce regulă să se aplice în fiecare funcție. Partea „recursivă” este vitală, deoarece putem cuibări recursiv nonterminale! Regexurile nu pot face asta: nici măcar nu pot face față parantezelor echilibrate. Deci avem nevoie de un instrument mai puternic.

Un parser pentru prima regulă ar arăta cam așa (codul complet):

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

Funcția eat() verifică dacă lookahead se potrivește cu simbolul așteptat și apoi mută indexul lookahead. Din păcate, acest lucru nu va funcționa încă, deoarece trebuie să remediem unele probleme cu gramatica noastră.

Ambiguitate gramaticală

Prima problemă este ambiguitatea gramaticii noastre, care poate să nu fie evidentă la prima vedere:

 expr -> expr '+' expr | NUM

Având în vedere intrarea 1 + 2 + 3 , analizatorul nostru ar putea alege să calculeze mai întâi fie expr -ul din stânga, fie expr din dreapta în AST rezultat:

De aceea trebuie să introducem ceva asimetrie :

 expr -> expr '+' NUM | NUM

Setul de expresii pe care le putem reprezenta cu această gramatică nu s-a schimbat de la prima sa versiune. Numai că acum este clar : analizatorul merge întotdeauna la stânga. Exact ce ne trebuia!

Acest lucru face ca operația noastră + left associative , dar acest lucru va deveni evident când ajungem la secțiunea Interpret.

Reguli recursive la stânga

Din păcate, remedierea de mai sus nu rezolvă cealaltă problemă a noastră, recursiunea stângă:

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

Avem recursivitate infinită aici. Dacă ar fi să pășim în această funcție, în cele din urmă am primi o eroare de depășire a stivei. Dar teoria analizei poate ajuta!

Să presupunem că avem o gramatică ca aceasta, în care alpha ar putea fi orice succesiune de terminale și nonterminale:

 A -> A alpha | B

Putem rescrie această gramatică ca:

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

Acolo, epsilon este un șir gol - nimic, nici un simbol.

Să luăm revizuirea actuală a gramaticii noastre:

 expr -> expr '+' NUM | NUM

Urmând metoda de rescriere a regulilor de parsare detaliată mai sus, alpha fiind jetoanele noastre '+' NUM , gramatica noastră devine:

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

Acum gramatica este în regulă și o putem analiza cu un parser recursiv descent. Să vedem cum ar căuta un astfel de analizator pentru această ultimă iterație a gramaticii noastre:

 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

Aici folosim simbolul EOF pentru a simplifica analizatorul nostru. Suntem întotdeauna siguri că există cel puțin un token în lista noastră, așa că nu trebuie să ne ocupăm de un caz special al unei liste goale.

De asemenea, dacă trecem la un lexer de streaming, nu am avea o listă în memorie, ci un iterator, așa că avem nevoie de un marker pentru a ști când ajungem la sfârșitul intrării. Când ajungem la final, jetonul EOF ar trebui să fie ultimul jeton rămas.

Mergând prin cod, putem vedea că o expresie poate fi doar un număr. Dacă nu mai rămâne nimic, următorul token nu ar fi un Plus , așa că am opri analizarea. Ultimul simbol ar fi EOF și am terminat.

Dacă șirul de intrare are mai multe jetoane, atunci acestea ar trebui să arate ca + 123 . Acolo începe recursiunea exprOpt() !

Generarea unui AST

Acum că ne-am analizat cu succes expresia, este greu să facem ceva cu ea așa cum este. Am putea pune niște apeluri inverse în analizatorul nostru, dar ar fi foarte greoi și imposibil de citit. În schimb, vom returna un AST, un arbore care reprezintă expresia de intrare:

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

Acest lucru seamănă cu regulile noastre, folosind clase de date simple.

Analizorul nostru returnează acum o structură de date utilă:

 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

Pentru eat() , error() și alte detalii de implementare, consultați depozitul GitHub însoțitor.

Simplificarea regulilor

Nonterminalul nostru ExprOpt poate fi încă îmbunătățit:

 '+' NUM exprOpt | epsilon

Este greu să recunoaștem tiparul pe care îl reprezintă în gramatica noastră doar privindu-l. Se pare că putem înlocui această recursivitate cu un construct mai simplu:

 ('+' NUM)*

Această construcție înseamnă pur și simplu '+' NUM apare de zero sau de mai multe ori.

Acum gramatica noastră completă arată astfel:

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

Și AST-ul nostru arată mai frumos:

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

Analizatorul rezultat are aceeași lungime, dar mai ușor de înțeles și utilizat. Am eliminat Epsilon , care este acum implicat de a începe cu o structură goală.

Nici măcar nu aveam nevoie de clasa ExprOpt aici. Am fi putut doar să punem case class Expr(num: Int, exprOpts: Seq[Int]) sau în format gramatical, NUM ('+' NUM)* . Deci de ce nu am făcut-o?

Luați în considerare că dacă am avea mai mulți operatori posibili, cum ar fi - sau * , atunci am avea o gramatică ca aceasta:

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

În acest caz, AST are nevoie de ExprOpt pentru a se adapta tipului de operator:

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

Rețineți că sintaxa [+-*] din gramatică înseamnă același lucru ca și în expresiile regulate: „unul dintre acele trei caractere”. Vom vedea asta în acțiune în curând.

Interpret Componenta 3: Scrierea unui interpret

Interpretul nostru va folosi lexerul și analizatorul nostru pentru a obține AST-ul expresiei noastre de intrare și apoi va evalua acel AST în orice mod dorim. În acest caz, avem de-a face cu numere și vrem să le evaluăm suma.

În implementarea exemplului nostru de interpret, vom folosi această gramatică simplă:

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

Și acest AST:

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

(Am abordat cum să implementăm un lexer și un parser pentru gramatici similare, dar orice cititor care se blochează poate citi implementările lexer și parser pentru această gramatică exactă în depozit.)

Acum vom vedea cum să scriem un interpret pentru gramatica de mai sus:

 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

Dacă am analizat intrarea noastră într-un AST fără a întâmpina o eroare, suntem siguri că vom avea întotdeauna cel puțin un NUM . Apoi luăm numerele opționale și le adăugăm la (sau le scădem din) rezultatul nostru.

Nota de la început despre asociativitatea din stânga a lui + este acum clară: Pornim de la numărul cel mai din stânga și adăugăm altele, de la stânga la dreapta. Acest lucru poate părea lipsit de importanță pentru adunare, dar luați în considerare scăderea: expresia 5 - 2 - 1 este evaluată ca (5 - 2) - 1 = 3 - 1 = 2 și nu ca 5 - (2 - 1) = 5 - 1 = 4 !

Dar dacă vrem să mergem dincolo de interpretarea operatorilor plus și minus, trebuie definită o altă regulă.

Precedenta

Știm cum să analizăm o expresie simplă precum 1 + 2 + 3 , dar când vine vorba de 2 + 3 * 4 + 5 , avem o mică problemă.

Majoritatea oamenilor sunt de acord cu convenția conform căreia înmulțirea are o prioritate mai mare decât adunarea. Dar analizatorul nu știe asta. Nu îl putem evalua doar ca ((2 + 3) * 4) + 5 . În schimb, vrem (2 + (3 * 4)) + 5 .

Aceasta înseamnă că trebuie să evaluăm mai întâi înmulțirea . Înmulțirea trebuie să fie mai departe de rădăcina AST pentru a forța să fie evaluată înainte de adăugare. Pentru aceasta, trebuie să introducem încă un strat de indirectă.

Remedierea unei gramatici naive de la început până la sfârșit

Aceasta este gramatica noastră originală, recursiva la stânga, care nu are reguli de precedență:

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

În primul rând, îi dăm reguli de prioritate și îi eliminăm ambiguitatea :

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

Apoi primește reguli non-recursive la stânga :

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

Rezultatul este un AST frumos expresiv:

 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)

Acest lucru ne lasă cu o implementare concisă a interpretului:

 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

Ca și înainte, ideile din lexerul și gramatica necesare au fost tratate mai devreme, dar cititorii le pot găsi în repo dacă este necesar.

Următorii pași în scrierea interpreților

Nu am acoperit acest lucru, dar gestionarea erorilor și raportarea sunt caracteristici esențiale ale oricărui analizator. În calitate de dezvoltatori, știm cât de frustrant poate fi atunci când un compilator produce erori confuze sau înșelătoare. Este o zonă care are multe probleme interesante de rezolvat, cum ar fi furnizarea de mesaje de eroare corecte și precise, nu descurajarea utilizatorului cu mai multe mesaje decât este necesar și recuperarea grațioasă din erori. Depinde de dezvoltatori care scriu un interpret sau un compilator pentru a se asigura că viitorii lor utilizatori au o experiență mai bună.

Parcurgând exemplele noștri de lexer, parseri și interpreți, am zgâriat doar suprafața teoriilor din spatele compilatorilor și interpreților, care acoperă subiecte precum:

• Domenii și tabele de simboluri
• Tipuri statice
• Optimizarea timpului de compilare
• Analizoare de programe statice și linters
• Formatarea codului și imprimarea destul de
• Limbi specifice domeniului

Pentru citiri suplimentare, recomand aceste resurse:

• Modele de implementare a limbajului de Terence Parr
• O carte online gratuită, Crafting Interpreters , de Bob Nystrom
• Introducere la gramatica și analizarea de Paul Klint
• Scrierea mesajelor de eroare bune ale compilatorului de Caleb Meredith
• Notele de la cursul de la Universitatea din Carolina de Est „Traducerea și compilarea programelor”