3.12. 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)-распознаватель. Прежде чем перейти к рассмотрению правил построения восходящих распознавателей, введем несколько вспомогательных понятий. Условимся называть символы полного словаря грамматикиграмматическими символами. Каждый грамматический символ может входить в разные правила грамматики и, более того, появляться в одном и том же правиле несколько раз. При этом положение символа в правиле грамматики может показывать, какое действие нужно выполнить: перенос или свертку, а также какие грамматические символы могут за ним следовать. Это обстоятельство позволяет связать позицию грамматического символа в правиле грамматики с понятием состояния распознавателя. Для удобства дальнейших рассуждений введем понятиеграмматического вхождения.

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

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

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

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

     Y * <L>bXab

и Xявляется самым левым вхождением в правой части правила<L>  Xa.

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

Г_{3. 13}:<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>
a1	a1		<C2>	<I12>
<I12>	a1		<C2>	<I13>
<I13>		b1
b1
<C2>
h0	a1		<C2>	<I0>
<I0>

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

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

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

Таблица 3.2
	a	b	<C>	
a1	П	П	П	О
<I12>	П	П	П	О
<I13>	П	П	П	О
b1	С(1)	С(1)	С(1)	С(1)
<C2>	С(2)	С(2)	С(2)	С(2)
h0	П	П	П	О
<I0>	О	О	О	Д

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

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

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

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

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

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

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

Магазин	Вход	Действие
1. h0	aaccbcb	П
2. h0a1	accbcb	П
3. h0a1a1	ccbcb	П
4. h0a1a1c2	cbcb	С(2)
5. h0a1a1<I12>	cbcb	П
6. h0a1a2<I12>c2	bcb	С(2)
7. h0a1a2<I12><I13>	bcb	П
8. h0a1a2<I12><I13>b1	cb	С(1)
9. h0a1<I12>	cb	П
10. h0a1<I12>c2	b	С(2)
11. h0a1<I12><I13>	b	П
12. h0a1<I12><I13>b1		С(1)
13. h0I0		Д

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

1. Вычислить для данной грамматики функции ВПЕРВиВПОСЛЕ.

2. Построить недетерминированную таблицу, имеющую по одному столбцу для каждого грамматического символа и по одной строке для каждого грамматического вхождения и маркера дна. Элемент в строкеR_jи столбцеСдолжен содержать все грамматические вхожденияC_K, такие, чтоC_K  ВПОСЛЕ(R_j).

3. Если таблица, построенная на шаге 2, получается недетерминированной, то нужно преобразовать эту таблицу в детерминированную, рассматривая ее как недетерминированную таблицу переходов конечного автомата с начальным состоянием h_o.

4. Состояния, полученные на шаге 3 (кроме состояния, соответствующего пустому множеству), следует использовать в качестве магазинных символов. Полученная таблица переходов может содержать переходы в пустое множество. Такие элементы следует понимать как запрещенные и рассматривать переходы в них как ошибки.

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

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

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