Tokens, patterns, and lexemes in Compiler Design - Step-by-Step Execution

Concept Flow - Tokens, patterns, and lexemes

Source Code Text

↓

Lexical Analyzer

↓

Pattern Matching

↓

Identify Lexemes

↓

Generate Tokens

↓

Pass Tokens to Parser

The source code is read by the lexical analyzer, which uses patterns to find lexemes and then generates tokens to pass to the parser.

Execution Sample

Compiler Design

int x = 10;
// Sample code line

This code line is scanned to identify lexemes and generate tokens like 'int', 'x', '=', '10', and ';'.

Analysis Table

Step	Input Text Segment	Pattern Matched	Lexeme Identified	Token Generated
1	"int"	Keyword pattern	"int"	KEYWORD_INT
2	" " (space)	Whitespace	Ignored	null
3	"x"	Identifier pattern	"x"	IDENTIFIER
4	" " (space)	Whitespace	Ignored	null
5	"="	Operator pattern	"="	ASSIGN_OP
6	" " (space)	Whitespace	Ignored	null
7	"10"	Number pattern	"10"	NUMBER
8	";"	Delimiter pattern	";"	SEMICOLON
9	\n	Newline	Ignored	null

💡 All input text processed; tokens generated for all lexemes except whitespace and newline which are ignored.

State Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	Final
Current Position	0	3	5	7	10	11
Current Lexeme	""	"int"	"x"	"="	"10"	";"
Tokens List	[]	[KEYWORD_INT]	[KEYWORD_INT, IDENTIFIER]	[KEYWORD_INT, IDENTIFIER, ASSIGN_OP]	[KEYWORD_INT, IDENTIFIER, ASSIGN_OP, NUMBER]	[KEYWORD_INT, IDENTIFIER, ASSIGN_OP, NUMBER, SEMICOLON]

Key Insights - 3 Insights

Why are spaces and newlines not turned into tokens?

Spaces and newlines are recognized as whitespace patterns and ignored during token generation, as shown in steps 2, 4, 6, and 9 in the execution_table.

How does the lexical analyzer know where one lexeme ends and another begins?

It uses pattern matching and checks for delimiters like spaces, operators, or punctuation to separate lexemes, as seen between steps 1 and 3 where space separates 'int' and 'x'.

What is the difference between a lexeme and a token?

A lexeme is the actual substring from the source code (like 'int' or '10'), while a token is the category or type assigned to that lexeme (like KEYWORD_INT or NUMBER), as shown in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what token is generated at step 5?

A IDENTIFIER

B ASSIGN_OP

C NUMBER

D SEMICOLON

💡 Hint

Check the 'Token Generated' column at step 5 in the execution_table.

At which step does the lexical analyzer identify the lexeme "x"?

A Step 5

B Step 1

C Step 3

D Step 7

💡 Hint

Look at the 'Lexeme Identified' column in the execution_table for "x".

If the input had no spaces, how would the lexical analyzer separate tokens?

A It uses patterns like operators and delimiters to separate lexemes

B It treats the entire line as one token

C It would fail to separate tokens

D It ignores all characters

💡 Hint

Refer to the key_moments explanation about how lexemes are separated.

Concept Snapshot

Tokens, patterns, and lexemes:
- Lexical analyzer reads source code text.
- Patterns define how lexemes (actual text pieces) are recognized.
- Tokens are categories assigned to lexemes (e.g., KEYWORD, IDENTIFIER).
- Whitespace and comments are usually ignored.
- Tokens are passed to the parser for syntax analysis.

Full Transcript

In compiler design, the lexical analyzer reads the source code text and uses patterns to find lexemes, which are actual substrings like 'int' or 'x'. Each lexeme is then assigned a token, which is a category like KEYWORD_INT or IDENTIFIER. Spaces and newlines are recognized as whitespace and ignored. The process continues until all input text is processed, generating a list of tokens for the parser to use. This step-by-step execution shows how the analyzer moves through the input, identifies lexemes, and generates tokens accordingly.

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