转载: https://abcdabcd987.com/notes-on-antlr4/
ANTLR4 是一个非常厉害的程序/库,可以用来生成 Lexer 和 Parser,而且生成的接口非常易用。昨天匆匆把 The Definitive ANTLR 4 Reference 扫了一遍,现在把一些常用的东西记下来。
安装
$ cd /usr/local/lib
$ curl -O http://www.antlr.org/download/antlr-4.5-complete.jar
$ vim ~/.zshrc # or vim ~/.bashrc
export CLASSPATH=".:/usr/local/lib/antlr-4.5-complete.jar:$CLASSPATH"
alias antlr4='java -Xmx500M -cp "/usr/local/lib/antlr-4.5-complete.jar:$CLASSPATH" org.antlr.v4.Tool'
alias grun='java org.antlr.v4.runtime.misc.TestRig'
$ . ~/.zshrc # or restart the terminal
语法
最重要的一点是,官方已经提供了非常多的常用的语言的语法文件了,拿来看看可以学到很多,甚至可以删删改改直接拿来用: https://github.com/antlr/grammars-v4
grammar
名称和文件名要一致- Parser 规则(即 non-terminal)以小写字母开始
- Lexer 规则(即 terminal)以大写字母开始
- 所有的 Lexer 规则无论写在哪里都会被重排到 Parser 规则之后
- 所有规则中若有冲突,先出现的规则优先匹配
- 用
'string'
单引号引出字符串 |
用于分隔两个产生式,(a|b)
括号用于指定子产生式,?+*
用法同正则表达式- 在产生式后面
# label
可以给某条产生式命名,在生成的代码中即可根据标签分辨不同产生式 - 不需要指定开始符号
- 规则以分号终结
/* block comment */
以及// line comment
- 默认的左结合,可以用
<assoc=right>
指定右结合 - 可以处理直接的左递归,不能处理间接的左递归
- 如果用
MUL: '*';
指定了某个字符串的名字,在程序里面就能用这个名字了 - 用
fragment
可以给 Lexer 规则中的公共部分命名
例子:
stmt: expr NEWLINE # printExpr
| ID '=' expr NEWLINE # assign
| NEWLINE # blank
;
expr: <assoc=right> expr op='^' expr # pow
| expr op=('*'|'/') expr # mulDiv
| expr op=('+'|'-') expr # addSub
| INT # int
| ID # id
| '(' expr ')' # parens
MUL : '*';
DIV : '/';
ADD : '+';
SUB : '-';
ID : Letter LetterOrDigit*
fragment Letter: [a-zA-Z_]
fragment Digit: [0-9]
fragment LetterOrDigit: Letter | Digit
NEWLINE: '
'? '
'
WS : [ ]+ -> skip
Reference:
- Chapter 4
- 1 Matching an Arithmetic Expression Language
- 2 Building a Calculator Using a Visitor
- Chapter 5
- 4 Dealing with Precedence, Left Recursion, and Associativity
- 5 Recognizing Common Lexical Structures
常见 Lexer 规则
//------ Puncuation
call : ID '(' exprList ')' ;
// or define token labels
call : ID LP exprList RP ;
LP : '(';
RP : ')';
//------ Keywords
returnStmt : 'return' expr ';' ;
//------ Identifiers
ID : ID_LETTER (ID_LETTER | DIGIT)* ;
fragment ID_LETTER : 'a'..'z' | 'A'..'Z' | '_' ;
fragment DIGIT : '0'..'9';
//------ Numbers
INT : DIGIT+ ;
FLOAT : DIGIT+ '.' DIGIT*
| '.' DIGIT+
;
//------ Strings
STRING : '"' (ESC | .)*? '"' ;
fragment ESC : '\' [btnr"\] ; // , ,
, ...
//------ Comments
LINE_COMMENT : '//' .*? '
' -> skip;
BLOCK_COMMENT : '/*' .*? '*/' -> skip;
//------ Whitespace
WS : [
]+ -> skip
Reference:
- Chapter 5
- 5 Recognizing Common Lexical Structures
整合到自己的程序中
ANTLR 4 提供了 Visitor 和 Listener 两种模式,通过这两种模式可以很轻松地把 Parser 的结果做各种处理。ANTLR 4 默认会生成 Listener 模式,如果不需要要加上 -no-listener
,如果要生成 Visitor 模式要加上 -visitor
。
$ antlr4 -visitor Calc.g4
$ ls
Calc.g4 CalcBaseVisitor.java CalcListener.java
Calc.tokens CalcLexer.java CalcParser.java
CalcBaseListener.java CalcLexer.tokens CalcVisitor.java
运行 ANTLR 4 会生成以下文件:
<Grammar>Lexer.java
: Lexer<Grammar>Parser.java
: Parser<Grammar>Listener.java
: Listener 接口<Grammar>BaseListener.java
: Listener 默认实现<Grammar>Visitor.java
: Visitor 接口<Grammar>BaseVisitor.java
: Visitor 默认实现<Grammar>[Lexer].tokens
: 当语法被拆分成多个多个文件时用于同步编号
使用方法就是把 *.java
复制到项目中合适的位置,然后编写调用代码、Visitor及(或)Listener。
调用代码
import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;
import java.io.*;
public class Calc {
public static void main(String[] args) throws IOException {
InputStream is = new FileInputStream("example/1.txt"); // or System.in;
ANTLRInputStream input = new ANTLRInputStream(is);
CalcLexer lexer = new CalcLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
CalcParser parser = new CalcParser(tokens);
ParseTree tree = parser.calc(); // calc is the starting rule
System.out.println("LISP:");
System.out.println(tree.toStringTree(parser));
System.out.println();
System.out.println("Visitor:");
EvalVisitor evalByVisitor = new EvalVisitor();
evalByVisitor.visit(tree);
System.out.println();
System.out.println("Listener:");
ParseTreeWalker walker = new ParseTreeWalker();
Evaluator evalByListener = new Evaluator();
walker.walk(evalByListener, tree);
}
}
可以看到使用方法就是把输入流包装一下喂给 Lexer,之后将 Token 流喂给 Parser,最后调用 ParseTree::<starting>
生成解析树。
解析树可以直接用 .toStringTree
按照 LISP 风格打印出来。
使用 Visitor 模式的话,就是新建 Visitor 对象,之后 visit(tree)
。
使用 Listener 模式的话,需要一个 ParseTreeWalker
和一个 Listener 对象,然后用这个 walker 在树上用这个 Listener 行走。
不论是 Visitor 模式还是 Listener 模式,解决的痛点都是把结构和行为分开,真的十分佩服这些设计模式的创造者。下面简单讲下这两个模式。
Visitor 模式
假设有一个复杂的结构,其中有个基类 B
,以及很多的派生类 Derived1
, Derived2
, …。然后我们现在有一些动作 Action1
, Action2
, …。
用 Visitor 模式的话,首先要在每个基类中指定一个 accept
函数来接受访客,接下来每个派生类重载这个函数,让传进来的访客访问自己。
另外一方面,规定 IVisitor
接口,里面对每个不同类型的派生类 Derived
都有分别的 void visit(Derived obj);
函数。每一个 Visitor 都要实现这个接口。
在对某个派生类对象obj
执行某个动作visitor
时,用 obj.accept(visitor);
。
具体可以看下面这个例子。由基类 Shape
派生出了 Rectangle
和 Circle
。我们分别想要求每种图形的周长和面积,于是编写了 PerimeterVisitor
和 AreaVisitor
两个 Visitor。注意调用的方式,是让派生类接受访问者,再让访问者访问自己。
import java.util.*;
//------ Interfaces
interface IShapeVisitor {
void visit(Rectangle r);
void visit(Circle c);
}
abstract class Shape {
public abstract void accept(IShapeVisitor visitor);
}
//------ Shapes
class Rectangle extends Shape {
public double height;
public double width;
Rectangle(double height, double width) { this.height = height; this.width = width; }
@Override
public void accept(IShapeVisitor visitor) { visitor.visit(this); }
}
class Circle extends Shape {
public double radius;
Circle(double radius) { this.radius = radius; }
@Override
public void accept(IShapeVisitor visitor) { visitor.visit(this); }
}
//------ Visitors
class PerimeterVisitor implements IShapeVisitor {
@Override
public void visit(Rectangle r) {
System.out.println((r.height + r.width) * 2);
}
@Override
public void visit(Circle c) {
System.out.println(2 * Math.PI * c.radius);
}
}
class AreaVisitor implements IShapeVisitor {
@Override
public void visit(Rectangle r) {
System.out.println(r.height * r.width);
}
@Override
public void visit(Circle c) {
System.out.println(Math.PI * Math.pow(c.radius, 2.));
}