Criando uma Calculadora Usando o Pyparsing

Não é de hoje que eu venho me interessando pela implementação de parsers, mas nunca estudei o suficiente pra fazer um BOM trabalho.
Começei a folhear o livro Programming Languages: Application and Interpretation (PLAI), que o Luciano Ramalho tinha me indicado na PythonBrasil[5] em Setembro de 2009. O livro é bem intessante, mas eu estava lendo no meu PSP e é um pouco desconfortável, por isso estou pensando em procurar saber se está à venda ou acabar imprimindo mesmo (está sob Creative Commons). O livro começa dizendo que nada melhor pra entender uma determinada linguagem do que escrevendo um interpretador para a mesma, assim, começa escrevendo um interpretador pra uma linguagem (inicialmente aritmética) em Scheme.

Achei bem interessante esta abordagem e acabei por tentar fazer algo parecido em Ruby, mas como em Ruby não há o mesmo suporte que Scheme pra expressões do tipo: (+ 1 2) e a linguagem já perceber que isto é um bloco e separar pra você o +, o 1 e o 2, acabei indo pro Python brincar com o Pyparsing – o qual eu já estou pra aprender de verdade há uns poucos meses e não estudei direito. Foi uma ótima oportunidade pra aprender um pouco do Pyparsing e botar alguns conhecimentos em prática.

Uma coisa que eu acho interessante quando se trata de interpretadores/parsers é a gramática – coisa que só começei a me interessar nos últimos meses. O Cucumber por exemplo, usa o TreeTop pra montar seu parser, dado uma gramática definida. Eu não poderia deixar de citar o famoso Yacc, que criar parsers em C (muito usado em conjunto com o Lex na criação de compiladores), mas eu nunca usei nenhuma dessas ferramentas e acabei por pegar o Pyparsing mesmo, o qual eu tenho que aprender a usar.

O objetivo desse tutorial é mostrar o uso do Pyparsing pra criar uma calculadora com notação prefixada e parênteses.
O que significa isso? Significa que as expressões matemáticas não serão do tipo: 1 + 2, mas sim (+ 1 2) [notação comum pra quem programa em LISP].

Caso eu fosse definir uma gramática BNF eu começaria assim:

<expr> ::= <num>
         | (+ <num> <num>)
         | (- <num> <num>)

O que isso significa? Significa que nossas expressões podem ser do tipo:

1
(+ 1 2)
(- 3 4)

E nada além disso!

Depois te instalar o pyparsing, vamos começar nossa implementação (pra instalar basta um easy_install pyparsing):

from pyparsing import Word, White, nums, Literal, OneOrMore, Group

numero = Word(nums)
abre_parenteses = Literal('(').suppress()
fecha_parenteses = Literal(')').suppress()
espacos = OneOrMore(White()).suppress()
mais = Literal('+')
menos = Literal('-')
expr = Group(numero |
             (abre_parenteses +
                 (mais|menos) + espacos + numero + espacos + numero +
              fecha_parenteses))

OPERACOES = {
             '+': lambda x, y: x + y,
             '-': lambda x, y: x - y,
            }

def calcular(e):
    expr_parseada = expr.parseString(e)[0]
    if len(expr_parseada) == 1:
        return int(expr_parseada[0])
    operacao = OPERACOES[expr_parseada[0]]
    return operacao(int(expr_parseada[1]), int(expr_parseada[2]))

Sempre que for necessário dizer que queremos um certo conjunto de caracteres que representam uma coisa só (diz-se que é uma palavra), usamos o Word. Nesse caso, nums é uma string com os caracteres de 0 a 9. Assim, temos um objeto que pode conter os dígitos de 0 a 9 em qualquer quantidade – uma “palavra” em que os caracteres possíveis são 0, 1, 2, 3, 4, 5, 6, 7, 8 ou 9 em qualquer ordem e quantidade.

O Literal é usado sempre que queremos dizer EXATAMENTE o que queremos – nada mais, nada menos! O método suppress apenas indica pro pyparsing que pra nós esse valor não importa, apesar de ter que estar no texto, nós o ignoramos como resultado.

Quando precisamos que algo apareça pelo menos uma vez, podemos usar o OneOrMore. No nosso caso deve haver pelo menos um espaço em branco, que está representado pelo White() (que diz respeito aos caracteres ' ', '\t', '\n', '\r') e também ignoraremos esse resultado.

O mais e menos são também expressões literais. Mas vejam que não foi usado o suppress neles, pois nesse caso é necessário obte-los como resultado.

Por fim, nossa expressão será um grupo (Group) de “subexpressões”. Estamos dizendo que nossa expressão expr será: um número OU um parêntese pra abrir, sinal de + ou de -, espaços, um número, espaços, outro número e um parêntese pra fechar. O pipe (|) significa OU de expressões.

Quando parsearmos alguma expressão válida com o pyparsing através do método parseString, ele retornará um objeto do tipo ParseResults, que pode ser usado com a mesma interface de uma lista. No caso acima o método parseString foi chamado passando como segundo argumento o valor True, indicando que nossa expressão não pode conter nada além do que foi definido.
Assim, dado o caso acima, quando fizermos:

>>> expr.parseString("1")
([(['1'], {})], {})

>>> print expr.parseString("1")
[['1']]

>>> print expr.parseString("1")[0]
['1']

O que nos interessa saber aqui é que no caso acima o resultado será uma lista-like, e o primeiro objeto é o nosso Group. O primeiro e único elemento nesse caso é o número 1 (como string).

O segundo caso (um bem simples), seria fazer:

>>> print expr.parseString("(+ 1 2)")[0]
['+', '1', '2']

Agora já é possível entender a implementação: se o resultado tiver apenas um elemento, é um número único. Caso contrário é uma expressão, tendo o operador como primeiro elemento e os dois próximos elementos são os operandos.

Bem, nossa calculadora está MUITO simples até agora. Só aceitamos números inteiros, podemos somar ou subtrair e subexpressões não funcionam. O interessante agora é implementar subexpressões.

Vamos começar trocando a nossa gramática BNF:

<expr> ::= <num>
         | (+ <expr> <expr>)
         | (- <expr> <expr>)

E agora, o que estamos dizendo?! Estamos dizendo que uma expressão pode ser um número sozinho, como em “1”, ou pode ser algo como “(+ (- 2 1) 3)”, que seria uma expressão com subexpressões. Oh, confuso? É a recursividade!
Parando pra analisar não fica difícil de entender. Atentente-se pra que no fim das contas vai existir uma subexpressão que será do tipo (+ <num> <num>), tornando possível fazer subexpressões em qualquer quantidade!

Vamos à implementação:

from pyparsing import Word, White, nums, Literal, OneOrMore, Group, Forward

numero = Word(nums)
abre_parenteses = Literal('(').suppress()
fecha_parenteses = Literal(')').suppress()
espacos = OneOrMore(White()).suppress()
mais = Literal('+')
menos = Literal('-')
expr = Forward()
atomo = numero | expr
expr << Group(numero |
              (abre_parenteses +
                 (mais|menos) + espacos + atomo + espacos + atomo +
               fecha_parenteses))

OPERACOES = {
             '+': lambda x, y: x + y,
             '-': lambda x, y: x - y,
            }

def avaliar(e):
    if len(e) == 1:
        return int(e[0])
    operacao = OPERACOES[e[0]]
    return operacao(avaliar(e[1]), avaliar(e[2]))

def calcular(e):
    expr_parseada = expr.parseString(e, True)[0]
    return avaliar(expr_parseada)

A maior diferença desse código pro anterior está na definição da expressão expr. Aquele Forward significa que definiremos depois o valor pra expr, mas ela já pode ser usada, mesmo sem valor definido! Mas pra que diabos seria isso necessário? Bem, é a única maneira de fazermos nossa expressão “recursiva”. Continuemos com a definição pra que clarifique o raciocínio… Foi definido atomo que pode ser um número ou uma expressão. Nesse ponto está a mágica. Cada “subexpressão” será um número ou uma expressão (que pode ser um número ou uma expressão e assim recursivamente, até chegar num momento que a subexpressão será um simples número). Se não pudessemos definir uma expressão sem valor previamente definido não seria possível fazer isso! Depois dizemos que expr vai receber (<<) a expressão desejada, que será: um número OU um parêntese pra abrir, sinal de + ou de -, espaços, uma expressão, espaços, outra expressão e um parêntese pra fechar. Repetindo: vai chegar numa hora que cada subexpressão será basicamente um número!

O método calcular agora passou a responsabilidade de avaliar cada subexpressão pro método avaliar, porque tem que ser feito recursivamente.
O método avaliar verifica se a expressão e é um número sozinho (ou seja, tem tamanho um), e, caso seja, retorna a string como inteiro. Caso contrário a expressão será do tipo “(+ <expr> <expr>)”, e teremos que ir avaliando essas subexpressões até chegar no ponto em que <expr> será um <num> (caso que retorna a conversão pra inteiro).

Simples, não?!

Agora implementar multiplicação, divisão e exponenciação é simples e ficará como exercício. A idéia de fazer uma calculadora com parênteses e prefixada é pra facilitar mesmo, pois não é necessário importar-se com precedências e etc.

Os códigos acima estão no github (e estão com testes!) como gists:
primeira calculadora em http://gist.github.com/279361 e a segunda calculadora em http://gist.github.com/279362

Depois que o leitor tiver feito o exercício, pode dar uma olhada numa outra calculadora um pouco mais “potente” que eu fiz usando a mesma idéia: http://gist.github.com/279357

Achei o Pyparsing realmente muito útil. O problema é que a documentação livre dele é muito fraca, mas pelo menos há vários códigos de exemplo no site. Há um livro sobre o Pyparsing, Geting Started with Pyparsing mas não está disponível livremente na rede. Não sei nem se existe algum material em português, mas fica aí a minha contribuição!

update: corrigida a confusão com os nomes infix e prefix