Search code examples
parsinghaskellbisonyacchappy

Ambiguous grammar and possible fixes

So I have this grammar for a language, the grammar certainly contains some ambiguity however I am finding it a bit unusually difficult to fix this one. Below is the BNF grammar of the language and below that part of my happy parser file.

BNF of the proposed language:

<program> ::=                                   Skel program
      "program" <id> ":" <pars> "."

--> <pars> ::=
      <par> [";" <pars>]                        parallel statements

<par> ::=
    "func" <id> <structs>                       structured expression
--> |   <pars> "||" <pars>                          parallel pipeline
|   "farm" <int> <pars>                         task farm

--> <structs> ::=
    <struct> [";" <structs>]                    statements

<struct> ::=
      <exprs>                                   expression
--> |     <structs> "•" <structs>                   composition
|     "iter" <int> <structs>                    iteration

--> <exprs> ::=
      <expr> ["," <exprs>]                      expressions

<expr> ::=
    <int>                                       integer value
    |  <string>                                 string value
    |  <bool>                                   boolean value
    |  <id> [ "=" <exprs> ]                     identifier/assignment
    |  "raise" <id> "=" <exprs>                 raise exception
    |  <exprs> "catch" <id> <id> ":" <exprs>    catch exception
    |  <exprs> <op> <exprs>                     binary operator
    |  "(" <exprs> ")"                          grouping

<op> ::=                        operators
    "+" | "*" | "-" | "div"| "<"| "<=" | "==" | "!="

Parser.y

TProgram: program ID ':' TPars '.'    { Program $2 $4 }

TPars   : TPar ';'                    {   [$1]  }
        | TPars TPar                  { $2 : $1 }

TPar    : func ID TStructs            { Function $2 $3   }
      --| "||" TPars                  { Parall $2        }
        | farm DIGIT TPars            { Farm $2 $3       }

TStructs: TStruct ';'                 {  [$1]  }
        | TStructs TStruct            { $2 : $1 }

TStruct : TExprs                      { ExprList $1   }
      --| '•' TStructs                { CompOp $2     }
        | iter DIGIT TStructs         { Iter $2 $3    }

TExprs  : TExpr                       {   [$1]    }
        | TExprs ',' TExpr            {  $3 : $1  }

BinExpr : Term                        {  $1  }
        | BinExpr Op BinExpr          { BinOp $2 $1 $3  }

Op      : '/'                         { Divide }
        | '*'                         { Times  }
        | '-'                         { Minus  }
        | '+'                         { Plus   }

Term    : ID                          { Var $1 }
        | DIGIT                       { Digit $1 }
        | FLOAT                       { Float $1 }

TExpr   : '(' TExprs ')'              { ParenExpr $2 }
        | true                        { Bool $1  }
        | false                       { Bool $1  }
        | ID '=' TExprs               { Assign $1 $3  }
        | raise ID '=' TExprs         { Raise $2 $4   }
        | BinExpr                     {  $1  }

Edit : I've added arrows to the BNF format showing what I believe is causing the ambiguity in the grammar.

Solution

  • So, how would you want

    a = true, false

    to get parsed? It could be

    (a=true), false

    or

    a = (true, false)

    If this was yacc, I would suggest to resolve the conflict by giving '=' and ',' associativity and precedence with the %right %left and %nonassoc pragmas, maybe Happy supports something like this.