When you read a sentence, you do not look at it letter by letter; your eyes group letters into words first, and only then do you think about grammar. A compiler does the same. Its very first phase, the lexical analyzer, reads the raw stream of characters and groups them into words called tokens. Everything later in the compiler works with tokens, never with individual characters.
In this chapter we define the three terms that every exam asks about (token, lexeme and pattern), see what the lexer does and why it is a separate phase, learn how tokens are specified with regular expressions, practise the famous "count the tokens" questions, and look at lexical errors. All token counts in this chapter were checked by running the code through a real scanner built with flex.
The Role of the Lexical Analyzer
Lexical analysis (scanning) is the first phase of a compiler. It reads the source program character by character, groups the characters into lexemes, and produces a sequence of tokens for the syntax analyzer.
The lexer usually does not run on its own to produce a full token file. Instead, the parser is in charge and asks for one token at a time:
getNextToken()
source +-------+ <------------- +--------+
program -->| LEXER | | PARSER |--> syntax tree --> rest of
+-------+ -------------> +--------+ the compiler
\ token /
\ /
+--> SYMBOL TABLE <-+
Jobs of the lexer
Group characters into tokens: keywords, identifiers, numbers, operators and so on.
Remove whitespace and comments. Blanks, tabs, newlines and comments separate tokens but are not tokens themselves, so the parser never sees them.
Track line (and column) numbers, so later error messages can say
e.c:3:12: error ....Enter identifiers into the symbol table (or at least record their names) and attach the entry to the token.
Report lexical errors, such as illegal characters or unterminated strings.
In some languages, expand macros (in C this is done by the preprocessor before lexing).
Why separate lexical analysis from parsing?
Simpler design. If the grammar had to deal with every blank and comment, it would be much more complicated. Removing them first keeps the parser clean.
Efficiency. The lexer is the only phase that touches every single character of the source, so it can take a noticeable share of compile time. A dedicated lexer can use fast buffering and table-driven automata (see Input Buffering & Recognition of Tokens).
Right tool for each job. Tokens have a simple structure that regular expressions describe perfectly; program structure needs the more powerful context-free grammars.
Portability. Character-set and input-device details stay inside the lexer.
Token, Lexeme and Pattern
These three words are related but not the same. Take the statement
count = count + 25;
Lexeme: an actual sequence of characters in the source program that matches the pattern for a token. Example:
count,=,25.Token: a pair consisting of a token name (an abstract symbol representing a kind of lexical unit) and an optional attribute value. Example: <id, pointer to "count">, <number, 25>. The token name is what the parser works with.
Pattern: a description (rule) of the form that the lexemes of a token may take. Example: "a letter or underscore followed by letters, digits or underscores" for identifiers.
A simple way to remember: the pattern is the rule, a lexeme is a real instance in the code that follows the rule, and the token is the category name the compiler gives to it.
Compare with English: the pattern for "noun" describes what nouns look like, the lexemes are the actual words table, Delhi, idea, and the token is the label NOUN.
Token name | Informal pattern | Sample lexemes |
|---|---|---|
if | the characters i, f |
|
while | the characters w, h, i, l, e |
|
id | letter or _ followed by letters, digits or _ |
|
number | any numeric constant |
|
relop |
|
|
literal | anything between double quotes except a quote |
|
comma | the character , |
|
Notice that one token can have many lexemes (id has infinitely many), while a keyword token has exactly one lexeme. That is why identifiers and numbers need an attribute: the parser only needs to know "this is an id", but later phases need to know which id.
Typical token classes
Keywords (reserved words):
int,if,return. Usually one token name per keyword.Identifiers: names of variables, functions, types. One token name, id.
Constants / literals: numbers, character constants, string literals.
Operators:
+,++,<=,&&, sometimes grouped into classes like relop or addop.Punctuation / special symbols:
(){}[];,.
Token Attributes
A token is written as <token-name, attribute-value>. Which attribute is stored depends on the token:
id: a pointer to its symbol-table entry (which holds the name, and later its type, scope, address).
number: the numeric value (or a pointer to a constant table).
relop: which operator it is, e.g.
LE,NE, so the parser sees one token name for all six relational operators.Keywords and single punctuation marks: no attribute needed; the token name says it all.
Worked example. Tokenise if (count >= 100) total = total * 1.5e2;
# | Lexeme | Token |
|---|---|---|
1 |
| <if> |
2 |
| <(> |
3 |
| <id, pointer to symbol-table entry for count> |
4 |
| <relop, GE> |
5 |
| <number, 100> |
6 |
| <)> |
7 |
| <id, pointer to entry for total> |
8 |
| <assign_op> |
9 |
| <id, pointer to entry for total> (same entry as #7) |
10 |
| <mult_op> |
11 |
| <number, 150.0> |
12 |
| <;> |
12 tokens. Note that >= is one token, not two, and the second total points to the same symbol-table entry as the first.
Specifying Tokens with Regular Expressions
Patterns must be precise, so they are written as regular expressions. (The theory of regular languages is covered in the Theory of Computation tutorial; here we only need the notation.)
Strings and languages
An alphabet is a finite set of symbols, e.g. ASCII.
A string is a finite sequence of symbols; ε denotes the empty string.
A language is a set of strings, e.g. the set of all valid identifiers.
Operation on languages L and M | Definition |
|---|---|
Union L ∪ M | strings in L or in M |
Concatenation LM | a string from L followed by a string from M |
Kleene closure L* | zero or more strings of L concatenated (includes ε) |
Positive closure L+ | one or more strings of L concatenated |
Regular expression notation
Regex | Meaning | Example |
|---|---|---|
| a or b (union) |
|
| a followed by b |
|
| zero or more a's | "", "a", "aa", ... |
| one or more a's (= | "a", "aa", ... |
| zero or one a (= | "", "a" |
| character class: any one of a..z |
|
Precedence, highest first: closure (*, +, ?), then concatenation, then union. So ab*|c means (a(b*))|c.
Regular definitions
Long regular expressions are hard to read, so we give names to parts and reuse them. Each name is defined using only symbols and earlier names:
letter_ -> [A-Za-z_]
digit -> [0-9]
id -> letter_ ( letter_ | digit )*
digits -> digit+
fraction -> . digits
exponent -> ( E | e ) ( + | - )? digits
number -> digits fraction? exponent?
relop -> < | <= | > | >= | == | !=
ws -> ( blank | tab | newline )+
Let us test the number definition:
String | Matches number? | Why |
|---|---|---|
| Yes | digits, no fraction, no exponent |
| Yes | digits fraction |
| Yes | digits fraction exponent |
| Yes | digits exponent (fraction is optional) |
| No | fraction needs at least one digit after the point |
| No | must start with a digit |
| No | exponent needs digits |
(Real C also accepts 12. and .5; our simplified definition does not. Every language defines its own patterns.) How such definitions are turned into a working recogniser is the subject of Input Buffering & Recognition of Tokens and Lex & Flex.
Two Rules That Resolve Ambiguity
Patterns often overlap. if matches both the keyword pattern and the identifier pattern; <= starts with <, which is itself a token. Lexers use two rules:
Longest match (maximal munch): always take the longest prefix of the remaining input that matches some pattern. So
<=is one token, not<followed by=; andiffyis one identifier, not the keywordiffollowed byfy.Priority: if two patterns match the same longest lexeme, the one listed first (or the keyword) wins. So
ifon its own is the keyword, not an identifier.
Maximal munch is greedy and never looks back to "fix" a choice for the parser. This explains some surprising C behaviour:
a = b+++c; tokens: a = b ++ + c ; (7 tokens, means (b++) + c)
x = a+++++b; tokens: x = a ++ ++ + b ; (8 tokens)
The second line could have been read as a++ + ++b, which is valid, but maximal munch produces a ++ ++ + b, and GCC rejects it with error: lvalue required as increment operand (you cannot apply ++ to the value a++). The lexer does not care that the parser will fail. Writing a++ + ++b with spaces fixes it.
Counting Tokens: Solved Problems
"How many tokens are in this code?" is a GATE and university favourite. The rules:
Whitespace and comments are not tokens.
A whole string literal
"..."is one token, whatever it contains (even%d, commas or&). Same for a character constant like'\n'.Multi-character operators (
>=,++,+=,->,&&) are one token each, by maximal munch.Every keyword, identifier, constant, operator and punctuation mark counts.
Problem 1 (classic)
printf("i = %d, &i = %x", i, &i);
printf | ( | "i = %d, &i = %x" | , | i | , | & | i | ) | ;
1 2 3 4 5 6 7 8 9 10
Answer: 10. The commas and & inside the string are part of the single string token.
Problem 2
int max(int x, int y) { return x > y ? x : y; }
Class | Tokens | Count |
|---|---|---|
Keywords |
| 4 |
Identifiers |
| 7 |
Operators |
| 3 |
Punctuation |
| 6 |
Answer: 20. Every occurrence counts, so x is counted three times in the body.
Problem 3
while(i<=n){sum+=i;i++;}
while ( i <= n ) { sum += i ; i ++ ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Answer: 15. No spaces are needed between tokens; <=, += and ++ are single tokens.
Problem 4 (comments)
int a = 10; /* initial value */ a += 5;
int a = 10 ; gives 5 and a += 5 ; gives 4; the comment gives 0. Answer: 9.
Problem 5 (comment or division?)
x = a /*p;*/ + b; /* line A */
x = a / *p; /* line B */
In line A, /* starts a comment that ends at */, so the code is really x = a + b;: 6 tokens. In line B the space separates / and *, so we get x = a / * p ;: 7 tokens (division by the value pointed to by p). One space changes the meaning completely.
Problem 6 (errors the lexer does not see)
main() { int a = 10; char b = "abc"; in t c = 30; /* comment */ }
Count: main ( ) { = 4, int a = 10 ; = 5, char b = "abc" ; = 5, in t c = 30 ; = 6, } = 1. Answer: 21.
This code has two mistakes, but neither is a lexical error. in and t are valid identifiers (the error appears in syntax analysis), and assigning a string to a char is a type error (semantic analysis). The lexer happily produces 21 tokens.
Problem 7
for (int i = 0; i < 10; i++) printf("%d", i);
for ( int i = 0 ; i < 10 ; i ++ ) printf ( "%d" , i ) ;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Answer: 21.
Lexical Errors and Recovery
The lexer sees only a tiny part of the program at a time, so it can detect only a few kinds of error:
A character that cannot begin any token, e.g.
@or a stray backtick in C. GCC:stray '@' in program.An unterminated string or comment. GCC:
missing terminating " character.A malformed constant, e.g.
2xor9lives. GCC:invalid suffix 'x' on integer constant.An identifier or number that is too long, in languages that set a limit.
A misspelled keyword like fi (a == b) is not a lexical error; fi is a valid identifier, and the problem is found later.
Recovery strategies
Strategy | What it does |
|---|---|
Panic mode | Delete successive characters from the remaining input until the lexer can find a well-formed token again. Simplest and most common. |
Delete one character | Remove the offending character (e.g. drop the |
Insert a character | Insert a missing character (e.g. a closing quote). |
Replace a character | Replace one character by another. |
Transpose | Swap two adjacent characters. |
The goal of recovery is not to guess the programmer's intention perfectly, but to get back on track so that later errors can still be reported in the same compile. A more ambitious strategy looks for the minimum number of such edits that turn the input into valid tokens, but it is rarely used because it is expensive.
Common Mistakes Students Make
Mixing up token and lexeme.
countis a lexeme; id is its token. "How many tokens" means how many lexemes produce tokens, counting repeats.Counting inside string literals.
"a, b"is one token.Splitting multi-character operators.
<=,++,!=,->are single tokens.Counting comments or whitespace. They are discarded.
Calling every mistake in code a lexical error. The lexer only checks that characters form valid words. Misspelled keywords, missing semicolons and type errors are found later.
Forgetting maximal munch.
a+++bisa ++ + b, nevera + ++b.
GATE / Interview Questions
1. Define token, lexeme and pattern with one example.
In sum = 0;, the lexeme sum is an actual character sequence; it matches the pattern "letter followed by letters or digits"; the lexer reports it as the token <id, pointer to sum's entry>.
2. How many tokens are in int main() { int a = 10, b = 20; printf("sum is: %d", a + b); return 0; }?
27. int main ( ) { = 5; int a = 10 , b = 20 ; = 9; printf ( "sum is: %d" , a + b ) ; = 9; return 0 ; } = 4. Total 5 + 9 + 9 + 4 = 27.
3. How many tokens in x = y---z;, and how is it parsed?
7 tokens: x = y -- - z ;. By maximal munch the lexer takes -- first, so the expression means (y--) - z.
4. Why are whitespace and comments removed by the lexer and not by the parser?
Including them in the grammar would make it far more complex, since blanks and comments may appear between any two tokens. Removing them in the lexer keeps the grammar small and the parser simple.
5. Which of these is detected in lexical analysis: (a) int x = 08@; (b) missing semicolon (c) undeclared variable (d) whiel instead of while?
(a), because of the illegal character @. (b) is a syntax error, (c) a semantic error, and (d) is a valid identifier, so it is found later. (Note: 08 is also a lexical-level error in C, since 8 is not an octal digit.)
6. Why do identifiers and numbers carry attribute values but keywords do not?
A keyword token has exactly one possible lexeme, so the token name says everything. Identifiers and numbers have many possible lexemes, and later phases need to know which name (symbol-table pointer) or which value it was.
7. Write a regular definition for identifiers that start with a letter, contain letters, digits and underscores, and cannot end with an underscore.
letter -> [A-Za-z], digit -> [0-9], id -> letter ( (letter | digit | _)* (letter | digit) )?. The optional group lets a single letter be an identifier and forces any longer identifier to end with a letter or digit.
8. What is panic-mode recovery in a lexer?
When no pattern matches the remaining input, the lexer deletes characters one by one from the input until a well-formed token can be found, reports the error, and continues.
Summary
The lexical analyzer turns characters into tokens on demand from the parser, removes whitespace and comments, tracks line numbers and works with the symbol table.
A lexeme is the actual text, a pattern is the rule, and a token is the <name, attribute> pair the parser receives. Identifiers carry a symbol-table pointer, numbers their value.
Patterns are written as regular expressions and regular definitions (union, concatenation, closure, plus
+,?and character classes).Overlaps are resolved by longest match and then priority (keywords before identifiers).
When counting tokens: string literals are one token, multi-character operators are one token, whitespace and comments are none.
printf("i = %d, &i = %x", i, &i);has 10 tokens.Lexical errors are limited to illegal characters, unterminated strings/comments and malformed constants; the usual recovery is panic mode.
Next, Input Buffering & Recognition of Tokens shows how a lexer reads input efficiently with buffer pairs and sentinels, and how token patterns become transition diagrams that can be coded directly.