A compiler turns source text into runnable code through a pipeline of phases, and the very first phase, lexical analysis, is where a stream of characters becomes a stream of meaningful units. Get this phase right and the rest of the compiler has clean input to work with. Miss the vocabulary, tokens versus patterns versus lexemes, and the exam questions all blur together.
Lexical analysis is also the phase that connects compiler design back to theory of computation, because a scanner is a finite automaton in disguise. Let us walk the phases, then build the scanner.
Phases of a compiler at a glance
A compiler is usually described as six phases, with two support structures running alongside all of them:
Lexical analysis (the scanner): characters to tokens.
Syntax analysis (the parser): tokens to a parse tree, checked against the grammar.
Semantic analysis: type checking and scope rules on the tree.
Intermediate code generation: a machine-independent representation.
Code optimization: improving that representation.
Code generation: producing target machine code.
The two support structures are the symbol table, shared by every phase, and the error handler. The first four phases, through intermediate code generation, form the analysis or front end and are machine-independent; code optimization and code generation form the synthesis or the back end. Lexical analysis is the boundary between raw text and structured compilation.
Tokens, patterns and lexemes
These three words are tested constantly and are easy to swap by mistake. Keep them separate:
A token is a category with a name, such as identifier, keyword, number, or operator. It is what the parser consumes.
A pattern is the rule that describes the set of strings a token can match, almost always written as a regular expression.
A lexeme is the actual sequence of characters in the source that matches a pattern.
So in the assignment below, `x` is a lexeme, its token is identifier, and the pattern for identifier is the regular expression for a letter followed by letters or digits. One token category, many possible lexemes, one pattern.
A worked tokenization
Take the line of source code:
`int x = a + 42 ;`
The scanner reads left to right, groups characters into lexemes, discards whitespace, and emits a token for each lexeme:
Lexeme | Token | Attribute |
|---|---|---|
int | keyword | reserved word |
x | identifier | symbol-table entry |
= | operator | assignment |
a | identifier | symbol-table entry |
+ | operator | addition |
42 | number | integer constant |
; | punctuation | statement end |
Notice two things. Keywords like `int` are recognised as their own tokens, not as identifiers, even though they match the identifier pattern, so the scanner checks a reserved-word list. And the identifiers `x` and `a` each get a symbol-table entry whose index becomes the token's attribute. That attribute is how later phases recover the name, type and scope.
Regular expressions to a DFA scanner
Every token pattern is a regular expression, and regular expressions describe exactly the regular languages, the ones a finite automaton can recognise. That is why the scanner can be built mechanically:
Write a regular expression for each token pattern.
Convert each to a nondeterministic finite automaton, typically by Thompson's construction.
Combine and convert to a deterministic finite automaton by subset construction.
Minimize the DFA, and it becomes the transition table that drives the scanner.
Scanner generators such as Lex and Flex automate exactly this path, from your regular-expression rules to a DFA-driven scanner. This is the direct link to theory of computation: the scanner is a DFA, and everything you know about regular languages applies.
Input buffering
Reading the source one character at a time from disk is too slow, and the scanner often needs to look one or two characters ahead to decide where a lexeme ends. For example, on seeing `<` the scanner must peek to tell `<` from `<=`. The standard fix is a two-buffer scheme with a pair of buffers loaded alternately, plus a sentinel character marking each buffer's end so a single test detects both the buffer boundary and the end of input. Two pointers, one at the lexeme's start and one scanning forward, bracket the current lexeme.
The symbol table
The symbol table is the compiler's memory of names. When the scanner meets an identifier, it enters the name into the table, or finds the existing entry, and stores attributes that later phases fill in and read: the identifier's name, type, scope, and eventually its memory location. Because every phase touches it, the symbol table is drawn beside the phase pipeline, not inside it. Efficient lookup, often via a hash table, matters because the scanner and later phases query it constantly.
How lexical analysis is tested in GATE
GATE CS treats compiler design as a full subject, and lexical analysis is its entry point. Expect a definition question separating token, pattern and lexeme, a count of how many tokens a given source line produces, a regular-expression or DFA question tied to a token pattern, and a conceptual question on which task belongs to the scanner versus the parser. Because the scanner is a finite automaton, the same regular-language reasoning from theory of computation transfers directly.
That cross-link is worth using while you revise. Our finite automata deep-dive on DFA versus NFA and the regular expressions and pumping lemma post cover the machinery a scanner is built from, and the Compiler Design learn module sequences the phases in order. To drill this phase, work the tokens and lexical analysis set from previous years.
Practise it, do not just read it
Lexical analysis is confirmed on questions. Learn the phase order, keep token, pattern and lexeme cleanly apart, and tokenize one line of code by hand until it is automatic.
Work the previous-year tokens and lexical analysis set with worked solutions.
For compiler design across the whole GATE CS syllabus, GATE Guidance by Sanchit Sir sequences the phases with theory of computation.
Browse the neighbouring topics in the CS Fundamentals category.
Learn the phases, master the three-way vocabulary, and hand-tokenize one statement. Do that, and the front end of the compiler stops being a blur and becomes reliable marks.
