Lexical analysis looks like easy vocabulary, so students often skim token, lexeme, and pattern. Then a question asks for the token count or an identifier DFA, and that loose understanding fails. Take int count = count + 10;: it yields seven tokens from six distinct spellings, and a comparison written <= yields one token rather than two. Both answers follow from rules a scanner applies mechanically.
Where lexical analysis sits in the compiler
The lexical analyzer, also called the scanner, is the first compiler phase. It reads raw source characters and produces tokens for the parser. The six phases around it, and the symbol table they all share, are laid out in Lexical Analysis in Compiler Design: Tokens, Patterns and Lexemes Explained.
Its main jobs are to:
group characters into lexemes and emit the corresponding tokens;
remove whitespace, tabs, newlines, and comments;
enter identifiers and constants into the symbol table;
track line numbers so later phases can report useful errors.
Macro and include expansion belongs to the preprocessor, not the lexer.
The parser usually calls getNextToken(). The scanner returns one token, remembers its position, and continues on the next call. Lexing is therefore demand-driven in most real compilers.
Tokens, lexemes, and patterns
A pattern is the rule that describes the form of a lexeme. A lexeme is the actual character string matched in the source. A token is the category assigned to that lexeme, often with an attribute.
Token | Sample lexemes | Informal pattern |
|---|---|---|
id |
| letter followed by letters or digits |
num |
| digits with an optional fraction |
relop |
| one of the six comparison forms |
keyword |
| one fixed reserved word |
sep |
| one punctuation symbol |
Consider this input:
int count = count + 10;Scan it from left to right:
intbecomes a keyword token.The first
countbecomes an id token.=becomes an assignment-operator token.The second
countbecomes another id token.+becomes an arithmetic-operator token.10becomes a num token.;becomes a separator token.
The answer is 7 tokens but only 6 distinct lexeme spellings because count occurs twice. Both id-token instances point to the same symbol-table entry, entry 1. The figure above shows that stream leaving the scanner, with whitespace already discarded.
Specifying tokens with regular expressions
A scanner needs precise token definitions, and regular expressions supply them. Every token pattern in a scanner is a regular expression over the source character set.
Standard regular definitions are:
letter -> A | B | ... | Z | a | ... | z | _
digit -> 0 | 1 | ... | 9
id -> letter ( letter | digit )*
num -> digit+ ( . digit+ )? ( E ( + | - )? digit+ )?count matches id: c is a letter, and the rest satisfy (letter | digit)*. 10 matches num through digit+; 3.14 also uses the optional fraction. 2x fails id because it begins with a digit.
Token structures need no nesting or recursion, so finite-state machines can recognise them. The parser handles recursive structure later.
How a scanner moves from a regular expression to a DFA
The pipeline is regular expression to NFA by Thompson's construction, NFA to DFA by subset construction, then a minimised DFA or transition table. Finite Automata: DFA vs NFA and Subset Construction covers that machinery. The separate token patterns are joined by alternation first, so one DFA recognises every token class in a single left-to-right pass, and each accepting state is tagged with the token it reports.
For an identifier, a letter moves State 0 to State 1. In State 1, each letter or digit loops to State 1. Any other character moves to accepting State 2.
The other character belongs to the next token, so the scanner retracts it. Trace count , including the trailing space:
0 -c-> 1 -o-> 1 -u-> 1 -n-> 1 -t-> 1 -space-> 2*It emits <id, count> and pushes back the space. A classic relop recogniser similarly distinguishes <, <=, <>, =, >, and >=.
Longest match, lookahead, and input buffering
The longest-match, or maximal-munch, rule takes the longest valid lexeme. For equal-length matches, the earlier pattern wins. Keywords get priority or are checked in a reserved-word table.
Three small inputs expose the rule:
For
<=, the scanner does not return<immediately. It reads=and returns one<=token.iffis one identifier, not keywordiffollowed by identifierf.10.5is one num token, not10,., and5as three tokens.
Lookahead finds the longest match, and retraction corrects overshooting. Efficient scanners use two buffer halves of size N, each ending in a sentinel. lexemeBegin indicates the lexeme start; forward searches for its end.
Counting tokens and recognising phase boundaries
For token counts, whitespace and comments are ignored, a whole string literal is one token, and punctuation stays separate unless longest match forms one operator.
Now scan:
printf("Total = %d", count);The tokens are:
printf, id(, punctuation"Total = %d", one string-literal token,, commacount, id), punctuation;, semicolon
The answer is 7 tokens. The spaces, =, and %d inside the quotes are characters within one string lexeme, not separate tokens.
A lexer cannot detect undeclared or type-mismatched variables, which belong to semantic analysis. Nor can it detect unbalanced parentheses or invalid statement structure, which belong to parsing. It tokenises fi (a == b) because fi is a valid identifier; the parser later rejects the intended statement.
A lexical error means no pattern matches. Examples include a stray @ or # in C, or 2x when no rule accepts a number running into a letter.
How GATE and interviews test lexical analysis
Typical questions cover token counts, token versus lexeme versus pattern, DFAs for id, num, or relop, longest match, lexical versus syntax errors, and symbol-table updates. Two slips cost most of the marks in the counting ones: reading <= or >= as two tokens each, and counting the characters inside a string literal separately.
Interviews ask: How would you tokenise an expression? Why can regular expressions describe tokens but not balanced parentheses? Finite automata handle regular forms; parsers handle recursive grammar.
The official GATE Computer Science and Information Technology syllabus lists Compiler Design with lexical analysis, parsing, and syntax-directed translation. Place it among the other core areas in GATE CS Subject Weightage, and use the current official syllabus when planning.
The short version and your next step
A lexer turns source characters into tokens for the parser.
A pattern is the rule, a lexeme is the matched string, and a token is its category.
Token recognisers are DFAs built from regular expressions.
Longest match, lookahead, and retraction decide ambiguous token boundaries.
The lexer recognises words, but it cannot validate program meaning or recursive structure.
For the full compiler sequence, work through the Compiler Design module in GATE Guidance by Sanchit Sir. For placement interviews, use CS Fundamentals for Placements by Sanchit Sir. Keep the GATE CS Subject Weightage beside your plan for the remaining subjects.
