Top-Down Parsing System

A Top-Down Parsing System is a Parsing System that searches for parse trees using a top-down expansion of a set of formal grammar rules.

• AKA: Top-Down Parser.
• Context:
  • It can range from being a LL Parsing System to being a Recursive Descent Parsing System.
• Example(s):
  • a Definite Clause Grammar Parsing System (Pereira et al., 1980)
  • a Recursive Descent Parser System such as:
    • JavaCC;
    • Coco/R;
    • ANTLR;
    • CodeCodex;
  • Tail Recursive Parsing System,
  • Predictive Parsing System,
  • Earley Parsing System.
  • …
• Counter-Example(s):
  • an Adaptive Parsing System,
  • a Bottom-Up Parsing System,
  • a LR Parsing System,
  • an Operator Precedence Parsing System,
  • a Cocke-Younger-Kasami (CYK) Parsing System,
  • a Recursive Ascent Parsing System,
  • a Shift-Reduce Parsing System.
• See: Context-Free Grammar, Visual Programming Languages, Graph Grammar, Natural Language User Interface, Top-Down Parsing, Parse Tree, Formal Grammar, Ambiguity, Addison-Wesley Longman, Bottom-up Parsing, LR Parser, Shift-Reduce_parser.

---

---

References

2019a

• (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Parsing#Types_of_parsers Retrieved:2019-7-7.
  • The task of the parser is essentially to determine if and how the input can be derived from the start symbol of the grammar. This can be done in essentially two ways:
    • Top-down parsing - 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. Tokens are consumed from left to right. Inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules.
    • Bottom-up parsing - A parser can start with the input and attempt to rewrite it to the start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. LR parsers are examples of bottom-up parsers. Another term used for this type of parser is Shift-Reduce parsing.
  • LL parsers and recursive-descent parser are examples of top-down parsers which cannot accommodate left recursive production rules. Although it has been believed that simple implementations of top-down parsing cannot accommodate direct and indirect left-recursion and may require exponential time and space complexity while parsing ambiguous context-free grammars, more sophisticated algorithms for top-down parsing have been created by Frost, Hafiz, and Callaghan which accommodate ambiguity and left recursion in polynomial time and which generate polynomial-size representations of the potentially exponential number of parse trees. Their algorithm is able to produce both left-most and right-most derivations of an input with regard to a given context-free grammar.

    An important distinction with regard to parsers is whether a parser generates a leftmost derivation or a rightmost derivation (see context-free grammar). LL parsers will generate a leftmost derivation and LR parsers will generate a rightmost derivation (although usually in reverse).

    Some graphical parsing algorithms have been designed for visual programming languages. Parsers for visual languages are sometimes based on graph grammars. Adaptive parsing algorithms have been used to construct "self-extending" natural language user interfaces.

2019b

• (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Top-down_parsing Retrieved:2019-7-7.
  • In computer science, top-down parsing 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.

2017

• (Wikibooks, 2017) ⇒ https://en.wikibooks.org/wiki/Compiler_Construction/Syntax_Analysis
  • QUOTE: A recursive descent parser is a top-down parser built from a set of mutually-recursive procedures (or a non-recursive equivalent) where each such procedure usually implements one of the production rules of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.

    A predictive parser is a recursive descent parser with no backup. Predictive parsing is possible only for the class of LL(k) grammars, which are the context-free grammars for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input. (The LL(k) grammars therefore exclude all ambiguous grammars, as well as all grammars that contain left recursion. Any context-free grammar can be transformed into an equivalent grammar that has no left recursion, but removal of left recursion does not always yield an LL(k) grammar.) A predictive parser runs in linear time.

     Recursive descent with backup is a technique that determines which production to use by trying each production in turn. Recursive descent with backup is not limited to LL(k) grammars, but is not guaranteed to terminate unless the grammar is LL(k). Even when they terminate, parsers that use recursive descent with backup may require exponential time.

    Although predictive parsers are widely used, programmers often prefer to create LR or LALR parsers via parser generators without transforming the grammar into LL(k) form.

    Some authors define the recursive descent parsers as the predictive parsers. Other authors use the term more broadly, to include backed-up recursive descent.

---