I'm trying to eliminate left recursion from the following extract of a grammar -
expression := fragment ( ( + | - | * | / ) fragment )*
fragment := identifier | number | ( + | - ) fragment | expression
The issue is that expression can go to fragment, can go to expression. I've tried a bunch of ways to eliminate it, some look like they work (in JavaCC) but I'm a)unsure of their correctness, and b) pretty sure I've broken associativity by changing the structure of the grammar.
I'm pretty sure I need an expression', and have
fragment := identifier | number | ( + | - ) fragment | expression
changed to
fragment := identifier | number | ( + | - ) fragment | expressionPrime
But I'm unsure of the way to form expressionPrime. Both
expressionPrime := identifier | number | ( + | - ) fragment | {}
And
expressionPrime := ( ( + | - | * | / ) fragment )*
Seem to work, but I know it can't be both.
Any ideas would be much appreciated, even a point in the right direction.
Start with
expression ::= fragment ( ( + | - | * | / ) fragment )*
fragment ::= identifier | number | ( + | - ) fragment | expression
Define
frag1 ::= identifier | number | ( + | - ) fragment
Note that fragment is equivalent to frag1 | expression
. Replace the former by the latter everywhere to get
expression ::= (frag1 | expression) ( ( + | - | * | / ) (frag1 | expression) )*
frag1 ::= identifier | number | ( + | - ) (frag1 | expression)
fragment
is no longer needed.
Distribute to get
expression ::= frag1 more | expression more ,
where
more ::= ( ( + | - | * | / ) (frag1 | expression) )*
Now you can see that an expression is a frag1
followed by one or more more
So
expression ::= frag1 (more)+
Your grammar is still ambiguous -- there are 2 parse tress for "1 * - 2 * 3". But at least it is not left recursive anymore.
(If you use this in your assignment, be sure to cite this answer, so you don't end up breaking your institution's academic dishonesty rules.)
I still think your instructor made a mistake, since, if you change
fragment ::= identifier | number | ( + | - ) fragment | expression
to
fragment ::= identifier | number | ( + | - ) fragment | "(" expression ")" ,
you have a sensible grammar for expressions.