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

          

Удаление левой рекурсии


Основная трудность при использовании предсказывающего анализа - это нахождение такой грамматики для входного языка, по которой можно построить таблицу анализа с однозначно определенными входами. Иногда с помощью некоторых простых преобразований грамматику, не являющуюся LL(1), можно привести к эквивалентной LL(1)-грамматике. Среди этих преобразований наиболее эффективными являются левая факторизация и удаление левой

рекурсии. Здесь необходимо сделать два замечания. Во-первых, не всякая грамматика после этих преобразований становится LL(1), и, во-вторых, после таких преобразований получающаяся грамматика может стать менее понимаемой.

Непосредственную левую рекурсию, т.е. рекурсию вида A

Удаление левой рекурсии
A
Удаление левой рекурсии
, можно удалить следующим способом. Сначала группируем A-правила:

Удаление левой рекурсии

где никакая из строк

Удаление левой рекурсии
i не начинается с A. Затем заменяем

этот набор правил на

Удаление левой рекурсии

Удаление левой рекурсии

где A' - новый нетерминал. Из нетерминала A можно вывести те же цепочки, что и раньше, но теперь нет левой рекурсии. С помощью этой процедуры удаляются все непосредственные левые рекурсии, но не удаляется левая рекурсия, включающая два или более шага.

Приведенный ниже алгоритм 4.7 позволяет удалить все левые рекурсии из грамматики.

Алгоритм 4.7. Удаление левой рекурсии.

Вход. КС-грамматика G без e-правил (правил вида A

Удаление левой рекурсии
e).

Выход. КС-грамматика G' без левой рекурсии, эквивалентная G.

Метод. Выполнить шаги 1 и 2.

  • Упорядочить нетерминалы грамматики G в произвольном порядке.
  • Выполнить следующую процедуру:

    for (i=1;i for (j=1;j пусть Aj

    Удаление левой рекурсии
    Удаление левой рекурсии
    1 |
    Удаление левой рекурсии
    2 | ... |
    Удаление левой рекурсии
    k

    - все текущие правила для Aj;

    заменить

    все правила вида Ai

    Удаление левой рекурсии
    Aj
    Удаление левой рекурсии

    на правила Ai

    Удаление левой рекурсии
    Удаление левой рекурсии
    1
    Удаление левой рекурсии
    |
    Удаление левой рекурсии
    2
    Удаление левой рекурсии
    | ... |
    Удаление левой рекурсии
    k
    Удаление левой рекурсии
    ;

    }

    удалить правила вида Ai

    Удаление левой рекурсии
    Ai;

    удалить непосредственную левую рекурсию в правилах для Ai;

    }

После (i - 1)-й итерации внешнего цикла на шаге 2 для любого правила вида Ak

Удаление левой рекурсии
As
Удаление левой рекурсии
, где k < i, выполняется s > k. В результате на следующей итерации (по i) внутренний цикл (по j) последовательно увеличивает нижнюю границу по m в любом правиле Ai
Удаление левой рекурсии
Am
Удаление левой рекурсии
, пока не будет m
Удаление левой рекурсии
i. Затем, после удаления непосредственной левой рекурсии

для Ai-правил, m становится больше i.

Алгоритм 4.7 применим, если грамматика не имеет e-правил (правил вида A

Удаление левой рекурсии
e). Имеющиеся в грамматике e-правила могут быть удалены предварительно. Получающаяся грамматика без левой рекурсии может иметь e-правила.



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