Introdução
Continuando a série sobre Treetop, é hora de ver como realmente utilizar um parser para produzir resultados de execução. Até o momento, vimos somente como montar a gramática e como obter uma árvore que pode ser utilizada de alguma forma.
Como a árvore sintática que o parser gera já é bem completa, a tentação seria de usar a mesma e processá-la recursivamente através de um rotina que identificasse os dados necessários ou alguma espécie de pattern com o Visitor.
Não é uma estratégia de todo ruim, mas o Treetop provê mecanismos para ajudar nisso sem a necessidade de processar a árvore diretamente nó a nó; antes, é possível processar somente os nós necessários e já fazer algum tipo de interpretação direta dos elementos reconhecidos da linguagem.
Esse processamento pode ser feito de duas maneiras. Primeiro, pela injeção de código Ruby diretamente no parser, permitindo o processamento posterior através de algum callback. Segundo, pela construção de alguma árvore sintática específica à linguagem que espelhe a árvore inicial gerada mas de uma maneira mais processável, por assim dizer.
O tema desse artigo é a primeira técnica, que veremos logo a seguir.
Introduzindo código Ruby no parser
Vamos voltar a nossa gramática inicial:
grammar SimpleMath
rule expression
term ('+' / '-') expression /
term
end
rule term
factor ('*' / '/') term /
factor
end
rule factor
'(' expression ')' /
number
end
rule number
[0-9]+
end
end
Digamos que queremos ter o resultado da expressão aritmética que está sendo reconhecida pela linguagem. O processo não é complicado.
Obviamente, precisamos começar tendo o valor dos números que compõem a unidade final da gramática. Em seguida, pelo modo como nossa gramática está estruturada, precisamos ter o valor da multiplicação ou divisão entre fatores e termos, expresso pela segunda regra. E assim por diante.
Uma pergunta é: por que não precisamos de processar cada um das regras. A resposta está na própria forma como a gramática é reconhecida. Em última instância, por exemplo, um termo é também um fator (como expresso pela segunda opção dentro da regra term
). E, pelo mesmo ponto de vista, um fator, em última instância pode ser um número. Isso implica que em alguns casos, basta o reconhecimento da regra final para permitir o acesso.
Vamos aplicar, então, esse conhecimento à gramática, reconhecendo inicialmente números. A gramática ficaria assim:
grammar SimpleMath
rule expression
term ('+' / '-') expression /
term
end
rule term
factor ('*' / '/') term /
factor
end
rule factor
'(' expression ')' /
number
end
rule number
[0-9]+ {
def eval
text_value.to_f
end
}
end
end
Note o código Ruby entre as chaves, em negrito. Essa é a forma que o Treetop usa para inserir código diretamente dentro do nó sintático que aquela regra representa.
O código acima introduz um novo método chamado eval
ao nó que reconhece a regra números. Esse código diz que o valor daquele nó é o seu valor textual convertido para um número de ponto flutuante. O método text_value
é inerente ao Treetop e existe em todos os nós.
Podemos usar agora isso da seguinte maneira:
>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1")
=> SyntaxNode+Number0 offset=0, "1" (eval):
SyntaxNode offset=0, "1"
>> p.parse("1").eval
=> 1.0
Note duas coisas. Primeiro, o método eval
está disponível diretamente na árvore sintática, como mostrado pelo resultado do parsing. Segundo, embora a regra inicial da gramática seja expression
, somente a regra number
foi reconhecida dessa vez. Isso prova o que foi explicado acima, sobre o cascateamento de expressões.
Note também o uso de próprio nome de uma regra (expression
nesse caso) dentro do método. Qualquer não-terminal dentro de uma regra será exposto pelo Treetop dessa forma.
Vamos agora evoluir para reconhecer fatores, a regra imediatamente acima que usa números ou reconhece uma expressão dentro de parênteses. A idéia é a mesma e a implementação é igualmente simples.
grammar SimpleMath
rule expression
term ('+' / '-') expression /
term
end
rule term
factor ('*' / '/') term /
factor
end
rule factor
'(' expression ')' {
def eval
expression.eval
end
} /
number
end
rule number
[0-9]+ {
def eval
text_value.to_f
end
}
end
end
Agora é possível fazer a interpretação de expressões como a mostrada abaixo, o que constrói o nosso próximo nível:
>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("(1)")
=> SyntaxNode+Factor1+Factor0 offset=0, "(1)" (expression,eval):
SyntaxNode offset=0, "("
SyntaxNode+Number0 offset=1, "1" (eval):
SyntaxNode offset=1, "1"
SyntaxNode offset=2, ")"
>> p.parse("(1)").eval
=> 1.0
Com isso pronto, é hora de reconhecer multiplicação e divisão, ou seja, operações sobre termos, o nosso próximo item nas regras. A modificação não é muito mais complexa:
grammar SimpleMath
rule expression
term ('+' / '-') expression /
term
end
rule term
factor operator:('*' / '/') term {
def eval
factor.eval.send(operator.text_value.to_sym, term.eval)
end
} /
factor
end
rule factor
'(' expression ')' {
def eval
expression.eval
end
} /
number
end
rule number
[0-9]+ {
def eval
text_value.to_f
end
}
end
end
Esse código faz uso de uma característica nova do Treetop: a possibilidade de nomear um não-terminal ou terminal reconhecido para uso na implementação internal. No caso acima, como o resultado do reconhecimento da regra pode ser tanto o sinal de adição quando o de multiplicação dentro da escolha ordenada entre parênteses, precisamos de uma forma para referenciar isso. O label
colocado à frente do não-terminal se encarrega disso, criando um novo método que o representa e pode ser usado como qualquer outro termo interno.
O código também faz uso do fato de que o Ruby é uma linguagem (quase que) 100% orientada a objetos e que mesmo elementos primitivos da linguagens podem receber mensagens.
Para que não conhece detalhes do Ruby, essencialmente, o código acima faz o seguinte:
- Avalia o fator, o lado esquerdo da expressão. Esse método
eval
foi introduzido no passo anterior; - Avalia o termo restante, o lado direito da expressão;
- Finalmente, envia o método representado pelo operador ao termo, com o parâmetro sendo o resultado do termo.
Digamos que o fator tenha tido como resultado 2 e o termo tenha tido o resultado 3 como o operador +
. A expressão final é equivalente a:
2.send(:+, 3) # => 2 + 3 = 5
Para fechar a interpretação, o código que lida com termos é o mesmo:
grammar SimpleMath
rule expression
term operator:('+' / '-') expression {
def eval
term.eval.send(operator.text_value.to_sym, expression.eval)
end
} /
term
end
rule term
factor operator:('*' / '/') term {
def eval
factor.eval.send(operator.text_value.to_sym, term.eval)
end
} /
factor
end
rule factor
'(' expression ')' {
def eval
expression.eval
end
} /
number
end
rule number
[0-9]+ {
def eval
text_value.to_f
end
}
end
end
Agora é possível rodar expressões arbitrárias como demonstrado abaixo:
>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1+2*3").eval
=> 7.0
>> p.parse("(1+2)*3").eval
=> 9.0
>> p.parse("(1+2)*(3-4)").eval
=> -3.0
>> p.parse("(1+2)*(3-4/5)").eval
=> 6.6
Como é possível ver, as regras de precedência normais são reconhecidas. Isso acontece pela forma como a gramática foi desenhada e não por causa de propriedades inerentes da linguagens.
Caso fosse possível acompanhar a execução de cada expressão acima, seria fácil perceber que os métodos são recursivamente invocados para gerar o resultado final, ou seja, para a expressão (1+2)*(3-4/5)
, o processo acontece da seguinte forma:
1.0 +
2.0
3.0
3.0 *
3.0 -
4.0 /
5.0
0.8
2.2
2.2 =
6.6
Conclusão
Como esse artigo demonstra, introduzir código Ruby em um parser gerado pelo Treetop é algo bem simples e facilmente controlável. Embora o artigo tenha mostrado somente a inserção de um método simples, é possível introduzir qualquer quantidade de métodos, públicos ou não, para utilização.
Por exemplo, para uma gramática um pouco diferente (mostrada abaixo de forma incompleta), utilizando não-terminais para operadores, seria simples fazer algo do tipo:
grammar SimpleMath
rule expression
operand1:term operator:SUM_OP operand2:expression {
operator.apply(operand1, operand2)
} /
term
end
rule SUM_OP
'+' {
def apply(operand1, operand2)
operand1 + operand2
end
} /
'-' {
def apply(operand1, operand2)
operand1 - operand2
end
}
end
# ...
end
Como é possível ver, não há limite para o que se possa fazer com essa técnica.
Até o momento, vimos como usar uma gramática para não só reconhecer uma linguagem formal como também para executar instruções sobre essa linguagem. Na maioria dos casos, isso é suficiente mesmo para tarefas mais complexas. Entretanto, algumas vezes é necessário utilizar um reconhecimento mais sofisticado. Esse será o tema do próximo artigo.
Nota: Para seguir a série completa, siga a categoria Treetop deste blog.
Æ!!
Artigo impecável! 😀
Muito bom de acompanhar e mostrando passos simples e fáceis de entender!
Ronaldo como sempre mandando bem! Aguardo a continuação da série!
Há braços
Opa, Willian! Mais uma vez, obrigado!