python - 一个解析项多次出现导致的无限递归 YACC-PLY

Question

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

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

注意:问题类似于:Python PLY zero or more occurrences of a parsing item但是那里提出的解决方案不起作用，我总是有无限递归。

Answer 1

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

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

• 序列中的零个或多个属性(相当于类似正则表达式的“x*”)
• 一个或多个按顺序排列的属性(等同于类似正则表达式的“x+”)
• 零个或一个属性，但仅此而已(相当于类似正则表达式的“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

作为一般规则，当使用右递归时，解析器最终不得不“转移”(插入其解析堆栈)更多标记。最终，解析器遇到一个不符合规则的标记(在本例中，不是 STRING 或 NUMBER)，然后它可以开始使用右递归规则，从右到左处理 STRING-and-NUMBER。使用左递归，它可以更早地进行归约，从左到右工作。看 http://www.gnu.org/software/bison/manual/html_node/Algorithm.html#Algorithm了解更多。