Regular Expressions

Regular Expressions

1. Definition

A regular expression (RE) is a compact notation for a regular language using **ε, symbols, 丨 (or), concatenation, *, +, ?**. Every token pattern in Lex/Flex is written as an RE.

Precedence: * + ? highest, then concatenation, then 丨 lowest. Parentheses override.

2. Operators with Examples ($Σ$ = {a,b,0,1,letters,digits})

RE	Language
a 丨 b	{a, b}
ab	{ab} only
a*	{ε, a, aa, aaa, ...}
a+	{a, aa, aaa, ...} (no ε)
(a丨b)*abb	strings ending in abb
[a-z][a-z0-9]*	typical identifiers
[0-9]+(\.[0-9]+)?	unsigned numbers

Character classes: [abc] = a丨b丨c, [a-z] = range, [^...] = complement, . = any char (in Lex).

3. RE vs FA

Same power: for every RE there is an FA and vice versa. RE is human notation; FA is machine that runs it.

4. Worked — identifier vs keyword clash

keyword RE:  if | else | while   (exact)
identifier RE: [a-zA-Z_][a-zA-Z0-9_]*
rule: if input is `ifx` → identifier (longest match beats keyword); `if` alone → keyword (priority to keyword on tie)

5. Exam Points

• Write RE for identifier, number, string literal, comment — 5 marks, very frequent.
• Explain operators + precedence — 3 marks, frequent.
• RE for strings ending in abb / containing pattern — 5 marks, frequent in automata-linked questions.