Monkey é uma linguagem de programação feita para aprender a criar linguagens de programação.
let add = fn(x, y) {
x + y;
};
let result = add(1, 2); .="=.
_/.-.-.\_ _
( ( o o ) ) ))
|/ " \| //
.-------. \'---'/ //
_|~~ ~~ |_ /`"""`\\ ((
=(_|_______|_)= / /_,_\ \\ \\
|:::::::::| \_\\_'__/ \ ))
|:::::::[]| /` /`~\ |//
|o=======.| / / \ /
jgs `"""""""""` ,--`,--'\/\ /
'-- "--' '--'
ASCII arts by ASCII Art Archive
Para podermos trabalhar com o código fonte precisamos antes transformar texto em algo que possamos trabalhar, e é isso que a analise léxica faz, ela transforma o código fonte em tokens.
Código fonte --[Analise Léxica]-> Tokens --[Analise Sintática]-> AST --[Avaliação]-> Resultado
Tokens são peganas estruturas de dados que carregam informações sobre o código fonte, como o tipo do token, o valor do token e a linha e coluna que o token se encontra.
Nessa primeira versão não vamos nos preocupar com a linha e coluna do token, mas vamos nos preocupar com o tipo e o valor do token. Contudo a informação da linha e da coluna é importante para gerar mensagens de erro mais precisas.
Alguns tokens tem significado especial para a gente, como as palavras chaves e os operadores, mas outros tokens não tem significado especial, como os identificadores e os números.
Veja o exemplo abaixo:
let i = 42;Ao processar esse input, vamos gerar os seguintes tokens:
| Tipo | Valor |
|---|---|
| LET | let |
| IDENT | i |
| = | = |
| INT | 42 |
| ; | ; |
Os tipos podem variar de acordo com a sua implementação, mas o conceito é o mesmo.
Palavras chaves são palavras que tem significado especial para a linguagem, como let, fn, true, false, if, else, return, etc.
Identificadores são nomes que damos para variáveis, funções, etc. No estágio atual somente identificadores declarados com caracteres de a a z e _ são suportados.
Números são números, como 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. No momento só suportamos inteiros.
Espaços em branco são espaços, tabulações e quebras de linha. Eles são usados para separar tokens, mas não tem significado especial então a gente só DEVORA eles e segue em frente.
================================================.
.-. .-. .--. |
| OO| | OO| / _.-' .-. .-. .-. .''. |
| | | | \ '-. '-' '-' '-' '..' |
'^^^' '^^^' '--' |
===============. .-. .================. .-. |
| | | | | '-' |
| | | | | |
| ':-:' | | .-. |
l42 | '-' | | '-' |
===============' '================' |
O lexer é a ferramenta que nos permite transformar o código fonte em tokens, ele lê o código fonte e gera os tokens. Nós pegamos a string de entrada e transformamos em uma lista de tokens.
Fazemos isso percorrendo a string de entrada e consumindo os caracteres um a um. Por isso comentei que o lexer devora os espaços em branco, ele consome os caracteres que não tem significado especial e gera os tokens que tem significado especial. Fazemos isso até encontrar um carácter que não sabemos o que fazer, nesse caso geramos um erro, ou até o fim da string.
ReadEvaluatePrintLoop
O REPL é uma ferramenta que nos permite executar código fonte de forma interativa, ele lê o código fonte, avalia o código fonte, imprime o resultado e repete tudo de novo.
REPLs são muito úteis para testar código e para aprender uma linguagem de programação.
Eles foram popularizados pelo Lisp e hoje em dia são muito comuns em diversas linguagens de programação.
go run main.goUm parser transform um determinado input em uma estrutura de dados hierárquica, no nosso caso o parser transforma os tokens em uma árvore sintática abstrata (AST).
Uma AST é uma estrutura de dados que representa o código fonte de forma hierárquica, ela é muito útil para avaliar o código fonte.
Existem ferramentas capazes de gerar parsers a partir de uma gramática, mas nesse projeto o parser é feito manualmente.
Essa "gramática" citadada acima costuma ser uma Context Free Grammar (Gramática livre de contexto) (CFG), que é uma forma de descrever uma linguagem.
Uma gramática é uma forma de descrever uma linguagem, ela é composta por regras que descrevem como a linguagem funciona e como você pode construir sentenças válidas.
Existem diversas formas de escrever uma gramática, mas a mais comum é a Backus-Naur Form (BNF) e a Extended Backus-Naur Form (EBNF).
<regra> ::= <expressão>
Exemplo simples:
<operador> ::= +|-|/|*
A regra acima descreve um operador, que pode ser +, -, / ou *.
Exemplo mais complexo:
chunk ::= block
block ::= {stat} [retstat]
stat ::= ‘;’ |
varlist ‘=’ explist |
functioncall |
label |
break |
goto Name |
do block end |
while exp do block end |
repeat block until exp |
if exp then block {elseif exp then block} [else block] end |
for Name ‘=’ exp ‘,’ exp [‘,’ exp] do block end |
for namelist in explist do block end |
function funcname funcbody |
local function Name funcbody |
local attnamelist [‘=’ explist]
attnamelist ::= Name attrib {‘,’ Name attrib}
attrib ::= [‘<’ Name ‘>’]
retstat ::= return [explist] [‘;’]
label ::= ‘::’ Name ‘::’
funcname ::= Name {‘.’ Name} [‘:’ Name]
varlist ::= var {‘,’ var}
var ::= Name | prefixexp ‘[’ exp ‘]’ | prefixexp ‘.’ Name
namelist ::= Name {‘,’ Name}
explist ::= exp {‘,’ exp}
exp ::= nil | false | true | Numeral | LiteralString | ‘...’ | functiondef |
prefixexp | tableconstructor | exp binop exp | unop exp
prefixexp ::= var | functioncall | ‘(’ exp ‘)’
functioncall ::= prefixexp args | prefixexp ‘:’ Name args
args ::= ‘(’ [explist] ‘)’ | tableconstructor | LiteralString
functiondef ::= function funcbody
funcbody ::= ‘(’ [parlist] ‘)’ block end
parlist ::= namelist [‘,’ ‘...’] | ‘...’
tableconstructor ::= ‘{’ [fieldlist] ‘}’
fieldlist ::= field {fieldsep field} [fieldsep]
field ::= ‘[’ exp ‘]’ ‘=’ exp | Name ‘=’ exp | exp
fieldsep ::= ‘,’ | ‘;’
binop ::= ‘+’ | ‘-’ | ‘*’ | ‘/’ | ‘//’ | ‘^’ | ‘%’ |
‘&’ | ‘~’ | ‘|’ | ‘>>’ | ‘<<’ | ‘..’ |
‘<’ | ‘<=’ | ‘>’ | ‘>=’ | ‘==’ | ‘~=’ |
and | or
unop ::= ‘-’ | not | ‘#’ | ‘~’
O exemplo acima é toda a sintaxe da linguagem Lua.
Um gerador de parser pegaria uma sintaxe como essa e geraria um parser em uma linguagem de programação como C ou Java.
Mas enfim, vamos voltar para o nosso parser.
Existem diversas estratégias para escrever um parser, mas a mais comum é a Recursive Descent, que é uma estratégia top-down, ou seja, a gente começa do topo da árvore e vai descendo até as folhas. É como vamos fazer o nosso.
Outras variações são LL e LL(k), que são parsers top-down que usam lookahead para decidir qual regra aplicar.
Parsers bottom-up são mais complexos e geralmente são gerados a partir de uma gramática, como é o caso do LALR e LR.
Em linguagens de programação existem duas categorias de coisas, statements e expressions.
Statements são coisas que não retornam valores.
Expressions são coisas que retornam valores.
Exemplos de statements:
let x = 1;
Em algumas linguagens de programação let x = 1 é uma expression, mas em Monkey é um statement. Isso é uma decisão de design. Nem sempre uma mesma sintaxe em linguagens diferentes tem o mesmo significado.
Em GDScript, por exemplo, um
ifé uma expression, mas em JavaScript umifé um statement.
Exemplos de expressions:
-
1 + 2(retorna3) -
1(retorna1) -
true(retornatrue)
Essa distinção é importante porque em Monkey não podemos fazer coisas como:
let x = let y = 1;Isso não é possível porque let y = 1 é um statement e não uma expression.
A definição de statement e expression pode variar de pessoa para pessoa, mas essa definição vai servir para o nosso caso.
AST = Abstract Syntax Tree (Árvore Sintática Abstrata)
Uma AST é uma estrutura de dados que representa o código fonte de forma hierárquica, ela é muito útil para avaliar o código fonte.
O código fonte a seguir é representado pelo AST abaixo:
let x = 1 + 2;{
"type": "Program",
"value": [
{
"type": "LetStatement",
"value": {
"type": "Identifier",
"value": "x"
},
"expression": {
"type": "InfixExpression",
"value": {
"type": "IntegerLiteral",
"value": 1
},
"operator": "+",
"right": {
"type": "IntegerLiteral",
"value": 2
}
}
}
]
}O AST acima é um JSON fictício, mas os ASTs reais são muito parecidos com ele.
Significado de cada propriedade:
Dizemos que é uma árvore porque ela é composta por nós, e esses nós podem ter filhos. Dizemos que é uma árvore sintática porque ela representa a sintaxe da linguagem. Dizemos que é uma árvore sintática abstrata porque ela não representa o código fonte de forma exata, ela é uma abstração do código fonte onde só consideramos o que é importante para nós.
O parser é a ferramenta que nos permite transformar os tokens em uma AST, ele lê os tokens e gera a AST.
O nosso parser é um recursive-descent parser. Isso quer dizer que começamos do topo da árvore e vamos descendo até as folhas. Criando um nó raiz e adicionando nós filhos a ele usando funções recursivas que sabem que ASTs gerar para cada token.
- Context Free Grammar
- Backus-Naur Form
- Extended Backus-Naur Form
- Suporte a unicode (byte -> rune)
- Suporte a números de ponto flutuante
- Suporte a números hexadecimais
- Suporte a números binários
- Suporte a números octais
- Suporte a "_" em números para melhorar a legibilidade
- Suporte a comentários com
#