Superfície Reflexiva

Introdução

Uma das tarefas mais comuns em programação é transformar uma representação qualquer de dados e/ou código em outra necessária para a execução de uma tarefa.

Quem acompanha o meu blog há mais tempo, sabe que eu sou um grande fã de Domain Specific Languages, uma das formas de fazer esse tipo de transformação sem sair do escopo da própria linguagem em que se está desenvolvendo. Muitas vezes, entretanto, é necessário algum tipo de conversão mais específica–uma compilação, por assim dizer.

Existem várias formas de fazer esse tipo de compilação mais específica, que podem ser baseadas em estruturas tão “simples” como expressões regulares a estruturas bem mais complexas como gramáticas livre de contexto (CFG) que lidam com ambigüidades e recursividade de maneira mais completa. De uma forma mais simples, tanto expressões regulares como CFGs são linguagens formais que, por sua vez, expressam como uma outra linguagem específica pode ser gerada ou analisada para criar a transformação necessária.

Esse tipo de formalização é válida para qualquer transformação e é exatamente a mesma técnica, por exemplo, aplicada na descrição de uma linguagem de programação. O que varia, na maioria dos casos, é a complexidade final da linguagem que está sendo descrita, que limita o tipo de gramática e formalização que precisa ser usada. Para ilustrar isso, considere o seguinte exemplo em C:

x * y;

A princípio, isso pode ser interpretado como uma simples multiplicação de duas variáveis x e y cujo valor é descartado sem ser usado. Por outro lado, isso também pode ser interpretado com a declaração de uma variável y que é um ponteiro deferenciado do tipo x. Esse tipo de ambigüidade e complexidade limita quais ferramentas e técnicas podem ou precisam ser utilizadas. Um exemplo final dessa ambigüidade é o problema do else solto.

Nos últimos anos, uma técnica ou ferramenta que tem surgido com uma alternativa para tornar o trabalho de definição de linguagens e transformações de maneira mais fácil são as Parsing Expression Grammars, das quais o Treetop, assunto desse artigo, é um gerador.

Uma parsing expression grammars (ou PEG) é um tipo de gramática formal que descreve uma linguagem e pode ser usada para criar a base de uma transformação mais específica e mais poderosa do que uma simples linguagem de domínio baseada em uma linguagem de programação qualquer.

Uma característica fundamental de uma PEG é que ela é, por definição, analítica, isto é, ela reconhece texto em uma linguagem e gera uma árvore sintática do que reconheceu--ou, obviamente, falha. Isso difere da capacidade geradora de outras classes de gramáticas que são capazes, como o nome indica, de gerar todas as possíveis expressões representadas por uma linguagem formal.

Uma outra característica fundamental de uma PEG é que ela não pode ser ambígua. Dado um texto qualquer a ser reconhecido como uma parte de linguagem, aquele texto possui uma e somente uma árvore sintática. Isso não quer dizer que a linguagem não seja capaz de ter construtos ambíguos--eles somente não serão reconhecidos diretamente na fase em que a PEG está envolvida e requerem algum processamento posterior. Significa, entretanto, que se há alguma ambigüidade inerente na linguagem que precise ser resolvida em tempo de análise sintática, uma PEG não será capaz de lidar com a mesma.

Finalmente, uma terceira característica de uma implementação de PEG é que a fase de análise léxica e análise sintática são feitas de uma única vez.

Para terminar com essa breve introdução teórica--que, por admissão, nem arranha a superfície do assunto--um item final é que a implementação do parser de uma PEG possui certas características de performance de execução que podem inviabilizar a implementação de uma gramática qualquer. Para lidar com isso, normalmente a implementação é feita usando um packrat parser, que é uma forma de implementação que troca uso de memória para conseguir rodar em tempo linear. Basta dizer que o Treetop é um exemplo desse tipo de gerador, criando packrat parser em Ruby puro.

Descrevendo uma PEG

A descrição de uma PEG, ou seja, a formalização de qual linguagem a mesma reconhece usa uma notação que mistura elementos de expressões regulares e BNF, com uma interpretação ligeiramente diferente para tornar o reconhecimento mais simples.

