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
Define
Note that fragment is equivalent to
frag1 | expression
. Replace the former by the latter everywhere to getfragment
is no longer needed.Distribute to get
where
Now you can see that an expression is a
frag1
followed by one or moremore
So
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
to
you have a sensible grammar for expressions.