编译原理08-parser-allstar

Adaptive LL(*) 语法分析算法

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

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

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

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

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

Example

1 + 2 * 3

根本问题

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

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

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

Example:

-a + b!

幂运算的例子

Example:

1 ^ 2 ^ 3 + 4

总结

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的错误报告与恢复

LexerNoViableAltException

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

InputMismatchException

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

NoViableAltException

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

自定义错误报告消息

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

四项基本原则：

1. 特殊情况, 特殊处理
2. 一般情况, 统一处理
3. 统一处理, 精细控制
4. 自定义错误处理策略

特殊情况， 特殊处理

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

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

单词法符号移除

单词法符号补全

一般情况, 统一处理

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

统一处理, 精细控制

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

自定义错误处理策略

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

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

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$）

Incrementally and dynamically build up a lookahead DFA

that map lookahead phrases to predicated productions.

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

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