python - 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”，并且由于没有后续的“)”，它应该放弃该名称并尝试函数(失败)，然后继续执行应用程序。然后它解析名称“a”(第一个匹配)，并继续分析名称“b”以完成名称、应用程序，然后匹配“)”以完成 exp1 和表达式。

显然，情况并非如此。

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

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

` #结果: ([([(['λ', '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']]]]]]

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

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

给予:

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

或更清楚地说:

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

在您发布的解析器中，您还有“应用程序”的概念。我推测您所说的应用程序就是引用的傻瓜文章中所说的“解决”。要解析函数，您可以将后续表达式与函数头中的每个名称一一对应，并用其各自的表达式替换主体中的名称。我试图在解析时理解这一点，但在函数嵌套在其他函数中的表达式中遇到了困难，或者头部和主体在嵌套括号中定义，替换表达式与函数通过多个嵌套级别分开。我得出的结论是，解析必须在名称和函数解析完成后进行。 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()