The Gateway to Computer Science Excellence
0 votes
144 views

in Compiler Design by Junior (529 points) | 144 views
0
I am getting 6 but ans given is 2

2 Answers

+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.

by Boss (35.4k points)
edited by
0 votes
  a b $
S S-->aAbB S-->bAaB S--e
A

A-->S

A--->e

A--->S

A--->e

 
B B-->S B-->S B---e
by Loyal (7.7k points)
0
I think S->epsilon will be under column a and b , since S-->epsilon needs to be put under follow(S) which is {a,b}
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,167 answers
193,833 comments
93,993 users