ние неукорачивающей грамматики. Такие преобразования могут оказаться полезными, если нарушается второе условие принадлежности грамматики к классу LL(1).

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

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

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

r = <A> → ψ и задана цепочка γ = ρ1 ψ ρ2. Поскольку правая часть цепочки правила r

является частью цепочки τ, то можно получить цепочку τ = ρ1<Α> ρ2, заменяя правую часть правила грамматики левой частью. В этом случае говорят, что цепочка τ получа-

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

γ τ.

Определение. Если существует множество цепочек { ω1, ω2, ... , ωn }, таких, что

ω1 ω2 , ω2 ω3 , ... ,ωn-1 ωn ,

то говорят, что цепочка ω1 сворачивается в цепочку ωn и используют обозначение

ω1 ωn

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

Например, сворачивание цепочки, полученной с помощью правого вывода и правил следующей грамматики

Г3. 11 :

(1)<I> → a,

(2)<I> → (<I><R> ,

38