Editing Left recursion (section)

== Accommodating left recursion in top-down parsing==
A [[formal grammar]] that contains left recursion cannot be [[parse]]d by a [[LL parser|LL(k)-parser]] or other naive [[recursive descent parser]] unless it is converted to a [[Weak equivalence (formal languages)|weakly equivalent]] right-recursive form. In contrast, left recursion is preferred for [[LALR parser]]s because it results in lower stack usage than [[right recursion]]. However, more sophisticated top-down parsers can implement general [[context-free grammar]]s by use of curtailment. In 2006, Frost and Hafiz described an algorithm which accommodates [[ambiguous grammar]]s with direct left-recursive [[Formal grammar#The syntax of grammars|production rules]].<ref name="FrostHafiz2006">{{cite journal|last=Frost|first=R.|author2=R. Hafiz|date=2006|title=A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time.|journal=ACM SIGPLAN Notices|volume=41|issue=5|pages=46–54|url=http://portal.acm.org/citation.cfm?id=1149988|doi=10.1145/1149982.1149988|s2cid=8006549|url-access=subscription}}, available from the author at http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf {{Webarchive|url=https://web.archive.org/web/20150108175703/http://hafiz.myweb.cs.uwindsor.ca/pub/p46-frost.pdf |date=2015-01-08 }}</ref> That algorithm was extended to a complete [[parsing]] algorithm to accommodate indirect 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="FrostHafizCallaghan2007">{{cite journal|last=Frost|first=R.|author2=R. Hafiz|author3=P. Callaghan|date=June 2007|title=Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars.|journal=10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE|pages=109–120|url=http://acl.ldc.upenn.edu/W/W07/W07-2215.pdf|archive-url=https://web.archive.org/web/20110527032954/http://acl.ldc.upenn.edu/W/W07/W07-2215.pdf|url-status=dead|archive-date=2011-05-27}}</ref> The authors then implemented the algorithm as a set of [[parser combinator]]s written in the [[Haskell (programming language)|Haskell]] programming language.<ref name="FrostHafizCallaghan2008">{{cite book|last=Frost|first=R. |author2=R. Hafiz |author3=P. Callaghan|title=Practical Aspects of Declarative Languages |chapter=Parser Combinators for Ambiguous Left-Recursive Grammars |date=January 2008|volume=4902|issue=2008|pages=167–181|url=https://cs.uwindsor.ca/~richard/PUBLICATIONS/PADL_08.pdf|doi=10.1007/978-3-540-77442-6_12|series=Lecture Notes in Computer Science|isbn=978-3-540-77441-9}}</ref>