pyparsing 部分匹配或递归限制命中

Question

使用 pyparsing，我似乎无法理解为什么我的语法部分匹配或达到递归限制。

lparens = Suppress("(")
rparens = Suppress(")")
name = Word(alphanums, exact=1)
expression = Forward()
function = Group(Literal("λ") + OneOrMore(name) + Literal(".").suppress() + expression)
application = Group(expression + expression) #<-- the problem *I think*
exp1 = ( name | function | application )
exp2 = (lparens + exp1 + rparens) | exp1
expression << exp2

因此以下将解析但仅提取 "a" 并且不应用应用程序步骤：

expression.parseString("ab") #result is: (['a'], {})
expression.parseString("(ab)") #result is: exception - recursion limit reached.

在第一个示例中，为什么它在 'a' 处停止并且没有将应用步骤和运行应用到与第二个示例中相同的无限外观中？

在第二个例子中它匹配'('所以它需要')'来完成exp1。所以它应该解析名称 'a' 并且因为没有后面的 ')' 它应该放弃它并尝试函数（失败）然后继续应用程序。然后它解析 name 'a'（第一个匹配项）并且应该继续到 name 'b' 完成名称、应用程序，然后匹配 ')' 以完成 exp1 和表达式。

显然情况并非如此。

编辑：忘记添加以下作品：

expression.parseString("((λa.a)(λa.a))")

