Tokens, patterns, and lexemes in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the relationship between tokens, patterns, and lexemes

Which of the following best describes the relationship between tokens, patterns, and lexemes in lexical analysis?

A A lexeme is a category defined by a pattern, and a token is the actual string matching that pattern.

B A pattern is the actual string, a lexeme is the category, and a token is the rule to match them.

C A token is a category defined by a pattern, and a lexeme is the actual string matching that pattern.

D Tokens, patterns, and lexemes all mean the same thing and are interchangeable terms.

💡 Hint

Think about what each term represents in the scanning process.

A token is a type or category (like 'identifier' or 'number'), defined by a pattern (a rule or regular expression). A lexeme is the actual substring from the source code that matches the pattern.

📋 Factual

intermediate

Identifying lexemes from source code

Given the source code snippet: int count = 42;, which of the following is NOT a lexeme?

A "number"

B "count"

C "="

D "int"

💡 Hint

Lexemes are actual substrings from the source code.

"number" is not present in the source code snippet, so it cannot be a lexeme. The others are exact substrings.

🔍 Analysis

advanced

Determining the token sequence from a code snippet

Consider the code snippet: sum = a + b * 10;. Which sequence of tokens correctly represents this snippet?

A identifier, assignment_operator, identifier, plus_operator, identifier, multiply_operator, number, semicolon

B keyword, assignment_operator, identifier, plus_operator, identifier, multiply_operator, number, semicolon

C identifier, equals_sign, identifier, plus_sign, identifier, multiply_sign, number, semicolon

D identifier, assignment_operator, identifier, plus_operator, identifier, multiply_operator, number

💡 Hint

Focus on the categories of tokens, not the exact characters.

The snippet contains identifiers (sum, a, b), operators (assignment '=', plus '+', multiply '*'), a number (10), and a semicolon. Option A correctly names these token categories. Option A incorrectly labels 'sum' as a keyword. Option A uses character names instead of token categories. Option A misses the semicolon token.

❓ Comparison

advanced

Comparing patterns for identifiers

Which of the following patterns correctly describes a typical identifier in many programming languages?

A Contains only digits and special characters.

B Starts with a digit, followed by letters or underscores.

C Starts with a special character, followed by letters or digits.

D Starts with a letter or underscore, followed by any number of letters, digits, or underscores.

💡 Hint

Think about common rules for variable names.

Identifiers usually start with a letter or underscore and can contain letters, digits, or underscores afterward. Starting with a digit or special character is generally invalid.

❓ Reasoning

expert

Effect of ambiguous patterns on lexical analysis

Suppose a lexical analyzer has two patterns: one for keywords (e.g., "if", "while") and one for identifiers (any letter followed by letters or digits). If the input is "if", what will the lexical analyzer output and why?

A It outputs both tokens "keyword" and "identifier" for the same lexeme.

B It outputs the keyword token "if" because keyword patterns have higher priority.

C It raises an error due to ambiguity between keyword and identifier patterns.

D It outputs an identifier token "if" because identifiers match any letter sequence.

💡 Hint

Consider how lexical analyzers resolve conflicts between overlapping patterns.

Lexical analyzers typically assign higher priority to keywords over identifiers. Even though "if" matches the identifier pattern, it is recognized as a keyword token.

Practice

1. What is a token in compiler design?

easy

A. The exact sequence of characters in the source code

B. A category or label for a group of characters

C. A rule describing valid sequences of characters

D. A syntax error found during compilation

Solution

1. Step 1: Understand the role of tokens

   Tokens act like words in a sentence, grouping characters into meaningful categories.

2. Step 2: Differentiate tokens from lexemes and patterns

   Lexemes are the actual text, patterns are rules, tokens are the labels for those texts.

3. Final Answer:

   A category or label for a group of characters -> Option B

4. Quick Check:

   Token = label/category [OK]

Hint: Tokens are like word types, not the words themselves [OK]

Common Mistakes:

• Confusing tokens with lexemes
• Thinking tokens are the exact text
• Mixing tokens with syntax errors

2. Which of the following correctly describes a pattern in lexical analysis?

easy

A. The exact characters matched in the source code

B. A syntax error detected during compilation

C. The output of the parser after syntax analysis

D. A rule or regular expression defining valid tokens

Solution

1. Step 1: Define what a pattern is

   Patterns describe the rules or formats that valid tokens must follow, often using regular expressions.

2. Step 2: Eliminate incorrect options

   Exact characters are lexemes, parser output is unrelated, syntax errors are not patterns.

3. Final Answer:

   A rule or regular expression defining valid tokens -> Option D

4. Quick Check:

   Pattern = rule for tokens [OK]

Hint: Patterns are rules, not actual text [OK]

Common Mistakes:

• Confusing patterns with lexemes
• Thinking patterns are output of parsing
• Mixing patterns with errors

3. Given the source code snippet: int count = 10; Which of the following is a correct lexeme for the token identifier?

medium

A. count

B. =

C. 10

D. int

Solution

1. Step 1: Identify the token 'identifier'

   An identifier token represents names like variables or functions.

2. Step 2: Match lexemes to token types

   In the snippet, 'count' is the variable name, so it is the lexeme for the identifier token.

3. Final Answer:

   count -> Option A

4. Quick Check:

   Identifier lexeme = count [OK]

Hint: Identifiers are names, not keywords or symbols [OK]

Common Mistakes:

• Choosing keywords like 'int' as identifiers
• Selecting numbers or operators as identifiers
• Confusing lexemes with token types

4. Identify the error in this tokenization process for the input var_1 = 25;: Tokens identified are var (identifier), _1 (identifier), = (assignment), 25 (number), ; (semicolon).

medium

A. The underscore and digit should be part of the same identifier token

B. The assignment operator should be tokenized as two separate tokens

C. The number 25 should be split into two tokens '2' and '5'

D. The semicolon should not be a token

Solution

1. Step 1: Understand identifier token rules

   Identifiers can include letters, digits, and underscores as one token, not split.

2. Step 2: Analyze the given tokenization

   Splitting 'var_1' into 'var' and '_1' is incorrect; it should be one identifier token.

3. Final Answer:

   The underscore and digit should be part of the same identifier token -> Option A

4. Quick Check:

   Identifier tokens include underscores and digits [OK]

Hint: Keep underscores and digits inside one identifier token [OK]

Common Mistakes:

• Splitting identifiers incorrectly
• Misinterpreting assignment operator tokenization
• Ignoring semicolon as a token

5. You want to design a lexical analyzer that recognizes tokens for integers and identifiers. Which pattern correctly matches an identifier but not an integer?

hard

A. [a-zA-Z0-9]+

B. [0-9]+

C. [a-zA-Z_][a-zA-Z0-9_]*

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

Solution

1. Step 1: Understand identifier and integer patterns

   Identifiers start with a letter or underscore, followed by letters, digits, or underscores. Integers are digits only.

2. Step 2: Eliminate incorrect options

   A matches integers like '123'; B matches only integers; D fails to match identifiers ending in digits like 'var1'.

3. Final Answer:

   [a-zA-Z_][a-zA-Z0-9_]* -> Option C

4. Quick Check:

   Identifier pattern starts with letter/underscore [OK]

Hint: Identifiers start with letter/underscore, not digit [OK]

Common Mistakes:

• Allowing digits as first character in identifiers
• Confusing integer patterns with identifiers
• Using patterns that match both integers and identifiers