Theoretical Aspects of Lexical Analysis

Lexical analysis, the first step in the compilation process, splits the input data into segments and classifies them. Each segment of the input (a lexeme) will be assigned a label (the token).

In this case, we will be using regular expressions for recognizing portions of the input text.

Regular Expressions

Regular expressions are defined considering an alphabet { a, b, ..., c } and the empty string eps.

• eps
• a

Primitive constructors:

• concatenation
• alternative
• Kleene-star (*)

Extensions:

• Transitive closure (+) - a+ ("one or more 'a'")
• Optionality (?) - a? ("zero or one 'a'")
• Character classes - [a-z] ("all chars in the 'a-z' range" - only one character is matched)