GATE CSE · Compiler Design

Parsing Practice Questions

Master topic for Parsing. Includes Syntax Analysis, Top-Down Parsing, Bottom-Up Parsing, Error Detection & Recovery.

143 questions · 6 PYQs · 14 AI practice · GATE CSE 2027

Q81MCQ

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

🚀 Solve in Practice Mode

📖 Explanation

A grammar is defined as ambiguous if there exists at least one string in the language that has more than one distinct leftmost derivation or parse tree. The presence of left recursion ( $A \to A\alpha$ ) and right recursion ( $A \to \beta A$ ) in a grammar does not inherently guarantee ambiguity, nor does it preclude it. For example, the grammar $S \to aS \mid Sa \mid a$ is ambiguous because the string $aa$ has two distinct derivations. However, it is possible to construct unambiguous grammars containing both left and right recursive rules, provided the structure ensures a unique derivation for every string. Since the ambiguity depends on the specific interaction of all production rules within the grammar, the presence of both recursion types is not sufficient information to determine if the grammar is ambiguous or unambiguous.

Q82MCQ

Which of the following statements is true?

🚀 Solve in Practice Mode

📖 Explanation

The hierarchy of power among LR parsers is strictly defined as $SLR(1) \subset LALR(1) \subset LR(1)$ . While $LALR(1)$ parsers merge states of an $LR(1)$ parser to reduce table size, this compression can introduce reduce-reduce conflicts that are not present in the original $LR(1)$ parser. Consequently, the Canonical LR ( $LR(1)$ ) parser is strictly more powerful than the $LALR(1)$ parser, as it can parse a larger class of grammars without ambiguity. Therefore, statement C is the correct relationship.

Q84MCQ

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

🚀 Solve in Practice Mode

📖 Explanation

The grammar is ambiguous because it contains the classic "dangling else" problem, where the else clause can be associated with either the first or the second if. Specifically, for the sentence $\text{ if a then if b then c:= d else c:= f }$ , there are two valid interpretations (parse trees):

The else attaches to the inner if: $\text{ if a then } (\text{ if b then c:= d else c:= f })$ .
The else attaches to the outer if: $\text{ if a then } (\text{ if b then c:= d }) \text{ else } (\text{ c:= f })$ .
Since the existence of two distinct parse trees for a single string defines ambiguity, Option D is the correct description.