Compiler Design | Semester 6 Complete Core Notes
Semester 6 - Page 2: Compiler Design. 25 numbered topics, highlighted rules, worked token/grammar/IR examples, answered exam questions, diagrams, comparison tables and three complete Python demos. General common-core guide, not an official syllabus or a full compiler.
Topic map
- Compiler, interpreter and JIT
- Compiler phases and toolchain
- Tokens, lexemes and source locations
- Regular expressions and finite automata
- Lexical edge cases and comments
- CFGs, derivations and ambiguity
- Precedence, associativity and AST
- Left recursion and left factoring
- FIRST, FOLLOW and nullable symbols
- LL(1) tables and predictive choices
- Recursive-descent parsing
- Bottom-up parsing and handles
- LR items, states and conflicts
- Syntax errors and recovery
- Symbol tables and scope
- Type checking and coercion
- Syntax-directed translation and attributes
- IR and three-address code
- Control flow, basic blocks and backpatching
- Runtime storage and calling conventions
- Data-flow analysis and liveness
- Optimization and preservation
- Code generation and register allocation
- Compiler testing and differential checks
- Exam pipeline and limitations
1. Compiler, interpreter and JIT
A compiler translates representations under language semantics; an interpreter executes a representation; a JIT compiles during execution. Real systems can combine these roles.
Answer: No. Dynamic values and language rules can require checks during execution.
2. Compiler phases and toolchain
Lexing, parsing, semantic analysis, IR, optimization and code generation have different jobs. Assembly/linking/loading are related toolchain stages, not identical to parsing.
Answer: No. Semantic analysis is a separate responsibility.
Characters -> tokens -> syntax tree -> semantic facts -> IR -> justified optimization -> target code
3. Tokens, lexemes and source locations
A token has a kind and often value/span; a lexeme is the matched source text. Source positions support diagnostics and tooling.
Answer: Not necessarily. Lexer rules/priority can classify reserved words separately.
4. Regular expressions and finite automata
Regular patterns describe many lexical classes and can be implemented with finite automata. Longest match and rule priority resolve overlaps under stated rules.
Answer: No. General balanced nesting usually belongs to grammar/parsing machinery.
5. Lexical edge cases and comments
Whitespace/comments may be skipped unless semantically meaningful. Strings, escapes, encodings and malformed literals need deliberate rules and diagnostics.
Answer: Skipping can change the program meaning and hide source mistakes.
Toy lexer with exact unmatched-character errors
import re
pattern = re.compile(r"(?P<SPACE>\s+)|(?P<ID>[A-Za-z_][A-Za-z_0-9]*)|(?P<NUM>[0-9]+)|(?P<OP>[=+*();-])")
def tokens(text):
answer, position = [], 0
while position < len(text):
match = pattern.match(text, position)
if match is None: raise ValueError("invalid character at " + str(position))
if match.lastgroup != "SPACE": answer.append((match.lastgroup, match.group()))
position = match.end()
return answer
print(tokens("sum12 = 3 + 4;"))
try: tokens("x@2")
except ValueError as error: print(error)
Checked output:
[('ID', 'sum12'), ('OP', '='), ('NUM', '3'), ('OP', '+'), ('NUM', '4'), ('OP', ';')]
invalid character at 1
6. CFGs, derivations and ambiguity
A context-free grammar defines terminals, nonterminals, productions and start symbol. Ambiguity means multiple parse trees for one token string.
Answer: No. The grammar or disambiguation strategy may be changed.
7. Precedence, associativity and AST
Precedence chooses which operators bind tighter; associativity resolves grouping among equal precedence. ASTs preserve meaningful structure while omitting incidental parse details.
Answer: No. AST construction deliberately removes grammar scaffolding.
+
/ \
2 *
/ \
3 4
Value = 2 + (3 x 4) = 148. Left recursion and left factoring
Basic predictive recursive descent cannot consume input through direct left recursion. Factoring separates shared prefixes, but these changes do not guarantee every grammar becomes LL(1).
Answer: No. FIRST/FOLLOW choices and ambiguity still matter.
9. FIRST, FOLLOW and nullable symbols
FIRST identifies possible starting terminals; FOLLOW identifies terminals after a nonterminal plus end marker for the start. Nullable derivations require fixed-point propagation.
Answer: No. FOLLOW contains terminals/end marker, not an empty string.
Fixed-point FIRST/FOLLOW for the stated tiny grammar
grammar = {"S": [["A", "b"]], "A": [["a"], []]}
first = {n: set() for n in grammar}
nullable = set()
def sequence(symbols):
result = set()
for symbol in symbols:
if symbol not in grammar: return result | {symbol}, False
result |= first[symbol]
if symbol not in nullable: return result, False
return result, True
changed = True
while changed:
changed = False
for left, rules in grammar.items():
for rule in rules:
values, empty = sequence(rule)
before = (len(first[left]), len(nullable))
first[left] |= values
if empty: nullable.add(left)
changed |= before != (len(first[left]), len(nullable))
follow = {n: set() for n in grammar}; follow["S"].add("$")
changed = True
while changed:
changed = False
for left, rules in grammar.items():
for rule in rules:
for i, symbol in enumerate(rule):
if symbol not in grammar: continue
values, empty = sequence(rule[i+1:]); before = len(follow[symbol])
follow[symbol] |= values
if empty: follow[symbol] |= follow[left]
changed |= before != len(follow[symbol])
for symbol in sorted(grammar):
print(symbol, "FIRST:", sorted(first[symbol]), "nullable:", symbol in nullable, "FOLLOW:", sorted(follow[symbol]))
Checked output:
A FIRST: ['a'] nullable: True FOLLOW: ['b'] S FIRST: ['a', 'b'] nullable: False FOLLOW: ['$']
10. LL(1) tables and predictive choices
An LL(1) table uses one lookahead with FIRST and nullable/FOLLOW rules. Multiple productions in one cell indicate a conflict under that grammar.
Answer: No. It generally indicates a syntax error under that parse state.
11. Recursive-descent parsing
Recursive-descent functions mirror grammar responsibilities and consume tokens. Explicit precedence levels and full-input checks avoid accidental partial acceptance.
Answer: Otherwise a valid prefix could hide an invalid suffix.
Full-input arithmetic recursive descent
import re
def evaluate(text):
parts = re.findall(r"[0-9]+|[()+*-]|\S", text) + ["EOF"]
position = 0
def factor():
nonlocal position
token = parts[position]
if token.isascii() and token.isdigit():
position += 1; return int(token)
if token == "(":
position += 1; value = expression()
if parts[position] != ")": raise ValueError("expected closing parenthesis")
position += 1; return value
raise ValueError("expected integer or parenthesis")
def term():
nonlocal position
value = factor()
while parts[position] == "*":
position += 1; value *= factor()
return value
def expression():
nonlocal position
value = term()
while parts[position] in ("+", "-"):
operator = parts[position]; position += 1; right = term()
value = value+right if operator == "+" else value-right
return value
result = expression()
if parts[position] != "EOF": raise ValueError("trailing token")
return result
for text in ["2+3*4", "(2+3)*4", "8-3-1", "2+", "2 3"]:
try: print(text, "=", evaluate(text))
except ValueError as error: print(text, "error:", error)
Checked output:
2+3*4 = 14 (2+3)*4 = 20 8-3-1 = 4 2+ error: expected integer or parenthesis 2 3 error: trailing token
12. Bottom-up parsing and handles
Shift-reduce parsing builds toward the start symbol by recognizing reduction handles. A stack and tables coordinate shifts, reductions and acceptance.
Answer: No. State/lookahead and viable-prefix context matter.
13. LR items, states and conflicts
LR items describe position in productions; closure/goto construct parser states. SLR uses FOLLOW-based reductions; LR/LALR variants differ in lookahead/state handling.
Answer: No. Their construction and stack meaning differ.
14. Syntax errors and recovery
Diagnostics identify location, offending token and expected construct. Recovery can synchronize at delimiters; one error may trigger later cascades.
Answer: No. Earlier missing delimiters can cause cascading errors.
15. Symbol tables and scope
A symbol table records names, declarations, types and related information. Resolution follows language scope rules; nearest visible binding may shadow an outer declaration.
Answer: No. Declaration/name resolution belongs to semantic analysis.
16. Type checking and coercion
Type rules determine allowed operations, assignments and calls. Static and dynamic checks have different timing; implicit conversions depend on the language.
Answer: Yes. Names, types and contextual rules can fail after parsing.
17. Syntax-directed translation and attributes
Attributes attach computed information to grammar structure; semantic actions can construct ASTs or values. Synthesized/inherited dependencies must be evaluated in a valid order.
Answer: No. Translation must respect the language's defined behavior.
18. IR and three-address code
IR makes operations and control flow explicit and separates front-end concerns from target details. Three-address code often uses temporaries for elementary operations.
Answer: No. The IR must represent relevant source behaviors correctly.
Source: a = b + c * d
IR: t1 = c * d
t2 = b + t1
a = t219. Control flow, basic blocks and backpatching
A basic block is a straight-line unit with suitable entry/exit boundaries. CFG edges represent possible execution; backpatching fills deferred jump targets in some translation schemes.
Answer: No. It should model relevant possible control transfers.
20. Runtime storage and calling conventions
Activation records, parameters, returns, locals and saved state depend on language/runtime and calling convention. Heap allocation and stack-like call behavior serve different lifetimes.
Answer: No. Optimization/runtime representation can change placement.
21. Data-flow analysis and liveness
Data-flow analyses propagate facts over CFGs to a fixed point. Liveness concerns future reads before overwrite; reaching definitions tracks potential originating assignments.
Answer: No. Side effects, exceptions and language observability matter.
22. Optimization and preservation
Constant folding, propagation, common-subexpression elimination, loop transformations and dead-code removal need semantic justification. Overflow and floating-point rules can restrict algebra.
Answer: No. Overflow, rounding, traps and evaluation order can differ.
23. Code generation and register allocation
The back end selects instructions, orders control flow and assigns registers/spills under target constraints. Correct target behavior matters beyond fewer instructions.
Answer: No. Spilling/memory or other allocation choices may be required.
24. Compiler testing and differential checks
Test valid/invalid syntax, precedence, name/type errors and optimization behavior. Compare independent implementations on bounded domains where suitable.
Answer: No. Translation behavior and target execution need tests.
25. Exam pipeline and limitations
Trace characters to tokens, AST, semantic facts, IR and target; distinguish FIRST/FOLLOW, AST/CFG and compile/runtime checks. State assumptions before transformations.
Answer: A worked trace with rules, diagnostics and behavior-preservation limits.
Phase diagnostics
| Phase | Input/output | Example error |
|---|---|---|
| Lexer | Characters -> tokens | Unmatched character |
| Parser | Tokens -> syntax | Missing operand/delimiter |
| Semantic | Syntax + declarations -> checked facts | Undeclared name/type mismatch |
| Optimization | IR -> equivalent IR | Unsafe removal of observable effect |
| Back end | IR -> target | Incorrect calling/register behavior |
LL and LR distinctions
| Aspect | LL / predictive | LR / shift-reduce |
|---|---|---|
| Direction | Top-down derivation | Bottom-up reduction |
| Typical decisions | FIRST/FOLLOW lookahead | State/items/table |
| Left recursion | Basic recursive descent needs removal | Many left-recursive grammars supported |
| Conflict | Competing predictive cell | Shift/reduce or reduce/reduce |
Tiny grammar sets
| Symbol | FIRST terminals / nullable | FOLLOW |
|---|---|---|
| A -> a or empty | {a}; nullable | {b} |
| S -> A b | {a,b}; not nullable | {$} |
| Conventions | Empty tracked separately in code | FOLLOW never contains epsilon |
Revision and implementation checklist
Trace tokens, precedence AST, scope/type facts and IR; calculate nullable/FIRST/FOLLOW; distinguish AST from control flow. Check malformed and trailing input. State side effects, overflow and floating-point constraints before claiming a rewrite is valid.
Resources and sources
Compiler teaching and LLVM front-end tutorials support these concepts. All diagrams and small Python examples here are original, not a production compiler implementation.
Comments
Post a Comment