【Antlr】Antlr 处理优先级、左递归、结合性

1.概述

出自 Antlr权威指南

在自顶向下的语法和手工编写的递归下降语法分析器中，处理表达式都是一件相当棘手的事情，这首先是因为大多数语法都存在歧义，其次是因为大多数语言的规范使用了一种特殊的递归方式，称为左递归 (left recursion)。

我们稍后会详细讨论它，现在请记住点，自顶向下的语法和语法分析器的经典形式无法处理左递归。为了阐明这个问题，假设有一种简单的算术表达式语言，它包含乘法和加法运算符，以及整数因子。表达式是自相似的，所以，很自然地，我们说，一个乘法表达式是由*连接的两个子表达式，一个加法表达式是由+连接的两个子表达式。

另外单个整数也可以作为简单的表达式。

这样写出的就是下列看上去非常合理的规则：

问题在于，对于某些输入文本而言，上面的规则存在歧义。换句话说，这条规则可以用不止一种方式匹配某种输入的字符流，正如2.3节中所描述的那样。这个语法在简单的整数表达式和单运算符表达式上工作得很好．例如1+2和1*2 是因为只存在一种方式去匹配它们。对于1+2，上述语法只能用第二个备选分支去匹配，如图5-2左侧的语法分析树所示。