Antlr4初体验

学习记录
,

0x00：介绍

Antlr 4 是一个强大的语法分析器生成工具，可以用来读取、处理、执行和转换结构化文本或二进制文件。通过称为文法的形式化语言描述，ANTLR可以为该语言自动生成词法分析器。生成的语法分析器可以自动构建语法分析树，它是表示文法如何匹配输入的数据结构。ANTLR还可以自动生成树遍历器，用来访问树节点以执行特定的代码。

0x01: why this？

我一直觉得编译原理相关的东西（理论也好，工具也好）可以和漏洞挖掘发生奇妙的化学反应。和9k师傅聊过相关的东西，有类似想法的人很多。甚至github上六年前的一个项目，使用flex+bison去生成文件来做fuzz。

和flex+bison比较，antlr4无疑是更容易上手，也更加强大的，当然用哪个就是仁者见仁智者见智了。

在深入学习这些东西之后，对domato的思想有了更深刻的理解。其实就是词法分析那套，自顶向下的。不得不说，真的很棒，而且应用范围很广泛，但是效果怎么样我就不知道了，还在摸索。

0x02： 关于本文

《Antlr4权威指南》中8.4章节练习的学习记录。这部分的例子是一个语法检查器，针对Cymbol语言的。

比如下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f(int x, float y) {
    g();   // forward reference is ok
    i = 3; // no declaration for i (error)
    g = 4; // g is not variable (error)
    return x + y; // x, y are defined, so no problem
}

void g() {
    int x = 0;
    float y;
    y = 9; // y is defined
    f();   // backward reference is ok
    z();   // no such function (error)
    y();   // y is not function (error)
    x = f; // f is not a variable (error)
}

经过该语法检查器，可以将一些语法错误找出来，比如未定义的符号、类型引用错误(函数当变量，变量当函数)。

0x03: 例子

1. 语法分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/** Simple statically-typed programming language with functions and variables
 *  taken from "Language Implementation Patterns" book.
 */
grammar Cymbol;

file:   (functionDecl | varDecl)+ ;

varDecl
    :   type ID ('=' expr)? ';'
    ;
type:   'float' | 'int' | 'void' ; // user-defined types

functionDecl
    :   type ID '(' formalParameters? ')' block // "void f(int x) {...}"
    ;

formalParameters
    :   formalParameter (',' formalParameter)*
    ;
formalParameter
    :   type ID
    ;

block:  '{' stat* '}' ;   // possibly empty statement block

stat:   block
    |   varDecl
    |   'if' expr 'then' stat ('else' stat)?
    |   'return' expr? ';' 
    |   expr '=' expr ';' // assignment
    |   expr ';'          // func call
    ;

/* expr below becomes the following non-left recursive rule:
expr[int _p]
    :   ( '-' expr[6]
        | '!' expr[5]
        | ID
        | INT
        | '(' expr ')'
        )
        ( {8 >= $_p}? '*' expr[9]
        | {7 >= $_p}? ('+'|'-') expr[8]
        | {4 >= $_p}? '==' expr[5]
        | {10 >= $_p}? '[' expr ']'
        | {9 >= $_p}? '(' exprList? ')'
        )*
    ;
*/

expr:   ID '(' exprList? ')'    # Call
    |   expr '[' expr ']'       # Index
    |   '-' expr                # Negate
    |   '!' expr                # Not
    |   expr '*' expr           # Mult
    |   expr ('+'|'-') expr     # AddSub
    |   expr '==' expr          # Equal
    |   ID                      # Var
    |   INT                     # Int
    |   '(' expr ')'            # Parens
    ;

exprList : expr (',' expr)* ;   // arg list

K_FLOAT : 'float';
K_INT   : 'int';
K_VOID  : 'void';
ID  :   LETTER (LETTER | [0-9])* ;
fragment
LETTER : [a-zA-Z] ;

INT :   [0-9]+ ;

WS  :   [ \t\n\r]+ -> skip ;

SL_COMMENT
    :   '//' .*? '\n' -> skip
    ;

2. 符号表

