6

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.

rajkumar
  • 365
  • 5
  • 10
  • I already mentioned to ask another question as it's too broad to include second part. Ask second afresh so that a broad answer for why this is not in LL(1) can be given! By the way, I have added left-recursion for you for the 2nd question... – Am_I_Helpful Dec 30 '14 at 08:14
  • Thanks @shekar suman .please help in this http://stackoverflow.com/questions/27703952/how-to-prove-left-recursion-grammar-is-not-in-ll1-using-parsing-table – rajkumar Dec 30 '14 at 10:44

1 Answers1

2

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.

Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
  • Thanks shekhar suman for your nice answer . I understand your explanation. – rajkumar Dec 30 '14 at 07:12
  • Is grammar LL(1)? Can anyone explain?? – John Dec 29 '18 at 18:40
  • Hi @John, sorry for the late reply. Please go through this question: https://stackoverflow.com/q/8496642/3482140, and let me know if you've difficulty evaluating whether the aforementioned grammar is LL(1) or not! – Am_I_Helpful Jan 01 '19 at 13:02
  • Thanks @Am_I_Helpful for your effort but I got my answer already. – John Jan 02 '19 at 08:38