21 abril, 2016 0 Comentários AUTOR: elemarjr CATEGORIAS: Compiladores, CSharp, Java, Programação Tags:

Aprendendo ANTLR4 - Parte 1 - Um breve overview

Tempo de leitura: 6 minutos

Para mim, algumas das atividades mais bacanas da computação são a definição de novas linguagens, bem como a escrita de programas que interpretam código nessas linguagens e produzem alguma saída.

Há diversas ferramentas disponíveis no mercado que apoiam a execução dessas atividades. Dentre elas, uma das mais populares é ANTLR.

Recentemente, resolvi aprender como utilizar adequadamente ANTLR4 (a quarta geração da ANTLR). Para isso, estou lendo o excelente The Definitive ANTLR 4 Reference de Terence Parr.

Nessa série compartilho minhas notas de estudo. O código fonte dos exemplos está disponível no Github.

O que é ANTLR?

Citando o site oficial:

ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files. It's widely used to build languages, tools, and frameworks. From a grammar, ANTLR generates a parser that can build and walk parse trees.

Em outras palavras, usamos ANTLR para gerar parsers - programas que validam se um código está em conformidade com a definição de uma linguagem e oferecem uma estrutura de dados representando este código.

A definição de uma linguagem, em ANTLR, é feita a partir de sua gramática. Ele usa essa gramática para gerar código-fonte regular (em Java, C# ou outra linguagem target suportada) de um parser.

Obtendo o ANTLR4

ANTLR4 é escrito em Java e é multiplataforma. Para usar ANTLR você precisa ter Java instalado em seu computador. Para instalar ANTLR em seu sistema operacional, siga as indicações disponíveis no site oficial.

Um exemplo de gramática

Para que possamos avançar de forma consistente, vamos examinar um exemplo simples de gramática (exemplo extraído do livro The Definitive ANTLR 4 Reference):

grammar LabeledExpr;

prog: stat+;

stat:   expr NEWLINE            # printExpr
    |   ID '=' expr NEWLINE     # assign
    |   NEWLINE                 # blank
    ;
    
expr:   expr op=('*'|'/') expr  # MulDiv
    |   expr op=('+'|'-') expr  # AddSub
    |   INT                     # int 
    |   ID                      # id
    |   '(' expr ')'            # parens
    ;
    
MUL:    '*';
DIV:    '/';
ADD:    '+';
SUB:    '-';

ID:         [a-zA-Z]+;
INT:        [0-9]+;
NEWLINE:    '\r'? '\n';
WS:         [ \t]+ -> skip;

Essa gramática, LabeledExpr, define linguagem para equações matemáticas simples. Como toda gramática, ela é composta por algumas regras.

Segundo a definição nessa gramática:

  • Um programa (prog) é composto por um ou mais statements (stat)
  • Um statement pode ser uma expressão matemática ou uma atribuição de variável.
  • Uma expressão (expr) pode ser uma multiplicação/divisão, adição/subtração, um número, um ID ou uma expressão entre parênteses.
  • expr é uma definição recursiva.

Se você está habituado a escrever gramáticas perceberá que ANTLR é uma ferramenta bastante permissiva (principalmente com recursão a esquerda). Se ainda não está habituado a escrita de gramáticas, tente "pegar a ideia". Nos próximox posts, tudo ficará mais simples.

Compilando a gramática (Java)

Antes de podermos usar nossa gramática, esta precisa passar por um processo de conversão para Java seguido de compilação do código resultante:

antlr LabeledExpr.g4
javac LabeledExpr*.java

A primeira instrução converte a definição da gramática em código fonte Java. A segunda linha compila o código Java para fazer com que nossa gramática seja "executável".

Mesmo que você seja um desenvolvedor .NET, recomendo que utilize Java enquanto estiver aprendendo ANTLR.

Testando a gramática

Para que possamos fazer algum teste, precisamos de um código fonte compatível com a definição de nossa gramática. Abaixo, compartilho um pequeno exemplo (salvo em meu exemplo em t.expr):

42
a=4
b=5
a+b*2
2+2/2
(2+2)/2

ANTLR fornece uma ferramenta para que possamos testar nossa gramática. Vejamos as opções que ela oferece:

%> grun /?
java org.antlr.v4.gui.TestRig GrammarName startRuleName
  [-tokens] [-tree] [-gui] [-ps file.ps] [-encoding encodingname]
  [-trace] [-diagnostics] [-SLL]
  [input-filename(s)]
Use startRuleName='tokens' if GrammarName is a lexer grammar.
Omitting input-filename makes rig read from stdin.

Seguindo o que está definido nessa ajuda:

grun LabeledExpr prog -gui t.expr

Que resulta em:

antlr1

Perfeito! Temos uma AST.

Visitando a árvore sintática (Java)

Já temos uma árvore sintática, agora podemos escrever algum código que a explore. ANTLR consegue gerar um Visitor adequado para nossa gramática.

antlr LabeledExpr.g4 -no-listener -visitor

Essa instrução faz com que ANTLR gere uma interface (LabeledExprVisitor):

import org.antlr.v4.runtime.tree.ParseTreeVisitor;
public interface LabeledExprVisitor<T> extends ParseTreeVisitor<T> {
    T visitProg(LabeledExprParser.ProgContext ctx);
    T visitPrintExpr(LabeledExprParser.PrintExprContext ctx);
    T visitAssign(LabeledExprParser.AssignContext ctx);
    T visitBlank(LabeledExprParser.BlankContext ctx);
    T visitParens(LabeledExprParser.ParensContext ctx);
    T visitMulDiv(LabeledExprParser.MulDivContext ctx);
    T visitAddSub(LabeledExprParser.AddSubContext ctx);
    T visitId(LabeledExprParser.IdContext ctx);
    T visitInt(LabeledExprParser.IntContext ctx);
}

Também gera uma implementação abstrata:

import org.antlr.v4.runtime.tree.AbstractParseTreeVisitor;

public class LabeledExprBaseVisitor<T> extends AbstractParseTreeVisitor<T> implements LabeledExprVisitor<T> {
	@Override public T visitProg(LabeledExprParser.ProgContext ctx) { return visitChildren(ctx); }
	@Override public T visitPrintExpr(LabeledExprParser.PrintExprContext ctx) { return visitChildren(ctx); }
	@Override public T visitAssign(LabeledExprParser.AssignContext ctx) { return visitChildren(ctx); }
	@Override public T visitBlank(LabeledExprParser.BlankContext ctx) { return visitChildren(ctx); }
	@Override public T visitParens(LabeledExprParser.ParensContext ctx) { return visitChildren(ctx); }
	@Override public T visitMulDiv(LabeledExprParser.MulDivContext ctx) { return visitChildren(ctx); }
	@Override public T visitAddSub(LabeledExprParser.AddSubContext ctx) { return visitChildren(ctx); }
	@Override public T visitId(LabeledExprParser.IdContext ctx) { return visitChildren(ctx); }
	@Override public T visitInt(LabeledExprParser.IntContext ctx) { return visitChildren(ctx); }
}

Vamos escrever nossa implementação:

import java.util.HashMap;
import java.util.Map;

public class EvalVisitor extends LabeledExprBaseVisitor<Double> {
    Map<String, Double> memory = new HashMap<String, Double>();
    
    @Override
    public Double visitAssign(LabeledExprParser.AssignContext ctx) {
        String id = ctx.ID().getText();
        double value = visit(ctx.expr());
        memory.put(id, value);
        return value;
    }
    
    @Override
    public Double visitPrintExpr(LabeledExprParser.PrintExprContext ctx) {
        Double value = visit(ctx.expr());
        System.out.println(value); 
        return 0.; 
    }
    
    @Override
    public Double visitInt(LabeledExprParser.IntContext ctx) {
        return Double.valueOf(ctx.INT().getText());
    }
    
    @Override
    public Double visitId(LabeledExprParser.IdContext ctx) {
        String id = ctx.ID().getText();
        if ( memory.containsKey(id) ) return memory.get(id);
        return 0.;
    }
    
    @Override
    public Double visitMulDiv(LabeledExprParser.MulDivContext ctx) {
        double left = visit(ctx.expr(0));
        double right = visit(ctx.expr(1)); 
        if ( ctx.op.getType() == LabeledExprParser.MUL ) return left * right;
        return left / right; 
    }

    @Override
    public Double visitAddSub(LabeledExprParser.AddSubContext ctx) {
        double left = visit(ctx.expr(0));
        double right = visit(ctx.expr(1)); 
        if ( ctx.op.getType() == LabeledExprParser.ADD ) return left + right;
        return left - right;
    }
    
    @Override
    public Double visitParens(LabeledExprParser.ParensContext ctx) {
        return visit(ctx.expr());
    }
}

Essa implementação tem a capacidade de interpretar e executar as expressões contidas em um fonte.

Agora, vamos escrever um pequeno programa que aproveita esse Visitor:

import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;
import java.io.FileInputStream;
import java.io.InputStream;

public class Calc {
    public static void main(String[] args) throws Exception {
        InputStream is = (args.length == 0) 
            ?  System.in
            : new FileInputStream(args[0]);
        
        ANTLRInputStream input = new ANTLRInputStream(is);
        LabeledExprLexer lexer = new LabeledExprLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        LabeledExprParser parser = new LabeledExprParser(tokens);
        
        ParseTree tree = parser.prog();
        
        EvalVisitor eval = new EvalVisitor();
        eval.visit(tree);
    }
}

Nada incrível aqui. Basicamente, esperamos por um arquivo ou por uma cadeia de caracteres encerrada por ^Z. E seguida, submetemos essa cadeia de caracteres para o parser e processamos a AST resultante usando o Visitor.

Visitando a árvore sintática (C#)

Vamos repetir a implementação anterior, agora com C#.

Começamos criando uma nova aplicação console. Por enquanto, a versão mais atualizada do .NET framework que podemos utilizar é a 4.51.

Projeto criado, adicionamos referência para o pacote Nuget ANTLR4.

Install-Package ANTLR4

Adicionamos o arquivo com a definição da gramática ao projeto, observando para que a codificação do arquivo seja Codepage 1252.

Em seguida, precisamos fazer uma pequena modificação no arquivo de projeto (.csproj) para indicar que queremos que a gramática seja processada pelo ANTLR.

<ItemGroup>
  <Antlr4 Include="LabeledExpr.g4">
    <Generator>MSBuild:Compile</Generator>
    <CustomToolNamespace>Calc</CustomToolNamespace>
    <Listener>True</Listener>
    <Visitor>True</Visitor>
  </Antlr4>
</ItemGroup>

Pronto!

Agora, basta adicionar código. Comecemos pelo parser:

using System;
using System.Collections.Generic;

namespace Calc
{
    class EvalVisitor : LabeledExprBaseVisitor<double>
    {
        readonly Dictionary<string, double> _memory = 
            new Dictionary<string, double>();

        public override double VisitAssign(LabeledExprParser.AssignContext context)
        {
            var id = context.ID().GetText();
            var value = Visit(context.expr());
            _memory[id] = value;
            return value;
        }

        public override double VisitPrintExpr(LabeledExprParser.PrintExprContext context)
        {
            var value = Visit(context.expr());
            Console.WriteLine(value);
            return 0;
        }

        public override double VisitInt(LabeledExprParser.IntContext context)
        {
            return double.Parse(context.INT().GetText());
        }

        public override double VisitId(LabeledExprParser.IdContext context)
        {
            var id = context.ID().GetText();
            return _memory.ContainsKey(id) 
                ? _memory[id] 
                : 0;
        }

        public override double VisitMulDiv(LabeledExprParser.MulDivContext context)
        {
            var left = Visit(context.expr(0));
            var right = Visit(context.expr(1));
            return context.op.Type == LabeledExprParser.MUL 
                ? left*right 
                : left/right;
        }

        public override double VisitAddSub(LabeledExprParser.AddSubContext context)
        {
            var left = Visit(context.expr(0));
            var right = Visit(context.expr(1));
            return context.op.Type == LabeledExprParser.ADD
                ? left + right
                : left - right;
        }

        public override double VisitParens(LabeledExprParser.ParensContext context)
        {
            return Visit(context.expr());
        }
    }
}

Finalmente, programa que orquestra o processo:

using System.IO;
using Antlr4.Runtime;

namespace Calc
{
    class Program
    {
        static void Main(string[] args)
        {
            string inputFile = null;
            if (args.Length > 0) inputFile = args[0];
            var istream = System.Console.In;
            if (inputFile != null) istream = File.OpenText(inputFile);

            var input = new AntlrInputStream(istream);
            var lexer = new LabeledExprLexer(input);
            var tokens = new CommonTokenStream(lexer);
            var parser = new LabeledExprParser(tokens);
            var tree = parser.prog();

            var eval = new EvalVisitor();
            eval.Visit(tree);
        }
    }
}

Perceba como o código em C# é semelhante ao código que escrevemos para Java

Concluindo

ANTLR é uma ferramenta fantástica. ANTLR4 simplifica consideravelmente a definição de linguagens pois permite uma escrita "frouxa" de gramáticas e gera parsers bem eficientes.

A adoção do pattern visitor oferece uma abstração bem acessível para o processamento da AST.

Era isso.

Enviar um comentário