Redirected
in Compiler Design edited by
5,166 views
1 vote
1 vote
How to find FIrst and Follow in following case?
S -> aAbB | bAaB | epsilon
A -> S
B -> S

I am little confused because of the production A->S, does it say that Follow(A) is subset of Follow(S) or Follow(S) is subset of Follow(A) or both are equal?
in Compiler Design edited by
5.2k views

4 Comments

Got it but 2 entries would be under (A,a) and (A,b)
0
0
Under (S,a) entry : S$\rightarrow$aAbB, S$\rightarrow$ϵ

Under (S,b) entry : S$\rightarrow$bAaB, S$\rightarrow$ϵ

Under (A,a) and (A,b) : A$\rightarrow$S
0
0

no ..under (A,a) and(A,b)...we would get...A->S   First of S(a,b)

similarly   under (B,a) and (B,b)....B->S

0
0

7 Answers

5 votes
5 votes
First(S) = { a,b,epsilon}

First(A) = First(S)

First(B) = First(S)

Now,

Follow(A) = { a, b}

Follow(S) = { dollar } + Follow(A) = { dollar,a,b}

Follow(B) = Follow(S)

That means follow(A) is subset of follow(S)
edited by

2 Comments

And Follow(B)=Follow(S) only because there are both productions B->S and S->aAbB | bAaB, i guess.
Thanks. This helps!
0
0
Follow(B) = Follow(S) is becoz of only S->aAbB | bAaB  not B->S

B->S implies   Follow(S)=Follow(B)
0
0
1 vote
1 vote

$First (S) = First(A) = First(B)= {\{a, b, \epsilon}\} \\ Follow (S)= {\{a, b, \$} \}$

$Follow (A)= {\{a, b} \}$

$Follow (B)= {\{a, b, \$} \}$

LL(1) Parse Table:

  $a$ $b$ $
$S$

$S\rightarrow aAbB$

$S\rightarrow \epsilon$

$S\rightarrow bAaB$

$S\rightarrow \epsilon$

$S\rightarrow \epsilon$
$A$ $A\rightarrow S$ $A\rightarrow S$  
$B$ $B\rightarrow S$ $B\rightarrow S$ $B\rightarrow S$

2 multiple entries

Hence 2 is the correct answer

edited by

4 Comments

but indirectly A is driving epsilon
0
0
Yes, it is driving but we didn't add it into the table, we add only those entries present in grammar.

See LL(1) is a predictive parser, on the basis of current input symbol it decides which grammar production it will select.

Suppose at any instant when next input symbol is 'a' which is in first of A then production A->S is selected by parser

LL(1) table contains only productions present in grammar
1
1
thanks !
0
0
1 vote
1 vote

 $S \rightarrow aAbB \ \ \ \ \ \ \ ..... 1   $ 
$S \rightarrow bAaB \ \ \ \ \ \ \ ..... 2   $
$S \rightarrow \epsilon \ \ \ \ \ \  \ \  \ \ \ \ \ \ \ \ ..... 3   $ 
$A \rightarrow S \ \ \ \ \ \  \ \  \ \ \ \ \ \ \  ..... 4   $
$B \rightarrow S \ \ \ \ \ \  \ \  \ \ \ \ \ \ \  ..... 5   $

 

FIRST FOLLOW  NON-TERMINAL a b $
$\{ a, b, \epsilon  \}$ $\{ \$,b,a \}$ S  1 / 3 2 / 3 3
$\{ a, b, \epsilon  \}$ $\{b,a \}$ A 4 / 4 4 / 4  
$\{ a, b, \epsilon  \}$ $\{ \$,b,a \}$ B 5 / 5 5 / 5

 

$$\begin{array}{|l|l|l|l|l|}\hline \textbf{FIRST}&\textbf{FOLLOW}&\textbf{NON-TERMINAL}&\textbf{a}&\textbf{b}&\textbf{\$}\\\hline \{a,b,\epsilon\}&\{\$,b,a\}&\text{S}&1/3&2/3&3\\\hline \{a,b,\epsilon\}&\{b,a\}&\text{A}&4/4&4/4&\\\hline \{a,b,\epsilon\}&\{\$,b,a\}&\text{B}&5/5&5/5&5\\\hline\end{array}$$

There are 2 entries with multiple different productions which results in First/First conflict.

however there are 6 multiple entries in the table.

edited by
0 votes
0 votes
First of S={a,b,epsilon}

First of A={a,b,epsilon}

First of B={a,b,epsilon}

Follow::

Follow of S=   {$}

Follow of A=  {a,b}

Follow of B=   {$}