parsingrecursioncompiler-constructionautomatapushdown-automaton

confusion in finding first and follow in left recursive grammar

Recently I faced the problem for finding first and follow 

S->cAd
A->Ab|a

Here I am confused with first of A which one is correct {a} , {empty,a} as there is left recursion in A's production . I am confused whether to include empty string in first of A or not Any help would be appreciated. -------------edited---------------

what wil be the first and follow of this ,,This is so confusing grammar i have ever seen

S->SA|A
A->a

I need to prove this grammar is not in LL(1) using parsing table but unable to do because i didnot get 2 entry in single cell.

Solution

  • Firstly,you'll need to remove left-recursion leading to 

    S -> cAd
A -> aA'
A' -> bA' | epsilon

    Then, you can calculate 

    FIRST(A) = a         // as a is the only terminal nderived first from A.

    EDIT :-

    For your second question,

    S -> AS'
S' -> AS' | epsilon
A -> a

FIRST(A) = a
FIRST(S) = a
FIRST(S') = {a,epsilon}.

    The idea of removing left-recursion before calculating FIRST() and FOLLOW() can be learnt here.