` #result: ([([(['λ', 'a', 'a'], {}), (['λ', 'a', 'a'], {})], {})], {})

将 setDebug() 和 setName() 添加到各种元素并解析 '(ab)' 产生：

Match expression at loc 0(1,1)
Match exp2 at loc 0(1,1)
Match lparens at loc 0(1,1)
Matched lparens -> []
Match exp1 at loc 1(1,2)
Match name at loc 1(1,2)
Matched name -> ['a']
Matched exp1 -> ['a']
Match rparens at loc 2(1,3)
Exception raised:Expected ")" (at char 2), (line:1, col:3)
Match name at loc 0(1,1)
Exception raised:Expected name (at char 0), (line:1, col:1)
Match function at loc 0(1,1)
Exception raised:Expected "λ" (at char 0), (line:1, col:1)
Match application at loc 0(1,1)
Match expression at loc 0(1,1)
Match exp2 at loc 0(1,1)
Match lparens at loc 0(1,1)
Matched lparens -> []
Match exp1 at loc 1(1,2)
Match name at loc 1(1,2)
Matched name -> ['a']
Matched exp1 -> ['a']
Match rparens at loc 2(1,3)
Exception raised:Expected ")" (at char 2), (line:1, col:3)
Match name at loc 0(1,1)
Exception raised:Expected name (at char 0), (line:1, col:1)
Match function at loc 0(1,1)
Exception raised:Expected "λ" (at char 0), (line:1, col:1)
Match application at loc 0(1,1)
Match expression at loc 0(1,1)
Match exp2 at loc 0(1,1)
Match lparens at loc 0(1,1)
Matched lparens -> []
Match exp1 at loc 1(1,2)
Match name at loc 1(1,2)
... etc etc etc...

Answer 1

我很难回答你的问题，因为我并没有真正理解你试图解析的内容。幸运的是，函数定义中的 lambda 字符足以作为提示，我搜索了一些有关 lambda 演算符号的背景知识，并在此处找到了一个不错的描述：http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html

由此我想到了一个简单的 BNF：

expr ::= (name | function | '(' expr ')')+
function ::= 'λ' name+ '.' expr
name ::= a single character 'a'..'z' or 'A'..'Z'

从这里翻译成 pyparsing 看起来像：

lparens = Suppress("(")
rparens = Suppress(")")
dot = Suppress('.')
# work around output encoding issues by displaying as '^'
λ = Literal('λ').setParseAction(replaceWith('^'))

# Forward() placeholder for recursive expression
expression = Forward()

# implement BNF bottom-up
name = oneOf(list(alphas))
function = Group(λ + Group(OneOrMore(name))("head") + dot + expression("body"))
lambda_term = name | function | lparens + expression + rparens
expression <<= Group(OneOrMore(lambda_term))

这会将您的示例表达式解析为：

((λa.a)(λa.a))
[[[[['^', ['a'], ['a']]], [['^', ['a'], ['a']]]]]]

这似乎有很多额外的嵌套需要处理。我们可以通过稍微调整 expression 来减少其中的一些，仅当有 2 个或更多表达式时才进行分组，否则解析单个未分组的表达式。元组乘法功能让我们将其定义为：

expression <<= Group(lambda_term*(2,)) | lambda_term

给予：

[[['^', ['a'], 'a'], ['^', ['a'], 'a']]]

或者更明确地说：

[
    [
        ['^', ['a'], 'a'], 
        ['^', ['a'], 'a']
    ]
]

在你发布的解析器中，你也有一个"application"的概念。我推测您所说的应用程序就是引用的傻瓜文章所指的 "resolving"。要解析一个函数，您需要将后续表达式与函数头中的每个名称一一对应，并将函数体中的名称替换为其各自的表达式。我试图在解析时理解这一点，但在函数嵌套在其他函数中的表达式中挣扎，或者头部和主体定义在嵌套的括号中，替换表达式通过几个嵌套级别与函数分开。我得出的结论是必须在名称和函数解析完成后进行解析。 pyparsing 赋予结果的结构应该使遍历结果并用表达式连续解析名称变得简单。

完整的解析器代码如下：

"""
(from http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html)

BNF:
  expr ::= (name | function | '(' expr ')')+
  name ::= ['a'..'z' 'A'..'Z']+
  function ::= lambda name+ '.' expr
"""

lparens = Suppress("(")
rparens = Suppress(")")
dot = Suppress('.')
# work around output encoding issues by displaying as '^'
λ = Literal('λ').setParseAction(replaceWith('^'))

# Forward() placeholder for recursive expression
expression = Forward()

# implement BNF bottom-up
name = oneOf(list(alphas))
function = Group(λ + Group(OneOrMore(name))("head") + dot + expression("body"))
lambda_term = name | function | lparens + expression + rparens
#~ expression <<= Group(OneOrMore(lambda_term))
expression <<= Group(lambda_term*(2,)) | lambda_term


tests = """\
    ((λa.a)(λa.a))
    (λy.xy) ab
    λx.λy.xzy
""".splitlines()
for t in tests:
    t = t.strip()
    print(t.replace('λ','^'))
    expression.parseString(t, parseAll=True).pprint()
    print()

Answer 2

为了理解为什么您的语法无法完成工作，您首先必须了解 pyparsing 的工作原理。您似乎相信 pyparsing 会探索所有可能的路径，直到找到正确表示 entire 输入字符串的路径。这是不正确的。请参阅以下示例：

exp1 = ( name | function | application )
exp1.parseString("ab") # outputs ['a']

此处，"a" 是有效的 name，因此也是有效的 exp1。这就是你得到的结果。 Pyparsing 不关心额外的 "b"。它找到了 exp1 的匹配项，因此它在此处停止。

至于无限递归，问题是这样的：

application = Group(expression + expression)
exp1 = ( name | function | application )
exp2 = (lparens + exp1 + rparens) | exp1
expression << exp2

这意味着 application 是一个有效的 exp1，而 exp1 又是一个有效的 exp2，这是一个有效的 expression。这是一个问题，因为 application 是由 expression 组成的。因此，当 pyparsing 尝试解析一个 expression 即 application 时，它必须在第一个中解析 another expression。这然后无限地继续下去。

一步一步，这是我们调用 expression.parseString("(ab)") 时发生的情况：

应用规则expression：
1. 应用规则左侧 exp2 (lparens + exp1 + rparens)：
  1. ( 匹配 lparens
  2. a 匹配 name
  3. b 不匹配 rparens -> 中止
2. 应用规则右侧 exp2 (exp1)：
  1. 应用 ( name | function | application ) (name) 中的第一个选项：
    1. ( 不匹配 name -> 中止
  2. 应用第二个选项（function）：
    1. ( 不匹配 λ -> 中止
  3. 应用第三个选项（application）：
    1. 应用规则 application (expression + expression):
      1. 应用规则expression：
        
        开始

请参阅了解工作实施。

pyparsing 部分匹配或递归限制命中

pyparsing partial match or recursion limit hit

python

pyparsing

python-3.x