3

我一直在使用 PLY 为我的语言构建解析器，但是我遇到了 shift/reduce 冲突，这给我带来了一些麻烦。我的语言具有语法 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++ 这样的系统，但是我认为它仍然是可能的，但是我更喜欢一个仅限于语法的解决方案。

4

1 回答 1

1

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

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

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

Python 是否有任何与 Ruby 的Treetop等价的东西？那将解决问题。Bison 的%glr-parser功能也可以“解决”这样的问题，尽管是以一种相当 BFI 的方式。

于 2009-11-27T18:06:10.587 回答