GATE CSE Lexical Analysis, Parsing and SDT PYQs

Core concepts

• FIRST and FOLLOW set calculation including handling of epsilon transitions
• LL(1) predictive parsing table construction and conflict conditions
• Shift-reduce bottom-up parsing, rightmost derivation in reverse, and reduction step counting
• Viable prefix definition and shift-reduce stack invariants
• LR parsing hierarchy (LR(0), SLR(1), LALR(1), CLR(1))
• Compiler front-end phases (Lexical, Syntax, Semantic) and their respective inputs, data structures, and errors
• Operator precedence and associativity translation to parse tree hierarchy
• Lexical analysis and DFA minimization
• Parsing and production/parse trees
• Register allocation via graph coloring of interference graphs
• Expression evaluation via post-order syntax tree traversal
• LR Parsing definition (Left-to-right scanning, Rightmost derivation in reverse)
• Bottom-up shift-reduce parsing mechanics
• Handle pruning and derivation correspondence

Recurring question patterns

• FIRST and FOLLOW Set Computation

  Commonmixed1 marks2025, 2021, 2019, 2017

  Given a context-free grammar with null derivations ($\epsilon$), compute the FIRST or FOLLOW set of specific non-terminals, often formatted as an option selection, table cell filler, or indexed integer in NAT.

• Compiler Phase Responsibilities and Pipeline Mapping

  CommonMCQ1 marks2021, 2018, 2017, 2016

  Match compiler phases (Lexical, Syntax, Semantic, Intermediate Code, Runtime) to their corresponding inputs, representations, functions, or detect which phase reports a specific program error.

• Parser Power Hierarchy and Theoretical Properties

  Commonmixed1 marks2025, 2017, 2015

  Evaluate statements regarding bottom-up parsers (viable prefixes on stack, LR parser power hierarchy: $\text{LR}(0) < \text{SLR}(1) < \text{LALR}(1) < \text{CLR}(1)$) or standard FIRST/FOLLOW construction rules.

• Parse Tree Construction from Precedence and Associativity

  OccasionalMCQ2 marks2011

  Construct an expression parse tree given user-defined operator precedence levels and associativity rules (left vs. right).

• Parsing Steps and Table Construction

  Occasionalmixed2 marks2021, 2020

  Determine the exact sequence/count of shift-reduce reduction steps to derive a target string, or fill in specific entries of an LL(1) parsing table.

• Phase-to-Algorithm Matching

  CommonMCQ1 marks2015

  A two-column match setup pairing compiler phases or runtime tasks (e.g., Lexical Analysis, Parsing, Register Allocation, Expression Evaluation) with corresponding theoretical models or algorithmic methods (e.g., DFA minimization, Production tree, Graph coloring, Post-order traversal).

• Parser Derivation Identification

  CommonMCQ1 marks2019

  Direct recall or conceptual classification of the scanning direction and underlying derivation order used by standard parsing algorithms (e.g., LL vs. LR).

Formulas GATE uses

Examiner traps in Lexical Analysis, Parsing and SDT

• Adding to a FOLLOW set ( is never present in any FOLLOW set).
• Forgetting to include the input end-marker \ into FOLLOW(S) of start symbol S$.
• Failing to propagate FOLLOW(A) into FOLLOW(B) when ⇒* in A → B .
• Confusing operator precedence hierarchy with parse tree depth (lower precedence operators sit higher/closer to the root).
• Misidentifying semantic errors (e.g., undeclared type or identifier) as syntax or lexical errors.
• Confusing the tree representation of syntax (production tree / parse tree) with evaluation order (post-order tree traversal).
• Misidentifying register allocation's theoretical basis (graph coloring on register interference graphs) with other graph-based optimization problems.
• Confusing the scanning direction (L) with the derivation type (Leftmost vs. Rightmost).
• Overlooking the 'in reverse' aspect of bottom-up / shift-reduce reductions compared to top-down LL derivations.

How questions are asked

• Match the compiler phase to its input/output or representation
• Calculate FIRST/FOLLOW set for a specific non-terminal in a CFG
• Count the total number of bottom-up reduction steps for a given string
• Fill missing entries in an LL(1) parsing table
• Multi-statement correctness evaluation on parsing theory or definitions (MSQ/MCQ)
• Select the correct parse tree reflecting operator precedence and associativity
• Two-column match the following (Phase/Task to Algorithm/Data Structure)
• Direct conceptual identification of parser derivation type

Paper trends

• Shift from simple phase matching MCQs towards algorithmic table verification (LL(1) table completion) and numerical derivation counts (NAT).

  2021, 2020, 2019

• Introduction of MSQ format in 2025 to test foundational definitions of FIRST and FOLLOW sets rather than pure computation.

  2025

• Testing cross-cutting compiler theory in single-mark matching MCQs that span both front-end (lexical/syntax) and back-end (code generation/optimization).

  2015

• Direct, 1-mark theoretical recall questions are used to verify fundamental bottom-up parsing definitions without requiring construction of parsing tables.

  2019

Difficulty notes