COMPILER DESIGN – 100 FLASHCARDS (Q&A +

Explanation)
1️⃣ What is a compiler?

Answer:
A compiler is a software program that translates source code written in a high-level language
into machine code.

Explanation:
It performs lexical, syntactic, semantic, and code generation processes to produce executable
programs.

2️⃣ What are the major phases of a compiler?

Answer:

1. Lexical Analysis
2. Syntax Analysis
3. Semantic Analysis
4. Intermediate Code Generation
5. Code Optimization
6. Code Generation

Explanation:
Each phase transforms the input into a new form, adding structure and meaning until machine
code is generated.

3️⃣ What is Lexical Analysis?

Answer:
It is the process of converting a sequence of characters into a sequence of tokens.

Explanation:
A lexical analyzer (scanner) identifies keywords, identifiers, constants, and symbols used by
the parser.

4️⃣ What is a Token?

Answer:
A token is a pair consisting of a token name and an optional attribute value.

Explanation:
Examples:
if → keyword,
x → identifier,
123 → number.

5️⃣ What is a Lexeme?

Answer:
A lexeme is the actual character sequence that forms a token.

Explanation:
Example: In statement sum = a + b;, lexemes are sum, =, a, +, b, ;.

6️⃣ What is a Pattern in lexical analysis?

Answer:
A rule that describes the structure of lexemes for a token.

Explanation:
For example, identifiers follow the pattern [A-Za-z][A-Za-z0-9]*.

7️⃣ What are the outputs of Lexical Analysis?

Answer:
Tokens, Symbol Table entries, and sometimes error messages.

Explanation:
Tokens are passed to the next compiler phase—Syntax Analysis.

8️⃣ What is a Symbol Table?

Answer:
A data structure that stores information about identifiers such as names, types, and memory
locations.

Explanation:
It is used during semantic analysis and code generation to check declarations and references.

9️⃣ What is Syntax Analysis?

Answer:
The process of analyzing token sequences according to grammar rules to form a parse tree.

Explanation:
Also called parsing, it verifies that the token sequence follows the correct syntax.
🔟 What is a Parse Tree?

Answer:
A hierarchical tree structure representing how a string derives from the grammar’s start symbol.

Explanation:
Leaves represent tokens, and internal nodes represent grammar symbols.

11️⃣ What is a Grammar?

Answer:
A set of production rules describing the syntax of a programming language.

Explanation:
Grammars are usually written as context-free grammars (CFG) for compilers.

12️⃣ What are the four components of a Context-Free Grammar (CFG)?

Answer:

1. Terminals
2. Non-terminals
3. Start symbol
4. Production rules

Explanation:
Terminals are tokens; non-terminals are abstract symbols representing structures like expressions
or statements.

13️⃣ What is Left Recursion?

Answer:
When a grammar rule refers to itself on the left side of a production.

Example:
A → Aα | β

Explanation:
Left recursion causes problems in top-down parsers and must be eliminated.

14️⃣ What is Right Recursion?

Answer:
When a grammar rule refers to itself on the right side of the production.
Example:
A → βA | ε

Explanation:
Right recursion is used in bottom-up parsing and is not problematic.

15️⃣ What is Left Factoring?

Answer:
A grammar transformation to remove ambiguity by factoring out common prefixes.

Example:

A → αβ1 | αβ2
becomes
A → αA'
A' → β1 | β2

Explanation:
Helps predictive parsers handle multiple alternatives starting with the same token.

16️⃣ What is Ambiguous Grammar?

Answer:
A grammar that can generate more than one parse tree for the same string.

Explanation:
Ambiguity must be removed for deterministic parsing.

17️⃣ What is Semantic Analysis?

Answer:
The phase where the compiler checks for meaningful correctness—type checking, variable
declarations, etc.

Explanation:
Example: verifying that variables are declared before use and operations are type-compatible.

18️⃣ What are Semantic Errors?

Answer:
Errors in program meaning such as type mismatches or undeclared variables.

Explanation:
Unlike syntax errors, they don’t prevent parsing but affect program logic.
19️⃣ What is Intermediate Code Generation?

Answer:
Translating the parsed source code into a machine-independent intermediate representation.