这部分是精髓，作者直接拿了自己另一本书里的代码来用，代码不长也好懂。这里我只列一部分比较重要的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public abstract class BaseScope implements Scope {
    Scope enclosingScope; // 临近的作用区，如果当前是全局作用域，应该置null
                          // 因为作用域查找是往前找的，全局已经是最靠前了
    Map<String, Symbol> symbols = new LinkedHashMap<String, Symbol>();

    public BaseScope(Scope enclosingScope) { this.enclosingScope = enclosingScope;  }

    public Symbol resolve(String name) {
        Symbol s = symbols.get(name);
        if ( s!=null ) return s;//在当前作用域找到了，直接返回
        //如果临近作用域不空，那么就去临近作用域找
        //比如，一个函数内，符号定义没找到，就去往上（全局）找
        if ( enclosingScope != null ) return enclosingScope.resolve(name);
        //还找不到，那就是未定义，报错
        return null; // not found
    }

    public void define(Symbol sym) {
        symbols.put(sym.name, sym);
        sym.scope = this; // track the scope in each symbol
    }

    public Scope getEnclosingScope() { return enclosingScope; }

    public String toString() { return getScopeName()+":"+symbols.keySet().toString(); }
}
3. 如何检查

因为目标语言Cymbol允许向前引用，比如：

1
2
3
4
5
6
7
8

int f(){
    g();
}

void g(){
    ;
}

所以需要两次遍历，第一次找到所有定义，并放入符号表，将符号表构造好。
接下来进行第二次遍历，这时遇到一个引用，就去找符号表，找到了就是正常，找不到就是有问题。

4. 代码

主要是两个文件，DefPhase.java和RefPhase.java。

1. Defphase

关键的问题：在第一次遍历构造符号表的时候，遇到新的作用域，需要把新的作用域的父作用域设置为当前作用域，并且把新的作用域设置为当前作用域。

对于遇到的变量定义直接使用对应的构造符号表的对象去构造就好了。

2. RefPhase

遍历检查每个引用部分，去符号表里查找，找不到就报错。这部分比较简单。

3. checkSymbol
1
2
3
4
5
6
7
8
9
10
11
parser.setBuildParseTree(true);
ParseTree tree = parser.file();
// show tree in text form
//System.out.println(tree.toStringTree(parser));

ParseTreeWalker walker = new ParseTreeWalker();
DefPhase def = new DefPhase();
walker.walk(def, tree);
// create next phase and feed symbol table info from def to ref phase
RefPhase ref = new RefPhase(def.globals, def.scopes);
walker.walk(ref, tree);
5. 结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# muhe @ muheMacBookPro in ~/Study/antlr_study/chapter_8_4 [16:03:46]
$ antlr4 Cymbol.g4

# muhe @ muheMacBookPro in ~/Study/antlr_study/chapter_8_4 [16:03:49]
$ javac Cymbol*.java CheckSymbols.java *Phase.java *Scope.java *Symbol.java -Xlint:deprecation
CheckSymbols.java:9: 警告: [deprecation] org.antlr.v4.runtime中的ANTLRInputStream已过时
import org.antlr.v4.runtime.ANTLRInputStream;
                           ^
CheckSymbols.java:40: 警告: [deprecation] org.antlr.v4.runtime中的ANTLRInputStream已过时
        ANTLRInputStream input = new ANTLRInputStream(is);
        ^
CheckSymbols.java:40: 警告: [deprecation] org.antlr.v4.runtime中的ANTLRInputStream已过时
        ANTLRInputStream input = new ANTLRInputStream(is);
                                     ^
3 个警告

# muhe @ muheMacBookPro in ~/Study/antlr_study/chapter_8_4 [16:03:56]
$ java CheckSymbols vars.cymbol
locals:[]
function<f:tINT>:[<x:tINT>, <y:tFLOAT>]
locals:[x, y]
function<g:tVOID>:[]
globals:[f, g]
line 3:4 no such variable: i
line 4:4 g is not a variable
line 13:4 no such function: z
line 14:4 y is not a function
line 15:8 f is not a variable

0x04： 引用

《antlr4权威指南》