Implementing a lexical analyzer in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the role of a lexical analyzer

What is the primary function of a lexical analyzer in a compiler?

A It generates machine code from intermediate representation.

B It optimizes the syntax tree for faster execution.

C It converts source code into a sequence of tokens by grouping characters.

D It manages memory allocation during program execution.

💡 Hint

Think about the first step after reading raw source code characters.

The lexical analyzer reads raw characters and groups them into meaningful units called tokens, which are then passed to the parser.

📋 Factual

intermediate

Token recognition in lexical analysis

Which of the following best describes how a lexical analyzer recognizes tokens?

A By using regular expressions to match patterns in the input stream.

B By constructing abstract syntax trees directly from characters.

C By executing semantic actions during parsing.

D By generating machine instructions for each character.

💡 Hint

Consider how patterns like identifiers or numbers are detected.

Lexical analyzers use regular expressions or finite automata to match patterns and identify tokens in the input stream.

🔍 Analysis

advanced

Handling ambiguous token patterns

Given the token patterns for identifiers (letters followed by letters or digits) and keywords (specific reserved words), how should a lexical analyzer handle the input ifelse?

A Recognize <code>ifelse</code> as a single identifier token.

B Split into two tokens: keyword <code>if</code> and identifier <code>else</code>.

C Split into two tokens: keyword <code>if</code> and keyword <code>else</code>.

D Raise an error because <code>ifelse</code> is not a valid token.

💡 Hint

Think about longest match rule and reserved words.

The lexical analyzer applies the longest match rule, so it recognizes ifelse as one identifier token since it does not match the keyword if or else separately.

❓ Comparison

advanced

Differences between lexical analyzer and parser

Which statement correctly distinguishes the lexical analyzer from the parser in a compiler?

A The lexical analyzer executes semantic actions; the parser performs lexical analysis.

B The lexical analyzer generates machine code; the parser optimizes it.

C The lexical analyzer manages memory; the parser handles input/output operations.

D The lexical analyzer groups characters into tokens; the parser analyzes token sequences to build syntax trees.

💡 Hint

Consider the roles of tokenization and syntax analysis.

The lexical analyzer converts raw characters into tokens, while the parser takes these tokens and builds a structured representation like a syntax tree.

❓ Reasoning

expert

Error detection in lexical analysis

Consider a lexical analyzer that encounters the input string @variable, where @ is not part of any token pattern. What is the best way for the lexical analyzer to handle this situation?

A Replace <code>@</code> with a space and continue scanning.

B Report a lexical error immediately and stop processing further input.

C Treat <code>@</code> as a valid token and include it in the token stream.

D Ignore the <code>@</code> character and continue scanning the rest as tokens.

💡 Hint

Think about the importance of detecting invalid characters early.

Lexical analyzers must detect invalid characters and report errors to prevent incorrect parsing later. Ignoring or altering input can cause confusion and incorrect compilation.

Practice

1. What is the main job of a lexical analyzer in compiler design?

easy

A. Break input text into meaningful tokens

B. Execute the program code

C. Optimize the compiled code

D. Generate machine code

Solution

1. Step 1: Understand the role of lexical analyzer

   A lexical analyzer reads the input text and divides it into tokens like keywords, identifiers, and symbols.

2. Step 2: Differentiate from other compiler phases

   It does not execute code, optimize, or generate machine code; those are later phases.

3. Final Answer:

   Break input text into meaningful tokens -> Option A

4. Quick Check:

   Lexical analyzer = tokenization [OK]

Hint: Lexical analyzer splits text into tokens [OK]

Common Mistakes:

• Confusing lexical analysis with code execution
• Thinking it optimizes or generates machine code
• Assuming it handles syntax errors

2. Which of the following is a correct way to define a token pattern in a lexical analyzer?

easy

A. token = (123)+

B. token = [a-zA-Z_][a-zA-Z0-9_]*

C. token = {print}

D. token = 123abc

Solution

1. Step 1: Recognize token pattern syntax

   Token patterns use regular expressions; [a-zA-Z_][a-zA-Z0-9_]* matches identifiers starting with letter or underscore.

2. Step 2: Check other options for correctness

   token = (123)+ uses invalid syntax for token pattern; C uses braces incorrectly; D is not a valid pattern.

3. Final Answer:

   token = [a-zA-Z_][a-zA-Z0-9_]* -> Option B

4. Quick Check:

   Valid regex pattern = token = [a-zA-Z_][a-zA-Z0-9_]* [OK]

Hint: Token patterns use regex-like syntax starting with letters or underscore [OK]

Common Mistakes:

• Using invalid characters in token patterns
• Confusing literal strings with patterns
• Ignoring start character rules

3. Given the input string int x = 10;, what tokens will a lexical analyzer produce?

medium

A. ["int", "x=10;"]

B. ["int x", "= 10;"]

C. ["int", "x", "=", "10", ";"]

D. ["int", "x", "=", "1", "0", ";"]

Solution

1. Step 1: Identify tokens in the input

   The lexical analyzer splits by language rules: keyword 'int', identifier 'x', operator '=', number '10', and symbol ';'.

2. Step 2: Compare with options

   ["int", "x", "=", "10", ";"] correctly lists all tokens separately. Others combine tokens incorrectly or split numbers wrongly.

3. Final Answer:

   ["int", "x", "=", "10", ";"] -> Option C

4. Quick Check:

   Tokens = separate meaningful units [OK]

Hint: Tokens separate keywords, identifiers, operators, numbers, symbols [OK]

Common Mistakes:

• Combining multiple tokens into one
• Splitting numbers into digits
• Ignoring punctuation as tokens

4. Identify the error in this lexical analyzer rule: NUMBER = [0-9]+(.[0-9]+)?

medium

A. Plus (+) should be replaced with star (*)

B. Parentheses should be removed

C. Square brackets are not allowed

D. Dot (.) should be escaped as \.

Solution

1. Step 1: Analyze the regex pattern

   The dot (.) in regex means any character; to match a literal dot, it must be escaped as \.

2. Step 2: Check other parts of the pattern

   Plus (+) is correct for one or more digits; square brackets and parentheses are valid here.

3. Final Answer:

   Dot (.) should be escaped as \. -> Option D

4. Quick Check:

   Escape dot for literal period [OK]

Hint: Escape dot in regex to match literal '.' [OK]

Common Mistakes:

• Not escaping dot causing wrong matches
• Changing quantifiers unnecessarily
• Removing valid grouping parentheses

5. How can a lexical analyzer handle comments in source code effectively?

hard

A. By recognizing comment patterns and skipping them

B. By converting comments into tokens

C. By treating comments as syntax errors

D. By storing comments as identifiers

Solution

1. Step 1: Understand comment handling

   Comments are ignored by the compiler; the lexical analyzer must detect comment start and end patterns and skip their content.

2. Step 2: Evaluate other options

   Converting comments into tokens or treating them as errors is incorrect; storing as identifiers is wrong.

3. Final Answer:

   By recognizing comment patterns and skipping them -> Option A

4. Quick Check:

   Skip comments during tokenization [OK]

Hint: Detect and skip comments, don't tokenize them [OK]

Common Mistakes:

• Tokenizing comments as code
• Raising errors on comments
• Confusing comments with identifiers