Top-down parsing

Top-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Top-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top-down parsing strategy.

Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis. It occurs in the analysis of both natural languages and computer languages.

Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for parse-trees using a top-down expansion of the given formal grammar rules. Inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules.

Simple implementations of top-down parsing do not terminate for left-recursive grammars, and top-down parsing with backtracking may have exponential time complexity with respect to the length of the input for ambiguous CFGs. However, more sophisticated top-down parsers have been created by Frost, Hafiz, and Callaghan, which do accommodate ambiguity and left recursion in polynomial time and which generate polynomial-sized representations of the potentially exponential number of parse trees.

Programming language application

A compiler parses input from a programming language to an internal representation by matching the incoming symbols to production rules. Production rules are commonly defined using Backus–Naur form.

An LL parser is a type of parser that does top-down parsing by applying each production rule to the incoming symbols, working from the left-most symbol yielded on a production rule and then proceeding to the next production rule for each non-terminal symbol encountered. In this way the parsing starts on the Left of the result side (right side) of the production rule and evaluates non-terminals from the Left first and, thus, proceeds down the parse tree for each new non-terminal before continuing to the next symbol for a production rule.

For example: A \rightarrow aBC B \rightarrow c \mid cd C \rightarrow df \mid eg which produces the string A=acdf would match A \rightarrow aBC and attempt to match B \rightarrow c \mid cd next. Then C \rightarrow df \mid eg would be tried. As one may expect, some languages are more ambiguous than others.

For a non-ambiguous language, in which all productions for a non-terminal produce distinct strings, the string produced by one production will not start with the same symbol as the string produced by another production. A non-ambiguous language may be parsed by an LL(1) grammar where the (1) signifies the parser reads ahead one token at a time.

For an ambiguous language to be parsed by an LL parser, the parser must lookahead more than 1 symbol, e.g. LL(3). The common solution to this problem is to use an LR parser, which is a type of shift-reduce parser, and does bottom-up parsing.

Examples

Some of the parsers that use top-down parsing include: Definite clause grammar parsers Recursive descent parser Predictive parser Earley parser

See also

Bottom-up parsing Parsing Parsing expression grammar

Text derived from https://en.wikipedia.org/w/index.php?oldid=1354914222 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001354914222 · captured 2026-05-18 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Top-down parsing”, snapshot enwiki-001354914222. https://encyclopegia.org/a/top-down-parsing

Sources cited in this revision

11 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.