Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
LL parser
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, an LL parser (left-to-right, <a href="/facts/Leftmost_derivation/yu1FFdK4">leftmost derivation</a>) is a <a href="/facts/Top-down_parsing/VVqphs5y">top-down parser</a> for a restricted <a href="/facts/Context-free_language/sHDxB5So">context-free language</a>. It parses the input from Left to right, performing <a href="/facts/Context-free_grammar/yu1FFdK4">Leftmost derivation</a> of the sentence. </p><p>An LL parser is called an LL(<i>k</i>) parser if it uses <i>k</i> <a href="/facts/Token_(parser)/T1JYWpIf">tokens</a> of <a href="/facts/Parsing/nRKB01S3">lookahead</a> when parsing a sentence. A grammar is called an <a href="/facts/LL_grammar/oy4o6Inv">LL(<i>k</i>) grammar</a> if an LL(<i>k</i>) parser can be constructed from it. A formal language is called an LL(<i>k</i>) language if it has an LL(<i>k</i>) grammar. The set of LL(<i>k</i>) languages is properly contained in that of LL(<i>k</i>+1) languages, for each <i>k</i> ≥ 0. A corollary of this is that not all context-free languages can be recognized by an LL(<i>k</i>) parser. </p><p>An LL parser is called LL-regular (LLR) if it parses an <a href="/facts/LL-regular_language/oy4o6Inv">LL-regular language</a>. The class of <a href="/facts/LL-regular_grammar/oy4o6Inv">LLR grammars</a> contains every LL(<i>k</i>) grammar for every <i>k</i>. For every LLR grammar there exists an LLR parser that parses the grammar in linear time. </p><p>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. LL(*) and LL(finite) parsers are functionally closer to <a href="/facts/Parsing_expression_grammar/8XdfJ7D0">PEG</a> parsers. An LL(finite) parser can parse an arbitrary LL(<i>k</i>) 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 <a href="/facts/Top-down_parsing_language/aYFundzW">TDPL</a> parsers. 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). </p><p>LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct, and many <a href="/facts/Computer_language/n3L56qdP">computer languages</a> are designed to be LL(1) for this reason. LL parsers may be table-based, i.e. similar to <a href="/facts/LR_parser/bpMod8K0">LR parsers</a>, but LL grammars can also be parsed by <a href="/facts/Recursive_descent_parser/ARhcuAv1">recursive descent parsers</a>. According to Waite and Goos (1984), LL(<i>k</i>) grammars were introduced by Stearns and Lewis (1969). </p>