Novas linguagens de programação são criadas o tempo todo para resolver problemas específicos ou apenas por diversão, compreender como as linguagens são pensadas e estruturadas pode nos ajudar a aprofundar mais em nossa carreira de programação.
Assim como a gramática da linguagem humana (Português, Inglês, etc), a sintaxe especifica a forma correta de organizar e estrutrar as instruções para que o computador possa entender e executar nosso código de forma desejavel. Além da sintaxe, temos a semântica que determina o comportamento da linguagem. Ela define o significado de uma instrução, como funciona e se um determinado conjunto de caracteres ‘faz sentido’. Essas duas definições são essenciais em qualquer linguagem.
Exemplo de gramática para o Português
Vamos começar vendo a gramática da língua portuguesa, nossa gramática terá artigos definidos, substantivos e verbos.
Um artigo definido pode ser: o, a, os, as.
Vamos definir nossos artigos usando o símbolo <A>. Portanto, sempre que nos referirmos a um artigo, usaremos seu símbolo <A>.
<A> ::= o | a | os | as
Para substantivos usaremos apenas três opções: cão, gato ou rato.
<S> ::= cão | gato | rato
Os verbos que usaremos são: ama, odeia e come.
<V> ::= ama | odeia | come
Seguindo o português, todo substantivo é precedido de um artigo. Vamos chamar a junção do artigo com o substantivo de <AS>.
<AS> ::= <A> <S>
Uma frase precisa ser composta por um artigo, seguido de um substantivo, depois um verbo, e novamente seguido de outro artigo e substantivo. Sendo <S> nossa sentença, podemos descrever isso da seguinte forma:
<S> ::= <AS> <V> <AS>
Ao reunir todas as definições, obtemos um pequeno subconjunto da língua portuguesa.
<A> ::= o | a | os | as<S> ::= cão | gato | rato<V> ::= ama | odeia | come<AS> ::= <A> <S><S> ::= <AS> <V> <AS>Bom, a partir de todas essas definições, podemos estruturá-las em forma de árvore. Como a sentença (<S>) é a definição que agrupa todas as demais, colocaremos ela como a raiz da árvore, e as chamadas de gramáticas serão seus nós filhos, e assim sucessivamente. Essa árvore será chamada de ‘Arvore de Sintaxe’ ou ‘Syntax Tree’ em inglês.
Com este conjunto, podemos montar uma árvore da seguinte maneira:
---
config:
theme: dark
---
graph TD;
S[< S >] --> AS[< AS >];
S --> V[< V >];
S --> AS2[< AS >];
AS --> A[< A >];
AS --> N[< N >];
AS2 --> A2[< A >];
AS2 --> N2[< N >];
Inclusive, podemos substituir e definir os valores de seus nós folhas para criarmos uma sentença, por exemplo:
---
config:
theme: dark
---
graph TD;
S[< S >] --> AS[< AS >];
AS --> A[< A >];
AS --> N[< N >];
A --> A3["O"];
N --> N3["Cão"];
S --> V[< V >];
V --> V2["Ama"];
S --> AS2[< AS >];
AS2 --> A2[< A >];
AS2 --> N2[< N >];
A2 --> A4["O"];
N2 --> N4["Gato"];
É sempre possível manipular seus valores, verbos, substantivos e artigos. No entanto, se você seguir a definição feita e a estrutura da árvore, sempre teremos uma gramática correta.
Agora, retornando um pouco às linguagens de programação, aqui está um exemplo de gramática para uma linguagem bastante simples:
<exp> ::= <exp> + <exp> | <exp> * <exp> | ( <exp> ) | a | b | cEsta gramática nos informa que uma expressão (<exp>) pode ser:
- A soma de duas expressões
- O produto de duas expressões
- Uma expressão envolvida por parênteses
- Uma das variáveis a, b ou c.
Entao nossa gramatica inclui expressões parecidas com:
aa+ba+b*c((a+b)*c)
Em forma de arvore, podemos representar da seguinte forma:
---
config:
theme: dark
---
graph TD;
EXP[< exp >] --> LB["("];
EXP --> EXP2[< exp >];
EXP2 --> EXP3[< exp >];
EXP3 --> LB2["("];
EXP3 --> EXP5[< exp >];
EXP3 --> RB2[")"];
EXP5 --> EXP6[< exp >];
EXP6 --> A["A"];
EXP5 --> PLUS["+"];
EXP5 --> EXP7[< exp >];
EXP7 --> B["B"];
EXP2 --> MUL["*"];
EXP2 --> EXP4[< exp >];
EXP4 --> C["C"];
EXP --> RB[")"];
BNF - Backus-Naur Form
A forma BNF (Backus-Naur Form) é uma maneira eficaz de descrever o conjunto de sequências válidas em uma linguagem particular. Ela permite a definição de uma linguagem de programação de forma concisa e precisa. A forma BNF é usada na descrição da sintaxe de muitas linguagens de programação, como Java, C++ e Python.
Em BNF, uma gramática consiste em uma série de regras de produção. Cada regra de produção tem um símbolo à esquerda do símbolo ”::=”, que é o nome do símbolo não terminal, e à direita, tem uma sequência de símbolos terminais e não terminais. Essa sequência indica uma forma válida que o símbolo à esquerda pode assumir.
Os tokens são a menor unidade de uma sintaxe. Eles são strings e símbolos que escolhemos para ser a base da nossa linguagem. No nosso exemplo, a palavra ‘cat’ é um token. Em linguagens de programação, podemos escolher palavras-chave para isso, como ‘for’.
Os símbolos não terminais são strings envolvidas por <>, como <NP>.
A linguagem escolhe um símbolo não terminal para ser o ponto de partida, a que chamaremos de símbolo inicial <S>.
Definindo nossa gramática
Antes de começarmos a programar de fato, precisamos definir bem a gramática da nossa linguagem, neste caso, iremos fazer uma gramática bem simples para interpretar algumas expressões matemáticas.
<S> ::= <exp><exp> ::= <term> | <exp> "+" <term> | <exp> "-" <term><term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor><factor> ::= <number> | "(" <exp> ")"<number> ::= <digit> | <digit> <number><digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"De forma resumida,
<exp>representa uma expressão completa. Pode ser apenas um termo, ou um termo seguido de um operador (+ ou -) e outro termo.<term>representa um termo dentro de uma expressão. Pode ser apenas um fator, ou um termo seguido de um operador (* ou /) e outro fator.<factor>é um elemento básico da expressão. Pode ser um número ou uma expressão entre parênteses.<number>é um número inteiro. Pode ser um único dígito ou vários dígitos em sequência.<digit>é um dígito de 0 a 9.
Mãos ao código
Em nossos exemplos usaremos TypeSscript, nada de especial, mas uma linguagem fácil de compreender e com uma tipagem mais forte. Bom, iniciaremos o projeto com o Bun.
Vamos começar definindo os tipos de tokens que nossa linguagem aceita, e a estrutura de um token.
Seguindo nossa gramática, aceitaremos os tokens +, -, *, /, (, ) e Número. Adicionaremos mais dois aqui para facilitar nossa vida, o fim de arquivo (EndOfFile) e o erro (Error) que nos ajudará nos testes.
export enum TokenType { Plus, Minus, Multiply, Divide, LeftParenthesis, RightParenthesis, Number, EndOfFile, Error,}Usando o bom e velho POO, definimos nossa estrutura de um token tendo duas propriedades: kind (armazena o tipo do token) e o value (usaremos para quando o token for um número).
export class Token { readonly kind: TokenType; readonly value: number | null;
constructor(kind: TokenType, value: number | null = null) { this.kind = kind; this.value = value; }}Lexer
O primeiro passo após definir a gramática, é criar um lexer, que vai ser responsável por receber uma entrada em forma de texto e converte-la para uma lista de tokens significativos para que o interpretador consiga de fato interpretá-los.
Bom, o lexer é bem simples, vamos montar um passo a passo do que deve ser realizado:
- Receber um texto de entrada, nosso “source”.
- Dividir em pedaçoes menores que fazem sentido individualmente, pedaços esses que chamaremos de token (que inclusive já definimos).
- Identificar cada pedaço, basicamente dar sentido ao token, o que ele significa.
- Ignorar o que não faz sentido e não tem importância, como por exemplo, no nosso caso, as quebras de linhas e espaços (em python, as quebras de linha, tabs e espaços importam).
- Criar uma lista ordenada de tokens.
- Reportar erros, caso encontrarmos algum elemento fora da grámatica, devemos gerar um erro, para que ele não passe para as próximas etapas (erro léxico).
Vamos criar uma classe responsável pelo lexing.
1export default class Lexer {2 tokens: Token[] = []; // Armazenar a lista de tokens gerados3 source: string; // Texto de entrada4
5 constructor(source: string) {6 this.source = source;7 }8
9 lex(): Token[] {10 return this.tokens;11 }12}O método lex será responsável por transformar a entrada em uma lista de tokens, para começar é preciso percorrer todos os caracteres do texto de entrada.
1export default class Lexer {2 current: number = 0;3 tokens: Token[] = [];4 source: string;5
6 constructor(source: string) {7 this.source = source;8 }9
10 private getCurrentChar(): string {11 return this.source[this.current];12 }13
14 private isAtEnd(): boolean {15 return this.current >= this.source.length;16 }17
18 lex(): Token[] {19 while (!this.isAtEnd()) {20 const currentChar = this.getCurrentChar();21 console.log(currentChar);22 this.current++;23 }24
25 return this.tokens;26 }27}Agora temos um método que percorre todos os caracteres e imprime-os. Bom, ainda falta verificar o significado de cada caractere e convertê-lo à um token. Vamos começar pelos token Number:
1export default class Lexer {2 current: number = 0;3 tokens: Token[] = [];4 source: string;5
6 constructor(source: string) {7 this.source = source;8 }9
10 private addToken(kind: TokenType, value: number | null = null): void {11 this.tokens.push(new Token(kind, value));12 }13
14 private getCurrentChar(): string {15 return this.source[this.current];16 }17
18 private isAtEnd(): boolean {19 return this.current >= this.source.length;20 }21
22 private number(): number {23 let number = this.getCurrentChar();24 this.current++;25
26 while (!this.isAtEnd() && /^[0-9]*$/.test(this.getCurrentChar())) {27 number += this.getCurrentChar();28 this.current++;29 }30
31 return parseInt(number);32 }33
34 lex(): Token[] {35 while (!this.isAtEnd()) {36 const currentChar = this.getCurrentChar();37
38 if (/^[0-9]*$/.test(currentChar)) {39 this.addToken(TokenType.Number, this.number());40 continue;41 }42
43 this.current++;44 }45
46 return this.tokens;47 }48}O que o lexer está fazendo é bem simples, ao percorrer os caracteres, caso encontre um dígito (0, 1, 2, …, 9), chama o método number, que por sua vez, continua percorrendo o texto até que encontra um novo caractere que não seja um dígito.
---
config:
theme: dark
---
flowchart TD
A((Início)) --> |Recebe texto de entrada| B(Seleciona o primeiro caractere)
B --> C{O caractere é um dígito?}
C -->|Não| D(Converta a string de dígitos concatenada para número)
C -->|Sim| E(Concatene com os outros dígitos)
E --> F(Vá para o próximo caractere)
F --> C
D --> G((Fim))
Por exemplo, vamos usar o texto de entrada '123'.
'1'é um dígito? sim, então armazene e vá para o próximo.'2'é um dígito? sim, concatene com o'1'e vá para o próximo.'3'é um dígito? sim, concatene com o'12'e vá para o próximo.- Não há mais caracteres, encerra o loop e converte a string
'123'para número. - Cria um objeto de Token passando o
TokenType::Numbercom o valor123. - Adicione o token ao fim da lista de tokens.
O lexer já é capaz de identificar e converter números. Agora é necessário converter os outros tipos de token, que são bem mais simples.
1export default class Lexer {2 // ...3
4 lex(): Token[] {5 while (!this.isAtEnd()) {6 const currentChar = this.getCurrentChar();7
8 if (/^[0-9]*$/.test(currentChar)) {9 this.addToken(TokenType.Number, this.number());10 continue;11 }12
13 switch (currentChar) {14 case '+':15 this.addToken(TokenType.Plus);16 break;17 case '-':18 this.addToken(TokenType.Minus);19 break;20 case '*':21 this.addToken(TokenType.Multiply);22 break;23 case '/':24 this.addToken(TokenType.Divide);25 break;26 case '(':27 this.addToken(TokenType.LeftParenthesis);28 break;29 case ')':30 this.addToken(TokenType.RightParenthesis);31 break;32 default:33 if (!/\s/.test(currentChar)) {34 this.addToken(TokenType.Error);35 }36 }37
38 this.current++;39 }40
41 return this.tokens;42 }43}Para os demais tokens não tem segredo, eles são caracteres únicos como ’+’ e ’-’, então ao encontrá-los, crie um objeto com seu respectivo tipo e adicione-o ao fim da lista de tokens. Caso o caractere passe por todos os tipos de verificação e o mesmo não seja um espaço em branco, um token do tipo erro é adicionado à lista, neste caso pode-se lançar uma exceção para interromper a execução do programa antes de seguir para as próximas etapas, mas não será implementado aqui.
Ficou faltando um token a ser analisado, o EndOfFile, só adicioná-lo ao fim do loop.
1export default class Lexer {2 // ...3
4 lex(): Token[] {5 while (!this.isAtEnd()) {6 const currentChar = this.getCurrentChar();7 // ...8 this.current++;9 }10
11 this.addToken(TokenType.EndOfFile);12
13 return this.tokens;14 }15}Pronto, agora para testá-lo, vamos instanciar o lexer e passar um valor de entrada a ele.
1import Lexer from "@/lexer/lexer";2
3const lexer = new Lexer("11 + 12");4const tokens = lexer.lex();5
6console.log(tokens);7/* [8 Token { kind: 6, value: 11 },9 Token { kind: 0, value: null },10 Token { kind: 6, value: 12 },11 Token { kind: 7, value: null }12] */Parser
O parser é a etapa seguinte no processo de entender uma linguagem, logo após o lexer. Se o lexer é o amigo que separa as palavras e símbolos, o parser é aquele que pega essas palavras e começa a entender o que elas significam juntas, em frases e sentenças.
O parser recebe uma lista de tokens, gerada pelo lexer, e começa a organizá-los de acordo com as regras gramaticais definidas.
É como pegar as palavras e montar sentenças que façam sentido. Por exemplo, let x = 42; é uma instrução válida em Javascript.
O parser verifica se os tokens seguem essa estrutura.
Enquanto analisa os tokens, o parser vai gerando uma Syntax tree. Por exemplo com a expressão 2 * (2 + 1):
---
config:
theme: dark
---
graph TD;
EXP["*"] --> LB["2"];
EXP --> EXP2["+"];
EXP2 --> EXP3["2"];
EXP2 --> EXP4["1"];
No final do processo, o parser gera uma representação do código que pode ser usada por outras etapas do interpretador. Essa representação é baseada na syntax Tree, que é uma forma estruturada e organizada de entender o que o código faz.
Antes de constuirmos o parser, precisamos montar uma estrutura para a syntax tree.
1export class Node {2 kind: TokenType;3 value: any;4 children: Node[];5
6 constructor(kind: TokenType, value: number|null = null, children: Node[] = []) {7 this.kind = kind;8 this.value = value;9 this.children = children;10 }11}Esta é a estrutura de um nó da nossa árvore, que armazena um token e possui filhos.
Já com o nó definido, vamos definir o Parser:
1export default class Parser {2 current: number = 0;3 tokens: Token[] = [];4
5 constructor(tokens: Token[]) {6 this.tokens = tokens;7 }8
9 private nextToken(): Token {10 return this.tokens[this.current++];11 }12
13 private isAtEnd(): boolean {14 return this.current >= this.tokens.length;15 }16
17 private match(kind: TokenType): boolean {18 if (this.isAtEnd()) {19 return false;20 }21
22 return this.tokens[this.current].kind === kind23 }24
25 parse(): Node {26 // TODO: implementar27 }28}Adicionei inicialmente as métodos auxiliares:
nextToken: retorna o próximo token da lista, incrementando o indice atual.isAtEnd: verifica se os tokens acabaram.match: verifica se o token atual é de um tipo específico, especificado pelo parâmetro.
O método parse é o que iremos chamar para realizar o parse dos tokens.
Primeiro, precisamos relembrar a gramática da nossa ‘linguagem’:
<S> ::= <exp><exp> ::= <term> | <exp> "+" <term> | <exp> "-" <term><term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor><factor> ::= <number> | "(" <exp> ")"<number> ::= <digit> | <digit> <number><digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"Como podemos ver, a gramática começa sempre uma expressão, vamos escrever isso:
1export default class Parser {2 // ...3
4 private expression(): Node {5 //6 }7
8 parse(): Node {9 return this.expression();10 }11}Expressão
Vamos analisar a gramática da expressão.
<exp> ::= <term> | <exp> "+" <term> | <exp> "-" <term>Ela pode ser um termo ou uma soma/subtração de uma expressão com um termo. Ou seja, uma expressão sempre vai ter um termo, caso não tenha nenhuma operação, podemos simplesmente retornar o termo, ele será nosso elemento mais à esquerda.
1export default class Parser {2 // ...3
4 private expression(): Node {5 let left = this.term();6 return left;7 }8
9 // ...10}Após obter o termo mais à esquerda, falatm mais duas partes: obter o operador e a expressão à direita. Para isso, basta continuar percorrendo a lista e verificar se o próximo token é uma soma ou subtração, caso seja, consuma o operador e o termo seguinte.
1export default class Parser {2 // ...3
4 private expression(): Node {5 let left = this.term();6
7 while (!this.isAtEnd() && (this.match(TokenType.Plus) || this.match(TokenType.Minus))) {8 let operator = this.nextToken();9 let right = this.term();10 }11
12 return left;13 }14
15 // ...16}Com o os dois termos e o operador em mãos, é necessário gerar um novo nó da arvore, de forma que os dois termos sejam nós folhas e então retornar o nó ao invés do termo.
1export default class Parser {2 // ...3
4 private expression(): Node {5 let left = this.term();6
7 while (!this.isAtEnd() && (this.match(TokenType.Plus) || this.match(TokenType.Minus))) {8 let operator = this.nextToken();9 let right = this.term();10 let newNode = new Node(operator.kind, null);11 newNode.children.push(left);12 newNode.children.push(right);13 left = newNode;14 }15
16 return left;17 }18
19 // ...20}Termo
A próxima etapa é o termo, vamos analisá-lo:
<term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor>Um termo pode ser um fator ou uma multiplicação/divisão de termo com fator. Muito parecido com a expressão, vamos implementá-la de forma semelhante:
1export default class Parser {2 // ...3
4 private term(): Node {5 let left = this.factor()6
7 while (!this.isAtEnd() && (this.match(TokenType.Multiply) || this.match(TokenType.Divide))) {8 let operator = this.nextToken();9 let right = this.factor();10 let newNode = new Node(operator.kind, null);11 newNode.children.push(left);12 newNode.children.push(right);13 left = newNode;14 }15
16 return left;17 }18
19 // ...20}Fator
Agora o fator, que tem a seguinte gramática:
<factor> ::= <number> | "(" <exp> ")"Ele pode ser um número, ou simplesmente uma expressão dentro de parênteses.
Sua implementação é ainda mais simples, basta pegar o próximo token e verificar se é uma abertura de parêntese ’(’, caso seja, consuma a expressão e procure pelo fechamento do parêntese ’)’, caso não encontrado podemos lançar um erro, na nossa gramática não pode haver parênteses sem fechamento. Caso o token consumido não seja uma abertura de parênteses, podemos simplesmente retorná-lo e seguir a vida.
1export default class Parser {2 // ...3
4 private factor(): Node {5 let currentToken = this.nextToken();6
7 if (currentToken.kind === TokenType.LeftParenthesis) {8 let left = this.expression();9 // Verifica se o próximo token é um ')' e consome-o10 if (this.nextToken().kind !== TokenType.RightParenthesis) {11 throw new Error("Expressão mal formada: parêntese de fechamento ausente.");12 }13
14 return left;15 }16
17 return new Node(currentToken.kind, currentToken.value);18 }19
20 // ...21}O fator tem uma importância extrema, ele gera e precedência no nosso interpretador, sempre que houver parênteses, a expressão é jogada para um nó abaixo. Futuramente veremos que o nosso interpretador sempre interpretará os nós debaixo para cima, por isso que devemos ter este cuidado com a posição dos nós na syntax tree.
Vamos testar:
1import Lexer from "@/lexer/lexer";2import Parser from "@/parser/parser";3
4const parser = new Parser((new Lexer("11 + 12")).lex());5
6console.log(parser.parse());7/*8 Node {9 kind: 0,10 value: null,11 children: [12 Node {13 kind: 6,14 value: 11,15 children: [],16 },17 Node {18 kind: 6,19 value: 12,20 children: [],21 }22 ],23 }24*/A impressão do console.log está de uma forma bem feia, vamos implementar nossa impressora:
1export function printAST(node: Node, depth: number = 0) {2 const indent = '-'.repeat(depth);3 let output = indent + tokenTypeName(node.kind);4
5 if (node.value !== null) {6 output += ': ' + node.value;7 }8
9 console.log(output);10
11 for (const child of node.children) {12 printAST(child, depth + 1);13 }14}1import Lexer from "@/lexer/lexer";2import Parser from "@/parser/parser";3
4const parser = new Parser((new Lexer("11 + 12")).lex());5const ast = parser.parse();6
7printAST(ast);8/*9 Plus10 -Number: 1111 -Number: 1212*/Vamos testar algo mais complexo:
1import Lexer from "@/lexer/lexer";2import Parser from "@/parser/parser";3
4const parser = new Parser((new Lexer("2 * (2 + 1)")).lex());5const ast = parser.parse();6
7printAST(ast);8/*9 Multiply10 -Number: 211 -Plus12 --Number: 213 --Number: 114*/A impressora implementada é bem básica, existe formas melhores de implementá-la. Por enquanto estou satisfeito com ela.
Runtime
O runtime é a etapa de execução do código, não tem segredo, ele recebe syntax tree e simplesmente interpreta, executando as operações que a ‘linguagem’ foi projetada para fazer e também lidando com tratamento de erros. Numa linguagem como JS, o runtime faz uma infinidade a mais de passos, como a interação com o sistema operacional e o gerenciamento de memória. No nosso caso não há nada disso, é um tópico para outra hora.
Como de costume, iniciamos definindo a classe de Runtime, que armazenará a syntax tree (ast) e um método de execução (execute):
1export default class Runtime {2 ast: Node;3
4 constructor(ast: Node) {5 this.ast = ast;6 }7
8 private interpret(node: Node): number {9 //10 }11
12 execute(): number {13 return this.interpret(this.ast);14 }15}Vamos implementar o método ìnterpret, mas primeiro tentaremos entender o que ele precisa fazer.
Nossa ‘linguagem’ é uma expressão matemática, correto? Logicamente, com o gramática que definimos, nosso interpretador só pode nos retornar um número nom fim das contas. Logo, se temos um nó do tipo ‘Number’, não há o que interpretar, apenas retorná-lo.
1export default class Runtime {2 // ...3
4 private interpret(node: Node): number {5 if (node.kind === TokenType.Number) {6 return node.value;7 }8 }9
10 // ...11}No caso em que tenha um nó com filhos, como este exemplo:
---
config:
theme: dark
---
graph TD;
EXP["+"] --> LB["2"];
EXP --> EXP2["2"];
Neste caso, precisamos interpretar toda a subárvore à esquerda, depois a subárvore à direita para obtermos números, que é o objetivo final.
No exemplo acima, ambos as subárvores são números literais, logo o método interpret retornará estes números e então poderemos realizar a operação entre eles.
Mas há casos como este:
---
config:
theme: dark
---
graph TD;
EXP["*"] --> LB["2"];
EXP --> EXP2["+"];
EXP2 --> EXP3["2"];
EXP2 --> EXP4["1"];
Para isso, precisamos interpretar a árvore de forma recursiva, chamando a própria função para cada subárvore.
1export default class Runtime {2 // ...3
4 private interpret(node: Node): number {5 if (node.kind === TokenType.Number) {6 return node.value;7 }8
9 const left = this.interpret(node.children[0]);10 const right = this.interpret(node.children[1]);11 }12
13 // ...14}Com as subárvores interpretadas é só realizar a operação entre elas:
1export default class Runtime {2 // ...3
4 private interpret(node: Node): number {5 if (node.kind === TokenType.Number) {6 return node.value;7 }8
9 const left = this.interpret(node.children[0]);10 const right = this.interpret(node.children[1]);11
12 switch (node.kind) {13 case TokenType.Plus:14 return this.sum(left, right);15 case TokenType.Minus:16 return this.subtract(left, right);17 case TokenType.Multiply:18 return this.multiply(left, right);19 case TokenType.Divide:20 return this.divide(left, right);21 default:22 throw new Error('Operador inválido: ' + node.kind);23 }24 }25
26 // ...27}Os métodos sum, subtract, multiply e divide ainda não existem, vamos criá-los:
1export default class Runtime {2 // ...3
4 private sum(left: number, right: number): number {5 return left + right;6 }7
8 private subtract(left: number, right: number): number {9 return left - right;10 }11
12 private multiply(left: number, right: number): number {13 return left * right;14 }15
16 private divide(left: number, right: number): number {17 return left / right;18 }19
20 // ...21}Nada de especial por aqui, cada método recebe dois números e realizam a operação esperada. A divisão, como sabemos, o dividor não pode ser zero, nenhum número pode ser dividido por zero. Bom, o typescript interromperia a execução desse tipo de divisão, mas vamos implementar a nossa própria exceção:
1export default class Runtime {2 // ...3
4 private divide(left: number, right: number): number {5 return left / right;6
7 if (right === 0) {8 throw new Error('Erro de divisão por zero');9 }10
11 return left / right;12 }13
14 // ...15}Agora só testar 😁😁
1import Lexer from "@/lexer/lexer";2import Parser from "@/parser/parser";3import Runtime from "@/parser/runtime";4
5const runtime = new Runtime((new Parser((new Lexer("2 * (2 + 1)")).lex())).parse())6
7console.log(runtime.execute()); // 6Conclusão
Esse projeto foi somente uma brincadeira para estudar e praticar um pouco de interpretadores, usei o livro ‘Modern Programming Languages: A Practical Introduction’ como base para algumas explicações, uma linguagem de programação completa é muita mais complexa e levaria muito tempo até ter uma gramática descente, se quiser estudar um pouco mais sobre, recomendo o livro ‘Crafting Interpreters’.
O código final eu realizei alguns ajustes e testes para ficar mais legível, deixei o repositório público e pode ser acessado aqui.