The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
1.1k views

For the grammar below, a partial $LL(1)$ parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. $\varepsilon$ is the empty string, \$ indicates end of input, and, $\mid$ separates alternate right hand sides of productions.

  • $S\rightarrow a A b B \mid b A a B \mid \varepsilon$
  • $A\rightarrow S$
  • $B\rightarrow S$
  a b $
$S$ E1 E2 $S\rightarrow \varepsilon $
$A$ $A\rightarrow S$ $A\rightarrow S$ error
$B$ $B\rightarrow S$ $B\rightarrow S$ E3

The FIRST and FOLLOW sets for the non-terminals $A$ and $B$ are


  1. $\text{FIRST}(A) = \{a, b, \varepsilon\} =\text{FIRST}(B)$
    $\text{FOLLOW}(A) = \{a, b\}$
    $\text{FOLLOW}(B) = \{a, b, \$\}$
     

  2. $\text{FIRST}(A) = \{a, b, \$\}$
    $\text{FIRST}(B) = \{a, b, \varepsilon\}$
    $\text{FOLLOW}(A) = \{a, b\}$
    $\text{FOLLOW}(B) = \{\$\}$
     

  3. $\text{FIRST}(A) = \{a, b, \varepsilon\} =\text{FIRST}(B)$
    $\text{FOLLOW}(A) =\{a, b\}$
    $\text{FOLLOW}(B) = \varnothing$
     

  4. $\text{FIRST}(A) = \{a, b\} = \text{FIRST}(B)$
    $\text{FOLLOW}(A) = \{a, b\}$
    $\text{FOLLOW}(B) =\{a, b\}$
asked in Compiler Design by Boss (18.1k points)
edited by | 1.1k views

3 Answers

+13 votes
Best answer

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

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

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

So, the answer to question 52 is option A.
 

answered by Boss (31.6k points)
edited by
+1
How can we now that the production to entered in E3 is B=>S and not B=>∊ ? Precisely, how do we decide to be inser B=>∊ versus some other production. For S at M[S, $], the production entered is S=>∊. What is the difference?
+5 votes
Q 52 : ans is A.

first we can easly find.

follow of A = {a,b}, all symbols appeared after A in RHS

follow of B = {a,b,\$}, as B is at the end in RHS, follow(B) = follow (S) and S is also at the end in RHS so follow(S) = follow(A) = {a,b} and S is start symbol, so its follow contains \$ also.

hence, follow(B) = {a,b,\$}

Q 53.

ans is C.
answered by Loyal (8.2k points)
–2 votes
Q52 answer - D

Q53 answer - A
answered by Loyal (9k points)
Answer:

Related questions



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

39,751 questions
46,766 answers
140,658 comments
58,520 users