3.9. LR(k)-грамматики

Пред.Страница След.Страница Раздел Содержание

Детерминированные восходящие распознаватели, так же как и нисходящие, могут быть построены не для всякой КС-грамматики, а только для определенных подклассов таких грамматик. Наиболее широким подклассом КС-грамматик являются LR(k)-грамматики. Эти грамматики обеспечивают распознавание цепочки при просмотре слева направо, об этом говорит буква L (Left) в названии грамматики, и позволяют выполнить правостороннее сворачивание, это показывает буква R (Right) в названии. Параметр k говорит о том, что для определения того правила грамматики, которое нужно применить для сворачивания цепочки, потребуется просмотреть не более k еще не прочитанных символов входной цепочки.
В общем случае алгоритмы построения распознавателей дл LR(k)-грамматик оказываются достаточно сложными и трудоемкими, поэтому на практике чаще всего используют подклассы LR(k)-грамматик: LR(0), или SLR(1)—простые (Simple) LR(1)-грамматики, позволяющие относительно просто выполнять построение восходящих распознавателей. При этом для каждого подкласса LR(k)-грамматик используется свой алгоритм построения. Если задана КС-грамматика, то определить ее принадлежность к одному из подклассов грамматик LR(k) можно только путем анализа возможности построения для нее с помощью определенного алгоритма детерминированного распознавателя. Учитывая последнее обстоятельство, условимся называть распознаватели по подклассу соответствующих грамматик: LR(0)-распознаватель или SLR(1)-распознаватель.
Прежде чем перейти к рассмотрению правил построения восходящих распознавателей, введем несколько вспомогательных понятий.
Условимся называть символы полного словаря грамматики грамматическими символами. Каждый грамматический символ может входить в разные правила грамматики и, более того, появляться в одном и том же правиле несколько раз. При этом положение символа в правиле грамматики может показывать, какое действие нужно выполнить: перенос или свертку, а также какие грамматические символы могут за ним следовать. Это обстоятельство позволяет связать позицию грамматического символа в правиле грамматики с понятием состояния распознавателя. Для удобства дальнейших рассуждений введем понятие грамматического вхождения.

Определение.Грамматическое вхождение символа грамматики
                         задается номером правила и номером позиции,
                        которая указывает место символа в правой части
                        правила, полагая, что самый левый символ правой
                        части правила является первым.

Условимся обозначать грамматические вхождения символов, входящих в правую часть правила только один раз, с помощью одного индекса, равного номеру правила. Примем также, что каждая грамматика содержит грамматическое вхождение, называемое начальным вхождением. Это вхождение задается начальным символом грамматики.

Построение таблиц распознавателя.
Алгоритм работы распознавателя.

Для грамматических вхождений определим две функции ВПЕРВ и ВПОСЛЕ. Функция ВПЕРВ по аналогии с функцией ПЕРВ(Y) определяет множество грамматических вхождений, которые могут стоять на первом месте в цепочках, выводимых из Y. Это множество строится следующим образом: в него входит символ Y и все символы, начинающие промежуточные цепочки, выводимые из Y без применения аннулирующих правил. Формально вторая часть утверждения означает, что X Î ВПЕРВ(Y), если
     Y Þ* <L>b Þ Xab
и X является самым левым вхождением в правой части правила <L> ® Xa.

В качестве примера построим функции ВПЕРВ для символов следующей грамматики, не содержащей аннулирующих правил:

Г_{3. 12}:
<I> ® a₁<I₁₂><I₁₃>b₁
<I> ® с₂
Эти функции имеют следующий вид:
     ВПЕРВ(a₁) = {a₁},
     ВПЕРВ(<I₁₂>) = {<I₁₂>, a₁, с₂},
     ВПЕРВ(<I₁₃>) = {<I₁₃>, a₁, с₂},
     ВПЕРВ(b₁) = {b₁},
     ВПЕРВ(<C₂>) = {с₂},
     ВПЕРВ(<I₀>) = {<I₀>, a₁, с₂}.
Функция ВПОСЛЕ(Y) является аналогом функции СЛЕД. Она определяет множество грамматических вхождений, которые могут встречаться непосредственно после Y в цепочках, выводимых из начального символа грамматики. Правило вычисления функции ВПОСЛЕ(Y) можно записать так: если в правой части некоторого правила после Y непосредственно следует Z, то
     ВПОСЛЕ(Y) = ВПЕРВ(Z).
При построении распознавателей необходимо учитывать наличие маркера дна, поэтому, забегая вперед, сформулируем еще одно правило вычисления этой функции: если Y является маркером дна магазина, то
     ВПОСЛЕ(h₀) = ВПЕРВ(<I₀>),
