Конструирование таблицы предсказывающего анализатора

Для конструирования таблицы предсказывающего анализатора по грамматике G может быть использован алгоритм, основанный на следующей идее. Предположим, что A

- правило вывода грамматики и

. Тогда анализатор делает развертку A по

, если входным символом является a. Трудность возникает, когда

= e или

. В этом случае нужно развернуть A в

, если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и

Алгоритм 4.7. Построение таблицы предсказывающего анализатора.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Таблица M[A; a] предсказывающего анализатора,

Метод. Для каждого правила вывода A

грамматики выполнить шаги 1 и 2. После этого выполнить шаг 3.

(1) Для каждого терминала a из FIRST(R) добавить A

R к M[A; a].

(2) Если

, добавить A

R к M[A; b] для каждого терминала b из FOLLOW(A). Кроме того, если

, добавить A

к M[A; $].

(3) Положить все неопределенные входы равными "ошибка".

Пример 4.5. Применим алгоритм 4.7 к грамматике из примера 4.3. Поскольку FIRST(TE') = FIRST(T) = {(, id }, в соответствии с правилом вывода E

TE' входы M[E, ( ] и M[E, id ] становятся равными E

TE'.

В соответствии с правилом вывода E'

+TE' значение M[E', +] равно E'

+TE'. В соответствии с правилом вывода E'

e значения M[E', )] и M[E', $] равны E'

e, поскольку FOLLOW(E') = { ), $}.

Таблица анализа, построенная по алгоритму 4.7. для этой грамматики, приведена в таблица 4.3.

Содержание раздела