解决LALR解析器中的移位/减少冲突

Question

我一直在使用PLY为我的语言构建解析器，但是我遇到了移位/减少冲突，这给我造成了一些麻烦。我的语言具有语法ala C++模板的泛型类型。所以现在我有这样的规则：

expression : expression LESS expression %prec COMPARISON 
    expression : template 
    template : NAME 
      | NAME LESS templates GREATER 
    templates : template 
       | templates COMMA template 

然而，我发现，这是无法解析：

a < 2 

（这是显而易见的原因有问题）。以下是调试输出：

PLY: PARSE DEBUG START 

State : 0 
Stack : . <Token: 'NAME' 'a'> 
Action : Shift and goto state 42 

State : 42 
Stack : NAME . <Token: 'LESS' '<'> 
Action : Shift and goto state 81 

State : 81 
Stack : NAME LESS . <Token: 'NUMBER' '2'> 
ERROR: Error : NAME LESS . <Token: 'NUMBER' '2'> 

如果我需要更多的解析器，我可以提供它。谢谢。

编辑：向我提出的一种解决方案是让类型自己的令牌。这需要一点工作，因为我的语言不使用像C/C++这样的预处理器包含系统，但是我认为它仍然是可能的，但是我更喜欢一个限于语法的解决方案。

Answer 1

Yacc解析器不是特别强大，尝试上下文无关的解析可能会要求太多。我建议使用某种技巧来使yacc像分析上下文敏感语法一样行事，或者，不要尝试使用解析器来强制执行每条语法规则。

• 添加上下文
  当你解析类型识别，设置一个标志或调用一个方法来此传送给扫描仪，然后在这种情况下返回不同的终端符号<和>。
• 简化语法
  或者，继续，只对模板生成的一部分使用统一的表达式/模板语法，并在代码中错误地输出除模板语法之外的任何内容。解析器是系统中能力最低的部分，因此尽可能将工作推送到代码中。 （对代码没有限制，对yacc有很多限制。）

我并不是说这些是你唯一的选择。如果你花费了几天时间，对国家表格感到困惑，并将语法调整到yacc满意的地步，我想你会“成功”，但这不值得。那时你可能刚写了一个递归下降解析器。 （RD是更多的代码行，并且你不会看到在BNFish yacc中整齐排列的语法，但至少你可以解析任何东西，并且你永远不会陷入“不工作”的谜题。）

Python与Ruby的Treetop有什么相同之处吗？这将解决问题。野牛的%glr-parser功能也可以“解决”这样的问题，尽管采用BFI方式。