ANTLR

ANother Tool for Language Recognitionwww.antlr.org

Jobson Ronan (jrjs)Renato Viana (rvf)

Motivação

Parsers criados com YACC tendem a ter baixa qualidade de mensagens de erro

Erros em gramáticas do YACC são difíceis de entender. YACC informa um erro de "shift/reduce" ou "reduce/reduce" associado a uma dada regra da gramática

Possibilidade de gerar Parsers para várias linguagens (C++, Java, C# e Python)

Open-source

Características

ANTLR gera recursive decent parsers e possui uma boa reportagem de erros.

Parsers gerados pelo ANTLR são razoavelmente legíveis. Facilitando a depuração

Possui boa documentação e grande quantidade de exemplos Apesar disso, a curva de aprendizagem ainda é grande.

Aprendendo por exemplo

Exp: Linguagem de expressões aritméticas Suporta soma, subtração e multiplicação de inteiros Suporta parêntesis para definir prioridades

Ex: 2+3 1 5*(3+7)

Gramática

Todas as gramáticas do ANTLR são subclasses de Lexer, Parser, or TreeParser As regras são específicadas em uma notação

EBNFclass ExprParser extends Parser;

expr: mexpr ((PLUS|MINUS) mexpr)* ;

mexpr : atom (STAR atom)* ;

atom: INT | LPAREN expr RPAREN ;

Lexerclass ExprLexer extends Lexer;

options { k=2; // needed for newline junk charVocabulary='\u0000'..'\u007F'; // allow ascii}

LPAREN: '(' ;RPAREN: ')' ;PLUS : '+' ;MINUS : '-' ;STAR : '*' ;INT : ('0'..'9')+ ;WS : ( ' ' | '\r' '\n' | '\n' | '\t' ) {$setType(Token.SKIP);} ;

Gerando

Executar ferramenta de geração$ java antlr.Tool expr.g

ResultadoExprLexer.java

ExprParser.java

ExprParserTokenTypes.java

Testando

Executar o parserimport antlr.*;public class Main { public static void main(String[] args) throws Exception { ExprLexer lexer = new ExprLexer(System.in); ExprParser parser = new ExprParser(lexer); parser.expr(); }}

Avaliando Expressões

Avaliando expressões on-the-flyclass ExprParser extends Parser;

expr returns [int value=0]{int x;} : value=mexpr ( PLUS x=mexpr {value += x;} | MINUS x=mexpr {value -= x;} )* ;

mexpr returns [int value=0]{int x;} : value=atom ( STAR x=atom {value *= x;} )* ;

atom returns [int value=0] : i:INT {value=Integer.parseInt(i.getText());} | LPAREN value=expr RPAREN ;

Testando

Alterações no método expr()import antlr.*;

public class Main { public static void main(String[] args) throws Exception { ExprLexer lexer = new ExprLexer(System.in); ExprParser parser = new ExprParser(lexer); int x = parser.expr(); System.out.println(x); }}

Problemas

Mistura de interesses Código de definição da gramática Código de definição das ações Código da linguagem alvo (Java)

Solução Gerar uma AST

Gerando ASTs

Pequenas alterações na definição da gramática Indica-se açucares sintáticos Indica-se nomes dos nós

Define-se um TreeParser

Alterações na gramática

“^” Índica as raízes das sub-arvores “!” Índica os açucares sintáticos

class ExprParser extends Parser;

options { buildAST=true;}

expr: mexpr ((PLUS^|MINUS^) mexpr)* ;

mexpr : atom (STAR^ atom)* ;

atom: INT | LPAREN! expr RPAREN! ;

Definindo TreeParser

class ExprTreeParser extends TreeParser;

options { importVocab=ExprParser;}

expr returns [int r=0]{ int a,b; } : #(PLUS a=expr b=expr) {r = a+b;} | #(MINUS a=expr b=expr) {r = a-b;} | #(STAR a=expr b=expr) {r = a*b;} | i:INT {r = (int)Integer.parseInt(i.getText());} ;

Testando

import antlr.*;import antlr.collections.*;

public class Main { public static void main(String[] args) throws Exception { ExprLexer lexer = new ExprLexer(System.in); ExprParser parser = new ExprParser(lexer); parser.expr(); AST t = parser.getAST(); System.out.println(t.toStringTree()); ExprTreeParser treeParser = new ExprTreeParser(); int x = treeParser.expr(t); System.out.println(x); } }

Exercícios

1. Adicionar a linguagem de expressões o comando print

print(4+3*6) 2. Adicionar a linguagem de expressões

suporte a varáveisv1 = 3+5print(v1+10)

*Não tente fazer os dois ao mesmo tempo

ANTLR

ANother Tool for Language Recognitionwww.antlr.org

Jobson Ronan (jrjs)Renato Viana (rvf)