Explanation:
Common forms include Three-Address Code (TAC) and Syntax Trees.

20️⃣ What is Three-Address Code (TAC)?

Answer:
An intermediate representation where each statement has at most three addresses (operands).

Example:
t1 = a + b
t2 = t1 * c

Explanation:
Simplifies optimization and translation to machine code.

21️⃣ What are the forms of Intermediate Code?

Answer:

 Postfix notation
 Syntax trees
 DAG (Directed Acyclic Graph)
 Three-address code

Explanation:
Different forms are suited for different optimization strategies

22️⃣ What is a Syntax Tree?

Answer:
A condensed representation of the parse tree showing only essential structure.

Explanation:
It focuses on operators and operands rather than detailed grammar rules.

23️⃣ What is Code Optimization?

Answer:
Improving intermediate code to make the final program run faster or take less memory.
Explanation:
Optimization does not change the program’s semantics—only its efficiency.

24️⃣ What are the types of Code Optimization?

Answer:

1. Machine-independent (e.g., constant folding)

2. Machine-dependent (e.g., register allocation)

Explanation:
Machine-independent optimizations work on intermediate code, while dependent ones target
specific hardware.

25️⃣ What is Constant Folding?

Answer:
A compiler optimization where constant expressions are evaluated at compile time.

Example:
x = 5 * 4 → replaced with x = 20

Explanation:
Reduces computation during execution.

26️⃣ What is Dead Code Elimination?

Answer:
Removing code that never affects program results.

Example:

if (false) x = 10;

Explanation:
Such statements waste memory and CPU time; removing them improves efficiency.

27️⃣ What is Loop Optimization?

Answer:
Improving loops by reducing redundant calculations or moving invariant code outside loops.

Explanation:
Reduces execution time in repetitive tasks.
28️⃣ What is Code Generation?

Answer:
Translating intermediate representation into machine-level or assembly instructions.

Explanation:
It assigns registers, selects instructions, and manages addressing modes.

29️⃣ What are the main tasks of Code Generation?

Answer:

 Register allocation
 Instruction selection
 Address computation
 Control flow translation

Explanation:
It ensures that optimized intermediate code becomes efficient target code.

30️⃣ What is a Compiler Front End?

Answer:
Includes lexical, syntax, and semantic analysis phases.

Explanation:
Responsible for analyzing source structure and building intermediate representations.

31️⃣ What is a Compiler Back End?

Answer:
Includes code optimization and code generation.

Explanation:
Responsible for producing efficient machine code for the target platform.

32️⃣ What is an Interpreter?

Answer:
A program that executes source code line by line instead of compiling it into machine code.

Explanation:
Examples: Python, JavaScript interpreters.

33️⃣ Difference between Compiler and Interpreter?

Answer:

Aspect Compiler Interpreter

Execution Translates entire program Executes line-by-line
Output Object code Immediate execution
Speed Faster at runtime Slower
Example C, C++ Python, Bash

Explanation:
Compilers translate once; interpreters repeatedly analyze code at runtime.

34️⃣ What is Bootstrapping in compilers?

Answer:
The process of writing a compiler in the same language it compiles.

Explanation:
A compiler written in its own language is called a self-compiling compiler.

35️⃣ What are the different types of compilers?

Answer:

 Cross compiler
 JIT (Just-In-Time) compiler
 Incremental compiler
 Threaded compiler

Explanation:
Each type suits different environments (e.g., cross compilers build for other architectures).

36️⃣ What is a DFA (Deterministic Finite Automata)?

Answer:
A mathematical model used to recognize tokens in lexical analysis.

Explanation:
It has a finite set of states, transitions, and accepts input strings that match token patterns.

37️⃣ What is an NFA (Non-Deterministic Finite Automata)?

Answer:
A finite automaton where multiple transitions for the same input are possible.
Explanation:
NFAs are easier to design but are converted to DFAs for implementation efficiency.

38️⃣ What is a Regular Expression (RE)?

Answer:
A symbolic expression that defines a set of strings.

Explanation:
Used to specify token patterns during lexical analysis.

39️⃣ What is the relation between Regular Expressions and Finite Automata?

