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.^[1] 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.^[2]

Simple implementations of top-down parsing do not terminate for

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:

• ${\displaystyle A\rightarrow aBC}$
• ${\displaystyle B\rightarrow c\mid cd}$
• ${\displaystyle C\rightarrow df\mid eg}$

which produces the string A=acdf

would match ${\displaystyle A\rightarrow aBC}$ and attempt to match ${\displaystyle B\rightarrow c\mid cd}$ next. Then ${\displaystyle 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.

Accommodating left recursion in top-down parsing

A

Additionally, one may use a Graph-structured stack (GSS) in addition to the aforementioned curtailment in order to accommodate left recursion by 'merging' stacks with common prefixes and by preventing infinite recursion, thereby reducing the number and contents of each stack, thereby reducing the time and space complexity of the parser. This leads to an algorithm known as Generalized LL parsing, in which you use a GSS, left-recursion curtailment, and an LL(k) parser to parse input strings relative to a given CFG.^[7][8]

Time and space complexity of top-down parsing

When top-down parser tries to parse an ambiguous input with respect to an ambiguous CFG, it may need exponential number of steps (with respect to the length of the input) to try all alternatives of the CFG in order to produce all possible parse trees, which eventually would require exponential memory space. The problem of exponential time complexity in top-down parsers constructed as sets of mutually recursive functions has been solved by Norvig in 1991.^[9] His technique is similar to the use of dynamic programming and state-sets in Earley's algorithm (1970), and tables in the CYK algorithm of Cocke, Younger and Kasami.

The key idea is to store results of applying a parser p at position j in a memorable and to reuse results whenever the same situation arises. Frost, Hafiz and Callaghan^[4][5] also use memoization for refraining redundant computations to accommodate any form of CFG in polynomial time (Θ(n⁴) for left-recursive grammars and Θ(n³) for non left-recursive grammars). Their top-down parsing algorithm also requires polynomial space for potentially exponential ambiguous parse trees by 'compact representation' and 'local ambiguities grouping'. Their compact representation is comparable with Tomita's compact representation of bottom-up parsing.^[10]

Using PEG's, another representation of grammars, packrat parsers provide an elegant and powerful parsing algorithm. See Parsing expression grammar.

Examples

Some of the parsers that use top-down parsing include:

• Definite clause grammar parsers^[11]
• Recursive descent parser
• Predictive parser
• Earley parser

See also

• Bottom-up parsing
• Parsing
• Parsing expression grammar

References