Пред.Страница
След.Страница
Раздел Содержание
3.11. Восходящие распознаватели для грамматик с аннулирующими правилами
Прежде чем сформулировать правила построения восходящих распознавателей для грамматик с аннулирующими правилами, рассмотрим пример и попытаемся выяснить какие дополнительные действия должен выполнять распознаватель и положение этих действий в управляющих таблицах.
Пусть задана грамматика, задающая арифметические выражение без скобок с двумя операциями:
Г 3. 15 :
<I> ® a<R>
<R> ® +a<R>
<R> ® -a<R>
<R>
® &
Четвертое правило данной грамматики имеет пустую правую часть, поэтому оно не должно влиять на выполнение первых четырех этапов процедуры построения SLR(1)-распознавателя. Используя эту процедуру, построим таблицы переходов и действий распознавателя, не учитывающего наличие аннулирующих правил, которые имеют вид:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
При выводе четвертое правило грамматики позволяет исключить нетерминал <R> из выводимой цепочки. Следовательно, при сворачивании этому правилу необходимо сопоставить операцию записи символа <R> в магазин. Эту операцию обозначим
Свертка (4) или С4. Чтобы определить в каких случаях должна выполняться эта операция, необходимо решить после каких символов в выводимых цепочках может следовать нетерминал <R> и какие символы могут следовать за ним.
Множество символов x1, x2, …, xk, за которыми может следовать <R>, можно найти, определив в какие множества ВПОСЛЕ(Xk) входит <R>. Это множество можно найти по таблице переходов следующим образом.
Возьмем столбец, отмеченный символом <R>, таблицы переходов и найдем все строки, в которых на пересечении с этим столбцом находятся непустые элементы. Множество отметок этих строк {a1,a2,a3} и является множеством грамматических вхождений, за которыми может следовать <R>. Учитывая, что за символом <R> могут следовать входные символы множества СЛЕД(<R>) = {^}, находим,что в элементы таблицы действий, соответствующих парам (a1, ^), (a2, ^) и (a3, ^), нужно вписать операцию С4. В результате получаем таблицу 7.11, которая с таблицей 7.9 задает восходящий распознаватель для заданной грамматики.
|
Таблица 3.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)–распознаватель.