BASIC语法中"END"和"END IF"之间的冲突，使用Lark

Question

我正在尝试使用 Lark 为 BASIC 创建 LALR 解析器，但我很难修复 "END" 语句与 "END IF" 等语句之间的冲突.这是语法的简化版本：

%ignore /[ \t\f]+/

program: _nlopt _part_list

_part_list: (stmt | block) _nl _part_list
          |

_nlopt: _nl
      |

_nl: _NEWLINE _nl
   | _NEWLINE

block: if_block

stmt: print_stmt
    | end_stmt

end_stmt: END_KW

if_block: IF_KW expr THEN_KW _nl block_body endif_stmt

endif_stmt: END_KW IF_KW

block_body: _block_body_item block_body
          |

_block_body_item: stmt _nl

print_stmt: PRINT_KW expr

?expr: NUMERIC_LITERAL

_NEWLINE: "\n"
NUMERIC_LITERAL: /[\-+]?\d+(\.\d*)?[!#%&]?/

END_KW: "end"i
IF_KW: "if"i
PRINT_KW: "print"i
THEN_KW: "then"i

如果我用这样的代码尝试这个语法：

parser = Lark(grammar, start='program', parser='lalr')

prog = r"""
if 1 then
   print 200
end if
"""
t = parser.parse(prog)
print(t.pretty())

这是我从 Lark 得到的：

Traceback (most recent call last):
  File "test.py", line 230, in <module>
    t = parser.parse(prog)
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/lark.py", line 250, in parse
    return self.parser.parse(text)
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/parser_frontends.py", line 37, in parse
    return self.parser.parse(token_stream, *[sps] if sps is not NotImplemented else [])
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/parsers/lalr_parser.py", line 68, in parse
    for token in stream:
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/lexer.py", line 341, in lex
    for x in l.lex(stream, self.root_lexer.newline_types, self.root_lexer.ignore_types):
  File "/home/user/.pyenv/versions/venv/lib/python3.6/site-packages/lark/lexer.py", line 175, in lex
    raise UnexpectedCharacters(stream, line_ctr.char_pos, line_ctr.line, line_ctr.column, allowed=allowed, state=self.state)
lark.exceptions.UnexpectedCharacters: No terminal defined for 'i' at line 4 col 5

end if
    ^

Expecting: ['__IGNORE_0', '_NEWLINE']

如果我删除 "end_stmt" 规则，就不会发生这种情况。有没有办法修复语法以防止这种情况发生？

Answer 1

默认情况下，Lark 不会就语法中的 shift-reduce 冲突向您发出警告，而是默默地解决它们以支持移位。这通常会导致解析器无法解析您想要的内容——就像这里的情况一样。你可以通过将 debug = True 标志传递给 Lark() 让 lark 警告你这些冲突。这样，您甚至可以在通过测试发现问题之前就发现问题所在，甚至可以获得有关问题所在的有用信息。

启用 debug 选项后，您会收到一条警告，提示存在 shift-reduce 冲突，其中 END_KW 可能意味着当前 block_body 已结束或者它可以是 end_stmt。这是一个问题，因为 LALR(1) 解析器只能向前看一个标记，但我们必须向前看第二个标记，看看 end 之后是否有 if 才能正确决定哪个选择采取。

你可以通过将 end if 变成一个像这样的单个标记来解决这个问题，有点 hackishly：

ENDIF_KW: /end[ \t\f]+if/i

然后使用 ENDIF_KW 代替 END_KW IF_KW。

PS：请注意，如果您使用 Earley 解析而不是 LALR(1)，您的语法将在没有这些更改的情况下正常工作。

Answer 2

我的基本语法也有同样的冲突。由于 END WHILE、END IF 等，基本语言是 LALR(2) 或 LR(2)。如果您有 LR(2) 解析器生成器，则可以解析 basic。 LRSTAR 解析器生成器可以创建 LR(2) 解析器。

BASIC语法中"END"和"END IF"之间的冲突，使用Lark

Collision in between "END" and "END IF" in BASIC grammar, using Lark

python

grammar

parsing

lark-parser