Python lrparsing 模块；无法解析简单递归语法。

Question

expr = Ref('expr')
block = '{' + Repeat(expr) + '}'
expr = block | Token(re='[0-9]')
START = expr

这是一个使用Python的lrparsing模块的语法。该模块报告没有语法冲突。

它无法解析字符串{{0}}，并显示错误：lrparsing.ParseError: line 1 column 5: Got '}' when expecting __end_of_input__ while trying to match block in state 11 堆栈状态逐步如下：

shift  '{'; ItemSet:5='{'
shift  '{'; ItemSet:5='{' ItemSet:5='{'
shift  /[0-9]/; ItemSet:4=/[0-9]/ ItemSet:5='{' ItemSet:5='{'
reduce '}'; ItemSet:4=/[0-9]/ -- ItemSet:7=expr ItemSet:5='{' ItemSet:5='{'
reduce '}'; ItemSet:7=expr -- ItemSet:9=expr ItemSet:5='{' ItemSet:5='{'
shift  '}'; ItemSet:11='}' ItemSet:9=expr ItemSet:5='{' ItemSet:5='{'

据我所知，这意味着它正在转移{{0，然后在看到}时将0减少到expr，然后再次在}上进行减少而没有先移动它，这让我感到困惑。

这是一个错误吗？还是我做了一些非常简单和愚蠢的事情？

如果这是我的语法问题，我该如何重构它，以满足我永恒的渴望？如果这是一个 Bug，有人能指导我使用与 lrparsing 最相似的语法的 python 模块吗？

编辑：

blocks = Ref('blocks')
block = Ref('block')
expr = Ref('expr')
blocks = blocks + block | THIS*0 # THIS*0 is the idiomatic way of getting the empty string
block = '{' + expr + '}'
expr = blocks | Token(re='[0-9]')
START = expr

允许正确解析。现在我的问题是...为什么？我觉得lrparsing之前应该会提醒我任何解析问题...难道Repeat的工作方式不符合我的期望吗？

- user

Answer 1

我是Lrparsing的作者。正如Serge所说，这是一个错误，在1.0.8版本中已经修复。这种情况只发生在Serge在Source Forge的错误跟踪器上报告了此问题后——否则我就不会知道。谢谢你，Serge。

关于Repeat()可能存在错误的评论表明他们不理解lrparsing的作用。Lrparsing是一个相当复杂的工具。它允许您以希望Python程序员自然的方式输入语法。然后，它将编译为LR(1)解析器生成器可以理解的内容，即一系列产生式。然后，它从这些产生式生成一个LR(1)解析表。最后，它将您的输入语言和解析表提供给LR(1)解析器来生成解析树。值得一提的是，该错误出现在生成解析表的部分。

对于我来说，要调试这样一系列转换几乎是不可能的，如果我看不到每个步骤产生的结果的话。因此，lrparsing有一个repr_xxxx()函数，用于显示每个步骤的输出。第一个转换是解析您的语法。结果由repr_grammar()显示：

<G> = START + __end_of_input__
START = expr
block = '{' + expr * () + '}'
expr = block | /[0-9]/

这看起来与问题中呈现的原始语法非常相似。下一步是把这些规则编译成产生式，这是LR(1)解析器生成器可以理解的内容。通过 repr_productions() 打印这些产生式：

<G> = START __end_of_input__
START = expr
block = '{' '}'
block = '{' block.Sequence.Repeat '}'
block.Sequence.Repeat = expr
block.Sequence.Repeat = block.Sequence.Repeat expr
expr = block
expr = /[0-9]/

block.Sequence.Repeat是lrparsing引入的新非终端，用于处理Repeat()。对我来说，这些产生式看起来像是原始语法的忠实表现。

Lrparsing竭尽全力隐藏它引入的非终结符，如block.Sequence.Repeat。例如，它们不会出现在输出解析树中。这意味着除了两种情况外，lrparsing用户不需要关心它们。这两种情况是错误恢复和尝试理解解析引擎的日志输出。前者是大多数人不会尝试的复杂技术。但是，一些人在此处查看了后者，以试图了解lrparsing正在做什么。如果您无法看到LR(1)解析器尝试识别的产生式，日志将毫无意义。但是，如果您已经看到了它们，就会知道Repeat()中没有错误。

您还可以转储生成的LR(1)解析表。如果您真的想了解LR(1)解析器如何工作，那么您应该尝试理解它。除非您碰巧发现解析是一个深刻有趣的话题，否则我不建议您这样做。

- Russell Stuart

Answer 2

当我遇到这个页面时，我已经向lrparsing的作者报告了您的问题——这确实是一个bug，并且已经在1.0.8版本中修复。如果将来有用的话，可以在这里找到lrparsing的bug跟踪器。

- Serge Monkewitz

---

感谢您报告这个错误，与我这个愚蠢的自己不同。+1 - user

Answer 3

lrparsing存在一个错误；它没有正确考虑递归重复。您的实际问题可以通过简单的递归解决，就像您在扩展编辑中所做的那样，尽管稍微清理一下即可。

block = Ref('block')
block = '{' + block + '}' | Token(re='[0-9]')
START = block

请注意，您原来的语法允许输入例如{{0{1}}}。 （原因是可重复部分可以扩展为简单数字或expr）。 考虑到您的第二个语法，您可能并不想要那样的结果。

我已经使用pyparsing完成了一些工作，但语法差别很大。 类比的例子：

from pyparsing import Forward, Literal, nums, oneOf, Word

l = lambda c: Literal(c).suppress()
block = Forward()
block << (Word(nums, exact=1) ^ l('{') + block + l('}'))
print(block.parseString("{{0}}"))

输出：

['0']

希望这有所帮助。

- mknecht

---

@Atash：发现了一个漏洞。你的语法并不含糊，首先expr 需要扩展为block，然后Repeat 需要被扩展。没有歧义。尽管如此，pyparsing存在一个错误，因为它没有正确地处理递归重复。我会根据这个修改答案。（希望这样做是正确的。随意取消答案标记。）对此感到抱歉。 - mknecht

谢谢您纠正答案！所以，我将删除答案标记...然后再把它放回去，因为答案是正确的。对吧？ :-P - user