Единственный успешный маршрут данного автомата является элементарным. Автомат с командами

(po,a,Zo) - (pi,Zo),

(pi,a, Zo) - (p4,Zo),

(p4, b, Zo) - (p2, Zo),

(P2,b,Zo) - (p3,Zo),

(p3,b,Zo) - (f,Zo) эквивалентен предыдущему, но, в отличие от него, не имеет циклов.

Пусть 6(7, v), где 7 - цепочка магазинных символов, обозначает результат вычеркивания из 7 всех вхождений символа v.

Пусть v = Zo - магазинный символ автомата M. Обозначим через 6(M,v) автомат, получаемый из M выполнением следующих действий:

каждую команду вида

(q1,b, v7i) - (q2,y,72)

заменить командами множества

{(qi,b,v7i) - (q2,y, v/72)v/ = v, 3 команда вида (q,a,v7) - (q,y,vv)} (из конструкции преобразователя ELRM(G) и неравенства v = Zo следует, что если такая замена требуется, то она всегда осуществима);

каждую команду

(q, a, 7) - (q/, y, 7/)

заменить командой

(q, a, 6(7, v)) - (q/, y, 6(7/, v)).

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

Пусть q, q/, b, 7 и y таковы, что для любой команды вида (q, b, 7i) - (q/, y, 72) существует такая непустая магазинная цепочка 7/, что 7i = 7/7, 72 = 7/. Тогда назовем (q, q/, b, 7, y) группой множество

{в 37/ е Г+ : в = (q,b, 7/7) - (,У,У)} команд данного преобразователя. (Содержательно, переход, определяемый любой командой группы, не зависит от префикса 7/ обозреваемой магазинной цепочки 7/7.) В противном случае (q, q/, b, 7, у)группа пуста.

Назовем законным каждое из следующих двух преобразований автомата M: сохраняющее родословные преобразование M в б(М, v) и замену непустой (q, q/, b, 7, у)группы одной командой (q,b, 7) - (q/,у, Л).

Алгоритм 5. Уменьшение преобразователя.

Вход. Преобразователь M.

Выход. Наилучший (по числу команд или по какимлибо другим свойствам) из преобразователей, которые получаются следующими преобразованиями автомата

Шаг 1. Построить по M преобразователь Mi - результат некоторой последо -вательности законных преобразований, к которому уже не применимы законные преобразования.

Шаг 2. Если полученный шагом 1 преобразователь Mi является детерминиро -ванным, то применить к нему модификацию алгоритма 3, устраняющую команды,

которые не читают входного символа, не пишут выходных символов и не стирают в магазине. (Нужная модификация достигается переопределением множества дуг, которые подлежат устранению: теперь они должны быть не только нечитающими и нестирающими, но и не писать на выходную ленту.)

Нетрудно убедиться, что шаг 1 сохраняет свойство детерминированности. То же доказано для алгоритма, упомянутого шагом 2. Следовательно, алгоритм 2 можно считать и алгоритмом уменьшения детерминированных ELR(1)анализаторов.

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

Следующий алгоритм указывает очевидно разумные попытки уменьшить число прогнозов анализатора A(G) путем объединения некоторых прогнозов.

Пусть v1 и v2 - различные прогнозы, используемые преобразователем M в качестве состояний (и, возможно, магазинных символов). Если замена каждого использования этих прогнозов объединением vi U v2 сохраняет родословные, то назовем прогнозы v1 и v2 объединимыми (друг с другом).

Алгоритм 6. Сокращение числа прогнозов.

Вход и выход. Pr - множество прогнозов; первоначально это прогнозы анализатора A(G), по окончании - прогнозы сокращенного анализатора.

Метод. Пока множество Pr содержит некоторые объединимые прогнозы v1 и v2, выполнять:

(Pr := Pr - {vi, v2} U {vi U v2};

заменить на v1 U v2 каждое вхождение v1 и v2 в команды преобразователя M (можно вместо этого изменять соответствующие автомату M таблицы действий и переобозначений).

Алгоритм 3 можно рассматривать и как алгоритм сокращения таблиц анализатора, и как алгоритм сокращения распознавателя.

Заметим, что для одного из тех элементов множества Pr, которые указыва ют роли нетерминального символа A, можно использовать обозначение A. Тогда сократится общее число обозначений, нужных для описания анализатора. Кро -ме того, исходная грамматика будет легче "проглядываться"в анализаторе. Такой же прием возможен и для терминальных символов, не являющихся полезными состояниями преобразователя M(G).

Проверка следующих условий резко сокращает число прогнозов, объедини мость которых имеет смысл исследовать:

NoConfl(v1 U 1J2) = {v1 U 1J2};

VX е V ([ i = 1, 2 3vxi : (vi, X, vxi) е RT(G)] vx 1 и vx2 объединимы).

Заметим, что если ограничиться распознаванием цепочек и не формировать вы ход, то несложные модификации алгоритмов 5 и 6 будут производить по преобра -зователю ELRM(G) эквивалентный магазинный автомат, экономность которого определяется в основном экономностью исходной грамматики G. Модификация

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

Порядок применения алгоритмов 5 и 6 не безразличен: от него существенно зависит вид результирующего преобразователя.

Пример 3. Рассмотрим грамматику G с единственным правилом

Элемент характеристики x(G) также один:

(о±[01Л](1а[11±]а[12±])1[02А]±[03А])о M(G) и ELRM(G) совпадают. Если занумеровать прогнозы в цепочке выше начиная с нуля, то команды преобразователей таковы:

1.(Zo, ±,zo) - (0, A,Zo0)

2.(0,а, 0) - (1, Л, 01)

3.(1,а, 1) - (2, Л, 12)

4.(2, ±, 012) - (±, 1, 03)

5.(±, A,Zo03) - (f, 0,Zo)

Если алгоритм 5 применить первым к данному преобразователю, то последний превратится в неуменьшаемый конечный преобразователь. Если же применить первым алгоритм 6, то число прогнозов уменьшится, так как прогнозы 1 и 2, указывающие роли символа а, объединимы. После этого объединения изменятся команды 3 и 4:

3. (1,а, 1) - (1, Л, 11)

4. (1, ±, 011) - (±, 1, 03)

Теперь алгоритм 5 способен ликвидировать только магазинные символы 0 и 3, но не 1. Результирующий преобразователь останется магазинным:

1.(Zo, ±,Zo) - (0, Zo)

2.(0,Zo) - (1, Л,Zo1)

3.(1,а, 1) - (1, Л, 11)

4.(1, ±,Zo11) - (±, 1,Zo)

5.(±, Л,Zo) - (f, 0,Zo)

В детерминированном случае алгоритмы 5 и 6 можно интерпретировать как алгоритмы уменьшения LR(1)анализаторов. Вместе с приемом расщепления [Игнатов 87б] грамматики и приведенными выше необходимыми условиями объеди-нимости прогнозов они дают приемлемый на практике метод построения LR(1) анализаторов. Построенные таким образом LR(1) анализаторы будут, по видимо му, неулучшаемыми.

§3. Прием разделения в обработке языковых описаний

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