1 Answers
In computer science, an LL parser is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence.
An LL parser is called an LL parser if it uses k tokens of lookahead when parsing a sentence. A grammar is called an LL grammar if an LL parser can be constructed from it. A formal language is called an LL language if it has an LL grammar. The set of LL languages is properly contained in that of LL languages, for each k ≥ 0. A corollary of this is that not all context-free languages can be recognized by an LL parser.
An LL parser is called LL-regular if it parses an LL-regular language. The class of LLR grammars contains every LL grammar for every k. For every LLR grammar there exists an LLR parser that parses the grammar in linear time.
Two nomenclative outlier parser types are LL and LL. A parser is called LL/LL if it uses the LL/LL parsing strategy. LL and LL parsers are functionally more closely resemblant to PEG parsers. An LL parser can parse an arbitrary LL 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 TDPL parsers.Against the popular misconception, LL parsers are not LLR in general, and are guaranteed by construction to perform worse on average and far worse in the worst-case.