Compiler Design for the GATE Exam — Chinese candidates

Common failure modes

These are the patterns that cause most candidates to lose marks on this topic. Recognising them in advance is half the work.

• !Computing FIRST sets incorrectly when a production has nullable symbols
• !Building FOLLOW sets without including the eof ($) marker for the start symbol
• !Misclassifying parsing conflicts: shift-reduce vs reduce-reduce in an LR parsing table
• !Confusing LL(1) conflict conditions with LR(0) conflict conditions
• !Generating incorrect three-address code by misordering temporaries in expressions

Study tips

• 1Practise FIRST and FOLLOW set computation on at least 10 different grammars — errors here cascade into parser table construction.
• 2For LL(1) parsing, verify the LL(1) condition: no two rows for the same non-terminal have the same terminal in their selection sets.
• 3Build the canonical LR(0) item sets and SLR parsing table for a small grammar (4–5 productions) from scratch.
• 4Memorise the precedence of common code optimisation techniques: constant folding → dead-code elimination → common-subexpression elimination → loop invariant code motion.
• 5Practice syntax-directed translation: attribute grammars, S-attributed vs L-attributed, and evaluating inherited vs synthesised attributes.
• 6中国考生备考 GATE 时，建议优先攻克英语听力与写作两个最易失分的板块 — 每日固定时段做真题模拟。

Sample GATE Compiler Design questions

These sample items mirror the format and difficulty of real GATE questions. Practice with thousands more on the free Koydo question bank.

1. 1

   For the grammar S → aAb | b and A → aA | ε, FIRST(S) is:

   • A{a}
   • B{a, b}Correct
   • C{a, b, ε}
   • D{a, ε}
   Why this answer?

   (GATE CS style) From S → aAb: FIRST starts with 'a'. From S → b: FIRST includes 'b'. S cannot derive ε, so ε ∉ FIRST(S). Therefore FIRST(S) = {a, b}.

2. 2

   Which of the following is a shift-reduce conflict in an LR parser?

   • ATwo items want to reduce by different productions on the same lookahead
   • BOne item wants to shift and another wants to reduce on the same lookaheadCorrect
   • CTwo items want to shift on the same lookahead
   • DAn item set has no actions defined for a terminal
   Why this answer?

   (GATE CS style) A shift-reduce conflict occurs when, for the same lookahead symbol, the parser can either shift the symbol onto the stack or reduce by a production. This makes the grammar ambiguous for LR(0)/SLR parsing without additional lookahead.

Frequently asked questions

Related study guides

• Data Structures for GATE (China)Another GATE topic for Chinese candidates
• Algorithms for GATE (China)Another GATE topic for Chinese candidates
• Theory of Computation for GATE (China)Another GATE topic for Chinese candidates
• Computer Organization & Architecture for GATE (China)Another GATE topic for Chinese candidates
• Operating Systems for GATE (China)Another GATE topic for Chinese candidates
• Compiler Design for GATE — U.S. candidatesSame Compiler Design topic, different locale framing
• Compiler Design for GATE — U.K. candidatesSame Compiler Design topic, different locale framing
• Compiler Design for GATE — Indian candidatesSame Compiler Design topic, different locale framing