![](https://csdnimg.cn/release/download_crawler_static/85245721/bg6.jpg)
Xtext 使用一个适合于交互式编辑的解析器算法,因为它能更好处理错误恢
复。不幸的是,这个解析器算法没有处理左递归规则。当规则的第一个符号
(symbol)是非终端(non-terminal)的并且引用了规则自身,则规则是递归
的。上述添加的规则确实是递归的,所以被 Xtext 拒绝。请注意,一个规则也
可以通过多个规则调用来保持左递归,而不需要任何令牌。
Xtext 生成一个 ANTLR 解析器(见 Parr 2007),其依赖于 LL(*)算法,
我们不会详细讨论解析算法;感兴趣的读者,可以参考“aho 等人 2007”的书。
这个解析器,在调试和错误恢复方面有很好的优势(在 IDE 中为程序员提供更
好的反馈至关重要)。不过这个解析器不能处理左递归语法。
好消息是我们可以解决这个问题。坏消息是我们必须使用左因素分解转换,
通过删除左递归来修改语法。
ANTLR 生成的解析器不能处理左递归,因为它依赖于自上而下的策略。自下
而上的解析器就没有这个问题,但他们会要求处理运算符优先级(它决定哪些子
表达式应该在给定的表达式中先计算)和关联性(确定在没有括号的情况下,相
同优先级的运算符如何分组)。我们将在本节中看到,左因素分解将允许我们隐
含地定义运算符优先级和关联性。
我们使用标准技术删除左递归:我们为表达式引入一个 atomic 规则,我们
指出,加法由一个左部分组成,这是一个原子表达式;和一个可选的右部分,它
是递归的表达式(请注意,右递归并不会影响 ANTLR 解析器):
Expression:
{Plus} left=Atomic ('+' right=Expression)?;
Atomic returns Expression:
{IntConstant} value=INT |
{StringConstant} value=STRING |
{BoolConstant} value=('true'|'false') |
{VariableRef} variable=[Variable];
请记住,规则的名称是 Atomic,但是由此创建的 AST 中的对象规则,将用
IntConstant、StringConstant 等类型替代(实际上,不会从前面的规则生成
Atomic 类)。静态地,这些对象将被认为是表达式类型,因此 Plus 类中的左
和右字段,将是 Expression 的类型。
前面的解决方案仍然有一个主要的缺点,那就是会在 AST 中创建额外的、