search
Log In
3 votes
334 views

GATE CSE 2021 Set 1 | Question-6.8

  1. GATE CSE 2021 Set 1 | Question-30
  2. GATE CSE 2021 Set 1 | Question-30
  3. GATE CSE 2021 Set 1 | Question-30
  4. GATE CSE 2021 Set 1 | Question-30

Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$. $$\begin{array}{lll} S & \rightarrow & d \: a \: T \mid R \: f \\ T & \rightarrow & a \: S \: \mid \: b \: a \: T \: \mid \epsilon \\ R & \rightarrow & c \: a \: T \: R \: \mid \epsilon \end{array}$$

The following is a partially-filled $LL(1)$ parsing table.

$$\begin{array} {c c c }  & a & b & c & d & f & \$ \\\hline  S & & & \bigcirc{1} & S \rightarrow daT & 2 & \\\hline T & T \rightarrow aS & T \rightarrow baT & 3 &  & T \rightarrow \varepsilon & 4\\\hline R &  & & R \rightarrow caTR & &   R \rightarrow \varepsilon &  \end{array}$$

Which one of the following choices represents the correct combination for the numbered cells in the parsing table (“blank” denotes that the corresponding cell is empty)?

  1. $1\;S \rightarrow Rf \qquad 2\;S \rightarrow Rf \qquad 3\; T \rightarrow \varepsilon \qquad 4\;T \rightarrow \varepsilon$
  2. $1\;\text{blank} \qquad 2\;S \rightarrow Rf \qquad 3\; T \rightarrow \varepsilon \qquad 4\;T \rightarrow \varepsilon$
  3. $1\;S \rightarrow Rf  \qquad 2\;\text{blank} \qquad 3\; \text{blank} \qquad 4\;T \rightarrow \varepsilon$
  4. $1\;\text{blank} \qquad 2\;S \rightarrow Rf \qquad 3\; \text{blank} \qquad 4\;\text{blank} $
in Compiler Design
recategorized ago by
334 views
0
Option A?
1

 yes A

2 Answers

2 votes
  FIRST Follow
$S \rightarrow daT / Rf$ $\left \{ d,c,f \right \}$ $\left \{ c,f,\$ \right \}$
$T \rightarrow aS / baT/ \varepsilon $ $\left \{ a,b,\varepsilon \right \}$ $\left \{ c,f,\$ \right \}$
$R \rightarrow caTR/ \varepsilon $ $\left \{ c,\varepsilon \right \}$ $\left \{ f \right \}$

 

  a b c d f $
S     $S \rightarrow Rf$ --(1) $S \rightarrow daT$ $S \rightarrow Rf$ --(2)  
T $T \rightarrow aS  $ $T \rightarrow  baT $ $T \rightarrow  \varepsilon $ –- (3)   $T \rightarrow  \varepsilon $ $T \rightarrow  \varepsilon $ –- (4)
R     $R \rightarrow caTR$   $R \rightarrow  \varepsilon $  

Ans : A  (1) $S \rightarrow Rf$  (2) $S \rightarrow Rf$ (3) $T \rightarrow  \varepsilon $ (4) $T \rightarrow  \varepsilon $

1 vote

 

Ans: A  (1) S→Rf (2) S→Rf (3) T→ε (4) T→ε

Answer:

Related questions

1 vote
2 answers
1
392 views
Consider the following statements. $S_1$: Every $\text{SLR(1)}$ grammar is unambiguous but there are certain unambiguous grammars that are not $\text{SLR(1)}$. $S_2$: For any context-free grammar, there is a parser that takes at most $O(n^3)$ time to parse a string of length $n$. ... $S_2$ is false $S_1$ is false and $S_2$ is true $S_1$ is true and $S_2$ is true $S_1$ is false and $S_2$ is false
asked Feb 18 in Compiler Design Arjun 392 views
0 votes
2 answers
2
896 views
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation $\text{(SDT)}$ ... The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions. The actions will lead to an infinite loop
asked Feb 18 in Compiler Design Arjun 896 views
1 vote
2 answers
3
338 views
Consider the following $C$ code segment: $\begin{array}{lllll} a & = & b & + & c; \\ e & = & a& + & 1; \\ d & = & b & + & c; \\ f & = & d& + & 1; \\ g& = & e&+&f; \end{array}$ a = b + c; e = a + 1; d = b + c; f = d + 1; g = e + f; In a compiler, this code segment is represented internally as a directed acyclic graph $\text{(DAG)}$. The number of nodes in the $\text{DAG}$ is _____________
asked Feb 18 in Compiler Design Arjun 338 views
39 votes
5 answers
4
8.2k views
Consider the following grammar G $S \rightarrow F \mid H$ $F \rightarrow p \mid c$ $H \rightarrow d \mid c$ Where $S$, $F$, and $H$ are non-terminal symbols, $p, d$, and $c$ are terminal symbols. Which of the following statement(s) is/are correct? S1 ... are generated using grammar G S2: LR(1) can parse all strings that are generated using grammar G Only S1 Only S2 Both S1 and S2 Neither S1 and S2
asked Feb 15, 2015 in Compiler Design jothee 8.2k views
...