Compiler Phases, Lexical Analysis and Semantic Processing PYQs for GATE CS

Solve 9+ Compiler Phases, Lexical Analysis and Semantic Processing previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Compiler Design

Your Journey Through This Chapter

1. Compiler Phases, Front-End, Back-End and Symbol Tables

Current Topic. The structural foundation. Understand the pipeline and the central memory.

2. Lexical Tokens, Regular Expressions and Finite Automata

How the compiler reads characters and groups them into meaningful tokens using mathematical models.

3. Semantic Analysis and Syntax-Directed Type Checking

Ensuring the code makes logical sense, checking types, and attaching meaning to the structure.

4. Lexical, Syntax and Semantic Error Classification

Identifying exactly which phase catches which type of mistake in your code.

By the end of this chapter, you will be able to look at any code snippet or compiler behavior and instantly identify which phase is responsible.

The Big Picture: What is a Compiler?

A compiler is a program that translates source code written in a high-level programming language into an equivalent low-level target code, such as assembly or machine code.

To manage this complex translation, the compiler is logically divided into two major parts:

Part	Primary Goal	Dependency
Front-End (Analysis)	Understands the source code, checks for correctness, and creates an intermediate representation.	Depends on the source language. Independent of the target machine.
Back-End (Synthesis)	Takes the intermediate representation and generates optimized, machine-specific target code.	Depends on the target machine. Independent of the source language.

This separation is a powerful design choice. It allows us to build $N$ front-ends for $N$ languages and $M$ back-ends for $M$ machines, creating $N \times M$ compilers without rewriting the entire system.

Compiler Phases, Lexical Analysis and Semantic Processing: Solved Questions with Step-by-Step Explanations (9 Problems)

Question 1 · Compiler Design · 2026_Set2 NAT

A lexical analyzer uses the following token definitions

•

l e tt er \to [A - Z a - z]

•

d i g i t \to [0 - 9]

•

i d \to l e tt er (l e tt er ∣ d i g i t)^{*}

•

n u mb er \to d i g i t^{+}

•

w s \to (b l ank ∣ t ab ∣ n e w l in e)^{+}

For the string given below,

x 123 mm 78 y 7 z z z 514 A 8 H A aY cD