где <I₀>—начальное вхождение.

Для грамматики Г_{3. 12}функции ВПОСЛЕ имеют вид
     ВПОСЛЕ(a₁) = {<I₁₂>, a₁, с₂},
     ВПОСЛЕ(<I₁₂>) = {<I₁₃>, a₁, с₂},
     ВПОСЛЕ(<I₁₃>) = {b₁},
     ВПОСЛЕ(b₁) = Æ,
     ВПОСЛЕ(<C₂>) = Æ,
     ВПОСЛЕ(<I₀>) = Æ,
     ВПОСЛЕ(h₀) = {<I₀>, a₁, с₂}.
Согласно определению функции ВПОСЛЕ(Y) она определяет грамматические вхождения, которые могут следовать после вхождения Y в выводимых или сворачиваемых цепочках. Например, если очередным грамматическим вхождением является символ a₁и за нимдолжен следовать грамматический символ I, то по значению функции ВПОСЛЕ( a₁ ) можно определить, что символу I в этом случае соответствует вхождение I₁₂. Таким образом, при сворачивании с помощью функции ВПОСЛЕ(Y) можно определить, какому грамматическому вхождению соответствует очередной грамматический символ сворачиваемой цепочки.
Если взять последовательность грамматических символов, то пользуясь функциями ВПОСЛЕ ей можно поставить в соответствие последовательность грамматических вхождений. В этом случае удобно рассматривать грамматические вхождения, как состояни конечного автомата, а грамматические символы, как входные воздействия. Смену состояний этого автомата можно представить в виде таблицы переходов, которая строится следующим образом. Каждому грамматическому вхождению выделим одну строку таблицы, а каждому грамматическому символу—один столбец. Клетки таблицы заполняются элементами функций ВПОСЛЕM таким образом, что элемент X_kÎ ВПОСЛЕ(Y_j) заносится в клетку, находящуюся на пересечении строки Y_j и столбца, отмеченного грамматическим символом X.

Таблица переходов распознавателя, построенная для рассматриваемой грамматики, имеет вид:

Таблица 3.1
	a	b	<C>	<I>
a₁	a₁		<C₂>	<I₁₂>
<I₁₂>	a₁		<C₂>	<I₁₃>
<I₁₃>		b₁
b₁
<C₂>
h₀	a₁		<C₂>	<I₀>
<I₀>

Эта таблица задает функцию

f( B_ij , X ) = X_kl,
которая для текущего грамматического вхождения B_ij и очередного символа грамматики X определяет грпмматическое вхождение очередного символа X_kl.
Следует отметить, что при построении таблицы переходов в клетках таблицы могут оказаться по несколько грамматических вхождений соответствующих символов. Такая таблица является недетерминированной, и ее нужно преобразовать в детерминированную таблицу с помощью приемов, использованных для преобразования таблиц конечных автоматов. В результате может получиться таблица, у которой строки отмечены множествами грамматических вхождений.

Построенная таблица переходов описывает смену состояний распознавателя, но она никак не отражет в каких случаея распознаватель должен выполнять действия переноса прочитанных символов в магазин и сворачивания. Если для хранения промежуточных цепочек, полученных в процессе сворачивания, использовать магазин, то таблица переходов может быть использована для определения грамматических вхождений, записываемых в магазин.
Для описания порядка действий магазинного распознавателя построим еще одну таблицу. В этой таблице обозначим действие переноса символов из входной цепочки в магазин символом П (Перенос), а действия, связанные со сворачивание цепочек, соответствующих правым частям правил, обозначаим символом С(К), где К—номер использованного правила. Для обозначения действий, осуществляющих передачу на выход результатов работы распознавателя, условимся использовать начальные буквы слов Допустить (Д) и Отвергнуть (О).
Учитывая, что действия преобразователя зависят как от символов входной цепочки, так и от символов, находящихся в магазине, обозначим строки таблицы грамматическими вхождениями, а столбцы - терминальными символами грамматики и символом конца цепочки ^.
Основанием для заполнения таблицы являются следующие два положения:
1. Операция сворачивания должна выполняться независимо от входного символа всегда, если в вершине магазина находится самое правое грамматическое вхождение некоторого правила. Для таких грамматических вхождений значением функции ВПОСЛЕ является пустое множество.
2. Если в вершине магазина находится грамматическое вхождение, не являющиеся самым правым вхождением какого-либо правила, то следует выполнить перенос очередного символа входной цепочки в магазин.
Следуя эти положениям и учитывая, что прцесс распознавания заканчивается успешно при обнаружении символа ^ на входе и символа I_о в магазине, и что в оставшихся случаях входная цепочка должна быть отвергнута, получаем таблицу действий в следующем виде:

