Given CFG G: S → Aa | bAc | dc | bda; A → d. Which ONE of the following is TRUE?

Correct Answer: (C) LALR(1) but not SLR(1)SLR(1) conflict: In a state containing both S→d·c and A→d·, when lookahead is 'c': FOLLOW(A) = {a, c} (since S→Aa and S→bAc). SLR(1) sees 'c' ∈ FOLLOW(A) → reduce, AND 'c' could shift for S→d·c → shift. Shift-reduce conflict: NOT SLR(1).LALR(1): In LALR(1), the exact lookahead for A→d· in the relevant state is {a} only (not {c}), because the state where A→d appears as A→d (in context S→bAc) has lookahead {c}, while in context S→Aa it has lookahead {a}. When merged into LALR(1), the conflict disappears. G IS LALR(1).

GATE-CS is a competitive examination conducted in India. This question is from the 2025 GATE-CS Compiler Design paper.

How can I prepare for GATE-CS Compiler Design?

To prepare for GATE-CS Compiler Design, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2025 question covers Parsing (Top-Down and Bottom-Up) topic.

What is the difficulty level of this question?

This GATE-CS 2025 Compiler Design question has a hard difficulty level and is marked as an important question.

Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

GATE-CS Compiler Design 2025 - Given CFG G: S → Aa | bAc...

Consider the canonical LR(0) parsing of the grammar below using terminals {a, b, c} and non-terminal…

HARD2026GATE-CSCompiler Design

Which of the following statements is/are true?(A) LL(1) parser uses backtracking.(B) For a grammar t…

MEDIUM2026GATE-CSCompiler Design

G1: S → if E then S | if E then S else S | a; E → bG2: S → if E then S | M; M → if E then M else S |…

HARD2025GATE-CSCompiler Design

Which of the following statement(s) is/are TRUE while computing First and Follow during top down par…

MEDIUM2025GATE-CSCompiler Design

Consider the operator precedence and associativity rules for integer arithmetic operators: '+' has H…

HARD2024GATE-CSCompiler Design

Consider the grammar G with S as start symbol. Three productions are incomplete: S --> daT | (1), T …

HARD2024GATE-CSCompiler Design

Given CFG G: S → Aa | bAc | dc | bda; A → d. Which ONE of the following is TRUE?

Master GATE-CS with Our Test Series

More Questions from Parsing (Top-Down and Bottom-Up)

Frequently Asked Questions

Given CFG G: S → Aa | bAc | dc | bda; A → d. Which ONE of the following is TRUE?

Master GATE-CS with Our Test Series

More Questions from Parsing (Top-Down and Bottom-Up)

Frequently Asked Questions