Left recursion elimination in an LL1 grammar

Question

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.

There are well-documented methods for removing left recursion: what have you tried? — user439793
Why do you think you need expression in fragment at all? — user2357112 supports Monica
Changed the question to reflect what I've tried. Part of the problem I'm having is the wording, examples I've read use productions like A -> Ab |c to illustrate, but I'm finding it very difficult to link the parts of the grammar above to their respective parts in the tutorials. — Saf
user2357112, its a grammar we've been set, we can change it if we can make a case for the change. Would it not fundamentally change what the grammar could accept if I just removed expression from fragment? — Saf
Yep. And because that's too short to be a comment, double yep. — user2357112 supports Monica

Theodore Norvell Theodore Norvell · Accepted Answer · 2013-12-04T21:10:37

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.

Left recursion elimination in an LL1 grammar

1 Answers