Redirected
edited by
5,194 views
1 votes
1 votes
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?
edited by

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)
1 votes
1 votes

$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
1 votes
1 votes

 $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=   {$}

Related questions

1 votes
1 votes
1 answer
1
Mk Utkarsh asked Feb 1, 2018
2,632 views
Find First and Follow of the given grammar$S \rightarrow aSa | bSb|A$$A \rightarrow aBb$$B \rightarrow aB|bB|\epsilon$
0 votes
0 votes
1 answer
2
Subhrangsu asked Apr 15, 2022
2,022 views
Compute FIRST and FOLLOW sets:S→ aAC | bBA→ Abc| Abd | eB→ f | gC→ h | i
1 votes
1 votes
0 answers
3
aditi19 asked May 12, 2019
1,648 views
why do first sets can have epsilon symbol but follow sets don’t?P.S: I’ve a silly doubt :P
0 votes
0 votes
1 answer
4
saumya mishra asked Jun 3, 2018
3,113 views
Find first and follow of the given grammar?S->ABA->BS/a/€B->AS/b