LL(k)-грамматики
(2) (2) [a, a]=выброс для всех aОE.
(3) (3) M[$, e]=допуск.
(4) (4) В остальных случаях M[X, a]=ошибка для XОNИEИ{$} и aОEИ{e}.
ТРМ: Предложенный алгоритм строит корректную управляющую таблицу для LL (1) — грамматики G.
Разбор для LL (k) — грамматик.
Построим управляющую таблицу для произвольной грамматики. Если грамматика сильная, то можно применить предыдущий алгоритм с аванцепочками расширенными до k символов. В противном случае возникает несколько проблем. В 1-м предсказывающем алгоритме разбора в магазин помещались только символы из EИN и оказывалось, что для однозначного определения очередного применяемого правила достаточно знать нетерминальный символ наверху магазина и текущий входной символ. Для не сильных грамматик этого может оказаться недостаточно.
ПРМ: Возьмем грамматику S®aAaa|bAba A®b|e Если даны нетерминал A и аванцепочка ba, то не известно, какое из правил надо применить.
Неопределенности такого рода однако можно разрешить, связав с каждым нетерминалом и частью левовыводимой цепочки (которая может оказаться справа), специальный символ, называемый LL (k) — таблицей. По данной аванцепочке LL (k) — таблица будет однозначно определять какое правило надо применить на очередном шаге вывода.
ОПР: Пусть E — некоторый алфавит. Если L1 и L2 — подмножества E, то положим L1 Еk L2 = { w | для некоторых xОL1 и yОL2 либо w = xy, если |xy| £k либо w состоит из первых k символов цепочки xy } ЛМА: Для любой КС- грамматики G=(N, E, P, S) и любых a`, b`О (NИE): FIRSTk (a`b`) =FIRSTk (a`) Еk FIRSTk (b`) ОПР: Пусть G=(N, E, P, S) — КС- грамматика. Для каждых AОN и LНE определим LL (k) — таблицу Ta, l, соответствующую A и L, как функцию T (u), значением которой служит: (1) (1) ошибка, если в P нет такого правила A®a`, что FIRSTk (a`) Еk L содержит u; (2) (2) =(A®a`, <Y1, Y2… Ym>), если A®a` единственное правило из P, для которого FIRSTk (a`) Еk L содержит u; (3) (3) е определено, если в множестве найдутся два и более правила (эту ситуацию называют конфликтом между правилами) На нормальном языке это означает что вырабатывается значение ошибка, если u вообще не является цепочкой грамматики, возвращается правило если оно существует и только одно и если несколько правил — то значение не определяется.
АЛГ 2: Построение LL (k) — таблиц.
Вход: LL (k) -грамматика G=(N, E, P, S).
Выход: Множество TG LL (k) — таблиц, необходимых для построения управляющей таблицы для G.
Метод: (1) (1) построить LL (k) — таблицу T0, соответствующую S и {e}.