Implementing a lexical analyzer in Compiler Design - Step-by-Step Execution

Concept Flow - Implementing a lexical analyzer

Start Input Source Code

↓

Read Next Character

↓

Is Character Whitespace?

Yes→Ignore and Read Next

No↓

Is Character Part of Token?

No→Error or Skip

Yes↓

Build Token String

↓

Is Token Complete?

No→Read Next Character

Yes↓

Classify Token Type

↓

Output Token

↓

More Characters?

Yes→Read Next Character

No↓

End

The lexical analyzer reads characters one by one, groups them into tokens, classifies each token, and outputs tokens until the input ends.

Execution Sample

Compiler Design

input = "int x = 10;"
pos = 0
while pos < len(input):
  ch = input[pos]
  if ch.isalpha():
    token = ch
    pos += 1

This code reads characters from input, detects if a character is a letter, and starts building a token.

Analysis Table

Step	pos	ch	Condition	Action	Token Built	Output Token
1	0	i	ch.isalpha()=true	Start token with 'i'	i
2	1	n	ch.isalpha()=true	Add 'n' to token	in
3	2	t	ch.isalpha()=true	Add 't' to token	int
4	3		ch.isalpha()=false	Token complete	int	int (keyword)
5	4	x	ch.isalpha()=true	Start token with 'x'	x
6	5		ch.isalpha()=false	Token complete	x	x (identifier)
7	6	=	ch.isalpha()=false	Single char token	=	=
8	7		Whitespace	Ignore
9	8	1	ch.isdigit()=true	Start token with '1'	1
10	9	0	ch.isdigit()=true	Add '0' to token	10
11	10	;	ch.isdigit()=false	Token complete	10	10 (number)
12	11	;	ch.isalpha()=false	Single char token	;	;
13	12		pos >= len(input)	End of input

💡 pos reaches input length 12, no more characters to read

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	Final
pos	0	1	2	3	4	5	6	7	8	9	10	11	12
ch		i	n	t		x		=		1	0	;
token		i	in	int	int	x	x	=		1	10	10

Key Insights - 3 Insights

Why does the token 'int' complete when a space character is read?

Because the space is not part of an identifier, the lexical analyzer recognizes the token is complete at step 4 in the execution_table.

How does the analyzer handle single character tokens like '=' and ';'?

At steps 7 and 12, the analyzer treats these characters as complete tokens immediately since they are operators or punctuation.

Why is whitespace ignored and not output as a token?

Whitespace is used only to separate tokens and is skipped as shown at steps 4, 6, 8, and 13 in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the token built so far?

A i

B in

C int

D n

💡 Hint

Check the 'Token Built' column at step 3 in the execution_table.

At which step does the lexical analyzer output the token 'x'?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look for 'Output Token' column showing 'x (identifier)' in the execution_table.

If the input had no spaces, how would the token completion change?

A Tokens complete only on non-alphanumeric characters

B Tokens would never complete

C Tokens complete on whitespace only

D Tokens complete after fixed length

💡 Hint

Refer to the 'Condition' and 'Action' columns in the execution_table to see when tokens complete.

Concept Snapshot

Lexical Analyzer Basics:
- Reads input character by character
- Skips whitespace
- Groups characters into tokens
- Recognizes token types (keywords, identifiers, numbers, symbols)
- Outputs tokens sequentially
- Stops at end of input

Full Transcript

A lexical analyzer reads source code one character at a time. It skips spaces and groups letters or digits into tokens like keywords, identifiers, or numbers. When it encounters a character that can't be part of the current token, it finishes that token and outputs it. Single characters like '=' or ';' are tokens by themselves. This process repeats until all input is read. The execution table shows each step with the current character, token being built, and when tokens are output. Variables like position and token string change as the analyzer moves through the input.

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