4

我写一个 GLR 是为了好玩（同样，因为自从我上次尝试以来我理解了一些事情）。解析器现在正在工作，我正在实施消歧规则。我正在以一种似乎有效的方式处理优先级。现在我对关联性有点不知所措。

假设我有这样的语法：

E <- E '+' E (rule 1)
E <- E '-' E (rule 2)
E <- '0'     (rule 3)
E <- '1'     (rule 4)

其中规则 1) 和 2) 具有相同的优先级和左结合性。

如果没有关联性处理，字符串 '1-1+0' 将生成两个解析树：

   1                2
  / \              / \
 /   \            /   \
2     3          4     1
|  \                   | \
4   4                  4  3

其中数字表示用于减少的规则。正确的解析树是第一个，因此我只想保留这个。

我想知道如何通过算法有效地检测关联性侵犯。

我尝试的一种方法是查看在第一棵树的顶部节点处，规则 2 是规则 1 子列表中规则 3 的左侧，而在第二棵树中，规则 1 是规则 4 的右侧，因此由于规则2 和 1 是左关联的我只保留第一棵树。

然而，在更复杂的例子中，这并没有让我走得太远。此解决方案的一个限制是我只能根据与另一棵树的比较来丢弃树。

您认为我可以使用这种方法的改进版本找到解决方案吗？标准的做法是什么？

4

2 回答 2

0

要在算法上执行此操作，我将分为两组：包含规则 3 和 4 的 SIMPLE 和包含规则 1 和 2 的 COMPLEX。如果（COMPLEX）（子）根的最右边的孩子是 COMPLEX，则删除这棵树，因为它是（部分) 右结合。

于 2012-09-01T21:42:22.683 回答
0

在我看来，这最好通过整合到语法规则中来表达，彻底解决歧义：

E <- F
E <- E '+' F
E <- E '-' F
F <- '0'
F <- '1'

当您设置为 (G)LR 时，应该可以同样好地表达左关联性和右关联性。由于单位推导，解析树深度的增加可以通过适当的后处理来解决。

这将完全避免发明一种新机制，并利用无论如何使用的 BNF 的表现力。我认为它需要强有力的论据来支持模棱两可的符号，以及如何解决的单独规范。

XQuery 语言规范在其定义过程中，从使用带有额外消歧规则的模糊 EBNF（参见2002 年 4 月 30 日草案）演变为放弃后者，转而使用包含优先级和关联性的明确规则（参见2002 年 8 月 16 日草案）。作为一名实施者，我非常感谢 - 它让我的生活更轻松。

于 2012-08-08T19:29:24.777 回答