Compiler Construction: Regular Expressions

Regular Expressions are used in the Lexical Analyzer phase of the compiler. We use Lex or flex to create the lexical analysis tool that is used later on.

Some Useful RegEx

RegEx (r)	Meaning	Example	Recognized Inputs
a	The character a	a	a
\n	The newline	\n	\n
.	Any character excluding \n	.	a, b, A, B, 0, \t, +
"test"	The string "test"	"test"	test
r+	One or more occurrences of regex r	a+	a, aa, aaa, aaaaaaaaa
r*	Zero or more occurrences of regex r	a*	\0, a, aa, aaa, aaaaaaaa
r?	Zero or one occurrences of regex r	a?	\0, a
^r	Regex r at the start of an input	^a	a, abc, abcdef
r$	Regex r at the end of an input	a$	a, cba, fedcba
[class]	Any character from the string within the [] (Character Class)	[aeiou]	a, e, i, o, u
[^class]	Any character not from the string within the [] (Character Class)	[^aeiou]	b, c, d, f, g
[start-end]	Range of ascii characters (separated by hyphen -)	[a-z]	a, b, c, d, z
r{m,n}	Regex r at least m times and at most n times	a{2,5}	aa, aaaa, aaaaa
r1r2	Concatenation of regex r1 and regex r2	ab	ab
r1|r2	Regex r1 or regex r2	a|b	a, b
(r)	Higher Precedence (grouping regex)	(a|b)?	\0, a, b
[ \t\n]	Class of whitespaces	[ \t\n]	, \t, \n

More information on Regular Expressions can be found

• Official Flex Documentation
• This Cheat Sheet Page

Conflicting RegEx

Some Regex can be used to match multiple patterns in the same input. But this issue is resolved by lex itself.

1. Multiple prefixes match multiple patterns:

   %%
   a   printf("1A");
   aa  printf("2A");
   %%

   Now assume the input is aaa. Lex matches the longest matching prefix first and gives the output as 2A1A

2. Single prefix matches multiple patterns:

   l [a-zA-Z]
   d [0-9]
   %%
   {l}({l}|{d})    printf("ID");
   'if'            printf("IF");
   %%

   Now assume the input is if. Lex matches the first matched pattern in the rules section and gives the output as ID