[HD] EECS4302 F26 - 2026-10-27 (Tuesday) - Lecture 12

Overview

Jackie Wang reviews DFA minimization and demonstrates how a scanner recognizes tokens by converting regular-expression patterns into a DFA and tracing its transitions with a stack. Using the register pattern R[0-9]+, the lecture explains token categories, longest valid-prefix recovery, and how the lexer’s token sequence becomes the parser’s input for building a parse tree.

Key takeaways

DFA minimization terminates when an iteration produces the same partition as the previous one; each refinement splits states that transition differently under some input.
A candidate DFA-minimization subset must be splittable, a proper subset, and maximal among subsets meeting those conditions.
The register pattern R[0-9]+ accepts an uppercase R followed by at least one digit, and its DFA reaches accepting state S2 only after reading a digit.
The scanner’s stack preserves earlier states so that after an error transition, it can backtrack to the most recent accepting state and return the longest accepted prefix.
Lexing maps characters to categorized tokens, while parsing maps the resulting token sequence into a tree; these are distinct stages with different inputs and outputs.

Chapters

0:00 Assignment 2, Project, and Upcoming Assessments

Assignment 2, focused on compiler implementation, is due October 28; Jackie Wang says solutions will be available after the deadline.
The programming test is scheduled for November 5, with a practice guide and test expected before Thursday’s class.
A tentative Monday lab session will simulate test conditions; a written test is planned about two weeks after the programming test.

3:25 DFA Minimization Stops at a Fixed Point

Each outer-loop iteration copies the current partition P into the previous result and rebuilds T from an empty set.
If the updated partition T differs from P, the algorithm found a refinement and must continue; equality marks the fixed point.
The lecture site contains written solutions for the assigned DFA-minimization exercises.

4:54 Recording DFA-Minimization Iterations in a Table

Jackie Wang tracks P, T, and the splittable subset S across initialization and successive iterations.
The initial P separates accepting states S3 and S5 from non-accepting states, including the error state, S0, S1, S2, and S4.
T starts empty, so the initial P and T differ and the first iteration must run.

7:49 Choosing the Splittable Subset S

A valid S must be splittable: some input character sends its states to a different partition.
S must be a proper subset, rather than a whole partition whose states all transition together.
Among eligible subsets, choose the maximum one; in the worked example, S2 and S4 are split out in the first iteration.

10:49 Updating DFA Partitions and Checking Convergence

After the first iteration, the partitions include {S2, S4}, {error, S0, S1}, and {S3, S5}.
Because P and T differ after that refinement, another iteration is required; the next P is copied from T.
For an exam trace, Jackie Wang says the minimization pseudocode will be provided, but students should understand the iteration steps.

13:55 Combining Regular Expressions into Scanner Token Categories

A scanner defines a regular-expression pattern for each of n token categories, such as registers, identifiers, and whitespace.
The patterns are combined by union, so a matching input segment can be returned as a token with its corresponding category.
ANTLR 4 automates scanner construction from token patterns; rule order or priority can resolve competing matches.

22:47 From Register Pattern R[0-9]+ to a Minimized DFA

The register example uses uppercase R followed by one or more digits, matching strings such as R01 and R0123.
The regular expression is converted through an epsilon-NFA into a DFA, then minimized before implementation.
A DFA transition table can be implemented with a two-dimensional array or a hash map.

31:07 Reading the Register DFA and Its Transition Table

The example DFA uses S0 for the start, S1 after reading R, S2 after at least one digit, and SE for errors.
S2 is the accepting state and carries the register token category; S0, S1, and SE are non-accepting.
The transition table groups input as register-start R, digit, and other; the diagram includes transitions into the explicit error state.

34:58 Scanner Trace Setup for the Input R2

The worked input is R2 followed by EOF, and the trace tracks the accumulated word, current state, category, and stack.
The scanner starts in S0 with an empty word and a stack initialized with the bottom marker.
The first loop continues until the current DFA state becomes the error state.

42:00 Tracing R and 2 Through DFA States S0, S1, and S2

Reading R appends it to the word, records the register category, and transitions the DFA from S0 to S1.
Reading 2 appends the digit, updates the current category to digit, and transitions from S1 to accepting state S2.
The stack saves prior states so the scanner can recover the last accepting position if a later character causes an error.

48:19 EOF Triggers Backtracking to the Last Accepting State

Reading EOF from S2 transitions to SE, ending the first loop while S2 remains on top of the stack.
The second loop pops S2 and truncates the accumulated input from R2EOF back to R2.
Because S2 is accepting, the scanner returns the recognized register rather than treating the trailing EOF transition as a lexical error.

55:45 Returning Register Tokens and Practicing Error Cases

The scanner result separates token type register from the token text R2.
Students are asked to trace the longer input R24 followed by EOF and a case with R24 followed by a multiplication symbol and 3.
The example is a simplified scanner for one token category; a complete scanner must keep processing input and combine multiple patterns.

59:19 Lexer-to-Parser Pipeline and the Move to Parsing

The lexer turns a file’s character sequence into a linear sequence of categorized tokens using the union of regular-expression patterns.
The parser consumes that token sequence and constructs a non-linear parse tree or abstract syntax tree.
The next lectures introduce top-down and bottom-up parsing and review context-free grammars, derivations, and parse trees.

Transcript excerpt

0:05 All right, just before we wrap up the very last topic for lexical analysis, I would like to remind everybody over here. So, lecture digest, uh notes template, usual place, no surprise. And for the minimizing DFA exercise we did, we did a simple one, and there were another two I assigned as exercises for the for you guys. You can look at the solution right here, okay? I just checked that it's actually there. So, if you go to the lecture site, you will see under exercises, minimizing DFA. If you open that, it shows you the written solution. Of course, go over that. If you got any doubts about any steps, do let me know. But, I do want to uh go a little bit more about the algorithm today, just to show to you uh how you can trace the algorithm. That

0:52 might just give you a little more insight. But, you can take a look at the solution. It's right there, okay? Just make sure you can find it. And then, of course, your assignment number two and projects are going uh ongoing. Let's look at the calendar here because your very first assessment is happening soon. Not this week, don't worry, but next week, okay? So, let's look at the schedule here. Actually, your assignment number two will be due tomorrow, the 28th, right? So, do the best you can. Apparently, assignment two it's uh about implementing the compiler. Make sure you finish the tutorial and try the best you can about the programming exercises. I'll give you the solution also after the deadline. And next uh Thursday, which will be

1:38 uh November 5th, it will be your programming test happening. I'm still uh confirming the lab room, but I'll definitely make sure uh I I keep you

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

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.