Superfície Reflexiva

Introdução

Continuando a série sobre Treetop, vamos evoluir a utilização do parser de interpretação direta para um formato mais sofisticado que leve em conta outras características de processamento posterior. Na maioria dos casos, interpretação direta é suficiente para extrair da linguagem o necessário para a transformação ou execução. Algumas vezes, entretanto, as estruturas reconhecidas precisarão de algum refinamento ou recombinação posterior que fazer valer a pena um formato intermediário.

Para ilustrar isso, vamos usar a mesma gramática dos exemplos anteriores para gerar uma árvore sintática formalizada para as estruturas reconhecidas. E para fazer isso, vamos também usar algumas características adicionais do Treetop que gerar código mais elegante e com acoplamento menor.

Nossa gramática inicial permanece a mesma, como visto abaixo:

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

Usando módulos adicionais

Além de permitir a inserção de código Ruby diretamente na gramática, o Treetop permite duas outras formas de extensão da gramática. Uma dessas formas é definir classes específicas que herdam de SyntaxNode e permitem injeção de código manual no run-time do Treetop. Uma segunda forma, ainda mais elegante, é a definição de módulos que serão automaticamente utilizados pelo Treetop através do mecanismo usual de mixins do Ruby. Esse é o método que utilizaremos agora.

Vamos dizer que queremos transformar as produções reconhecidas pela linguagem definida por nossa gramática em uma árvore sintática específica para a mesma que possa ser guardada e posteriormente executada.

Obviamente, estamos usando uma linguagem tão simples que não há muitos benefícios em fazer isso. Mas, muitas vezes, isso faz sentido até por razões de performance. Digamos, por exemplo, que você esteja extraindo uma representação que será executada várias vezes com parâmetros diferentes. Não vale a pena executar o parsing a cada momento, utilizando o código diretamente injetado. Para esses momentos, uma representação sintática definida e específica para o domínio é bem mais interessante.

Para deixar as coisas mais interessantes, vamos modificar a nossa gramática acima para permitir que variáveis externas seja definidas e utilizadas, como por exemplo, para computar a expressão (b * b) - (4 * a * c) onde a, b e c são parâmetros variáveis fornecidos pelo ambiente de execução.

A gramática ficaria assim:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    primary
  end
  
  rule primary
    variable /
    number
  end
  
  rule variable
    [a-z]+
  end
  
  rule number
    [0-9]+
  end
  
end

Como é fácil perceber, não mudamos muita coisa. Existe agora uma regra adicional que define uma primária que pode ser um número ou uma variável e uma variável é simples um identificador alfabético simples.

Nossa árvore sintática será definida por uma coleção de nós com tipos que representam as várias estruturas que queremos ter no final. Por exemplo, queremos representar operações (um nó com um operador e dois operadores), variáveis e constantes. Essa é uma representação que definimos e que não necessariamente corresponde à árvore sintática reconhecida inicialmente pelo parser. Estamos transformando uma representação em outra.

A primeira coisa que precisamos, então é definir essas classes. Em um arquivo adicional, chamado simplemathast.rb, vamos inserir o seguinte código inicial:

class Constant
  
  def initialize(value)
    @value = value
  end
  
end

O código é trivial e, inicialmente, só define como vamos armazenar as informações. É fácil perceber que não estamos assumindo absolutamente nada sobre os dois operandos (left_side e right_side) na classe Operation. Os dois operandos podem ser outros nós da árvore tão complexos ou simples como necessário, ou seja, podem ser outras operações ou variáveis ou constantes.

O que precisamos agora é uma forma de construir a nossa árvore. Para isso, vamos interceptar a execução do parser usando módulos adicionais que serão inseridos nos nós sintáticos do Treetop para gerar o que precisamos.

A primeira coisa a fazer é adaptar a gramática. Como no artigo anterior, vamos começar de modo simples, reconhecendo somente números. A gramática ficaria assim:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    primary
  end
  
  rule primary
    variable /
    number
  end
  
  rule variable
    [a-z]+
  end
  
  rule number
    [0-9]+ <NumberPredicate>
  end
  
end

Veja a notação em negrito. Essa notação pede ao Treetop que introduza um módulo chamado NumberPredicate no nó sintático que reconhece números. Os métodos disponíveis no módulo serão, conseqüentemente, disponibilizados para o nó.

Para definir esse módulo, vamos usar um arquivo chamado simplemathext.rb com o seguinte conteúdo inicialmente:

module NumberPredicate
  
  def build
    Constant.new(text_value.to_f)
  end
  
end

O código define um módulo que será injetado no reconhecimento da produção number da gramática e que possui um método build que fará a construção inicial da árvore sintática. Esse método será usado para geração final da árvore. Vamos ver o método em execução no irb:

