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

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

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

Определение. Пусть задана грамматика Г, в схеме которой имеется    правило                           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. 12} :
        (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>.

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

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

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

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

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