Thread: I need help with left recursion

I have this project and I have to eliminate left recursion from my grammar, the book gives psuedocode. I understand how the pseudocode works, but I can't figure out how to implement it.

I know that

E -> E + T
E -> T

goes to

E -> + E E'
E' -> T
E' ->

I've tried a few things, but I can't figure it out. Obviously I can't have a null token.

void Expression() :
{}
{
LOOKAHEAD(2) Expression() <OP> Expression()
| LOOKAHEAD(2) Expression() <LSBRACE> Expression() <RSBRACE>
| LOOKAHEAD(2) Expression() <DOT> <LENGTH>
| Expression() <ID> <LPAREN> ExpressionList() <RPAREN>
| <NUM>
| <TRUE>
| <FALSE>
| <ID>
| <THIS>
| LOOKAHEAD(2) <NEW> "int" <LSBRACE> Expression() <RSBRACE>
| <NEW> <ID> <LPAREN> <RPAREN>
| <NOT> Expression()
| <LPAREN> Expression() <RPAREN>
}

Oh, it's JavaCC, not Sable.

Without providing a grammar of the language it is very hard for me to tell what your code is trying to do, so if you could provide one, great.

Sorry to say but your code is seriously screwed! So this will be a hard and torturous critique:

First off, consider breaking the grammar down into more non-terminals. "Expression" is usually reserved in languages for additive operations like "a + b" and not anything more complex.

( Usually a language can be seperated as these stages, but your language may be somewhat different (it may not have blocks, for instance):

program -> block -> statement -> expression (add/sub e.g. a + b) -> term (mul/div e.g. a * b) -> factor (e.g. identifier, constant, bracketed expressions).

A statement can contain many other things other than mathematical expressions...)

Bundling all this together as an "expression" is not only ludicrous but wrong. Consider the production as given in your code:

E -> E (op) E

Valid code therefore is thus: 4 + 4 * 2

As JavaCC generated syntax analysers are left recursive, your compiler will generate a structure that will evaluate to 4 + 4 = 8, 8 * 2 = 16, rather than 4 + 8 = 12, which is right.

To avoid just this one example, instead of

E -> E (any old op) E, you need

E -> T (+ T or - T)*
T -> F (* F or / F) *
F -> NUM or ID or (E)

That way, operator precedence is observed and left recursion (and the need for a cheeky LOOKAHEAD(2)!) is removed. In code:

Code:

void expression():
{
}
{
	term()
	(
		addingOp()
		term()
	)*
}

void addingOp():
{
}
{
	<PLUS> | <MINUS>
}

void term():
{
}
{
	factor()
	(
		multOp()
		factor()
	)*
}

void multOp():
{
}
{
	<MULTIPLY> | <DIVIDE>
}

void factor():
{
}
{
	(
		constant()
	)
	|
	(
		identifier()

	)
	|
	(
		<OPEN_BRKT>
		expression()
		<CLOSE_BRKT>
	)
}

You may want to move many of your other more exotic productions to a STATEMENT non-terminal. In order to avoid type conflicts you may want to move your boolean-ish productions to a BOOLEANEXPRESSION non-terminal.

When you sort it out you should:

• NEVER have expression() on the left hand side of the production. As JavaCC makes LR(k) analysers this is lethal!
• I predict you should have no need for LOOKAHEAD(2). 1 (the default) is always preferable! In some cases k=2 is inevitable though....

PLEASE POST YOUR GRAMMAR if you want more help! And by the look of things, e.g. ignoring operator precedence, you may want to brush up on those sample grammars JavaCC so amply provides on it's homepage.

The Expression part of the grammar is as follows

Code:

Exp -> Exp op Exp
Exp -> Exp [Exp]
Exp -> Exp .length
Exp -> Exp .id (ExpList)
Exp -> INTEGER_LITERAL
Exp -> true
Exp -> false
Exp -> id
Exp -> this
Exp -> new int [Exp]
Exp -> new id ( )
Exp -> ! Exp
Exp -> ( Exp )

ExpList -> Exp ExpRest*
ExpList ->

ExpRest ->, Exp

Sorry for being so clueless, I'm not a low level guy at all, I'm a graphics guy so this is all new to me and reading the book twice doesn't help very much.

You'll never write a sensible parser out of that. As I said, there's no operator precedence and heaps of left recursion. In short it does nothing, and it does nothing spectacularly badly.

You need a new grammar. What are you trying to do? My post above should help you with putting the precedence stuff in.

The grammar doesn't do anything, it's just an exercise. That's exactly how it's written in the book. Would you like to see the rest of the grammar?

Originally Posted by ninja9578

The grammar doesn't do anything, it's just an exercise. That's exactly how it's written in the book. Would you like to see the rest of the grammar?

If you can't see what's wrong with the grammar, obviously you need to go through the basics again, I cannot help you there. It is an exercise and you therefore must do it yourself.

It's pretty easy, maybe you need a better book and/or lecturer.