GATE CS Parsing (LL, LR) questions

Which of the following statements is/are true?

Consider the control flow graph shown in the figure. Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B$4$ and B$5$? Note: All the variables are integers.

Which of the following grammars is/are ambiguous?

Consider the canonical $L R(0)$ parsing of the grammar below using terminals $\{a, b, c\}$ and non-terminals $\{A, B, C, S\}$ with $S$ as the start symbol. $$\begin{array}{l} S \rightarrow A C B \\ A \rightarrow a A \mid \epsilon \\ C \rightarrow c C \mid \epsilon \\ B \rightarrow b B \mid b \end{array}$$ Which one of the following options gives the …

Which of the following statement(s) is/are TRUE while computing $\operatorname{First}$ and $\operatorname{Follow}$ during top down parsing by a compiler?

Consider two grammars $G_{1}$ and $G_{2}$ with the production rules given below: $G_{1} : S \rightarrow$ $if$ $E$ $then$ $S$ $|$ $if$ $E$ $then$ $S$ $else$ $S$ $|$ $a$ $E \rightarrow b$ $G_{2} :S \rightarrow$ $if$ $E$ $then$ $S$ $|$ $M$ $M \rightarrow$ $if$ $E$ $then$ $M$ $else$ $S$ $|$ $c$ …

​​Given a Context-Free Grammar $\text{G}$ as follows: $$\begin{array}{l} S \rightarrow A a|b A c| d c \mid b d a \\ A \rightarrow d \end{array}$$ Which ONE of the following statements is TRUE?

Which of the following is/are Bottom-Up Parser(s)?

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below. …

Let $G=(V, \Sigma, S, P)$ be a context-free grammar in Chomsky Normal Form with $\Sigma=\{a, b, c\}$ and $V$ containing $10$ variable symbols including the start symbol $S$. The string $w=a^{30} b^{30} c^{30}$ is derivable from $S$. The number of steps (application of rules) in the derivation $S \rightarrow^* w$ is __________.

​​​​Consider a context-free grammar $\text{G}$ with the following $3$ rules. $$S \rightarrow a S, S \rightarrow a S b S , S \rightarrow c$$ Let $w \in L(G)$. Let $n_{a}(w), n_{b}(w), n_{c}(w)$ denote the number of times $a, b, c$ occur in $w$, respectively. Which of the following statements is/are TRUE?

Consider the following augmented grammar, which is to be parsed with a $\text{SLR}$ parser. The set of terminals is $\{a, b, c, d, \#, @\}$ $$\begin{array}{l} S^{\prime} \rightarrow S \\ S \rightarrow S S|A a| b A c|B c| b B a \\ A \rightarrow d \# \\ B \rightarrow @ \end{array}$$ Let …

Which one of the following statements is $\text{TRUE}?$

Consider the augmented grammar with $\{ +, {\ast}, (,),\text{id} \}$ as the set of terminals. $S’ \rightarrow S$ $S \rightarrow S + R\; |\; R$ $R \rightarrow R {\ast} P \;| \;P$ $P \rightarrow (S)\; |\; \text{id}$ If $I_{0}$ is the set of two $\textit{LR}(0)$ items $\{ [S’ \rightarrow S.], [S \rightarrow S. + R] \}$, then …

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$. Which one of the following options is correct?

Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$. …

Consider the following augmented grammar with $\{ \#, @, <, >, a, b, c \}$ as the set of terminals. $$\begin{array}{l} S’ \rightarrow S \\ S \rightarrow S \# cS \\ S \rightarrow SS \\ S \rightarrow S @ \\ S \rightarrow < S > \\ S \rightarrow a \\ S \rightarrow b \\ S \rightarrow c \end{array}$$Let …

Consider the following grammar. $S \rightarrow aSB \mid d$ $B \rightarrow b$ The number of reduction steps taken by a bottom-up parser while accepting the string $aaadbbb$ is ___________.

Which one of the following kinds of derivation is used by LR parsers?

Consider the augmented grammar given below: $S’ \rightarrow S$ $S \rightarrow \langle L \rangle \mid id$ $L \rightarrow L, S \mid S$ Let $I_0 = \text{CLOSURE} (\{[S’ \rightarrow \cdot S ]\}).$ The number of items in the set $\text{GOTO} (I_0, \langle \: )$ is______