the number of tokens (excluding

w s

) that will be produced by the lexical analyzer is __________. (answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: Apply the maximal munch rule (longest match) to tokenize the input string based on the given regular expressions.

Step 1: The input string is separated by whitespace. We process each space-separated chunk.

Step 2: x1 starts with a letter and is followed by a digit. Matches id. (1 token)

Step 3: 23mm starts with digits. The longest match for number is 23. The remaining mm matches id. (2 tokens)

Step 4: 78 matches number. (1 token)

Step 5: y matches id. (1 token)

Step 6: 7z starts with a digit. 7 matches number. z matches id. (2 tokens)

Step 7: zz5 starts with a letter, followed by letters/digits. Matches id. (1 token)

Step 8: 14A starts with digits. 14 matches number. A matches id. (2 tokens)

Step 9: 8H starts with a digit. 8 matches number. H matches id. (2 tokens)

Step 10: AaYcD starts with a letter, followed by letters. Matches id. (1 token)

Step 11: Sum the tokens: 1 + 2 + 1 + 1 + 2 + 1 + 2 + 2 + 1 = 13.

Answer: 13

Question 2 · Compiler Design · 2026_Set1 MSQ

Consider the following C statements:

char *str1 = "Hello; /* Statement S1 */
char *str2 = "Hello;"; /* Statement S2 */
int *str3 = "Hello"; /* Statement S3 */

Which of the following options is/are correct?

A.
S1 and S2 have syntactic errors
B.
S2 has a lexical error and S3 has a syntactic error
C.
S1 has a lexical error and S3 has a semantic error
D.
S1 has a syntactic error and S3 has a semantic error

Correct Answer:

["C"]

Step-by-Step Solution

Key idea: This is an Error Classification question involving C string literals and pointer types. We must analyze each statement to find which compiler phase catches its error.

Step 1: Analyze Statement S1.

char *str1 = "Hello;

The string literal is missing the closing double quote. The lexical analyzer reads characters and tries to form tokens based on patterns. A string literal pattern requires matching opening and closing quotes. When it hits the end of the line or file without a closing quote, it cannot form a valid string token.

Error type: Lexical Error.

Step 2: Analyze Statement S2.

char *str2 = "Hello";

This is a perfectly valid C statement. A character pointer is initialized with the base address of a valid string literal.

Error type: No Error.

Step 3: Analyze Statement S3.

int *str3 = "Hello";

The lexical and syntax analyzers will successfully tokenize and parse this statement (it follows the grammar type id = string ;). However, the semantic analyzer checks for type compatibility. A string literal decays to a char (pointer to char), but it is being assigned to an int * (pointer to int). This is a type mismatch.

Error type: Semantic Error.

Step 4: Match with options.

S1 has a lexical error and S3 has a semantic error.

Answer: C

Question 3 · Compiler Design · 2025_Set1 MCQ

Which ONE of the following statements is FALSE regarding the symbol table?

A.
Symbol table is responsible for keeping track of the scope of variables.
B.
Symbol table can be implemented using a binary search tree.
C.
Symbol table is not required after the parsing phase.
D.
Symbol table is created during the lexical analysis phase.

Correct Answer:

Step-by-Step Solution

Key idea: Understand the lifecycle and usage of the symbol table across all compiler phases.

Step 1: Analyze Option A. The symbol table stores information about identifiers, including their scope, type, and memory location. This is TRUE.

Step 2: Analyze Option B. The symbol table can be implemented using various data structures like hash tables, binary search trees, or linked lists, depending on the scope structure. This is TRUE.

Step 3: Analyze Option C. The symbol table is heavily used after the parsing phase. Semantic analysis uses it for type checking, intermediate code generation uses it for address calculation, and the back-end uses it for final memory allocation. Thus, saying it is "not required after the parsing phase" is FALSE.

Step 4: Analyze Option D. The lexical analyzer recognizes identifiers and inserts them into the symbol table. Thus, it is created/populated during the lexical analysis phase. This is TRUE.

Answer: C

Question 4 · Compiler Design · 2024_Set2 MCQ

Consider the following two sets:

Which one of the following options is the CORRECT match from Set X to Set Y ?

A.
P – 4; Q – 1; R – 3; S – 2
B.
P – 2; Q – 3; R – 1; S – 4
C.
P – 2; Q – 1; R – 3; S – 4
D.
P – 4; Q – 3; R – 2; S – 1

Correct Answer:

Step-by-Step Solution

Key idea: This is a Compiler Phases matching question. We must map each compiler phase to its primary output or associated optimization technique.

Step 1: Analyze P (Lexical Analyzer).

The lexical analyzer reads the source code character stream and groups it into meaningful units called Tokens (e.g., keywords, identifiers, operators).

Match: P $\to$ 2.

Step 2: Analyze Q (Syntax Analyzer).

The syntax analyzer (parser) takes the token stream and checks it against the grammar rules to build a hierarchical structure, specifically the Parse Tree (or concrete syntax tree).

Match: Q $\to$ 3.

Step 3: Analyze R (Intermediate Code Generator).

The intermediate code generator takes the syntax tree (often after semantic analysis converts it to an AST) and produces an intermediate representation. In many textbook classifications, it produces the Abstract Syntax Tree (AST) or three-address code. Here, AST is the best fit among the choices.

Match: R $\to$ 1.

Step 4: Analyze S (Code Optimizer).

The code optimizer improves the intermediate code to make it faster or smaller. Constant Folding (evaluating constant expressions at compile time, like replacing 3 + 4 with 7) is a classic machine-independent optimization technique.

Match: S $\to$ 4.

Step 5: Combine the matches.

P-2, Q-3, R-1, S-4.

Answer: B

Question 5 · Compiler Design · 2023 MCQ

Consider the following statements regarding the front-end and back-end of a compiler.

S1: The front-end includes phases that are independent of the target hardware.
S2: The back-end includes phases that are specific to the target hardware.
S3: The back-end includes phases that are specific to the programming language used in the source code.

Identify the CORRECT option.

A.
Only S1 is TRUE.
B.
Only S1 and S2 are TRUE.
C.
S1, S2, and S3 are all TRUE.
D.
Only S1 and S3 are TRUE.

Correct Answer:

Step-by-Step Solution

Key idea: This question tests the conceptual division of a compiler into Front-End and Back-End.

Step 1: Analyze S1.

"The front-end includes phases that are independent of the target hardware."

The front-end handles lexical analysis, syntax analysis, semantic analysis, and intermediate code generation. These phases depend only on the source programming language, not on the machine where the code will run.

Statement S1 is TRUE.

Step 2: Analyze S2.

"The back-end includes phases that are specific to the target hardware."

The back-end handles code optimization (machine-dependent) and code generation. These phases must know the instruction set, registers, and memory architecture of the target CPU.

Statement S2 is TRUE.

Step 3: Analyze S3.

"The back-end includes phases that are specific to the programming language used in the source code."

This is FALSE. The programming language specifics are entirely handled by the front-end. The back-end only cares about the intermediate representation (IR) and the target hardware.

Statement S3 is FALSE.

Step 4: Conclusion.

Only S1 and S2 are TRUE.

Answer: B

Question 6 · Compiler Design · 2023 MCQ

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:

letter t e x t b f d i g i t t e x t b f i d \to [A-Za-z] \to [0-9] \to letter (letter ∣ digit)^{*}

Which one of the following Non-deterministic Finite-state Automata with

ϵ

-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

Correct Answer:

Step-by-Step Solution

Key idea: This is a Finite Automata construction question. We need to identify the NFA with $ϵ$ -transitions that correctly accepts the regular expression $letter (letter ∣ digit)^{*}$ .

Step 1: Analyze the Regular Expression.

The regex requires:

Exactly one letter to start.
Followed by zero or more occurrences of either letter or digit.

Step 2: Evaluate the structural requirements for the NFA.

The start state must transition to a final state on a letter.
To handle the Kleene star $(letter ∣ digit)^{*}$ , there must be a mechanism to loop back and accept any sequence of letters and digits.
In an NFA with $ϵ$ -transitions (like Thompson's construction), this is typically done by having $ϵ$ -transitions from the final state back to an intermediate state that branches into letter and digit transitions, which then loop back via $ϵ$ -transitions.

Step 3: Analyze the given options (based on standard GATE patterns).

Options that allow an $ϵ$ -transition directly from the start state to the final state incorrectly accept the empty string $ϵ$ .
Options that branch into separate non-communicating loops for letter and digit cannot accept mixed strings like a1b.
The correct NFA must have a central looping mechanism: after the first letter, an $ϵ$ -transition leads to a state that can read a letter OR a digit, and after reading either, it must be able to return to the start of the loop to read more characters.

Step 4: Identify the correct option.

Option D (the 4th option) correctly implements this structure:

Start $letter q_{1}$ (final).

$q_{1} ϵ q_{2}$ .

$q_{2} letter q_{3}$ (final) and $q_{2} digit q_{4}$ (final).

$q_{3} ϵ q_{2}$ and $q_{4} ϵ q_{2}$ .

This perfectly matches $letter (letter ∣ digit)^{*}$ .

Answer: D

Question 7 · Compiler Design · 2022 MCQ

Which one of the following statements is TRUE?

A.
The $L A L R (1)$ parser for a grammar $G$ cannot have reduce-reduce conflict if the $L R (1)$ parser for $G$ does not have reduce-reduce conflict.
B.
Symbol table is accessed only during the lexical analysis phase.
C.
Data flow analysis is necessary for run-time memory management.
D.
$L R (1)$ parsing is sufficient for deterministic context-free languages.

Correct Answer:

Step-by-Step Solution

Key idea: Evaluate each statement based on formal language theory and compiler design principles.

Step 1: Analyze Option A. LALR(1) parsers are formed by merging states of LR(1) parsers. This merging can introduce reduce-reduce conflicts that were not present in the original LR(1) parser. Thus, Option A is FALSE.

Step 2: Analyze Option B. The symbol table is a central data structure accessed by almost all compiler phases (lexical, syntax, semantic, intermediate code generation, optimization, and code generation), not just lexical analysis. Thus, Option B is FALSE.

Step 3: Analyze Option C. Data flow analysis is a technique used for code optimization (e.g., constant propagation, dead code elimination), not for run-time memory management. Run-time memory management is handled by the run-time system. Thus, Option C is FALSE.

Step 4: Analyze Option D. Deterministic Context-Free Languages (DCFLs) are exactly the class of languages that can be recognized by a Deterministic Pushdown Automaton (DPDA). LR(1) parsing is a deterministic parsing technique that can parse all DCFLs. Thus, Option D is TRUE.

Answer: D

Question 8 · Compiler Design · 2021_Set2 MCQ

Consider 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?

A.
Lexical analyzer
B.
Syntax analyzer
C.
Semantic analyzer
D.
Machine dependent optimizer

Correct Answer:

Step-by-Step Solution

Key idea: This is an Error Classification question. We must trace the given code through the compiler phases to see which one first flags an error.

Step 1: Analyze the code snippet.

The code is Integer x;. In ANSI C, Integer is not a reserved keyword (the correct keyword is int).

Step 2: Lexical Analysis Phase.

The lexical analyzer (scanner) reads the characters and groups them into tokens based on regular expressions. Since Integer is not a reserved keyword, the scanner treats it as a standard identifier (id).

The token stream produced is: <id, "Integer">, <id, "x">, <;>.

No lexical error is thrown because Integer is a perfectly valid identifier.

Step 3: Syntax Analysis Phase.

The syntax analyzer (parser) receives the token stream and tries to build a parse tree using the context-free grammar of C.

A variable declaration in C requires a type specifier followed by an identifier and a semicolon (e.g., type_specifier id ;).

The parser sees <id> <id> ;. This sequence does not match any valid production rule for a declaration or statement in the C grammar.

Therefore, the parser fails to parse the tokens and throws a Syntax Error.

Step 4: Semantic Analysis Phase.

The semantic analyzer never receives this code because the compilation halts (or at least flags the primary error) at the syntax analysis phase. Even if it did, it would look for type compatibility, but the structural grammar violation is caught first.

Answer: Syntax analyzer

Question 9 · Compiler Design · 2021_Set1 MCQ

Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:

P D D E E E \to D^{*} E^{*} \to int ID {record that ID.lexeme is of type int} \to bool ID {record that ID.lexeme is of type bool} \to E_{1} + E_{2} {check that E_{1} . type = E_{2} . type = int; set E . type := int} \to! E_{1} {check that E_{1} . type = bool; set E . type := bool} \to ID {set E . type := int}

With respect to the above grammar, which one of the following choices is correct?

A.
The actions can be used to correctly type-check any syntactically correct program.
B.
The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
C.
The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
D.
The actions will lead to an infinite loop.

Correct Answer:

Step-by-Step Solution

Key idea: Trace the syntax-directed translation (SDT) actions to see what types are actually supported and checked.

Step 1: Look at the declaration rules. The grammar allows declaring variables as int or bool and records them in the symbol table.

Step 2: Look at the expression rules. The rule E -> ID has the action {set E.type := int}. It hardcodes the type to int and completely ignores the symbol table lookup.

Step 3: Because E -> ID always returns int, any boolean variable used in an expression will be incorrectly treated as an integer. Therefore, the SDT cannot correctly type-check any program (Option A is false) and cannot type-check boolean expressions (Option C is false).

Step 4: The SDT does not contain any recursive or cyclic dependencies that would cause an infinite loop (Option D is false).

Step 5: Since the expression rules only support int (e.g., E1 + E2 checks for int), the SDT can only successfully type-check integer variable declarations and integer expressions.

Answer: B

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Compiler Phases, Lexical Analysis and Semantic Processing PYQs for GATE CS

Chapter Roadmap: Compiler Design

Your Journey Through This Chapter

The Big Picture: What is a Compiler?

Compiler Phases, Lexical Analysis and Semantic Processing: Solved Questions with Step-by-Step Explanations (9 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit