Treetop: Depuração

September 30th, 2009 § 0 comments

Introdução

Continuando a série sobre Treetop, o objetivo desse artigo é falar um pouco sobre a depuração de gramáticas. Muitas vezes, o mecanismo de verificação do que a gramática está esperando, ilustrado no primeiro artigo, não é suficiente para identificar porque um reconhecimento está faltando–especialmente quando a gramática se torna mais complexa.

Parte da depuração consiste, na verdade, em tentar evitar erros mais primários. Outra parte consiste em usar alguns mecanismos para identificar problemas quando os erros primários já foram removidos. Falaremos de cada um deles na seqüência.

Evitando erros comuns

Um detalhe que deixei de fora no primeiro artigo é que uma PEG representa um parser descendente recursivo. E uma das fraquezas desse tipo de parser é que eles não são capazes de lidar com recursividade à esquerda.

Por exemplo, veja a regra abaixo:

string-of-a := string-of-a 'a' | 'a'

A lógica dita que isso deveria reconhecer uma seqüência de caracteres “a”. Na prática, isso não acontecer porque a regra está escrita de tal forma que para reconhecer a produção “string-of-a” seria necessário reconhecer “string-of-a” em seguida, o que leva, necessariamente, a recursividade infinita.

Existem packrat parsers que são capazes de lidar com isso mas não é o caso do Treetop. Existem técnicas formais para lidar com isso mas geralmente a melhor opção é criar uma regra que faça o processamento indireto do que se precisar e, com alguma criatividade, reescrever o necessário em uma fase posterior.

Para ilustrar ainda mais o ponto, veja a gramática abaixo que é uma variação da que estamos usando.

value := [0-9]+ / '(' expression ')'
product := expression (('*' / '/') expression)*
sum := expression (('+' / '-') expression)*
expression := product / sum / value

O problema com esse é que para saber o que é uma expressão, precisamos saber o que é um produto. Mas, para saber um produto, precisamos também saber o que é uma expressão.

A solução é simples:

expression := sum
sum := product (('+' / '-')) product)*
product := value (('*' / '/')) value)*
value := number / '(' expression ')'
number := [0-9]+

Um segundo ponto é utilizar apropriadamente operadores de lookahead para ajudar a remover ambigüidades da gramática. O uso dos mesmos é especialmente necessário por conta do modo como o operador de escolha ordenada trabalha. Como a segunda opção somente é considerada caso a primeira falhe, algumas vezes é necessário especificar cenários de falha na primeira para forçar a segunda a acontecer.

Suponha, por exemplo, que você tenha a seguinte gramática:

expression := numeric_expression / string_expression
numeric_expression := identifier ('+' identifier)*
string_expression := identifier ('||' identifier)*
identifier := [a-z]+

O problema dessa gramática é que a regra string_expression jamais será reconhecida. O que acontece é que para tentar descobrir se uma expressão é numérica, o parser precisa encontrar um identificador. Quando isso acontece, como a regra numeric_expression já possui um reconhecimento parcial, o parser tenta então encontrar o terminal +. Se isso não acontece–porque há um terminal ||–o parser aborta por não ter como seguir naquela regra.

Uma solução simples para resolver a ambigüidade é olhar para a frente e somente dizer que algo é uma expressão numérica se o identificador não for seguido por um operador que atue sobre strings. A gramática ficaria assim então:

expression := numeric_expression / string_expression
numeric_expression := identifier !'||' ('+' identifier)*
string_expression := identifier ('||' identifier)*
identifier := [a-z]+

Na maioria dos casos, isso é tudo o que você precisa para resolver a situação. Uma outra alternativa, é claro, é condensar as duas expressões, já que elas são essencialmente equivalentes, e fazer a diferenciação semântica em uma fase posterior (na análise semântica, mais ao ponto).

Um terceiro ponto é saber distinguir bem os separadores necessários para reconhecimento dos terminais. Em muitos casos, o modo mais simples é ideal. Algumas vezes, entretanto, é preciso usar alguma sofisticação. Para ilustrar, usando um exemplo da própria documentação do Treetop, teríamos algo como:

rule end_keyword
  'end' ![a-zA-Z0-9_]
end