Answer:
For every RE, there exists a corresponding finite automaton that recognizes the same language.

Explanation:
Lexical analyzers often convert RE → NFA → DFA → Tokens.

40️⃣ What is a Parser?

Answer:
A parser processes tokens to check grammatical structure and build a parse tree.

Explanation:
It ensures syntactic correctness based on the grammar rules of the language.

41️⃣ What are the two main types of parsers?

Answer:

1. Top-Down Parsers
2. Bottom-Up Parsers

Explanation:

 Top-Down: Build parse tree from root to leaves (e.g., LL parsers).

 Bottom-Up: Build parse tree from leaves to root (e.g., LR parsers).

42️⃣ What is a Recursive Descent Parser?

Answer:
A top-down parser built from a set of mutually recursive procedures for each grammar rule.
Explanation:
Simple to implement but cannot handle left-recursive grammars.

43️⃣ What is a Predictive Parser?

Answer:
A non-recursive top-down parser that uses lookahead tokens to predict the next production.

Explanation:
Based on LL(1) grammars, which can be parsed with one-token lookahead.

44️⃣ What is an LL Parser?

Answer:
A Left-to-right, Leftmost derivation parser.

Explanation:
It reads input from left to right and produces the leftmost derivation. LL(1) is the simplest form
(one lookahead).

45️⃣ What is an LR Parser?

Answer:
A Left-to-right, Rightmost derivation in reverse parser.

Explanation:
It uses a stack and parsing table for shift–reduce actions. Examples: SLR, LALR, and
Canonical LR parsers.

46️⃣ What is the difference between LL and LR parsers?

Answer:

Feature LL Parser LR Parser

Derivation Leftmost Rightmost (in reverse)
Grammar Predictive (LL(1)) More general
Implementation Recursive/Non-recursive Table-driven
Handles left recursion No Yes

Explanation:
LR parsers are more powerful and widely used in modern compilers.

47️⃣ What is a Shift-Reduce Parser?

Answer:
A bottom-up parser that shifts tokens onto a stack until a handle is recognized, then reduces it
using grammar rules.

Explanation:
It forms the basis of LR parsers and constructs the parse tree from leaves upward.

48️⃣ What is a Handle in parsing?

Answer:
A substring that matches the right-hand side of a production and whose reduction represents one
step in the rightmost derivation.

Explanation:
The parser repeatedly finds handles and replaces them with non-terminals until the start symbol
remains.

49️⃣ What are the common types of parsing errors?

Answer:

1. Lexical errors (invalid tokens)

2. Syntax errors (grammar violations)
3. Semantic errors (meaning violations)

Explanation:
Each error type occurs in different compilation phases and must be detected and handled
appropriately.

50️⃣ What is Error Recovery in a compiler?

Answer:
The process of handling errors gracefully so compilation can continue.

Explanation:
Typical strategies include panic mode, phrase-level, and error productions.

51️⃣ What is Panic Mode Error Recovery?

Answer:
The compiler skips input symbols until a synchronizing token (like ;) is found.

Explanation:
This prevents cascading errors and resumes parsing quickly.
52️⃣ What is Phrase-Level Error Recovery?

Answer:
It attempts to repair the input by inserting or deleting tokens.

Explanation:
Used in simple parsers where error corrections are predictable.

53️⃣ What is Syntax-Directed Translation (SDT)?

Answer:
A method of attaching semantic rules to grammar productions for translation.

Explanation:
These rules specify how to compute attributes or generate intermediate code as parsing proceeds.

54️⃣ What are Synthesized Attributes?

Answer:
Attributes computed from the attributes of children nodes in a parse tree.

Explanation:
Commonly used in bottom-up parsing.

55️⃣ What are Inherited Attributes?

Answer:
Attributes passed from parent or sibling nodes to a node.

Explanation:
Used in top-down parsing when attribute values flow from higher to lower levels.

56️⃣ What is an Attribute Grammar?

Answer:
A context-free grammar with attributes and semantic rules associated with its productions.

Explanation:
It provides a formal framework for defining syntax-directed translation.

57️⃣ What is a DAG (Directed Acyclic Graph)?

Answer:
A structure representing expressions where common subexpressions are shared.

