4

我正在使用 lark，一个优秀的python 解析库。

它提供了 Earley 和 LALR(1) 解析器，并通过自定义EBNF格式定义。（EBNF 代表扩展巴科斯-瑙尔形式）。

小写定义是规则，大写定义是终端。Lark 还为大写定义提供了权重，以优先匹配。

我正在尝试定义语法，但我陷入了一种我似乎无法平衡的行为。

我对未命名的文字（双引号之间的字符串或字符）有一些规则：

directives: directive+
directive: "@" NAME arguments ?
directive_definition: description? "directive" "@" NAME arguments? "on" directive_locations
directive_locations: "SCALAR" | "OBJECT" | "ENUM"

arguments: "(" argument+ ")"
argument: NAME ":" value

union_type_definition: description? "union" NAME directives? union_member_types?

union_member_types: "=" NAME ("|" NAME)*

description: STRING | LONG_STRING    

STRING: /("(?!"").*?(?<!\\)(\\\\)*?"|'(?!'').*?(?<!\\)(\\\\)*?')/i
LONG_STRING: /(""".*?(?<!\\)(\\\\)*?"""|'''.*?(?<!\\)(\\\\)*?''')/is
NAME.2: /[_A-Za-z][_0-9A-Za-z]*/

它适用于 99% 的用例。但是，如果在我解析的语言中，我使用了一个directive叫做的 directive，那么一切都会中断：

union Foo @something(test: 42) = Bar | Baz   # This works
union Foo @directive(test: 42) = Bar | Baz   # This fails

在这里，当字符串应该匹配终端时，它会匹配规则directive中未命名的文字。directive_definitionNAME.2

我怎样才能平衡/调整它，以便 LALR(1) 解析器没有歧义？

4

1 回答 1

8

Lark 的作者在这里。

发生这种误解是因为“指令”可以是两个不同的标记：“指令”字符串或 NAME。默认情况下，Lark 的 LALR 词法分析器总是选择更具体的词法，即字符串。

那么我们如何让词法分析器知道这@directive是一个名称，而不仅仅是两个常量字符串呢？

解决方案 1 - 使用上下文词法分析器

在这种情况下（如果没有完整的语法很难确定）可能会有所帮助的是使用上下文词法分析器，而不是标准的 LALR(1) 词法分析器。

上下文词法分析器可以在某种程度上与解析器进行通信，以确定在每个点上哪个终端更有意义。这是 Lark 独有的算法，你可以这样使用它：

parser = Lark(grammar, parser="lalr", lexer="contextual")

（这个词法分析器可以做任何标准词法分析器可以做的事情，甚至更多，所以在未来的版本中它可能成为默认的词法分析器。）

解决方案 2 - 为终端添加前缀

如果上下文词法分析器无法解决您的冲突，则针对这种情况的更“经典”解决方案是定义一个指令标记，例如：

DIRECTIVE: "@" NAME

与您的指令规则不同，这不会给词法分析器留下歧义。指令和“指令”字符串（或 NAME 终端）之间有明显的区别。

如果所有其他方法都失败了，您始终可以使用 Earley 解析器，它会以性能为代价，适用于您提供的任何语法，无论可能有多少冲突。

希望这可以帮助！

编辑：我只想指出上下文词法分析器现在是 LALR 的默认值，所以调用它就足够了：

parser = Lark(grammar, parser="lalr")
于 2018-02-16T22:18:10.940 回答