python - lark中的 bool 表达式解析器无法解析 'a OR b OR c'

Question

这个Lark解析器是基于这个question还有这个website ，但解析 a OR b OR c 时失败.

website建议:

<expression>::=<term>{<or><term>}
<term>::=<factor>{<and><factor>}
<factor>::=<constant>|<not><factor>|(<expression>)
<constant>::= false|true
<or>::='|'
<and>::='&'
<not>::='!'

这与其他 question 一致。我的实现和测试用例...

import lark

PARSER = lark.Lark("""
    ?exp: term | term OR term
    ?term: factor | factor AND factor
    ?factor: symbol | NOT factor | "(" exp ")"
    symbol: /[a-z]+/
    AND: "AND"
    OR: "OR"
    NOT: "NOT"
    %ignore " "
""", start='exp')

qs = [
        'a',
        'NOT a',
        'a OR b',
        'a OR b OR c',
        'a AND b AND c',
        'NOT (a AND b AND c) OR NOT (b OR c)',
        'NOT a AND NOT b',
    ]

for q in qs:
    t = PARSER.parse(q)

运行它:

$ python ./foo.py 
Traceback (most recent call last):
  File "./foo.py", line 26, in <module>
    t = PARSER.parse(q)
  File "/tmp/v/lib64/python3.6/site-packages/lark/lark.py", line 311, in parse
    return self.parser.parse(text, start=start)
  File "/tmp/v/lib64/python3.6/site-packages/lark/parser_frontends.py", line 185, in parse
    return self._parse(text, start)
  File "/tmp/v/lib64/python3.6/site-packages/lark/parser_frontends.py", line 54, in _parse
    return self.parser.parse(input, start, *args)
  File "/tmp/v/lib64/python3.6/site-packages/lark/parsers/earley.py", line 292, in parse
    to_scan = self._parse(stream, columns, to_scan, start_symbol)
  File "/tmp/v/lib64/python3.6/site-packages/lark/parsers/xearley.py", line 137, in _parse
    to_scan = scan(i, to_scan)
  File "/tmp/v/lib64/python3.6/site-packages/lark/parsers/xearley.py", line 114, in scan
    raise UnexpectedCharacters(stream, i, text_line, text_column, {item.expect.name for item in to_scan}, set(to_scan))
lark.exceptions.UnexpectedCharacters: No terminal defined for 'O' at line 1 col 8

a OR b OR c
       ^

Expecting: {'AND'}

我哪里出错了？我的转换是term { OR term }至term | term OR term错了？

Answer 1

我对 Lark 不太熟悉，但通常如果没有直接的方法来实现可选重复，此类语法的实现为

    ?exp: term | exp OR term
    ?term: factor | term AND factor

从我在文档中找到的内容来看，Lark 确实直接支持这种构造:

    ?exp: term (OR term)*
    ?term: factor (AND factor)*

这些确实会导致不同的语法树:

# first parser output
Tree(exp, [
    Tree(exp, [
        Tree(symbol, [Token(__ANON_0, 'a')]),
        Token(OR, 'OR'), 
        Tree(symbol, [Token(__ANON_0, 'b')])]),
    Token(OR, 'OR'),
    Tree(symbol, [Token(__ANON_0, 'c')])])
# second parser output
Tree(exp, [
    Tree(symbol, [Token(__ANON_0, 'a')]),
    Token(OR, 'OR'),
    Tree(symbol, [Token(__ANON_0, 'b')]),
    Token(OR, 'OR'),
    Tree(symbol, [Token(__ANON_0, 'c')])])