parsingcompiler-constructionll-grammarleft-recursion

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.

Solution

  • 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'