Editing Top-down parsing

{{Short description|Parsing technique}}
'''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]].<ref name="GruneJacobs2007">{{cite book|author1=Dick Grune|author2=Ceriel J.H. Jacobs|title=Parsing Techniques: A Practical Guide|url=https://books.google.com/books?id=05xA_d5dSwAC&q=%22top-down%22|date=29 October 2007|publisher=Springer Science & Business Media|isbn=978-0-387-68954-8}}</ref> [[LL parser]]s 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 [[language]]s and [[computer language]]s.

Top-down parsing can be viewed as an attempt to find [[Context-free grammar#Derivations and syntax trees|left-most derivations]] of an input-stream by searching for [[parse tree|parse-trees]] using a top-down expansion of the given [[formal grammar]] rules. Inclusive choice is used to accommodate [[syntactic ambiguity|ambiguity]] by expanding all alternative right-hand-sides of grammar rules.<ref name="AhoSethiUllman 1986">{{cite book |last1=Aho |first1=Alfred V. |authorlink1=Alfred Aho |last2=Sethi |first2=Ravi |authorlink2=Ravi Sethi |last3=Ullman |first3=Jeffrey D. |authorlink3=Jeffrey Ullman |title=Compilers, principles, techniques, and tools |year=1986 |publisher=Addison-Wesley Pub. Co. |isbn=978-0201100884 |edition=Rep. with corrections. |url=https://archive.org/details/compilersprincip00ahoa }}</ref>

Simple implementations of top-down parsing do not terminate for [[left recursion|left-recursive]] grammars, and top-down parsing with backtracking may have [[exponential time]] complexity with respect to the length of the input for ambiguous [[Context-free grammar|CFGs]].<ref name="AhoUllman 1972">{{cite book |last1=Aho |first1=Alfred V. |authorlink1=Alfred Aho |last2=Ullman |first2=Jeffrey D. |authorlink2=Jeffrey Ullman |title=The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) |year=1972 |publisher=Prentice-Hall |location=Englewood Cliffs, NJ |isbn=978-0139145568 |edition=Repr. |url=https://archive.org/details/theoryofparsingt00ahoa }}</ref> However, more sophisticated top-down parsers have been created by Frost, Hafiz, and Callaghan,<ref name="FrostHafizCallaghan 2007">Frost, R., Hafiz, R. and Callaghan, P. (2007) " [https://aclanthology.info/pdf/W/W07/W07-2215.pdf Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars] ." ''10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE '', Pages: 109 - 120, June 2007, Prague.  [https://web.archive.org/web/20181112231051/https://aclanthology.info/pdf/W/W07/W07-2215.pdf Archived] from the original on 12 November 2018.</ref><ref name="FrostHafizCallaghan 2008">Frost, R., Hafiz, R. and Callaghan, P. (2008) " [http://scholar.uwindsor.ca/cgi/viewcontent.cgi?article=1411&context=etd#page=61 Parser Combinators for Ambiguous Left-Recursive Grammars]." '' 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN '', Volume 4902/2008, Pages: 167-181, January 2008, San Francisco.</ref> which do [[#Accommodating left recursion in top-down parsing|accommodate ambiguity and left recursion]] in [[Time complexity#Polynomial time|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 [[Formal grammar#The syntax of grammars|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:

* <math>A \rightarrow aBC</math>
* <math>B \rightarrow c \mid cd</math>
* <math>C \rightarrow df \mid eg</math>

which produces the string ''A''=''acdf''

would match <math>A \rightarrow aBC</math> and attempt to match <math>B \rightarrow c \mid cd</math> next. Then <math>C \rightarrow df \mid eg</math> 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 [[formal grammar]] that contains [[left recursion]] cannot be [[parsing|parsed]] by a naive [[recursive descent parser]] unless they are converted to a weakly equivalent right-recursive form. However, recent research demonstrates that it is possible to accommodate left-recursive grammars (along with all other forms of general [[Context-free grammar|CFGs]]) in a more sophisticated top-down parser by use of curtailment. A [[recognizer|recognition]] algorithm that accommodates [[ambiguous grammar]]s and curtails an ever-growing direct left-recursive parse by imposing depth restrictions with respect to input length and current input position, is described by Frost and Hafiz in 2006.<ref name="FrostHafiz2006">Frost, R. and Hafiz, R. (2006) " [http://richard.myweb.cs.uwindsor.ca/PUBLICATIONS/SIGPLAN_06.pdf A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time]." ''ACM SIGPLAN Notices'', Volume 41 Issue 5, Pages: 46 - 54. {{doi|10.1145/1149982.1149988}}</ref> That algorithm was extended to a complete [[parsing]] algorithm to accommodate indirect (by comparing previously computed context with current context) as well as direct left-recursion in [[polynomial]] time, and to generate compact polynomial-size representations of the potentially exponential number of parse trees for highly ambiguous grammars by Frost, Hafiz and Callaghan in 2007.<ref name="FrostHafizCallaghan 2007"/> The algorithm has since been implemented as a set of [[parser combinator]]s written in the [[Haskell (programming language)|Haskell]] programming language. The implementation details of these new set of combinators can be found in a paper<ref name="FrostHafizCallaghan 2008"/> by the authors, which was presented in PADL'08.
The [http://www.cs.uwindsor.ca/~hafiz/proHome.html X-SAIGA] site has more about the algorithms and implementation details.

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 [[Context-free grammar|CFG.]]<ref>{{Cite web | url=http://dotat.at/tmp/gll.pdf | title=GLL Parsing | first1=Elizabeth | last1=Scott | first2=Adrian | last2=Johnstone | publisher=[[University of London]] | website=dotat.at}}</ref><ref>{{Cite web | url=https://pure.royalholloway.ac.uk/portal/files/26408385/postprint.pdf | title=Structuring the GLL parsing algorithm for performance |  first1=Elizabeth | last1=Scott | first2=Adrian | last2=Johnstone | publisher=[[University of London]] | website=dotat.at}}</ref>

== 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 [[Peter Norvig|Norvig]] in 1991.<ref name=" Norvig 1991">Norvig, P. (1991) “[https://aclanthology.info/pdf/J/J91/J91-1004.pdf Techniques for automatic memoisation with applications to context-free parsing].” ''Journal - Computational Linguistics'' Volume 17, Issue 1, Pages: 91 - 98.</ref> His technique is similar to the use of dynamic programming and state-sets in [[Earley parser|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 <code>p</code> at position <code>j</code> in a memorable and to reuse results whenever the same situation arises. Frost, Hafiz and Callaghan<ref name="FrostHafizCallaghan 2007"/><ref name="FrostHafizCallaghan 2008"/> also use [[memoization]] for refraining redundant computations to accommodate any form of CFG in [[polynomial]] time ([[Big O notation|Θ]](n<sup>4</sup>) for left-recursive grammars and [[Big O notation|Θ]](n<sup>3</sup>) 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 [[Masaru Tomita|Tomita]]'s compact representation of [[bottom-up parsing]].<ref name=" Tomita1985">Tomita, M. (1985) “[https://books.google.com/books?id=DAjkBwAAQBAJ Efficient Parsing for Natural Language].” ''Kluwer, Boston, MA''.</ref>

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<ref>Pereira, Fernando CN, and David HD Warren. "[http://cgi.di.uoa.gr/~takis/pereira-warren.pdf Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks]." Artificial intelligence 13.3 (1980): 231-278.</ref>
* [[Recursive descent parser]]
* [[Predictive parser]]
* [[Earley parser]]

==See also==
* [[Bottom-up parsing]]
* [[Parsing]]
* [[Parsing expression grammar]]

==References==
{{reflist}}

== External links ==
* [http://www.cs.uwindsor.ca/~hafiz/proHome.html X-SAIGA] - eXecutable SpecificAtIons of GrAmmars

{{Parsers}}

{{DEFAULTSORT:Top-Down Parsing}}
[[Category:Parsing algorithms]]