CODEWITHSUNDEEP
parsingcompiler-constructionll-grammarleft-recursion
webchatowner
webchatowner

Reputation: 155

How Do I left factor and eliminate left recursion?

My Production rules are as follows:

S → id = Exp
S → id (Arglist)
Arglist → Arglist , Exp
Arglist → Exp
Exp → id (Arglist)
Exp → id

This is my first attempt:

S -> id S'
S' -> ϵ | = EXP | (Arglist)
Arglist -> Arglist'
Arglist' -> ϵ | ,Exp Arglist'
Exp -> id Exp'
Exp' -> ϵ | (Arglist)

My problem is with the Arglist production rule, I am wrong.

Upvotes: 0

Views: 76

Answers (1)

rici
rici

Reputation: 241911

You just need to change Arglist to being right-recursive, which will recognise the same language (with a slightly different parse tree):

Arglist → Exp , Arglist
Arglist → Exp

Then left-factor:

Arglist → Exp Arglist'
Arglist' → ε | , Exp Arglist'

Upvotes: 2

Related Questions