Regular expressions for token patterns in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the role of regular expressions in token patterns

Which of the following best describes the primary purpose of using regular expressions in defining token patterns during lexical analysis?

A To specify the exact sequence of characters that form valid tokens in the source code

B To optimize the runtime performance of the compiled program

C To execute the source code directly without compilation

D To translate high-level code into machine code

💡 Hint

Think about how lexical analyzers identify meaningful units in code.

Regular expressions define patterns that describe valid tokens, such as identifiers, keywords, or numbers, allowing the lexical analyzer to recognize these tokens in the source code.

📋 Factual

intermediate

Identifying token pattern for integer literals

Which regular expression correctly matches a decimal integer literal consisting of one or more digits?

A "[0-9]?"

B "[a-zA-Z]+"

C "[0-9]+"

D "[0-9]*"

💡 Hint

Consider that the integer must have at least one digit.

The pattern "[0-9]+" matches one or more digits, which correctly represents decimal integer literals. Other options either match letters or allow zero digits.

🔍 Analysis

advanced

Determining the output of a regex-based token matcher

Given the regular expression "a(b|c)?d", which of the following strings will be matched by this pattern?

A "abcd"

B "ad"

C "abbd"

D "acbd"

💡 Hint

Analyze the pattern step-by-step: it starts with 'a', followed by zero or one 'b' or 'c', and ends with 'd'.

The pattern "a(b|c)?d" matches strings starting with 'a', optionally followed by exactly one 'b' or 'c', and ending with 'd'. "ad" matches because the optional part is absent. "abcd" ('bc'), "abbd" ('bb'), and "acbd" ('cb') have two characters between 'a' and 'd', which do not fit the pattern.

❓ Comparison

advanced

Comparing token patterns for identifiers

Which regular expression correctly matches identifiers that start with a letter and are followed by any combination of letters and digits?

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

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

C "[a-zA-Z0-9]+"

D "[a-zA-Z]*[0-9]+"

💡 Hint

Remember that identifiers cannot start with digits.

Option A requires the first character to be a letter, followed by zero or more letters or digits, which matches typical identifier rules. Option A starts with a digit, which is invalid. Option A allows starting with a digit. Option A requires ending with digits and allows zero letters at start, which is invalid.

❓ Reasoning

expert

Analyzing ambiguity in token patterns

Consider two token patterns defined by regular expressions: ID = "[a-zA-Z][a-zA-Z0-9]*" and KEYWORD = "if|int|for". When scanning the input string "int", which token should the lexer produce and why?

A Both tokens simultaneously, because "int" matches both patterns

B ID token, because "int" matches the identifier pattern

C No token, because the input is ambiguous

D KEYWORD token, because keywords have higher priority than identifiers

💡 Hint

Think about how lexers resolve conflicts when multiple patterns match the same input.

Although "int" matches the identifier pattern, lexers typically assign higher priority to keywords to ensure reserved words are recognized correctly. Therefore, "int" is tokenized as a KEYWORD.

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