Writing token definitions as regular expressions

0 · Recall Warm-up

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

• How many tokens are in x+++y, and why? from Lesson 1.1.2
• Give the postorder of a tree with root R and children A and B (in that order). from Lesson 0.2.4
• Which phase reports an illegal character such as @? from Lesson 0.1.3

1 · The Story

📖

Cards for every kind of word

Mira moves to a new project: speeches about software, full of C words. She writes one card per kind of word, building cards from smaller cards so that nothing is written twice.

First the small cards: digit (0 to 9), letter (A to Z, a to z, and the underscore). Then name: a letter, then letters or digits. Then number: digits, optionally a dot and more digits, optionally an exponent part. One card for the comparison marks, one for blanks.

Her assistant Asha notices a problem: the word while fits the name card and also the keyword card. “Both cards fit. Which stamp do I use?” Mira writes a note on the catalogue: check the order of the cards. That note becomes the next lesson.

2 · Predict First

🤔

Is 1.E5 a number under the definition “digits, optionally (. digits), optionally (E [+−]? digits)”? Write your guess down. The answer is in the vault.

3 · Core Concept

From kinds of words to regular definitions

Each token name gets one pattern, written as a regular definition (Primer 0.2.2). Smaller names are defined first and reused:

digit    → [0-9]
digits   → digit+
letter   → [A-Za-z_]
id       → letter ( letter | digit )*
number   → digits ( . digits )? ( E [+-]? digits )?
relop    → <  |  <=  |  ==  |  !=  |  >  |  >=
if       → if        else → else        while → while
ws       → ( blank | tab | newline )+

From pattern to token

More C patterns

hex       → 0 [xX] [0-9a-fA-F]+
char      → ' ( [^'\\] | \\ . ) '
string    → " ( [^"\\\n] | \\ . )* "
comment   → // [^\n]*    |    /* ( anything not containing */ ) */

The string pattern reads: a quote, then any number of either ordinary characters (not a quote, backslash or newline) or a backslash followed by any character (escapes like \n, \"), then a closing quote.

When patterns overlap

Patterns are written independently, so they overlap: while matches both while and id; <= starts like <. A list of patterns alone does not say which token to produce. The lexer needs two extra rules, longest match and priority, taught next.

Story → compiler term

4 · Visual

The number pattern as three parts; only the first is required.

Checked against the regular expression by running it.

5 · Worked Examples

Example 1 Easy

Which of 12, 3.14, 6.02E23, 1.E5, .5 match number?

Solution

12, 3.14 and 6.02E23 match. 1.E5 fails (no digit after the dot) and .5 fails (no leading digits). Mira’s number card is strict about digits on both sides of the dot.

Example 2 Medium

Write a pattern for C hexadecimal constants such as 0x1F and 0XabC.

Solution

0 [xX] [0-9a-fA-F]+. It accepts 0x1F and 0XabC and rejects 0X (no digits) and 0xg1 (g is not a hex digit). Checked by running the expression.

Example 3 GATE

Which of _tmp9, 9lives, max_val, a-b, int match the id pattern [A-Za-z_][A-Za-z0-9_]*? Which of the matching ones still does not become an id token?

Solution

_tmp9, max_val and int match the pattern. 9lives starts with a digit; a-b contains a minus (it is three tokens). int matches the id pattern but becomes the keyword token int, the overlap Asha found, resolved by priority in the next lesson.

6 · Shortcuts

⚡

Test a lexeme against a pattern from left to right, ticking off each required part; optional parts (?) can be skipped, starred parts can repeat or vanish. Valid when: membership questions on number, id, string patterns.

⚡

Keywords match id. Whenever an id pattern is given, check whether the lexeme is reserved. Valid when: questions mixing keywords and identifiers.

7 · GATE Traps

⚠️

• digits means digit+ (at least one).
• Under the textbook number pattern, 1.E5 and .5 are not numbers, even though real C accepts them; follow the definition in the question.
• The id pattern also matches keywords; the pattern alone does not decide the token.
• Escapes inside a string (") do not end the string.

8 · Memory Hook

🧠

Small cards build big cards: digit → digits → number; letter → id.

9 · Connect the Dots

Patterns describe each token kind, but they overlap and can be matched in several lengths. The next lesson draws a pattern as a flowchart of states and adds the two rules that make the lexer’s choice unique: longest match and priority.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MSQ1 markPatterns

Which lexemes match [A-Za-z_][A-Za-z0-9_]*?

• (A) _tmp9
• (B) 9lives
• (C) max_val
• (D) a-b

Q2MCQ1 markNumber pattern

Under digits (. digits)? (E [+-]? digits)?, which lexeme is a number?

• (A) 1.E5
• (B) .5
• (C) 6.02E23
• (D) E5

Q3MCQ1 markHex

Which pattern describes C hexadecimal constants?

• (A) [0-9a-f]+
• (B) 0[xX][0-9a-fA-F]+
• (C) 0x[0-9]+
• (D) [xX][0-9a-fA-F]*

Q4MCQ1 markOverlap

The lexeme while matches the id pattern. In a C lexer it becomes:

• (A) an id token
• (B) the keyword token while
• (C) two tokens wh and ile
• (D) a lexical error

Q5MSQ2 marksString pattern

Given string → " ( [^"\\\n] | \\. )* ", which lexemes are complete string literals?

• (A) "abc"
• (B) "a"b"
• (C) "x
• (D) ""

11 · Rule Card

• 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.

12 · Concept Ledger

regular definition for tokensdigit / digits / letterid patternnumber patternrelopwshex patternstring patternoverlapping patterns

13 · Answer Vault