4.2.3.Алгоритм построения управляющей таблицы для lr(0)-грамматики без -правил

Рассмотрим управляющую таблицу анализатора для LR(0)-грамматики G₂, приведенную на рис. 4.6. Каждый символ мага­зинного алфавита V_p (грамматическое вхождение символа грам­матики из словаря V в правую часть правила вывода) можно ин­терпретировать как кодированное представление подцепочки из правой части правила, последним символом которой он является.

При такой интерпретации магазинный символ вталкивается только тогда, когда символ из верхушки магазина является ко­дированным представлением префикса подцепочки, представляемой вталкиваемым в магазин символом, или когда вталкиваемый сим­вол представляет новый префикс правой части какого-либо пра­вила. Перенос символов в магазин осуществляется до тех пор, пока в верхушке магазина не окажется символ, являющийся кодирован­ным представлением основы. В этом случае цепочка ма­газинных символов, соответствующих основе, выталкивается из магазина, и в магазин вталкивается символ, который представ­ляет подцепочку, совместимую с подцепочкой, представляемой магазинным символом, расположенным под основой.

Рассмотрим, например, вторую строку управляющей таблицы, отмеченную грамматическим вхождением a₁, которое представля­ет префикс правой части правила (1). Пусть b – текущий вход­ной символ. Согласно правилу (1) за a₁ может следовать грамматическое вхождение нетерминала A₁ или символ, пред­ставляющий подцепочку, порождаемую вхождением A₁. Цепочка, порождаемая A₁, может начинаться либо вхождением b₃ ( прави­ло (3)), либо вхождениемB₄ (правило (4)), которое в свою очередь порождает цепочку, начинающуюся с a₅ или c₆. Следо­вательно, для входного символа b в магазин можно втолкнуть только грамматическое вхождение b₃, которое является кодиро­ванным представлением префикса правой части правила (3).

Строка таблицы, отмеченная маркером дна магазина , соот­ветствует начальной конфигурации алгоритма. В начальный мо­мент времени в магазин можно записать только грамматическое вхождение a₁ или с₂, которые представляют префиксы цепочек, выводимых из начального вхождения S₀, (грамматического вхож­дения начального символа грамматики S, входящего в правую часть нулевого правила вывода пополненной грамматики).

Как следует из таблицы, функция действия f(u) не зависит от текущего входного символа, а определяется только верхним символом магазина. Это означает, что для выбора нужного дей­ствия (переноса или свертки) алгоритм не должен заглядывать вперед на символы входной цепочки и, следовательно, k=0. Алгоритм построения управляющей таблицы для LR(0)-грамматик основывается на рассмотрении пар грамматических вхожде­ний, которые могут быть представлены соседними магазинными символами в процессе разбора допустимых цепочек.

Введем ряд понятий, которые понадобятся для построения управляющей таблицы.

Пусть Х_i и Z_i – грамматические вхождения символов Х и Z в правую часть i-го правила, a Y_j – грамматическое вхождение символа Y в правую часть j-го правила. Определим множество ВПЕРВ( Y_j) (ВХОДИТ_ПЕРВЫМ), в которое включим Y_j и все грамматические вхождения, которыми могут начинаться цепочки, выводимые из Y.

ВПЕРВ(Y_j) = { Y_j }  { X_i  Y   A  X и

Xi - самое левое грамматическое вхождение в правую часть правила A  X} .

Заметим, что если в грамматике есть правила с пустой пра­вой частью, то на последнем шаге вывода они не применяются.

Используя множества ВПЕРВ, определим отношение ВПОД (ВХОДИТ_ПОД) следующим образом:

1. X_i ВПОД Y_j – это множество {( X_i,Y_j )  A X_iZ_i  R и Y_j BПЕРВ(Z_i) } ;

2.  ВПОД Y_j – это множество { ( ,Y_j )  Y_j BПЕРВ(S₀) } .

В последнем определении S₀ – начальное вхождение.

Отношение X_i ВПОД Y_j определяет множество Q грамматичес­ких вхождений X_i, для которых представляющие их магазинные символы могут встретиться в магазине непосредственно под сим­волом, представляющим Y_j.

Отношение ВПОД будем задавать с помощью матрицы, содержа­щей n столбцов и n+1строк, где n – число грамматических вхождений пополненной грамматики G’. Первые n строк и столбцы матрицы отмечены грамматическими вхождениями, а по­следняя отрока – маркером дна магазина. Если X_i ВПОД Y_j, то элемент матрицы, расположенный в строке X_i и столбце Y_j, равен 1.

Пример 4.2.

