CD Notes

Lex: Original Lexical Analyzer

Introduction to Lex, comparison with Flex, and historical context

Introduction and History

Lex is the grandfather of all lexical analyzer generators. Created by Mike Lesk and Eric Schmidt at Bell Labs in 1975 (yes, the same Eric Schmidt who later became Google's CEO), Lex transformed compiler construction by automating the tedious process of writing scanners by hand. Before Lex, building a lexer meant writing hundreds of lines of character-by-character switch statements. After Lex, you could specify token patterns as regular expressions and get a working, efficient scanner automatically.

Lex was distributed as part of Unix and became the standard tool for the first fifteen years of modern compiler development. In 1987, Vern Paxson created Flex (Fast Lex) as an improved, faster, open-source replacement. Today, Flex is the standard choice for new projects, but understanding Lex provides historical context and helps you work with legacy systems.

How Lex Works: From Patterns to Scanner

Lex reads a specification file containing regular expression patterns paired with C code actions. It converts these patterns into a deterministic finite automaton (DFA) and outputs a C source file implementing the scanner:

Lex specification (.l file) │ ▼ ┌─────────────────────┐ │ Lex tool │ Converts regex → NFA → DFA → C code └────────┬────────────┘ │ ▼ ┌─────────────────────┐ │ lex.yy.c │ Generated C source implementing yylex() └────────┬────────────┘ │ ▼ ┌─────────────────────┐ │ gcc lex.yy.c -ll │ Compile with Lex library └─────────────────────┘

The generated yylex() function reads input characters, matches them against the compiled DFA, and executes the action associated with the longest matching pattern.

Lex Specification File Format

A Lex file has three sections, separated by %%:

Example

%{ /* Section 1: C declarations #includes, global variables, function prototypes */ #include <stdio.h> #include <string.h> int line_count = 0; int word_count = 0; %} /* Definitions: named patterns for reuse */ DIGIT [0-9] LETTER [a-zA-Z] ID {LETTER}({LETTER}|{DIGIT}|_)* %% /* Section 2: Rules — pattern-action pairs */ {DIGIT}+ { printf("INTEGER: %s\n", yytext); } {DIGIT}+\.{DIGIT}+ { printf("FLOAT: %s\n", yytext); } {ID} { printf("IDENTIFIER: %s\n", yytext); word_count++; } "if" { printf("KEYWORD: if\n"); } "while" { printf("KEYWORD: while\n"); } "+" { printf("OPERATOR: +\n"); } "-" { printf("OPERATOR: -\n"); } "*" { printf("OPERATOR: *\n"); } "/" { printf("OPERATOR: /\n"); } "=" { printf("OPERATOR: =\n"); } "==" { printf("OPERATOR: ==\n"); } [ \t]+ { /* Skip whitespace */ } \n { line_count++; } . { printf("UNKNOWN: %s\n", yytext); } %% /* Section 3: User code — main() and helper functions */ int main(int argc, char *argv[]) { if (argc > 1) yyin = fopen(argv[1], "r"); yylex(); printf("Lines: %d, Words: %d\n", line_count, word_count); return 0; } int yywrap() { return 1; } /* Signal end of input */

Understanding Key Lex Variables and Functions

Lex provides several important variables that your actions can use:

Variable/Function	Purpose
`yytext`	Pointer to the matched text (the lexeme)
`yyleng`	Length of the matched text
`yyin`	Input file pointer (default: stdin)
`yyout`	Output file pointer (default: stdout)
`yylex()`	The generated scanner function
`yywrap()`	Called at end-of-file; return 1 to stop, 0 to continue
`yylineno`	Current line number (if `%option yylineno` in Flex)
`ECHO`	Macro that writes yytext to yyout

Lex Regular Expression Syntax

Lex supports a rich set of regular expression operators:

Literal characters

a Matches character 'a'

"if" Matches literal string "if"

\n Matches newline

\t Matches tab

\\ Matches backslash

Character classes

[abc] Matches a, b, or c

[a-z] Matches any lowercase letter

[0-9] Matches any digit

[^abc] Matches anything EXCEPT a, b, c

. Matches any character except newline

Repetition operators

a* Zero or more 'a's

a+ One or more 'a's

a? Zero or one 'a'

a{3} Exactly 3 'a's

a{2,5} Between 2 and 5 'a's

Anchors

^pattern Match only at beginning of line

pattern$ Match only at end of line

Alternation and grouping

a|b Match a or b

(ab)+ One or more repetitions of "ab"

The Longest Match and Rule Priority Principles

Lex uses two critical rules to resolve ambiguity when multiple patterns could match:

Longest Match: If multiple patterns match starting at the same position, Lex chooses the one that matches the most characters. For input "identifier123", the pattern [a-zA-Z][a-zA-Z0-9]* matches all 13 characters rather than just "identifier".

Rule Priority: If two patterns match the same length of input, the rule listed first in the specification wins. This is why keywords must appear before the general identifier pattern:

Example

"if" { return IF; } /* Must come first! */ "while" { return WHILE; } [a-zA-Z_][a-zA-Z0-9_]* { return ID; } /* General pattern last */

If the identifier pattern came first, "if" would match as an identifier and the keyword rule would never fire.

Worked Example: Scanning C-like Input

Given this input file:

c example

int x = 42;
if (x > 0) {
    x = x + 1;
}

Our Lex scanner processes character by character:

Position 0: 'i'	starts matching "if"? Also matches ID pattern
'i','n','t'	"int" matches ID (3 chars), "if" only matches 2
But "int" keyword rule matches 3 chars too	first rule wins
Output	KEYWORD: int
Position 4: 'x'	matches ID pattern (1 char)
Output	IDENTIFIER: x
Position 6: '='	matches "=" rule (1 char)
But check next	is it "=="? No, next char is space
Output	OPERATOR: =
Position 8: '4','2'	matches DIGIT+ (2 chars)
Output	INTEGER: 42
Position 10: ';'	matches ";" rule
Output	DELIMITER: ;

Lex vs Flex: Practical Differences

While the file format is nearly identical, Flex provides significant improvements:

Performance: Flex generates table-driven scanners that are 30-40% faster than Lex's output. Flex uses compressed tables that fit better in CPU cache.

Reentrant scanners: Flex can generate thread-safe scanners (no global state) using %option reentrant, essential for multi-threaded applications.

Start conditions: Flex has much better support for scanner states. For example, handling string literals and comments cleanly:

Example

%x STRING COMMENT %% \" { BEGIN(STRING); } <STRING>[^"]* { /* accumulate string content */ } <STRING>\" { BEGIN(INITIAL); return STRING_TOKEN; } "/*" { BEGIN(COMMENT); } <COMMENT>"*/" { BEGIN(INITIAL); } <COMMENT>.|\n { /* skip comment content */ }

Debugging: Flex provides %option debug for tracing scanner operation, invaluable during development.

Compiling and Running a Lex Program

bash example

# Using original Lex (if available)
lex scanner.l            # Generates lex.yy.c
cc lex.yy.c -ll -o scanner  # Compile with lex library

# Using Flex (recommended)
flex scanner.l           # Generates lex.yy.c
gcc lex.yy.c -lfl -o scanner  # Compile with flex library

# Run the scanner
echo "int x = 42;" | ./scanner
# Or read from file:
./scanner source_code.c

Key Takeaways

Lex pioneered the concept of declarative scanner specification — instead of writing procedural code to recognize tokens, you declare the patterns and let the tool generate an efficient DFA-based implementation. This separation of specification from implementation made compiler construction dramatically more accessible. While Flex has replaced Lex for new projects, the concepts, file format, and approach remain unchanged. Every modern lexical analyzer generator — whether for C, Java, Python, or any other host language — traces its lineage back to Lex.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Lex: Original Lexical Analyzer.

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, parser, generators, lex, introduction

Continue learning this concept

Parser GeneratorsYACC: Original Parser GeneratorHistorical context and usage of YACC, comparison with Bison Parser GeneratorsBison: LALR Parser GeneratorDetailed guide to Bison parser generation, grammar rules, LALR parsing, and compiler construction Parser GeneratorsFlex: Lexical Analyzer GeneratorComprehensive guide to Flex tool, regular expressions, state machines, and DFA generation Parser GeneratorsParser Generator WorkflowComplete guide to using Flex and Bison together, build systems, debugging, and best practices Parser GeneratorsPractical Parser ProjectsReal-world parser implementation guide with AST construction, symbol tables, and code generation Code GenerationIntroduction to Code Generation in Compiler DesignComprehensive introduction to the code generation phase of compilation covering objectives, challenges, target code forms, and the interface between intermediate representation and machine code.

PreviousFlex: Lexical Analyzer Generator NextParser Generator Workflow

CD Notes

Lex: Original Lexical Analyzer

Introduction to Lex, comparison with Flex, and historical context

Introduction and History

How Lex Works: From Patterns to Scanner

The generated yylex() function reads input characters, matches them against the compiled DFA, and executes the action associated with the longest matching pattern.

Lex Specification File Format

A Lex file has three sections, separated by %%:

Example

Understanding Key Lex Variables and Functions

Lex provides several important variables that your actions can use:

Variable/Function	Purpose
`yytext`	Pointer to the matched text (the lexeme)
`yyleng`	Length of the matched text
`yyin`	Input file pointer (default: stdin)
`yyout`	Output file pointer (default: stdout)
`yylex()`	The generated scanner function
`yywrap()`	Called at end-of-file; return 1 to stop, 0 to continue
`yylineno`	Current line number (if `%option yylineno` in Flex)
`ECHO`	Macro that writes yytext to yyout

Lex Regular Expression Syntax

Lex supports a rich set of regular expression operators:

Literal characters

a Matches character 'a'

"if" Matches literal string "if"

\n Matches newline

\t Matches tab

\\ Matches backslash

Character classes

[abc] Matches a, b, or c

[a-z] Matches any lowercase letter

[0-9] Matches any digit

[^abc] Matches anything EXCEPT a, b, c

. Matches any character except newline

Repetition operators

a* Zero or more 'a's

a+ One or more 'a's

a? Zero or one 'a'

a{3} Exactly 3 'a's

a{2,5} Between 2 and 5 'a's

Anchors

^pattern Match only at beginning of line

pattern$ Match only at end of line

Alternation and grouping

a|b Match a or b

(ab)+ One or more repetitions of "ab"

The Longest Match and Rule Priority Principles

Lex uses two critical rules to resolve ambiguity when multiple patterns could match:

Rule Priority: If two patterns match the same length of input, the rule listed first in the specification wins. This is why keywords must appear before the general identifier pattern:

Example

"if" { return IF; } /* Must come first! */ "while" { return WHILE; } [a-zA-Z_][a-zA-Z0-9_]* { return ID; } /* General pattern last */

If the identifier pattern came first, "if" would match as an identifier and the keyword rule would never fire.

Worked Example: Scanning C-like Input

Given this input file:

c example

int x = 42;
if (x > 0) {
    x = x + 1;
}

Our Lex scanner processes character by character:

Position 0: 'i'	starts matching "if"? Also matches ID pattern
'i','n','t'	"int" matches ID (3 chars), "if" only matches 2
But "int" keyword rule matches 3 chars too	first rule wins
Output	KEYWORD: int
Position 4: 'x'	matches ID pattern (1 char)
Output	IDENTIFIER: x
Position 6: '='	matches "=" rule (1 char)
But check next	is it "=="? No, next char is space
Output	OPERATOR: =
Position 8: '4','2'	matches DIGIT+ (2 chars)
Output	INTEGER: 42
Position 10: ';'	matches ";" rule
Output	DELIMITER: ;

Lex vs Flex: Practical Differences

While the file format is nearly identical, Flex provides significant improvements:

Performance: Flex generates table-driven scanners that are 30-40% faster than Lex's output. Flex uses compressed tables that fit better in CPU cache.

Reentrant scanners: Flex can generate thread-safe scanners (no global state) using %option reentrant, essential for multi-threaded applications.

Start conditions: Flex has much better support for scanner states. For example, handling string literals and comments cleanly:

Example

Debugging: Flex provides %option debug for tracing scanner operation, invaluable during development.

Compiling and Running a Lex Program

bash example

# Using original Lex (if available)
lex scanner.l            # Generates lex.yy.c
cc lex.yy.c -ll -o scanner  # Compile with lex library

# Using Flex (recommended)
flex scanner.l           # Generates lex.yy.c
gcc lex.yy.c -lfl -o scanner  # Compile with flex library

# Run the scanner
echo "int x = 42;" | ./scanner
# Or read from file:
./scanner source_code.c

Key Takeaways

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Lex: Original Lexical Analyzer.

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, parser, generators, lex, introduction

Continue learning this concept

PreviousFlex: Lexical Analyzer Generator NextParser Generator Workflow