5.4. Предсказывающие алгоритмы разбора
Рис.5.2
Этот алгоритм пытается проследить левый вывод цепочки, записанной на его входной ленте.
При чтении анализируемой цепочки, находящейся на входной ленте, входная головка может “заглядывать вперед” на k очередных символов (отсюда число k в названии k-предсказывающего алгоритма). Эту цепочку из k символов, увиденную впереди входной головкой, будем называть аванцепочкой. На рис.5.2 аванцепочкой служит подцепочка u входной цепочки wux.
Магазин содержит цепочку Xa$, где Хa - цепочка магазинных символов из алфавита Г, $ – специальный символ для маркировки дна магазина. Выходная лента содержит цепочку p, состоящую из номеров правил.
Определение. Конфигурацией предсказывающего алгоритма А называется тройка (x, Xa, p), где
1) x — неиспользованная часть входной цепочки;
2) Xa — содержимое магазина (X — верхний символ);
3) p — выходная цепочка. ¨
Работу алгоритма А определяет управляющая таблица М:
(Г È {$}) ´ å *k ® {(b, i), выброс, допуск, ошибка},
где b Î Г * — цепочка, построенная из магазинных символов;
i — номер правила из множества Р.
На каждом такте сначала определяется аванцепочка u и верхний символ магазина Х. Затем рассматривается элемент М(Х, u) управляющей таблицы и в соответствии с его содержанием выполняется одно из 4 действий:
1) если М(Х,
u) = (b,
i), то
(x, Xa,
p)
(x, ba,
p
i), т.е. верхний
символ магазина заменяется цепочкой b
и к выходу добавляется номер правила
i,
входная головка не сдвигается;
2) если М(а,
u)= «выброс»
и x=a
,
то (x, aa,
p)
(
,
a,
p),
т.е. если верхний символ магазина
совпадает с текущим входным символом,
то он выбрасывается из магазина и входная
головка сдвигается на один символ
вправо;
3) если алгоритм достигает конфигурации (e, $, p), работа прекращается и выходная цепочка p называется разбором первоначальной входной цепочки. Будем считать, что M($, e) = «допуск» и (e, $, p) — допускающая конфигурация;
4) если M(Х, u)= «ошибка», то разбор прекращается и выдается сообщение об ошибке, а соответствующая конфигурация (x, Xa, p) называется ошибочной.
Для входной цепочки w и ее разбора p, получаемого на выходе алгоритма А, будем писать А(w)=p.
Определение. Переводом, определяемым алгоритмом А, называется множество:
t(А) = { (w, p) | A(w) = p}. ¨
Определение. Алгоритм разбора А для КС-грамматики G называется корректным, если:
1) L(G) = { w | A(w) определено};
2) если A(w) = p, то p — левый разбор цепочки w. ¨
Управляющая таблица такого алгоритма называется корректной управляющей таблицей для грамматики G.
Пример 5.9. 1-предсказывающий алгоритм для простой LL(1)-грамматики G с правилами:
(1) S ® aAS,
(2) S ® b,
(3) A ® a,
(4) A ® bSA.
Управляющая таблица показана в табл.5.1.
Таблица 5.1
Верхний символ магазина |
Аванцепочка |
||
|
a |
b |
e |
S |
aAS,1 |
b,2 |
ошибка |
А |
a,3 |
bSA,4 |
ошибка |
a |
выброс |
ошибка |
ошибка |
b |
ошибка |
выброс |
ошибка |
$ |
ошибка |
ошибка |
допуск |
Рассмотрим потактно работу алгоритма для входной цепочки w=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. Легко убедиться, что это левый разбор.