Распознавателя
- Способ построения распознавателя предусматривает сопоставление каждому правилу грамматики команды распознавателя .
Согласно общему способу построения распознавателей для КС-грамматик, описанному в предыдущем разделе, каждому правилу разделенной грамматики, которые имеют вид:
<A> ® a a , где a
- цепочка символов полного словаря и a принадлежит
терминальному словарю, нужно поставить в соответствие команду
- (*) f 0( s0 , e , <A> ) = ( s0
, a
' a) ,
которая задает такт работы без сдвига входной головки и в которой
a ' представляет собой зеркальное отображение цепочки a
. Отметим, что в результате выполнения этой команды, в вершине магазина окажется терминал a. Общий способ построения редусматривает также построение для каждого a
символа грамматики команды:
- (**)
f ( s0 , a , a ) = ( s0 , $ )
которая удаляет этот терминал из магазина и сдвигает входную головку.
Учитывая, что в разделенной грамматике каждое правило начинается с терминального символа, и что эти терминалы не повторяются, можно сделать вывод о том , что команда (*) должна выполняться только в том случае, когда под входной головкой находится терминал
a, и после нее всегда должна выполняться команда (**).
Чтобы исключить неопределенность правил вида (*) и уменьшить число тактов работы распознавателя, объединим команды вида (*) и (**) в одну команду. Построение такой команды должно выполняться следующим образом: каждому правилу разделенной грамматики <A> ® a a
поставим в соответствие команду
- f ( s0 , a , <A>) = ( s0 , a
') ,
которая определяет такт работы распознавателя со сдвигом входной головки.
Кроме того, следует учесть, что терминальные символы могут быть расположены в правых частях правил не только на самой левой позиции. Для таких терминалов необходимо построить команды вида :
- f ( s0 , b , b ) = ( s0
, $ )
Для перехода в заключительное состояние добавим правило:
- f ( s0 , $ ,h0 ) = ( s1 , $ ) ,
а в качестве начальной конфигурации распознавателя примем, как
обычно, следующее выражение :
( s0 , a
, h0<I> ) ,
где <I> - начальный символ грамматики, а a - заданная входная цепочка.
Применяя приведенные выше правила, построим распознаватель для разделенной грамматики
Г3. 0
. В результате получаем: М 4 : P = { a , b }, H = { a , b ,<I> , <B> , h0 }, S = {s0}, F= {s0},
f ( s0 , a , <I>) = ( s0
, <B>b )
f ( s0 , a , <B>) = ( s0
, $ )
f ( s0 , b , <I> ) = ( s0
, <I> b <B> )
f ( s0 , b , <B> ) = ( s0
, <B> )
f ( s0 , b , b ) = ( s0
, $ )
f ( s0 , e
, h0 ) = ( s0 , $ )
Работу построенного автомата покажем на примере анализа цепочки bbabab.
( s0 , bbababa , h0<I> ) |---
( s0 , bababa , h0<I>b<B> ) |---
( s0 , ababa , h0<I>b<B> ) |---
( s0 , baba , h0<I>b ) |---
( s0 , aba , h0<I> ) |---
( s0 , ba , h0<B>b ) |---
( s0 , a , h0<B> )
|--- ( s0 , $ , h0
) |--- ( s0 , $ , $ ) .
Приведенная последовательность конфигураций показывает, что в каждой конфигурации может быть применена единственная команда детерминированного распознавателя.
Пред.Страница
След.Страница Раздел Содержание