Jison parser generator, shift reduce 文法冲突，如何解决？

Question

我目前正在使用 jison 开发 Visual Basic 转换器，我的语法中有这些冲突：

Conflict in grammar: multiple actions possible when lookahead token is ELSE in state 11
- reduce by rule: If -> IfBlock
- shift token (then go to state 16)
Conflict in grammar: multiple actions possible when lookahead token is ELSE_IF in state 11
- reduce by rule: If -> IfBlock
- shift token (then go to state 17)
Conflict in grammar: multiple actions possible when lookahead token is TERMINATOR in state 27
- reduce by rule: IfBlock -> IF Expression THEN Body
- shift token (then go to state 13)
Conflict in grammar: multiple actions possible when lookahead token is TERMINATOR in state 29
- reduce by rule: IfBlock -> IfBlock ELSE_IF Expression THEN Body
- shift token (then go to state 13)

States with conflicts:
State 11
  If -> IfBlock . #lookaheads= $end TERMINATOR IF_END ELSE ELSE_IF SUB_END
  If -> IfBlock .ELSE Body IF_END #lookaheads= $end TERMINATOR IF_END ELSE ELSE_IF SUB_END
  IfBlock -> IfBlock .ELSE_IF Expression THEN Body #lookaheads= $end ELSE ELSE_IF TERMINATOR SUB_END IF_END
State 27
  IfBlock -> IF Expression THEN Body . #lookaheads= $end ELSE ELSE_IF TERMINATOR SUB_END IF_END
  Body -> Body .TERMINATOR Line
  Body -> Body .TERMINATOR
State 29
  IfBlock -> IfBlock ELSE_IF Expression THEN Body . #lookaheads= $end ELSE ELSE_IF TERMINATOR SUB_END IF_END
  Body -> Body .TERMINATOR Line
  Body -> Body .TERMINATOR

这是我的语法的简化版本（动作已删除）：

const grammar = {
  Root: [
    [
      ''
    ],
    [
      'Body'
    ]
  ],
  Body: [
    [
      'Line'
    ],
    [
      'Body TERMINATOR Line'
    ],
    [ 'Body TERMINATOR' ]
  ],
  Line: [ [ 'Expression' ], [ 'Statement' ] ],
  Statement: [ [ 'Return' ], [ 'If' ] ],
  Expression: [ [ 'Code' ] ],
  Return: [
    [
      'RETURN Expression'
    ],
    [
      'RETURN'
    ]
  ],
  Code: [
    [
      'SUB_START Identifier PARAM_START ParamList PARAM_END TERMINATOR Body SUB_END'
    ]
  ],
  IfBlock: [
    [
      'IF Expression THEN Body'
    ],
    [
      'IfBlock ELSE_IF Expression THEN Body'
    ]
  ],
  If: [
    [ 'IfBlock' ],
    [
      'IfBlock ELSE Body IF_END'
    ]
  ]
}

当我尝试为 If 语句执行规则时发生冲突，它似乎与 Body 规则冲突。

我花了将近一天的时间试图解决它，但我做不到。我知道解析器只能向前看一个标记，但我自己想不出解决方案。而且我必须使用 jison，所以我不能使用另一个解析器生成器。我的语法有什么解决方法吗？

Answer 1

看看这些作品：

If: [
        [ 'IfBlock' ],
        [ 'IfBlock ELSE Body IF_END ']
    ]

在我看来语法是说 if 语句必须由 IF_END 终止 只有当 它包含 else 条款。缺少 else 子句的 if 不能由 IF_END.

终止

这不是我对 Visual Basic 语法的理解。 END_IF 在多行语法中是必需的，在单行语法中不使用。

所以你有两个冲突，因为你的 If 生产接受一些带有 END_IF 的语句和一些没有：

对于没有 END_IF 的 if 语句，你有典型的 "dangling else" 歧义。
此外，对于没有 END_IF 的多行 if 语句，语法无法判断后续语句是否是 [=13] 中最后一个子句的一部分=] 语句或新语句。（这就是为什么多行 if 语句需要 END_IF.

"dangling else" 歧义相对良性 -- 也就是说，更喜欢 shift 而不是 reduce 的正常分辨率将产生正确的结果。如果要消除错误消息，可以使用优先规则明确解决方案，使 ELSE 和 ELSE_IF 的优先级高于 IF。要使用此技术，您必须使 IF 在取决于优先级的规则中可见，这基本上意味着从 IfBLock 中删除 IF 以留下：

IfBlock: [
  [ 'Expression THEN Body' ],
  [ 'IfBlock ELSE_IF Expression THEN Body' ]
],
If: [
  [ 'IF IfBlock' ],
  [ 'IF IfBlock ELSE Body' ]  // IF_END removed
]

您还需要优先关系：

[ 'left', 'IF' ],
[ 'left', 'ELSE', 'ELSE_IF' ]

这或多或少会让你继续使用单行 if 语句，除了你需要用不允许 TERMINATOR.[=50= 的东西替换 Block ]

但是，对于多行 if 语句，您需要不同的语法：

END_IF是必须的
在THEN和ELSE之后，ELSE和END_IF之前必须有一个TERMINATOR。换句话说，多行 if 中的语句块必须从一行的开头开始，并以 TERMINATOR.

这些限制不仅仅是装饰性的：它们之所以存在，是因为否则不可能在多行 if 语句之后放置一个语句，因为如果没有 END_IF，任何后续语句都会被添加到最后一个 THEN 或 ELSE 子句。

Jison parser generator, shift reduce 文法冲突，如何解决？

Jison parser generator, shift reduce grammar conflict, how to solve?

javascript

parsing

bison

yacc

jison