Os elementos fundamentais dessa notação são:

• Uma regra de início da gramática
• Um conjunto de terminais, isto é, elementos que geram uma representação final da linguagem, que não podem ser quebrados em unidades menores sem perder significado
• Um conjunto de não-terminais, isto é, elementos que podem ser decompostos em outros, inclusive em referências a si próprios
• Um conjunto de regras que descrevem essa decomposição

Essas regras podem ser definidas pelos seguintes operadores:

• Seqüência: e₁ e₂ -- a regra é composta por esses dois elementos na ordem dada
• Escolha ordenada: e₁ / e₂ -- a regra é composta por um ou outro dos elementos
• Zero ou mais: e*
• Um ou mais: e+
• Opcional: e?
• Predicado E: &e
• Predicado Não: !e

A regra acima que explica a diferença essencial entre uma PEG e uma CFG é que o operador de escolha é ordenado, ist é, se a primeira alternativa tem sucesso, a segunda é completamente ignorada. Não existe então a possibilidade de que duas árvores sintáticas sejam geradas. Em caso de ambigüidade, a escolha ordenada pode ser usada para escolher uma cominho específico.

Além disso, os predicados E e Não podem ser usados para remover ainda mais ambigüidades por permitir olhar à frente nas regras que estão sendo analisadas e tomar decisões com base nisso. Por exemplo, é possível dizer que uma regra qualquer é válida desde que não seja seguida por tais e tais construtos. A possibilidade de olhar à frente (lookahead) de maneira ilimitada é responsável pelas complicações mencionadas acima que requerem a implementação de packrat parsers.

Para dar um exemplo de uma gramática e tornar esse questão toda mais real, vamos olhar uma gramática capaz de reconhecer expressões matemáticas simples:

expression := term ('+' / '-') expression / term
term := factor ('*' / '/') term / factor
factor := '(' expression ')' / number
number := [0-9]+

A gramática acima descreve as seguintes regras:

• Uma expressão é um termo, seguido de um operador de adição ou subtração, seguido de uma outra expressão OU um simples termo;
• Um termo, por sua vez, é um fator seguido de uma operador de multiplicação ou divisão, seguido por um outro termo OU um simples fator;
• Um fator é uma expressão entre parênteses OU um número;
• Finalmente, um número é uma seqüência de um ou mais dígitos.

Note o uso do operador de escolha ordenada para descrever as regras. Por ser ordenado, o operador automaticamente estabelece regras de precedência, ou seja, uma adição, por aparecer primeiro, tem maior precedência do que uma subtração. O mesmo é válido para a multiplicação e divisão.

Por outro lado, isso não significa que haja automaticamente uma precedência específica entre regras diferentes. No caso acima, pela forma como as regras estão estruturadas, multiplicação e divisão possuem maior precedência do que subtração e adição por serem reconhecidas primeiro.

Uma outra maneira de descrever a mesma gramática é:

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

Ambas as formalizações acima descrevem a mesma gramática de formas diferentes. A árvore final gerada será diferentes mas tem a mesma interpretação. A grande diferença, talvez, seja que a segunda gramática é mais fácil de entender do que a primeira, embora mais difícil de ser estendida.

Essa gramática descreve as seguintes regras:

• Uma expressão é uma soma;
• Uma soma é uma seqüência de zero ou mais adições ou subtrações de produtos;
• Um produto é uma seqüência de zero ou mais multiplicações ou divisões de valores;
• Um valor é um número ou uma expressão entre parênteses;
• Finalmente, um número é uma seqüência de um ou mais dígitos.

Dependendo de como o parser é gerado, pode ser mais ou menos fácil lidar com uma gramática em particular. Nesse caso, a escolha de quais produções são especificadas pela gramática pode ser crucial para facilitar a implementação da linguagem.

Note que as gramáticas acima não descrevem reconhecimento de espaços brancos entre as produções. A gramática acima reconheceria 1+2*3 mas não 1 + 2 * 3. Para mudar isso, algo a mais ter que ser definido. Mostrando um pedaço de uma gramática adaptada, as regras ficaram, por exemplo:

