Key Code Examples
BNF Grammar โ Arithmetic Expressions:
expr โ expr + term | expr โ term | term
term โ term ร factor | term รท factor | factor
factor โ ( expr ) | number
expr โ expr + term | expr โ term | term
term โ term ร factor | term รท factor | factor
factor โ ( expr ) | number
Recursive Descent Parser (Python-like):
def expr():
node = term()
while peek() in ('+', '-'):
op = consume()
node = BinOp(op, node, term())
return node
def expr():
node = term()
while peek() in ('+', '-'):
op = consume()
node = BinOp(op, node, term())
return node
Three-Address Code โ t = a + b ร c:
t1 = b * c
t2 = a + t1
t1 = b * c
t2 = a + t1
Lexical Token Pattern (Regex):
NUMBER: [0-9]+(\.[0-9]+)?
IDENTIFIER: [a-zA-Z_][a-zA-Z0-9_]*
OPERATOR: \+|โ|\*|/|=|<|>|<=|>=|==|!=
NUMBER: [0-9]+(\.[0-9]+)?
IDENTIFIER: [a-zA-Z_][a-zA-Z0-9_]*
OPERATOR: \+|โ|\*|/|=|<|>|<=|>=|==|!=
FIRST/FOLLOW Sets:
FIRST(expr) = { (, number, id }
FOLLOW(expr) = { $, ), +, โ }
FIRST(term) = { (, number, id }
FOLLOW(term) = { +, โ, $ ) }
FIRST(expr) = { (, number, id }
FOLLOW(expr) = { $, ), +, โ }
FIRST(term) = { (, number, id }
FOLLOW(term) = { +, โ, $ ) }
Core Concepts
1. Phases of Compilation
Lexical Analysis (scanning) โ Syntax Analysis (parsing) โ Semantic Analysis โ Intermediate Code Generation โ Code Optimization โ Code Generation. Each phase transforms the source representation toward machine code.
Lexical Analysis (scanning) โ Syntax Analysis (parsing) โ Semantic Analysis โ Intermediate Code Generation โ Code Optimization โ Code Generation. Each phase transforms the source representation toward machine code.
2. Lexical Analysis
The scanner groups characters into tokens (keywords, identifiers, operators, literals). Implemented using regular expressions and finite automata (DFA/NFA). Tools: Lex, Flex.
The scanner groups characters into tokens (keywords, identifiers, operators, literals). Implemented using regular expressions and finite automata (DFA/NFA). Tools: Lex, Flex.
3. Syntax Analysis (Parsing)
Parsers build a parse tree/AST from tokens according to grammar rules. Top-down: Recursive Descent, LL(k). Bottom-up: LR(0), SLR(1), LALR(1), LR(1). Tools: Yacc, Bison, ANTLR.
Parsers build a parse tree/AST from tokens according to grammar rules. Top-down: Recursive Descent, LL(k). Bottom-up: LR(0), SLR(1), LALR(1), LR(1). Tools: Yacc, Bison, ANTLR.
4. Semantic Analysis
Type checking, scope resolution, and attribute evaluation ensure the program's meaning is valid. Uses symbol tables and attribute grammars. Catches errors like undeclared variables and type mismatches.
Type checking, scope resolution, and attribute evaluation ensure the program's meaning is valid. Uses symbol tables and attribute grammars. Catches errors like undeclared variables and type mismatches.
5. Code Optimization
Intermediate-level (peephole, constant folding, dead code elimination) and machine-level (loop unrolling, register allocation, instruction scheduling). Goal: faster execution, less memory, lower power.
Intermediate-level (peephole, constant folding, dead code elimination) and machine-level (loop unrolling, register allocation, instruction scheduling). Goal: faster execution, less memory, lower power.
Core Definitions
Regular Expression: A notation for describing regular languages. Operators: concatenation, union (|), Kleene star (*). Examples: a* = {ฮต, a, aa, aaa, ...}. Recognized by finite automata.
Context-Free Grammar (CFG): A 4-tuple (V, ฮฃ, R, S) โ variables, terminals, production rules, start symbol. Generates context-free languages. Example: S โ aSb | ฮต generates {aโฟbโฟ : n โฅ 0}.
Left Recursion: A production where the leftmost symbol on the right-hand side is the same as the left-hand side variable: A โ Aฮฑ | ฮฒ. Eliminated by rewriting to A โ ฮฒA', A' โ ฮฑA' | ฮต.
Symbol Table: A data structure storing identifier information: name, type, scope, memory location, and attributes. Used by all compiler phases for lookup and update.
Worked Examples
Example 1: Recursive Descent Parse
Input: 3 + 4 ร 5
expr โ term { (+|โ) term } โ 3 + term โ 3 + factor { (ร|รท) factor } โ 3 + 4 ร 5
AST: (+ 3 (* 4 5)). Evaluates to 23 (multiplication has higher precedence).
Input: 3 + 4 ร 5
expr โ term { (+|โ) term } โ 3 + term โ 3 + factor { (ร|รท) factor } โ 3 + 4 ร 5
AST: (+ 3 (* 4 5)). Evaluates to 23 (multiplication has higher precedence).
Example 2: Left Recursion Elimination
Original: E โ E + T | T
Rewritten: E โ T E'
E' โ + T E' | ฮต
This allows top-down parsing without infinite recursion.
Original: E โ E + T | T
Rewritten: E โ T E'
E' โ + T E' | ฮต
This allows top-down parsing without infinite recursion.
Example 3: Three-Address Code Generation
Source: x = (a + b) ร (c โ d)
t1 = a + b
t2 = c โ d
t3 = t1 ร t2
x = t3
Each instruction has at most three operands โ easily translated to assembly.
Source: x = (a + b) ร (c โ d)
t1 = a + b
t2 = c โ d
t3 = t1 ร t2
x = t3
Each instruction has at most three operands โ easily translated to assembly.
Practice Problems
Problem 1: Write a regular expression for C-style identifiers (letter/underscore followed by alphanumerics/underscores).
Answer: [a-zA-Z_][a-zA-Z0-9_]*
Answer: [a-zA-Z_][a-zA-Z0-9_]*
Problem 2: Convert the NFA for (a|b)*ab to a DFA. How many states?
Answer: The DFA has 3 states: {q0} (start), {q0,q1}, {q0,q1,q2} (accept). Transitions track last two symbols.
Answer: The DFA has 3 states: {q0} (start), {q0,q1}, {q0,q1,q2} (accept). Transitions track last two symbols.
Problem 3: Eliminate left recursion from: A โ A ฮฑ | ฮฒ.
Answer: A โ ฮฒ A'; A' โ ฮฑ A' | ฮต
Answer: A โ ฮฒ A'; A' โ ฮฑ A' | ฮต
Problem 4: Generate three-address code for: y = a * b + c * d + e.
Answer: t1 = a * b; t2 = c * d; t3 = t1 + t2; y = t3 + e
Answer: t1 = a * b; t2 = c * d; t3 = t1 + t2; y = t3 + e
Problem 5: What is the difference between SLR(1) and LALR(1) parsers?
Answer: SLR uses FOLLOW sets for lookahead (larger state sets, more conflicts). LALR merges LR(1) states with identical cores โ smaller tables than LR(1), fewer conflicts than SLR. Same power: LALR โ LR(1), LALR โ SLR.
Answer: SLR uses FOLLOW sets for lookahead (larger state sets, more conflicts). LALR merges LR(1) states with identical cores โ smaller tables than LR(1), fewer conflicts than SLR. Same power: LALR โ LR(1), LALR โ SLR.