Режим переполоха. Преобразование входного текста в постфиксную форму записи

Режим переполоха

Идея вытекает из рассмотрения процесса синтаксического анализа программы, содержащей, например, такую цепочку:

…

x = ( x + ) ) * ) ( ( + y ;

…

Множественные ошибки обнаруживаются при попытке разбора нетерминала Выражение в правиле, выглядящем приблизительно так:

ОператорПрисваивания : Выражение ;

Можно поступить так:

1.  В тот момент, когда будет обнаружена невозможность нейтрализации одиночной ошибки, приступить к поиску символа «;». Все остальные символы просто пропускать.

2.  При обнаружении символа «;» (в тот момент, когда этот символ стал текущим) модифицировать стек и состояние автомата так, как будто бы

a.  нисходящий автомат вернулся туда, откуда был выполнен переход для разбора нетерминала Выражение

b.  восходящий выполнил свертку основы для нетерминала Выражение и операцию перехода (Go) по этому нетерминалу.

3.  Вернуться к анализу текста.

Такая схема организации работы называется «режим переполоха».

В общем случае ситуация выглядит так:

Уровень восстанавливаемого дерева разбора можно представить себе так:

a g ▼j b

Существует вывод N => g j

В момент включения режима переполоха нужно:

-  определить множество ожидаемых символов (либо предшественников цепочки b, либо последователей нетерминала N);

-  определить состояние автомата, в котором он должен оказаться в момент выхода из режима переполоха;

-  определить, каким должно быть содержимое стека автомата к этому моменту.

Нисходящий автомат с несколькими состояниями