ACompressed recap
🧾
Each token name has a pattern written as a regular definition (digit, letter, id, number, relop, ws). A lexer turns patterns into transition diagrams: DFA-like flowcharts whose accepting states return tokens, with * meaning retract one character. Overlaps are resolved by longest match first and priority (list order, keywords before id) second. Lookahead is the reading past a lexeme needed to know it has ended.
BMerged rule card
1.2.1 Writing token definitions as regular expressions
- digit → [0-9]; digits → digit+; letter → [A-Za-z_].
- id → letter (letter | digit)*.
- number → digits (. digits)? (E [+-]? digits)?.
- relop → | = | == | != | > | >=.
- ws → (blank | tab | newline)+ gives no token.
- Patterns overlap (keywords match id): resolve by rules, not by the patterns.
1.2.2 Transition diagrams; longest match and priority rules; lookahead
- 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().
CInterleaved GATE-style questions
Q1MCQ1 markPatterns
Which lexeme matches digits (. digits)? (E [+-]? digits)??
- (A) 3.
- (B) 3.0E-2
- (C) E10
- (D) 3E
Q2MCQ2 marksLongest match
Patterns in priority order: T1 = a(a|b)*, T2 = b+, T3 = (a|b)*c. Output for cab?
- (A) T3(c) T1(ab)
- (B) T3(cab)
- (C) T1(ab) after an error
- (D) T3(ca) T2(b)
Q3MCQ1 markPriority
Why are keyword patterns listed before the id pattern?
- (A) so that longer identifiers win
- (B) so that a keyword wins when both match the same lexeme
- (C) so that ids are never recognised
- (D) because keywords are longer
Q4NAT2 marksPattern simulation
Patterns in priority order: A = ab, B = a(b|c)*, C = (a|b)+c. How many tokens are produced for abcab?
Numerical answer: ________
Q5MSQ1 markTransition diagram
In the relop diagram, which inputs end in a state marked * (needing a retract)?
- (A)
<x - (B)
<= - (C)
=a - (D)
!=
Q6MCQ1 markLookahead
In C, distinguishing < from <= needs how many characters of lookahead beyond <?
- (A) 0
- (B) 1
- (C) 2
- (D) unbounded
Q7MSQ1 markRegular definitions
Which are valid regular definitions (each name defined only by earlier names and symbols)?
- (A) digit → [0-9]
- (B) digits → digit+
- (C) id → letter ( letter | digit )* (with letter defined earlier)
- (D) num → num digit
Q8NAT1 markTokens
How many tokens does whilex=x>=10 produce?
Numerical answer: ________
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: (B)1 mark
Digits, fraction, exponent with sign: valid.
- (A) is wrong: A dot needs digits after it.
- (C) is wrong: Must start with digits.
- (D) is wrong: E needs digits after it.
Re-read: Lesson 1.2.1 — Writing token definitions as regular expressions
Q2 Answer: (A)2 marks
At position 1 only T3 matches, taking just c. Then T1 takes ab.
- (B) is wrong: T3 must end in c.
- (C) is wrong: c is matched by T3, no error.
- (D) is wrong: T3 cannot end in a.
Re-read: Lesson 1.2.2 — Transition diagrams; longest match and priority rules; lookahead
Q3 Answer: (B)1 mark
Priority breaks ties of equal length in favour of the earlier pattern.
- (A) is wrong: Longest match already does that.
- (C) is wrong: Ids that are not keywords still match.
- (D) is wrong: Length is irrelevant to the order.
Re-read: Lesson 1.2.2 — Transition diagrams; longest match and priority rules; lookahead
Q4 Answer: 22 marks
B takes abc (longest at position 1; C would also need ab+c = abc, but B is listed first), then A takes ab: B(abc) A(ab) → 2.
Re-read: Lesson 1.2.2 — Transition diagrams; longest match and priority rules; lookahead
Q5 Answer: (A) (C)1 mark
< followed by other, and = followed by other, both retract. <= and != do not.
Re-read: Lesson 1.2.2 — Transition diagrams; longest match and priority rules; lookahead
Q6 Answer: (B)1 mark
One more character decides.
- (A) is wrong: Without looking ahead, the lexer cannot know.
- (C) is wrong: One is enough.
- (D) is wrong: That is the Fortran problem, not C’s.
Re-read: Lesson 1.2.2 — Transition diagrams; longest match and priority rules; lookahead
Q7 Answer: (A) (B) (C)1 mark
A regular definition cannot use its own name on the right.
Re-read: Lesson 0.2.2 — Regular expressions (what lexical analysis needs)
Q8 Answer: 51 mark
id(whilex) assign id(x) relop(GE) number(10) = 5.
Re-read: Lesson 1.2.2 — Transition diagrams; longest match and priority rules; lookahead