We're using GPPG (essentially bison for C#) to generate a parser for a programming language. Everything is going great except for one really nasty bit. The language we are parsing has a sort of "implicit comparison" rule, where "expression expression" should be interpreted as "expression == expression".
For example, this is a perfectly valid statement:
If SomeValue False Then
EndIf
This obviously introduces all sorts of conflicts during parser generation. My first attempt at solving them went something along these lines (edited for brevity). I tried to do some refactoring of the rules, and it doesn't seem to be ambiguous anymore, but I must just be missing something obvious.
Here is a very small grammar that shows the conflict I'm having, and how I've attempted to solve it, doesn't work though
%start program
%token <Token> Plus
%token <Token> Times
%token <Constant> Constant
%left Plus
%left Times
%left IMPLICIT_COMPARISON
%%
program: expression;
expressionBase: Constant
| expression Plus expression
| expression Times expression;
expression: expressionBase
| expression expressionBase %prec IMPLICIT_COMPARISON;
%%
Any help would be greatly appreciated
How about this:
program: expression;
expressionBase: Constant
| expressionBase Plus expressionBase
| expressionBase Times expressionBase;
expression: expressionBase
| expressionBase expression;
You need to build the grammar from bottom to top, not mixing your low-level concepts (like expressionBase) amd high-level ones (like expression). The high-level ones are build with the low-level ones. If you need it the other way around, you have to clearly delimit the high-level concept with parentheses or some such, like below:
expressionBase: Constant
| expressionBase Plus expressionBase
| expressionBase Times expressionBase
| LeftParen expression RightParen;
The actual rules are rather more complicated but this should get you started.