dojo@centro 16/01/2013 – “Tolkien” e partes de compiladores

Olá, pessoas queridas. Tudo bem com vocês?

Na semana passada rolou um problema que foi muito bem recebido por todos e tem um excelente relato. Ia escrever um texto, mas postaram no grupo do Coding Dojo Rio uma excelente explicação, por isso essa explicação será postada e em seguida os participantes mais pontos positivos/negativos:

Post do Juan Lopes

É um problema que escolhemos com uma certa frequência, mas ontem tomamos um caminho bem interessante pra resolver.

Pra quem não esteve lá, é o problema da avaliação de expressões matemáticas. Terminamos o passo de tokenização da expressão, e paramos no meio da análise sintática. Estava bastante ansioso para continuar esse problema em casa, porque nunca havia feito isso “na unha”, sempre com ajuda de parser generators e fiquei surpreso em perceber que muito da teoria por trás de compiladores acaba ajudando na elegância do código final.
Essa gramática para parse de expressões aritiméticas é bem conhecida, podemos definir como:
<add> ::= <mult> (“+” <mult>)*
<add> ::= <mult> (“-” <mult>)*
 
<mult> ::= <primary> (“*” <primary>)*
<mult> ::= <primary> (“/” <primary>)*
<primary> ::= <number>
<primary> ::= “(” <add> “)”
O que achei legal é que se abrirmos mão de algumas práticas mais comuns, podemos implementar essa gramática quase como se lê em python.
A soma, por exemplo:
def add(tokens):
e = mult(tokens)        
while(tokens[0][0] in “+-“):
kind, image = tokens.pop(0) #+-
e = e + mult(tokens) + [kind]
return e
Simplesmente combinando a regra para parsear a soma com a da multiplicação (mostro depois), eu consigo combinar os dois resultados. Por exemplo, se eu tiver a expressão “1*2+3*4”, a primeira chamada de mult, vai ler os tokens 1, * e 2, processar isso e retornar algo como [1, 2, ‘*’], a segunda chamada (dentro do for), vai obter o token ‘+’ (tokens.pop(0)) e vai chamar mult de novo para ler 3*4, no final, ele vai concatenar o resultado da primeira chamada, com o resultado da segunda chamada e vai colocar a operação no final, resultando em:
[1, 2, ‘*’, 3, 4, ‘*’, ‘+’]
A multiplicação tem uma implementação igual (exceto que chama a regra primary, no lugar):
def mult(tokens):
e = primary(tokens)        
while(tokens[0][0] in “*/”):
kind, image = tokens.pop(0) #*/
e = e + primary(tokens) + [kind]
return e
A única regra diferente é a primary, que tem que decidir se produz um número ou inicia uma nova expressão com parenteses, mas isso é só uma questão de verificar o tipo do token antes:
def primary(tokens):
kind, image = tokens[0]
if kind == ‘N’:
tokens.pop(0) #N
return [int(image)]
elif kind == ‘(‘:
tokens.pop(0) #(
e = add(tokens)
tokens.pop(0) #)
return e
E só usando esse parser recursivo, conseguiríamos parsear qualquer expressão contendo as quatro operações básicas e parenteses, respeitando a precedência das operações.
O gist do método parse que passa nos testes do problema de ontem: https://gist.github.com/4556536.

Complementado por Thiago Belem:
Menção honrosa ao BNF que torna isso tudo super fácil de entender 🙂

 
Curti muito o problema e a nossa caminhada até uma possível (e bem plausível!) solução.
 
Claro que a sua explicação do N [+ N]* mudou o rumo da coisa, mas era só questão de identificar isso.
Compiladores foi a matéria que mais gostei (e aprendi algo?) até hoje na faculdade, mas o dojo de ontem valeu mais que um período inteiro! 😀
 
A qualidade e o conteúdo do dojo estão cada vez melhores, fico muito feliz de acompanhar esse progresso e aprender junto.

E como não poderia deixar de ser, Rodolfo contribuiu com:

E as pessoas que aprenderam um pouquinho mais de compiladores foram:
  • Flávio Amieiro
  • Eduardo Stalinho
  • Otávio Cardoso
  • Thiago Belem
  • Carlos Cunha
  • Juan Lopes
  • Eduardo Vinicius
  • Jacqueline Abreu
  • Israel Teixeira

Os “tolkiens” positivos foram 😀 :

  • “Tolkien +++
  • Problema (foi uma excelente releitura do problema, mostrando que podemos dar abordagens diferentes para problemas já feitos) +++
  • Polonesa Reversa (com gente achando que era posição sexual O_õ) ++
  • Componentes de compilador construído na unha (tem gente que deixará a unha crescer)
  • Compiladores apresentados mais formalmente no dojoRio
  • Volta de pessoas conhecidas e que estavam sumidas +++
  • Jac chegou “cedo” hoje (menos Barra na vida da Jac)
  • Cuca da Cissa – Mais um produto Bel[eé]m +
  • Rever os participantes do dojoRio #Centro
  • Não houve muita reescrita do código do outro – o grupo estava unido e conseguiu avançar a solução dada pela dupla que estava pilotando anteriormente.
  • Python
  • Casa cheia+
  • Muita comida (em especial a Cuca da Cissa) ++++
  • Retorno (pessoal) ao dojo
  • Chegar cedo
  • As pérolas proferidas neste dojo
Os “tolkiens” negativos foram 😀 :
  • Pessoas falando no vermelho
  • Jac pedindo desculpas demais
  • Código do tokenizer pode melhorar
  • Problema não foi definido no início e isso causou certo atraso
  • Não tinha suco
  • Atraso
  • Café acabou

 Quem sabe um dia, poderemos ter um compilador totalmente construído no dojoRio. Isso seria demais.

Se você gostou do relato, não deixe de estar conosco na ÍparosAv Treze de Maio, 13 – sala 616 – TODAS as 4º feiras. O pessoal começa a chegar entre 18:30 e 19:00 e para voltar, tem o metrô Cinelândia pertinho :D .

Esperamos todos vocês lá \o/

Anúncios

One Response to dojo@centro 16/01/2013 – “Tolkien” e partes de compiladores

  1. […] parte verde do diagrama acima foi resolvido no dojo de “Tolkien” e partes de compiladores e neste dojo o objetivo foi continuar construindo o compilador através do parser (ou a parte […]

%d blogueiros gostam disto: