CD Notes

Lexemes in Compiler Design

Understanding lexemes, their role in lexical analysis, how they are identified from source code, and their relationship with tokens and patterns.

What is a Lexeme?

A lexeme is the actual sequence of characters in the source program that is matched by the pattern of a token. It is the raw substring of the source code that the lexical analyzer identifies as belonging to a particular token category. While a token is an abstract classification, a lexeme is the concrete text from the source program.

Think of it this way:

Token: The category (like "IDENTIFIER" or "NUMBER")
Lexeme: The actual text (like "count" or "42")
Pattern: The rule that describes valid lexemes for that token

Lexemes vs Tokens vs Patterns

Lexeme	Token	Pattern
total	IDENTIFIER	letter(letter\|digit)*
=	ASSIGN	=
price	IDENTIFIER	letter(letter\|digit)*
*	MULTIPLY	*
quantity	IDENTIFIER	letter(letter\|digit)*
+	PLUS	+
tax	IDENTIFIER	letter(letter\|digit)*
;	SEMICOLON	;

Identifying Lexemes

The process of identifying lexemes involves:

1. Character-by-Character Scanning

The lexical analyzer reads the source program one character at a time, building up potential lexemes.

2. Pattern Matching

Each accumulated sequence is tested against known patterns to determine when a complete lexeme has been formed.

3. Delimiter Recognition

Lexemes are typically bounded by whitespace, operators, or special characters that serve as delimiters.

Input	"x = 123 + y"
- Read 'x'	could be start of identifier
- Read ' '	delimiter found, "x" is complete lexeme
- Read '='	single-char operator, "=" is complete lexeme
- Read '1'	could be start of number
- Read '2'	still building number
- Read '3'	still building number
- Read ' '	delimiter found, "123" is complete lexeme
- Read '+'	single-char operator, "+" is complete lexeme
- Read 'y'	could be start of identifier
- Read EOF	"y" is complete lexeme

Types of Lexemes

Fixed Lexemes

These are lexemes with a predetermined, fixed character sequence:

Keywords	if, else, while, for, return, int, float
Operators	+, -, *, /, =, ==, !=, <=, >=
Delimiters	(, ), {, }, [, ], ;, ,

Variable Lexemes

These are lexemes whose exact content varies:

Identifiers	count, totalPrice, _temp, MAX_SIZE
Numbers	42, 3.14, 0xFF, 1.5e-3
Strings	"hello world", "compiler design"
Characters	'a', '\n', '\0'

Lexeme Boundaries

Determining where one lexeme ends and another begins is critical:

Explicit Delimiters

c example

int x = 5; // spaces and ; clearly separate lexemes

Implicit Boundaries

c example

x+y           // No space needed; + acts as delimiter
a>=b          // >= is one lexeme, not > and =

Ambiguous Cases (Resolved by Rules)

Example

x++y // Is it x, ++, y OR x, +, +, y? // Answer: x, ++, y (longest match rule) a-->b // Is it a, --, >, b OR a, -, -, >, b? // Answer: a, --, >, b (longest match)

Lexeme Storage

Symbol Table Entry

When an identifier lexeme is recognized, it's entered in the symbol table:

