Предсказывающие алгоритмы разбора
Разбор для LL(k)-грамматики удобно осуществлять с помощью так называемого k-предсказывающего алгоритма разбора, k-предсказывающий алгоритм А для КС-грамматики G=(N,,P,S) использует входную ленту, магазин и выходную ленту и, по существу, моделирует работу МП-преобразователя, опустошающего магазин .
Рис.
Этот алгоритм пытается проследить левый вывод цепочки, записанной на его входной ленте.
При чтении анализируемой цепочки, находящейся на входной ленте, входная головка может “заглядывать вперед” на k очередных символов (отсюда число k в названии k-предсказывающего алгоритма). Эту цепочку из k символов, увиденную впереди входной головкой, будем называть аванцепочкой. На рис. аванцепочкой служит подцепочка u входной цепочки wux.
Магазин содержит цепочку X$, где Х - цепочка магазинных символов из алфавита Г, $ – специальный символ для маркировки дна магазина. Выходная лента содержит цепочку , состоящую из номеров правил.
Определение. Конфигурацией предсказывающего алгоритма А называется тройка (x, X, ), где
1) x — неиспользованная часть входной цепочки;
2) X — содержимое магазина (X — верхний символ);
3) — выходная цепочка.
Работу алгоритма А определяет управляющая таблица М:
(Г {$}) *k {(, i), выброс, допуск, ошибка},
где Г * — цепочка, построенная из магазинных символов;
i — номер правила из множества Р.
На каждом такте сначала определяется аванцепочка u и верхний символ магазина Х. Затем рассматривается элемент М(Х, u) управляющей таблицы и в соответствии с его содержанием выполняется одно из 4 действий:
1) если М(Х,
u) = (,
i), то
(x, X,
)
(x, ,
i), т.е. верхний
символ магазина заменяется цепочкой
и к выходу добавляется номер правила
i,
входная головка не сдвигается;
2) если М(а,
u)= «выброс»
и x=a
,
то (x, a,
)
(
,
,
),
т.е. если верхний символ магазина
совпадает с текущим входным символом,
то он выбрасывается из магазина и входная
головка сдвигается на один символ
вправо;
3) если алгоритм достигает конфигурации (e, $, ), работа прекращается и выходная цепочка называется разбором первоначальной входной цепочки. Будем считать, что M($, e) = «допуск» и (e, $, ) — допускающая конфигурация;
4) если M(Х, u)= «ошибка», то разбор прекращается и выдается сообщение об ошибке, а соответствующая конфигурация (x, X, ) называется ошибочной.
Для входной цепочки и ее разбора , получаемого на выходе алгоритма А, будем писать А()=.
Определение. Переводом, определяемым алгоритмом А, называется множество:
(А) = { (, ) | A() = }.
Определение. Алгоритм разбора А для КС-грамматики G называется корректным, если:
1) L(G) = { | A() определено};
2) если A() = , то — левый разбор цепочки .
Управляющая таблица такого алгоритма называется корректной управляющей таблицей для грамматики G.
Пример . 1-предсказывающий алгоритм для простой LL(1)-грамматики G с правилами:
(1) S aAS,
(2) S b,
(3) A a,
(4) A bSA.
Управляющая таблица показана в табл.
Таблица
Верхний символ магазина |
Аванцепочка |
||
|
a |
b |
e |
S |
aAS,1 |
b,2 |
ошибка |
А |
a,3 |
bSA,4 |
ошибка |
a |
выброс |
ошибка |
ошибка |
b |
ошибка |
выброс |
ошибка |
$ |
ошибка |
ошибка |
допуск |
Рассмотрим потактно работу алгоритма для входной цепочки =abbab:
(abbab, S$, e) (abbab, aAS$, 1)
(bbab, AS$, 1)
(bbab, bSAS$, 14)
(bab, SAS$, 14)
(bab, bAS$, 142)
(ab, AS$, 142)
(ab, AS$, 1423)
(b, S$, 1423)
(b, b$, 14232)
(e, $, 14232)
Итак, А(abbab) = 14232. Легко убедиться, что это левый разбор.