Editing Top-down parsing (section)

== 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>