Parse tree

A parse tree shows one syntactic derivation of a string under a formal grammar. In a context-free grammar, each internal node is labeled by a nonterminal, and its children are the symbols on the right-hand side of the production used to expand that nonterminal; the root is the start symbol. Reading the terminal leaves from left to right yields the derived string, a property called the tree’s frontier or yield.¹ The order of children matters because ordinary grammars describe ordered strings, not merely collections of symbols. A tree may also contain an empty-string leaf when a production derives ε. The hierarchy records relationships that a flat token sequence cannot show, such as which expression forms the operand of an operator.

Parsing constructs or recognizes a parse tree by applying grammar productions to an input string. A top-down parser begins with the start symbol and predicts expansions until the leaves match the input, whereas a bottom-up parser begins with input fragments and combines them into larger constituents until it reaches the start symbol.² Algorithms differ in how they store this information: recursive-descent implementations may represent it with recursive calls, while chart parsers keep partial constituents and shared substructures. Shift-reduce parsers used in LR-family tools record states and reductions; each reduction corresponds to applying a production and can create a parent node.³ A successful parse establishes membership in the grammar’s language, while failure identifies an input that the grammar does not derive.

A grammar is ambiguous when at least one string has two distinct parse trees. Arithmetic expressions provide the standard example: without precedence and associativity rules, a string such as a + b × c can admit competing structures, and repeated subtraction can be grouped in different ways.¹ Parser specifications resolve such cases through grammar rewriting, precedence declarations, or explicit disambiguation policies. Compilers commonly transform a concrete parse tree into an abstract syntax tree, which omits punctuation and grammar-only nodes while retaining the structure needed for semantic analysis and code generation. The two structures should not be conflated: a parse tree explains how the grammar produced the text, whereas an abstract syntax tree represents the program’s essential meaning more compactly.

Parse trees apply beyond programming-language syntax. They are central to natural-language parsing, mathematical notation, protocol descriptions, and proofs about formal languages. A grammar can be unambiguous yet still produce trees with substantial redundant detail; conversely, an ambiguous grammar may be useful when later context selects an interpretation. General context-free parsers, including Earley’s algorithm, can represent all parses rather than committing immediately to one tree, making them useful for ambiguous or highly variable grammars.⁴ Some implementations use packed parse forests, which share identical subtrees among many possible parses and avoid storing every tree separately. Parse trees also support error reporting: the parser can identify the expected syntactic categories near a point where no valid continuation exists, although the quality of that diagnosis depends on the grammar and recovery strategy.

Nonterminal

A grammar symbol that can be expanded by one or more production rules.

Terminal

A symbol that appears in the derived string and is not further expanded by the grammar.

Yield

The left-to-right sequence of terminal leaves produced by a parse tree.

Abstract syntax tree

A simplified structural representation that removes grammar-specific detail while preserving relevant program structure.