如何使用Jison生成处理语法歧义的解析器？

Question

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

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

• 语言/词汇。js：lexer

语法本身如下所示：

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);']
    ]
};

模棱两可的是，非终端机DeclExpress可以匹配TypeDecl VarDeclList或PrimaryExpress。这使得Jison发出以下警告：

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

生成的解析器无法解析测试代码（Type var）=

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

据我所知，这是=

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




Answer 1

我发现我可以通过选择“单反”或“lr”（LR1）解析器类型来为这个（简化的）语法生成一个函数解析器：

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

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

Answer 2

你的语法不能与LALR（1）解析器一起使用的原因是，你的语法在TypeDecl和PrimaryExpression状态下的DeclExpression状态对LALR（1）解析器不明确。

让我来解释一下。如错误消息所述，解析器在TypeDecl和PrimaryExpression上检测到冲突。两者都有ID作为令牌，但由于LALR（1）解析器只能向前看一个令牌，这意味着解析器不知道在解列压缩状态下该做什么。另一方面，单反相机有一种动态的头像，这将以牺牲一些内存来解决冲突。

如果您想让它在LALR（1）解析器上工作，只需将您的DeclExpression规则重构为ID VarDeclList | ID，这样解析器就不必为了找到正确的规则而查看头部。