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

3.13. Построение SLR(1)-распознавателя
 

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

Г _{3. 14} :
<I> ® t<A₁>
<A> ® <A₂>, <B₂>
<A> ® <B₃>
<B> ® a
<B> ® b

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

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

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

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

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

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

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

5. Таблица действий заполняется поэлементно для каждой строки, отмеченной маркером дна или множеством грамматических вхождений Q, следующим образом:
а) Если 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)-распознавателем.
Все описанные выше процедуры построения распознавателей применимы к неукорачивающим грамматикам. Они являются также базой для построения восходящих распознавателей для укорачивающих грамматик. Однако эти процедуры должны быть дополнены правилами построения, учитывающими наличие аннулирующих правил.

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