Lexical analysis
In 1960, the ALGOL programming language eliminated whitespace and comments during its initial compilation phase. This decision marked a shift in how early compilers handled raw text input. Lexical tokenization converts character sequences into meaningful tokens within computer science. A lexer program defines categories such as identifiers, operators, grouping symbols, and data types. These tokens form the building blocks for further processing stages like parsing or semantic analysis. The process transforms raw strings into structured units that machines can interpret. For example, the string "The quick brown fox jumps over the lazy dog" contains 43 characters but yields only nine distinct tokens when split by spaces. Each token carries an assigned meaning based on predefined rules. In natural languages, these categories include nouns, verbs, adjectives, and punctuation marks. Programming languages use similar logic to identify reserved words, numeric literals, and symbolic operators. Tokens are often represented as enumerated types where each category maps to a number. An identifier might be zero while an addition operator becomes two. This mapping allows parsers to work with simple numerical values instead of complex character streams.
A finite-state machine processes input one character at a time until it reaches a boundary defined by acceptable characters. This first stage is called scanning and produces lexemes from continuous character streams. Consider the C programming language where a single 'L' prefix cannot distinguish between an identifier starting with L and a wide-character string literal. The scanner must examine subsequent characters before making a final decision. Once a lexeme is identified, the second stage evaluates its value for downstream use. An evaluator converts raw text into processed data such as numeric values or stripped quotes. For instance, a quoted string literal may have its surrounding quotation marks removed during evaluation. Integer literals can either pass through unchanged or be converted directly into numbers depending on compiler design choices. Some evaluators suppress entire lexemes like whitespace or comments entirely since they carry no semantic weight for most compilers. A typical token stream might list IDENTIFIER followed by "net_worth_future" then EQUALS and OPEN_PARENTHESIS. Each line represents a distinct unit passed forward to syntactic analysis. The maximal munch rule ensures scanners consume the longest possible sequence matching valid patterns before stopping. Backtracking becomes necessary when rules involve recursive structures that simple state machines cannot handle alone. Finite automata lack the ability to count nested parentheses across arbitrary depths without external help.
The lex tool paired with yacc parser generator emerged in the 1970s as a standard approach for building lexical analyzers. These tools accept regular expressions describing allowed input sequences and emit executable source code automatically. Developers gain rapid development cycles especially during early stages where language specifications change frequently. Hand-written lexers remain practical only when token lists stay small enough to manage manually. Modern generators produce engines using table-driven approaches which jump between states via goto statements. Tools like re2c generate faster engines than flex by optimizing these transitions directly. Performance improvements of two to three times are achievable through tuned generation techniques compared to older methods. Automatically generated lexers sometimes lack flexibility requiring manual adjustments for advanced features. Pre- and post-condition handling proves difficult to implement by hand but comes naturally with automated systems. Stable languages such as C or HTML run their lexers repeatedly making speed optimizations critical. Most modern lexer generators outperform most hand-coded versions despite historical assumptions about control. The tradeoff involves balancing ease of creation against runtime efficiency needs. Complex grammars benefit from automation while niche requirements may demand custom solutions. A balance exists between developer productivity and execution performance depending on project constraints.
Python implements block structure through indentation levels rather than explicit braces like curly brackets. Increasing indent triggers an INDENT token emission while decreasing indent produces DEDENT tokens. This mechanism requires the lexer to maintain a stack tracking current indentation depth dynamically. Line continuation features allow backslash characters followed immediately by newlines to join adjacent lines into single logical units. Bash scripts and Python both discard the backslash-newline pair during scanning instead of treating them as separate tokens. Semicolon insertion adds missing statement terminators automatically when they appear absent in source code. JavaScript uses this feature though its rules remain complex enough that developers often add defensive semicolons manually. Go language inherits optional semicolon behavior from BCPL yet omits it entirely compared to B or C variants. These context-sensitive behaviors force lexers to hold state beyond simple character matching. Information flows backward from semantic analysis phases back to the lexer itself in advanced cases. The C programming language exemplifies this complexity where typedef names and variable names share identical lexical forms until later stages resolve ambiguity. Such scenarios require communication channels extending beyond standard one-way data flow between components.
Ancient Greek, Chinese, and Thai languages exhibit no explicit word boundaries within written text. Tokenization becomes particularly difficult for these scriptio continua systems lacking spaces between words. Agglutinative languages like Korean further complicate segmentation tasks due to morphological richness. Naive tokenizers relying on whitespace delimiters fail completely without additional heuristics or models. Developers address these challenges by developing more sophisticated algorithms querying tables of common special cases. Language models identify collocations during subsequent processing steps to infer correct breaks. Regular expressions alone cannot handle recursive patterns requiring full parsers with stack-based counting capabilities. Some approaches fit tokens into probabilistic frameworks identifying likely groupings based on training data. Edge cases abound even within space-separated languages including contractions hyphenated compounds emoticons and URIs. A phrase like "New York-based" illustrates how naive splitting at spaces creates incorrect units compared to hyphen-aware alternatives. These difficulties highlight limitations inherent in rule-based segmentation strategies when applied globally across diverse linguistic traditions.
Common questions
What year did the ALGOL programming language eliminate whitespace and comments during compilation?
The ALGOL programming language eliminated whitespace and comments in 1960. This decision marked a shift in how early compilers handled raw text input.
How does a finite-state machine process input for lexical analysis?
A finite-state machine processes input one character at a time until it reaches a boundary defined by acceptable characters. This first stage is called scanning and produces lexemes from continuous character streams.
When did the lex tool paired with yacc parser generator emerge as a standard approach?
The lex tool paired with yacc parser generator emerged in the 1970s as a standard approach for building lexical analyzers. These tools accept regular expressions describing allowed input sequences and emit executable source code automatically.
Why do Python and Bash scripts handle backslash-newline pairs differently than other languages?
Python and Bash scripts discard the backslash-newline pair during scanning instead of treating them as separate tokens. Line continuation features allow these characters to join adjacent lines into single logical units.
Which ancient languages exhibit no explicit word boundaries within written text?
Ancient Greek, Chinese, and Thai languages exhibit no explicit word boundaries within written text. Tokenization becomes particularly difficult for these scriptio continua systems lacking spaces between words.
All sources
10 references cited across the entry
- 5journalRE2C: A more versatile scanner generatorP. Bumbulis et al. — Mar–Dec 1993
- 8inlineEffective Go, "Semicolons"