修复Lemon解析器语法上的歧义

Question

我的语法看上去很模糊。在FileText下似乎存在一些问题，因为当我只运行最上面的部分(FileText之上)时，没有冲突。有人能帮我找出我的问题所在吗？我相信我的树看起来很好。下面是一个输入示例：

lemon AND (#Chapter1.Title : "BNF grammar" AND #Chapter10.Title : ("BNF notion" OR "EBNF notion"))

错误：

     QUOT shift        17
     QUOT reduce       14  ** Parsing conflict **
      STR shift-reduce 20  subval ::= STR
      STR reduce       14  ** Parsing conflict **
     LPAR shift         7  
     LPAR reduce       14  ** Parsing conflict **
       WS shift-reduce 10  space ::= WS
       WS reduce       14  ** Parsing conflict **
       op shift         9
    space shift        12
     text shift-reduce 15  filetext::= filetext text
 subvalue shift-reduce 15  filetext::= filetext text /*because subval==text
 {default} reduce      14  location ::= location COLON filetext

语法：

%left::=AND.
%left::=OR.

book::= expr.

expr::= expr term.
expr::= expr op term.
expr::= term.

term::= value.
term::= QUOT STR QUOT.

value::= atom.
value::= LPAR expr RPAR.

atom::= STR.
atom::= file.

op::= space AND space.
op::= space OR space.

space::= WS.
space::= space WS.

file::= location COLON filetext.

location::= SHARP STR PERIOD STR.

filetext::= filetext text.
filetext::= filetext op text.
filetext::= text.

text::= subvalue.
text::= QUOT STR QUOT.

subvalue::= subatom.
subvalue::= LPAR filetext RPAR.

subatom::= STR.

关于什么是值得的，这棵树提出并推导出了我的语法：

​

​

Answer 1

问题是，在expr和filetext中都允许隐式级联(即没有运算符)。

考虑一下级联expr term。

请注意，expr可以派生file (通过term -> value -> atom)，file以filetext结尾，而filetext又可以是filetext text。

text和term都派生STR和QUOT STR QUOT。假设您的输入类似于

SHARP STR PERIOD STR COLON      STR       STR
------location------       --filetext--?
----------------------file-------------?

现在，这最后一次STR将如何处理？

解析器可以将location COLON filetext还原为file，然后将expr还原为expr。然后，可以将最后一个STR简化为term (通过atom和value)，从而使整个输入减少到使用expr::=expr term的expr。

但它也可以将STR缩减为text (通过subatom和subvalue)，这将允许它将filetext扩展到包含最后一个STR。然后，当它将location COLON filetext还原为file和expr时，就完成了。

这绝对是一种模糊(而且它只是众多的其中之一)。没有明显的解决冲突的方法--至少，对我来说没有什么是显而易见的--所以你必须找出你真正想要的替代方案。

顺便说一句，我不认为您的空格处理符合您的期望。例如，语法中的任何内容都不允许围绕:的空格。你最好在你的词法分析器中忽略空格，把它从语法中删除，因为语法只会使事情复杂化。如果您不希望将"word"suffix作为两个词("word" suffix)进行分析，那么您可以在词法分析器中进行检查，这需要使用一个近引号来避免后面跟着一个STR (类似地，一个开引号不能在前面加上一个STR)。实际上，在词法分析器中识别引用的字符串可能会更好；因为区别在于词法而不是句法。正如所写的，QUOT STR QUOT将不匹配"BNF grammar"，例如(因为BNF grammar与STR不匹配)。