Предсказывающие алгоритмы разбора и разбор для LL(1)-грамматик

Разбор для LL(k) -грамматики удобно осуществлять с помощью k-пред­ска­зы­ваю­ще­го алгоритма разбора. Такой алгоритм A для КС-грамматики G=(N, S, P, S), используя входную ленту, магазин и выходную ленту (см. рис. 5.2), пытается проследить левый вывод цепочки, записанной на его входной ленте.

При чтении анализируемой цепочки, находящейся на входной ленте, входная головка может “заглядывать вперед” на k очередных символов. Эту цепочку из k символов, увиденную впереди входной головкой, принято называть аванцепочкой. На рис. 5.2 аванцепочкой служит подцепочка u входной цепочки wuc.

Магазин содержит цепочку Xa$, где Xa – цепочка магазинных символов, X – верхний символ магазина, а $ - специальный символ, используемый в качестве маркера дна магазина. Алфавит магазинных символов (без $) обозначим через G.

Выходная лента содержит цепочку p, состоящую из номеров правил грамматики, применяемых при левом выводе.

Конфигурацию предсказывающего алгоритма разбора будем представлять в виде тройки (j, Xa, p), где

(1) j – еще не проанализированная часть входной цепочки,

(2) Xa – цепочка в магазине (X – верхний символ магазина),

(3) p – цепочка на выходной ленте.

Например, на рис. 5.2 изображена конфигурация (uc, Xa, p).

Работой k -предсказывающего алгоритма A руководит управляющая таблица М, задающая отображение множества (GÈ{$})´S ^*k в множество, содержащее:

(1) (b,i), где bÎG ^*, а i – номер правила (предполагается, что b будет либо правой частью i -го правила, либо некоторым ее представлением),

(2) выброс (извлечение из магазина),

(3) допуск,

(4) ошибка.

Алгоритм анализирует входную цепочку, проделывая последовательность тактов, очень похожих на такты преобразователя с магазинной памятью (см. [10] или раздел 4.1 данного пособия). На каждом такте сначала определяется аванцепочка u и верхний символ магазина X. Затем рассматривается элемент M(X, u) управляющей таблицы. Такты алгоритма A мы опишем в терминах отношения перехода ÷¾, определенного на множестве конфигураций. Пусть u = FIRST_k(j), тогда в алгоритме A возможны следующие такты:

(1) (j, Xa, p)÷¾ (j, ba, pi), если M(X, u) = (b,i). Здесь верхний символ магазина X заменяется цепочкой bÎG ^* (правой частью правила X ® b) и к выходу добавляется номер этого правила i. Входная головка не сдвигается.

(2) (j, a a, p)÷¾ (j¢, a, p), если M(X, u) = выброс и j = aj¢. Когда верхний символ магазина совпадает с текущим входным символом (первым символом аванцепочки), он удаляется из магазина и входная головка сдвигается на один символ вправо.

(3) Если алгоритм достигает конфигурации (e, $, p), работа прекращается и выходная цепочка p называется левым разбором исходной входной цепочки. Будем предполагать, что всегда M($, e) = допуск, и конфигурацию (e, $, p) будем называть допускающей.

(4) Если алгоритм достигает конфигурации (j, Xa, p) и M(X, u) = ошибка, то разбор прекращается и выдается сообщение об ошибке. Эту конфигурацию (j, Xa, p) называют ошибочной.

Алгоритм построения управляющих таблиц для LL(k) -грамматик в случае k >1 довольно сложен, управляющие таблицы имеют большой объем и на практике такие k -предсказывающие алгоритмы не нашли применения. Синтаксис большинства известных языков программирования описывается LL(1) -грамматиками. Поэтому ниже мы и рассмотрим только один важный частный случай, когда G – LL(1) -грамматика.

Алгоритм 5.1. Построение управляющей таблицы для LL(1)-грамматики.

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

Выход. Управляющая таблица M для грамматики G.

Метод. Будем считать, что $ – маркер дна магазина. Таблица M определяется на множестве (N È S È {$}) ´ (S È {e}) следующим образом:

(1) Если A ® a – правило из P с номером i, то M(A, a) = (a, i) для всех а ¹ e, принадлежащих FIRST₁(a). Если e Î FIRST₁(a), то M(A, b) = (a, i) для всех
b Î FOLLOW₁(A).

(2) M(a, a) = выброс для всех a Î S.

(3) M($, e) = допуск.

(4) В остальных случаях M(X, a) = ошибка для X Î N È S È {$} и a Î S È {e}. 

Пример 5.7. Рассмотрим построение управляющей таблицы для грамматики G с набором правил:

С помощью теоремы 5.2 можно проверить, что G – LL(1) -грамматика. Предложенная грамматика ни что иное, как результат устранения левой рекурсии из фрагмента хорошо известной нам не LL -грамматики арифметических выражений с правилами:

Е ®E+TôT T ® T*FôF F ® (E)ôa

На шаге (1) алгоритма 5.1 найдем элементы строки таблицы для нетерминала E. Здесь FIRST₁(TE¢) = {(, a}, так что M (E, () = (TE¢, 1) и M (E, a) = (TE¢, 1). Все остальные элементы этой строки – ошибки. Вычислим теперь строку для нетерминала E¢. Заметим, что FIRST₁(+TE¢) = +, так что M (E¢, +) = (+TE¢, 2). Так как есть правило
E¢ ® e, мы должны вычислить FOLLOW₁(E¢) = {e,) }. Таким образом, M (E¢, e) = M (E¢,)) = (e, 3). Каждый из остальных элементов строки для E¢ – ошибка. Продолжая в том же духе, получим управляющую таблицу для G, представленную на рис. 5.3, где ячейки, в которых должна стоять ошибка, оставлены пустыми.

1 -предсказывающий алгоритм разбора проанализирует цепочку (a*a) следующим образом:

[(a*a), E$, e] ú¾ [(a*a), TE¢$, 1] ú¾ [(a*a), FT¢E¢$, 14] ú¾

[(a*a), (E)T¢E¢$, 147] ú¾ [a*a), E)T¢E¢$, 147] ú¾ [a*a), TE¢)T¢E¢$, 1471] ú¾

[a*a), FT¢E¢)T¢E¢$, 14714] ú¾ [a*a), aT¢E¢)T¢E¢$, 147148] ú¾

[*a), T¢E¢)T¢E¢$, 147148] ú¾ [*a), *FT¢E¢)T¢E¢$, 1471485] ú¾

[a), FT¢E¢)T¢E¢$, 1471485] ú¾ [a), aT¢E¢)T¢E¢$, 14714858] ú¾

[), T¢E¢)T¢E¢$, 14714858] ú¾ [), E¢)T¢E¢$, 147148586] ú¾

[),)T¢E¢$, 1471485863] ú¾ [e, T¢E¢$, 1471485863] ú¾

[e, E¢$, 14714858636] ú¾ [e, $, 147148586363] 

Поскольку действия при LL(1) -разборе зависят только от пары “очередной нетерминал - очередной символ”, этот разбор легко запрограммировать, используя и другой не универсальный, но зато довольно прозрачный метод рекурсивного спуска.

Поиск по сайту: