Q2Compiler Design
Question
2 marks
Define Regular Expression.
Answer
A Regular Expression is a notation for specifying patterns of strings over an alphabet, used in lexical analysis to define the patterns of tokens.
A Regular Expression (RE) is a formula that describes a set of strings (a regular language) over an alphabet Σ. Regular expressions are the standard notation for specifying the patterns of tokens in lexical analysis. They are defined inductively:
- Basis: ε (empty string), ∅ (empty set), and any symbol a ∈ Σ are regular expressions.
- Union (Alternation): If r and s are REs, then r|s is an RE denoting L(r) ∪ L(s).
- Concatenation: If r and s are REs, then rs is an RE denoting L(r) · L(s).
- Kleene Closure: If r is an RE, then r* is an RE denoting zero or more repetitions of strings in L(r).
- Positive Closure: r+ = rr* (one or more repetitions).
- Optional: r? = r|ε (zero or one occurrence).
- Example: Identifier = letter(letter|digit)* where letter = [a-zA-Z_].