языков. Крме того, не уступая известным в лаконичности, КСвыражения подробней и наглядней указывают закон образования цепочек языка из "подчинен-ных"цепочек. КСвыражения обобщают регулярные [Kleene 56]; есть надежда, чт они приближают нас к адекватной алгебраической трактовке магазинных автома -тов и бесконтекстных грамматик.

Легко вообразить, что между магазинными автоматами и бесконтекстными грамматиками существует соответствие (назовем его сходством), при котором ядра соответствующих объектов определяют одно и то же бесконтекстное выра -жение. В связи с этим возникает надежда на существование практически полез -ных алгоритмов, преобразующих одни описания бесконтекстного языка в другие. К полезным следует отнести алгоритм преобразования бесконтекстной грамма тики в магазинный автомат, не слишком громоздкий по сравнению с исходной грамматикой (ср. задачу уменьшения LR(k)анализаторов, о которой речь пойдет ниже).

Построение по магазинному автомату схожей бесконтекстной грамматики рас -смотрено А.А.Вылитком [Станевичене -Вылиток 93], [Вылиток -Станевичене -Чернцов 96], [Вылиток 98]. В последней работе доказано, что в этой грамма -тике сохраняется однозначность, детерминированность (в виде LR(1)свойства), одноповоротность (в форме линейности), неспособность к согласованной итерации двух непустых цепочек и некоторые другие свойства исходного автомата. Заметим, что А.А.Вылиток использует лишь подмножество ядра магазинного ав -томата, достаточное для построения схожей грамматики. На самом деле этого подмножества достаточно, по видимому, и в большинстве задач, но допущенная в определении ядра избыточность облегчает доказательство некоторых теорем. Заметим еще, что в [Вылиток 96] получена верхняя оценка длин путей, рассмот рение которых требуется для построения ядра D графа, существенно лучшая, чем приведенная в настоящей работе. Основной фактор, обеспечивший улучше -ние оценки - возможность рассматривать входящие в ядро пути не целиком, а по некоторым их участкам.

Отметим теперь, что кнутовские LR(1) таблицы - это представление преобра зователя с магазинной памятью, который сопоставляет входной цепочке ее раз бор относительно грамматики, определившей таблицы. При оптимизации такого преобразователя необходима схожесть старого и нового преобразователей, что бы исходный синтаксис не был "забыт". Так как только требование схожести и ограничивает в выборе средств оптимизации, перебор преобразователей некото рого конечного множества позволяет найти минимальный, например, по числу состояний (кстати, уменьшение LR(1) таблиц, предлагаемое в известных работах, обычно можно интерпретировать как уменьшение числа состояний обсуждаемых здесь преобразователей).

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

Некоторые особенности LR(k) таблиц, заведомо обеспечивающие их уменьше ние, были замечены многими исследователями. Были даже выделены подклас -сы LR(k) грамматик, имеющих LR(k) анализаторы сравнительно малого объема. Наиболее известны подклассы SLR(k) и LALR(k) грамматик, определенные в

[DeRemer 69], [DeRemer 71]. Интересно, что распространение идеи 1(к)метода на грамматики более общих классов (кроме наших работ, упоминавшихся выше, и [Lee -Choe 94] укажем [Walters 70] и [Шумей -Зонис 75], где рассматриваются контекстные грамматики), также может быть связано с приемами уменьшения таблиц анализатора. Выработанная техника уменьшения LR(k)таблиц может быть обобщена в совокупости условий, которая отсеет подавляющую часть безуспеш ных вариантов.

В данной работе (см. также [Станевичене 96б]) вопрос уменьшения LR(k)-таблиц решается как подзадача более общей задачи. Мы указываем метод синтаксического анализа бесконтекстных языков, реализуя идею схожести синтакси ческих описаний и распространяя идею LR(1) метода на случай всех бесконтекст ных грамматик. Наш метод имеет ту общую черту с известным алгоритмом Эрли [Earley 68], что дает тем более эффективный анализатор, чем "лучше"грамматика. В частности, если грамматика принадлежит LR(1) классу, то наш метод обеспе чивает построение LR(1) анализатора. Вообще, анализатор отражает все черты исходной бесконтекстной грамматики, так как он строится по ее ядру и может быть представлен преобразователем с магазинной памятью, который основан на магазинном автомате, схожем с заданной грамматикой. В случае праволинейной грамматики соответствующий преобразователь легко превращается в конечный.

Итак, в нашей работе суммируются и усиливаются результаты исследований LR(k) метода, не прибегающих к обработке грамматики "по частям". Но мы счи таем очень важной идею работы [Korenjak 69], в которой рассматривались эври -стические приемы разбиения грамматики с тем, чтобы построить LR(k) таблицы по частям, каждая из которых не слишком велика.

