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 the Lex tool for automatic generation of lexical analyzers from regular expression specifications, including syntax, rules, and examples.
Introduction
Lex (and its modern successor Flex) is a tool that automatically generates lexical analyzers from a specification file. Instead of manually coding a scanner, you write regular expression patterns paired with actions, and Lex produces a C program that implements the scanner. This dramatically simplifies lexical analyzer development.
How Lex Works
| Lex Source | Lex | lex.yy.c | ||
|---|---|---|---|---|
| (spec.l) | ──> | Tool | ──> | (C source) |
Lex Specification Format
A Lex specification has three sections:
Example
%{
/* Declarations Section - C code copied directly */
#include <stdio.h>
int lineCount = 0;
%}
/* Definitions Section - named patterns */
DIGIT [0-9]
LETTER [A-Za-z]
ID {LETTER}({LETTER}|{DIGIT})*
%%
/* Rules Section - patterns and actions */
pattern1 { action1; }
pattern2 { action2; }
%%
/* User Code Section - additional C functions */
int main() {
yylex();
return 0;
}
Key Variables and Functions
| Name | Type | Description |
|---|---|---|
yytext | char* | Pointer to matched text |
yyleng | int | Length of matched text |
yyin | FILE* | Input file (default: stdin) |
yyout | FILE* | Output file (default: stdout) |
yylex() | function | Main scanning function |
yywrap() | function | Called at EOF |
ECHO | macro | Print matched text |
Complete Example: Simple Scanner
Example
%{
#include <stdio.h>
#include <string.h>
int num_lines = 0;
int num_words = 0;
int num_ids = 0;
%}
DIGIT [0-9]
LETTER [A-Za-z_]
%%
"if" { printf("KEYWORD: if\n"); }
"else" { printf("KEYWORD: else\n"); }
"while" { printf("KEYWORD: while\n"); }
"int" { printf("KEYWORD: int\n"); }
"float" { printf("KEYWORD: float\n"); }
"return" { printf("KEYWORD: return\n"); }
{LETTER}({LETTER}|{DIGIT})* {
printf("IDENTIFIER: %s\n", yytext);
num_ids++;
}
{DIGIT}+ { printf("INTEGER: %s\n", yytext); }
{DIGIT}+"."{DIGIT}+ { printf("FLOAT: %s\n", yytext); }
"+" { printf("OPERATOR: PLUS\n"); }
"-" { printf("OPERATOR: MINUS\n"); }
"*" { printf("OPERATOR: TIMES\n"); }
"/" { printf("OPERATOR: DIVIDE\n"); }
"=" { printf("OPERATOR: ASSIGN\n"); }
"==" { printf("OPERATOR: EQUAL\n"); }
"!=" { printf("OPERATOR: NOT_EQUAL\n"); }
"<" { printf("OPERATOR: LT\n"); }
">" { printf("OPERATOR: GT\n"); }
"<=" { printf("OPERATOR: LTEQ\n"); }
">=" { printf("OPERATOR: GTEQ\n"); }
"(" { printf("LPAREN\n"); }
")" { printf("RPAREN\n"); }
"{" { printf("LBRACE\n"); }
"}" { printf("RBRACE\n"); }
";" { printf("SEMICOLON\n"); }
"," { printf("COMMA\n"); }
"//"[^\n]* { /* skip single-line comments */ }
"/*"([^*]|"*"[^/])*"*/" { /* skip multi-line comments */ }
[ \t]+ { /* skip whitespace */ }
\n { num_lines++; }
. { printf("ERROR: Unknown character '%s'\n", yytext); }
%%
int main(int argc, char *argv[]) {
if (argc > 1) {
yyin = fopen(argv[1], "r");
if (!yyin) {
fprintf(stderr, "Cannot open %s\n", argv[1]);
return 1;
}
}
yylex();
printf("\nStatistics:\n");
printf("Lines: %d\n", num_lines);
printf("Identifiers: %d\n", num_ids);
return 0;
}
int yywrap() {
return 1; // No more input files
}
Building and Running
bash example
# Generate scanner C code
flex scanner.l # produces lex.yy.c
# Compile
gcc lex.yy.c -o scanner -lfl
# Run
echo "int x = 42;" | ./scannerPattern Matching Rules in Lex
Rule Priorities
- Longest match: Lex always matches the longest possible string
- First match: If two rules match the same length, the first rule wins
Example
"if" { return IF; } /* Rule 1 */
[a-z]+ { return ID; } /* Rule 2 */
Input: "ifx"
→ Rule 2 matches "ifx" (longest match beats keyword)
Input: "if"
→ Rule 1 wins (same length, first rule priority)
Start Conditions
For context-dependent scanning:
lex example
%x COMMENT
%%
"/*" { BEGIN(COMMENT); }
<COMMENT>"*/" { BEGIN(INITIAL); }
<COMMENT>. { /* ignore content */ }
<COMMENT>\n { /* ignore newlines */ }Integration with Yacc/Bison
Lex typically provides tokens to a Yacc/Bison parser:
Example
%{
#include "y.tab.h" // Token definitions from Yacc
%}
%%
"if" { return IF; }
"else" { return ELSE; }
[0-9]+ { yylval.ival = atoi(yytext); return NUMBER; }
[a-z]+ { yylval.sval = strdup(yytext); return ID; }
%%
Advantages and Limitations
Advantages
- Rapid development of scanners
- Mathematically proven correctness
- Automatic optimization (DFA minimization)
- Easy to modify and maintain
- Well-tested code generation
Limitations
- Generated code can be larger than hand-coded
- Sometimes slower than hand-optimized scanners
- Limited to regular languages
- Debugging generated code is difficult
- Less control over error handling
Interview Questions
- What is Lex and what does it produce?
Lex is a lexical analyzer generator that takes a specification file (containing regex patterns with actions) and produces a C source file implementing a scanner. The specification uses .l extension, and the output is lex.yy.c.
- What are the three sections of a Lex specification?
(1) Declarations section (between %{ and %}) for C includes and variable declarations, (2) Rules section (between %% delimiters) containing pattern-action pairs, and (3) User code section for additional C functions like main().
- How does Lex resolve conflicts between multiple matching patterns?
Using two rules: longest match (the pattern matching the most characters wins) and first match (if multiple patterns match the same length string, the pattern listed first in the specification wins).
- What are yytext and yyleng?
yytext is a character pointer to the text of the current matched lexeme. yyleng is an integer giving the length of the matched text. Both are set automatically before each action is executed.
- What is a start condition in Lex?
A start condition is a named state that enables context-dependent scanning. Rules prefixed with <STATE> only match when that state is active. They're useful for handling multi-line comments, string literals, and other context-sensitive constructs.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Lex Tool - Lexical Analyzer Generator.
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, lex, tool
Related Compiler Design Topics
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 AnalysisLexemes in Compiler DesignUnderstanding lexemes, their role in lexical analysis, how they are identified from source code, and their relationship with tokens and patterns.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.