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

(4) A®b

Построим соответствующие LL (2)-таблицы. Начнем с T0=TS,{e }. Затем по T0 найдем T1=TA,{e }, далее T2=TS,{aa} и T3=TA,{aa}:

T0 T2

u правило множества u правило множества

e S ®e - aa S ®e -

ab S ®abA {e } ab S ®abA {aa}

T1 T3

u правило множества u правило множества

b A ®b - aa A ®S aa {aa}

aa A ®S aa {aa} ab A ®S aa {aa}

ab A ®S aa {aa} ba A ®b -

По этим таблицам построим управляющую таблицу:

aa ab a ba bb b e

T0 abT1,2 e ,1

T1 T2aa,3 T2aa,3 b,4

T2 e ,1 abT3,2

T3 T2aa,3 T2aa,3 b,4

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

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

$ допуск

Алгоритм построенный по таблице разберет цепочку abaa следующим образом:

(abaa,T0$,e ) |- (abaa,abT1$,2)

|- (baa,bT1$,2)

|- (aa,T1$,2)

|- (aa,T2aa$,23)

|- (aa,aa$,231)

|- (a,a$,231)

|- (e ,$,231)

ТРМ: Число шагов, выполняемых k- предсказывающим алгоритмом с управляющей таблицей, построенной предыдущим алгоритмом по LL (k)- грамматике G, линейно зависит от n, где n - длинна входной цепочки.