3.14. Восходящие распознаватели для грамматик с аннулирующими правилами

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

Пусть задана грамматика, задающая арифметические выражение без скобок с двумя операциями:

Г _{3. 15} :

<I>  a<R>

<R>  +a<R>

<R>  -a<R>

<R>  &

Четвертое правило данной грамматики имеет пустую правую часть, поэтому оно не должно влиять на выполнение первых четырех этапов процедуры построения SLR(1)-распознавателя. Используя эту процедуру, построим таблицы переходов и действий распознавателя, не учитывающего наличие аннулирующих правил, которые имеют вид:

 

Таблица 7.9 a + - <R> <I> <I0>           a1   + - <R1>   <R1>           + a2         a2   + - <R2>   <R2>           - a3         a3   + - <R3>   <R3>           h0 a1       <I0>

Таблица 7.10 a + -  <I0>       Д a1   П П   <R1>       С1 + П       a2   П П   <R2>       С2 - П       a3   П П   <R3>       С3 h0 П

 

При выводе четвертое правило грамматики позволяет исключить нетерминал <R>из выводимой цепочки. Следовательно, при сворачивании этому правилу необходимо сопоставить операцию записи символа<R>в магазин. Эту операцию обозначим Свертка (4) или С4. Чтобы определить в каких случаях должна выполняться эта операция, необходимо решить после каких символов в выводимых цепочках может следовать нетерминал<R>и какие символы могут следовать за ним. Множество символовx₁, x₂, …, x_k, за которыми может следовать<R>, можно найти, определив в какие множестваВПОСЛЕ(X_k)входит<R>. Это множество можно найти по таблице переходов следующим образом. Возьмем столбец, отмеченный символом<R>, таблицы переходов и найдем все строки, в которых на пересечении с этим столбцом находятся непустые элементы. Множество отметок этих строк{a₁,a₂,a₃}и является множеством грамматических вхождений, за которыми может следовать<R>. Учитывая, что за символом<R>могут следовать входные символы множестваСЛЕД(<R>) = {}, находим,что в элементы таблицы действий, соответствующих парам(a₁, ),(a₂, )и(a₃, ), нужно вписать операцию С4. В результате получаем таблицу 7.11, которая с таблицей 7.9 задает восходящий распознаватель для заданной грамматики.

 

Таблица 7.11
	a	+	–	
<I0>				Д
a1		П	П	С4
<R1>				С1
+	П
a2		П	П	С4
<R2>				С2
–	П
a3		П	П	С4
<R3>				С3
h0	П

 

Последовательность конфигураций, описывающая работу распознавателя для входной цепочки a + a – a имеет вид:

 

Вход	Магазин	Действие
1. a + a - a 	h0	П
2. + a - a 	h0a1	П
3. a - a 	h0a1 +	П
4. - a 	h0a1 + a2	П
5. a 	h0a1 + a2 -	П
6. 	h0a1 + a2 - a3	С4
7. 	h0a1 + a2 + a3<R3>	С3
8. 	h0a1 + a2<R2>	С2
9. 	h0a1<R1>	С1
10. 	h0<I0>	Д

 

Рассмотренный пример показывает, что в общем случае правила построения восходящих SLR(1)-распознавателей необходимо дополнить еще одним пунктом 5 (г), который должен учитывать наличие аннулирующих правил в заданной грамматике. Этот пункт процедуры построения запишем в следующим виде:

5г.

Заполнение элементов таблицы действий для аннулирующего правила  <A>  $с номеромkвыполняется следующим образом: Чтобы найти множество грамматических вхождений, за которыми может следовать символ Y, выделим в таблице переходов столбец, отмеченный символом Y. В этом столбце выделим строки, имеющие непустые элементы. Допустим, что эти строки отмечены символами x1, x2, …, xm. Найдем множествоСЛЕД(<A>) = {z1, z2, …, zn}. Это множество грамматитических символов, которые могут следовать за символом Y. Для каждой пары элементов(xi, zj)в соответствующую клетку таблицы действий нужно вписать операцию Свертка (k).

Процедура построения распознавателя с пунктами 5 (а), (б), (в) и (г) позволяет получить результат только в том случае, если заданная грамматика с аннулирующими правилами является грамматикой SLR(1). Если же при построении обнаруживаются противоречия, то это означает, что заданная грамматика не принадлежит подклассу SLR(1) грамматик, и для нее нельзя построить SLR(1)–распознаватель.