In the last two chapters, Lexical Analysis: Tokens, Lexemes & Patterns and Input Buffering & Recognition of Tokens, we described tokens with regular expressions and then recognized them by hand with transition diagrams. That works, but writing a scanner by hand for a real language is slow and error-prone: dozens of keywords, operators that share prefixes (<, <=, <<), numbers in several formats, comments, strings, and careful buffer handling.
Notice that everything a scanner does is fully determined by the list of patterns. So why not let a program generate the scanner from that list? That is exactly what Lex and its modern version Flex do. You write the regular expressions and say what to do when each one matches; the tool writes the C code for a fast DFA-based scanner.
In this chapter you will learn the structure of a Lex program, its pattern syntax, the built-in variables like yytext and yylex(), and, most importantly for exams, how Lex decides which rule matches. Every program in this chapter was compiled with flex 2.6.4 and gcc, and the outputs shown are real.
What Are Lex and Flex?
Lex is a lexical-analyzer generator: it takes a specification made of regular expressions paired with C actions and produces a C program (a scanner) that reads input, finds the lexemes matching those expressions, and runs the corresponding actions.
Lex was written at Bell Labs in the mid-1970s by Mike Lesk and Eric Schmidt, as part of Unix.
Flex ("fast lexical analyzer generator") is the free, faster, mostly compatible re-implementation used on Linux today. When people say "Lex" in a lab, they almost always run
flex.
Lex is usually paired with Yacc (or its GNU version Bison), a parser generator. Lex produces the function yylex() that hands out one token at a time; Yacc produces yyparse(), which calls yylex() whenever it needs the next token. We will meet Yacc in the Yacc & Bison chapter.
The Big Picture
scanner.l ──► [ flex ] ──► lex.yy.c ──► [ gcc ] ──► a.out (the scanner)
(patterns + (C code with │
actions) yylex()) ▼
source text ──► a.out ──► tokens / outputSo there are two translation steps: flex translates your specification into C, and the C compiler translates that into an executable. Only the executable ever looks at the input text.
Structure of a Lex Program
A Lex file has three sections separated by lines containing only %%:
definitions
%%
rules
%%
user codeSection | What goes here | Copied to lex.yy.c? |
|---|---|---|
Definitions | C code inside | The |
Rules | Lines of the form | Turned into the DFA tables and a big |
User code | Any C functions you need, usually | Copied verbatim at the end |
The first %% is required (a file needs at least a rules section). The second %% and the user-code section are optional.
A First Program: Counting Lines, Words and Characters
Here is a tiny version of the Unix wc command, where a "word" is a run of letters:
%{
#include <stdio.h>
int chars = 0, words = 0, lines = 0;
%}
%option noyywrap
%%
[a-zA-Z]+ { words++; chars += yyleng; }
\n { lines++; chars++; }
. { chars++; }
%%
int main(void) {
yylex();
printf("lines=%d words=%d chars=%d\n", lines, words, chars);
return 0;
}Input file input1.txt:
Hello world
Compilers are fun!Build and run:
$ flex count.l # produces lex.yy.c
$ gcc lex.yy.c -o count
$ ./count < input1.txt
lines=2 words=5 chars=31Check by hand: the words are Hello, world, Compilers, are, fun (5). Characters: "Hello world" is 11 plus a newline (12), "Compilers are fun!" is 18 plus a newline (19), total 31. The real wc command gives the same numbers for this file.
What is happening:
yylex()is the scanner flex generated. It loops over the input, finds the next match, runs its action and keeps going until end of input (because none of our actionsreturn).yylengis the length of the matched text, so one action adds the whole word's length at once..matches any single character except newline, which is why\nneeds its own rule.%option noyywraptells flex we do not supply ayywrap()function (explained below), so we do not need to link the flex library.
Lex Pattern Syntax
Lex patterns are the regular expressions from the Lexical Analysis chapter, plus some convenient shorthands:
Pattern | Matches | Example |
|---|---|---|
| The character x |
|
| Any character except newline |
|
| One character from the set |
|
| One character in the range |
|
| One character not in the set (newline included!) |
|
| Zero or more, one or more, zero or one r |
|
| Two to four copies of r ( |
|
| r or s |
|
| Grouping |
|
| The string literally (operators lose their meaning) |
|
| Escape: the character x literally, or C escapes like |
|
| The named pattern defined in the definitions section |
|
| r only at the beginning of a line |
|
| r only at the end of a line |
|
| r, but only if followed by s (s is not consumed) |
|
| r, only when the scanner is in start condition S |
|
| End of file (flex extension) | error for unclosed comment |
Two points that trip people up:
Inside
[ ]most operators are ordinary characters:[+*]means "plus or star". A-is literal only at the start or end of the class, so write[-+*/], not[+-*/]. In the second form+-*is read as a range from+(ASCII 43) down to*(ASCII 42), and flex stops with the error "negative range in character class".Spaces end the pattern. To match a space, write
" "or\or put it in a class[ ].
Trailing Context in Action
The r/s operator lets a rule "look ahead" without eating characters. This scanner tells a function name apart from an ordinary identifier by peeking for (:
%option noyywrap
%%
[a-z]+/"(" { printf("CALL(%s) ", yytext); }
[a-z]+ { printf("ID(%s) ", yytext); }
[ \t\n,()+] { /* skip */ }
%%
int main(void) { yylex(); printf("\n"); return 0; }$ printf 'max(a, b) + max\n' | ./trail
CALL(max) ID(a) ID(b) ID(max) The first max is followed by (, so the first rule matches; the ( stays in the input and is then skipped by the third rule. The last max is not followed by (, so it is an ordinary ID.
Built-in Variables and Functions
Every generated scanner provides these names. You will use the first six in almost every program:
Name | Type | Meaning |
|---|---|---|
| function | The scanner. Each call scans until an action executes |
|
| The lexeme just matched, as a null-terminated string |
|
| Length of |
|
| Input and output streams (default stdin and stdout). Set |
| usually | The attribute value of the token (for example the number's value). Declared by the parser when you use Yacc; you declare it yourself otherwise |
| function | Called at end of input. Return 1 to stop, or 0 after pointing |
|
| Current line number (in flex, needs |
| macro | Copy |
| macro | Switch to start condition S ( |
| macro | Keep only the first n characters of the match; push the rest back into the input |
| function | Append the next match to the current |
| macro | Give up this match and use the next-best rule (slows the scanner down) |
| functions | Read one more character directly / push a character back |
About yywrap and -lfl
When yylex() reaches end of file, it calls yywrap(). Someone must define that function. You have three choices:
Write
%option noyywrap: flex behaves as ifyywrap()returned 1. This is the simplest and what we use in this chapter.Define
int yywrap(void) { return 1; }yourself in the user-code section.Link the flex library with
-lfl(classic Lex used-ll). It supplies a defaultyywrap()returning 1 and a defaultmain()that keeps callingyylex()until it returns 0.
If you do none of these, the link step fails with "undefined reference to yywrap". This is the most common error students see in the Lex lab.
The Default Rule
What happens to characters that match no pattern? Lex has an implicit last rule: copy the character to the output (as if the action were ECHO). This file has a rules section with only one rule and no user code, so we link with -lfl to get main() and yywrap():
%%
[0-9]+ { printf("<NUM:%s>", yytext); }
%%$ flex echo.l && gcc lex.yy.c -lfl -o echo
$ printf 'Room 101, floor 3\n' | ./echo
Room <NUM:101>, floor <NUM:3>Everything that is not a number passed through unchanged. This makes Lex handy for quick text filters, but in a real scanner you should add a final . rule that reports an error, so stray characters never sneak through silently.
How Lex Chooses a Rule: Longest Match, Then First Rule
Several patterns can match at the same position. Lex settles it with two rules, applied in this order:
1. Longest match: choose the rule that matches the longest prefix of the remaining input.
2. Rule priority: if two or more rules match the same longest prefix, choose the one listed first in the file.
After the action runs, scanning resumes right after the matched text. These two rules are exactly the conventions from the Input Buffering & Recognition of Tokens chapter; Lex just applies them automatically.
Why these rules?
Longest match makes
<=one token instead of<followed by=, makescountone identifier instead of five one-letter identifiers, and makes3.14a single real number.First rule wins ties lets keywords beat identifiers:
ifmatches both the keyword pattern and the identifier pattern with the same length, so the keyword rule must come before the identifier rule.
Worked Example: Tracing a Lex Specification
A favourite exam question gives a few rules and an input string and asks for the output. Consider:
%option noyywrap
%%
ab { printf("1(%s) ", yytext); }
a+ { printf("2(%s) ", yytext); }
a*b+ { printf("3(%s) ", yytext); }
\n { printf("\n"); }
%%
int main(void) { yylex(); return 0; }Question: What is printed for the input abaabbbaa?
Step 1. Remaining input abaabbbaa. Find the longest match of each rule at this position:
Rule | Longest prefix it matches | Length |
|---|---|---|
1: | ab | 2 |
2: | a | 1 |
3: | ab (the next character is a, so b+ stops) | 2 |
Rules 1 and 3 tie at length 2, so the earlier rule, rule 1, wins. Output 1(ab).
Step 2. Remaining aabbbaa. Rule 1 does not match (the second character is a), rule 2 matches aa (2), rule 3 matches aabbb (5). Longest wins: 3(aabbb).
Step 3. Remaining aa. Only rule 2 matches (rule 3 needs at least one b): 2(aa).
The real run agrees:
$ printf 'abaabbbaa\n' | ./puzzle
1(ab) 3(aabbb) 2(aa) When Rule Order Goes Wrong
Here the identifier rule is placed before the keyword:
%option noyywrap
%%
[a-z]+ { printf("ID(%s) ", yytext); }
"if" { printf("IF "); }
[ \t\n] { }
%%
int main(void) { yylex(); printf("\n"); return 0; }flex notices the problem and warns us while generating the scanner:
$ flex order.l
order.l:4: warning, rule cannot be matched
$ printf 'if iffy ifs if\n' | ./order
ID(if) ID(iffy) ID(ifs) ID(if) Every if came out as an identifier: whenever "if" matches, [a-z]+ matches the same two characters and is listed first. Put the keyword rule first and the output becomes IF ID(iffy) ID(ifs) IF. Notice that iffy stays an identifier either way, thanks to longest match.
(Real compilers often avoid long keyword lists in the patterns: they match all words with the identifier rule and then look the lexeme up in a keyword table. Both approaches are fine.)
A Complete Scanner for a Small Language
Now let's put everything together: named definitions, keywords, identifiers, integer and real numbers, operators, comments and an error rule.
%{
/* tokens.l : a scanner for a tiny C-like language */
#include <stdio.h>
%}
%option noyywrap yylineno
DIGIT [0-9]
LETTER [a-zA-Z_]
ID {LETTER}({LETTER}|{DIGIT})*
NUM {DIGIT}+
REAL {DIGIT}+"."{DIGIT}+([eE][+-]?{DIGIT}+)?
%%
"//".* { /* skip single-line comment */ }
[ \t\r\n]+ { /* skip whitespace */ }
"if"|"else"|"while"|"int"|"float"|"return" { printf("%-3d KEYWORD %s\n", yylineno, yytext); }
{ID} { printf("%-3d ID %s\n", yylineno, yytext); }
{REAL} { printf("%-3d REAL %s\n", yylineno, yytext); }
{NUM} { printf("%-3d NUM %s\n", yylineno, yytext); }
"<="|">="|"=="|"!=" { printf("%-3d RELOP %s\n", yylineno, yytext); }
"<"|">" { printf("%-3d RELOP %s\n", yylineno, yytext); }
"=" { printf("%-3d ASSIGN %s\n", yylineno, yytext); }
[-+*/] { printf("%-3d ARITHOP %s\n", yylineno, yytext); }
[(){};,] { printf("%-3d PUNCT %s\n", yylineno, yytext); }
. { printf("%-3d ERROR unexpected '%s'\n", yylineno, yytext); }
%%
int main(void) {
yylex();
return 0;
}Test program prog.c (note the deliberate errors: ifx is not declared, which is the parser's business, and @ is not a legal character, which is the scanner's business):
int count = 0; // counter
float rate = 2.5e3;
if (count <= 10) ifx = count == rate;
else return 3.14 @ 7;$ flex -o tokens.c tokens.l && gcc tokens.c -o tokens
$ ./tokens < prog.c
1 KEYWORD int
1 ID count
1 ASSIGN =
1 NUM 0
1 PUNCT ;
2 KEYWORD float
2 ID rate
2 ASSIGN =
2 REAL 2.5e3
2 PUNCT ;
3 KEYWORD if
3 PUNCT (
3 ID count
3 RELOP <=
3 NUM 10
3 PUNCT )
3 ID ifx
3 ASSIGN =
3 ID count
3 RELOP ==
3 ID rate
3 PUNCT ;
4 KEYWORD else
4 KEYWORD return
4 REAL 3.14
4 ERROR unexpected '@'
4 NUM 7
4 PUNCT ;Things to notice in the output:
// counterand all whitespace produced nothing: their actions are empty, so the scanner just moves on.2.5e3is one REAL token (longest match), not NUM2followed by junk.<=and==are single tokens, again by longest match.ifxis an ID: the keyword rule matches onlyif(2 characters) while{ID}matchesifx(3).@fell through to the final.rule, which reports an error and lets scanning continue with7. A lexical error does not stop the scanner.The
{DIGIT},{ID}names make long patterns readable, just like regular definitions in the Lexical Analysis chapter.
Returning Tokens to a Parser
The scanners so far printed tokens themselves. Inside a compiler, the scanner instead returns one token at a time to the parser, together with an attribute value. Each call to yylex() runs until an action executes return:
The return value is the token code (an integer). Codes for named tokens start above 255 so that single characters like
'+'can be returned as their own character codes if you like; Bison numbers named tokens from 258 (256 and 257 are reserved for its internalerrorand "undefined" tokens), while classic Yacc started at 257.The attribute goes into the global
yylval.At end of input,
yylex()returns 0, which the parser treats as the end marker.
This scanner also shows a start condition, a mini-mode of the scanner. %x COMMENT declares an exclusive condition: while the scanner is in it, only rules prefixed with <COMMENT> are active. That is the clean way to skip a multi-line /* ... */ comment.
%{
#include <stdio.h>
#include <stdlib.h>
enum { NUM = 258, ID, PLUS, TIMES, LPAREN, RPAREN };
int yylval; /* value of a NUM token */
%}
%option noyywrap yylineno
%x COMMENT
%%
"/*" { BEGIN(COMMENT); }
<COMMENT>"*/" { BEGIN(INITIAL); }
<COMMENT>.|\n { /* ignore everything inside the comment */ }
<COMMENT><<EOF>> { fprintf(stderr, "line %d: unterminated comment\n", yylineno); return 0; }
[0-9]+ { yylval = atoi(yytext); return NUM; }
[a-zA-Z_][a-zA-Z0-9_]* { return ID; }
"+" { return PLUS; }
"*" { return TIMES; }
"(" { return LPAREN; }
")" { return RPAREN; }
[ \t\n]+ { /* skip */ }
. { fprintf(stderr, "line %d: bad character '%s'\n", yylineno, yytext); }
%%
int main(void) {
static const char *name[] = { "NUM", "ID", "PLUS", "TIMES", "LPAREN", "RPAREN" };
int tok;
while ((tok = yylex()) != 0) {
if (tok == NUM)
printf("%-7s lexeme=%-6s value=%d\n", name[tok - 258], yytext, yylval);
else
printf("%-7s lexeme=%s\n", name[tok - 258], yytext);
}
printf("end of input\n");
return 0;
}$ printf 'rate * (x1 + 42) /* a\nmulti-line comment */ + 7\n' | ./scan
ID lexeme=rate
TIMES lexeme=*
LPAREN lexeme=(
ID lexeme=x1
PLUS lexeme=+
NUM lexeme=42 value=42
RPAREN lexeme=)
PLUS lexeme=+
NUM lexeme=7 value=7
end of input
$ printf 'a + 1 /* oops' | ./scan
ID lexeme=a
PLUS lexeme=+
NUM lexeme=1 value=1
line 1: unterminated comment
end of inputThe main() here plays the role a parser would play. In the Yacc & Bison chapter the token codes and yylval come from the parser's header file instead of our own enum, but the scanner side looks almost the same.
Why not just write a pattern like "/*"(.|\n)*"*/" for comments? Because of longest match: in /* a */ x = 1; /* b */, that pattern would happily match from the first /* to the last */, swallowing the code in between. A correct single regex exists but is hard to read; the start condition is simpler and also lets us report an unterminated comment.
How Lex Works Inside
Flex turns your specification into a scanner using the theory from the previous chapters and from the Theory of Computation tutorial:
Each pattern pi is converted into an NFA Ni (Thompson's construction).
A new start state gets ε-moves to the start of every Ni, giving one big NFA for the whole specification. Each accepting state remembers which rule it belongs to.
Subset construction turns this NFA into a DFA, and its transition tables are then compressed (any merging of equivalent states must keep apart states that accept for different rules). A DFA state that contains accepting states of several rules is labelled with the earliest of those rules: that is how "first rule wins" is built into the tables.
At run time, the scanner walks the DFA from the current position, remembering the last accepting state and its input position. When the DFA gets stuck (no transition), it backs up to that last accepting position: that is the longest match. It runs that rule's action and restarts from the next character.
input: a a b b b a a rules: 1 = ab, 2 = a+, 3 = a*b+
^
DFA walk from here: a → (rule 2 accepts) a → (rule 2) b → (rule 3) b → (rule 3)
b → (rule 3) a → no move → STOP, back up to last accept
longest match = "aabbb", rule 3Because the work per input character is just a table lookup, a generated scanner is about as fast as a carefully hand-written one, usually faster. The price is paid once, at generation time: subset construction can in the worst case produce a DFA with exponentially many states, but for real token sets the DFA is small.
Lex vs Flex
Aspect | Lex (original Unix) | Flex |
|---|---|---|
Availability | Proprietary Unix tool (POSIX specifies its interface) | Free, open source, default on Linux |
Speed | Slower generated scanners | Faster, with table-compression options |
Library |
|
|
Extras | Basic start conditions | Exclusive start conditions ( |
Common Mistakes
Putting the identifier rule before the keywords. Every keyword then becomes an identifier. Flex warns "rule cannot be matched"; do not ignore it.
Thinking the first rule always wins. Rule order only breaks ties between matches of the same length. A longer match by a later rule always wins.
Indenting a pattern. In the rules section a line starting with whitespace is treated as C code, not as a pattern.
Forgetting that
.excludes newline, so a scanner with only a.rule echoes newlines through the default rule.Writing
[+-*/]: the-in the middle creates a character range (here an invalid one, so flex refuses the file). Put-first or last.Linker error "undefined reference to yywrap": add
%option noyywrap, defineyywrap(), or link with-lfl.Storing the
yytextpointer for later. Its contents are overwritten by the next match; copy the string (for example withstrdup) if you need to keep it.
GATE and Interview Questions
What are the three sections of a Lex program, and which ones are optional?
Definitions, rules and user subroutines, separated by %%. The definitions section may be empty and the second %% with the user code may be omitted, but the first %% must be present.
Lex has the rules "if" {return IF;} and [a-z]+ {return ID;}, in that order. What tokens are produced for the input if ifelse (whitespace skipped)?
IF, then ID. For if, both rules match 2 characters and the earlier rule wins. For ifelse, the ID rule matches 6 characters, longer than the 2 of "if", so longest match makes it a single ID.
With the rules a → print 1, a*b → print 2, b+ → print 3 (in that order), what is printed for aaabbab?
At the start, a*b matches aaab (4), longer than a (1) or b+ (0): print 2. Remaining bab: a*b matches b (1), b+ matches b (1), tie, earlier rule wins: print 2. Remaining ab: a*b matches ab (2): print 2. Output: 222.
What do yytext, yyleng and yylval hold?
yytext is the matched lexeme, yyleng its length, and yylval the attribute value passed to the parser along with the token (for example the numeric value of a NUM token).
What does yywrap() return and why does it exist?
It is called at end of input. Returning 1 means "no more input", so yylex() returns 0. Returning 0 means the function has set up yyin with a new file and scanning should continue. It exists so one scanner can process several input files in sequence.
Which automaton does Lex finally use to recognize tokens, and how does it implement the longest-match rule?
A DFA, obtained from the patterns via NFA construction and subset construction. While running, it records the most recent accepting state and position; when no transition is possible, it backs up to that position and runs the rule associated with that accepting state.
What happens to input characters that match none of the rules?
The default rule copies them to yyout (standard output) unchanged. A good scanner adds a catch-all . rule at the end to report them as lexical errors.
What is a start condition? Give a use.
A named state of the scanner that enables a particular subset of rules, entered with BEGIN(name). Typical uses are skipping multi-line comments and scanning string literals with escape sequences, where the rules inside the comment or string are different from the normal ones.
Summary
Lex/Flex generates a C scanner (
lex.yy.cwith the functionyylex()) from regular-expression patterns and C actions.A Lex file has three parts: definitions %% rules %% user code.
Key names:
yytext(lexeme),yyleng(length),yylval(attribute),yyin/yyout(streams),yywrap()(end of input),BEGIN(start conditions).Conflicts are resolved by longest match first, then by earliest rule. So keywords go before the identifier rule.
Unmatched characters are echoed by the default rule; add a catch-all error rule.
To feed a parser, actions return token codes and put values in
yylval;yylex()returns 0 at end of input.Internally: patterns → NFAs → one combined NFA → DFA (subset construction) → compact table-driven scanner with back-up to the last accepting state.
You describe the tokens; Lex builds the automaton. Just remember the two tie-breakers: the longest match wins, and among equals, the first rule wins.