Como abordar a escrita de um intérprete do zero

Alguns dizem que “tudo se resume a uns e zeros” – mas será que realmente entendemos como nossos programas são traduzidos para esses bits?

Compiladores e interpretadores pegam uma string bruta representando um programa, analisam-na e dão sentido a ela. Embora os intérpretes sejam os mais simples dos dois, escrever até mesmo um intérprete muito simples (que só faz adição e multiplicação) será instrutivo. Vamos nos concentrar no que compiladores e interpretadores têm em comum: lexing e parsing da entrada.

Os prós e contras de escrever seu próprio intérprete

Os leitores podem se perguntar O que há de errado com um regex? As expressões regulares são poderosas, mas as gramáticas do código-fonte não são simples o suficiente para serem analisadas por elas. Nem são linguagens específicas de domínio (DSLs), e um cliente pode precisar de uma DSL personalizada para expressões de autorização, por exemplo. Mas mesmo sem aplicar essa habilidade diretamente, escrever um interpretador torna muito mais fácil apreciar o esforço por trás de muitas linguagens de programação, formatos de arquivo e DSLs.

Escrever analisadores corretamente à mão pode ser um desafio com todos os casos extremos envolvidos. É por isso que existem ferramentas populares, como o ANTLR, que podem gerar analisadores para muitas linguagens de programação populares. Também existem bibliotecas chamadas de combinadores de analisadores , que permitem que os desenvolvedores escrevam analisadores diretamente em suas linguagens de programação preferidas. Exemplos incluem FastParse para Scala e Parsec para Python.

Recomendamos que, em um contexto profissional, os leitores usem tais ferramentas e bibliotecas para evitar reinventar a roda. Ainda assim, entender os desafios e as possibilidades de escrever um interpretador do zero ajudará os desenvolvedores a aproveitar essas soluções de forma mais eficaz.

Visão geral dos componentes do intérprete

Um interpretador é um programa complexo, portanto, há vários estágios para ele:

1. Um lexer é a parte de um interpretador que transforma uma sequência de caracteres (texto simples) em uma sequência de tokens.
2. Um analisador , por sua vez, recebe uma sequência de tokens e produz uma árvore de sintaxe abstrata (AST) de uma linguagem. As regras pelas quais um analisador opera geralmente são especificadas por uma gramática formal.
3. Um interpretador é um programa que interpreta o AST da fonte de um programa em tempo real (sem compilá-lo primeiro).

Não construiremos um interpretador específico e integrado aqui. Em vez disso, exploraremos cada uma dessas partes e seus problemas comuns com exemplos separados. No final, o código do usuário ficará assim:

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

Seguindo os três estágios, esperamos que este código calcule um valor final e imprima o Result is: 19 . Este tutorial usa Scala porque é:

• Muito conciso, cabendo muito código em uma tela.
• Orientado à expressão, sem necessidade de variáveis ​​não inicializadas/nulas.
• Tipo seguro, com uma poderosa biblioteca de coleções, enumerações e classes de casos.

Especificamente, o código aqui é escrito em sintaxe de chaves opcionais Scala3 (uma sintaxe baseada em indentação semelhante a Python). Mas nenhuma das abordagens é específica de Scala , e Scala é semelhante a muitas outras linguagens: os leitores acharão simples converter essas amostras de código em outras linguagens. Exceto isso, os exemplos podem ser executados online usando Scastie.

Por fim, as seções Lexer, Parser e Interpreter têm diferentes gramáticas de exemplo . Como mostra o repositório GitHub correspondente, as dependências nos exemplos posteriores mudam um pouco para implementar essas gramáticas, mas os conceitos gerais permanecem os mesmos.

Componente do Interpretador 1: Escrevendo um Lexer

Digamos que queremos lex esta string: "123 + 45 true * false1" . Ele contém diferentes tipos de tokens:

• Literais inteiros
• A + operador
• Um * operador
• Um true literal
• Um identificador, false1

Os espaços em branco entre os tokens serão ignorados neste exemplo.

Nesse estágio, as expressões não precisam fazer sentido; o lexer simplesmente converte a string de entrada em uma lista de tokens. (O trabalho de “dar sentido aos tokens” é deixado para o analisador.)

Usaremos este código para representar um 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

Cada token tem um tipo, representação textual e posição na entrada original. A posição pode ajudar os usuários finais do lexer com a depuração.

O token EOF é um token especial que marca o fim da entrada. Não existe no texto fonte; nós o usamos apenas para simplificar o estágio do analisador.

Esta será a saída do nosso 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) )

Vamos examinar a implementação:

 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

Começamos com uma lista vazia de tokens, depois percorremos a string e adicionamos tokens à medida que surgem.

Usamos o caractere lookahead para decidir o tipo do próximo token . Observe que o caractere de antecipação nem sempre é o caractere mais à frente a ser examinado. Com base na antecipação, sabemos como é o token e usamos currentPos para verificar todos os caracteres esperados no token atual e, em seguida, adicionamos o token à lista:

Se o lookahead for um espaço em branco, nós o ignoramos. Os tokens de uma única letra são triviais; nós os adicionamos e incrementamos o índice. Para números inteiros, só precisamos cuidar do índice.

Agora chegamos a algo um pouco complicado: identificadores versus literais. A regra é que pegamos a correspondência mais longa possível e verificamos se é um literal; se não for, é um identificador.

Tome cuidado ao manipular operadores como < e <= . Lá você tem que olhar para frente mais um caractere e ver se é = antes de concluir que é um operador <= . Caso contrário, é apenas um < .

Com isso, nosso lexer produziu uma lista de tokens.

Componente 2 do intérprete: escrevendo um analisador

Temos que dar alguma estrutura aos nossos tokens - não podemos fazer muito com uma lista sozinha. Por exemplo, precisamos saber:

Quais expressões estão aninhadas? Quais operadores são aplicados em que ordem? Quais regras de escopo se aplicam, se houver?

Uma estrutura de árvore suporta aninhamento e ordenação. Mas primeiro, temos que definir algumas regras para construir árvores. Gostaríamos que nosso analisador não fosse ambíguo - sempre retornasse a mesma estrutura para uma determinada entrada.

Observe que o analisador a seguir não usa o exemplo anterior do lexer . Este é para adicionar números, então sua gramática tem apenas dois tokens, '+' e NUM :

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

Um equivalente, usando um caractere de barra vertical ( | ) como um símbolo “ou” como em expressões regulares, é:

 expr -> expr '+' expr | NUM

De qualquer forma, temos duas regras: uma que diz que podemos somar duas expr s e outra que diz que expr pode ser um token NUM , que aqui significará um inteiro não negativo.

As regras geralmente são especificadas com uma gramática formal . Uma gramática formal consiste em: As próprias regras, como mostrado acima Uma regra inicial (a primeira regra especificada, por convenção) Dois tipos de símbolos para definir as regras com: Terminais: as “letras” (e outros caracteres) da nossa linguagem— os símbolos irredutíveis que compõem os tokens Não-terminais: construções intermediárias usadas para análise sintática (ou seja, símbolos que podem ser substituídos)

Apenas um não-terminal pode estar no lado esquerdo de uma regra; o lado direito pode ter terminais e não terminais. No exemplo acima, os terminais são '+' e NUM , e o único não terminal é expr . Para um exemplo mais amplo, na linguagem Java, temos terminais como 'true' , '+' , Identifier e '[' , e não terminais como BlockStatements , ClassBody e MethodOrFieldDecl .

Há muitas maneiras de implementar esse analisador. Aqui, usaremos uma técnica de análise de “descida recursiva”. É o tipo mais comum porque é o mais simples de entender e implementar.

Um analisador descendente recursivo usa uma função para cada não terminal na gramática. Ele começa da regra inicial e desce daí (daí “descida”), descobrindo qual regra aplicar em cada função. A parte “recursiva” é vital porque podemos aninhar recursivamente não terminais! Regexes não podem fazer isso: eles não podem nem lidar com parênteses balanceados. Então, precisamos de uma ferramenta mais poderosa.

Um analisador para a primeira regra seria algo assim (código completo):

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

A função eat() verifica se o lookahead corresponde ao token esperado e então move o índice lookahead. Infelizmente, isso ainda não funcionará porque precisamos corrigir alguns problemas com nossa gramática.

