Lexical analysis

• 1. Cutting Up Text

  ›

  Lexical analysis, also called lexical tokenization, starts with a puzzle hidden inside a sentence everyone knows. Take The quick brown fox jumps over the lazy dog. A person sees nine words at once. A program sees only a run of 43 characters. It does not split the string on spaces by itself. Someone must tell it explicitly to cut the input into 9 tokens, using a space as the delimiter. That small act is how raw text becomes something a machine can sort, label and pass along. Behind it sit a few questions. What exactly is a token, and how does it differ from a lexeme? How does a program decide where one token ends and the next begins? Why do some lexers add punctuation that nobody typed? And which kinds of writing still resist the simplest approach?

  1

• 2. Tokens and Lexemes

  ›

  A lexical token has two parts: a token name and an optional token value. Linguists would recognize the token name as something like a part of speech. In a natural language, a lexer's categories include nouns, verbs, adjectives and punctuation marks. In a programming language, the common categories are identifier, keyword, separator or punctuator, operator, literal, comment and whitespace.

  Identifiers are names assigned by the programmer, and keywords are words reserved by the language. Separators cover punctuation characters and paired delimiters. Operators are symbols that act on arguments and produce results. Literals are numeric, logical, textual and reference values. Comments and whitespace are usually discarded.

  When a lexer hands tokens to a parser, it typically labels them with an enumerated type, which is a list of number representations. Identifier might be 0, Assignment operator 1 and Addition operator 2.

  The word lexeme hides a trap for anyone crossing between fields. In rule-based natural language processing, a lexeme is not the same thing that linguists call a lexeme. The two match only in analytic languages such as English, and not in highly synthetic languages such as fusional ones. The programmer's lexeme is closer to a linguist's word, and occasionally closer to a morpheme. Neither should be confused with a word in computer architecture.

  Large language models use a cousin of this idea, with two differences. A lexical tokenizer usually follows a lexical grammar, while an LLM tokenizer is usually probability-based. The LLM tokenizer also takes a second step that converts its tokens into numerical values.

  When one token class can stand for many different lexemes, the lexer often keeps enough information to rebuild the original lexeme. That matters because a number may also be a valid identifier. The parser typically retrieves the retained detail and stores it in the abstract syntax tree, so nothing is lost.

  12

• 3. Scanner and Evaluator

  ›

  The lexer forms the first phase of a compiler frontend, and its analysis generally happens in a single pass. Compilers are the usual customers for lexers and parsers. The same machinery also serves other language tools, such as prettyprinters and linters. Inside the lexer, the work divides into two stages.

  The scanner comes first, and it is usually built on a finite-state machine. That machine encodes which sequences of characters can appear inside each kind of token. An integer lexeme, for example, may be any sequence of digit characters. Often the first non-whitespace character reveals what kind of token is coming. The scanner then reads one character at a time until it meets a character that does not belong. This is called the maximal munch, or longest match, rule.

  Some languages make this harder and force the scanner to backtrack over characters it has already read. In C, a single letter L is not enough to tell an identifier that begins with L from a wide-character string literal.

  The evaluator is the second stage. A lexeme at this point is only a string known to be of a certain kind. The evaluator goes over its characters and produces a value holding what the parser needs. The lexeme's type combined with that value is what properly makes a token.

  Values vary by kind. An identifier token often just carries the characters of its lexeme. Keywords and special characters usually omit the value, because the type says everything. An integer literal may pass along as a string, or the evaluator may compute the number. A simple quoted string needs only its quotes removed, while an escaped string also needs its escape sequences unescaped. The evaluator may even suppress a lexeme entirely, hiding it from the parser.

  A line of source code could become a stream beginning with IDENTIFIER "net_worth_future", then EQUALS and OPEN_PARENTHESIS. Next come IDENTIFIER "assets", MINUS and IDENTIFIER "liabilities", then CLOSE_PARENTHESIS and SEMICOLON. If the lexer meets an invalid token, it reports an error. After tokenizing comes parsing.

  125

• 4. Lexical Grammar

  ›

  In the 1960s, compilers for ALGOL stripped whitespace and comments out in a separate line reconstruction phase. That phase was the initial step of the compiler frontend. It has since been eliminated, and the lexer now handles those jobs.

  A language specification often includes a lexical grammar, a set of rules defining the lexical syntax. The lexical syntax is usually a regular language, with rules written as regular expressions. Each expression defines the possible character sequences, the lexemes, for one kind of token. For each kind of string it finds, the lexer takes an action, most simply producing a token.

  Whitespace and comments are two important categories in that grammar. They may produce no tokens at all, and at most they separate two tokens, as in if x instead of ifx. There are two important exceptions. In off-side rule languages, which delimit blocks with indentation, the initial whitespace is significant because it determines block structure. And some tools need the original text. A prettyprinter must output the comments, and some debugging tools show the programmer the original source code.

  A lexical analyzer generally does nothing with combinations of tokens. It recognizes parentheses as tokens, but does not check that each opening one is matched with a closing one. Regular expressions and their finite-state machines cannot handle recursive patterns, such as n opening parentheses, then a statement, then n closing parentheses. They cannot keep count and verify that n is the same on both sides, unless only a finite set of values is allowed. Recognizing such patterns in general takes a full parser, which can push parentheses onto a stack and pop them off, then check that the stack ends empty. The book Structure and Interpretation of Computer Programs gives an example of this technique.

  2310

