1.2.2 Transition diagrams; longest match and priority rules; lookahead

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

Write the regular definition of number used for tokens. from Lesson 1.2.1
What does a token carry besides its token name? Give two examples. from Lesson 1.1.1
How many prefixes, including ε and the string itself, does relop have? from Lesson 0.2.1

1 · The Story

📖

Peeking

Speeches about software contain comparison marks: <, <=, ==, !=, >, >=. Mira draws herself a flowchart: start in a circle; on “<” go right; then, if the next mark is “=”, stamp LESS-OR-EQUAL; otherwise stamp LESS.

The “otherwise” case hides a problem. To know that “<” stood alone, Mira had to read one mark too many, for example the “3” in “<3”. That “3” belongs to the next word. So she slides it back onto the input pile before stamping. She calls this peeking.

Asha’s question from last time comes back: while fits both the keyword card and the name card. Mira writes two house rules at the top of the catalogue:

Always cut the longest piece that fits some card.
If two cards fit that same longest piece, the card higher in the catalogue wins, and keyword cards sit above the name card.

2 · Predict First

🤔

With the two house rules, how is whilex stamped: keyword while followed by name x, or one name whilex? Write your guess down. The answer is in the vault.

3 · Core Concept

Transition diagrams

A transition diagram is a DFA-like flowchart for recognising one token: states (circles), edges labelled with characters, a start state, and accepting states with an action (return a token). One extra convention: a ***** on an accepting state means the last character read is not part of the lexeme and must be retracted (pushed back into the input) before returning.

Identifiers and keywords

The id diagram loops on letters and digits and leaves on any other character (with a *). Then two common designs:

Pre-load keywords into the symbol table, marked as keywords. On reaching the accepting state, installID() finds or inserts the lexeme, and getToken() returns the keyword token if the entry is marked, else id. One diagram for all words.
Separate diagrams for each keyword (more states, same result).

Two rules that make the choice unique

Longest match: among all patterns, take the longest prefix of the remaining input that matches any pattern.
Priority: if several patterns match that same longest prefix, pick the pattern listed first. Keywords are listed before id.

To find the longest match with a combined DFA, the lexer keeps reading while a move exists, remembers the last position where it was in an accepting state, and when it gets stuck, goes back to that position and returns the token for that state.

Lookahead

The lexer often has to read characters beyond the end of the lexeme just to know the lexeme has ended: one character for < vs <=, more in unlucky languages. In Fortran, blanks are ignored, so DO 5 I = 1.25 (an assignment to the variable DO5I) and DO 5 I = 1,25 (a loop) differ only at the dot or comma, far ahead. C needs at most a few characters of lookahead. The characters read beyond the lexeme are retracted.

Story → compiler term

In the story	In the compiler
Mira’s flowchart	transition diagram
peeking at the next mark	lookahead
sliding the extra mark back	retract (the * states)
“cut the longest piece that fits”	longest match
“the higher card wins”	priority rule (keywords before id)
stamping LESS-OR-EQUAL	return ⟨relop, LE⟩

4 · Visual

Diagram: < · = · other · = · = · other · > · = · other · ! · = · start · 0 · 1 · 2 · return ⟨relop, LE⟩ · 3 · * retract; ⟨relop, LT⟩ · 4 · 5 · return ⟨relop, EQ⟩ · 6 · * retract; ⟨assign⟩ · 7 · 8 · return ⟨relop, GE⟩ · 9 · * retract; ⟨relop, GT⟩ · 10 · 11 · return ⟨relop, NE⟩

Transition diagram for C’s relational operators and =. A * on a state means: the last character read belongs to the next token, so retract (push it back) before returning.

Diagram: letter · letter, digit · other · start · 0 · 1 · 2 · * retract; installID(); return getToken()

Transition diagram for identifiers and keywords. Keywords are pre-loaded in the symbol table, so getToken() tells them apart from names.

5 · Worked Examples

Example 1 Easy

Trace the relational-operator diagram on <=, then on <5.

Solution

