UNIX regular expressions

Hopcroft 2e, §3.3.1 and §3.3.2.

A UNIX regular expression has far more operators than the three of §3.1 — character classes, +, ?, bounded repetition, anchors, backreferences. Most are pure convenience: they save typing and change nothing about what can be described. One of them is not, and knowing which is the difference between a shorthand and a different class of language.

Does this feature keep the language regular?

Toggle each one to see what it is shorthand for. A feature that can be rewritten using only union, concatenation and star adds no power at all.

Lexical analysis

§3.3.2 — the first stage of a compiler. Each token class is a regular expression; the lexer runs them together and cuts the input into tokens by longest match, breaking ties in favour of the rule declared first.

That tie-break is why a real lexer lists keywords above identifiers. Without it if inside iffy would end the token early, and the compiler would see a keyword where the programmer wrote a name.

The rules, in order. On a tie the first one wins — which is why KEYWORD sits above IDENT.
Rule	Expression	Matches
KEYWORD	aa	A two-letter keyword, like "if".
IDENT	a(a+d)*	A letter then letters or digits.
NUMBER	dd*	One or more digits.
OP	=+\+	An operator: = or +.
SPACE	\ \ *	Runs of spaces.

Snippet — letters as a, digits as d, plus spaces, = and +

aaKEYWORD␣SPACEaddIDENT␣SPACE=OP␣SPACEadIDENT␣SPACE+OP␣SPACEddNUMBER

Try aa against aaa: the first is a KEYWORD, the second an IDENT, because longest match takes the three-letter reading before the two-letter one.

Where this shows up in the exam

The applied case studies on password validation, mobile numbers and log analysis are all this material. So is the tutorial component “lexical analyzer design using regular expressions” on the syllabus.