Таблица 3.2
	a	b	<C>	^
a₁	П	П	П	О
<I₁₂>	П	П	П	О
<I₁₃>	П	П	П	О
b₁	С(1)	С(1)	С(1)	С(1)
<C₂>	С(2)	С(2)	С(2)	С(2)
h₀	П	П	П	О
<I₀>	О	О	О	Д

Эта таблица задает функцию действий
                f ( B_{i j} , x ) ( - { Д, О, С (1), С (2), ..., С (N) },
где N - число правил заданной грамматики, которая определяет какое действие должен выполнить распознаватель, находящийся в состоянии B_{i j} и прочитавший выходной символ x.
Для рассматриваемого примера операции свертки определяются следующим образом:
                C (1) = { a₁<I₁₂><I₁₃>b₁ | => I₀ },
                C (2) = { c₂ | => I₀ }.
Последняя таблица, которую иногда называют управляющей таблицей распознавателя, и таблица состояний полностью задают работу распознавателя. Алгоритм работы, использующий таблицу состояний и таблицу действий можно описать так:

Прочитать очередной символ входной цепочки—x.

Прочитать символ состояния, находящийся в вершине магазина—Y_K1.

Прочитать значение элемента таблицы действий, находящегося в строке Y_K1 и столбце x.

Если прочитанное значение есть 0 или D, то работу следует закончить, поскольку результат получен.

Если прочитанное значение определяет операцию, результатом которой является грамматический символ Z, то прочитать в таблице состояний элемент Z _{i j}, находящийся в строке Y_K1 и столбце Z. Записать Y_K1 и прочитанный символ Z _{i j} в магазин и выполнять п.1.

Используя описанный алгоритм, работу распознавателя, заданного таблицами 3.1 и 3.2, можно представить в виде последовательности конфигураций:

Магазин	Вход	Действие
`1. h₀`	`aaccbcb`^	`П`
`2. h₀a₁`	`accbcb`^	`П`
`3. h₀a₁a₁`	`ccbcb`^	`П`
`4. h₀a₁a₁c₂`	`cbcb`^	`С(2)`
`5. h₀a₁a₁<I₁₂>`	`cbcb`^	`П`
`6. h₀a₁a₂<I₁₂>c₂`	`bcb`^	`С(2)`
`7. h₀a₁a₂<I₁₂><I₁₃>`	`bcb`^	`П`
`8. h₀a₁a₂<I₁₂><I₁₃>b₁`	`cb`^	`С(1)`
`9. h₀a₁<I₁₂>`	`cb`^	`П`
`10. h₀a₁<I₁₂>c₂`	`b`^	`С(2)`
`11. h₀a₁<I₁₂><I₁₃>`	`b`^	`П`
`12. h₀a₁<I₁₂><I₁₃>b₁`	^	`С(1)`
`13. h₀I₀`	^	`Д`

В общем случае процедуру построения восходящего распознавателя по заданной грамматике, не содержащей аннулирующих правил, можно описать следующим образом:

Вычислить для данной грамматики функции ВПЕРВ и ВПОСЛЕ.
Построить недетерминированную таблицу, имеющую по одному столбцу для каждого грамматического символа и по одной строке для каждого грамматического вхождения и маркера дна. Элемент в строке R_j и столбце С должен содержать все грамматические вхождения C_K, такие, что C_K Î ВПОСЛЕ(R_j).
Если таблица, построенная на шаге 2, получается недетерминированной, то нужно преобразовать эту таблицу в детерминированную, рассматривая ее как недетерминированную таблицу переходов конечного автомата с начальным состоянием h_o.
Состояния, полученные на шаге 3 (кроме состояния, соответствующего пустому множеству), следует использовать в качестве магазинных символов. Полученная таблица переходов может содержать переходы в пустое множество. Такие элементы следует понимать как запрещенные и рассматривать переходы в них как ошибки.
Таблица действий заполняется строка за строкой согласно множествам грамматических вхождений, помечающих строки, следующим образом:

а.	Если строка отмечена начальным вхождением I₀, то в столбец, соответствующий маркеру конца строки ^, заносится операция Допустить, а во все остальные строки - операция Отвергнуть.
б.	Если строка отмечена грамматическим вхождением, являющимся самым правым вхождением в правиле с номером k, то во все элементы строки помещается операция Cвертка(k).
в.	Если строка отмечена маркером дна `h₀` или если все грамматические вхождения, входящие во множество, помечающее строку, не являются самыми правыми в своих правилах, то в столбец, отмеченный концевым маркером строки, заносится операция Отвергнуть, а во все остальные столбцы — операция Перенос.
г.	Если множество, помечающее строку после преобразования НКА, содержит начальное вхождение и хотя бы одно вхождение, отличное от начального, но не содержит ни одного самого правого вхождения, то в столбец, помеченный символом конца строки, нужно поместить операцию Допустить, а в остальные столбцы — Перенос.

Приведенная процедура обеспечивает построение распознавателя, только если заданная грамматика принадлежит подклассу LR(0), поскольку действия в каждой строке управляющей таблицы одинаковы, то есть не зависят от входного символа. Если же в процессе построения обнаруживается, что хотя бы один из пунктов (а), (б), (в) или (г) выполнить нельзя, то это означает, что для заданной грамматики нельзя построить LR(0)-распознаватель и что она не является LR(0)-грамматикой.

Пример построения LR(0)-распознавателя

В качестве иллюстрации применения описанной процедуры рассмотрим построение распознавателя для следующей грамматики:

Г _{3. 13} :
1. <E> ®<E₁> + <T₁>
2. <E> ® <T₂>
3. <T> ® (<E₃>)
4. <T> ® i

Функции ВПЕРВ и ВПОСЛЕ для этой грамматики имеют вид:

`ВПЕРВ(<E₁>)={<E₁>,<T₂>,(,i},`	`ВПОСЛЕ(<E₁>) = {+},`
`ВПЕРВ(<T₁>)={<T₁>,(,i},`	`ВПОСЛЕ(<T₁>) =`f`,`
`ВПЕРВ(<T₂>)={<T₂>,(,i},`	`ВПОСЛЕ(<T₂>) =`f`,`
`ВПЕРВ(+) = {+},`	`ВПОСЛЕ(+) = {<T₁>,(,i},`
`ВПЕРВ(i) = {i},`	`ВПОСЛЕ(i) =` f`,`
`ВПЕРВ(() = {(},`	`ВПОСЛЕ(()={<E₁>,<E₃>,<T₂>,(,i},`
`ВПЕРВ()) = {)},`	`ВПОСЛЕ()) =` f`,`
`ВПЕРВ(<E₃>)={<E₃>,<E₁>,<T₂>,(,i},`	`ВПОСЛЕ(<E₀>) =`f`,`
	`ВПОСЛЕ(h₀)={<E₀>,<E₁>,<T₂>,(,i},`
	`ВПОСЛЕ(<E₃>) = {)}`.

Таблица переходов, построенная по функциям ВПОСЛЕ, изображается так:

Таблица 3.3
	<E>	<T>	+	(	)	i
<E₀>
<E₁>			+
<T₁>
<T₂>
+		<T₁>		(		i
i
(	<E₁><E₃>	<T₂>		(		i
)
h₀	<E₁><E₀>	<T₂>		(		i
<E₃>					)

Полученная таблица переходов является недетерминированной. После преобразования таблицы, обозначая множество состояний (<E₀>, <E₁>) = <E_x> и
(<E₁>, <E₃>) = <E_y> и полагая, что начальным состоянием является h₀, получаем:

Таблица 3.4
	<E>	<T>	+	(	)	i
<E_x>			+
<E_y>			+		)
<T₁>
<T₂>
+		<T₁>		(		i
(	<E_y>	<T₂>		(		i
)
h₀	<E_x>	<T₂>		(		i
i

Учитывая состав множеств, обозначенных <E_x> и <E_y>, построим таблицу действий искомого распознавателя.

Таблица 3.5
	^	+	(	)	i
E_x	D	П	П	П	П
E_y	О	П	П	П	П
T₁	С (1)	С (1)	С (1)	С (1)	С (1)
T₂	С (2)	С (2)	С (2)	С (2)	С (2)
+	О	П	П	П	П
i	С (4)	С (4)	С (4)	С (4)	С (4)
(	О	П	П	П	П
)	С (3)	С (3)	С (3)	С (3)	С (3)
h₀	О	П	П	П	П

Построенный распознаватель является эквивалентным недетерминированному распознавателю, но эти распознаватели имеют разные состояния. Следовательно, им должны соответствовать эквивалентные, но не одинаковые грамматики. Такое различие должно отразиться в операциях сворачивания. В рассматриваемом случае операция Свертка(1) должна учитывать, что недетерминированному распознавателю соответствует грамматика с правилами <E>® <E_x> + <T> и <E> ® <E_y> + <T>.