GATE CS Parsing (LL, LR) questions

Consider the grammar shown below. $S \rightarrow C \ C$ $C \rightarrow c \ C \mid d$ This grammar is

Assume that the SLR parser for a grammar G has $n_1$ states and the LALR parser for G has $n_2$ states. The relationship between $n_1$ and $n_2$ is

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

To evaluate an expression without any embedded function calls

Which of the following statements is false?

Given the following expression grammar: $$\begin{align} E &\to E * F \mid F + E \mid F \\[1em] F &\to F - F \mid id \end{align}$$ Which of the following is true?

Which of the following derivations does a top-down parser use while parsing an input string? The input is scanned from left to right.

A grammar that is both left and right recursive for a non-terminal, is

Which of the following is the most powerful parsing method?

Type checking is normally done during

Which of the following statements is true?

In the following grammar $X ::= X \oplus Y \mid Y$ $Y::= Z * Y \mid Z$ $Z::= id$ Which of the following is true?

The grammar whose productions are $\langle\text{stmt}\rangle \to\text{ if id then } \langle\text{stmt}\rangle$ $\langle\text{stmt}\rangle\to\text{ if id then } \langle\text{stmt}\rangle\text{ else } \langle\text{stmt}\rangle$ $\langle\text{stmt}\rangle \to\text{ id }:=\text{ id}$ is ambiguous because if a then if b then c:= d has more than two parse …

Consider a grammar with the following productions $S \rightarrow a \alpha b \mid b \alpha c \mid aB$ $S \rightarrow \alpha S\mid b$ $S \rightarrow \alpha b b\mid ab$ $S \alpha \rightarrow bd b\mid b$ The above grammar is:

Which of the following features cannot be captured by context-free grammars?

If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form?

Consider the $\text{SLR(1)}$ and $\text{LALR (1)}$ parsing tables for a context free grammar. Which of the following statement is/are true?

For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal $A$ in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" by "left sentential" and "right most sentential" respectively in the definition of FOLLOW (A).

An operator precedence parser is a

A context-free grammar is ambiguous if: