parsing - 解决 LALR 解析器中的移位/归约冲突

Question

我一直在使用 PLY 为我的语言构建一个解析器，但是我遇到了移位/归约冲突，这给我带来了一些麻烦。我的语言具有通用类型，其语法与 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'>

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

编辑:向我建议的一个解决方案是使类型成为自己的 token 。这需要一些工作，因为我的语言不使用像 C/C++ 这样的预处理器包含系统，但我认为它仍然是可能的，但我更喜欢仅限于语法的解决方案。

Answer 1

Yacc 解析器并不是特别强大，尝试上下文无关解析可能要求太多。我建议使用某种技巧让 yacc 表现得像解析上下文相关的语法，或者不要尝试使用解析器来强制执行每个语法规则。

• 添加上下文
  识别何时解析类型，设置标志或调用方法将其传达给扫描器，然后为 < 返回不同的终端符号。和>在这种情况下。
• 简化语法
  或者，继续使用统一的表达式/模板语法进行部分模板生成，并在代码中错误地排除除模板语法之外的任何内容。解析器是系统中功能最弱的部分，因此请尽可能将工作放入代码中。 (对代码没有限制，对 yacc 有很多限制。)

我并不是说这些是您唯一的选择。如果您花了几天时间研究状态表并将语法调整到 yacc 满意的程度，我想您会“成功”，但这是不值得的。那时您可能刚刚编写了一个递归下降解析器。 (RD 是更多行代码，您看不到 BNFish yacc 中整齐排列的语法，但至少您可以解析任何内容，并且您永远不会陷入“它不起作用”的难题中。)

Python 是否有与 Ruby 类似的 Treetop ？这样就解决了问题。野牛的%glr-parser该功能也可以“解决”这样的问题，尽管是以一种相当 BFI 的方式。