GATE CSE 2021 Set 1 | Question: 31
Arjun asked in Compiler Design Feb 18, 2021 retagged Nov 30, 2022 by Lakshman Patel RJIT
Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$. $$\begin{array}{lll} \text{S} & \rightarrow & d \: a \: \text{T} \mid \text{R} \: f \\ \text{T} & \rightarrow & a \: \text{S} \: \mid \: b \: a \: \text{T} \: \mid \epsilon \\ \text{R} & \rightarrow & c \: a \: \text{T} \: \text{R} \: \mid \epsilon \end{array}$$
The following is a partially-filled $\textsf{LL(1)}$ parsing table.$$\begin{array} {c c c } & a & b & c & d & f & \$ \\\hline \text{S} & & & \boxed{1} & \text{S} \rightarrow da \text{T} & \boxed{2} & \\\hline \text{T} & \text{T} \rightarrow a\text{S} & \text{T} \rightarrow ba\text{T} & \boxed{3} & & \text{T} \rightarrow \varepsilon & \boxed{4}\\\hline \text{R} & & & \text{R} \rightarrow ca\text{T}\text{R} & & \text{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)?
$\boxed{1}\;\text{S} \rightarrow \text{R}f \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{T} \rightarrow \varepsilon \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon$
$\boxed{1}\;\text{blank} \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{T} \rightarrow \varepsilon \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon$
$\boxed{1}\;\text{S} \rightarrow \text{R}f \qquad \boxed{2}\;\text{blank} \qquad \boxed{3}\; \text{blank} \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon$
$\boxed{1}\;\text{blank} \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{blank} \qquad \boxed{4}\;\text{blank} $
gatecse-2021-set1
compiler-design
2-marks
by Arjun
by zxy123
commented Feb 18, 2021
Option A?
by Mk Utkarsh
zxy123 yes A
$\begin{array}{|c|c|c|}\hline
&\textsf{FIRST}&\textsf{FOLLOW}\\\hline
S \rightarrow daT \mid Rf & \left \{ d,c,f \right \} & \left \{ c,f,\$ \right \} \\\hline
T \rightarrow aS \mid baT \mid \varepsilon & \left \{ a,b,\varepsilon \right \} & \left \{ c,f,\$ \right \} \\ \hline
R \rightarrow caTR\mid \varepsilon & \left \{ c,\varepsilon \right \} & \left \{ f \right \} \\\hline
\end{array}$
$\begin{array}{|c|c|c|c|c|c|c|}\hline
&a&b&c&d&f&\$ \\ \hline
S & & &\underset{\boxed{1}} {S \rightarrow Rf}& S \rightarrow daT &\underset{\boxed{2}}{S \rightarrow Rf}& \\ \hline
T & T \rightarrow aS & T \rightarrow baT & \underset{\boxed{3}}{T \rightarrow \varepsilon} &&T \rightarrow \varepsilon & \underset{\boxed{4}}{T \rightarrow \varepsilon} \\ \hline
R & && R \rightarrow caTR && R \rightarrow \varepsilon \\ \hline
Ans: A (1) $S \rightarrow Rf\quad$ (2) $S \rightarrow Rf\quad$ (3) $T \rightarrow \varepsilon \quad$ (4) $T \rightarrow \varepsilon $
Bhargav D Dave 6 answered Feb 19, 2021 selected May 31, 2021 by Arjun
by Bhargav D Dave 6
by Pranavpurkar
commented Nov 24, 2022
In $1$ and $2$ , s→ $\epsilon$ will also be present right?
by abir_banerjee
@Pranavpurkar in 1 and 2 S->epsilon will not be present because FIRST of S does not contain epsilon .
If FIRST of a non terminal contains epsilon then we place epsilon on the FOLLOW of that non-terminal.
@abir_banerjee
Thanks bro!
Ans: A (1) S→Rf (2) S→Rf (3) T→ε (4) T→ε
Harshq answered Feb 27, 2021
by Harshq
Arjun asked in Compiler Design Feb 18, 2021
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation $\text{(SDT)}$ ... used to type-check syntactically correct boolean variable declarations and boolean expressions. The actions will lead to an infinite loop
syntax-directed-translation
Consider the following $C$ code segment: 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 _____________
code-optimization
directed-acyclic-graph
numerical-answers
GATE CSE 2021 Set 1 | Question: 5
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 ... 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
lr-parser
1-mark
Arjun asked in Quantitative Aptitude Feb 18, 2021
GATE CSE 2021 Set 1 | GA Question: 6
We have $2$ rectangular sheets of paper, $\text{M}$ and $\text{N}$, of dimensions $\text{6 cm $\times$ 1 cm}$ each. Sheet $\text{M}$ is rolled to form an open cylinder by bringing the short edges of the sheet together. Sheet $\text{N}$ is cut into equal ... of the cylinder to that of the cube is _________. $\frac{\pi}{2}$ $\frac{3}{\pi}$ $\frac{9}{\pi}$ $3\pi$
quantitative-aptitude