引用

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,其语法和标识需要在后面的笔记中记录。
 
05-07 15:17