Explanation:
It avoids recomputation of repeated expressions, enabling optimization.

58️⃣ What is Common Subexpression Elimination (CSE)?

Answer:
An optimization technique that reuses previously computed expressions.

Example:

x = a + b
y = a + b

→ replace with

t = a + b
x = t
y = t

Explanation:
Reduces redundant computation.

59️⃣ What is Loop Invariant Code Motion?

Answer:
Moving calculations that yield the same result in every iteration outside the loop.

Explanation:
Improves performance by reducing repeated computation inside loops.

60️⃣ What is Constant Propagation?

Answer:
Replacing variables known to have constant values with those values.

Example:

x = 5
y = x + 3 → y = 8

Explanation:
Simplifies code and enables further optimization.
61️⃣ What is Peephole Optimization?

Answer:
A local optimization technique that examines small windows (“peepholes”) of target code to
improve performance.

Explanation:
Typical examples include redundant instruction elimination and replacing costly operations with
cheaper equivalents.

62️⃣ What is Register Allocation?

Answer:
Assigning frequently used variables to CPU registers to speed up access.

Explanation:
Part of machine-dependent optimization in the code generation phase.

63️⃣ What is Instruction Scheduling?

Answer:
Reordering instructions to avoid pipeline stalls or delays without changing program behavior.

Explanation:
Improves performance on pipelined processors.

64️⃣ What are the different forms of Intermediate Code Representation?

Answer:

 Syntax trees
 Postfix notation
 DAG
 Three-address code

Explanation:
TAC is most common for optimization and translation simplicity.

65️⃣ What are the types of Three-Address Code statements?

Answer:
  Assignment: x = y op z
 Unary: x = op y
 Copy: x = y
 Conditional/unconditional jumps

Explanation:
Each statement represents a simple operation suitable for code generation.

66️⃣ What is Backpatching?

Answer:
A technique used in code generation for filling in incomplete jump addresses later.

Explanation:
Commonly used in generating code for control statements like if and while.

67️⃣ What is Target Code Generation?

Answer:
The process of translating intermediate code into machine-level code.

Explanation:
It selects appropriate instructions, addressing modes, and manages registers.

68️⃣ What are Addressing Modes?

Answer:
Techniques for specifying operand addresses in machine instructions.

Examples:
Immediate, Direct, Indirect, Register, Indexed.

Explanation:
Different modes improve flexibility and performance.

69️⃣ What are the main challenges in Code Generation?

Answer:

 Register allocation
 Instruction selection
 Handling control flow
 Optimization
Explanation:
Balancing efficiency and correctness is critical in the final translation stage.

70️⃣ What is a Symbol Table used for?

Answer:
To store information about identifiers such as their names, types, scope, and memory locations.

Explanation:
It is used by multiple phases to check declarations and manage variable lifetimes.

71️⃣ What are Symbol Table Operations?

Answer:

 Insert (add new symbol)

 Lookup (retrieve symbol info)
 Modify/Delete (update scope or type)

Explanation:
Efficient symbol table management is vital for performance.

72️⃣ What are different Symbol Table structures?

Answer:

 Linear list
 Hash table
 Binary search tree

Explanation:
Hash tables offer the fastest lookup for large programs.

73️⃣ What is Scoping?

Answer:
Defines the visibility and lifetime of variables within a program.

Explanation:

 Static scope → determined at compile time.

 Dynamic scope → determined at runtime.

74️⃣ What is Static Scoping?

Answer:
The scope of a variable is determined by the program’s structure at compile time.

Explanation:
Most modern languages use static scoping (e.g., C, Java).

75️⃣ What is Dynamic Scoping?

Answer:
Variable scope determined by the program’s calling sequence at runtime.

Explanation:
Used in older languages like LISP or early BASIC.

76️⃣ What is Type Checking?

Answer:
Ensuring that operations in a program are performed on compatible data types.

Explanation:
Example: disallowing addition between a string and an integer.

77️⃣ What are the two types of Type Checking?

Answer:

1. Static Type Checking – done at compile time.

2. Dynamic Type Checking – done at runtime.

Explanation:
Statically typed languages (like C++) detect errors earlier.

78️⃣ What is Type Conversion (Casting)?

