parsingbisonyaccparser-generatorjison

Jison parser generator shift reduce conflict with parenthesis, how to solve?


I'm trying to implement parenthesis in my parser but i got conflict in my grammar. "Conflict in grammar: multiple actions possible when lookahead token is )" Here is simplified version of it:

// grammar
{
    "Root": ["", "Body"],
    "Body": ["Line", "Body TERMINATOR Line"],
    "Line": ["Expression", "Statement"],
    "Statement": ["VariableDeclaration", "Call", "With", "Invocation"],
    "Expression": ["Value", "Parenthetical", "Operation", "Assign"],
    "Identifier": ["IDENTIFIER"],
    "Literal": ["String", "Number"],
    "Value": ["Literal", "ParenthesizedInvocation"],
    "Accessor": [". Property"],
    "ParenthesizedInvocation": ["Value ParenthesizedArgs"],
    "Invocation": ["Value ArgList"],
    "Call": ["CALL ParenthesizedInvocation"],
    "ParenthesizedArgs": ["( )", "( ArgList )"],
    "ArgList": ["Arg", "ArgList , Arg"],
    "Arg": ["Expression", "NamedArg"],
    "NamedArg": ["Identifier := Value"],
    "Parenthetical": ["( Expression )"],
    "Operation": ["Expression + Expression", "Expression - Expression"]
}

//precedence
[
  ['right', 'RETURN'],
  ['left', ':='],
  ['left', '='],
  ['left', 'IF'],
  ['left', 'ELSE', 'ELSE_IF'],
  ['left', 'LOGICAL'],
  ['left', 'COMPARE'],
  ['left', '&'],
  ['left', '-', '+'],
  ['left', 'MOD'],
  ['left', '\\'],
  ['left', '*', '/'],
  ['left', '^'],
  ['left', 'CALL'],
  ['left', '(', ')'],
  ['left', '.'],
]

In my implementation i need function calls like this (with parenthesis and comma separated):

Foo(1, 2)
Foo 1, 2

And be able to use regular parenthesis for priority of operations. Even in function calls (but only in parenthesized function calls):

Foo(1, (2 + 4) / 2)
Foo 1, 2

Function call without parenthesis treated as statement, function call with parenthesis treated as expression.

How can i solve this conflict?


Solution

  • In VBA, function call statements (as opposed to expressions) have two forms (simplified):

     CALL name '(' arglist ')'
     name arglist
    

    Note that the second one does not have parentheses around the argument list. That's precisely to avoid the ambiguity of:

    Func (3) 
    

    which is the ambiguity you're running into.

    The ambiguity is that it is not clear whether the parentheses are parentheses which surround an argument list, or parentheses which surround an parenthesized expression. That's not an essential ambiguity, since the result is effectively the same. But it's still important because of the possibility that the program continues like this:

    Foo (3), (4)
    

    in which case, it is essential that the parentheses be parsed as parentheses surrounding a parenthesized expression.

    So one possibility is to modify your grammar to be similar to the grammar in the VBA reference:

    call-statement = "Call" (simple-name-expression / member-access-expression / index-expression / with-expression)
    call-statement =/ (simple-name-expression / member-access-expression / with-expression) argument-list
    

    But I suppose that you really want to implement a language similar to VBA without being strictly conformant. That makes things slightly more complicated.

    As a first approximation, you can require that the form name '(' [arglist] ')' have at least two arguments (unless it's empty):

    # Not tested
    "Invocation": ["Literal '(' ArgList2 ')' ", "Literal '(' ')' ", "Literal ArgList"],
    "ArgList": ["Arg", "ArgList2"],
    "ArgList2": ["Arg ',' Arg", "ArgList2 ',' Arg"],