Essa regra reconhece uma palavra chave end em uma linguagem em que palavras chaves podem ser seguidas por pontuação qualquer mas não por caracteres alfanuméricos.

Representações gráficas

Em muitos casos, é interessante visualizar o que o Treetop está reconhecendo. Para isso, uma característica interessante do mesmo adicionada em versões recentes é a habilidade de gerar um arquivo para o Graphviz. O uso é bem simples.

>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1+2*3-(4/5)").write_dot_file("results")
=> nil

O resultado é um arquivo results.dot que pode ser processado em uma imagem como no exemplo abaixo:

~$ dot -Tpng results.dot > results.png

A imagem final ficaria assim:

Parsing 1+2*3-(4/5)

Essa é uma maneira fácil de ver como o Treetop reconhecer a sintaxe de maneira mais básica.

Capturando a execução

Uma última forma de capturar o resultado da execução é interceptar as chamadas do parser gerado pelo Treetop. Essa é a forma menos confiável porque depende do conhecimento da estrutura interna do Treetop, que pode mudar a qualquer momento. Apesar disso, mesmo com adaptações necessárias de quando em quando, é uma boa forma de saber o que o Treetop está fazendo por trás das cenas.

A primeira coisa a fazer é gerar o arquivo do parser em si:

~$ tt simple_math.rb

Isso gera o parser em sua forma final, ao invés de compilá-lo cada vez que o require é feito.

A partir disso, é possível construir sobre os módulos que o Treetop gerou. Existe um módulo default com o nome que foi dado a gramática–no nosso caso, esse módulo é o SimpleMath. Em um arquivo simplemathdebug.rb, poderíamos ter o seguinte código:

require "treetop"
require "simple_math"

module SimpleMath
  
  def __depth
    @__depth ||= 0
  end
  
  def __inc_depth
    @__depth = __depth + 1
  end

  def __dec_depth
    @__depth = __depth - 1
  end
  
end

SimpleMath.instance_methods.each do |method|
  
  next unless method =~ /^_nt_(.*)$/
  
  rule = $1
  
  SimpleMath.send(:alias_method, ("_old" + method).to_sym, method.to_sym)
  
  SimpleMath.send(:define_method, method.to_sym) do
    puts (" " * __depth) + rule
    __inc_depth
    result = send("_old" + method)
    __dec_depth
    result
  end  
  
end

O que o código acima faz é interceptar as chamadas aos métodos que começam com _nt_, que são os métodos que efetivamente implementam o reconhecimento de produções e rastrear a profundidade em que estão sendo chamados para exibir a ordem em que as mesmas foram feitos.

Veja um exemplo de chamada:

>> require "simple_math_debug"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1+2*3")
expression
 term
  factor
   number
  factor
 expression
  term
   factor
    number
   term
    factor
     number
    factor
  term
=> SyntaxNode+Expression0 offset=0, "1+2*3" (expression,term):
  SyntaxNode offset=0, "1":
    SyntaxNode offset=0, "1"
  SyntaxNode offset=1, "+"
  SyntaxNode+Term0 offset=2, "2*3" (factor,term):
    SyntaxNode offset=2, "2":
      SyntaxNode offset=2, "2"
    SyntaxNode offset=3, "*"
    SyntaxNode offset=4, "3":
      SyntaxNode offset=4, "3"
>> p.parse("1+")
expression
 term
  factor
   number
  factor
 expression
  term
   factor
    number
   factor
  term
 term

Essa é uma maneira simples de saber o que está acontecendo e de ver se há falhas no reconhecimento específico de alguma regra. Como algumas regras podem ser bem complexas em sua implementação, esse tipo de estratégia permite uma visualização das entradas e saídas dos métodos.

Conclusão

Embora o Treetop seja relativamente simples em sua implementação, em alguns momentos é preciso quebrar a abstração e olhar o que está sob o código externalizado. As técnicas acima podem ajudar a resolver problemas comuns que vão surgir durante a implementação de uma linguagem qualquer.

No próximo artigo, um bônus: uma linguagem Turing-complete implementada usando o Treetop para análise sintática.

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

Tagged

Leave a Reply

Your email address will not be published. Required fields are marked *

What's this?

You are currently reading Treetop: Depuração at Superfície Reflexiva.

meta