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

Question

I'm currently working on visual basic converter using jison, and I have these conflicts in my grammar:

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

Here is simplified version of my grammar (actions deleted):

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

The conflict is happening when I'm trying to implement a rule for If statement, it seems to conflict with the Body rule.

I spent almost a day trying to solve it, but I can't. I know that the parser can look only one token ahead, but I can't figure out solution by myself. And I'm bound to jison so I cannot use another parser generator. Is there any workaround for my grammar?

Answer 1

Looking at these these productions:

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

It seems to me like the grammar is saying that an if statement must be terminated by IF_END only if it includes an else clause. An if which lacks an else clause cannot be terminated by IF_END.

That's not my understanding of the syntax of visual basic. END_IF is mandatory in the multiline syntax and is not used in the single line syntax.

So you have two conflicts, because your If production accepts some statements with END_IF and some without:

• For if statements without END_IF, you have the classic "dangling else" ambiguity.

• In addition, for multiline if statements without END_IF, the grammar provides no way to tell whether a following statement is part of the last clause in the if statement or a new statement. (That's why multiline if statements need END_IF.

The "dangling else" ambiguity is relatively benign -- that is, the normal resolution which prefers shift to reduce will produce the correct result. If you want to eliminate the error message, you can make the resolution explicit using precedence rules, giving ELSE and ELSE_IF higher precedence than IF. To use this technique, you must make the IF visible in the rules which depend on precedence, which basically means removing IF from IfBLock to leave you with:

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

You'll also need the precedence relations:

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

That will more or less get you going on single-line if statements, except that you'll need to replace Block with something which does not allow a TERMINATOR.

For multiline if statements, though, you'll need a different syntax:

• The END_IF is mandatory

• There must be a TERMINATOR after THEN and ELSE, and before ELSE and END_IF. In other words, the blocks of statements in a multiline if must start at the beginning of a line and be terminated with TERMINATOR.

These restrictions aren't just cosmetic: They are there because otherwise it is impossible to put a statement after a multiline if statement, since without the END_IF, any following statement would be added to the last THEN or ELSE clause.