Compiler Design - Lexical Analysis, Parsing & Intermediate Code Generation Flashcards

Question 1

Compiler Architecture: Front-End vs. Back-End

Accepted Answer

A compiler is split into two main sections:
- **Front-End**: Source-language dependent. Consists of Lexical Analysis, Syntax Analysis, Semantic Analysis, and Intermediate Code Generation.
- **Back-End**: Target-machine dependent. Consists of Intermediate Code Optimization and Target Code Generation.

Question 2

Lexical Analyzer (Scanner)

Accepted Answer

The first phase of a compiler. It reads the raw stream of source characters, strips whitespace/comments, and groups characters into meaningful sequences called **lexemes**, producing a stream of **tokens** for the parser.

Question 3

Token vs. Lexeme vs. Pattern

Accepted Answer

- **Token**: An abstract category returned by the scanner (e.g., `id`, `num`, `if`).
- **Lexeme**: The actual character string in the source code matching a token (e.g., `total`, `42`).
- **Pattern**: The formal rule (usually a Regular Expression) describing how a lexeme is formed.

Question 4

NFA vs. DFA

Accepted Answer

- **Nondeterministic Finite Automata (NFA)**: Can have $\epsilon$-transitions (spontaneous state changes) and multiple outgoing transitions for a single input character from a given state.
- **Deterministic Finite Automata (DFA)**: Has no $\epsilon$-transitions and exactly one deterministic transition per input character for each state. Preferred for fast run-time lexical analysis.

Question 5

Thompson's Construction & Subset Construction

Accepted Answer

- **Thompson's Construction**: Converts a Regular Expression into an equivalent NFA.
- **Subset Construction (Powerset Construction)**: Converts an NFA into an equivalent DFA by mapping NFA state sets to individual DFA states.

Question 6

Context-Free Grammar (CFG)

Accepted Answer

A formal grammar $G = (V, \Sigma, R, S)$ used to specify the syntactic structure of a programming language, where:
- $V$: Non-terminals
- $\Sigma$: Terminals
- $R$: Production rules of the form $A \rightarrow \alpha$ ($A \in V, \alpha \in (V \cup \Sigma)^*$)
- $S$: Start symbol

Question 7

Ambiguous Grammar

Accepted Answer

A grammar is **ambiguous** if there exists at least one string that yields more than one distinct **parse tree** (or left-most / right-most derivation). Ambiguity must be eliminated by enforcing operator precedence and associativity rules.

Question 8

Left Recursion & Its Elimination

Accepted Answer

A grammar has **immediate left recursion** if it contains a rule $A \rightarrow A\alpha \mid \beta$. Left recursion causes top-down parsers to loop infinitely. It is eliminated by replacing the rule with:
- $A \rightarrow \beta A'$
- $A' \rightarrow \alpha A' \mid \epsilon$

Question 9

FIRST and FOLLOW Sets

Accepted Answer

- $	ext{FIRST}(\alpha)$: The set of terminals that can appear as the first symbol of a string derived from string $\alpha$.
- $	ext{FOLLOW}(A)$: The set of terminals that can immediately follow non-terminal $A$ in any sentential form derived from the start symbol.

Question 10

Top-Down Parsing & LL(1) Grammars

Accepted Answer

Top-down parsers build parse trees from the root (start symbol) down to leaves. An **LL(1)** parser reads input Left-to-right, constructs a Left-most derivation, using 1 token of lookahead. A grammar is LL(1) if its parsing table has no duplicate entry conflicts.

Question 11

Bottom-Up Parsing (Shift-Reduce)

Accepted Answer

Constructs a parse tree from the leaves up to the root by finding **handles** (substrings matching a production right-hand side) and reducing them to non-terminals. Core actions are:
- **Shift**: Push current token onto the stack.
- **Reduce**: Replace a handle on top of the stack with a non-terminal.

Question 12

Shift-Reduce Conflicts

Accepted Answer

- **Shift/Reduce Conflict**: The parser cannot decide whether to shift the next input token or reduce the stack top.
- **Reduce/Reduce Conflict**: The parser has two or more valid productions matching the top of the stack and cannot decide which reduction to perform.

Question 13

LR Parsing Hierarchy

Accepted Answer

Bottom-up deterministic parsers that read Left-to-right, building Right-most derivations in reverse:
- **SLR(1)**: Simple LR; smallest table size, uses simple FOLLOW sets for reductions.
- **LALR(1)**: Look-Ahead LR; merges states of Canonical LR that share core items (used by `yacc`/`bison`).
- **LR(1)**: Most powerful; includes explicit lookahead tokens in items, but generates very large state tables.

Question 14

Parse Tree vs. Abstract Syntax Tree (AST)

Accepted Answer

- **Parse Tree (Concrete Syntax Tree)**: Represents every detail of the syntactic derivation, including punctuation, parentheses, and intermediate non-terminals.
- **Abstract Syntax Tree (AST)**: A condensed tree representation omitting purely structural syntax tokens (like semicolons and braces) to focus strictly on semantic constructs.

Question 15

Semantic Analysis & Type Checking

Accepted Answer

Checks source code for semantic consistency using the AST and **Symbol Table**. Key tasks include:
- **Type Checking**: Ensuring operations match operand types.
- **Scope Resolution**: Verifying variables are declared before use.
- **Flow Control Checks**: Ensuring `break` or `continue` statements lie inside loops.

Question 16

Symbol Table

Accepted Answer

A central data structure used across compiler phases to store metadata about identifiers (variables, functions, classes). It tracks attributes like name, data type, memory offset, scope level, and parameter lists.

Question 17

Intermediate Code Generation (ICG)

Accepted Answer

Translates the validated AST into a machine-independent intermediate language. ICG decouples language-dependent parsing from target-dependent code generation, enhancing compiler portability and reusability.

Question 18

Three-Address Code (TAC)

Accepted Answer

An intermediate representation where each instruction has at most **three operands** (typically two sources and one destination).

Example:
```text}
x = y + z * w
```
Translates to:
```text
t1 = z * w
t2 = y + t1
x = t2
```

Question 19

TAC Implementations: Quadruples vs. Triples

Accepted Answer

- **Quadruples**: Records with 4 fields: `(op, arg1, arg2, result)`. Easy to rearrange during optimization.
- **Triples**: Records with 3 fields: `(op, arg1, arg2)`. The result is implicitly referred to by its array index/position. Makes code movement harder.

Question 20

Static Single Assignment (SSA) Form

Accepted Answer

An intermediate representation property where **every variable is assigned exactly once**. Multiple assignments to a variable create new versions (e.g., $x_1, x_2$), and branches use $\phi$-functions (phi-nodes) to merge values. SSA greatly simplifies program optimization algorithms.

Question 21

Code Optimization & Target Code Generation

Accepted Answer

- **Code Optimizer**: Analyzes IR to produce faster or smaller code (e.g., dead-code elimination, loop unrolling, constant folding).
- **Target Code Generator**: Maps the optimized IR into target assembly or machine code, handling CPU-specific details like **register allocation** and instruction scheduling.

Compiler Design - Lexical Analysis, Parsing & Intermediate Code Generation

Cards in this deck

Related Flashcard Sets

HSK 1 - Basic Chinese Vocabulary, Pinyin & Character Recognition

Functional Programming - Immutability, Pure Functions & Higher-Order Functions

Neuroscience - Neuroanatomy & Brain Function

Microsoft Azure Administrator (AZ-104) - Compute, Storage & Networking