Lexeme "count"	Symbol Table Entry {
name	"count",
type	(to be filled by semantic analysis),
scope	(to be filled),
address	(to be filled by code generation)

String Table

String literals are often stored in a separate string table:

Lexeme "hello world"	String Table Entry {
value	"hello world",
length	11,
offset	0x100

Lexeme Recognition in Different Languages

C Language

c example

// Lexemes: float, pi, =, 3.14159, ;
float pi = 3.14159;

// Lexemes: char, *, str, =, "hello\n", ;
char *str = "hello\n";

Python

python example

# Lexemes: def, calculate, (, x, ,, y, ), :
def calculate(x, y):
    # Lexemes: return, x, **, 2, +, y, **, 2
    return x**2 + y**2

Java

java example

// Lexemes: System, ., out, ., println, (, "Hello", ), ;
System.out.println("Hello");

Common Challenges in Lexeme Identification

1. Overlapping Patterns

The lexeme "int" could be a keyword OR the start of an identifier "integer". Solution: Longest match rule — read as far as possible.

2. Context Sensitivity

In Fortran: DO 5 I = 1.25 vs DO 5 I = 1,25

First is assignment to DO5I
Second is a DO loop

Solution: Look ahead far enough to disambiguate.

3. Escape Sequences in Strings

Example

Lexeme: "line1\nline2" Must recognize \n as a single escape character within the string.

4. Nested Comments

Example

/* outer /* inner */ still comment? */ Some languages allow nested comments, requiring the scanner to track nesting depth.

Implementation Example

Example

class Lexer: def __init__(self, source): self.source = source self.pos = 0 self.current_char = source[0] if source else None def get_lexeme(self): """Extract the next lexeme from source""" self.skip_whitespace() if self.current_char is None: return None, 'EOF' # Identifier or keyword lexeme if self.current_char.isalpha() or self.current_char == '_': start = self.pos while self.current_char and (self.current_char.isalnum() or self.current_char == '_'): self.advance() lexeme = self.source[start:self.pos] token_type = 'KEYWORD' if lexeme in KEYWORDS else 'IDENTIFIER' return lexeme, token_type # Number lexeme if self.current_char.isdigit(): start = self.pos while self.current_char and self.current_char.isdigit(): self.advance() lexeme = self.source[start:self.pos] return lexeme, 'NUMBER'

Interview Questions

What is a lexeme and how does it differ from a token?

A lexeme is the actual character sequence in the source code (e.g., "count", "42", "if"). A token is the abstract category assigned to that lexeme (e.g., IDENTIFIER, NUMBER, KEYWORD). Multiple different lexemes can map to the same token type.

How does the lexical analyzer determine lexeme boundaries?

Through delimiters (whitespace, operators, punctuation), the longest match rule (always form the longest valid lexeme), and pattern matching (testing accumulated characters against token patterns).

Give examples of fixed and variable lexemes.

Fixed lexemes have predetermined text: keywords (if, while), operators (+, ==), delimiters (;, {). Variable lexemes have content that varies: identifiers (myVar, count), numbers (42, 3.14), strings ("hello").

What happens when a lexeme matches multiple patterns?

Two rules apply: (1) Longest match — choose the longest matching lexeme, (2) Priority — if two patterns match the same length, keywords take priority over identifiers.

Where are lexemes stored after recognition?

Identifier lexemes are stored in the symbol table with associated information (type, scope, address). String literal lexemes go to a string table. Numeric lexemes have their values computed and attached as token attributes.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Lexemes in Compiler Design.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, lexical, analysis, lexemes, lexemes in compiler design

Continue learning this concept

Lexical AnalysisFinite Automata in Lexical AnalysisHow finite automata (DFA and NFA) are used in lexical analysis to implement pattern matching for token recognition in compilers.Lexical AnalysisIntroduction to Lexical AnalysisComprehensive introduction to lexical analysis, the first phase of a compiler that reads source code and produces tokens for the parser.Lexical AnalysisLex Tool - Lexical Analyzer GeneratorComplete guide to the Lex tool for automatic generation of lexical analyzers from regular expression specifications, including syntax, rules, and examples.Lexical AnalysisLexical Analyzer DesignComplete guide to designing and implementing a lexical analyzer including architecture, algorithms, buffering strategies, and practical implementation.Lexical AnalysisLexical Errors and Error RecoveryUnderstanding lexical errors in compiler design, types of errors detected during scanning, and error recovery strategies used by lexical analyzers.Lexical AnalysisPatterns in Lexical AnalysisUnderstanding patterns that define valid lexemes for each token type, pattern specification using regular expressions, and pattern matching in scanners.

PreviousLex Tool - Lexical Analyzer Generator NextLexical Analyzer Design

CD Notes

Lexemes in Compiler Design

Understanding lexemes, their role in lexical analysis, how they are identified from source code, and their relationship with tokens and patterns.

What is a Lexeme?

Think of it this way:

Token: The category (like "IDENTIFIER" or "NUMBER")
Lexeme: The actual text (like "count" or "42")
Pattern: The rule that describes valid lexemes for that token

Lexemes vs Tokens vs Patterns

Lexeme	Token	Pattern
total	IDENTIFIER	letter(letter\|digit)*
=	ASSIGN	=
price	IDENTIFIER	letter(letter\|digit)*
*	MULTIPLY	*
quantity	IDENTIFIER	letter(letter\|digit)*
+	PLUS	+
tax	IDENTIFIER	letter(letter\|digit)*
;	SEMICOLON	;

Identifying Lexemes

The process of identifying lexemes involves:

1. Character-by-Character Scanning

The lexical analyzer reads the source program one character at a time, building up potential lexemes.

2. Pattern Matching

Each accumulated sequence is tested against known patterns to determine when a complete lexeme has been formed.

3. Delimiter Recognition

Lexemes are typically bounded by whitespace, operators, or special characters that serve as delimiters.

Input	"x = 123 + y"
- Read 'x'	could be start of identifier
- Read ' '	delimiter found, "x" is complete lexeme
- Read '='	single-char operator, "=" is complete lexeme
- Read '1'	could be start of number
- Read '2'	still building number
- Read '3'	still building number
- Read ' '	delimiter found, "123" is complete lexeme
- Read '+'	single-char operator, "+" is complete lexeme
- Read 'y'	could be start of identifier
- Read EOF	"y" is complete lexeme

Types of Lexemes

Fixed Lexemes

These are lexemes with a predetermined, fixed character sequence:

Keywords	if, else, while, for, return, int, float
Operators	+, -, *, /, =, ==, !=, <=, >=
Delimiters	(, ), {, }, [, ], ;, ,

Variable Lexemes

These are lexemes whose exact content varies:

Identifiers	count, totalPrice, _temp, MAX_SIZE
Numbers	42, 3.14, 0xFF, 1.5e-3
Strings	"hello world", "compiler design"
Characters	'a', '\n', '\0'

Lexeme Boundaries

Determining where one lexeme ends and another begins is critical:

Explicit Delimiters

c example

int x = 5; // spaces and ; clearly separate lexemes

Implicit Boundaries

c example

x+y           // No space needed; + acts as delimiter
a>=b          // >= is one lexeme, not > and =

Ambiguous Cases (Resolved by Rules)

Example

x++y // Is it x, ++, y OR x, +, +, y? // Answer: x, ++, y (longest match rule) a-->b // Is it a, --, >, b OR a, -, -, >, b? // Answer: a, --, >, b (longest match)

Lexeme Storage

Symbol Table Entry

When an identifier lexeme is recognized, it's entered in the symbol table:

Lexeme "count"	Symbol Table Entry {
name	"count",
type	(to be filled by semantic analysis),
scope	(to be filled),
address	(to be filled by code generation)

String Table

String literals are often stored in a separate string table:

Lexeme "hello world"	String Table Entry {
value	"hello world",
length	11,
offset	0x100

Lexeme Recognition in Different Languages

C Language

c example

// Lexemes: float, pi, =, 3.14159, ;
float pi = 3.14159;

// Lexemes: char, *, str, =, "hello\n", ;
char *str = "hello\n";

Python

python example

# Lexemes: def, calculate, (, x, ,, y, ), :
def calculate(x, y):
    # Lexemes: return, x, **, 2, +, y, **, 2
    return x**2 + y**2

Java

java example

// Lexemes: System, ., out, ., println, (, "Hello", ), ;
System.out.println("Hello");

Common Challenges in Lexeme Identification

1. Overlapping Patterns

The lexeme "int" could be a keyword OR the start of an identifier "integer". Solution: Longest match rule — read as far as possible.

2. Context Sensitivity

In Fortran: DO 5 I = 1.25 vs DO 5 I = 1,25

First is assignment to DO5I
Second is a DO loop

Solution: Look ahead far enough to disambiguate.

3. Escape Sequences in Strings

Example

Lexeme: "line1\nline2" Must recognize \n as a single escape character within the string.

4. Nested Comments

Example

/* outer /* inner */ still comment? */ Some languages allow nested comments, requiring the scanner to track nesting depth.

Implementation Example

Example

Interview Questions

What is a lexeme and how does it differ from a token?

How does the lexical analyzer determine lexeme boundaries?

Through delimiters (whitespace, operators, punctuation), the longest match rule (always form the longest valid lexeme), and pattern matching (testing accumulated characters against token patterns).

Give examples of fixed and variable lexemes.

What happens when a lexeme matches multiple patterns?

Two rules apply: (1) Longest match — choose the longest matching lexeme, (2) Priority — if two patterns match the same length, keywords take priority over identifiers.

Where are lexemes stored after recognition?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Lexemes in Compiler Design.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, lexical, analysis, lexemes, lexemes in compiler design

Continue learning this concept

PreviousLex Tool - Lexical Analyzer Generator NextLexical Analyzer Design