3

我正在尝试通过 Jison 为语言ChucK在 JavaScript 中生成一个解析器，并且已经有了一个良好的开端，除了生成的解析器无法处理的语言中存在歧义。最初的 ChuckK 编译器是由 Bison 生成的，它必须能够以某种方式解决这些歧义。

出于这个问题的目的，我已将问题简化为仅存在一种歧义的解释语法。作为参考，我列出了所有相关文件的要点（包括生成的parser）。项目结构如下：

语法本身如下所示：

grammar = {
    Program: [
        ['ProgramSection', '$$ = new yy.Program($1);']
    ],
    ProgramSection: [
        ['Expression SEMICOLON', '$$ = new yy.ExpressionStatement($1);']
    ],
    Expression: [
        ['DeclExpression', '$$ = $1;'],
        ['Expression OP DeclExpression', '$$ = new yy.ExpFromBinary($1, $2, $3);']
    ],
    DeclExpression: [
        ['TypeDecl VarDeclList', '$$ = new yy.DeclExp($1, $2, 0);'],
        ['PrimaryExpression', '$$ = $1;']
    ],
    VarDeclList: [
        ['VarDecl', '$$ = new yy.VarDeclList($1);']
    ],
    VarDecl: [
        ['ID', '$$ = new yy.VarDecl($1);']
    ],
    TypeDecl: [
        ['ID', '$$ = new yy.TypeDecl(new yy.IdList($1), 0);']
    ],
    PrimaryExpression: [
        ['ID', '$$ = new yy.ExpFromId($1);']
    ]
};

歧义在于非终结符 DeclExpression 可以匹配TypeDecl VarDeclList或PrimaryExpression。这使得 Jison 发出以下警告：

States with conflicts:
State 7
  TypeDecl -> ID . #lookaheads= ID SEMICOLON OP
  PrimaryExpression -> ID . #lookaheads= ID SEMICOLON OP

并且生成的解析器无法解析测试代码（Type var => out;），如下所示：

Error: Parse error on line 1: Unexpected 'SEMICOLON'

据我了解，它是=>解析器尝试与 rule 匹配的运算符之后的部分TypeDecl VarDeclList。

那么，如何生成能够处理这种歧义的解析器呢？

4

2 回答 2

1

您的语法不能与 LALR(1) 解析器一起使用的原因是因为您对于 LALR(1) 解析器在and状态下的DeclExpression状态不明确。TypeDeclPrimaryExpression

让我试着解释一下。如错误消息所述，解析器检测到TypeDecl和上的冲突PrimaryExpression。两者都有 ID 作为标记，但由于 LALR(1) 解析器只能向前看一个标记，这意味着解析器不知道在它处于DeclExpression状态时要做什么。另一方面，SLR 有一种动态的前瞻机制，它会以牺牲一些内存为代价来解决冲突。

如果你想让它在 LALR(1) 解析器上工作，只需将你的DeclExpression规则重构为 like ID VarDeclList | ID，这样解析器就不必为了找到正确的规则而进行查看。

于 2017-11-17T08:08:36.007 回答
0

我发现我可以通过选择“slr”（SLR）或“lr”（L​​R1）解析器类型来为这个（简化的）语法生成一个功能解析器：

// Generate SLR parser, since default LALR has conflicts
exports.generate = new Parser(parserConfig, {type: "slr"}).generate;

但是，我仍然想知道为什么默认 (LALR(1)) 不起作用，因为这应该是 Bison 生成的。

于 2013-12-09T16:46:19.030 回答