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

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

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

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

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

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

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

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

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

Например, на рис. 5.2 изображена конфигурация (u , X, ).

Работой k-предсказывающего алгоритма A руководит управляющая таблица М, задающая отображение множества ({$}) ^k в множество, содержащее:

(1) (,i), где  ^, а i – номер правила (предполагается, что  будет либо правой частью i-го правила, либо некоторым ее представлением),

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

(3) допуск,

(4) ошибка.

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

(1) (, X, ) (, , i), если M(X, u)  (,i). Здесь верхний символ магазина X заменяется цепочкой  ^ (правой частью правила X  ) и к выходу добавляется номер этого правила i . Входная головка не сдвигается.

(2) (, a , ) (, , ), если M(X, u)  выброс и   a. Когда верхний символ магазина совпадает с текущим входным символом (первым символом аванцепочки), он удаляется из магазина и входная головка сдвигается на один символ вправо.

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

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

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

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

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

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

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

(1) Если A   – правило из P с номером i, то M(A, a) = (, i) для всех а  , принадлежащих FIRST₁(). Если   FIRST₁(), то M(A, b) = (, i) для всех b  FOLLOW₁(A).

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

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

(4) В остальных случаях M(X, a) = ошибка для X  N    {$} и a    {}. 

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

(1)	E  T E	(2)	E   T E
(3)	E  	(4)	T  F T 
(5)	T    F T 	(6)	T   
(7)	F  ( E )	(8)	F  a

С помощью теоремы 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  , мы должны вычислить FOLLOW₁(E) = {, ) }. Таким образом, M ( E,  ) = M ( E, ) ) = (, 3). Каждый из остальных элементов строки для E – ошибка. Продолжая в том же духе, получим управляющую таблицу для G, представленную на рис. 5.3, где ячейки, в которых должна стоять ошибка, оставлены пустыми.

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

[(aa), 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]  [, TE$, 1471485863] 

[, E$, 14714858636]  [, $, 147148586363] 

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