引用
Terence Parr. The Definitive ANTLR Reference, Building Domain Specific Languages(antlr3 version).
前言
[1]为什么有了lex/yacc(flex/bison),为什Parr还要写个ANTLR?
C语言是拿着剃须刀在滑冰,Java是“隐藏”了指针的支持OO的C语言族中相对简单的语言,随着Martin的DSL概念深入人心,不管怎样,还是印证了那句话:模仿是最大的恭维。尽管这对有10+编译器方向工作的Parr来说,这样评价有点不公平。
[2]现在ANTLR已有版本4了,为什么还看版本3的参考指南?
Parr的另一本书《编程语言实现模式》中是用的版本3。
内容
不阐述编译器、DSL方面的概念,纯粹从该书的示例说起。
AntlrWorks工具在后面笔记中记录。
一个带变量的简单算术表达式语言的解释器两种实现方式:
(1)文法(词法、语法)识别器(recognizer)——>在文法中融入动作(action)实现解释器(translator)
(2)构建文法的AST(抽象语法树)中间表示——>编写树文法(tree grammer),遍历AST实现解释器
正文
依赖:antlr-3.5-complete.jar
语言样例:
a=12 b=23 2 + a*b 2 * (a + b)
1 动作驱动的解释器
1.1 文法识别器
//Expr.g,文件名称必须与grammar后名称一致,后缀名为.g
grammar Expr; prog : stat+ ; stat : expr NEWLINE | ID '=' expr NEWLINE | NEWLINE ; expr : multExpr (('+' | '-') multExpr)* ; multExpr : atom ('*' atom)* ; atom : INT | ID | '(' expr ')' ; ID : ('a'..'z'|'A'..'Z')+; INT :('0'..'9')+; NEWLINE : '\r'?'\n'; WS : (' '|'\t'|'\n'|'\r')+ {skip();};
生成parser、lexer和tokens命令
java -classpath antlr-3.5-complete.jar org.antlr.Tool Expr.g
生成文件ExprLexer.java、ExpreParser.java、Expr.tokens
编写识别测试类(test rig)Test
package impatient; import java.io.File; import java.io.FileInputStream; import java.io.InputStream; import org.antlr.runtime.*; public class Test { public static void main(String[] args) throws Exception { InputStream is = new FileInputStream(new File("D:/workspace/maven/antlrv3/language/impatient.test"));//impatient.test中包含语言样例 // create a CharStream that reads from standard input // ANTLRInputStream input = new ANTLRInputStream(System.in); ANTLRInputStream input = new ANTLRInputStream(is); // create a lexer that feeds off of input CharStream ExprLexer lexer = new ExprLexer(input); // create a buffer of tokens pulled from the lexer CommonTokenStream tokens = new CommonTokenStream(lexer); // create a parser that feeds off the tokens buffer ExprParser parser = new ExprParser(tokens); // begin parsing at rule r parser.prog(); } }
1.2 文法+动作
直接在文法中添加动作(java代码,用{}包含),严重影响文法的可读性!
//添加动作后的Expr.g
grammar Expr; @header { import java.util.HashMap; } @members { HashMap memory = new HashMap(); } prog : stat+ ; stat : expr NEWLINE {System.out.println($expr.value);} | ID '=' expr NEWLINE {memory.put($ID.text, new Integer($expr.value));} | NEWLINE ; expr returns [int value] : e=multExpr {$value = $e.value;} ('+' e=multExpr {$value += $e.value;} | '-' e=multExpr {$value -= $e.value;} )* ; multExpr returns [int value] : e=atom {$value = $e.value;} ('*' e=atom {$value *= $e.value;})* ; atom returns [int value] : INT {$value = Integer.parseInt($INT.text);} | ID { Integer v = (Integer) memory.get($ID.text); if(v != null) $value = v.intValue(); else System.err.println("undefined variable " + $ID.text); } | '(' expr ')' {$value = $expr.value;} ; ID : ('a'..'z'|'A'..'Z')+; INT :('0'..'9')+; NEWLINE : '\r'?'\n'; WS : (' '|'\t'|'\n'|'\r')+ {skip();};
重新生成parser、lexer和tokens,仍采用test rig Test运行
2 树文法驱动的解释器
2.1 AST
//生成输出中间表示(IR)的Expr.g
grammar Expr; options { output = AST; ASTLabelType = CommonTree; } prog : (stat {System.out.println($stat.tree.toStringTree());})+ ; stat : expr NEWLINE -> expr | ID '=' expr NEWLINE -> ^('=' ID expr) | NEWLINE -> ; expr returns [int value] : multExpr (('+'^ | '-'^) multExpr)* ; multExpr : atom ('*'^ atom)* ; atom : INT | ID | '('! expr ')'! ; ID : ('a'..'z'|'A'..'Z')+; INT :('0'..'9')+; NEWLINE : '\r'?'\n'; WS : (' '|'\t'|'\n'|'\r')+ {skip();};
两个后缀符号:!不输入AST、^作为AST的子根节点
->符号用于说明生成的AST结构
重新生成parser、lexer和tokens,仍采用test rig Test运行
结果输出AST的一维串行表示
2.2 树文法
//树文法Eval.g,与Expr.g共用tokens
tree grammar Eval; options { tokenVocab=Expr; ASTLabelType=CommonTree; } @header { import java.util.HashMap; } @members { HashMap memory = new HashMap(); } prog : stat+; stat : expr {System.out.println($expr.value);} | ^('=' ID expr) {memory.put($ID.text, new Integer($expr.value));} ; expr returns [int value] : ^('+' a=expr b=expr) {$value = a + b;} | ^('-' a=expr b=expr) {$value = a - b;} | ^('*' a=expr b=expr) {$value = a * b;} | ID { Integer v = (Integer)memory.get($ID.text); if(v!=null) $value = v.intValue(); else System.err.println("undefined variable " + $ID.text); } | INT {$value = Integer.parseInt($INT.text);} ;
生成treeparser命令
java -classpath antlr-3.5-complete.jar org.antlr.Tool Eval.g
生成文件Eval.java、Eval.tokens
AST遍历程程解释器test rig ASTTest
package impatient; import java.io.File; import java.io.FileInputStream; import java.io.InputStream; import org.antlr.runtime.*; import org.antlr.runtime.tree.CommonTree; import org.antlr.runtime.tree.CommonTreeNodeStream; public class ASTTest { public static void main(String[] args) throws Exception { InputStream is = new FileInputStream(new File("D:/workspace/maven/antlrv3/language/impatient.test")); // create a CharStream that reads from standard input // ANTLRInputStream input = new ANTLRInputStream(System.in); ANTLRInputStream input = new ANTLRInputStream(is); // create a lexer that feeds off of input CharStream ExprLexer lexer = new ExprLexer(input); // create a buffer of tokens pulled from the lexer CommonTokenStream tokens = new CommonTokenStream(lexer); // create a parser that feeds off the tokens buffer ExprParser parser = new ExprParser(tokens); // get rule prog return value structure ExprParser.prog_return r = parser.prog(); // WALKING RESULTING TREE CommonTree tree = r.getTree(); // one dimensional tree node stream CommonTreeNodeStream nodes = new CommonTreeNodeStream(tree); // tree parser Eval walker = new eval_r(nodes); walker.prog(); } }
3 遗憾
ANTLR文法也是一种DSL,其语法和标识需要在后面的笔记中记录。