3

我正在处理一个 Yacc（层层），我不知道如何在不使程序由于无限递归而崩溃的情况下使解析项出现更多次。假设我有：

def p_Attribute(p):
    ''' Attribute : STRING
                  | NUMBER 
                  | Attribute
                  | empty '''
[do stuff]

注意： 问题类似于：Python PLY 零次或多次出现解析项，但提出的解决方案不起作用，我总是有无限递归。

4

1 回答 1

2

这里的问题实际上出在你的语法上。类似 Yacc 的解析器不适用于这种规则，因为它需要减少一个属性来减少一个属性，因此是无限递归。（编辑添加注释：如果右手Attribute需要一些非空的非模棱两可的标记，例如，是可解析的并且允许在其他可接受的 s 前面有Attribute : STRING | NUMBER | '$' Attribute | empty任意数量的符号，那将是可以的。但事实上，两种选择,和, 可以完全为空。这是一个减少/减少冲突，它在这里解决得不好。我认为如果你把空规则放在第一位，减少/减少冲突可能会“按需要”解决——但这仍然是“错误的方式”一般来说，这样做。）$AttributeAttributeempty

大概你想要三件事之一（但我不确定是哪一个，所以想象一下解析器生成器的混乱:-)）：

  • 序列中的零个或多个属性（相当于 regexp-like "x*"）
  • 一个或多个按顺序排列的属性（相当于 regexp-like "x+"）
  • 零个或一个属性，但没有更多（相当于 regexp-like "x?"）

对于所有这三个，您通常应该首先定义一个非终端，该非终端可以准确识别一个有效的类似属性的事物，例如：

Exactly_One_Attribute : STRING | NUMBER

（我将在Attribute下面拼写）。

然后，您定义一个规则，该规则接受您打算允许的序列（或可选属性）。例如：

Zero_Or_More_Attributes : Zero_Or_More_Attributes Attribute | empty

（这使用“左递归”，这应该是最有效的。使用右递归——见下文——只有当你真的想以其他顺序识别项目时。）

至少需要一个属性：

One_Or_More_Attributes: One_Or_More_Attributes Attribute | Attribute

（在本例中也是左递归），或者：

Attribute_opt : empty | Attribute

它允许“无”（空）或仅允许一个属性。

右递归版本很简单：

Zero_Or_More_Attributes : Attribute Zero_Or_More_Attributes | empty

作为一般规则，当使用右递归时，解析器最终不得不“移动”（推入其解析堆栈）更多标记。最终，解析器遇到一个不符合规则的标记（在这种情况下，不是 aSTRING或NUMBER），然后它可以开始使用右递归规则减少每个移位的标记，从右到左处理STRING-and- 。NUMBER使用左递归，它可以更早地进行归约，从左到右工作。有关更多信息，请参见 http://www.gnu.org/software/bison/manual/html_node/Algorithm.html#Algorithm。

于 2013-08-02T10:29:35.013 回答