用CFG解析枚举

Question

我有一个字符串，它是从一个富文本枚举中生成的，例如：

"(1)设X表示下列之一：(a)重量(b)高度(c)深度(2) Y表示(a)颜色，(i)白色(ii)蓝色(b)压力“

我想要建造原来的结构，例如：

{"Let X denote one of the following:" : {"weight":{}, "height":{}, "depth":{}} , 
"Y denote": {"color, except": {"white":{}, "blue":{}}}, "pressure":{} }

很明显，这是上下文无关的语法，但是我在实现pyparsing时遇到了困难。

编辑

我不是CFG的专家，所以我希望BNF的陈述是正确的：

假设如下：

1. w相当于任何字符(re.compile("\w*"))
2. l等价于re.compile("[a-z]")
3. d相当于`re.compile("\d+")
4. r等价于罗马数字(i，ii，iii，.)

那么(希望)，BNF应该看起来像这样

<E1>::= "(" <d> ")" | <E1> " "
<E2>::= "(" <l> ")" | <E2> " "
<E3>::= "(" <r> ")" | <E3> " "
<L0>::= <w> | <w> <E1> <L1> <L0>
<L1>::= <w> | <w> <E2> <L2> <L1>
<L2>::= <w> | <w> <E3> <L2>

Answer 1

下面是您的语法分析器的第一部分，它使用pyparsing表达式：

import pyparsing as pp

LPAR, RPAR = map(pp.Suppress, "()")
COMMA, COLON = map(pp.Literal, ",:")
wd = pp.Word(pp.alphas)
letter = pp.oneOf(list(pp.alphas.lower())) 
integer = pp.pyparsing_common.integer
roman = pp.Word('ivx')

e1 = LPAR + integer + RPAR
e2 = LPAR + letter + RPAR
e3 = LPAR + roman + RPAR

下一部分，基于您的BNF，看起来可能如下：

# predefine levels using Forwards, since they are recursive
lev0 = pp.Forward()
lev1 = pp.Forward()
lev2 = pp.Forward()

lev0 <<= wd | wd + e1 + lev1 + lev0
lev1 <<= wd | wd + e2 + lev2 + lev1
lev2 <<= wd | wd + e3 + lev2

我假设lev0应该解析测试字符串，这是嵌套的第0‘级。

正如我在对您的问题的注释中提到的，这会立即失败，因为您的测试字符串以"(1)“开头，但是您的级别不会从任何e表达式开始。

在继续之前，BNF以经典的BNF形式实现了重复：

e ::= some expression
list_of_e ::= e (list_of_e | empty)

在little解析中，您应该更直接地实现这一点：

wd = pp.Word(pp.alphas)
list_of_wd = pp.OneOrMore(wd)
# or using tuple multiplication short-hand
list_of_wd = wd * (1,)

在您的示例中，我将BNF的级别重写为：

wds = pp.Group(wd*(1,))
lev0 <<= e1 + wds + lev1*(0,)
lev1 <<= e2 + wds + lev2*(0,)
lev2 <<= e3 + wds
expr = lev0()*(1,)
expr.ignore(COMMA | COLON)

(我没有看到逗号或冒号对解析有帮助，所以我只是忽略了它们。)

使用expr解析字符串：

tests = """\
(1) Y denote (a) color (b) pressure
(1) Let X denote one of the following: (a) weight (b) height (c) depth (2) Y denote (a) color, except (i) white (ii) blue (b) pressure
"""

for test in tests.splitlines():
    print(test)
    expr.parseString(test).pprint()
    print()

我们得到：

(1) Y denote (a) color (b) pressure
[1, ['Y', 'denote'], 'a', ['color'], 'b', ['pressure']]

(1) Let X denote one of the following: (a) weight (b) height (c) depth (2) Y denote (a) color, except (i) white (ii) blue (b) pressure
[1,
 ['Let', 'X', 'denote', 'one', 'of', 'the', 'following'],
 'a',
 ['weight'],
 'b',
 ['height'],
 'c',
 ['depth'],
 2,
 ['Y', 'denote'],
 'a',
 ['color', 'except'],
 'i',
 ['white'],
 'ii',
 ['blue'],
 'b',
 ['pressure']]

因此，它进行了解析，也就是说，它通过了整个输入字符串，但我们所做的只是基本的标记化，并且没有表示整数/alpha/罗马嵌套列表所隐含的任何结构。

Pyparsing解析包含一个分组类，用于构造结果：

G = pp.Group
wds = G(wd*(1,))
lev0 <<= G(e1 + G(wds + lev1*(0,)))
lev1 <<= G(e2 + G(wds + lev2*(0,)))
lev2 <<= G(e3 + wds)
expr = lev0()*(1,)
expr.ignore(COMMA | COLON)

这提供了更好地保留层次结构的输出：

(1) Y denote (a) color (b) pressure
[[1, [['Y', 'denote'], ['a', [['color']]], ['b', [['pressure']]]]]]

(1) Let X denote one of the following: (a) weight (b) height (c) depth (2) Y denote (a) color, except (i) white (ii) blue (b) pressure
[[1,
  [['Let', 'X', 'denote', 'one', 'of', 'the', 'following'],
   ['a', [['weight']]],
   ['b', [['height']]],
   ['c', [['depth']]]]],
 [2,
  [['Y', 'denote'],
   ['a', [['color', 'except'], ['i', ['white']], ['ii', ['blue']]]],
   ['b', [['pressure']]]]]]

一个完整的解析器实际上可以理解“以下内容之一”和“所有以下内容”的概念，以及元素的包含和排除，但这超出了这个问题的范围。