Parsing

Parsing determines whether a sequence of symbols conforms to a grammar and, if it does, how those symbols are organized. A grammar normally specifies terminals, nonterminals, production rules, and a start symbol; the parser applies those rules to an input such as source code, a mathematical expression, or a database query. The result may be a concrete parse tree that preserves every grammatical detail or an abstract syntax tree (AST) that retains the structure needed for later processing.

Parsing is distinct from tokenization, although the two are commonly adjacent. A lexer groups characters into tokens such as identifiers, numbers, and punctuation; a parser consumes those tokens and checks their relationships. In a compiler, parsing generally follows lexical analysis and precedes semantic analysis, optimization, and code generation. A syntactically valid program can still fail later because names, types, or control-flow constraints are invalid.

Formal grammars also make parsing precise. Context-free grammars are especially important because they can describe recursively nested constructions, including parentheses, blocks, expressions, and many programming-language constructs.¹

A parser builds structure by selecting grammar productions while advancing through the input. For an expression such as a + b * c, the grammar must encode precedence and associativity so that multiplication binds more tightly than addition. The resulting AST commonly represents the expression as addition whose right child is a multiplication node, rather than as a flat list of tokens.

Top-down parsers begin with the start symbol and predict which productions could generate the input. Recursive-descent parsing is a readable top-down technique in which grammar rules are represented by mutually calling procedures; LL parsers make related decisions from the left edge of the input. Bottom-up parsers instead begin with input fragments and repeatedly reduce them to larger grammatical units. LR, LALR, and related shift-reduce methods are widely used for programming languages because they can handle substantial classes of grammars while detecting errors near the point where the grammar can no longer be continued.²

Ambiguity occurs when one input has more than one valid parse tree. Parser designers resolve it by rewriting the grammar, imposing precedence rules, or adopting a documented disambiguation policy.

Parsing algorithms trade generality, speed, memory use, and implementation complexity. For a broad class of context-free grammars, the Cocke–Younger–Kasami algorithm uses dynamic programming and has a classic cubic worst-case time bound in the length of the input, although practical grammars and optimized implementations can behave much better. Earley's algorithm likewise supports general context-free grammars and is useful when the grammar is difficult to restrict to LL or LR form.

Parser generators automate much of the construction. A grammar author supplies productions and, often, precedence declarations; the tool emits a parser or parsing tables. Yacc and GNU Bison are associated with LALR and related bottom-up techniques, while ANTLR generates parsers using adaptive LL methods. These tools can expose conflicts: a shift/reduce conflict means the parser can either consume another token or reduce a recognized phrase, whereas a reduce/reduce conflict presents competing reductions. Such conflicts may reveal genuine ambiguity or an incomplete grammar design.

Hand-written parsers remain common when excellent diagnostics, unusual syntax, incremental editing, or tight integration with semantic actions matters more than automatic generation.

Useful parsing systems do more than accept or reject input: they explain errors and continue far enough to report additional problems. A parser can report a missing delimiter, an unexpected token, or an incomplete construct, often including a source location and a small excerpt of surrounding text. Error quality depends on both the grammar and the recovery strategy.

Common recovery methods include panic-mode recovery, which skips tokens until a synchronization point such as a semicolon or closing brace; phrase-level recovery, which inserts, deletes, or replaces a small number of tokens; and grammar productions designed specifically for common mistakes. Recovery must be conservative: an incorrect repair can cause a cascade of misleading diagnostics. Compiler front ends therefore often separate syntax recovery from later semantic checks.

Modern editors add another constraint: parsing may occur repeatedly while the user is typing, with incomplete or temporarily invalid input. Incremental parsers reuse unaffected portions of an earlier tree, while error-tolerant and concrete-syntax-tree systems preserve comments, whitespace, and exact source ranges for formatting, refactoring, syntax highlighting, and language-server features.

Parsing is not limited to compiler front ends; it is also a boundary between formal language design and real-world data exchange. Query languages, configuration formats, markup languages, network protocols, and natural-language tools all rely on parsing, but they differ in how strictly they define valid input and how they treat extensions.

Scannerless parsing removes a separate lexer and lets the grammar operate directly on characters or other low-level symbols. Generalized parsers can preserve multiple possible interpretations instead of forcing an early choice, which is useful for ambiguous or evolving languages. GLR parsing, for example, can pursue several alternatives and later merge or discard them. Packrat parsing applies memoization to certain top-down approaches, offering predictable linear-time behavior for suitable parsing-expression grammars at the cost of potentially high memory consumption.

Security considerations are easy to overlook. A parser may be exposed to deeply nested or deliberately pathological input that causes excessive CPU or memory use. Robust implementations impose limits on nesting, input size, recursion, and resource consumption, and they treat parsing as an input-validation boundary rather than assuming that syntactically well-formed data is trustworthy.

Abstract syntax tree

A simplified tree representing the meaningful structure of an input while omitting many surface details such as punctuation.

Context-free grammar

A formal grammar whose production rules replace one nonterminal with a sequence of terminals and nonterminals.

Lexer

A component that converts characters into tokens before or during parsing.

Shift-reduce parsing

A bottom-up method that shifts input tokens onto a stack and reduces recognized sequences according to grammar rules.

Ambiguity

A property of a grammar in which one input can have more than one valid parse tree.

Packrat parsing

A memoized parsing technique that can provide linear-time behavior for suitable parsing-expression grammars.