Восходящие распознаватели

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

Определение. Пусть задана грамматика Г, в схеме которой имеется    правило                           r =A®y  и задана цепочка  g = r1A r2.  Если правая часть цепочки                           правила r является частью цепочки , то можно получить цепочку                           t = r1y r2 , заменяя правую часть правила грамматики левой частью.                           В этом случае говорят, что цепочка  tt   получается путем                           непосредственного сворачивания цепочки g  и   используют                           обозначение                                               t <= g .  Определение. Если существует множество цепочек    W  = ( w1, w2, ...wn  ),                             таких, что     w1 Ь   w2 ,    w2 Ь    w3 ,  ...  ,  wn-1Ь   wn ,                             то говорят, что цепочка  wn    сворачивается в цепочку  w1   и                             используют обозначение                                                       w1 *Ь   wn .

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

 Г3. 11

:
        (1) <I> ®

a,

        (2) <I> ®

(<I><R> ,
        (3) <R> ®

,<I><R> ,
        (4) <R> ®




).

 

можно представить так:             (a,a) Ь 1 (<I>,a) Ь 1 (<I>,<I>) Ь 4

            (<I>,<I><R> Ь 3(<I><R> Ь 2 <I>.

Каждый шаг рассмотренной процедуры связан с выделением в цепочке правой части какого-либо правила и заменой его левой частью правила. В последовательности сворачиваний правые части правил  называются основой

рассматриваемой цепочки. В общем случае основу можно определить так:
 

Определение. Основой цепочки называют вхождение правой части последнего                           правила, примененного при правом выводе рассматриваемой                           цепочки.

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

  Магазин

Вход

Действие

1. h0	(a,a)^	Перенос
2. h0(	a,a)^	Перенос
3. h0(a	,a)^	Свертка(1)
4. h0(<I>	,a)^	Перенос
5. h0(<I>,	a)^	Перенос
6. h0(<I>,a	)^	Свертка(1)
7. h0(<I>,<I>	)^	Перенос
8. h0(<I>,<I>)	^	Свертка(4)
9. h0(<I>,<I><R>	^	Свертка(3)
10. h0(<I><R>	^	Свертка(2)
11. h0<I>	^	Допустить

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

Пред.Страница 

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


Содержание раздела

---