CD Notes
HubApplications of Compiler DesignCompiler vs Interpreter — Compiler DesignLanguage ProcessorsPhases of a CompilerWhat is Compiler Design?The AssemblerCompiler OverviewComplete Compilation ProcessThe LinkerThe LoaderThe PreprocessorFinite Automata in Lexical AnalysisIntroduction to Lexical AnalysisLex Tool - Lexical Analyzer GeneratorLexemes in Compiler DesignLexical Analyzer DesignLexical Errors and Error RecoveryPatterns in Lexical AnalysisRegular Expressions in Compiler DesignTokens in Compiler DesignAmbiguity in Grammars for Compiler DesignBottom-Up Parsing in Compiler DesignCLR Parser: Canonical LR(1) Parsing with Complete Lookahead InformationContext-Free Grammars for Syntax AnalysisDerivations in Syntax AnalysisIntroduction to Parsing in Compiler DesignLALR Parser: Practical LR(1) With State Merging for EfficiencyLL(1) Parser: Single Lookahead Predictive Parsing from First PrinciplesLR Parsers: Canonical LR Parsing for Complex Language SyntaxParse Trees in Compiler DesignPredictive Parsers: Lookahead-Guided Top-Down ParsingRecursive Descent Parsers: Procedural Approach to Top-Down ParsingShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax AnalysisSLR Parser: Simple LR Parsing with Efficient AutomataTop-Down Parsing Techniques in Compiler DesignScope Management: Symbol Table Design for Language ImplementationSemantic Analysis IntroductionSemantic Errors: Detection and Reporting in Compiler ConstructionSemantic Rules: Defining Language Semantics in Compiler ConstructionSymbol Table: Core Data Structure for Semantic Analysis and Code GenerationType Checking: Static Analysis for Type Safety in Compiler DesignType Conversion and Coercion in Compiler Semantic AnalysisAttribute Grammars: Foundation of Semantic Analysis and Code GenerationDependency Graphs: Visualizing Attribute Computation Order in Semantic AnalysisInherited Attributes: Top-Down Attribute Computation for Context TransferSyntax-Directed Definitions: Attribute Grammars for Semantic AnalysisSyntax-Directed Translation Schemes: Execution Semantics and Code GenerationSynthesized Attributes: Bottom-Up Attribute Computation in Compiler DesignDirected Acyclic Graphs (DAGs) in Compiler DesignIndirect Triples in Compiler DesignIntroduction to Intermediate Code GenerationQuadruples Representation in Compiler DesignSyntax Trees as Intermediate RepresentationThree-Address Code in Compiler DesignTriples Representation in Compiler DesignActivation Records: Function Call ManagementHeap Allocation: Dynamic Memory ManagementMemory Management: Strategies and OptimizationParameter Passing: Communication Between FunctionsRuntime Environment: Program Execution ContextStack Allocation: Automatic Memory ManagementStorage Organization: Memory Sections and LayoutIntroduction to Code Generation in Compiler DesignCode Generator Design in Compiler ConstructionInstruction Selection in Code GenerationMachine Code Generation in CompilersRegister Allocation in Compiler DesignRegister Assignment Strategies in Code GenerationTarget Machine Architecture for Code GenerationIntroduction to Code Optimization in Compiler DesignCommon Subexpression Elimination (CSE) in Compiler OptimizationConstant Folding Optimization in Compiler DesignConstant Propagation in Compiler OptimizationDead Code Elimination in Compiler OptimizationGlobal Optimization Techniques in Compiler DesignLocal Optimization Techniques in Compiler DesignLoop Optimization Techniques in Compiler DesignPeephole Optimization in Compiler DesignBison: LALR Parser GeneratorFlex: Lexical Analyzer GeneratorLex: Original Lexical AnalyzerParser Generator WorkflowPractical Parser ProjectsYACC: Original Parser GeneratorBytecode and Virtual MachinesGCC ArchitectureJava Compiler and BytecodeJust-In-Time CompilationLLVM: The Low-Level Virtual MachinePython Interpreter ArchitectureWebAssembly BasicsCalculator Compiler ProjectExpression Parser ProjectLexical Analyzer ProjectMini Programming Language ProjectSyntax Checker ProjectToy Compiler Project: Minimal Complete CompilerCompiler Design CheatsheetCompiler Design Interview QuestionsGATE Compiler Design QuestionsLexical Analysis Interview QuestionsParsing Interview QuestionsGlossary of Compiler Design TermsImportant Formulas and RulesQuick Revision Notes for ExamsRecommended Books and Resources — Compiler DesignContext-Free Languages in Compiler DesignDeterministic Finite Automata (DFA) in Compiler DesignFinite Automata Review for Compiler DesignNondeterministic Finite Automata (NFA) in Compiler DesignPushdown Automata (PDA) in Compiler DesignRegular Languages in Compiler DesignTuring Machines and Their Role in Compiler Theory
Complete guide to designing and implementing a lexical analyzer including architecture, algorithms, buffering strategies, and practical implementation.
Introduction
Designing a lexical analyzer involves translating formal token specifications (regular expressions) into an efficient program that can quickly scan source code and produce a stream of tokens. This involves decisions about architecture, data structures, input handling, and error recovery.
Architecture of a Lexical Analyzer
┌────────────────────────────────────────────────┐
│ Lexical Analyzer │
│ │
│ ┌──────────┐ ┌──────────┐ ┌──────────────┐ │
│ │ Input │ │ Scanner │ │ Token │ │
│ │ Buffer │→ │ Engine │→ │ Generator │ │
│ └──────────┘ └──────────┘ └──────────────┘ │
│ ↑ ↑ │ │
│ Source File Transition Token │
│ Table Stream │
└────────────────────────────────────────────────┘
│ │
▼ ▼
┌──────────┐ ┌──────────────┐
│ Symbol │ │ Parser │
│ Table │ │ │
└──────────┘ └──────────────┘
Design Approaches
1. Hand-Coded Scanner
A manually written scanner using direct coded automata:
Example
Token getNextToken() {
char c = getChar();
// Skip whitespace
while (c == ' ' || c == '\t' || c == '\n') {
if (c == '\n') lineNumber++;
c = getChar();
}
// Identifiers and keywords
if (isalpha(c) || c == '_') {
char buffer[MAX_ID_LEN];
int i = 0;
while (isalnum(c) || c == '_') {
buffer[i++] = c;
c = getChar();
}
buffer[i] = '\0';
ungetChar(c); // Put back lookahead
// Check if keyword
TokenType kw = lookupKeyword(buffer);
if (kw != NONE) return makeToken(kw);
return makeToken(IDENTIFIER, buffer);
}
// Numbers
if (isdigit(c)) {
int value = 0;
while (isdigit(c)) {
value = value * 10 + (c - '0');
c = getChar();
}
if (c == '.') {
// Handle floating point
// ...
}
ungetChar(c);
return makeToken(INTEGER, value);
}
// Operators and delimiters
switch (c) {
case '+': return makeToken(PLUS);
case '-': return makeToken(MINUS);
case '*': return makeToken(STAR);
case '=':
c = getChar();
if (c == '=') return makeToken(EQUAL);
ungetChar(c);
return makeToken(ASSIGN);
case '<':
c = getChar();
if (c == '=') return makeToken(LTEQ);
ungetChar(c);
return makeToken(LT);
// ... more cases
}
}
2. Table-Driven Scanner
Uses a precomputed transition table:
Example
// Transition table indexed by [state][character_class]
int delta[NUM_STATES][NUM_CHAR_CLASSES];
int accepting[NUM_STATES]; // Token type for accepting states
TokenType token_type[NUM_STATES];
Token scan() {
int state = START_STATE;
int lastAccept = -1;
int lastAcceptPos = -1;
char *start = forward;
while (state != ERROR_STATE) {
char c = *forward++;
int charClass = classify(c);
state = delta[state][charClass];
if (accepting[state]) {
lastAccept = state;
lastAcceptPos = forward - input;
}
}
if (lastAccept >= 0) {
forward = input + lastAcceptPos;
return makeToken(token_type[lastAccept], start, forward);
}
// Error: no token matched
reportError(start);
}
3. Generator-Based (Lex/Flex)
Using a tool like Lex or Flex:
Example
%{
#include "tokens.h"
%}
%%
[ \t\n]+ { /* skip whitespace */ }
"//"[^\n]* { /* skip comments */ }
"if" { return IF; }
"else" { return ELSE; }
"while" { return WHILE; }
"int" { return INT; }
"float" { return FLOAT; }
[A-Za-z_][A-Za-z0-9_]* { yylval.str = strdup(yytext); return ID; }
[0-9]+ { yylval.ival = atoi(yytext); return NUMBER; }
[0-9]+\.[0-9]+ { yylval.fval = atof(yytext); return FNUMBER; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return DIVIDE; }
"=" { return ASSIGN; }
"==" { return EQ; }
"!=" { return NEQ; }
";" { return SEMI; }
. { printf("Unknown char: %c\n", *yytext); }
%%
Input Buffering Strategies
Double Buffer Scheme
| Buffer 1 (4096) | Buffer 2 (4096) |
|---|---|
| i f ( x > 0 ) ... EOF | { y = x * 2 ; ... EOF |
Algorithm:
Example
char nextChar() {
if (forward is at EOF sentinel) {
if (forward is at end of first buffer) {
reload second buffer;
forward = beginning of second buffer;
} else {
// true end of input
return EOF;
}
}
return *forward++;
}
Symbol Table Interaction
The lexical analyzer creates symbol table entries for identifiers:
Example
typedef struct SymbolEntry {
char *name;
TokenType token;
int lineNumber;
// Type info filled by semantic analysis
// Address filled by code generation
} SymbolEntry;
Token scanIdentifier() {
char lexeme[MAX_ID];
// ... read the identifier lexeme ...
SymbolEntry *entry = lookup(symbolTable, lexeme);
if (entry == NULL) {
entry = insert(symbolTable, lexeme);
entry->lineNumber = currentLine;
}
return makeToken(IDENTIFIER, entry);
}
Handling Special Cases
Multi-line Strings
python example
# Python triple-quoted strings
text = """
This is a
multi-line string
"""
# Scanner must track state across linesNested Comments
Example
/* level 1 /* level 2 */ still level 1 */
# Requires counter or stack (beyond regular language)
Context-Sensitive Tokens
c example
// In C: is >> a right-shift or two template closing brackets?
vector<vector<int>> v; // Two > characters
x = a >> 2; // Right-shift operatorPerformance Considerations
| Technique | Benefit |
|---|---|
| Table-driven automaton | Predictable O(1) per character |
| Direct-coded scanner | Faster due to fewer table lookups |
| Buffer sentinels | Eliminate boundary checks |
| Perfect hash for keywords | O(1) keyword lookup |
| Character classification table | Faster than multiple comparisons |
Interview Questions
- What are the three main approaches to building a lexical analyzer?
Hand-coded (directly implementing the automaton in code), table-driven (using precomputed transition tables), and generator-based (using tools like Lex/Flex). Hand-coded offers best performance, table-driven offers clean separation, generators offer easiest development.
- Why is double buffering used in lexical analyzers?
To avoid frequent disk I/O (reading one character at a time is too slow) while handling the case where a lexeme spans the buffer boundary. Two buffers alternate: while one is being processed, the other can be refilled.
- How does a lexical analyzer handle the longest match rule?
It continues scanning even after finding a match, recording the last accepting state and position. When no more transitions are possible, it backtracks to the last accepting position and returns that token.
- What are the advantages of using a scanner generator over hand-coding?
Easier development, proven correctness (based on automata theory), easier maintenance (modify regex patterns), and automatic optimization. However, hand-coded scanners are often faster and more flexible for complex cases.
- How does the lexical analyzer interact with the symbol table?
When an identifier is recognized, the scanner looks it up in the symbol table. If not found, it creates a new entry. The token returned contains a pointer to the symbol table entry, which later phases use for type information, scope, and code generation.
Continue the lesson path
Study next in this module
01Lexical AnalysisLexemes in Compiler DesignUnderstanding lexemes, their role in lexical analysis, how they are identified from source code, and their relationship with tokens and patterns.02Lexical AnalysisLexical Errors and Error RecoveryUnderstanding lexical errors in compiler design, types of errors detected during scanning, and error recovery strategies used by lexical analyzers.03Lexical 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.04Lexical AnalysisPatterns in Lexical AnalysisUnderstanding patterns that define valid lexemes for each token type, pattern specification using regular expressions, and pattern matching in scanners.