antlr深入探索

本文结合案例分析antlr解析的原理

前言

之前文章antlr介绍已经通过案例了解了antlr的大致实现过程,那么究竟是使用了什么原理才能这么精准快速的将字符串转化成语法树的呢

词法解析

这个就比较简单了,假如有一组输入a = b + 1,那么词法解析的功能就是降这些字符拆解开来,a,=,b,+,1,再和声明的语法匹配分类,比如1就是int类别。

语法解析

将词法分析后的结果构成语法树,语法解析常见的两个策略LL和LR

  • LL
    LL中第一个L的意思是从左往右解析字符串,也就是和我们平时阅读的方向一致;第二个L的意思是从最左端开始衍生。整个解析的流程是自顶向下的。

  • LR
    LR的R表示从最右端开始衍生。整个解析流程是自底向上的。

举个例子来感受一下LL和LR的去区别,有这么一个语法规则:

1
2
3
4
s: a ;
a: (b '+' a) | b;
b: B ;
B: [0-9] ;

然后给一组输入数据

1
1+2+3

如果是LL解析,解析顺序是自顶向下,先父后子的

1
2
3
4
5
6
7
8
9
s
a
b + a
1 + a // match 1
1 + b + a
1 + 2 + a // match 2
1 + 2 + b
1 + 2 + 3 // match 3
// success

而LR的解析顺序如下,可以看到是自底往上解析

1
2
3
4
5
6
7
8
9
10
b  // match 1
b + 2
b + b // match 2
b + b + 3
b + b + b // match 3
b + b + a // match a
b + a // match a
a // match a
s // match s
// success

可以很明显的看到两者的区别,LL更符合我们正常思维方式,最后这个例子构建出的语法树如下

1
2
3
4
5
6
7
8
9
10
11
   s
|
a
/ | \
b + a
| / | \
1 b + a
| |
2 b
|
3

通过语法树,我们再回顾一下LL和LR的区别;LL是对树的一次先序遍历,而LR是对树的一次后序遍历

参考资源

对antlr写的很棒的博客
对LL分析很深刻的博客
《The Definitive ANTLR 4 Reference》

ulysses wechat
订阅+