- •Автор: старший преподаватель кафедры Прикладной Математики и Информатики им. Ю.В.Кожевникова Сергей Викторович Сотников.
- •2.3. Общие методы синтаксического анализа 81
- •1. Класс контекстно-свободных языков (V-3.0 28.02.2009)
- •1.1. Свойства кс-языков
- •1.1.1. Теорема Огдена. Лемма о разрастании кс-языков
- •1.2. Приведение кс-грамматик
- •1.2.5. Удаление цепных правил
- •Удаление недостижимых символов;
- •Удаление бесплодных (бесполезных) символов;
- •Удаление цепных правил;
- •1.2.5.1. Алгоритм удаления цепных правил
- •1.3. Нормализация грамматик (Приведение кс-грамматик к нормальной форме)
- •1.3.1.1. Алгоритм преобразования к нормальной форме Хомского
- •1.3.2.1. Устранение левой (правой) рекурсии
- •1.3.2.1.1. Алгоритм устранения левой рекурсии
- •1.3.2.2. Преобразование нелеворекурсивной приведенной кс-грамматики к нормальной форме Грейбах
- •1.3.2.2.1. Алгоритм преобразования нелеворекурсивной приведенной кс-грамматики к нормальной форме Грейбах
- •1.3.2.3. Другой способ преобразования кс-грамматики к нормальной форме Грейбах (Метод Розенкранца)
- •1.3.2.3.1. Алгоритм метода Розенкранца
- •1.4. Автоматы с магазинной памятью (mп-автоматы)
- •1.5. Соотношения между различными мп-автоматами
- •1.5.1. Алгоритм построения мп-автомата по расширенному мп-автомату
- •1.5.2. Алгоритм построения расширенного мп-автомата по мп-автомату
- •1.5.3.1. Алгоритм построения по мп-автомату мп-автомата, допускающего цепочки опустошением магазина
- •1.5.3.1. Алгоритм построения мп-автомата по мп-автомату, допускающего цепочки опустошением магазина
- •1.6. Эквивалентность мп-автоматов и кс-грамматик
- •1.6.1. Алгоритм построения мп-автомата по произвольной кс-грамматике
- •1.6.2. Алгоритм построения расширенного мп-автомата по произвольной кс-грамматике
- •1.6.3. Алгоритм построения кс-грамматики для произвольного мп-автомата
- •1.6.4. Алгоритм построения кс-грамматики для произвольного расширенного мп-автомата
- •2. Методы трансляции
- •2.1. Теория перевода
- •2.1.1. Формализмы, используемые для определения перевода
- •2.1.1.1. Перевод и семантика
- •2.1.1.2. Схемы синтаксически управляемого перевода ( су-схемы)
- •2.1.1.3. Конечные преобразователи
- •2.1.1.4. Преобразователь с магазинной памятью
- •2.1.1.5. Эквивалентность простых су-схем и преобразователей с магазинной памятью
- •2.1.1.5.1. Алгоритм построения мп-преобразователя для простой су-схемы
- •2.1.1.5.2. Алгоритм построения простой су-схемы по мп-преобразователю
- •2.1.2. Лексический анализ
- •2.1.2.1. Непрямой лексический анализ
- •2.1.2.2. Прямой лексический анализ
- •2.1.2.3. Программное моделирование конечных преобразователей
- •2.1.3. Синтаксический анализ
- •2.1.3.1. Определение разбора
- •2.2. Общие методы синтаксического анализа
- •2.2.1. Синтаксический анализ с возвратами
- •2.2.1.1. Алгоритм нисходящего разбора с возвратами
- •2.2.1.2. Проблемы алгоритм нисходящего разбора с возвратами
- •2.2.1.3. Алгоритм восходящего разбора с возвратами
- •Синтаксический анализ с возвратами
- •2.3. Общие методы синтаксического анализа универсальные методы синтаксического анализа. Табличные методы синтаксического анализа Алгоритм Кока-Янгера-Касами
- •Алгоритм разбора Кока-Янгера-Касами
- •Алгоритм нахождения левого разбора по таблице разбора
- •Алгоритм Эрли
- •Алгоритм разбора Эрли
- •Алгоритм построения правого разбора по списку разбора
Алгоритм разбора Эрли
Вход: КС-грамматика
и входная цепочка
.
Выход: Список разбора для цепочки .
Метод:
Сначала строим список
:
Если
,
то добавить ситуацию вида
в список
.
Далее выполняем шаги 2 и 3 до тех пор, пока в можно включать новые ситуации.
Если
(Примечание. Заметим, что
может быть
),
включить в
ситуацию
для любого
.Если , то для каждого правила
включить в
ситуацию
(при условии, что она еще не там).
После того, как построены
,
строится
:
Для каждой ситуации
,
для которой
,
включить в
ситуацию
.
Далее выполнять шаги 5 и 6, пока в можно включать новые ситуации.
Пусть
.
Осуществляем поиск в
ситуации вида
.
Для каждой из них включить в
ситуацию
.Пусть
.
Для каждого
включить в
ситуацию
.
Примечание. Заметим, что рассмотрение ситуации, в которой справа от точки стоит терминал, на шагах 2, 3 и 5, 6 не дает новых ситуаций.
Пример №1
Задание.
Пусть задана грамматика с правилами
и пусть
– входная цепочка.
Решение.
Начинаем построение списка .
Выполняем шаг 1 алгоритма. Для правила
в список
добавим ситуацию вида
.
Также для правила
в список
добавим ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Для текущего содержимого списков выполнение шага 2 алгоритма невозможно.
Выполняем шаг 3 алгоритма. Для ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
Для ситуации
в список
также будут добавлены те же самые
ситуации
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
И снова для текущего содержимого списков выполнение шага 2 алгоритма невозможно.
Выполняем шаг 3 алгоритма. Ситуации вида
и
рассматривать не станем, так как они
уже были рассмотрены при предыдущем
выполнении шага 3 алгоритма. Рассмотрим
ситуации
и
.
Для ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Больше ситуаций в список включить нельзя.
Начинаем построение списка
.
Выполняем шаг 4 алгоритма. Для ситуации
и учитывая, что
,
включим в список
ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.
Выполняем шаг 6 алгоритма. Для ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Снова выполняем шаг 6 алгоритма. Для
ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
Для ситуации
в список
также будут добавлены те же самые
ситуации
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Снова выполняем шаг 6 алгоритма. Для
ситуации
и правила вида
в список
добавим ситуацию вида
.
Для то же ситуации и правила вида
в список
добавим ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Больше ситуаций в список включить нельзя.
Начинаем построение списка
.
Выполняем шаг 4 алгоритма. Для ситуации
и учитывая, что
,
включим в список
ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Выполняем шаг 5 алгоритма. Для ситуации
осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Всего таких ситуаций две:
и
.
Для каждой такой ситуации в список
включаем следующие ситуации:
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Рассматриваем добавленные в список
ситуации. Рассмотрение ситуации
ничего не дает. Выполняем шаг 5 алгоритма
для ситуации
.
Осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Таких ситуаций две:
и
.
Для них в список
включаем следующие ситуации:
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Рассматриваем добавленные в список
ситуации. Рассмотрение ситуации
ничего не дает. Выполняем шаг 5 алгоритма
для ситуации
.
Осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Такая ситуация одна:
.
Для нее в список
включаем следующую ситуацию:
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Больше ситуаций в список включить нельзя.
Начинаем построение списка
.
Выполняем шаг 4 алгоритма. Для ситуации
и учитывая, что
,
включим в список
ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.
Выполняем шаг 6 алгоритма. Для ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.
Выполняем шаг 6 алгоритма. Для ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
Для ситуации
в список
также будут добавлены те же самые
ситуации
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.
Выполняем шаг 6 алгоритма. Для ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
Для ситуации
в список
также будут добавлены те же самые
ситуации
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Больше ситуаций в список включить нельзя.
Начинаем построение списка
.
Выполняем шаг 4 алгоритма. Для ситуации
и учитывая, что
,
включим в список
ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Выполняем шаг 5 алгоритма. Для ситуации
осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Всего таких ситуаций две:
и
.
Для каждой такой ситуации в список
включаем следующие ситуации:
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Рассматриваем добавленные в список
ситуации. Рассмотрение ситуации
ничего не дает. Выполняем шаг 5 алгоритма
для ситуации
.
Осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Таких ситуаций две:
и
.
Для них в список
включаем следующие ситуации:
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Рассматриваем добавленные в список
ситуации. Рассмотрение ситуации
ничего не дает. Выполняем шаг 5 алгоритма
для ситуации
.
Осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Такая ситуация одна:
.
Для нее в список
включаем следующую ситуацию:
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Рассматриваем добавленную в список ситуацию. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Такая ситуация одна: . Для нее в список включаем следующую ситуацию: . После этого шага списки ситуаций будут выглядеть следующим образом:
Больше ситуаций в список включить нельзя.
Начинаем построение списка
.
Выполняем шаг 4 алгоритма. Для ситуации
и учитывая, что
,
включим в список
ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Выполняем шаг 5 алгоритма. Для ситуации
осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Всего таких ситуаций две:
и
.
Для каждой такой ситуации в список
включаем следующие ситуации:
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Рассматриваем добавленные в список
ситуации. Рассмотрение ситуации
ничего не дает. Выполняем шаг 5 алгоритма
для ситуации
.
Осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Таких ситуаций две:
и
.
Для них список
включаем следующие ситуации:
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Больше ситуаций в список включить нельзя.
Начинаем построение списка
.
Выполняем шаг 4 алгоритма. Для ситуации
и учитывая, что
,
включим в список
ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.
Выполняем шаг 6 алгоритма. Для ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Для текущего содержимого списков выполнение шага 5 алгоритма невозможно.
Выполняем шаг 6 алгоритма. Для ситуации
и правила вида
в список
добавим ситуацию вида
.
Для этой же ситуации и правила вида
в список
добавим ситуацию вида
.
Для ситуации
в список
также будут добавлены те же самые
ситуации
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Больше ситуаций в список включить нельзя.
Начинаем построение списка
.
Выполняем шаг 4 алгоритма. Для ситуации
и учитывая, что
,
включим в список
ситуацию вида
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Выполняем шаг 5 алгоритма. Для ситуации
осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Всего таких ситуаций две:
и
.
Для каждой такой ситуации в список
включаем следующие ситуации:
и
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Рассматриваем добавленные в список
ситуации. Рассмотрение ситуации
ничего не дает. Выполняем шаг 5 алгоритма
для ситуации
.
Осуществляем поиск в списке
ситуаций, в которых справа от точки,
стоит нетерминал
.
Такая ситуация одна:
.
Для нее в список
включаем следующую ситуацию:
.
После этого шага списки ситуаций будут
выглядеть следующим образом:
Рассматриваем добавленную в список ситуацию. Выполняем шаг 5 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Такая ситуаций две: и . Для них в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:
Больше ситуаций в список
включить нельзя. Построение списков
закончено. Так как ситуация
,
то цпочка
принадлежит языку, порождаемому заданной
грамматикой
.