Идея Кореньяка развита в работах [Игнатов 86], [Игнатов 87а], [Игнатов 87б], выполненных под нашим руководством. Там построен формальный алгоритм раз -биения грамматики, управляемый отношением, определяемым также формально и указывающим группы нетерминальных символов, разъединение которых по раз -ным подграмматикам нежелательно. Определение данного отношения выражает фактически некоторые особенности магазинного автомата, схожего с грамматикой (в смысле, указанном выше) и лежащего в основе LR(k) анализатора.

В нашей работе идея расщепления языкового описания с целью обработки по частям получила дальнейшее развитие. В главе 2 приводятся алгоритмы преобра -зования D графа в КС выражение и конечного автомата в регулярное выражение, базирующиеся на отщеплении частей обрабатываемых графов, которые (части) определяются с помощью понятия сильно связной компоненты графа.

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

Предыдущее обсуждение показывает полезность нашего подхода, применяюще го понятия Dграфа и КСвыражения. Рассмотрим еще два примера, когда наш подход обеспечивает заметные результаты. Они касаются трудных алгоритмиче ских проблем: регулярности и эквивалентности в классе детерминированных язы -ков. Эти проблемы были впервые поставлены в [Ginsburg -Greibach 65]. В статьях [Stearns 67], [Valiant 75] и др. излагаются доказательства разрешимости пробле -мы регулярности языка, допускаемого детерминированным магазинным автома том. В статьях [Мейтус 92] и [Senizergues 97] представлены два доказательства

алгоритмической разрешимости проблемы эквивалентности детерминированных магазинных автоматов.

В работе [Stearns 67] изложение ведется, по словам автора, "на слегка неформальной основе"с целью облегчить чтение. Это решение автора вряд ли удачно: работа непонятна (обсуждение некоторых ее неясностей приводится в главе 3 настоящей работы), и возникает сомнение не только в правильности приведенных в ней оценок, но даже и в разрешимости рассматриваемой проблемы.

Последующие работы направлены на уменьшение сложности алгоритма проверки регулярности детерминированного языка. К сожалению, и они не свободны от пробелов и неясностей, а работа [Shankar -Adiga 91, 92], за рубежом признанная, повидимому, как наиболее успешная, на самом деле ошибочна. Ошибочен алгоритм проверки регулярности детерминированного языка, основанный на убе ждении авторов в отсутствии LR(1) грамматик с самовставлением, порождающих регулярные языки. (Впрочем, допустимо и то, что они убеждены в обратном, но не разглядели законов взаимосвязи LR(1) грамматик с изучаемыми графами из за громоздкости последних. По существу, в [Shankar Adiga 91, 92] рассматривают ся наши D графы, но очень специфические и большие в случае даже самых про стеньких грамматик. Эти графы описывают переходы LR(1) анализатора и более обширны, чем LR(1) таблицы, так как, в отличие от таблиц, раскрывают технику свертки по правилу грамматики.) Пример с языком {ambanb\m > 1, n > 0} в нашей главе 3 доказывает, что они заблуждаются. Вариации примера опублико ваны в нескольких наших работах, достаточно давних, в том числе в "Докладах РАН"(см. [Станевичене 95]), которые переводятся на английский язык. Но, по -видимому, зарубежные читатели не заметили этой публикации или не сделали из нее надлежащих выводов.)

В нашей работе определяются праволинейные магазинные автоматы, рассмот ренные в [Станевичене -Чобан 94] и [Stanevichene -Choban 94] под другим названием. Об автоматах этого подкласса можно сказать, что они аналогичны праволинейным грамматикам, которые являются частным случаем грамматик без самовставления, введенных Н.Хомским [Chomsky 59a], [Chomsky 59b]. Праволи -нейный автомат допускает регулярный язык. Конечный автомат легко интерпре тировать как праволинейный магазинный автомат частного вида, поэтому спра ведливо и то, что любой регулярный язык допускается некоторым праволинейным магазинным автоматом. Таким образом, имеем еще одну характеристику регулярных языков.

В работе [Вылиток 98] найден более общий класс магазинных автоматов, ха -рактеризующий регулярные языки.

Мы устанавливаем, что праволинейность магазинного автомата распознается по его ядру (причем в детерминированном случае достаточно лишь сравнительно просто устроенных элементов ядра), и получаем достаточное условие регулярно сти бесконтекстного языка. В главе 3 на этой основе очень просто формулируется частичный алгоритм проверки регулярности бесконтекстного языка.

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