Построим матрицу отношения ВПОД для грамматики G₂ ('см. рис. 4.3).

Непосредственно из правил вывода (1) и (4) получим:

A₁ ВПОД b₁ и B₄ ВПОД b₄.

Из определения отношения ВПОД  ВПОД Y_j тогда и только тогда, когда Y_j  ВПЕРВ(S₀). Из S можно вывести цепочки:

S  a₁A₁b₁ и S  c₂ .

Следовательно, ВПЕРВ(S₀) = {a₁, c₂, S₀ } и  ВПОД а₁,  ВПОД c₂ и  ВПОД S_0.

Рассмотрим правило (1). Из определения отношения ВПОД сле­дует, что a₁ ВПОД Y_j для всех. Y_j  ВПЕРВ(A₁). Из А можно вы­вести цепочки:

A  b₃S₃ , A  B₄b₄  c₆b₄ , A  B₄b₄  a₅A₅b₄ .

Следовательно, ВПЕРВ (А₁) = { a₅, b₃, c₆, A1, B4 } и a₁ ВПОД a₅, a₁ ВПОД b₃,

a₁ ВПОД c₆, a₁ ВПОД A1, a₁ ВПОД B4.

Поступая подобным образом для правил (3) и (6), получим матрицу отношения ВПОД, приведенную на рис. 4.7.

	S0	a1	A1	b1	c2	b3	S3	B4	b4	a5	A5	c6
S0
a1			1			1		1		1		1
A1				1
b1
c2
b3		1			1		1
S3
B4									1
b4
a5						1		1		1	1	1
A5
c6
	1	1			1

Риc. 4.7

Опишем алгоритм построения управляющей таблицы LR(0)-ана­лизатора (множества LR(0)-таблиц) для LR(0)-грамматики, не содержащей правил с пустой правой частью (-правил). Этот алгоритм можно также использовать для проверки принадлежности КС-грамматики классу LR(0).

Вход

КС-грамматика G = < T, N, S, R > без -правил.

Выход

Множество LR(0)-таблиц для грамматики G или со­общение о том, что грамматика G не является LR(0)-граммати­кой.

Описание алгоритма

1. Построить пополненную грамматику G’ для исходной грам­матики G.

2. Вычислить отношения ВПОД для грамматических вхождений грамматики G’.

3. Определить функции переходов g(Х) следующим образом:

а) Построить таблицу, содержащую по одному столбцу для каждого символа из V  {} и одной отроке для каждого грам­матического вхождения грамматики G’и маркера дна. Элемент в строке, помеченной грамматическим вхождением Х_i или маркером дна , и столбце, отмеченном символом грамматики Y, должен содержать все грамматические вхождения, для которых справед­ливо отношение Х_i ВПОД Y_j. Заметам, что некоторые элементы построенной таким образом таблицы могут содержать более одно­го грамматического вхождения, т.е. таблица может быть неде­терминированной.

б) Интерпретируя построенную таблицу как таблицу конеч­ного автомата (состояния - грамматические вхождения и маркер дна (начальное состояние), а входные символы - символы из V  {}), определить тип автомата: детерминированный или недетерминированный. Недетерминированный автомат преобразо­вать в эквивалентный ему детерминированный автомат.

в) Определить магазинный алфавит V_p так, чтобы каждому состоянию детерминированного конечного автомата соответство­вал ровно один магазинный символ.

В качестве символов алфавита V_p можно использовать любые символы, не являющиеся символами словаря V’ грамматики G’. Для сохранения наглядности цепочек, представимых магазином, будем считать, что символы из V_p совпадают по написанию с соответствующими грамматическими вхождениями. Если магазинный символ представляет множество грамматических вхождений, то индексы магазинных символов будем обозначать строчными ла­тинскими буквами.

г) Заменить совокупности грамматических вхождений, отме­чающих состояния автомата, соответствующими символами из V_p.

Полученная таблица представляет собой таблицу функций пе­реходов g(X) LR(0)-анализатора, причем элементы таблицы, соответствующие переходу в пустое множество состояний, имеют значение ОШИБКА.

4. Определить функции действия f(a) для всех магазинных символов, каждому из которых соответствует одна строка табли­цы. Количество столбцов таблицы f(a) определяется количест­вом символов в T  {}. Элементы таблицы f(a) определяются следую щим образом.

а) Если магазинному символу Т соответствует единственное вхождение S₀, то в строке, отмеченной символом Т, f() = ДО­ПУСК, а все остальные элементы – ОШИБКА.

б) Если магазинному символу Т соответствует только одно грамматическое вхождение X_i, являющееся самым правым вхожде­нием в i-е правило вывода грамматики G, то все элемента строки, помеченной Т, имеют значение (СВЕРТКА, i).

в) Если магазинному символу Т соответствует маркер дна магазина  или все грамматические вхождения, представляемые символом Т, не являются самыми правыми в своих правилах, то в строке, отмеченной Т, f() = ошибка, а значения остальных элементов – ПЕРЕНОС.

г) Если множество вхождений, соответствующее магазинно­му символу Т, содержит начальное вхождение S₀ и хотя бы еще одно вхождение, отличное от которое не является самым правым в своем правиле, то в строке, отмеченной Т, f() = ДОПУСК, а значение всех остальных элементов - ПЕРЕНОС.

