Введение
Анализатор сверху вниз, который анализирует вход слева направо.
В информатике LL-анализатор (слева направо, самый левый вывод) — это анализатор сверху вниз для ограниченного контекстно-свободного языка. Он анализирует вход слева направо, выполняя самый левый вывод предложения. LL-анализатор называется LL(k)-анализатором, если он использует k токенов предварительного просмотра при анализе предложения. Грамматика называется LL(k)-грамматикой, если из нее можно построить LL(k)-анализатор. Формальный язык называется LL(k)-языком, если он имеет LL(k)-грамматику. Множество LL(k)-языков содержится в множестве LL(k+1)-языков для каждого k ≥ 0. Не все контекстно-свободные языки могут быть распознаны LL(k)-анализатором. LL-анализатор называется LL-регулярным (LLR), если он анализирует LL-регулярный язык. Класс LLR-грамматик содержит каждую LL(k)-грамматику для каждого k. Для каждой LLR-грамматики существует LLR-анализатор, который анализирует грамматику за линейное время. Два нестандартных типа анализаторов — LL(*) и LL(конечный). Анализатор называется LL(*)/LL(конечный), если он использует стратегию анализа LL(*)/LL(конечный). LL(*) и LL(конечный) анализаторы функционально ближе к анализаторам PEG. LL(конечный) анализатор может оптимально анализировать произвольную LL(k)-грамматику с точки зрения объема предварительного просмотра и сравнений предварительного просмотра. Класс грамматик, анализируемых стратегией LL(*), включает в себя некоторые контекстно-зависимые языки из-за использования синтаксических и семантических предикатов и не был идентифицирован. Предполагается, что LL(*) анализаторы лучше рассматривать как анализаторы TDPL. Вопреки распространенному заблуждению, LL(*) анализаторы обычно не являются LLR и по построению гарантированно работают хуже в среднем (суперлинейное по сравнению с линейным временем) и значительно хуже в худшем случае (экспоненциальное по сравнению с линейным временем). LL-грамматики, особенно LL(1)-грамматики, представляют большой практический интерес, поскольку анализаторы для этих грамматик легко построить, и многие компьютерные языки разработаны для LL(1) по этой причине. LL-анализаторы могут быть табличными, то есть похожими на LR-анализаторы, но LL-грамматики также могут быть проанализированы рекурсивными спусками. Согласно Уэйту и Гусу (1984), LL(k)-грамматики были введены Стирнсом и Льюисом (1969).
In computer science, an LL parser (Left to right, leftmost derivation) 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(k) parser if it uses k tokens of lookahead when parsing a sentence. A grammar is called an 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 ≥ 0. 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. The class of 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. 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 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 TDPL 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). LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct, and many computer languages are designed to be LL(1) for this reason. LL parsers may be table based, i. e. similar to LR parsers, but LL grammars can also be parsed by recursive descent parsers. According to Waite and Goos (1984), LL(k) grammars were introduced by Stearns and Lewis (1969).
Замена
Замена одного правила другим для устранения косвенных или конфликтов FIRST/FOLLOW. Следует отметить, что это может привести к конфликту FIRST/FIRST.