parsec.py 递归定义

Question

我喜欢这个库的简单性。可悲的是我还没有弄清楚如何进行递归定义：

考虑这个最小的人为示例：

import parsec as psc
digit = psc.regex("[0-9]")
number = lambda: digit ^ (digit + number())
_ = number().parse("42")

不出所料，number() 的计算是无限递归的：

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

我知道在这个具体例子中可以通过将第 3 行更改为

来解决

number = lambda: psc.many1(digit)

但我不确定在一般情况下是否总是可行。

是否可以像

那样递归解析数字

<number> ::= <digit><number> | <digit>

Answer 1

（更新）免责声明： 正如我们在评论中发现的那样，这仅适用于 parsec.py 以上的版本3.3，（截至 2018 年 8 月）是 PyPI 上可用的最新版本，因此现在您必须手动安装来自 GitHub 的开发版本才能实现此解决方案。

更新 2： parsec.py v3.4 终于发布并修复了问题。

在这种情况下，我发现 "manually expand" parsec 提供的原语并编写我们自己的 "low-level" 解析器（即采用 "manually expand" 的解析器通常很有帮助 text 和 index 参数，而不是从 parsec 基元构建的参数），只是为了看看发生了什么。通过从 parsec 源代码中获取 try_choice (^) 的定义并手动插入表达式 ¹ 的组成部分，我们可以编写一个解析器，我想做你想做的事：

import parsec as psc
digit = psc.regex("[0-9]")

def number():
  @psc.Parser
  def number_parser(text, index):
    res = (digit + number())(text, index)
    return res if res.status else digit(text, index)
  return number_parser

_ = number().parse("42423")
print(_)

输出：

('4', ('2', ('4', ('2', '3'))))

之所以有效，当然是因为 "parser-returning function" number() 仅在实际解析器中有条件地被调用，而不是（无条件地）在其自身中被调用。

一个更简单的写法是根本不使用 "parser-returning function" 而是直接写解析器本身：

@psc.Parser
def number(text, index):
  return ((digit + number) ^ digit)(text, index)

用法从 number().parse("42423") 更改为 number.parse("42423")，但作用相同。

最后，parsec.py 中是否有一些功能可以让您在没有显式 text 和 index 参数的情况下执行此操作，这样解析器就完全由其他 parsec.py 原语？结果是 parsec.generate fits the bill rather nicely! From its in-source documentation:

The most powerful way to construct a parser is to use the generate decorator. The generate creates a parser from a generator that should yield parsers. These parsers are applied successively and their results are sent back to the generator using .send() protocol. The generator should return the result or another parser, which is equivalent to applying it and returning its result.

您可以找到示例用法 here，从中可以清楚地看出我们可以写：

@psc.generate
def number():
  r = yield (digit + number) ^ digit
  return r

这是有效的，因为除了它所做的所有花哨的生成器魔法之外，generate 装饰器 returns 一个本身用 @parsec.Parser 装饰的函数（参见上面链接的源代码），所以得到的完全修饰的 number 函数将与第二种解决方案中的函数相同。因此，我们可以以与 digit 等相同的方式使用它，而不必调用它或其他任何东西，这就是我们在 yield 表达式中所做的。

用法又是 number.parse("42423") 并且 returns 与其他两个解决方案相同。

也许有更好的解决方案，但这就是我所能想到的。

_{¹ 我不得不将顺序从 digit ^ (digit + number()) 颠倒到 (digit + number()) ^ digit，因为第一个 returns 只是第一个数字然后认为自己完成了。希望没问题吧？}

Answer 2

如果已经有很多 parser-returning 函数或者只是想在风格上保持一致，另一种快速解决这个问题的方法是使函数惰性求值：

import parsec as psc

def lazy(fn):
  @psc.Parser
  def _lazy(text, index):
    return fn()(text, index)
  return _lazy

digit = lambda: psc.regex("[0-9]")
number = lambda: (digit() + lazy(number)) ^ digit()
print(number().parse("423242"))

打印：

('4', ('2', ('3', ('2', ('4', '2')))))

parsec.py 递归定义

parsec.py recursive definitions

python

recursion

parsec