Реферат: LL(k) - Грамматики
Неопределенности такого рода однако можно разрешить, связав с каждым нетерминалом и частью левовыводимой цепочки (которая может оказаться справа), специальный символ, называемый LL (k)- таблицей . По данной аванцепочке LL (k)- таблица будет однозначно определять какое правило надо применить на очередном шаге вывода.
ОПР: Пусть E - некоторый алфавит. Если L 1 и L 2 - подмножества E , то положим L 1 Åk L 2 = {
w | для некоторых xÎL 1 и yÎL 2
либо 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) =ошибка, если в P нет такого правила A®a` , что FIRSTk(a` ) Åk L содержит u;
(2) =(A®a` ,<Y1,Y2...Ym>), если A®a` - единственное правило из P, для которого FIRSTk(a` ) Åk L содержит u;
(3) не определено, если в множестве найдутся два и более правила (эту ситуацию называют конфликтом между правилами)
На нормальном языке это означает что вырабатывается значение ошибка, если u вообще не является цепочкой грамматики, возвращается правило если оно существует и только одно и если несколько правил - то значение не определяется.
АЛГ 2: Построение LL (k)- таблиц.
Вход: LL (k)- грамматика G =(N ,E ,P ,S ).
Выход: Множество TG LL (k)- таблиц, необходимых для построения управляющей таблицы для G .
Метод:
(1) Построить LL (k)- таблицу T0, соответствующую S и {e }.
(2) Положить вначале TG={T0}.
(3) Для каждой LL(k)-таблицы TÎTG, содержащей элемент T(u)=(A®x0B1x1...Bmxm,<Y1,Y2...Ym>) включить в TG LL (k)- таблицу T для 1£i£m, если T еще не входит в TG.
(4) Повторять шаг 3 пока в TG можно включать новые таблицы.
ПРМ: Построим соответствующее множество LL (2)- таблиц для грамматики S ®aAaa|bAba и A®b|e . Начнем с TG={TS,{e }} . Так как TS,{e }(aa)=( S ®aAaa,{aa}), то в TG надо включить TA,{aa}. Аналогично, так как T0(bb)=( S ®bAba,{ba}), то в TG нужно так же включить . (Элементы LL (2)- таблиц TA,{aa} и TA,{ba}, отличные от значения ошибка, приведены в таблице ниже). Сейчас TG={TS,{e},TA,{aa},TA,{ba}}, и алгоритм уже не может включить в TG новых таблиц, так что это три LL (2)- таблицы образуют множество соответствующее грамматике.
TA,{aa} TA,{ba}
u правило множества u правило множества
ba A ® b - ba A ® e -
aa A ® e - aa A ® b -
Теперь дадим алгоритм, которым можно построить корректную управляющую таблицу по соответствующему множеству LL (k)- таблиц. Управляемый этой таблицей k- предсказывающий алгоритм будет в качестве магазинных символов употреблять вместо нетерминалов LL (k)- таблицы.
АЛГ 3: Построение управляющей таблицы для LL (k)- грамматики.
Вход : LL (k)- грамматика и соответствующее множество TG LL (k)- таблиц.