Editing Top-down parsing (section)

{{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.