WikiSort.ru - Не сортированное

Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии.

Необходимо проверить качество перевода и привести статью в соответствие со стилистическими правилами Википедии. Вы можете помочь улучшить эту статью, исправив в ней ошибки. Оригинал на английском языке — LL_parser.

Этот перевод статьи с другого языка требует улучшения (см. Проверка переводов). Вы можете помочь улучшить перевод. Оригинал можно найти слева в списке языков. Статья, целиком являющаяся машинным переводом, может быть удалена на основании критерия быстрого удаления С2.

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

См. также LL(1)

Синтаксический LL-анализатор (LL parser) — в информатике нисходящий синтаксический анализатор для некоторого подмножества контекстно-свободных грамматик, известных как LL-грамматики. При этом не все контекстно-свободные грамматики являются LL-грамматиками.

Буквы L в выражении «LL-анализатор» означают, что входная строка анализируется слева направо (left to right), и при этом строится её левосторонний вывод (leftmost derivation).

LL-анализатор называется LL(k)-анализатором, если данный анализатор использует предпросмотр на k токенов (лексем) при разборе входного потока. Грамматика, которая может быть распознана LL(k)-анализатором без возвратов к предыдущим символам, называется LL(k)-грамматикой. Язык, который может быть представлен в виде LL(k)-грамматики, называется LL(k)o-языком. Существуют LL(k+n)-языки, которые не являются LL(k)-языками.

Далее описывается анализатор, в основе которого лежит построение таблиц; альтернативой может служить анализатор, построенный методом рекурсивного спуска, который обычно пишется вручную (хотя существуют и исключения, например, генератор синтаксических анализаторов ANTLR для LL(*) грамматик).

LL(1)-грамматики очень распространены, потому что соответствующие им LL-анализаторы просматривают поток только на один символ вперед при принятии решения о том, какое правило грамматики необходимо применить. Языки, основанные на грамматиках с большим значением k, традиционно считались трудными для распознавания, хотя при широком распространении генераторов синтаксических анализаторов, поддерживающих LL(k) грамматики с произвольным k, это замечание уже неактуально.

LL-анализатор называется LL(*)-анализатором, если нет строгого ограничения для k и анализатор может распознавать язык, если токены принадлежат какому-либо регулярному множеству (например, используя детерминированные конечные автоматы).

Существуют противоречия между так называемой «Европейской школой» построения языков, которая основывается на LL-грамматиках, и «Американской школой», которая предпочитает LR-грамматики. Такие противоречия обусловлены традициями преподавания и деталями описания различных методов и инструментов в конкретных учебниках; кроме того, своё влияние оказал Н. Вирт из ETHZ, чьи исследования описывают различные методы оптимизации LL(1) распознавателей и компиляторов.

Общий случай

Синтаксический анализатор предназначен для разрешения проблемы принадлежности строки заданной грамматике и построения дерева вывода в случае принадлежности.

Синтаксический анализатор состоит из:

• Ленты (входного буфера) — содержит анализируемую строку
• Стека — служит для сохранения промежуточных данных синтаксического анализа
• Таблицы синтаксического анализа — таблица, задающая однозначное соответствие правила грамматики для символа магазинного алфавита, находящегося на вершине стека, и текущего читаемого символа на ленте, или содержащая информацию об отсутствии такого правила для заданной пары символов.

В строках таблицы располагаются символы магазинного алфавита, а в столбцах — символы терминального алфавита.

При запуске синтаксического анализа, стек уже содержит два символа:

 [ S, $ ]

Где '$' — специальный терминал, служащий для указания конца стека, а 'S' — аксиома грамматики. Синтаксический анализатор пытается при помощи правил грамматики заменить в стеке аксиому на цепочку символов, аналогичную цепочке, находящейся на входной ленте, и затем полностью прочитать ленту, опустошая стек.

Пример

[ (, S, +, F, ), $ ]

[ S, +, F, ), $ ]

[ F, +, F, ), $ ]
[ 1, +, F, ), $ ]

[ F, ), $ ]

Комментарии

Как можно заметить исходя из примера — синтаксический анализатор выполняет три различных вида действий в зависимости от того, находится ли на вершине стека нетерминал, терминал или специальный символ $:

• Если вершина — нетерминал, то в таблице синтаксического анализа ищется правило грамматики, находящееся на пересечении столбца и строки, соответствующих нетерминалу на вершине стека и текущему символу на ленте (на который указывает головка МП-автомата). Если же в указанной ячейке таблицы правило отсутствует — синтаксический анализатор останавливается и сообщает об ошибке.
• Если вершина — терминал, то синтаксический анализатор сравнивает его с текущим символом на ленте. Если они равны, то символ с ленты прочитывается, а соответствующий символ из вершины стека — выталкивается.
• Если вершина — $ и текущий символ на ленте так же $, то синтаксический анализатор сообщает об успешном распознавании цепочки, в противном случае — сообщает об ошибке. В обоих случаях происходит останов анализатора.

Эти шаги повторяются до тех пор, пока не произойдёт останов. После останова мы получим или сообщение об ошибке, или сообщение об успешном распознавании цепочки.

Построение LL (1) таблицы синтаксического анализа

