lark 布尔表达式解析器解析失败 'a OR b OR c'

Question

此Lark解析器基于此question and this website，但在解析a OR b OR c时失败。

<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

使用上面给出的语法exp->term OR term进行推导，term将无法生成包含OR的表达式。将语法规则更改为。

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

exp: exp OR 项，因为 OR 与 AND 类似地左结合。

Answer 2

具体Lark我不是很熟悉，但是一般如果没有直接的方式实现optional repeating的话，这些语法实现为

    ?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')])])

lark 布尔表达式解析器解析失败 'a OR b OR c'

Boolean expression parser in lark fails to parse 'a OR b OR c'

python

lark-parser