What are common 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.

Lexical Analysis, Parsing and SDT

14 Qs · since 2011 · 17 marks · 0.7 marks/paperStandard yield

Take topic test

In GATE CS, this foundational topic tests grammar analysis, parsing techniques, and compiler phase interactions through both theoretical properties and computational mechanics. Que… Guide

Type

GATE CSE 2025 Set 1Q46MSQ2 marksEasyWhich of the following statement(s) is/are TRUE while computing $First$ and $Follow$ during top down parsing by a compiler?
GATE CSE 2021 Set 1Q31MCQ2 marksMediumDiagramConsider the following context-free grammar where the set of terminals is $\{a, b, c, d, f\}$ . $\begin{aligned} S &\to d a T \mid R f \\ T &\to a S \mid b a T \mid \epsilon \\ R &\to c a T R \mid \epsilon \end{aligned}$ The following is a partially-filled LL(1) parsing table. Which one of the following choices…
GATE CSE 2021 Set 2Q3MCQ1 markEasyConsider the following ANSI C program: int main() { Integer x; return 0; } Which one of the following phases in a seven-phase C compiler will throw an error?
GATE CSE 2020Q24NAT1 markMediumConsider the following grammar. $S \rightarrow aSB \mid d$ $B \rightarrow b$ The number of reduction steps taken by a bottom-up parser while accepting the string $aaadbbb$ is _______.
GATE CSE 2019Q3MCQ1 markEasyWhich one of the following kinds of derivation is used by LR parsers?
GATE CSE 2019Q19NAT1 markMediumDiagramConsider the grammar given below: $S \rightarrow Aa$ $A \rightarrow BD$ $B \rightarrow b \mid \epsilon$ $D \rightarrow d \mid \epsilon$ Let a, b, d, and $ be indexed as follows: Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order.…
GATE CSE 2018Q8MCQ1 markEasyWhich one of the following statements is FALSE?
GATE CSE 2017 Set 1Q17MCQ1 markEasyDiagramConsider the following grammar: What is $\text{FOLLOW}(Q)$ ?
GATE CSE 2017 Set 2Q5MCQ1 markEasyDiagramMatch the following according to input (from the left column) to the compiler phase (in the right column) that processes it:
GATE CSE 2017 Set 2Q6MCQ1 markEasyWhich of the following statements about parser is/are CORRECT? I. Canonical LR is more powerful than SLR. II. SLR is more powerful than LALR. III. SLR is more powerful than Canonical LR.
GATE CSE 2016 Set 2Q19MCQ1 markEasyMatch the following: (P) Lexical analysis (i) Leftmost derivation (Q) Top down parsing (ii) Type checking (R) Semantic analysis (iii) Regular expressions (S) Runtime environments (iv) Activation records
GATE CSE 2015 Set 1Q13MCQ1 markMediumWhich one of the following is TRUE at any valid state in shift-reduce parsing?
GATE CSE 2015 Set 2Q19MCQ1 markMediumDiagramMatch the following:
GATE CSE 2011Q27MCQ2 marksMediumConsider two binary operators ‘ $\uparrow$ ’ and ‘ $\downarrow$ ’ with the precedence of operator $\downarrow$ being lower than that of the operator $\uparrow$ . Operator $\uparrow$ is right associative while operator $\downarrow$ is left associative. Which one of the following represents the parse tree for…

Topic guide

What does GATE test in Lexical Analysis, Parsing and SDT?

In GATE CS, this foundational topic tests grammar analysis, parsing techniques, and compiler phase interactions through both theoretical properties and computational mechanics. Questions frequently evaluate FIRST/FOLLOW set computation, LL(1) parsing table construction, LR parser capabilities, and bottom-up reduction steps. In addition, conceptual items regularly test front-end compiler phase responsibilities, phase inputs/outputs, and error detection stages.

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
common · mixed · 1 marks · 2025, 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
common · MCQ · 1 marks · 2021, 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
common · mixed · 1 marks · 2025, 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
occasional · MCQ · 2 marks · 2011
Construct an expression parse tree given user-defined operator precedence levels and associativity rules (left vs. right).
Parsing Steps and Table Construction
occasional · mixed · 2 marks · 2021, 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
common · MCQ · 1 marks · 2015
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
common · MCQ · 1 marks · 2019
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

FOLLOW Set Computation Rule 1

\text{FOLLOW}(B) \supseteq (\text{FIRST}(\beta) \setminus \{\epsilon\}) \quad \text{for } A \to \alpha B \beta

Used whenever finding symbols immediately following a non-terminal $B$ in a production RHS.

FOLLOW Set Computation Rule 2

\text{FOLLOW}(B) \supseteq \text{FOLLOW}(A) \quad \text{if } A \to \alpha B \text{ or } A \to \alpha B \beta \text{ where } \beta \Rightarrow^* \epsilon

Used when a non-terminal appears at the end of a production or is followed by nullable symbols.

LL(1) Table Placement for Epsilon Production

M[A, a] = A \to \epsilon \quad \forall a \in \text{FOLLOW}(A)

Used to place $A \to \epsilon$ into LL(1) parsing table cells under terminals present in $\text{FOLLOW}(A)$ .

Parser Expressive Power Hierarchy

\text{LR}(0) < \text{SLR}(1) < \text{LALR}(1) < \text{CLR}(1)

Used to evaluate the relative grammar-recognition power and capability of bottom-up parsers.

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

Easy questions (1 mark) focus on direct definitions (FIRST/FOLLOW properties, viable prefix concepts), single-step FOLLOW calculations, or phase matching. Medium questions (1-2 marks) involve multi-nonterminal FIRST/FOLLOW dependencies, LL(1) table population with nullable non-terminals, or counting reductions requiring tracing the complete rightmost derivation.