用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）詞法分析部分的弱點。例如，在靈活生成的詞法分析器中，使用開始條件來分離詞法環境（程序/帶引號的字符串/帶括號的註釋）是正常的，而解析器則不會有歧義。

希望有所幫助。