Answer:
Changing a variable from one data type to another.

Explanation:
Can be implicit (automatic) or explicit (programmer-defined).

79️⃣ What is Error Handling in compilers?

Answer:
Detecting and managing syntax and semantic errors during compilation.
Explanation:
Ensures that the compiler reports helpful messages and continues processing.

80️⃣ What is a Compiler Driver?

Answer:
A program that manages and invokes the various compilation phases automatically.

Explanation:
Example: the gcc command calls the preprocessor, compiler, assembler, and linker.

81️⃣ What is the Role of the Assembler in compilation?

Answer:
Converts assembly code generated by the compiler into object (machine) code.

Explanation:
The assembler outputs relocatable object files used by the linker.

82️⃣ What is the Linker?

Answer:
Combines multiple object files into a single executable program.

Explanation:
It resolves external references and relocates addresses.

83️⃣ What is the Loader?

Answer:
Loads the executable program into main memory for execution.

Explanation:
Assigns runtime memory addresses and starts execution.

84️⃣ What is a Bootstrap Compiler?

Answer:
A compiler written in its own source language and used to compile itself.

Explanation:
It demonstrates the completeness and power of the language.

85️⃣ What is Just-In-Time (JIT) Compilation?

Answer:
Compiles intermediate code into machine code at runtime instead of before execution.

Explanation:
Used in Java Virtual Machine (JVM) to improve execution speed.

86️⃣ What is Intermediate Representation (IR)?

Answer:
A low-level form of source code used between the front end and back end of the compiler.

Explanation:
It bridges language-independent optimization and target-specific code generation.

87️⃣ What is a Control Flow Graph (CFG)?

Answer:
A graphical representation of program control flow, showing basic blocks and jumps.

Explanation:
Used for optimization such as dead code removal and loop detection.

88️⃣ What is a Basic Block?

Answer:
A sequence of consecutive statements with one entry and one exit point.

Explanation:
Simplifies analysis and optimization since control always enters at the beginning and leaves at
the end.

89️⃣ What is Dominator in CFG?

Answer:
A node D dominates node N if every path from the entry node to N passes through D.

Explanation:
Used in optimization and code restructuring.

90️⃣ What is Liveness Analysis?

Answer:
Determining which variables hold values that may be needed in the future.
Explanation:
Used for register allocation to avoid overwriting live variables.

91️⃣ What is Data Flow Analysis?

Answer:
Analyzing how data values propagate through a program.

Explanation:
Used for constant propagation, reaching definitions, and dead code elimination.

92️⃣ What is Machine-Independent Optimization?

Answer:
Optimizations applied on intermediate code regardless of the target machine.

Explanation:
Examples: constant folding, dead code removal.

93️⃣ What is Machine-Dependent Optimization?

Answer:
Optimizations tailored to the specific CPU architecture.

Explanation:
Examples: instruction scheduling, register allocation.

94️⃣ What is Inline Expansion?

Answer:
Replacing a function call with the body of the function itself.

Explanation:
Reduces call overhead but increases code size.

95️⃣ What is Strength Reduction?

Answer:
Replacing expensive operations with equivalent cheaper ones.

Example:
x = y * 2 → replaced by x = y + y

Explanation:
Improves speed without changing semantics.
96️⃣ What is Tail Recursion?

Answer:
A recursive call that occurs as the last action in a function.

Explanation:
Compilers optimize tail recursion into loops to save stack space.

97️⃣ What is a Cross Compiler?

Answer:
A compiler that runs on one machine but produces code for another machine.

Explanation:
Used in embedded system development.

98️⃣ What is an Optimizing Compiler?

Answer:
A compiler that improves performance and efficiency of the generated code.

Explanation:
Performs transformations like loop unrolling and inlining to make programs faster.

99️⃣ What is a One-Pass Compiler?

Answer:
A compiler that scans the source code only once to generate target code directly.

Explanation:
Faster but limited in optimization and error detection

100️⃣ What is a Multi-Pass Compiler?

Answer:
A compiler that scans the source multiple times to perform analysis and optimization in stages.

Explanation:
It separates concerns for better optimization and clearer structure, common in modern compilers.