Ambiguidade gramatical

A primeira questão é a ambiguidade de nossa gramática, que pode não ser aparente à primeira vista:

 expr -> expr '+' expr | NUM

Dada a entrada 1 + 2 + 3 , nosso analisador pode optar por calcular a expr esquerda ou a expr direita primeiro no AST resultante:

É por isso que precisamos introduzir alguma assimetria :

 expr -> expr '+' NUM | NUM

O conjunto de expressões que podemos representar com esta gramática não mudou desde sua primeira versão. Só agora é inequívoco : O analisador sempre vai para a esquerda. Exatamente o que precisávamos!

Isso torna nossa operação + left associative , mas isso ficará aparente quando chegarmos à seção Interpreter.

Regras recursivas à esquerda

Infelizmente, a correção acima não resolve nosso outro problema, recursão à esquerda:

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

Temos recursão infinita aqui. Se entrarmos nessa função, eventualmente receberemos um erro de estouro de pilha. Mas a teoria da análise pode ajudar!

Suponha que tenhamos uma gramática como esta, onde alpha pode ser qualquer sequência de terminais e não terminais:

 A -> A alpha | B

Podemos reescrever esta gramática como:

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

Lá, epsilon é uma string vazia – nada, nenhum token.

Vamos pegar a revisão atual da nossa gramática:

 expr -> expr '+' NUM | NUM

Seguindo o método de reescrever as regras de análise detalhadas acima, com alpha sendo nossos tokens '+' NUM , nossa gramática se torna:

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

Agora a gramática está OK, e podemos analisá-la com um analisador descendente recursivo. Vamos ver como esse analisador ficaria para esta última iteração de nossa gramática:

 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

Aqui usamos o token EOF para simplificar nosso analisador. Sempre temos certeza de que há pelo menos um token em nossa lista, portanto, não precisamos lidar com um caso especial de uma lista vazia.

Além disso, se mudarmos para um lexer de streaming, não teríamos uma lista na memória, mas um iterador, então precisamos de um marcador para saber quando chegamos ao final da entrada. Quando chegamos ao fim, o token EOF deve ser o último token restante.

Percorrendo o código, podemos ver que uma expressão pode ser apenas um número. Se não sobrar nada, o próximo token não seria um Plus , então pararíamos de analisar. O último token seria EOF e teríamos terminado.

Se a string de entrada tiver mais tokens, eles teriam que se parecer com + 123 . É aí que a recursão em exprOpt() entra em ação!

Gerando um AST

Agora que analisamos nossa expressão com sucesso, é difícil fazer qualquer coisa com ela como está. Poderíamos colocar alguns retornos de chamada em nosso analisador, mas isso seria muito complicado e ilegível. Em vez disso, retornaremos um AST, uma árvore representando a expressão de entrada:

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

Isso se assemelha às nossas regras, usando classes de dados simples.

Nosso analisador agora retorna uma estrutura de dados útil:

 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

Para eat() , error() e outros detalhes de implementação, consulte o repositório GitHub que o acompanha.

Simplificando Regras

Nosso não terminal ExprOpt ainda pode ser melhorado:

 '+' NUM exprOpt | epsilon

É difícil reconhecer o padrão que ele representa em nossa gramática apenas olhando para ele. Acontece que podemos substituir essa recursão por uma construção mais simples:

 ('+' NUM)*

Esta construção significa simplesmente '+' NUM ocorre zero ou mais vezes.

Agora nossa gramática completa se parece com isso:

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

E nosso AST fica mais bonito:

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

O analisador resultante tem o mesmo comprimento, mas é mais simples de entender e usar. Eliminamos Epsilon , que agora está implícito começando com uma estrutura vazia.

Nós nem precisamos da classe ExprOpt aqui. Poderíamos ter apenas colocado a case class Expr(num: Int, exprOpts: Seq[Int]) , ou no formato gramatical, NUM ('+' NUM)* . Então por que não fizemos?

Considere que, se tivéssemos vários operadores possíveis, como - ou * , teríamos uma gramática como esta:

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

Nesse caso, o AST precisa do ExprOpt para acomodar o tipo de operador:

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

Observe que a sintaxe [+-*] na gramática significa a mesma coisa que em expressões regulares: “um desses três caracteres”. Veremos isso em ação em breve.

Componente 3 do Intérprete: Escrevendo um Intérprete

Nosso interpretador fará uso de nosso lexer e analisador para obter o AST de nossa expressão de entrada e, em seguida, avaliar esse AST da maneira que quisermos. Nesse caso, estamos lidando com números e queremos avaliar sua soma.

Na implementação do nosso exemplo de intérprete, usaremos esta gramática simples:

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

E este AST:

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

(Cobrimos como implementar um lexer e um analisador para gramáticas semelhantes, mas qualquer leitor que ficar preso pode examinar as implementações de lexer e analisador para essa gramática exata no repositório.)

Agora veremos como escrever um interpretador para a gramática acima:

 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 analisarmos nossa entrada em um AST sem encontrar um erro, temos certeza de que sempre teremos pelo menos um NUM . Em seguida, pegamos os números opcionais e os adicionamos (ou subtraímos) ao nosso resultado.

A nota do início sobre a associatividade esquerda de + agora é clara: começamos do número mais à esquerda e adicionamos outros, da esquerda para a direita. Isso pode parecer sem importância para a adição, mas considere a subtração: A expressão 5 - 2 - 1 é avaliada como (5 - 2) - 1 = 3 - 1 = 2 e não como 5 - (2 - 1) = 5 - 1 = 4 !

Mas se quisermos ir além da interpretação de operadores de mais e menos, há outra regra a definir.

Precedência

Sabemos como analisar uma expressão simples como 1 + 2 + 3 , mas quando se trata de 2 + 3 * 4 + 5 , temos um pequeno problema.

A maioria das pessoas concorda com a convenção de que a multiplicação tem maior precedência do que a adição. Mas o analisador não sabe disso. Não podemos apenas avaliá-lo como ((2 + 3) * 4) + 5 . Em vez disso, queremos (2 + (3 * 4)) + 5 .

Isso significa que precisamos avaliar a multiplicação primeiro . A multiplicação precisa estar mais longe da raiz do AST para forçá-lo a ser avaliado antes da adição. Para isso, precisamos introduzir mais uma camada de indireção.

Corrigindo uma gramática ingênua do início ao fim

Esta é a nossa gramática original recursiva à esquerda, que não tem regras de precedência:

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

Primeiro, damos regras de precedência e removemos sua ambiguidade :

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

Em seguida, obtém regras não recursivas à esquerda :

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

O resultado é um AST lindamente expressivo:

 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)

Isso nos deixa com uma implementação concisa do interpretador:

 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

Como antes, as ideias no lexer e na gramática necessários foram abordadas anteriormente, mas os leitores podem encontrá-las no repositório, se necessário.

Próximos passos na escrita de intérpretes

Não abordamos isso, mas o tratamento de erros e a geração de relatórios são recursos cruciais de qualquer analisador. Como desenvolvedores, sabemos como pode ser frustrante quando um compilador produz erros confusos ou enganosos. É uma área que tem muitos problemas interessantes para resolver, como fornecer mensagens de erro corretas e precisas, não desencorajar o usuário com mais mensagens do que o necessário e recuperar-se de erros com facilidade. Cabe aos desenvolvedores escrever um interpretador ou compilador para garantir que seus futuros usuários tenham uma experiência melhor.

Ao percorrer nossos lexers, analisadores e intérpretes de exemplo, apenas arranhamos a superfície das teorias por trás dos compiladores e interpretadores, que cobrem tópicos como:

• Escopos e tabelas de símbolos
• Tipos estáticos
• Otimização em tempo de compilação
• Analisadores e linters de programas estáticos
• Formatação de código e impressão bonita
• Idiomas específicos do domínio

Para leitura adicional, recomendo estes recursos:

• Padrões de Implementação de Linguagem por Terence Parr
• Um livro online gratuito, Crafting Interpreters , de Bob Nystrom
• Introdução à gramática e análise por Paul Klint
• Escrevendo boas mensagens de erro do compilador por Caleb Meredith
• As notas do curso da East Carolina University “Program Translation and Compiling”