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.