Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
эл.лекции.doc
Скачиваний:
4
Добавлен:
01.05.2025
Размер:
7 Мб
Скачать
☆

Алгоритм разбора Эрли

Вход: КС-грамматика и входная цепочка .

Выход: Список разбора для цепочки .

Метод:

Сначала строим список :

  1. Если , то добавить ситуацию вида в список .

Далее выполняем шаги 2 и 3 до тех пор, пока в можно включать новые ситуации.

  1. Если (Примечание. Заметим, что может быть ), включить в ситуацию для любого .

  2. Если , то для каждого правила включить в ситуацию (при условии, что она еще не там).

После того, как построены , строится :

  1. Для каждой ситуации , для которой , включить в ситуацию .

Далее выполнять шаги 5 и 6, пока в можно включать новые ситуации.

  1. Пусть . Осуществляем поиск в ситуации вида . Для каждой из них включить в ситуацию .

  2. Пусть . Для каждого включить в ситуацию .

Примечание. Заметим, что рассмотрение ситуации, в которой справа от точки стоит терминал, на шагах 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 алгоритма для ситуации . Осуществляем поиск в списке ситуаций, в которых справа от точки, стоит нетерминал . Такая ситуаций две: и . Для них в список включаем следующие ситуации: и . После этого шага списки ситуаций будут выглядеть следующим образом:

Больше ситуаций в список включить нельзя. Построение списков закончено. Так как ситуация , то цпочка принадлежит языку, порождаемому заданной грамматикой .