Реферат: LL(k) - Грамматики

Метод: M определяется на множестве (TGÈEÈ{$})´E*k следующим образом:

(1) Если A®x0B1x1...Bmxm - правило из P с номером i и TA,LÎTG, то для всех u, для которых TA,L(u)=(A®x0B1x1...Bmxm,<Y1...Ym>) полагаем M[TA,L,u]=(x0TB1,Y1...TBm,Ymxm,i).

(2) M[a,av]=выброс для всех vÎE*(k-1).

(3) M[$,e ]=допуск.

(4) В остальных случаях M[X,u]=ошибка

(5) TS,{e } - начальная таблица.

ПРМ: Построим управляющую таблицу для LL (2)- грамматики

(1) S ®aAaa

(2) S ®bAba

(3) A®b

(4) A®e

используя соответствующее ей множество LL (2)-таблиц, найденное в предыдущем примере. Алгоритм должен выдать таблицу:

aa ab a ba bb b e

T0 aT1aa,1 aT1aa,1 bT2ba,2

T1 e ,4 b,3

T2 e ,4 b,3

a выброс выброс выброс

b выброс выброс выброс

$ допуск*

где T0=TS,{e}, T1=TA,{aa} и T2=TA,{ba}. Подразумевается, что в пустых ячейках - ошибка. Допуск* находится в последней колонке. Для входной цепочки bba 2-предсказывающий алгоритм выдаст такую последовательность тактов:

(bba,T0$,e ) |- (bba,bT2ba$,2)

|- (ba,T2ba$,2)

|- (ba,ba$,24)

|- (a,a$,24)

|- (e ,$,24)

ТРМ: Описанный алгоритм строит для LL (k)- грамматики G =(N ,E ,P ,S ) корректную таблицу, управляющую работой соответствующего k- предсказывающего алгоритма.

ПРМ: Рассмотрим LL (2)- грамматику G с правилами:

(1) S ®e

(2) S ®abA