Основы конструирования компиляторов

          

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


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

Конструирование таблицы предсказывающего анализатора
Конструирование таблицы предсказывающего анализатора
- правило вывода грамматики и a
Конструирование таблицы предсказывающего анализатора
FIRST(
Конструирование таблицы предсказывающего анализатора
). Тогда анализатор делает развертку A по
Конструирование таблицы предсказывающего анализатора
, если входным символом является a. Трудность

возникает, когда

Конструирование таблицы предсказывающего анализатора
= e или
Конструирование таблицы предсказывающего анализатора
Конструирование таблицы предсказывающего анализатора
*e. В этом случае нужно развернуть A в
Конструирование таблицы предсказывающего анализатора
, если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и $
Конструирование таблицы предсказывающего анализатора
FOLLOW(A).

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

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

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

Конструирование таблицы предсказывающего анализатора
N, a
Конструирование таблицы предсказывающего анализатора
T
Конструирование таблицы предсказывающего анализатора
{$}.

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

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

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

  • Для каждого терминала a из FIRST(
    Конструирование таблицы предсказывающего анализатора
    ) добавить A
    Конструирование таблицы предсказывающего анализатора
    Конструирование таблицы предсказывающего анализатора
    к M[A, a].
  • Если e
    Конструирование таблицы предсказывающего анализатора
    FIRST(
    Конструирование таблицы предсказывающего анализатора
    ), добавить A
    Конструирование таблицы предсказывающего анализатора
    Конструирование таблицы предсказывающего анализатора
    к M[A, b] для каждого

    терминала b из FOLLOW(A). Кроме того, если e

    Конструирование таблицы предсказывающего анализатора
    FIRST(
    Конструирование таблицы предсказывающего анализатора
    ) и $
    Конструирование таблицы предсказывающего анализатора
    FOLLOW(A), добавить A
    Конструирование таблицы предсказывающего анализатора
    Конструирование таблицы предсказывающего анализатора
    к M[A, $].
  • Положить все неопределенные входы равными «ошибка».

Пример 4.5. Применим алгоритм 4.6 к грамматике из примера 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.6 для этой грамматики, приведена на рис. 4.3.



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