Чтобы заполнить таблицу синтаксического анализа, необходимо установить, какое правило грамматики синтаксический анализатор должен выбрать, если нетерминальное A находится на вершине его стека и символ a - во входном потоке. Легко заметить, что такое правило должно иметь форму A → w и что у языка, соответствующего w , должна быть по крайней мере одна строка, начинающаяся с a. С этой целью мы определяем Первый набор w, написанного здесь как Fi(w), как набор терминалов, которые могут быть найдены в начале любой строки в w, и ε, если пустая строка также принадлежит w. Учитывая грамматику с правилами A₁ → w₁, …, A_n → w_n, можно вычислить Fi(w_i) и Fi(A_i) для каждого правила следующим образом:

1. инициализировать каждый Fi(Ai) пустым множеством
2. добавить Fi(wi) к Fi(Ai) для каждого правила Ai → wi, где Fi(wi) определён следующим образом:
   • Fi(a w' ) = { a } для каждого терминала a
   • Fi(A w' ) = Fi(A) для каждого нетерминального A с ε не в Fi(A)
   • Fi(A w' ) = Fi(A) \ { ε } ∪ Fi(w' ) для каждого нетерминального A с ε в Fi(A), включая случай Ai -> A, т. е. w' = ε, в этом случае Fi(A w' ) = Fi(A)
   • Fi(ε) = { ε }
3. повторяйте шаг 2, пока в наборах Fi происходят изменения.

К сожалению, первых наборов недостаточно, чтобы построить таблицу синтаксического анализа. Так происходит, потому что правая сторона w правила могла бы в конечном счете быть приведена к пустой строке. Таким образом синтаксический анализатор должен также использовать правило A → w если ε находится в Fi(w) и во входном потоке символ, который может следовать за A. Поэтому также необходимо построить Следующий набор A (здесь будет записываться как Fo(A)) который определен как набор терминалов a таких, что существует строка символов αAaβ которая может быть получена из начального символа. Вычисление Следующих наборов для нетерминалов в грамматике может быть сделано следующим образом:

1. инициализировать Fo(S) = { $ }, а все остальные Fo(A_i) пустыми множествами
2. если есть правило формы A_j → wA_iw' , тогда
   • если терминал a в Fi(w' ), то добавить a к Fo(A_i)
   • если ε находится в Fi(w' ) ,то добавить Fo(A_j) к Fo(A_i)
   • если w' длины 0, то добавить Fo(A_j) к Fo(A_i)
3. повторите шаг 2, пока в наборах Fo происходят изменения.

Теперь можно определить точно, какие правила будут содержаться в таблице синтаксического анализа. Если T[A, a] обозначает вход в таблице для нетерминального A и терминала a, то

T[A,a] содержит правило A → w если и только если:

1. a добавлено в Fi(A) при проходе правила A → w, или
2. ε находится в Fi(A) и a добавлено в Fo(A) при проходе правила A → w.

Если таблица будет содержать не более одного правила в каждой ячейке, то синтаксический анализатор сможет однозначно определить, какое правило необходимо применить на каждом шаге разбора. В этом случае грамматику называют LL(1) грамматикой.

Построение таблиц синтаксического анализа для LL(k) анализаторов

Размер таблицы синтаксического анализа в худшем случае имеет показательную сложность в зависимости от k. Однако, после выпуска набора инструментальных средств конструирования компиляторов (PCCTS, теперь известный как ANTLR) приблизительно в 1992 году было показано, что размер таблицы синтаксического анализа для большинства языков программирования не имеет тенденции к показательному росту, так как не является худшим вариантом. Кроме того, в определенных случаях было возможно создание даже LL(*)-анализаторов. Однако, несмотря на это, традиционные генераторы синтаксических анализаторов, такие как yacc/GNU bison, используют LALR(1) таблицы синтаксического анализа, чтобы создать ограниченный LR-анализатор.

LL генераторы синтаксических анализаторов

Список примеров в этом разделе не основывается на авторитетных источниках, посвящённых непосредственно предмету статьи или её раздела. Добавьте ссылки на источники, предметом рассмотрения которых является тема настоящей статьи (или раздела) в целом, а не отдельные элементы списка. В противном случае раздел может быть удалён.

Современные генераторы синтаксических анализаторов, для LL грамматик с мультиэстафетным предвидением, включают:

• ANTLR: Домашняя страница
• Coco/R: Домашняя страница
• JavaCC: Домашняя страница
• PCCTS — теперь ANTLR, старый сайт: http://www.polhode.com/pccts.html
• SLK : Strong LL(k) parsing(Сильный LL(k) синтаксический анализ), Домашняя страница — всестороннее обсуждение синтаксического LL(k) анализа
• Spirit Parser Framework : домашняя страница — генератор LL(*) анализаторов.
• JetPAG: Jet Parser Auto-Generator(Реактивный Автогенератор Синтаксического анализатора). LL (k) генератор синтаксических анализаторов.
• Parsec: Домашняя страница- одноместный синтаксический анализатор combinator, библиотека для Haskell, который может анализировать LL(*), контекстно-зависимые грамматики, однако лучше всего он работает для LL (1) грамматик.
• Ocaml Genlex Module : Домашняя страница
• JFLAP: На сайте учебник по LL(1) синтаксическому анализу.
• Grammatica: На сайте — LL(k) генератор синтаксических анализаторов для C# и Java.

Ссылки

• Простое объяснение первых и следующих наборов (попытка объяснить процесс создавания сначала и следовать за наборами более прямым способом)
• Обучающая программа для создания LL(1) синтаксических анализаторов на языке C#

Примечания

uy yr