<=: 0 –<→ 1 –=→ 2, return ⟨relop, LE⟩, no retract. <5: 0 –<→ 1 –5 (other)→ 3*: retract the 5, return ⟨relop, LT⟩. The 5 starts the next token, exactly the mark Mira slides back.

Example 2 Medium

Tokenize whilex=x>=10 using longest match and priority.

Solution

whilex: id (longest match beats the 5-letter keyword). =: 0 –=→ 4 –x (other)→ 6*, retract, ⟨assign⟩. x: id. >=: 0 –>→ 7 –=→ 8, ⟨relop, GE⟩. 10: number. Tokens: id assign id relop number = 5.

Example 3 GATE

A lexer has three token patterns, listed in priority order: T1 = a(a|b)*, T2 = b+, T3 = (a|b)*c. It uses longest match and then priority. What tokens does it produce for abbacab?

Solution

Position 1: T1 can take abba (4 characters, stops at c); T3 can take abbac (5, needs the c). Longest wins: T3(abbac). Remaining ab: T1 takes ab; T3 cannot (no c left). Output: T3(abbac) T1(ab), verified by simulation. Mira’s first house rule did all the work; priority was never needed.

6 · Shortcuts

⚡

At each position: find every pattern’s longest match, keep the longest, break ties by list order. Then restart right after it. Valid when: lexers with several patterns (longest-match questions).

⚡

A * state costs one retract: count how many characters were read past the lexeme. Valid when: diagrams with “other” edges.

7 · GATE Traps

⚠️

Longest match comes before priority: whilex is one id.
Priority applies only between matches of equal length.
After an “other” edge, the extra character must be retracted, or the next token loses its first character.
A pattern that matches a longer prefix later in the input does not matter; only the current position counts.
Keywords are usually recognised by the id diagram plus a symbol-table check, not by separate diagrams.

8 · Memory Hook

🧠

“Longest first, then highest card.” And a * means: give one back.

9 · Connect the Dots

The lexer can now recognise every token. Next: what happens when the input contains something that fits no card at all, and how a tool can build all these diagrams automatically from a list of patterns.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markLongest match

With keywords listed before id and longest match first, ifx is tokenized as:

(A) keyword if, then id x
(B) one id ifx
(C) a lexical error
(D) keyword if only

Q2MCQ2 marksPattern simulation

Patterns in priority order: T1 = a(a|b)*, T2 = b+, T3 = (a|b)*c. Output for bbaab?

(A) T2(bb) T1(aab)
(B) T3(bbaab)
(C) T2(bbaab)
(D) T2(b) T2(b) T1(aab)

Q3MCQ2 marksPattern simulation

Patterns in priority order: A = ab, B = a(b|c)*, C = (a|b)+c. Output for abab?

(A) A(ab) A(ab)
(B) B(ab) B(ab)
(C) B(abab)
(D) C(abab)

Q4NAT1 markRetract

Using the relop diagram, how many characters are retracted in total while tokenizing a<b>=c? (Count only retractions caused by relop/assign states; id tokens also retract, but ignore those.)

Numerical answer: ________

Q5MSQ1 markRules

Which statements are true?

(A) Priority is used only when two patterns match prefixes of the same length.
(B) Longest match may require reading characters beyond the lexeme.
(C) A * on a state means the lexeme is rejected.
(D) Keywords can be recognised by pre-loading them into the symbol table.

11 · Rule Card

Transition diagram: states, character edges, accepting states with actions; * = retract one character.
Longest match first; then priority (earlier pattern, keywords before id).
Combined DFA: remember the last accepting position; on failure go back to it.
Lookahead: characters read past the lexeme to decide; then retracted.
Keywords: pre-load into symbol table; installID() + getToken().

12 · Concept Ledger

transition diagramretract (* state)longest match rulepriority rulelookaheadinstallID() / getToken()reserved word

13 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Warm-up

number → digits (. digits)? (E [+-]? digits)?
An attribute: a symbol table pointer for an id, the value for a number, the operator kind (LE, GT, …) for relop.
6 (n + 1 with n = 5).

Predict First

One identifier, whilex. Longest match comes first: the id pattern matches all six letters, while the keyword matches only five. Priority only breaks ties between equally long matches.