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

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

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

Метод:

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

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

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

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

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

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

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

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

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

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

Примечание. Заметим, что рассмотрение ситуации, в которой справа от точки стоит терминал, на шагах 2, 3 и 5, 6 не дает новых ситуаций.

Пример №1

Задание.

Пусть задана грамматика с правилами

и пусть – входная цепочка.

Дата добавления: 2014-01-07