4.1 语法分析——ANTLR 4 语法分析器

call graphs

**目标：**利用语法分析功能来构建程序的函数调用图

---

对于 Cymbol 语言

一个程序是由变量声明或函数声明来组成的

block 由 stat 组成，stat 又可以由 block 组成，这样表达是嵌套，即在大括号中可以嵌套大括号

---

二义性文法

二义性文法：对于一个语法如果一个表达式可以有两种解释方式，即有歧义，是不可以的

如上述语法，对于 if a then if b then c else d

• 可以把 if b then c else 整体作为 stat，适用第一条规则；

• 也可以把 if b then c 作为 stat，适用第二条规则。

• 【即 else 到底属于哪个 if 的问题】

没有算法可以判定语法是否有二义性，一般靠经验对一些特定结构的语法来判断，并针对性的消除二义性

对于上面的二义性语法通过下面的改变来消除二义性，让 else 与最近的 if 匹配

但是 Antlr 不需要上面的改写就可以消除二义性【即我们不需要改写，只需要写原来的具有二义性的语法，Antlr 会帮我们消除二义性】，它的策略是：如果规则有多条可能性，那么在进行语法分析时会按照规则的书写顺序从上往下进行匹配，当上面的匹配不了才会采用下面的进行匹配。

【因此书写时一定要注意书写顺序，顺序就是匹配的优先级】

例如在上面的二义性规则中，优先匹配第一条规则就能解决二义性。

表达式文法的二义性

结合性：对于 1-2-3 可以是 (1-2)-3 也可以是 1-(2-3)

优先级：对于 1-2*3 可以是 1-(2*3) 也可以是 (1-2)*3

上面的规则是 expr 是左右递归，即 * 的左右都有 expr

可以改写成左递归和右递归的形式来实现优先级

但改写会导致简单的表达式很复杂，如下：同时注意右递归会导致运算符是右结合

对于 Antlr，可以直接处理，不需要改写，同样将书写顺序来作为优先级。并且如果不做特殊标记，默认是左结合的，如果要右结合，只需要加上一个标记告诉 Antlr 即可，如下：

对于一元运算符，不需要标记即为右结合，因为类似上面的右递归，对于一元运算法只能按照右结合进行语法树构建，没有其他的构建方式，如下：

---

Left-Factoring

有些算法没法处理有相同的左公因子的规则，因此必须要提取出来，表示成右边的样式。

但是显然，Antlr 可以处理有相同的左公因子的规则，不需要我们自己提取

---

Listener

Antlr 会为每一条规则生成监听器【enterXXX, exitXXX】，我们可以实现这个监听器【因为要完成自动构建函数调用图的功能，需要实现 enterXXX，当到达该节点的时候就执行；如果实现 exitXXX，一般是当前节点的信息依赖于子节点的信息时，才会在访问完子节点后才执行当前节点的函数】

监听器功能：在深度遍历语法树时【enter和exit分别在到达和离开这个节点时监听】，如果是该监听器监听的类型，那么会执行监听器中的功能。

在规则后面加上 #name 即可让 Antlr 遇到这个规则时生成粒度更细的 name 类型，而不是粗粒度的 expr。如果 expr 中的一个加上了 #，那么其他的 expr 中的其他规则也都要加上 #

对于同一个规则里面用 | 分隔的两个运算，使用 # 也无法区分，因此再加上 op=，这样在这条规则对应的树节点上面有一个成员 op，根据这个来区分，如下

calculator

目标：实现一个小计算器

要记录的信息即计算结果，需要在运算符节点记录叶子节点的计算结果，因此依赖于叶子节点，所以需要实现 exitXXX

因为 exitXXX 方法都是返回值为 0 的，所以无法记录状态，可以考虑使用全局变量，但是不好。事实上，Antlr 提供了一个 map<ParseTree, T> ParseTreeProperty<T> 来给每个节点记录信息

如下将 INT 节点的值放到了 map 中

这样比如在计算取反操作的时候，右下角的整数值是已经知道了的，并存在 map 中，所以当回到父节点时也即执行 exitXXX 时就可以直接使用这个存入的整数值

对于 +/- 操作因为的 g4 中标明了 lhs,rhs,op 所以它们是 ctx 的成员

理论部分

如果没有指定开始符号，那么第一条规则是开始符号

g4 中用的是 [E]BNF，即加入了 *+? 这类语法糖

所有的推导都是句型，当推导到只有终结符时是句子

文法定义的语言就是它能推导出的所有句子的集合

第一个问题决定了我们怎么去设计构建语法分析树的算法

L(G) 是什么？

简单的例子：

上下文无关文法表达能力更强

因为 m > k，所以肯定会有相同的状态 S_i 出现

假设在第一次碰到 S_i 时输入的是 aⁱ，那么在输入 a^m 时，在 i~m 之间的 j 会重新回到 S_i 。而根据定义，在输入 aⁱ 后输入 bⁱ 会到达终止状态，即被接受，那么输入 a^i+jbⁱ 也能到达终止状态，这与定义矛盾

这是所谓的泵引理，同理下面的语言是上下文无关文法也无法表达的