• 5. Lexer Generators

  ›

  The most established lexer generator is lex, which is paired with the yacc parser generator. Many reimplementations exist, such as flex, which is often paired with GNU Bison. These tools are a form of domain-specific language. They take a lexical specification, generally regular expressions with some markup, and emit a lexer.

  Each regular expression is attached to a production rule in the language's lexical grammar. For an English-based language, an identifier might be any letter a-z, A-Z or an underscore, followed by zero or more of a-z, A-Z, underscore or 0-9. A generator may produce source code to compile and run. Alternatively it may build a state transition table for a finite-state machine, which is plugged into template code.

  Hand-writing a lexer is practical when the list of tokens is small. For a larger number of potential tokens, automated tooling is more practical. Generators give very fast development, which matters in the early days of a language, when the specification may change often. They also offer advanced features, such as pre- and post-conditions, that are hard to program by hand. The cost is flexibility. A generated lexer may need manual modification, or may have to be rewritten entirely by hand.

  Performance matters most in stable languages where the lexer runs very often, such as C or HTML. Lexers generated by lex and flex are reasonably fast, but improvements of two to three times are possible with more tuned generators. The lex and flex family uses a table-driven approach, which is much less efficient than direct coding. With direct coding, the generator produces an engine that jumps straight to the next state using goto statements. Tools like re2c have proven to produce engines between two and three times faster than flex. Modern generators beat most hand-coded lexers, and it is difficult to hand-write one that outperforms re2c.

  5

• 6. Phrase Structure

  ›

  In bash, other shell scripts and Python, ending a line with a backslash immediately followed by a newline continues the statement onto the next line. This line continuation is generally done in the lexer. The backslash and newline are discarded, instead of the newline being turned into a token.

  Semicolon insertion works in the opposite direction. Many languages use the semicolon as a statement terminator, and in some it is optional in many contexts. The lexer then outputs a semicolon into the token stream even though none appears in the input. BCPL and its distant descendant Go have this feature, while B and C do not. JavaScript has it too, but its rules are somewhat complex and much criticized. To avoid bugs, some programmers recommend always writing semicolons. Others begin potentially ambiguous statements with a defensive semicolon. Optional terminators or separators are sometimes handled by the parser instead, notably for trailing commas or semicolons.

  The two features are complementary. Line continuation prevents a token from being generated, even though newlines generally do generate tokens. Semicolon insertion adds a token, even though newlines generally do not.

  Python handles blocks through the off-side rule, implemented in the lexer. When the indenting increases, the lexer emits an INDENT token. When it decreases, the lexer emits one or more DEDENT tokens. These stand in for the opening brace and closing brace of languages that use braces, so the phrase grammar does not care which style is used. To do this, the lexer must hold state, namely a stack of indent levels. That memory of earlier lines means the lexical grammar is no longer context-free.

  68910

• 7. Context-Sensitive Lexing

  ›

  Go's semicolon insertion has to look back exactly one token. That makes it one of the exceptions to a general rule. Lexical grammars are usually context-free, or nearly so, so they need no looking back, looking ahead or backtracking. This allows a simple, clean and efficient implementation. It also keeps communication one-way, from lexer to parser, with no information flowing back.

  Python's concatenation of consecutive string literals is another exception. The lexer must hold one token in a buffer before emitting it, to see whether the next token is also a string literal. These examples need only lexical context. They complicate the lexer somewhat, but they stay invisible to the parser and later phases.

  The lexer hack in C is a harder case. Typedef names and variable names look identical, yet they belong to different token classes. The class of a sequence of characters cannot be settled until the semantic analysis phase. So in the hack, the lexer calls the semantic analyzer, such as the symbol table, and checks whether the sequence needs to be a typedef name. Information must therefore flow back from the semantic analyzer to the lexer, not only from the parser. That complicates the design of the whole system.

  789

• 8. Where Words Break

  ›

  The phrase New York-based shows how slippery the idea of a word can be. A naive tokenizer breaks it at the space, though the better break is arguably at the hyphen. Typically, lexical tokenization occurs at the word level, but it is sometimes hard to say what a word is. Tokenizers often rely on simple heuristics. Punctuation and whitespace may or may not be included in the result. Contiguous strings of alphabetic characters form one token, and so do numbers. Whitespace or punctuation separates tokens.

  Languages that put spaces between words, such as most that use the Latin alphabet and most programming languages, make this fairly straightforward. Even there, edge cases abound, including contractions, hyphenated words, emoticons and larger constructs such as URIs, which for some purposes count as single tokens.

  The trouble grows in languages written in scriptio continua, which show no word boundaries at all. Ancient Greek, Chinese and Thai are examples. Agglutinative languages, such as Korean, also complicate tokenization.

  There are ways to attack the harder problems. One is to develop more complex heuristics. Another is to query a table of common special cases. A third is to fit the tokens to a language model that identifies collocations in a later processing step.

  14