[HD] EECS4302 F26 - 2026-09-22 (Tuesday) - Lecture 4

Overview

Jackie Wang explains compiler construction as a sequence of representations: Java source characters become tokens, tokens become parse trees, and semantic analysis can validate or transform those trees before output. The lecture connects compiler correctness to semantics-preserving optimization, illustrating loop-invariant code motion for `2 * b * c` and the parsing-to-pretty-printing workflow; it also previews Assignment 1 and upcoming lexical-analysis work with ANTLR 4.

Key takeaways

Compiler correctness can be reasoned about stage by stage: the front end preserves source meaning in IR1, each optimizer preserves meaning between IRs, and the back end preserves the optimized IR in the target.
Lexical analysis recognizes character patterns as tokens using regular languages; syntactic analysis requires context-free grammar rules to build trees for recursive structures.
A program can be syntactically valid but semantically invalid: both loop examples parse, but redeclaring integer variable `i` causes the second to fail declaration checking.
Loop-invariant code motion improves the example loop by calculating `2 * b * c` once before iteration and reusing a temporary, since `b` and `c` do not change inside the loop.
The compiler workflow can include multiple AST transformations between parsing and pretty printing; those intermediate trees are hidden from users, who see the source-to-output result.

Chapters

0:00 Course Plan: Assignment 1 and Upcoming Compiler Topics

Jackie Wang says Assignment 1 will be released September 23 and will use Java classes and JUnit tests.
The assignment reviews DFA, NFA, and regular expressions, with a two-week completion period.
Lexical analysis begins Thursday; syntactic analysis is planned after reading week, with math-review slides available for set notation and predicate logic.

4:28 Compiler Optimizers Between Front End and Back End

The front end maps source code to an intermediate representation (IR), and the back end maps an IR to a target program.
A compiler can contain multiple optimizer passes, each improving a specific property of an IR.
Optimization can target runtime performance or static structure, such as database normalization when mapping Java classes to tables.

9:26 Compiler Correctness: Preserve Meaning Across IRs

The front end must represent every important source-program concept accurately in IR1.
Each optimizer must preserve the meaning of its input while producing IR2, even if the representation changes.
The back end must accurately implement the optimized IR; correctness across multiple stages follows by composing these preservation guarantees.

14:24 Three Compiler Analyses and the Scanner–Parser Split

Lexical analysis views a Java file as characters; syntactic analysis views it as tokens; semantic analysis evaluates program meaning.
A scanner performs lexical analysis, while a parser performs syntactic analysis.
Lexical and syntactic analysis can be generated from token definitions and grammar rules with ANTLR 4; semantic analysis requires more problem-specific work.

22:14 Parser Input, Context-Free Grammars, and Parse Trees

A parser consumes a sequence of tokens rather than individual characters and builds a tree structure.
Regular expressions and finite automata are insufficient for general recursive grammar patterns, so syntactic analysis uses context-free grammars.
The course will cover top-down and bottom-up parsing approaches after reading week.

24:10 Java Lexical Analysis: Characters Become Tokens

The example Java program begins as a left-to-right character stream, including text such as `class MyClass`.
The scanner recognizes patterns for keywords, identifiers, method names, and punctuation using regular languages.
Whitespace is generally a meaningless delimiter and is discarded, while braces and other meaningful delimiters become tokens.

32:48 From Token Sequences to Nonlinear Abstract Syntax Trees

Character streams and token sequences are linear structures with a unique predecessor and successor for each interior element.
Syntactic analysis converts the linear token sequence into a nonlinear abstract syntax tree (AST), also called a parse tree.
A parse tree groups tokens according to grammar rules and can have multiple children at each node.

38:17 Semantic Analysis: Validate or Transform a Parse Tree

Semantic analysis takes a parse tree as input and may return a yes-or-no compilation result or another tree.
Possible tasks include checking program validity and removing unused imports.
Unlike character-to-token and token-to-tree processing, semantic analysis can transform one AST into another.

41:47 English Essay Analogy: Spelling, Grammar, and Meaning

Checking whether individual English words are spelled correctly parallels lexical analysis.
Checking sentence structure distinguishes grammatical `I love tennis` from the malformed `I tennis`.
Two individually grammatical sentences—`I love tennis` and `I hate racket sport`—can still conflict in meaning, illustrating semantic analysis.

49:49 Recursive Grammar Rules Generate Loop Syntax

The example grammar uses terminals such as `while`, parentheses, and braces, alongside nonterminals such as Boolean expression and implementation.
A recursive implementation rule can represent a statement followed by another implementation, allowing arbitrarily long statement sequences.
An alternative production, shown with a vertical bar, can permit an empty implementation or a recursively extended one.

57:13 Parse Trees Accept Syntax That Type Checking Rejects

Two `while (true)` examples both satisfy the illustrated syntax and can therefore receive parse trees.
The second example declares integer variable `i` twice, so semantic analysis rejects it during type or declaration checking.
Type checking may be performed during parsing for simple cases or as a separate pass over the completed tree.

1:02:34 Representing the Original Loop as an AST

The parse tree represents initial assignments to `b`, `c`, and `a`, followed by a loop from 1 to `n`.
Inside the loop, sequential composition connects the input operation for `d` with the assignment `a = a * 2 * b * c * d`.
This original AST provides the input representation that an optimization pass can restructure.

1:04:52 AST Optimization Moves `2 * b * c` Outside the Loop

The optimized program computes `2 * b * c` once before the loop and stores the result in a temporary variable.
The loop then uses that temporary in the assignment to `a`, avoiding repeated multiplication while preserving program behavior.
Implementing the transformation means adding an assignment branch to the AST and replacing the repeated expression with a variable reference.

1:07:03 Parsing, AST Transformation, and Pretty Printing

The commuting diagram connects an inefficient input program to its parse tree, an optimized tree, and the optimized output program.
Parsing maps concrete program syntax to a tree; semantic analysis can transform that tree; pretty printing converts the final tree back to readable syntax.
Compilers may apply several tree transformations, but end users mainly see the input and output programs.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jackie Wang.