Jardinagem de Árvores Abstratas

Jardinagem de Árvores Abstratas (V2)

Link da palestra

Um pouco sobre o jardineiro

Bairro Felicidade, Belo Horizonte
PSL-MG, Minas Livre, Encontro Mineiro de Software Livre
Ministério da Cultura, Cultura Digital
Governo do Rio Grande do Sul, Gabinete Digital
Uma meia dúzia de startups, Burnout :(
Recurse Center
Datadog

Façamos uma pequena linguagem de programação

Por que? Pra que? Pra quem?

Este é um papo informal

Arquitetura geral de uma linguagem de programação

A linguagem alvo pode ser ou uma linguagem textual, ou código de máquina (Bytecode, Assembly).

Execução

Interpretador de Árvores: Exemplo
Interpretador de Bytecode: Exemplo
Código de Máquina (Assembly): Intel x86, ARM, RISC-V, etc

Exemplos

texto pra texto

texto pra bytecode

A JVM é alvo de vários compiladores: Java, Clojure, Kotlin, Scala, Groovy, Jython, etc…

Chrome's v8: everything all at once

fonte da imagem

Parsing

Transforma lista de caracteres em árvore de tokens

parse(input: string): Node

class Node:
  pass

class Number(Node):
  value: int

class String(Node):
  value: str

class Assignment(Node): # variable = value
  identifier: str
  right_hand_side: Node

# ...

Algorítmos Bottom-Up or Top-Down
Escrito à mão ou gerado a partir de uma gramática

Context Free Grammars (LR, LL, …)
Parsing Expression Grammars

Ferramentas

GNU Bison (Yacc compatible)
https://tree-sitter.github.io
https://www.antlr.org
https://github.com/ohmjs/ohm
https://github.com/clarete/langlang (Não é estável ainda :-)

Parsing Expression Grammars

sequence	`e1 e2`
ordered choice	`e1 / e2`
not predicate	`!e`
and predicate	`&e`	(sugar for `!!e`)
zero or more	`e*`
one or more	`e+`	(sugar for `ee*`)
optional	`e?`	(sugar for `&ee / !e`)

e.g.: Parser de CSV

Gramática Entrada Resultado

Gramática	Entrada	Resultado
`File <- Line* Line <- Val (',' Val)* '\n' Val <- (![,\n] .)*`	`a,b c,d`	`File( Line( Val('a'), ',', Val('b'), '\n' ), Line( Val('c'), ',', Val('d'), '\n' ) )`

File <- Line*
Line <- Val (',' Val)* '\n'
Val  <- (![,\n] .)*

a,b
c,d

File(
  Line(
      Val('a'), ',', Val('b'), '\n'
  ),
  Line(
      Val('c'), ',', Val('d'), '\n'
  )
)

Expressões Aritméticas

1 + 2 * 3 = 7
(1 + 2) * 3 = 9

Primeiros Arbustos

1 + 2 * 3 = 7

(1 + 2) * 3 = 9

Propriedades de Operadores

Aridade
Precedência
Associatividade

Notações de Expressões

infix
prefix
postfix

Prefix

+ 1 * 2 3 = 7
* + 1 2 3 = 9

Quem usa notação prefix?

lisp é um exemplo

(+ 1 (* 2 3))
(* 3 (+ 1 2))

Postfix

3 2 * 1 + = 7
1 2 + 3 * = 9

Quem usa notação postfix?

Máquina de Pilha

3 2 * 1 + = 7 2 1 + 3 * = 9

3 2 * 1 + = 7	2 1 + 3 * = 9
`push 3 push 2 mul push 1 add`	`push 2 push 1 add push 3 mul`

push 3
push 2
mul
push 1
add

push 2
push 1
add
push 3
mul

Pilhas

Array.push() e Array.pop()

Funções Primitivas

Textual Máquina de Pilha

Textual	Máquina de Pilha
`print("a") print(25)`	`push "a" ; copia a constante "a" pro topo do stack prim "print" 1 ; chama a função primitiva "print" ; que tem 1 parâmetro push 25 ; copia a constante 25 pro topo do stack prim "print" 1`

print("a")
print(25)

push "a"        ; copia a constante "a" pro topo do stack
prim "print" 1  ; chama a função primitiva "print"
                ; que tem 1 parâmetro

push 25         ; copia a constante 25 pro topo do stack
prim "print" 1

Variáveis

Textual Máquina de Pilha

Textual	Máquina de Pilha
`a = 1 print(a)`	`push 1 ; coloca o valor 1 no topo da pilha store 0 ; remove o valor no topo da pilha ; e salva na variavel 0 load 0 ; copia a variável 0 pro topo da pilha prim "print" 1`

a = 1
print(a)

push 1     ; coloca o valor 1 no topo da pilha
store 0    ; remove o valor no topo da pilha
           ; e salva na variavel 0

load 0     ; copia a variável 0 pro topo da pilha
prim "print" 1

Condicionais: Galhos (Branches)

Textual Máquina de Pilha

Textual	Máquina de Pilha
`if (a == b) { print("oi!") }`	`push b push a ; compara os dois valores no topo da pilha cmp ; Jump If Not Equal: Pula pro rótulo "exit" ; se a comparação não for igual jne exit push "oi!" prim "print" 1 exit: halt`

if (a == b) {
  print("oi!")
}

      push b
      push a
      ; compara os dois valores no topo da pilha
      cmp
      ; Jump If Not Equal: Pula pro rótulo "exit"
      ; se a comparação não for igual
      jne exit
      push "oi!"
      prim "print" 1
exit: halt

Repetições

Textual Máquina de Pilha

Textual	Máquina de Pilha
`a = 0 while (a < 10) { print(a) a++ }`	`push 0 store 0 loop: load 0 push 10 cmp jnb exit ; Jump if not below load 0 prim "print" 1 load 0 incr store 0 jmp loop ; Unconditional Jump exit: halt`

a = 0
while (a < 10) {
  print(a)
  a++
}

      push 0
      store 0
loop: load 0
      push 10
      cmp
      jnb exit      ; Jump if not below
      load 0
      prim "print" 1
      load 0
      incr
      store 0
      jmp loop      ; Unconditional Jump
exit: halt

Funções

Textual Máquina de Pilha

Textual	Máquina de Pilha
`function sum() { a = 2 return 40 + a } print(sum())`	`call sum 0 prim "print" 1 halt sum: push 2 store 0 push 40 load 0 sum ret`

function sum() {
  a = 2
  return 40 + a
}

print(sum())

     call sum 0
     prim "print" 1
     halt

sum: push 2
     store 0
     push 40
     load 0
     sum
     ret