Patterns in Lexical Analysis

What are Patterns?

In compiler design, a pattern is a rule that describes the set of lexemes that can represent a particular token in the source language. Patterns are the formal specifications that tell the lexical analyzer what character sequences constitute valid tokens. They are typically expressed using regular expressions.

Pattern Specification Notation

Regular Expression Notation

Patterns are most commonly specified using regular expressions with these operations:

Regular Definitions

We can name patterns and use those names in other definitions:

Common Token Patterns

Identifiers

Integer Constants

Floating-Point Constants

String Literals

Operators and Punctuation

Comments

Pattern Matching Strategy

The lexical analyzer uses patterns in a specific order to match input:

1. Priority Rules

2. Maximal Munch (Longest Match)

Implementing Pattern Matching

Transition Diagram Approach

Each pattern can be converted to a transition diagram (finite automaton):

Table-Driven Approach

A transition table implements the pattern matching:

Pattern Design Best Practices

1. Unambiguous: Each input should match at most one token
2. Complete: Every valid input character sequence should be matchable
3. Efficient: Patterns should allow fast matching (avoid backtracking)
4. Readable: Use regular definitions for complex patterns
5. Maintainable: Organize patterns logically by token category

Interview Questions

1. What is a pattern in lexical analysis?

A pattern is a formal rule (typically a regular expression) that describes the set of all valid character sequences (lexemes) that can represent a particular token. For example, the pattern letter(letter|digit)* describes all valid identifiers.

1. How are patterns specified in lexical analyzers?

Patterns are specified using regular expressions, which can include concatenation, alternation (|), Kleene closure (*), positive closure (+), optional (?), and character classes ([a-z]). Named regular definitions allow building complex patterns from simpler ones.

1. What is the longest match rule and why is it important?

The longest match rule states that when multiple patterns could match the current input, the lexical analyzer always chooses the longest matching lexeme. This prevents incorrect tokenization — e.g., "integer" should be one identifier, not the keyword "int" followed by "eger".

1. How do you handle the ambiguity between keywords and identifiers?

Keywords have the same pattern as identifiers. The resolution strategy is: first match using the identifier pattern, then check if the matched string is a keyword in a reserved word table. If it is, return the keyword token; otherwise, return an identifier token.

1. Write the pattern for floating-point numbers with optional exponent.

digit+ . digit+ (E [+-]? digit+)? — This matches one or more digits, a dot, one or more digits, and optionally an exponent part (E, optional sign, one or more digits). Examples: 3.14, 1.5e10, 2.0E-3.