Lark 解析器语法适用于 Earley 但不适用于 LALR
Lark parser grammar works with Earley but not LALR
考虑 Python Lark parser 的这个简单测试:
GRAMMAR = '''
start: container*
container: string ":" "{" (container | attribute | attribute_value)* "}"
attribute: attribute_name "=" (attribute_value | container)
attribute_value: string ":" _value ("," _value)*
_value: number | string
attribute_name: /[A-Za-z_][A-Za-z_#0-9]*/
string: /[A-Za-z_#0-9]+/
number: /[0-9]+/
%import common.WS
%ignore WS
'''
data = '''outer : {
inner : {
}
}'''
parser = Lark(GRAMMAR, parser='lalr')
parser.parse(data)
这对 parser='earley'
有效,但对 parser='lalr'
无效。我不明白为什么。错误信息是:
UnexpectedCharacters: No terminal defined for '{' at line 2 col 12
inner : {
这只是一个 MWE。我的实际语法也有同样的问题。
LALR 失败的原因是它的前瞻性为 1(与 Earley 不同,后者具有无限前瞻性),并且它在 attribute_name
和 string
之间混淆。一旦它与另一个匹配(在这种情况下,attribute_name
),它就不可能回溯并匹配不同的规则。
如果您对 attribute_name 终端使用较低的优先级,它会起作用。例如:
attribute_name: ATTR
ATTR.0: /[A-Za-z_][A-Za-z_#0-9]*/
但建议的做法是尽可能对两者使用相同的终端,这样解析器就可以代替词法分析器为您进行思考。如果需要,您可以在解析完成后添加额外的验证。
这两种方法(更改优先级或合并终端)都可以解决您的问题。
考虑 Python Lark parser 的这个简单测试:
GRAMMAR = '''
start: container*
container: string ":" "{" (container | attribute | attribute_value)* "}"
attribute: attribute_name "=" (attribute_value | container)
attribute_value: string ":" _value ("," _value)*
_value: number | string
attribute_name: /[A-Za-z_][A-Za-z_#0-9]*/
string: /[A-Za-z_#0-9]+/
number: /[0-9]+/
%import common.WS
%ignore WS
'''
data = '''outer : {
inner : {
}
}'''
parser = Lark(GRAMMAR, parser='lalr')
parser.parse(data)
这对 parser='earley'
有效,但对 parser='lalr'
无效。我不明白为什么。错误信息是:
UnexpectedCharacters: No terminal defined for '{' at line 2 col 12
inner : {
这只是一个 MWE。我的实际语法也有同样的问题。
LALR 失败的原因是它的前瞻性为 1(与 Earley 不同,后者具有无限前瞻性),并且它在 attribute_name
和 string
之间混淆。一旦它与另一个匹配(在这种情况下,attribute_name
),它就不可能回溯并匹配不同的规则。
如果您对 attribute_name 终端使用较低的优先级,它会起作用。例如:
attribute_name: ATTR
ATTR.0: /[A-Za-z_][A-Za-z_#0-9]*/
但建议的做法是尽可能对两者使用相同的终端,这样解析器就可以代替词法分析器为您进行思考。如果需要,您可以在解析完成后添加额外的验证。
这两种方法(更改优先级或合并终端)都可以解决您的问题。