Если имеется множество грамматических вхождений, не удов­летворяющих перечисленнымвыше условиям, то G не является LR(0)-грамматикой.

Если построение f(a) закончено успешно, то грамматика является LR(0)-грамматикой, а таблица, полученная объедине­нием таблиц, задающих функции f(a) и g(X) – управляющей таблицей Ʈ LR(0)-анализатора.

Пример 4.3.

Построим управляющую таблицу LR(0)-ана­лизатора для грамматики G₃ (рис. 4.8).

1. О

   1. E  E + T

   2. E  T

   3. T  (E)

   4. T  i

   Рис. 4.8

   пределим пополненную грамматику

G₃’= < T, N  {S}, S, R  { S  E }>.

2. Вычислим отношение ВПОД для грамма­тических вхождений грамматики G₃’. Мат­рица отношения ВПОД изображена на рис. 4.9.

	E0	E1	+1	T1	T2	(3	E3	)3	i4
E0
E1			1
+1				1		1			1
T1
T2
(3		1			1	1	1		1
E3								1
)3
i4
	1	1			1	1			1

Рис.4.9

3. Определим функции переходов g(X).

а) Построим таблицу переходов конечного (недетерминиро­ванного) автомата (рис. 4.10,а).

б) Преобразуем недетер­минированный автомат в экви­валентный ему детерминирован­ный автомат, таблица перехо­дов которого изображена на рис. 4.10,б.

в) Определим множество магазинных символов (рис. 4.11).

Функции переходов g(Х) LR(0)-анализатора для грам­матики G₃ приведены на рис. 4.12.

а)

	E	T	(	)	i	+
E0
E1						+1
+1		T1	(3		i4
T1
T2
(3	E1, E3	T2	(3		i4
E3				)3
)3
i4
	E0, E1	T2	(3		i4

б)

	E	T	(	)	i	+
{  }	{ E0, E1 }	{ T2 }	{ (3 }		{ i4 }
{ E0, E1 }						{ +1 }
{ T2 }
{ (3 }	{ E1, E3 }	{ T2 }	{ (3 }		{ i4 }
{ i4 }
{ +1 }		{ T1 }	{ (3 }		{ i4 }
{ E1, E3 }				{ )3 }		{ +1 }
{ T1 }
{ )3 }

Рис. 4.10

	{E0, E1 }	{ E1, E3 }	{  }	{ T2 }	{ (3 }	{ i4 }	{ +1 }	{ T1 }	{ )3 }
Vp	Ex	Ey		T2	(3	i4	+1	T1	)3

Рис. 4.11

g(X)	E	T	(	)	i	+
	Ex	T2	(3		i4
Ex						+1
T2
(3	Ey	T2	(3		i4
i4
+1		T1	(3		i4
Ey				)3		+1
T1
)3

Рис. 4.12

4. Определим функции дей­ствия f(a).

Построим таблицу, содержащую по одной строке для каждого магазинного символа и одному столбцу для каждого символа из T  {}. Заполним построенную таблицу в соответствии с п. 4.алгоритма.

Для строки таблицы, отмеченной символом , соответствую­щее множество грамматических вхождений состоит из единствен­ного символа , поэтому в этой отроке f() = ошибка, а значения остальных элементов – ПЕРЕНОС (см. п.4,в алгоритма).

Множество грамматических вхождений, соответствующих мага­зинному символу Е_x, содержит два элемента: Е₀ и Е₁. Так как в это множество входит начальное вхождение E₀, а вхождение Е₁ не является самым правым в правиле (1), то в соответствии c п. 4,г алгоритма f() = ДОПУСК, а остальные элементы строки, отмеченные символом Е_x, имеют значение ПЕРЕНОС.

Магазинному символу Т₂ соответствует единственное грамма­тическое вхождение Т₂, которое является самым правым в прави­ле вывода (2) грамматики G₃. Следовательно, значение всех элементов строки, помеченной Т₂, – (СВЕРТКА, 2). Поступая подобным образом для остальных строк, получим таблицу функций переходов f(a),приведенную на рис. 4.13.

f(a)	(	)	i	+	
	П	П	П	П
Ex	П	П	П	П	Д
T2	С,2	С,2	С,2	С,2	С,2
(3	П	П	П	П
i4	С,4	С,4	С,4	С,4	С,4
+1	П	П	П	П
Ey	П	П	П	П
T1	С,1	С,1	С,1	С,1	С,1
)3	С,3	С,3	С,3	С,3	С,3

Рис. 4.13

Поскольку при построении f(a) не возникло конфликтных ситуаций, грамматика G₃ – LR (0)-грамматика. Объединив функции g(X) и f(a) в одну таблицу, получим управляющую таблицу Ʈ LR(0)-анализатора для грамматики G₃.