LL-анализатор

Материал из Википедии — свободной энциклопедии

(Перенаправлено с LL parser)
Перейти к: навигация, поиск
Стилевые проблемы
 Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка.
Статью следует исправить согласно стилистическим правилам Википедии.
Необходимо проверить качество перевода и привести статью в соответствие стилистическим правилам Википедии.
Вы можете помочь улучшить эту статью, исправив в ней ошибки.
Translation arrow icon Эта статья или секция — грубый перевод статьи на другом языке (см. Проверка переводов). Он мог быть генерирован программой-переводчиком или человеком со слабыми познаниями в языке статьи оригинала.

Пожалуйста, не поленитесь улучшить перевод. Оригинал можно найти слева в списке «на других языках».


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

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

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

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

Содержание

[править] Общий случай

Синтаксический анализатор воздействует на строки от специфической грамматики.

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

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

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

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

 [ S, $ ]

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

[править] Конкретный пример

[править] Установленный

Чтобы объяснить его работы, мы рассмотрим следующую маленькую грамматику:

  1. S → F
  2. S → (S + F)
  3. F → 1

и анализируйте следующий ввод:

(1 + 1)

Таблица синтаксического анализа для этой грамматики выглядит следующим образом:

( ) 1 + $
S 2  — 1 - -
F  —  — 3 - -

(Отметьте, что есть также столбец для специального терминала, представленного здесь как $, который используется, чтобы указать конец входного потока.)

[править] Синтаксический анализ процедуры

Синтаксический анализатор читает первый литерал '(' от входного потока, и контрольный символ 'S' из стека, тем самым получая на пересечении обоих значений в таблице синтаксического разбора - номер правила из списка грамматики. В конкретном случае должно выполнится правило 2, которая удалит последнее вхождение стека и перезапишет его значением из списка грамматики (меняем 'S' на '(S + F)' в обратном порядке) и написать число этого правила к выводу. Стек тогда становится:

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

В следующем шаге это удаляет '(' от его входного потока и от его стека:

[ S, +, F, ), $ ]

Теперь синтаксический анализатор видит '1' на его входном потоке, таким образом он знает, что он должен применить правило (1) и затем правило (3) от грамматики и написать их число потоку вывода. Это приводит к следующим стекам:

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

В следующих двух шагах синтаксический анализатор читает '1' и '+' от входного потока и, так как они соответствуют следующим двум элементам на стеке, также удаляет их из стека. Это приводит к:

[ F, ), $ ]

В следующих трех шагах 'F' будет заменен на стеке с '1', номер 3 будет написан потоку вывода и затем '1', и ')' будет удален от стека и входного потока. Таким образом синтаксический анализатор заканчивается и '$' на его стеке и на его входном потоке.

В этом случае это сообщит, что это приняло входную строку и написало к потоку вывода список чисел

[ 2, 1, 3, 3 ]

который является действительно крайним левым образованием из входной строки. Мы видим, что крайнее левое образование из входной строки:

S → (S + F) → (F + F) → (1 + F) → (1 + 1)

[править] Комментарии

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

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

Эти шаги повторены до остановок синтаксического анализатора, и затем это или полностью анализирует ввод и напишет крайнее левое образование потоку вывода, или это сообщит об ошибке.

[править] Построение LL (1) таблица синтаксического анализа

Чтобы заполнить таблицу синтаксического анализа, мы должны установить, какое правило грамматики синтаксический анализатор должен выбрать, если это видит нетерминальное A на вершине его стека и символа a на его входном потоке. Это просто видеть, что такое правило должно иметь форму A → w и что у языка, соответствующего w , должна быть по крайней мере одна строка, начинающаяся с a. С этой целью мы определяем Первый набор w, написанного здесь как Fi(w), как набор терминалов, которые могут быть найдены в начале любой строки в w, плюс ε если пустая строка также принадлежит w. Учитывая грамматику с правилами A1 → w1, …, An → wn, мы можем вычислить Fi(wi) и Fi(Ai) для каждого правила следующим образом:

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

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

  1. инициализируйте каждый Fo(Ai) с пустым множеством
  2. если есть правило формы Aj → wAiw' , тогда
    • если терминал a в Fi(w' ), то добавте a к Fo(Ai)
    • если ε находится в Fi(w' ), тогда добавьте Fo(Aj) к Fo(Ai)
  3. повторите шаг 2 до всего пребывания наборов Fo то же самое.

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

T[A,a] содержит правило A → w если и только если
a в Fi(w) или
ε находится в Fi(w) и a в Fo(A).

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

[править] Построение LL (k) синтаксический анализ таблицы

До середины 1990-ых широко полагалось, что LL(k) анализирующий (для k > 1) был непрактичен[источник не указан 54 дня], так как размер таблицы синтаксического анализа будет (вообще, в самом плохом случае) должны иметь показательную сложность в k. Это восприятие постепенно изменялось после выпуска набора инструментальных средств конструкции компилятора (PCCTS, теперь известный как ANTLR) приблизительно в 1992 году, когда было продемонстрировано что много языков программирования могут быть анализированы эффективно LL(k) parser синтаксический анализатор, не вызывая поведение самого плохого случая синтаксического анализатора. Кроме того, в определенных случаях синтаксический анализ LL выполним даже с неограниченным предвидением. В отличие от этого, традиционные генераторы синтаксического анализатора, как yacc/GNU bison, используют LALR(1) таблицы синтаксического анализа, чтобы создать ограниченный LR-анализатор с установленным предвидением с одной лексемой.

[править] LL (k) генераторы синтаксического анализатора

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

[править] Ссылки

Источник — «http://ru.wikipedia.org/wiki/LL-%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%82%D0%BE%D1%80»