python - Pyparsing 中的递归

Question

我无法将这个 EBNF 表达式翻译成 Pyparsing，知道吗？

token:: [A-Z]
P:: !|token;P|(P^P)|(P*P)

问题是在使用递归时，解释器会失败。这样的表达应该是有效的:

(ASD;!^FFF;!)
A;B;C;!
(((A;!^B;!)^C;D;!)*E;!)

Answer 1

要使用 Pyparsing 构建递归语法，您必须使用 pyparsing 的 Forward 类进行一些由内而外的思考。使用 Forward，您可以为稍后定义的表达式定义一个空占位符。这是此 BNF 的 pyparsing 的开始:

EXCLAM,SEMI,HAT,STAR = map(Literal,"!;^*")
LPAR,RPAR = map(Suppress,"()")
token = oneOf(list(alphas.upper()))

我使用 Literal 来定义您的运算符，但抑制分组 ()，我们将使用 pyparsing Group 将结果物理分组到子列表中。

现在我们用 Forward 定义占位符表达式:

expr = Forward()

现在我们可以使用这个占位符构建表达式(我们必须使用 '<<=' 作为赋值运算符，以便 expr 保持为 Forward，而不是反弹到表达式本身)。这是我的第一遍，按原样使用您的 BNF:

expr <<= (EXCLAM | 
          token + SEMI + expr | 
          Group(LPAR + expr + HAT + expr + RPAR) | 
          Group(LPAR + expr + STAR + expr + RPAR))

这给出了这些结果:

(ASD;!^FFF;!)
  ^
Expected ";" (at char 2), (line:1, col:3)

A;B;C;!
['A', ';', 'B', ';', 'C', ';', '!']

(((A;!^B;!)^C;D;!)*E;!)
[[[['A', ';', '!', '^', 'B', ';', '!'], '^', 'C', ';', 'D', ';', '!'], '*', 'E', ';', '!']]

在你的 BNF 中似乎有一个不成文的规则，一个或多个标记也可以一起出现，很容易固定为:

expr <<= (EXCLAM | 
          OneOrMore(token) + SEMI + expr | 
          Group(LPAR + expr + HAT + expr + RPAR) | 
          Group(LPAR + expr + STAR + expr + RPAR))

现在给予:

(ASD;!^FFF;!)
[['A', 'S', 'D', ';', '!', '^', 'F', 'F', 'F', ';', '!']]

A;B;C;!
['A', ';', 'B', ';', 'C', ';', '!']

(((A;!^B;!)^C;D;!)*E;!)
[[[['A', ';', '!', '^', 'B', ';', '!'], '^', 'C', ';', 'D', ';', '!'], '*', 'E', ';', '!']]

但看起来我们可以从额外的分组中获益，这样二元“^”和“*”运算符的操作数可以更清楚地分组。所以我决定:

expr <<= (EXCLAM | 
          Group(OneOrMore(token) + SEMI + ungroup(expr)) | 
          Group(LPAR + expr + HAT + expr + RPAR) | 
          Group(LPAR + expr + STAR + expr + RPAR) )

而且我认为这个版本的输出现在会更容易处理:

(ASD;!^FFF;!)
[[['A', 'S', 'D', ';', '!'], '^', ['F', 'F', 'F', ';', '!']]]

A;B;C;!
[['A', ';', 'B', ';', 'C', ';', '!']]

(((A;!^B;!)^C;D;!)*E;!)
[[[[['A', ';', '!'], '^', ['B', ';', '!']], '^', ['C', ';', 'D', ';', '!']], '*', ['E', ';', '!']]]

完整的脚本如下:

from pyparsing import *

EXCLAM,SEMI,HAT,STAR = map(Literal,"!;^*")
LPAR,RPAR = map(Suppress,"()")
token = oneOf(list(alphas.upper()))
expr = Forward()
expr <<= (EXCLAM | 
          Group(OneOrMore(token) + SEMI + ungroup(expr)) | 
          Group(LPAR + expr + HAT + expr + RPAR) | 
          Group(LPAR + expr + STAR + expr + RPAR) )

tests = """\
(ASD;!^FFF;!)
A;B;C;!
(((A;!^B;!)^C;D;!)*E;!)""".splitlines()

for t in tests:
    print t
    try:
        print expr.parseString(t).dump()
    except ParseException as pe:
        print ' '*pe.loc + '^'
        print pe
    print

最后一点:我假设“AAA”是 3 个连续的“A”标记。如果您的意思是标记是 1 个或多个 alpha 的单词分组，则将表达式中的 'OneOrMore(token)' 更改为 'Word(alphas.upper())' - 然后您将获得第一个测试用例的结果:

[[['ASD', ';', '!'], '^', ['FFF', ';', '!']]]