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

Question

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

第一个不起作用

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

第二个似乎有效

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].[=18= 这样的语法]

Answer 1

我假设 "doesn't work"，你的意思是野牛报告了 shift/reduce 冲突。如果你继续使用生成的解析器，那么在很多情况下它都不会正确解析，因为冲突是真实的并且无法通过任何静态规则解决。

问题很简单。请记住，一个 LALR(1) 自下而上的解析器，如 bison 生成的解析器，恰好在右侧的末尾执行每次归约，只考虑下一个标记（"lookahead token"）。因此它必须知道在作品被完全读取时使用哪个作品。（这给了它比自上而下的解析器更大的自由度，自上而下的解析器需要知道在产生式开始时将使用哪个产生式。但这仍然不够。）

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

如果with规则是右递归的：

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

那么解析器真的卡住了。如果后面有一定的维度，就需要继续尝试第一个产生式，也就是移动[。如果后面没有INDEX，就需要对第二个产生式进行缩减，这会触发一个缩减链，回到维度列表的开头。

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

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

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

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

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

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

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

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

how the order in this recursive rule does not give the same result?

grammar

bison

context-free-grammar