时间戳

首页 > 解决方案 > 这个递归规则中的顺序如何不给出相同的结果？

grammar - 这个递归规则中的顺序如何不给出相同的结果？

问题描述

谁能告诉我以下两条规则有什么区别（注意顺序）？

  1. 第一个不起作用

    without => "[" "]"  without | "[" "]"
with => "[" INDEX "]"  with | "[" INDEX "]"
array => ID with | ID without | ID with without

  2. 第二个似乎有效

    without => without  "[" "]"| "[" "]"
with => with "[" INDEX "]"  | "[" INDEX "]"
array => ID with | ID without | ID with without

我正在尝试实现具有大小的 n-dims 数组的语法，例如 C# 数组。所以下面的语法应该可以工作arr[], arr[1], arr[1][], arr[1][1],arr[][]但不是像arr[][1].

标签： grammarbisoncontext-free-grammar

解决方案

我假设“不起作用”是指野牛报告了移位/减少冲突。如果你继续使用生成的解析器，那么它在很多情况下都无法正确解析，因为冲突是真实存在的，任何静态规则都无法解决。

问题很简单。请记住，像 bison 生成的 LALR(1) 自下而上解析器会在右侧末尾准确执行每个归约，仅考虑下一个标记（“前瞻标记”）。所以它必须知道在产品被完全读取的那一刻使用哪个产品。（这给了它比自上而下的解析器更大的自由度，它需要知道在生产开始时它将使用哪个生产。但这仍然不够。）

有问题的情况是生产ID with without。在这里，任何输入匹配都需要在继续之前with减少为单个非终结符。为了达到这一点，解析器必须已经传递了一些维度，并且前瞻标记必须是，无论下一个维度是否具有确定的大小。withwithout'[' INDEX ']'[

如果with规则是右递归的：

with: '[' INDEX ']' with
    | '[' INDEX ']'

那么解析器就真的卡住了。如果接下来的内容有确定的维度，则需要继续尝试第一个产生式，这意味着将[. 如果后面的没有INDEX，它需要减少第二个生产，这将触发一连串的减少，导致回到维度列表的开头。

另一方面，使用左递归规则：

with: with '[' INDEX ']'
    | '[' INDEX ']'

解析器完全没有问题，因为每一个都with被减少了]。这意味着解析器不必知道接下来的内容就可以决定减少。它根据过去而不是未来在两个规则之间做出决定：第一个维度array使用第二个产生式，其余的（遵循 a with）使用第一个。

这并不是说左递归总是答案，尽管它经常是。从本例中可以看出，列表的右递归意味着单个列表元素堆积在解析器堆栈上，直到列表最终终止，而左递归允许立即进行归约，因此解析器堆栈不会不需要成长。因此，如果您有选择，您通常应该更喜欢左递归。

但有时右递归可能很方便，特别是在这样的语法中，列表的结尾与开头不同。另一种编写语法的方法可能是：

array  : ID dims
dims   : without
       | '[' INDEX ']'
       | '[' INDEX ']' dims
without: '[' ']'
       | '[' ']' without

在这里，由于 的结构，语法只接受列表末尾的空维度dims。但是为了达到这个效果，dims必须是右递归的，因为它是具有扩展语法的列表的末尾。

推荐阅读