Adaptive LL(*) 语法分析算法

  1. ANTLR 4 自动将类似 expr 的左递归规则重写成非左递归形式
  2. ANTLR 4 提供优秀的错误报告功能和复杂的错误恢复机制
  3. ANTLR 4 使用了一种名为 Adaptive LL(∗) 的新技术
  4. ANTLR 4 几乎能处理任何文法 (二义性文法✓ 间接左递归✗)

ANTLR 4如何处理直接左递归与优先级

08-01

我们在运行antlr4 LRExpr -Xlog后将会得到

08-02

我们将上述代码对应于一段递归函数 expr(int _p)

1
2
3
4
5
6
7
8
expr(int _p)
		: ( INT
		  | ID
		  )
		  ( {4 >= $_p}? '*' expr[5]
		  | {3 >= $_p}? '*' expr[4]
		  ) 
		;

Example

1 + 2 * 3

08-03

根本问题

究竟是在 expr 的当前调用中匹配下一个运算符,

还是让 expr 的调用者匹配下一个运算符。

再来看一个左结合与右结合的例子

08-04

08-05

Example:

-a + b!

08-06

幂运算的例子

08-07

Example:

1 ^ 2 ^ 3 + 4

08-08

总结

For left-associative operators, the right operand gets one more precedence level than the operator itself.

–对于左结合的运算符来说，右操作数比运算符本身的优先级高一个级别。

For right-associative operators, the right operand gets the same precedence level as the current operand.

–对于右结合的运算符来说，右操作数和当前操作数具有相同的优先级。

ANTLR 4的错误报告与恢复

08-09

LexerNoViableAltException

遇到未知字符, 出现词法错误

08-10

InputMismatchException

输入流中的当前词法单元与当前规则所期望的词法单元不匹配

08-11

NoViableAltException

剩余输入不符合当前规则的任何一个备选分支

08-12

自定义错误报告消息

08-13

恐慌/应急 (Panic) 模式**😗* 假装成功、调整状态、继续进行

四项基本原则：

  1. 特殊情况, 特殊处理

  2. 一般情况, 统一处理

  3. 统一处理, 精细控制

  4. 自定义错误处理策略

特殊情况， 特殊处理

如果下一个词法单元符合预期，则采用 “单词法符号移除 (single-token deletion)”

或 “单词法符号补全 (single-token insertion)” 策略

单词法符号移除

08-14

单词法符号补全

08-15

一般情况, 统一处理

采用 “同步-返回 (sync-and-return)” 策略,使用 “重新同步集合(resynchronization set)” 从当前规则中恢复

08-16

统一处理, 精细控制

如何从子规则中优雅地恢复出来

08-17

自定义错误处理策略

比如, (已知语法正确) 关闭默认错误处理功能, 提高运行效率

比如, (出错代价太大) 在遇到第一个语法错误时, 就停止分析

The Power of Danamic Analysis

$$
P = \lbrace S \rightarrow A c \mid Ad, , A \rightarrow aA \mid b \rbrace
$$

不是LL(1)文法，也不是LL(k)文法（$\forall k \geqslant 1$）

08-18

Incrementally and dynamically build up a lookahead DFA

that map lookahead phrases to predicated productions.

–逐步动态地构建一个向前搜索DFA，将向前搜索短语映射到条件产生式。

08-19

08-20

Move on terminals and Closure over $\epsilon$ and non-terminals