用LALR解析器解决我语法中的歧义问题

Question

我使用whittle解析语法，但我遇到了经典的LALR ambiguity problem。我的语法看起来像这样（简化）：

<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解析器，因此它试图将<name>解析为<string>，并且所有内容都会中断。语法使事情变得复杂，因为它为不同的事物使用了不同的字符串分隔符，这就是为什么我试图制定<string>规则的原因。

是否有规范化的方法来规范这个语法，使其符合LALR，如果它甚至可能？

Answer 1

这不是“经典的LALR模糊问题”，无论这可能是什么。这只是语言词汇规范中的一个错误。

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

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

只是一个错字的事实。

如果Ruby允许您使用[:print:]而不是Posix标准[[:print:]]，那么更好的办法是使用/[:print:]*/。

但是，这不会是正确的，因为lexing（通常）匹配最长的字符串，因此会吞噬结束引用和任何后续文本。

所以对于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算法中的任何弱点，这会导致你的痛苦，而且我认为这是惠特尔的（主要是未记录的afaics）词法分析部分的弱点。例如，在灵活生成的词法分析器中，使用开始条件来分离词法环境（程序/带引号的字符串/带括号的注释）是正常的，而解析器则不会有歧义。

希望有所帮助。