Regular expressions for token patterns in Compiler Design - Mini Project: Build & Apply

Regular Expressions for Token Patterns

📖 Scenario: You are designing a simple lexical analyzer for a programming language. Your task is to define regular expressions that match specific token patterns such as identifiers, numbers, and operators.

🎯 Goal: Build a set of regular expressions that correctly identify tokens like identifiers, integers, and arithmetic operators.

📋 What You'll Learn

Create variables holding regular expressions for identifiers, integers, and operators

Use standard regular expression syntax for token patterns

Combine simple patterns to form the final regular expressions

Ensure the regular expressions match the exact token definitions

💡 Why This Matters

🌍 Real World

Lexical analyzers use regular expressions to identify tokens in source code during compilation.

💼 Career

Understanding token patterns and regex is essential for compiler developers, language designers, and software engineers working on parsers.

1

Define the identifier pattern

Create a variable called identifier and assign it the regular expression string that matches an identifier. An identifier starts with a letter (a-z or A-Z) followed by zero or more letters or digits (a-z, A-Z, 0-9). Use the pattern ^[a-zA-Z][a-zA-Z0-9]*$.

Compiler Design

# Define the identifier regular expression pattern
# Your code here

Hint

Remember, identifiers start with a letter and can have letters or digits after.

2

Define the integer pattern

Create a variable called integer and assign it the regular expression string that matches an integer number. An integer consists of one or more digits (0-9). Use the pattern ^\d+$.

Compiler Design

identifier = r"^[a-zA-Z][a-zA-Z0-9]*$"
# Define the integer regular expression pattern
# Your code here

Hint

Use \d to represent digits and + to indicate one or more.

3

Define the operator pattern

Create a variable called operator and assign it the regular expression string that matches any of the arithmetic operators: plus (+), minus (-), multiplication (*), or division (/). Use the pattern ^[+\-*/]$.

Compiler Design

identifier = r"^[a-zA-Z][a-zA-Z0-9]*$"
integer = r"^\d+$"
# Define the operator regular expression pattern
# Your code here

Hint

Remember to escape special characters like minus inside the brackets.

4

Combine patterns for token recognition

Create a list called token_patterns that contains tuples pairing token names with their regular expressions. Include the pairs: ("IDENTIFIER", identifier), ("INTEGER", integer), and ("OPERATOR", operator).

Compiler Design

identifier = r"^[a-zA-Z][a-zA-Z0-9]*$"
integer = r"^\d+$"
operator = r"^[+\-*/]$"
# Create the list of token patterns
# Your code here

Hint

Use a list of tuples pairing token names with their regex variables.

Practice

1. What is the main purpose of using regular expressions in compiler design?

easy

A. To define patterns for recognizing tokens in source code

B. To execute arithmetic operations

C. To optimize machine code

D. To manage memory allocation

Solution

1. Step 1: Understand the role of regular expressions

   Regular expressions are used to describe patterns that match sequences of characters.

2. Step 2: Connect to compiler design

   In compiler design, these patterns help identify tokens like keywords, identifiers, and symbols.

3. Final Answer:

   To define patterns for recognizing tokens in source code -> Option A

4. Quick Check:

   Regular expressions = token patterns [OK]

Hint: Regular expressions match text patterns for tokens [OK]

Common Mistakes:

• Confusing regular expressions with code execution
• Thinking they optimize code performance
• Mixing up with memory management

2. Which of the following is the correct regular expression to match an identifier starting with a letter followed by letters or digits?

easy

A. [a-zA-Z][a-zA-Z0-9]*

B. [0-9][a-zA-Z]*

C. [a-zA-Z0-9]+[a-zA-Z]*

D. [0-9]+[a-zA-Z0-9]*

Solution

1. Step 1: Identify the pattern for an identifier

   An identifier starts with a letter, then can have letters or digits.

2. Step 2: Match the regular expression

   [a-zA-Z][a-zA-Z0-9]* matches one letter [a-zA-Z] followed by zero or more letters or digits [a-zA-Z0-9]*.

3. Final Answer:

   [a-zA-Z][a-zA-Z0-9]* -> Option A

4. Quick Check:

   Letter + letters/digits = [a-zA-Z][a-zA-Z0-9]* [OK]

Hint: Start with letter, then letters or digits [OK]

Common Mistakes:

• Starting identifier with a digit
• Using + instead of * incorrectly
• Allowing digits as first character

3. Given the regular expression \d{3}-\d{2}-\d{4}, what kind of token does it match?

medium

A. A date in format YYYY-MM-DD

B. A phone number with area code

C. A US Social Security Number format

D. An IP address

Solution

1. Step 1: Analyze the regular expression pattern

   \d{3} means exactly 3 digits, then a dash, then 2 digits, dash, then 4 digits.

2. Step 2: Identify the token format

   This matches the US Social Security Number format: 3 digits - 2 digits - 4 digits.

3. Final Answer:

   A US Social Security Number format -> Option C

4. Quick Check:

   \d{3}-\d{2}-\d{4} = SSN format [OK]

Hint: Count digits and dashes to identify pattern [OK]

Common Mistakes:

• Confusing with date formats
• Assuming phone number format
• Ignoring exact digit counts

4. Identify the error in this regular expression intended to match floating-point numbers: \d+\.\d*

medium

A. It requires at least one digit after decimal point

B. The dot is not escaped properly

C. It matches only integers

D. It does not allow numbers without decimal part

Solution

1. Step 1: Understand the pattern meaning

   \d+ means one or more digits, \. means a literal dot, \d* means zero or more digits after dot.

2. Step 2: Check what numbers it matches

   This matches numbers with a decimal point and optional digits after it, but does not match integers without a dot.

3. Final Answer:

   It does not allow numbers without decimal part -> Option D

4. Quick Check:

   Pattern requires dot, so no integers [OK]

Hint: Check if integers without dot are matched [OK]

Common Mistakes:

• Thinking dot is unescaped
• Assuming digits after dot are mandatory
• Confusing * and + quantifiers

5. How would you write a regular expression to match either the keyword if or else but not identifiers containing these as substrings?

hard

A. (if|else)+

B. \b(if|else)\b

C. if|else

D. [ifelse]+

Solution

1. Step 1: Understand the requirement

   We want to match exactly the words 'if' or 'else', not parts of longer words.

2. Step 2: Use word boundaries

   \b marks word boundaries, so \b(if|else)\b matches only whole words 'if' or 'else'.

3. Step 3: Check other options

   (if|else)+ allows repeated keywords, if|else matches substrings anywhere, [ifelse]+ matches any combination of letters i,f,e,l,s.

4. Final Answer:

   \b(if|else)\b -> Option B

5. Quick Check:

   Word boundaries ensure exact keyword match [OK]

Hint: Use \b for exact word matching [OK]

Common Mistakes:

• Not using word boundaries
• Using character classes instead of groups
• Allowing partial matches inside identifiers