3.5.5 确定性自顶向下和自底向上方法

只有一种确定性自顶向下方法,它叫做LL。第一个L代表从左至右(Lift-to-Right),第二个是“确定最左侧生成”(identifying the Leftmost production),就像定向自顶向下分析器一样。LL解析在第8章中进行讲解。LL解析,尤其是LL(1)非常受欢迎。LL(1)解析器通常是由一个解析器生成器生成的,但是一个简版的可以通过手工费点劲写出来,通过递归减少技术;见8.2.6节。偶尔将LL(1)方法从输入的最后一个标记开始,这时就叫做RR(1)

有很多的确定性自底向上方法,最强大的叫做LR,其中L也是值从左至右(Lift-to-Right),R代表“确定最右侧的生成”(identifyingthe Rightmost production)。线性自底向上方法将会在第9章讲到。他们的解析器只能是由一个解析器生成器生成的:这样一个解析器的控制机制太过复杂以至于人工是无法完成的。部分确定性自底向上方式非常的受欢迎,甚至可能比LL(1)方式更广泛的使用。

LR(1)解析比LL(1)解析更强大,但也更难以理解和不那么方便。其他方法无法随便同LL(1)相比。17.1节有实用解析方式之间的对比。LR(1)解析也能从输入最后端开始,此时被称作RL(1)

这两种技术都使用了前瞻性来确定下面的行动。通常这种前瞻性会被一个标记的限定(LL(1),LR(1)等),或者至多少数的几个标记的限定,但偶尔不受限的前瞻能带来很大帮助。这需要其他的解析技术,而这会带来确定性解析器的细化分类,见图3.11。

自顶向下和自底向上方法的差异很大,当我们细看不同分析器的选择时就很容易理解了。自顶向下解析器本质上没有什么选择:如果一个终结符已经被预测,那就没有别的选择而只能从存在的匹配中确定;只有当一个非终结符被预测到了,它才有一个选择那个非终结符的选择。一个自底向上解析器移向下一个输入符号,即便是缩减的也是可以的(并且也必须这样做)。此外,如果可能存在缩减,它还可能会选择在右侧的一组中进行选择。总的来说,它比自顶向下解析器有更多的选择,所以需要更强大的技术来确定它。

results matching ""

    No results matching ""