>> require "treetop"
=> true
>> require "simple_math_ast"
=> true
>> require "simple_math_ext"
=> true
>> require "simple_math_4"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1")
=> SyntaxNode+NumberPredicate offset=0, "1" (build):
  SyntaxNode offset=0, "1"
>> p.parse("1").build
=> #

Note como o nó sintático que representa o número agora possui automaticamente o módulo NumberPredicate adicionado e como o método build também faz parte do mesmo. Um problema que temos é a visualização da árvore, que pode ficar complicada à medida que mais nós são adicionados. Para resolver isso, uma maneira conveniente é utilizar S-expressions para gerar a visualização. A implementação é trivial:

class Constant
  
  def initialize(value)
    @value = value
  end
  
  def to_sexp
    [:constant, @value]
  end
  
end

E o resultado agora poderia ser visto com mais clareza:

>> p.parse("1").build.to_sexp
=> [:constant, 1.0]

A implementação de variáveis é similar. O nó da árvore sintática seria descrito no arquivo simplemathast.rb como mostrado abaixo:

class Variable
  
  def initialize(name)
    @name = name
  end
  
  def to_sexp
    [:variable, @name]
  end
  
end

class Constant
  
  def initialize(value)
    @value = value
  end
  
  def to_sexp
    [:constant, @value]
  end
  
end

Precisamos então criar o predicado que gera esse novo nó. No arquivo simplemathext.rb, o código ficaria assim:

module VariablePredicate

  def build
    Variable.new(text_value.downcase.to_sym)
  end
  
end

module NumberPredicate
  
  def build
    Constant.new(text_value.to_f)
  end
  
end

Finalmente, a gramática seria modificada para reconhecer isso:

grammar SimpleMath

  rule expression
    term ('+' / '-') expression / 
    term
  end
  
  rule term
    factor ('*' / '/') term / 
    factor
  end
  
  rule factor
    '(' expression ')' / 
    primary
  end
  
  rule primary
    variable /
    number
  end
  
  rule variable
    [a-z]+ <VariablePredicate>
  end
  
  rule number
    [0-9]+ <NumberPredicate>
  end
  
end

Usando o código, teríamos a possibilidade de fazer algo assim:

>> p.parse("x")
=> SyntaxNode+VariablePredicate offset=0, "x" (build):
  SyntaxNode offset=0, "x"
>> p.parse("x").build.to_sexp
=> [:variable, :x]

Implementar o nó que reconhece operações é também uma tarefa relativamente simples. Primeiro, temos o código do nó em si:

class Operation
  
  def initialize(operator, left_side, right_size)
    @operator = operator
    @left_side = left_side
    @right_side = right_size
  end
  
  def to_sexp
    [@operator, @left_side.to_sexp, @right_side.to_sexp]
  end
  
end

class Variable
  
  def initialize(name)
    @name = name
  end
  
  def to_sexp
    [:variable, @name]
  end
  
end

class Constant
  
  def initialize(value)
    @value = value
  end
  
  def to_sexp
    [:constant, @value]
  end
  
end

Note o uso recursivo dos lados esquerdo e direito na implementação do método to_sexp.

A implementação do predicado é um pouco maior agora já que precisamos lidar com dois casos: operações simples e expressões que estão entre parênteses (da mesma fora que fizemos no artigo anterior). A maneira mais simples é usar não um, mas dois predicados:

module NestedExpressionPredicate
  
  def build
    expression.build
  end
  
end

module OperationPredicate
  
  def build
    Operation.new(operator.text_value.downcase.to_sym, 
      operand1.build, operand2.build)
  end
  
end

module VariablePredicate

  def build
    Variable.new(text_value.downcase.to_sym)
  end
  
end

module NumberPredicate
  
  def build
    Constant.new(text_value.to_f)
  end
  
end

Usaremos o primeiro predicado para construir as expressões entre parênteses. Nesse caso, não precisamos construir a expressão simplesmente já que queremos somente ignorar os parênteses e construir a árvore da expressão aninhada. Por outro lado, o predicado da expressão já constrói um nó formal, da maneira que precisamos. Inserir isso na gramática é simples:

grammar SimpleMath

  rule expression
    operand1:term operator:('+' / '-') operand2:expression <OperationPredicate> / 
    term
  end
  
  rule term
    operand1:factor operator:('*' / '/') operand2:term <OperationPredicate> / 
    factor
  end
  
  rule factor
    '(' expression ')' <NestedExpressionPredicate> / 
    primary
  end
  
  rule primary
    variable /
    number
  end
  
  rule variable
    [a-z]+ 
  end
  
  rule number
    [0-9]+ 
  end
  
end

Note que estamos nomeando terminais para uso nos módulos. As regras são as mesmas que descrevemos no último artigo.

Com isso pronto, podemos reconhecer expressões inteiras:

>> p.parse("x").build.to_sexp
=> [:variable, :x]
>> p.parse("1+1").build.to_sexp
=> [:+, [:constant, 1.0], [:constant, 1.0]]
>> p.parse("x+1").build.to_sexp
=> [:+, [:variable, :x], [:constant, 1.0]]
>> p.parse("x+1-y").build.to_sexp
=> [:+, [:variable, :x], [:-, [:constant, 1.0], [:variable, :y]]]
>> p.parse("(b*b)-(4*a*c)").build.to_sexp
=> [:-, 
    [:*, [:variable, :b], [:variable, :b]], 
    [:*, [:constant, 4.0], [:*, [:variable, :a], [:variable, :c]]]]

A última linha foi quebrada para facilitar o entendimento da expressão gerada.

Se você observar agora somente o resultado de uma chamada ao método build, verá claramente que as estruturas estão aninhadas, com nós do tipo Operation codificando esse aninhamento.

É fácil perceber que não há muito mistério na criação de árvores sintáticas derivadas. Caso você queira ver um exemplo bem sofisticado disso, o projeto Cucumber é uma boa opção. Para parsing das estórias, o projeto usa um linguagem bem sofisticada descrita com o Treetop.

Interpretando a árvore sintática

Agora que temos uma árvore, podemos continuar executando a representação descrita pela árvore. Existem várias maneiras de fazer isso, mas a mais simples é usar a própria árvore recursivamente. Podemos criar um método run em cada nó que devolve o valor executado do mesmo. Esse método precisa receber algum tipo de ambiente para que variáveis possam receber seus valores. É fácil perceber que podemos gerar um árvore uma única vez e processá-la múltiplas vezes usado ambientes diferentes.

A maneira mais simples de implementar um ambiente é passar um hash que contenha as variáveis. A implementação, que é trivial, ficaria assim:

class Operation
  
  def initialize(operator, left_side, right_size)
    @operator = operator
    @left_side = left_side
    @right_side = right_size
  end
  
  def run(env = {})
    @left_side.run(env).send(@operator, @right_side.run(env))
  end
  
  def to_sexp
    [@operator, @left_side.to_sexp, @right_side.to_sexp]
  end
  
end

class Variable
  
  def initialize(name)
    @name = name
  end
  
  def run(env = {})
    env[@name] || (raise "The variable #{@name} is undefined")
  end
  
  def to_sexp
    [:variable, @name]
  end
  
end

class Constant
  
  def initialize(value)
    @value = value
  end
  
  def run(env = {})
    @value
  end
  
  def to_sexp
    [:constant, @value]
  end
  
end

Estamos usando exatamente a mesma técnica descrita no artigo anterior, recursivamente operando sobre a árvore para chegar a um resultado final. A diferença é que, nesse caso, estamos utilizando somente três tipos de nós nomeados. Poderíamos, é claro, ter feito algo mais sofisticado usando um nó diferente para cada operação mas isso seria mais do que precisamos no momento.

O código em operação ficaria assim:

>> require "rubygems"
=> false
>> require "treetop"
=> true
>> require "simple_math_ext"
=> true
>> require "simple_math_ast"
=> true
>> require "simple_math_4"
=> true
>> p = SimpleMathParser.new
=> ...
>> ast = p.parse("(b*b)-(4*a*c)").build
=> ...
>> ast.run(:a => 1, :b => 2, :c => 3)
=> -8.0
>> ast.run(:a => 0, :b => 2, :c => 10)
=> 4.0
>> ast.run(:a => 3.2, :b => 4.1, :c => 1.8)
=> -6.23
>> ast.run(:a => 0, :c => 0)
RuntimeError: The variable b is undefined

Alguns resultados foram elididos na representação acima mas é fácil ver como o código funciona. Mesmo o caso em que uma variável não é declarada, é possível capturar e processar o erro. De certa forma, isso representa um nível incipiente de análise semântica do código–que, nesse caso, aborta na primeira tentativa. Seria igualmente possível continuar o processamento e capturar todas as variáveis não declaradas de uma só vez.

Conclusão

Nesse artigo vimos que é possível processar o reconhecimento de uma linguagem qualquer com o parser gerado pelo Treetop em qualquer nível de sofisticação desejado. Obviamente, o exemplo que estamos usando é bem simples mas a mesma técnica poderia ser usada para realizar qualquer tipo de interpretação ou compilação desejada.

Um extensão possível do código acima, que pode ficar como um exercício, é implementar algum sistema de double dispatching para realizar geração de código (C, por exemplo), que faça o trabalho necessário.

No próximo artigo, veremos algumas técnicas rápidas para a depuração básica e identificação de erros em gramáticas Treetop.

Nota: Para seguir a série completa, siga a categoria Treetop deste blog.

Tagged: Tecnologia