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}.