2

这个 Lark 解析器是基于这个问题和这个网站的，但是解析时失败了a OR b OR c。

该网站建议：

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

这似乎与另一个问题一致。我的实现和测试用例......

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的吗？

4

2 回答 2

3

我对 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')])])
于 2019-11-26T07:53:59.013 回答
0

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

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

exp: exp OR 术语，因为 OR 与 AND 类似。

于 2019-11-26T07:52:46.360 回答