segunda-feira, 16 de agosto de 2010

Diversão com ANTLR

ANTLR – Another Tool for Language Recognition – é uma ferramenta para construção de analisadores léxico (lexer) e sintático (parser) de linguagens formais para JVM.

A grosso modo, é uma ferramenta para implementação de linguagens de programação.

E ANTLRWorks é um IDE gráfico para ANTLR.

Para entender como funciona ANTLR, vou explicar o exemplo do próprio sítio. Então instale o ANTLRWorks e mãos à obra!

Avaliador de expressões


Quando iniciar o ANTLRWorks, crie uma gramática chamada Expr.g.

O código já vai aparecer com a seguinte linha:
grammar Expr;


A ideia aqui é criar um interpretador que avalie expressões matemáticas simples, inclusive com variáveis.

Para suportar variáveis, precisamos de algum lugar para armazenar seus valores. Para isso usamos Java:
@header {
import java.util.Map;
import java.util.HashMap;
}

@members {
Map<String, Integer> memory = new HashMap<String, Integer>();
}


Isso criará o contentor memory, que é um mapa de chaves string e valores inteiros.

ANTLR funciona definindo regras. Nossa primeira regra é programa (prog) e precisamos defini-la:
prog:   stat+;


Então nosso programa é um grupo (+) de comandos (stat), o que nos leva à próxima regra.

Definimos comando como:
stat:   expr NEWLINE { System.out.println($expr.value); }
| ID '=' expr NEWLINE
{ memory.put($ID.text, new Integer($expr.value)); }
| NEWLINE
;


Calma, vou explicar!

Um comando pode ser uma expressão (expr) seguida de uma mudança de linha (NEWLINE). Neste caso, será impresso na saída padrão (System.out) o valor da expressão ($expr.value);

Um comando também pode ser (| significa OU) um identificador (ID) seguido de um sinal de igual ('='), uma expressão e uma mudança de linha. Neste caso o valor da expressão ($expr.value) será armazenado no contentor memory na chave igual ao texto do identificador ($ID.text).

Um comando ainda pode ser uma mudança de linha, que não fará nada.

Agora precisamos definir uma série de regras: expr, NEWLINE e ID. Vamos começar por expr:
expr returns [int value]
: e=multExpr { $value = $e.value; }
( '+' e=multExpr { $value += $e.value; }
| '-' e=multExpr { $value -= $e.value; }
)*
;


Quer dizer que expr retorna um valor inteiro (int value) e consiste de uma expressão múltipla (multExpr) seguido de nenhuma, uma ou mais repetições (*) do que estiver entre parêntesis. O valor retornado é igual ao valor da expressão múltipla.

A atribuição e= é necessária por haver mais de uma ocorrência de multExpr.

Entre parêntesis tempos o sinal de adição ('+') seguido de uma multExpr ou (|) um sinal de subtração ('-') seguido de uma multExpr. No primeiro caso o valor da multExpr é adicionado ao valor retornado, no segundo é subtraído.

A regra multExpr é definida como:
multExpr returns [int value]
: e=atom { $value = $e.value; } ('*' e=atom { $value *= $e.value; })*
;


Uma multExpr retorna um valor inteiro e consiste de um ou mais atómicos (atom). Os valores dos atómicos são multiplicados.

Definindo um atómico:
atom returns [int value]
: INT { $value = Integer.parseInt($INT.text); }
| ID
{
Integer v = memory.get($ID.text);
if (v != null) $value = v.intValue();
else System.err.println("undefined variable " + $ID.text);
}
| '(' expr ')' { $value = $expr.value; }
;


Então um atómico pode ser um inteiro (INT, o valor é o corpo do inteiro: $INT.text), um identificador (ID, o valor é o relacionado à chave no contentor memory – se não existir, gera um erro) ou o resultado de uma expressão (expr), que deve estar entre parêntesis.

Falta definir as regras ID, INT e NEWLINE:
ID  :   ('a'..'z'|'A'..'Z')+;
INT : '0'..'9'+;
NEWLINE: '\r'? '\n';


Ou seja: identificador é uma sequência de letras, inteiro uma sequência de números e mudança de linha é CRLF ou LF.

Para finalizar, para ignorar espaços em branco:
WS  :   (' '|'\t')+ { skip(); };


Testando


Para testar, clique em Debug e preencha a caixa Text com:
x = 1
y = 2
3 * (x + y)


Os parêntesis e a mudança de linha na última linha são importantíssimos!

Clique Ok e divirta-se acompanhando o debugger! Repare que, ao final da execução, vai mostrar 9 na aba Output.

[]’s
Cacilhας, La Batalema
blog comments powered by Disqus