соответствующие закрывающие скобки и, например, s3 содержит выделенное вхождение символа а, а t2 - выделенное вхождение символа b (при этом x2 содержит s2 как подцепочку, y2 содержит t3).

2.1.4. Прогнозы. Характеристика бесконтекстной грамматики

Пусть 0 < p < s. Тогда назовем пару (p,j), 1 < j < np, позицией (в правилах грамматики Augm(G)) символа Xpj. Если np = 0, то определим (p, 0) как позицию пустой цепочки.

Заметим, что одному символу грамматики может отвечать несколько позиций. То же верно для пустой цепочки. Для X е V U { 1 , Л} обозначим через positions(X) множество его позиций. Будем писать symb(r) = X Vr е positions(X).

Определим рекурсивно роли некоторых подцепочек структуры а е SG (в этой структуре):

1)пусть

а = u(pv)p(3az е L(Struct(G)),

0 < p < s, цепочка v сбалансирована, a е S U {±} или az = Л, ш([3) = Л; тогда если v = Л, то пустая цепочка между скобками (p и )p имеет в а роль [p, 0, а]; если же Л = v = xi ...Xnp, где Xpj *Struct(G) Xj для 1 < j < np, то цепочка Xj имеет в а роль [p, j, а];

2)пусть u(pv)py е SG и выделенная подцепочка (pv)p имеет в данной структуре роль r; тогда символ Ap имеет роль r в структуре а = uApy.

Как видим, в состав роли входят позиция в некотором правиле и терминальный символ, непосредственно следующий в некоторой сентенциальной форме грамматики Augm(G) за символом левой части этого правила.

Рассмотрим вопрос построения множества roles(X) всех ролей элемента X е V U Л}. Нетрудно убедиться, что структура

reduction(u, (p, v, )p, в, a, z)

является каноном. Следовательно, для такого построения достаточно ядра Core(G).

Подмножество множества

R = Uxev u{±,A} roles (X)

назовем прогнозом.

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

Термин "прогноз"призван заменить громоздкие словосочетания, введенные в работах по теории LR(k) анализа. Термин не только краток, но и достаточно метко характеризует информацию, хранимую LR(k) анализатором в магазине.

Обозначим через р(а), где а е SG, результат вставления в а вслед за каждой ее подцепочкой, имеющей в а роль, этой роли.

Пусть m > 1, а = ul.. .um е SG. Пусть для 1 < i < m имет место равенство uj = uil... uiki, где для 1 < j < hi щ е VU{±}U{(p, )p0 < p < s}. Тогда обозначим через p(ul,... ,um) такую последовательность (u[,... ,um), что р(а) = u[ ...um,

ui = ui1ri1 ...Uikiriki, где Tij G R U {Л}. (Таким образом, цепочка ui содержит вместе с символами цепочки ui их роли в структуре а.) Заметим, что одна и та же подцепочка ui в разных структурах или в разных местах одной структуры может отображаться операцией р на различные цепочки. Будем использовать для ui обозначение p(ui) в тех случаях, когда ui известна и, следовательно, исключена необходимость выбирать среди цепочек, могущих иметь обозначение p(ui).

Заметим, что цепочка ролей, получаемая из р(а) вычеркиванием всех символов исходной структуры а, позволяет восстановить а. Таким образом, в р(а) символы исходной структуры несут лишь избыточную информацию, и потому мы будем иногда игнорировать их (см., например, определение 22). Однако, они удобны, например, для определения прогнозов, которые являются состояниями конструируемого ниже преобразователя M(G).

Назовем множество

X(G) = {р(а)а G Core(G)}

характеристикой грамматики G.

Далее мы рассмотрим способы построения автомата, эквивалентного грамматике G, по характеристике x(G). При некоторых способах построения автомат наследует особенности грамматики G, например, является однозначным, если G однозначна, и т.п.

2.2. ЕЬК(1)анализатор бесконтекстного языка

2.2.1. Построение преобразователя по элементам характеристики, рассматриваемым порознь. Рассмотрим расширенный магазинный автомат

M = (K, Е, r,Zo,S,qo,F),

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

(qi,a,7i) - (q2,72),

где a G Е U {Л} и для i = 1, 2 qi G K, Yi G Г*.

Дополним такой автомат выходной лентой и выходным алфавитом А. Обяжем команду писать y G А* на выходной ленте. Полученное устройство называют (расширенным) преобразователем с магазинной памятью, подразумевая преобразование входной цепочки в выходную.

Команда преобразователя M будет иметь вид

(q1,a,7l) - (q2,y,72 )•

Слова "u есть подцепочка цепочки г"будем выражать записью "u С z". Цепочка x G x(G) представляется в виде

ziyi • ..zkyk,

где для 1 < i < k yi G Е U {±} U {)p0 < p < s}, а zi может содержать только роли и открывающие скобки множества 0 < p < s}. Прогнозы

