5.5. Алгоритмы построения управляющих таблиц для левых анализаторов

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

Вход А1: заданная LL(1)-грамматика G=(N, S, P, S).

Выход А1: управляющая таблица М.

Описание А1. Будем считать, что $ — маркер дна магазина. Таблица М определяется на множестве (N È S È {$})´(S È {e}) следующим образом:

1) если А®a — правило из P с номером i, то М(А, а) = (a, i) для всех (а¹е)ÎFIRST₁(a); если еÎFIRST₁(a), то М(А, b) = (a, i) для всех bÎFOLLOW₁(A);

2) М(а, а) = «выброс» для всех аÎS;

3) М($, е) = «допуск»;

4) в остальных случаях М(X, а)= «ошибка» для XÎ N È S È {$} и аÎS È {e}.

Пример 5.10. Рассмотрим LL(1)-грамматику G с правилами:

(1) E® T ,

(2) ® +T ,

(3) ® e,

(4) T® F ,

(5) ®*F ,

(6) ® e,

(7) F® (E),

(8) F® a.

Применение пунктов 2 – 4 алгоритма А1 при заполнении элементов таблицы М не вызовет затруднений. Проиллюстрируем применение п.1 при заполнении первых двух строк управляющей таблицы (табл. 5.2.)

Таблица 5.2

	а	(	)	+	*	e
E	T , 1	T , 1
			e,3	+ T , 2		e,3
T	F , 4	F , 4
			e, 6	e, 6	*F , 5	e, 6
F	a, 8	(E), 7
a	выброс
(		выброс
)			выброс
+				выброс
*					выброс
$						выброс

Следуя шагу 1 алгоритма А1, определяем элементы первой строки таблицы М для нетерминала Е в правиле (1). Имеем FIRST₁ [ T ] ={ ( , a} , поэтому M [ E , ( ] =[T ,1] и М[E ,a]= =[T ,1], а все остальные элементы этой строки - «ошибки».

Определяем теперь элементы строки для нетерминала . Для правила (2) находим FIRST₁ [+T ] = {+} , поэтому М[ ,+]= = [ + T , 2 ] .

Так как имеется е-правило (3) , то еÎFIRST₁ (a=e), поэтому вычисляем

FOLLOW₁ [ ]={e,)} .

Следовательно, M [ , e] = M[ , )] = [e ,3]. Все остальные элементы строки для - «ошибки» . Продолжая эти рассуждения, заполним все строки таблицы М . Использующий эту таблицу левый анализатор (l - предсказывающий алгоритм разбора ) проанализирует входную цепочку w = (а * а) следующим образом :

[(a*a) , E$ , e ] [(a*a) , T $ , 1] [(a*a) , F $ , 14 ]

[(a*a) , (E) $ ,147] [a*a) ,E) $ ,147]

[a*a) ,T ) $, 1471] [a*a) , F ) $ , 14714]

[a*a) , a ) $ , 147148] [*a) , ) $ , 147148]

[ *a) ,* F ) $ , 1471485 ] [a) , F ) $ , 1471485] [a) , a ) $ , 14714858] [ ) , ) $ , 14714858 ] [ ) , ) $ , 147148586 ] [) , ) $ , 1471485863]

[ e, $ , 1471485863] [ e , $ , 14714858636]

[e,$, 47148586363]

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

Вход А 2: заданная строго LL(k) - грамматика G = (N,S,P,S) .

Выход А2 : управляющая таблица М .

Описание А2 . Этот алгоритм почти идентичен алгоритму А1. Небольшое отличие состоит в следующем :

а) входные символы таблицы М , используемой в А1, необходимо заменить аванцепочками х длиной ½х½ £ k ;

б) в пункте 1 алгоритма А1 выражения FIRST₁(a) и FOLLOW₁(A) заменяются выражениями FIRST_к (a) и FOLLOW_к(A) соответственно .

Пример 5.11. Построим управляющую таблицу М для грамматики G из примера 5.7 :

(1) S ® aAS ,

(2) S ® AbSc,

(3) S ® e,

(4) A ® cbA,

(5) A® a.

Выпишем все аванцепочки длиной ½ х½ £ 2 :

aa,ab,ac,ba,bb, bc,ca,cb,cc,a,b,c,e. Вычислим функции FIRST и FOLLOW, необходимые для построения таблицы по п.1 алгоритма А1 . Такими функциями являются :

FIRST₂ (aAS) = {aa,ac},

FIRST₂ (AbSc) = {ab,cb},

FIRST₂ (cbA) = {cb},

FIRST₂ (a) = {a},

FOLLOW₂ (S) ={e , c , cc}.

Применяя А2, получим управляющую таблицу М (табл.5.3) .

Таблица 5.3

aa

ab

ac

ba

bb

bc

ca

cb

cc

a

b

c

e

S

aAS,1

AbSc,2

aAS,1

AbSc,2

e , 3

е ,3

е , 3

A

cbA,4

a ,5

a

выбр

b

выбр

c

выбр

$

допуск

Левый анализатор (2 - предсказывающий алгоритм разбора), использующий эту таблицу для входной цепочки w=acbacbabaac, выдаст ее левый разбор : 14524153 . Убедитесь в этом самостоятельно .

Мы рассмотрели алгоритмы построения управляющих таблиц левых анализаторов только для строго LL(k) - грамматики. Если грамматика G не является строго LL(k) - грамматикой , то применение алгоритма А2 приведет к построению некорректной таблицы в том смысле , что анализатор на некотором шаге разбора цепочки не сможет однозначно выбрать правило грамматики.

Для класса нестрогих LL(k) - грамматик используются другие алгоритмы, позволяющие построить корректные (не содержащие неоднозначности) управляющие таблицы. Описание этих алгоритмов приведено в монографии А. Ахо и Дж. Ульмана и мы рекомендуем их для самостоятельного изучения.