- #1
Jncik
- 103
- 0
Homework Statement
compute the first and follow sets of the following grammar
S -> ACB | CbB | Ba
A -> da | BC
B -> g|λ
C -> h|λ
The Attempt at a Solution
First(S) = First(ACB) U First(CbB) U First(Ba)
First(ACB) = First(A) - {λ} U First(CB)
First(CbB) = First(C) - {λ} U {b}
First(B) = {g,λ}
First(C) = {h,λ}
First(A) = {d} U First(B) - {λ} U First(C) = {d,g,h,λ}
hence First(CbB) = {h,b}
First(Ba) = {g,a}
First(ACB) = {d,g,h} U {h,b} U {g,a} = {a,b,d,g,h,e}
Follow sets:
Follow(S) = {$} since its initial
Follow(B) we have to check the following
i) S -> ACB
ii) S -> CbB
iii) S -> Ba
iv) A -> BC
i) we add Follow(S) to follow(B) since we have λ after B
hence we add {$}
ii) we add the same {$}
iii) we add {a}
iv) we add First(C) - {λ} U Follow(A) since we can get an empty string from C
hence we add {h,$}
hence Follow(B) = {a,h,$}
for Follow(A) we check S -> ACB and add First(CB) - {λ} U Follow(S)
First(CB) = First(C) - λ U First(B) = {h} U {g,λ}
hence Follow(A) = {h,g,$}
for Follow(B) we have S -> CbB and S -> Ba and A -> BC
hence we have Follow(B) = First(C) - λ U {a} U First(C) - λ U Follow(S)= {h,a,$}please is this correct?
EDIT: the follow sets are wrong, i ll update in 2 minutes
EDIT2: fixed
Last edited: