0

我正在使用whittle来解析语法，但我遇到了经典的LALR 歧义问题。我的语法看起来像这样（简化）：

<comment> ::= '{' <string> '}'           # string enclosed in braces
<tag> ::= '[' <name> <quoted-string> ']' # [tagname "tag value"]
<name> ::= /[A-Za-z_]+/                  # subset of all printable chars
<quoted-string> ::= '"' <string> '"'     # string enclosed in quotes
<string> ::= /[:print:]/                 # regex for all printable chars

问题当然是<string>。它包含所有可打印的字符，因此非常贪婪。由于它是一个 LALR 解析器，它试图将 a 解析<name>为 a<string>并且一切都中断了。语法使事情变得复杂，因为它对不同的事物使用不同的字符串定界符，这就是我<string>首先尝试制定规则的原因。

如果可能的话，是否有一种规范的方法来规范这个语法以使其符合 LALR 标准？

4

1 回答 1

1

这不是“经典的 LALR 歧义问题”，不管它是什么。这只是语言词汇规范中的错误。

我快速浏览了 Whittle 自述文件，但它与 OP 中的语法没有任何相似之处。所以我假设 OP 中的文本是概念性的而不是字面的，而且它包含明显不正确的事实

<string> ::= /[:print:]/                 # regex for all printable chars

只是一个错字。

更好的是/[:print:]*/，假设 Ruby 让您侥幸逃脱[:print:]而不是 Posix 标准[[:print:]]。

但这也不正确，因为词法分析（通常）匹配可能最长的字符串，因此会吞噬结束引号和任何后续文本。

所以正确的解决方案quoted-string是正确地写出来：

<quoted-string> ::= /"[^"]*"/

甚至

<quoted-string> :: /"([^\\"]|\\.)*"/
# any number of characters other than quote or escape, or escaped pairs

您可能对如何转义内部双引号有其他想法；这些只是例子。在这两种情况下，您都需要对标记进行后处理，以便（至少）去除双引号并可能解释转义序列。事情就是这样。

您的评论序列提出了一个更困难的问题，假设您的意图是评论可能包含嵌套大括号（例如。{This comment {with this} ends here}），因为嵌套大括号语法不规则，因此无法与正则表达式匹配。当然，现在很少有“正则表达式”库是真正有规律的，而且我不知道 Ruby 是否包含某种括号计数扩展，例如 Lua 的模式语法。嵌套大括号语法当然是上下文无关的，但要真正解析它，您需要以{...}不同于程序其余部分的方式对外部的内容进行词法分析。

正是后一种观察结果，而不是 LALR 算法中的任何弱点，导致了你的痛苦，我想说这是 whittle 的（主要是未记录的 afaics）词法分析部分的弱点。例如，在 flex 生成的词法分析器中，通常使用开始条件来分隔词法环境（程序/引用字符串/大括号注释），这样解析器就不会产生歧义。

希望有帮助。

于 2014-03-06T18:27:01.997 回答