Восходящий синтаксический анализ

     В данной части будет показано, что для каждой LR (k)-грамматики G = (N, Σ, Р, S) можно построить детерминированный правый анализатор, который ведет себя следующим образом.

     Прежде  всего, этот анализатор строится по пополненной грамматике G’. Ведет он себя во многом так же, как анализатор типа „перенос — свертка" за исключением того, что после каждого символа грамматики в магазин будет записываться специальный информационный символ, называемый LR (k)-таблицей. Эти LR (k)-таблицы помогут определять, что надо делать на очередном шаге — свертку или перенос, и в случае свертки — какое правило при этом применить.

     Для описания поведения LR(k)-анализатора рассмотрим пример. Возьмем грамматику G с правилами  1) S→SaSb

     2) S→e

которая, является LR(k)-грамматикой. Пополненная грамматика G' состоит из правил

     0) S’→S

     1) S→SaSb

     2) S→e

LR(1)-анализатор для грамматики G приведен на рис. 3.

Рис. 3. LR (k)-анализатор для грамматики G (i — свертка, при которой применено i-e правило, S —перенос, A—допуск, X — ошибка).

     LR (k)-анализатор для КС-грамматики G —это не что иное, как множество строк большой таблицы, каждая строка которой называется LR (k)-таблицей. Одна строка, здесь это T₀, выделяется в качестве начальной LR (k)-таблицы. Каждая LR (k)-таблица состоит из двух функций — функции действия f и функции переходов g:

     1) Аргументом функции .действия f служит цепочка u Σ^*k (она называется аванцепочкой), а соответствующее значение f(u) — один из символов “действий”: перенос, свертка i, ошибка или допуск.

     2) Аргументом функции переходов g служит символ X N Σ, а соответствующее значение g (X) — либо имя некоторой LR(k)- таблицы, либо ошибка.

     LR-анализатор  ведет себя так же, как алгоритм типа „перенос—свертка", используя в процессе работы магазин, входную и выходную ленты. Вначале магазин содержит начальную LR(k)-таблицу T₀ и ничего больше. На входной ленте находится анализируемая цепочка, а выходная лента вначале пустая. Если предположить, что надо разобрать входную цепочку aabb, то начальной конфигурацией анализатора будет (T₀, aabb, e). Затем разбор будет осуществляться согласно следующему алгоритму.

LR (k)-алгоритм разбора

     Вход. Множество LR(k)-таблиц для LR(k)-грамматики G=(N, Σ, Р, S) с таблицей T₀ выделенной в качестве начальной, и входная цепочка z Σ*, которую надо разобрать.

     Выход. Если z L(G), то правый разбор цепочки z в грамматике G, в противном случае сигнал об ошибке.

     Метод. Выполнять шаги 1) и 2) до тех пор, пока не будет допущена входная цепочка или не встретится сигнал об ошибке. В случае допуска цепочка на выходной ленте представляет собой правый разбор цепочки z.

     1) Определяется аванцепочка u, состоящая из k очередных входных символов (или менее чем k символов, если обрабатывается конец входной цепочки).

     2) Функция действия f таблицы, расположенной наверху магазина, применяется к аванцепочке u.

(а) Если  f(u) = перенос, то следующий входной символ, скажем а, переносится со входа в магазин. К а применяется функция переходов g верхней таблицы магазина и определяется новая таблица, которую надо поместить наверху магазина. После этого вернуться к шагу 1). Если следующего входного символа нет или значение g (а) не определено, остановиться и выдать сигнал об ошибке.

(б) Если f(u) = свертка i и A → α—правило с номером i, то из верхней части магазина устраняются 2|α| символов) и на выходной ленте записывается номер правила i. Наверху магазина оказывается тогда новая таблица Т', и ее функция переходов применяется к A для определения следующей таблицы, которую надо поместить наверху магазина. Помещаем А и эту новую таблицу наверху магазина и переходим к шагу A).

(в) Если  f(u) = ошибка, разбор прекращается (на практике надо перейти к процедуре исправления ошибок).

(г) Если  f(u) = допуск, остановиться и объявить цепочку, записанную на выходной ленте, правым разбором первоначальной входной цепочки.

     Рассмотрим  пример использования только что  рассмотренного алгоритма. Пусть алгоритм начинает работу в начальной конфигурации (T₀, aabb, e). Будем пользоваться LR (1)-таблицами, приведенными на рис. 3. Здесь аванцепочкой служит а. Значением функции действия таблицы T₀ на цепочке а будет свертка 2, где 2— номер правила S → е. На шаге 26) надо устранить из магазина 2|е| = 0 символов и выдать номер 2. Верхней

таблицей в  магазине все еще остается T₀. Так как функция переходов таблицы T₀ на аргументе S принимает значение T₁, то наверху магазина помещаем ST₁ — это приводит к конфигурации (T₀ST₁, aabb, 2).

     Пройдем еще раз через этот цикл. Аванцепочкой по-прежнему служит а. Значением функции  действия таблицы T₁ на а будет перенос, так что символ а переносим со входа в магазин. Функция переходов таблицы T₁ на аргументе а принимает значение T₂, так что после этого шага получится конфигурация (T₀ST₁aT₂, abb,2).

     Продолжая в том же духе, LR-анализатор сделает  такую последовательность тактов:      (T₀, aabb ,e) |— (T₀ST₁, aabb, 2)

                             |— (T₀ST₁aT₂, abb, 2)

     |—  (T₀ST₁aT₂ST₃, abb, 22)

     |—  (T₀ST₁aT₂ST₃aT₄, bb, 22)

     |—  (T₀ST₁aT₂ST₃aT₄ST₆, bb, 222)

     |—  (T₀ST₁aT₂ST₃aT₄ST₆bT₇, b, 222)

     |—  (T₀ST₁aT₂ST₃, b, 2221)

     |—  (T₀ST₁aT₂ST₃bT₅, e, 2221)

     |—  (T₀ST₁, e, 22211)

     Заключение

     Достоинства алгоритма восходящего разбора:

• Наличие стандартного алгоритма вывода;
• Возможность предсказать результат на любом этапе разработки программы;
• Простота отладки правил (но не алгоритма вывода!);
• Средняя сложность реализации в "процедурных" языках и языках логического программирования.

     Недостатки  алгоритма:

• Сложность реализации в алгоритме коэффициентов уверенности;
• Время выполнения вывода растёт экспоненциально с ростом числа правил;
• ("Неустранимый" недостаток данной цепочки рассуждений). При организации прямой цепочки рассуждений на каждом шаге терминальному символу ставится в соответствие нетерминальный символ ("основа"). Как найти эту основу и то, к чему она должна приводиться? Именно этот недостаток, требующий "подбора методом проб и ошибок", и является основанием для недостатка 2;
• Следствием недостатка №3 является то, что "в системе с реальным числом правил имеется столь много подразумеваемых (скрытых) фактов, что, будучи обнаружены, они затмят те несколько фактов, которые действительно представляют интерес и являются полезными".

     Поэтому в реальных системах в прямую цепочку  вывода часто добавляют элементы системы продукций. Это позволяет  изменить приоритеты в обработке  правил, что позволяет сократить  время работы программы и "отсечь" бесперспективные "ветви вывода".