parsing - 歧义语法和最右导数

Question

歧义语法被定义为，“歧义语法是一种上下文无关的语法，其中存在一个字符串，该字符串可以具有多个最左边的派生或解析树。”

我的疑问是，

1）如果语法有多个最右派生词，这是否会使语法模棱两可？

2）如果语法有多个最右导数，这是否意味着它将有多个最左导数？

并且拥有多个最右导数对 LL(1)、LR(0) 解析器、LR(1) 解析器等的解析能力有任何影响，为什么？

一切都是基于最左导数定义和处理的。这可能是因为我们从左向右移动。但是我们能从最右导数中获得任何见解吗？

Answer 1

左或右的选择完全是任意的。对于给定语法具有多个最左推导的句子也将具有多个最右推导，反之亦然。所以这两种可能的歧义定义是等价的。

如果您考虑推导生成树而不是一系列推导步骤，这可能会更清楚。这两个推导顺序对应于两个不同的遍历树的过程。（两者都是深度优先的，但一个从左到右访问节点，另一个从右到左访问。）如果某个句子（即树的边缘）出现在两个不同的分析树中，则语法是模棱两可的。两棵不同的树对于两个行走过程将具有不同的行走序列，因此可以使用遍历来比较树。（也可以使用此属性进行其他步行程序。）