Zi = {r gR r С zi}, 1 < i < k,

будут одновременно состояниями и магазинными символами преобразователя. Такой прогноз содержит один или два элемента. Последнее возможно, если

ZiVi = г в (рт)р, где

в e{{q 1 < q < s}*, а т - роль пустой правой части pro правила. Тогда

Zi = {т, т}.

Обозначим через Kx множество

{Zi1 < i < k} всех состояний, определяемых цепочкой x. Пусть

K = Ux6x(G)Kx.

Определим преобразователь M(G) = ({Z0, f, -1} U K U Е U Е х {p0 < p < s}, E U {±}, {Zo} U K, Zo, {p 0 < p < s}, Uxex(G)Sx, Zo, {f}).

Сформулируем правила построения подмножества 5x команд преобразователя, заметив, что всегда

ziyi = (o±,

Z2 содержит роль [0,1, Л] и

zfc iyfc izfcyk = [0, 2, Л]±[0, 3, Л])о.

Началу ziyiz2 цепочки x сопоставляется команда

(1)(Zo, ±,Zo) (Z2, Л,ZoZ2).

Окончанию [0, 2, Л]±[0, 3, Л])0 цепочки x сопоставляется команда

(2)(±, Л,ZoZ2{[0, 2, Л]}) (f, 0,Zo).

Остальные команды из 5x определяются следующими формулами (3)-(6), в которых Z - прогноз, составленный ролями цепочки z е {zi11 < i < k}, и аналогично определяется Z со штрихом или индексом.

(3)(q, b, Z) (Z, Л, ZZ), zaz С x, a = ±, (q, b) е {(Z, a), (a, Л)}.

(4)(q, b, Z) (a,p, ZZ), z)pz С x, [p, 0, a] е Z, (q, b) е {(Z, a), (a, Л)}. Следующие формулы (5)-(6) обусловлены соотношениями

zy(i)z(i)... y(np)z(np))pz С x, np > 0, для 1 < j < np [p, j, a] е Zz = w(pv, цепочка vy(i)z(i).. . y(np)z(np) сбалансирована, (q,b) е {(Z(np),a), (a, Л)}.

(5)(q,b,ZZ(i) ...Z- ((a,p), ).

(6)((a,p), Л,Z) (a,p,ZZ).

Проводя аналогию с анализатором типа "сдвигсвертка"[ЛЬо -Ullman 72], можно сказать, что команды вида (1) и (3) выполняют сдвиг, а команда (4) и после довательно выполняемые команды (5), (6) выполняют свертки. Команда (2) реализует действие "стоп", но можно также сказать, что она выполняет свертку по нулевому правилу грамматики Augm(G).

Для каждого прочитанного входного символа в магазин преобразователя M(G) поступает прогноз, содержащий роль этого символа. Формулы (5), (6) показыва -ют, что состояние из Е U {±} "запоминает использованный для свертки"входной символ до момента засылки в магазин прогноза, содержащего роль этого символа.