Editing LL parser (section)

{{Short description|Top-down parser that parses input from left to right}}
In [[computer science]], an '''LL parser''' (left-to-right, [[leftmost derivation]]) is a [[Top-down parsing|top-down parser]] for a restricted [[context-free language]]. It parses the input from '''L'''eft to right, performing [[Context-free grammar#Derivations and syntax trees|'''L'''eftmost derivation]] of the sentence.

An LL parser is called an LL(''k'') parser if it uses ''k'' [[token (parser)|tokens]] of [[Parsing#Lookahead|lookahead]] when parsing a sentence. A grammar is called an [[LL grammar|LL(''k'') grammar]] if an LL(''k'') parser can be constructed from it. A formal language is called an LL(''k'') language if it has an LL(''k'') grammar. The set of LL(''k'') languages is properly contained in that of LL(''k''+1) languages, for each ''k''&nbsp;≥&nbsp;0.<ref>{{cite journal
| last1=Rosenkrantz| first1=D. J.| last2=Stearns| first2=R. E.| title=Properties of Deterministic Top Down Grammars| journal=Information and Control| year=1970| volume=17| issue=3| pages=226–256| doi=10.1016/s0019-9958(70)90446-8| doi-access=free}}</ref> A corollary of this is that not all context-free languages can be recognized by an LL(''k'') parser.

An LL parser is called LL-regular (LLR) if it parses an [[LL-regular language]].{{clarify|reason=LLR-parsers are defined by their employed method (lookahead on regular partitions), not by their accepted language. An LLR language can well be parsed using another method.|date=August 2021}}<ref>{{cite journal |last1=Jarzabek |first1=Stanislav |last2= Krawczyk |first2= Tomasz |title=LL-Regular Grammars |journal=Instytutu Maszyn Matematycznych |date=1974 |pages=107–119}}</ref><ref>{{cite journal | url=https://www.sciencedirect.com/science/article/abs/pii/0020019075900095 | last1=Jarzabek |first1=Stanislav |last2= Krawczyk |first2= Tomasz | title=LL-Regular Grammars | journal=[[Information Processing Letters]] | volume=4 | number=2 | pages=31&ndash;37 | date=Nov 1975 | doi=10.1016/0020-0190(75)90009-5 | url-access=subscription }}</ref><ref>{{cite report | url=https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1176&context=cstech | author=David A. Poplawski | title=Properties of LL-Regular Languages | institution=[[Purdue University]], Department of Computer Science | type=Technical Report | number=77–241 | date=Aug 1977 }}</ref> The class of [[LL-regular grammar|LLR grammars]] contains every LL(''k'') grammar for every ''k''. For every LLR grammar there exists an LLR parser that parses the grammar in linear time.{{citation needed|date=June 2022}}

Two nomenclative outlier parser types are LL(*) and LL(finite). A parser is called LL(*)/LL(finite) if it uses the LL(*)/LL(finite) parsing strategy.<ref>{{cite journal |last1=Parr, Terence and Fisher, Kathleen |title=LL (*) the foundation of the ANTLR parser generator |journal=ACM SIGPLAN Notices |date=2011 |volume=46 |issue=6 |pages=425–436|doi=10.1145/1993316.1993548 }}</ref><ref>{{cite arXiv |last1=Belcak |first1=Peter |title=The LL(finite) parsing strategy for optimal LL(k) parsing |year=2020 |class=cs.PL |eprint=2010.07874 }}</ref> LL(*) and LL(finite) parsers are functionally closer to [[Parsing expression grammar|PEG]] parsers. An LL(finite) parser can parse an arbitrary LL(''k'') grammar optimally in the amount of lookahead and lookahead comparisons. The class of grammars parsable by the LL(*) strategy encompasses some context-sensitive languages due to the use of syntactic and semantic predicates and has not been identified. It has been suggested that LL(*) parsers are better thought of as [[Top-down parsing language|TDPL]] parsers.<ref>{{cite journal |last1=Ford |first1=Bryan |title=Parsing Expression Grammars: A Recognition-Based Syntactic Foundation |journal=ACM SIGPLAN Notices |date=2004 |doi=10.1145/982962.964011}}</ref>
Against the popular misconception, LL(*) parsers are not LLR in general, and are guaranteed by construction to perform worse on average (super-linear against linear time) and far worse in the worst-case (exponential against linear time).

LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct, and many [[computer language]]s are designed to be LL(1) for this reason.<ref>{{cite book | author=Pat Terry | title=Compiling with C# and Java | url=https://books.google.com/books?id=4O9ffYfX_H0C | publisher=Pearson Education | pages=159–164| isbn=9780321263605 | year=2005 }}</ref> LL parsers may be table-based,{{citation needed|reason=All LL parsers I ever saw were recursive-descent based.|date=February 2019}} i.e. similar to [[LR parser]]s, but LL grammars can also be parsed by [[recursive descent parser]]s. According to Waite and Goos (1984),<ref>{{cite book | isbn=978-3-540-90821-0 | author=William M. Waite and Gerhard Goos | title=Compiler Construction | location=Heidelberg | publisher=Springer | series=Texts and Monographs in Computer Science | year=1984 }} Here: Sect.&nbsp;5.3.2, p.&nbsp;121-127; in particular, p.&nbsp;123.</ref> LL(''k'') grammars were introduced by Stearns and Lewis (1969).<ref>{{cite journal | author=[[Richard E. Stearns]] and P.M. Lewis | title=Property Grammars and Table Machines | journal=[[Information and Control]] | volume=14 | number=6 | pages=524&ndash;549 | year=1969 | doi=10.1016/S0019-9958(69)90312-X | doi-access=free }}
</ref>