Regular expressions for token patterns in Compiler Design - Step-by-Step Execution

Concept Flow - Regular expressions for token patterns

Start

↓

Input string

↓

Apply regex patterns

↓

Match token pattern?

No→Error or skip

Yes↓

Extract token

↓

Store token

↓

More input?

Yes→Apply regex patterns

No↓

End

The process starts with an input string, applies regex patterns to find tokens, extracts and stores them, and repeats until all input is processed.

Execution Sample

Compiler Design

Input: "var x = 42;"
Patterns: identifier=[a-zA-Z_][a-zA-Z0-9_]*
          number=[0-9]+

This example shows how regex patterns match tokens like identifiers and numbers in a simple code snippet.

Analysis Table

Step	Input Segment	Regex Pattern	Match Result	Token Extracted	Next Action
1	"var x = 42;"	identifier=[a-zA-Z_][a-zA-Z0-9_]*	Matches 'var'	Token: identifier='var'	Store token, move forward
2	" x = 42;"	identifier=[a-zA-Z_][a-zA-Z0-9_]*	Matches 'x'	Token: identifier='x'	Store token, move forward
3	" = 42;"	identifier=[a-zA-Z_][a-zA-Z0-9_]*	No match	-	Try next pattern
4	" = 42;"	number=[0-9]+	No match	-	Try next pattern or skip
5	" = 42;"	symbol '='	Matches '='	Token: symbol='='	Store token, move forward
6	" 42;"	number=[0-9]+	Matches '42'	Token: number='42'	Store token, move forward
7	" ;"	symbol ';'	Matches ';'	Token: symbol=';'	Store token, move forward
8	" "	-	-	End of input reached	-

💡 All input processed, no more tokens to extract.

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
Input String	"var x = 42;"	" x = 42;"	" = 42;"	" = 42;"	" = 42;"	" 42;"	" ;"	" "	""
Current Token	-	'var'	'x'	-	-	'='	'42'	';'	-
Tokens List	[]	['var']	['var', 'x']	['var', 'x']	['var', 'x']	['var', 'x', '=']	['var', 'x', '=', '42']	['var', 'x', '=', '42', ';']	['var', 'x', '=', '42', ';']

Key Insights - 3 Insights

Why does the regex pattern for identifier not match the '=' symbol?

Because the identifier pattern only matches letters, digits, or underscores starting with a letter or underscore, '=' is not included, so no match occurs (see execution_table step 3).

What happens when no regex pattern matches the current input segment?

The lexer tries the next pattern or skips the character if none match, preventing infinite loops (see execution_table step 4).

How does the lexer know when to stop processing input?

When the input string is empty after extracting tokens, the lexer stops (see execution_table step 8).

Visual Quiz - 3 Questions

Look at the execution_table at step 2. What token is extracted from the input segment?

A number='x'

B identifier='x'

C symbol='x'

D No token extracted

💡 Hint

Check the 'Token Extracted' column at step 2 in the execution_table.

At which step does the lexer match the number token '42'?

A Step 6

B Step 5

C Step 4

D Step 7

💡 Hint

Look for the 'number' pattern match in the execution_table.

If the input started with '123var', which token would the lexer extract first?

A symbol='1'

B identifier='123var'

C number='123'

D No token extracted

💡 Hint

Recall that number pattern matches digits only and identifier must start with a letter or underscore.

Concept Snapshot

Regular expressions define patterns to identify tokens in input text.
Lexer applies these patterns sequentially to extract tokens.
Tokens include identifiers, numbers, symbols, etc.
If no pattern matches, lexer skips or errors.
Process repeats until input is fully tokenized.

Full Transcript

This visual execution trace shows how regular expressions are used to identify token patterns in a string. Starting with the full input, the lexer applies regex patterns like identifier and number to find matches. When a pattern matches, the corresponding token is extracted and stored, and the input moves forward. If no pattern matches, the lexer tries the next pattern or skips the character. This continues until the entire input is processed. The variable tracker shows how the input string shortens and tokens accumulate. Key moments clarify common confusions such as why certain characters don't match specific patterns and how the lexer knows when to stop. The quiz questions test understanding of token extraction steps and pattern matching order.

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