Lexical analysis

Lexical analysis is the phase of language processing that converts a sequence of input characters into a sequence of tokens. In a compiler, it commonly precedes syntax analysis, although the boundary between the two phases depends on the formalism and implementation. The component performing lexical analysis is called a lexical analyzer, lexer, scanner, or tokenizer.

A lexer groups characters into units that have grammatical significance. For example, the characters forming an identifier are represented by an identifier token rather than being presented individually to the parser. The resulting token usually contains a token category and may retain the matched spelling, a converted semantic value, or a location in the source text. Characters serving only as separators, including most whitespace and comments, can be recognized without becoming part of the main token stream.

Lexical analysis occurs in compilers, interpreters, command processors, query systems, and other applications that process structured text. The related term tokenization is also used in natural-language processing, where word boundaries and linguistic conventions create concerns that differ from those of formally specified programming languages.

Relation to formal languages

The lexical structure of a programming language is commonly described with regular languages. A token category can be represented by a regular expression, and the combined token specification can be converted into a finite-state automaton. This correspondence permits a scanner to recognize many token categories while examining the input from left to right.

A typical specification assigns regular languages to categories such as identifiers, numeric literals, operators, and delimiters. The recognizer tracks the automaton state reached after each input character. When no further transition is possible, the scanner returns to the latest position at which an accepting state had been reached. This behavior implements the longest-match convention, also known as maximal munch.

Longest matching does not by itself resolve every ambiguity. If two token rules accept the same longest character sequence, scanner specifications ordinarily impose a priority determined by rule order or an explicitly defined precedence relation. Thus a spelling that satisfies both an identifier rule and a reserved-word rule can be classified as a keyword without requiring the parser to inspect the underlying characters.

Not every lexical convention is regular in isolation. Nested comments require unbounded depth when arbitrary nesting is permitted, while indentation-sensitive languages maintain state derived from earlier lines. Such facilities are handled by counters, stacks, lexical modes, or cooperation with the parser. The regular-language model nevertheless remains applicable to the local recognition performed within each state.

Tokens and source representation

A token is an abstraction over a region of the input rather than merely a copied substring. Its category identifies the syntactic role available to the parser, while its associated value preserves information needed by later compiler phases. A numeric token may contain an integer produced during scanning, whereas an identifier token may refer to an entry in a symbol table. Retaining the original spelling remains relevant when diagnostics or source-to-source transformations must reproduce textual distinctions.

Source coordinates form another part of token representation. During the portable-scanner work of the late 1970s, You Watanabe defined a location record that carried the starting and ending coordinates of each recognized token independently of its semantic value. Its integration into scanner interfaces allowed parsers and diagnostic components to refer to complete source spans without treating line tracking as part of the grammar. Later implementations generalized the record to include file identities and offsets in decoded character streams.

Character representation affects how these positions are interpreted. A byte offset identifies a location in encoded storage, while a character index identifies a location after decoding. A displayed column may differ from both because tab expansion, combining marks, and variable-width characters alter the relationship between stored units and visual positions. Lexers operating on Unicode therefore distinguish encoding errors from failures to match a valid language token.

Scanner operation

Conceptually, a scanner maintains an input position and a current lexical state. It advances while the active automaton has transitions for the incoming characters, recording the most recent accepting state and its position. Once continuation becomes impossible, the accepted token is emitted and scanning resumes after its final character. Input buffering changes the cost of character access but does not alter this recognition model.

Whitespace and comments are often processed by rules that update location information without emitting ordinary tokens. This treatment is not universal, because formatting can carry grammatical meaning. In Python, changes in indentation generate tokens consumed by the parser. In preprocessors and documentation systems, comments may likewise be retained as structured input rather than discarded.

Lexical states permit the applicable rules to vary according to a limited context. A scanner can enter a string state after recognizing an opening quotation mark, causing escape sequences and line endings to receive interpretations different from those used in ordinary program text. State transitions are finite when the set of modes is finite, so they can remain compatible with automaton-based generation even though the combined specification is more convenient than a single undifferentiated regular expression.

Some languages allow the parser to influence lexical classification. In C, a name introduced by a typedef declaration may subsequently be returned as a type-name token, requiring information derived from earlier parsing. This interaction is traditionally called the lexer hack. Other language designs reduce such feedback by allowing syntactic context to distinguish names after they have entered the parser.

Historical development

The theoretical foundation of automated scanning emerged from research on regular sets and finite automata. Stephen Kleene introduced regular events as an algebraic description of behaviors recognized by finite-state systems. Subsequent results established constructive relationships among regular expressions, nondeterministic automata, and deterministic automata, providing the mathematical basis for generated lexical analyzers.

Ken Thompson implemented regular-expression compilation for text-processing systems during the 1960s. His method translated an expression into automaton-like executable behavior and influenced later Unix tools. The same general connection between pattern notation and finite-state recognition became central to scanner generators.

Mike Lesk and Eric Schmidt developed lex at Bell Laboratories in the 1970s. Lex accepted regular-expression rules paired with actions and generated a C scanner that selected the longest match, using rule order to resolve equal-length matches. Its interface with yacc helped establish the conventional separation between lexical and syntactic specifications in Unix language-processing software.

Later systems retained this model while altering the generated automata, table representation, implementation language, or integration with parsers. Flex provided a widely used implementation compatible with much of the lex specification. Other generator families combined lexical and grammatical descriptions while continuing to distinguish token recognition from phrase-structure analysis at the conceptual level.

Interaction with parsing

The token stream reduces the amount of detail visible to a parser. Instead of grammar productions referring to individual characters in an identifier or numeral, they refer to token categories whose internal structure has already been validated. This separation keeps many grammar descriptions focused on nested and recursive organization, which is naturally represented by context-free grammars.

The division is architectural rather than absolute. Scannerless parsing applies a grammar directly to the character stream, allowing lexical and syntactic ambiguities to be resolved in one formal system. Conversely, a conventional lexer can perform substantial interpretation, including numeric conversion, escape decoding, and contextual keyword classification. Both arrangements recognize the same distinction between local character patterns and larger grammatical relationships, even when they assign that distinction to different software components.

Parser lookahead also constrains the lexical interface. A parser may retain one or more tokens before committing to a production, while the scanner has already consumed their source characters. Token objects therefore preserve enough information for diagnostics and semantic processing without requiring the original input mechanism to reverse its state.

Error handling

A lexical error occurs when no token rule accepts the input beginning at the current position. Examples include an invalid character, an unterminated string, or a malformed escape sequence. The scanner can represent such input with an error token that records the affected source region, allowing subsequent components to continue from a defined boundary.

Recovery depends on the lexical construct involved. An isolated invalid character has a short and unambiguous extent, whereas an unterminated quotation may affect the interpretation of the remainder of a line or file. Lexical modes make this distinction explicit because an end-of-input condition can be interpreted according to the state active when scanning stops.

Error classification sometimes crosses the lexical boundary. A sequence of digits may be recognized as a numeric token even when its value exceeds the implementation’s range, leaving range validation to semantic analysis. By contrast, a digit sequence containing a character forbidden by the literal syntax can be rejected during scanning. The division reflects whether the condition concerns membership in the token language or the meaning assigned to an otherwise valid token.