value := [0-9]+ / '(' spaces? expression spaces? ')'
spaces := [ \t\r\n]+

Essa é uma visão simples do processamento de espaços opcionais, mas válida.

Usando o Treetop

Depois de toda essa introdução é hora de finalmente colocar o Treetop em ação. Assumindo que você tenha uma versão recente do Ruby, a instalação do Treetop é simples:

~$ sudo gem install treetop

Com o Treetop instalado, podemos escreve a nossa gramática. Não coincidentemente, a sintaxe do Treetop é uma PEG em também--para completar, inclusive, o Treetop possui é capaz de fazer o seu próprio bootstrap e esse é o seu método atual de desenvolvimento.

A sintaxe é bastante trivial. Usando a primeira gramática acima de exemplo, teríamos algo assim:

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

Essa é uma forma simples e direta de expressar a gramática. É possível, porém, ter uma gramática tão sofisticada e legível quanto se deseje. Veja a mudança abaixo para descrever exatamente a mesma gramática de maneira um pouco mais legível:

grammar SimpleMath


rule expression 
    term SUM_OP expression / 
    term 
  end

rule term
    factor MUL_OP term / 
    factor
  end

rule factor
    LPARENS expression RPARENS / 
    number
  end

rule number
    [0-9]+
  end

rule SUM_OP 
    '+' / '-'
  end

rule MUL_OP
    '*' / '/'
  end

rule LPARENS
    '('
  end

rule RPARENS
    ')'
  end

end

A diferença é que está possui mais elementos não-terminais--o que não impacta de forma alguma o processamento da mesma--mas impacta talvez seu uso já que elementos que seriam anteriormente inseridos diretamente na árvore como terminais, não gerando sub-expressões, agora o fazem. Veremos mais sobre isso adiante.

Usar a gramática acima, é fácil. Digamos que a gramática tenha sido salva em um arquivo chamado simple_math.rb. Para carregar isso em um programa Ruby, basta usar:

require "treetop"
Treetop.load "simple_math"

O resultado é a disponibilização de um parser chamada SimpleMathParser que reconhece a gramática em questão. Se o arquivo possui a extensão .treetop é possível usar require diretamente:

require "treetop"
require "simple_math"

Para usar o parser, basta instanciá-lo e tentar o parsing de uma expressão qualquer:

>> require "treetop"
=> true
>> require "simple_math"
=> true
>> p = SimpleMathParser.new
=> #
>> p.parse("1+2*3")
=> SyntaxNode+Expression0 offset=0, "1+2*3" (term,expression):
  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"

Note o resultado de um parsing bem sucedido: uma árvore sintática válida que expressa cada elemento da linguagem e o que foi reconhecido em cada ponto da mesma. Note que a árvore possui um detalhamento preciso de cada nó, incluindo terminais e não terminais.

Note que cada nó da árvore sintática é uma instância da classe SyntaxNode anotada com elementos que fornecem uma indicação do que aquele nó representa. Os nomes Expression0 e Term0 representam módulos Ruby que implementam detalhes dos nós sintáticos. Da mesma forma, os nomes entre parênteses (term, expression, etc) são as partes da linguagem reconhecidas dentro daquele nó.

Caso você queira ver o parser como ele realmente foi gerado, basta fazer o seguinte:

~$ tt simple_math.treetop

Um arquivo simple_math.rb será gerado com a implementação do parser em si. O código é bem legível e demonstra como o Treetop faz o reconhecimento descendente e mutuamente excludente dos terminais e não-terminais.

Continuando, vejamos o que acontece em caso de falha:

>> p.parse("1+2*")
=> nil
>> p.failure_reason
=> "Expected ( at line 1, column 5 (byte 5) after *"

Como essa é uma gramática simples, a mensagem pode não ser tão informativa. Mesmo assim, ela fornece uma indicação precisa do que é esperado e fica para o implementador a tarefa de converter isso em mensagens úteis de acordo com o contexto necessário.

