Восходящие распознаватели. LR(k) – грамматики. Построение и работа распознавателя

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

Пусть задана грамматика Г, в схеме которой имеется правило

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>.

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

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

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

Магазин Вход Действие

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> ^ Допустить

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

Детерминированные восходящие распознаватели, так же как и нисходящие, могут быть построены не для всякой КС-грамматики, а только для определенных подклассов таких грамматик. Наиболее широким подклассом КС-грамматик являются LR(k)-грамматики. Эти грамматики обеспечивают распознавание цепочки при просмотре слева направо, об этом говорит буква L (Left) в названии грамматики, и позволяют выполнить правостороннее сворачивание, это показывает буква R (Right) в названии. Параметр k говорит о том, что для определения того правила грамматики, которое нужно применить для сворачивания цепочки, потребуется просмотреть не более k еще не прочитанных символов входной цепочки.

В общем случае алгоритмы построения распознавателей дл LR(k)-грамматик оказываются достаточно сложными и трудоемкими, поэтому на практике чаще всего используют подклассы LR(k)-грамматик: LR(0), или SLR(1)—простые (Simple) LR(1)-грамматики, позволяющие относительно просто выполнять построение восходящих распознавателей. При этом для каждого подкласса LR(k)-грамматик используется свой алгоритм построения. Если задана КС-грамматика, то определить ее принадлежность к одному из подклассов грамматик LR(k) можно только путем анализа возможности построения для нее с помощью определенного алгоритма детерминированного распознавателя. Учитывая последнее обстоятельство, условимся называть распознаватели по подклассу соответствующих грамматик: LR(0)-распознаватель или SLR(1)-распознаватель.

Условимся называть символы полного словаря грамматики грамматическими символами. Каждый грамматический символ может входить в разные правила грамматики и, более того, появляться в одном и том же правиле несколько раз. При этом положение символа в правиле грамматики может показывать, какое действие нужно выполнить: перенос или свертку, а также какие грамматические символы могут за ним следовать. Это обстоятельство позволяет связать позицию грамматического символа в правиле грамматики с понятием состояния распознавателя. Для удобства дальнейших рассуждений введем понятие грамматического вхождения.

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

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