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

3.10. SLR(1)-распознаватели и их построение

Рассмотрим еще один пример построения распознавателя для следующей грамматики, не содержащей аннулирующих правил.

Г 3. 14 :
<I> ® t<A1>
<A> ® <A2>, <B2>
<A> ® <B3>
<B> ® a
<B> ® b

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

 

Таблица 3.6

 

t 

, 

a 

b 

<I> 

<A> 

<B> 

h0

t

 

 

 

<I0>

 

 

<I0>

 

 

 

 

 

 

 

<A1>

 

 

 

 

 

 

 

t

 

 

a

b

 

<A1><A2>

<B3>

<A2>

 

,

 

 

 

 

 

,

 

 

a

b

 

 

<B2>

<B2>

 

 

 

 

 

 

 

<B3>

 

 

 

 

 

 

 

a

 

 

 

 

 

 

 

b

 

 

 

 

 

 

 

 

Это недетерминированная таблица, поэтому введем обозначение <Ax> = (<A1>, <A2>) и преобразуем ее к детерминированному виду. В результате имеем:

 

Таблица 3.7

 

t 

, 

a 

b 

<I> 

<A> 

<B> 

h0

t

 

 

 

<I0>

 

 

<I0>

 

 

 

 

 

 

 

<Ax>

 

,

 

 

 

 

 

t

 

 

a

b

 

<Ax>

<B3>

,

 

 

a

b

 

 

<B2>

<B2>

 

 

 

 

 

 

 

<B3>

 

 

 

 

 

 

 

a

 

 

 

 

 

 

 

b

 

 

 

 

 

 

 

 

Продолжая построение в соответствии с описанной процедурой, мы столкнемся с противоречием при заполнении строк таблицы действий для строки, помеченной символом <Ax>. Поскольку <Ax> содержит грамматическое вхождение <A1>, являющееся самым правым символом правила 1, то нужно было бы записать в рассматриваемую строку таблицы действий операцию Свертка (1). Однако, в множестве <Ax> содержится также грамматическое вхождение <A2>, которое не является самым правым символом правила 2. Для такого символа данную строку таблицы действий нужно заполнить операцией Перенос. Обнаруженное противоречие показывает, что грамматика Г 3. 14 не является LR(0)-грамматикой, и что построить LR(0)-распознаватель с помощью описанной процедуры невозможно.
Попробуем теперь проверить, нельзя ли построить для заданной грамматики SLR(1)-распознаватель. Построение такого распознавателя отличается от описанного выше тем, что заполнение таблицы действий выполняется не целыми строками, а каждый элемент строки строится отдельно, и при этом учитываются только те символы, которые могут следовать за рассматриваемым в выводных цепочках.
В нашем примере при построении строки таблицы действий для символа <Ax> в столбец, отмеченный символом запятая запишем операцию Перенос, поскольку в таблице переходов в строке <A2> и столбце с запятой находится грамматический символ. В столбец, отмеченный символом конца строки ^, занесем операцию Свертка (1), поскольку за символом <A1> может следовать только символ ^. Последнее утверждение вытекает из того, что СЛЕД(<I>) = {^}. Учитывая, что 

     СЛЕД(<B>) = { , , ^}
     СЛЕД(<A>) =  { , , ^}

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

 

Таблица 3.8

 

t 

, 

a 

b 

^ 

h0

П

 

 

 

 

<I0>

 

 

 

 

Д

<Ax>

 

П

 

 

С(1)

t

 

 

П

П

 

,

 

 

П

П

 

<B2>

 

С(2)

 

 

С(2)

<B3>

 

С(3)

 

 

С(3)

a

 

С(4)

 

 

С(4)

b

 

С(5)

 

 

С(5)

 

Эта таблица вместе с таблицей 3.6 задает SLR(1)–распознаватель, который работает по тем же правилам, что и LR(0)–распознаватель. Незаполненные клетки таблицы соответствуют операции Отвергнуть.

Процедура построения SLR(1)–распознавателя отличается от процедуры построения LR(0)–распознавателя содержанием только одного пункта 5, который можно описать так:

а) Если Q содержит начальное вхождение, то в столбец, помеченный маркером входной строки, занести операцию Допустить.
б) Если Q содержит грамматическое вхождение R i j, не являющиеся самым правым вхождением никакого правила, и если элемент таблицы переходов для этого символа R i j и некоторого символа грамматики S не является пустым, то в элемент таблицы действий соответствующей паре ( R i j, S) заносится операция Перенос.
в) Если Q содержит самое правое грамматическое вхождение p цепочки a правила <A> ® a с номером k, то для каждого входного символа x Î СЛЕД(<A>) в элемент таблицы действий, соответствующий паре (p,x), заносится операция Свертка (k).

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

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