Um exercício interessante, que fica para o leitor, é fazer com que a gramática anterior seja capaz de reconhecer espaços.

Conclusão

Até o momento, vimos uma breve introdução teórica e como criar a gramática em si. Ter somente a capacidade de reconhecer uma linguagem, entretanto, não é algo muito útil. Precisamos agora fazer um uso das informações. Para isso, o Treetop oferece duas formas bem convenientes de acessar o que a árvore sintática reconhecida. No próximo artigo, portanto, veremos como fazer esse uso.

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

Tagged: Tecnologia

§ 6 Responses to “Treetop: Básico”

• Caio Ariede says:

  September 25, 2009 at 7:24 pm

  Muito interessante.

  Logo que vi “Treetop” já vim correndo pra ler.

  Não utilizo-o, porém utilizo o Neotoma, que é uma implementação do Treetop para Erlang.

  Espero pelo próximo artigo!

  @caioariede
• Hugo says:

  September 28, 2009 at 12:01 pm

  Legal, isso me lembra a aula de linguagens de programação que tive na faculdade.
  O texto ficou bem explicado e gostei de ver o exemplo do treetop. Eu já conhecia ele mas nunca parei para usá-lo.

  Descrever gramáticas pode dar um bom trabalho

  Me lembrou o professor quando você escreveu “isso fica como exercício para o leitor”
• Thiago Silva says:

  September 28, 2009 at 12:11 pm

  Fala Ronaldão,
  pequenas sugestões/comentários:

  “[...] tanto expressões regulares como CFGs são linguagens formais [...]”

  Eu acho que ficaria melhor dizer que elas geram ou definem linguagens formais. Dizer que expressões regulares e CFGs são linguagens formais, ao meu ver, dá a entender que essas meta linguagens são linguagens formais – acho que não era essa a intenção.

  “Uma característica fundamental de uma PEG é que ela é, por definição, analítica, isto é, ela reconhece texto em uma linguagem e gera uma árvore sintática do que reconheceu [...]”

  Daqui me pareceu que a geração de uma árvore é uma característica fundamental de uma PEG (talvez por ter mencionado o reconhecimento, me pareceu que a geração da árvore seria uma etapa seguinte, ambos fazendo parte do conceito de uma PEG). Também, eu diria que PEGs reconhecem linguagens em um texto (e não o contrário, hehe).

  []‘s
• PotHix says:

  September 28, 2009 at 11:58 pm

  Æ!!

  Como sempre com posts bem legais!

  Só algumas correções de português / digitação:

  “A regra acima que explica a diferença essencial entre uma PEG e uma CFG é que o operador de escolha é ordenado, ist é”

  Seria “isto é”.

  para escolher uma cominho específico.

  Seria “um caminho”

  ambigüidades

  Acho que o trema foi descontinuado nas novas regras do português.

  A árvore final gerada será diferentes mas tem a mesma interpretação

  Seria “diferente”

  Parabens pelo artigo! É sempre bom pensar fora de caixa e ler coisas interessantes!

  Há braços
• Ronaldo says:

  October 1, 2009 at 1:10 pm

  Opa, Caio, obrigado atrasado! Espero que os demais tenha sido interessante.

  Eu cheguei a brincar com o Neotoma mas achei críptico demais até para os padrões do Erlang. A linguagem é interessante mas a sintaxe é dose.

  —

  Obrigado, Hugo. Espero que os demais artigos tenha sido do seu agrado também.

  —

  Opa, Thiago! Obrigado. Corrigidos os erros, eu acho. Veja se estão OK. Como minha teoria vem do que aprendi sem formalizações, minha linguagem é falha.

  —

  Opa, Willian, Obrigado! Sobre os erros corrigidos.

  Quando ao trema, acho que ainda vai demorar para eu me acostumar a tirá-lo da reta…
• Juan Maiz says:

  July 3, 2010 at 11:35 pm

  Pra quem se interessar, fiz um parser mega ultra simples de lógica proposicional com o TT http://github.com/softa/rl

§ Leave a Reply

Click here to cancel reply.

Name (required)

Mail (will not be published) (required)

Website