При оценке времени работы шага 3 естественно учесть время tb поиска в множествах

Alter natives(i), i G AN ames(C), элементов минимальной длины.

Подытоживая, получаем верхнюю оценку

+ ...«с n + max{t,V G ANames<C)}),

где к31 и к32 - некоторые коэффициенты, на значения которых могут повлиять лишь способ представления обрабатываемых данных и удачность приемов обра ботки.

Время tt в худшем случае пропорционально величине , так как число элементов в Alternatives(i) не превосходит числа гнезд в (0С)0. Заменяя tt на k33 • , преобразуем формулу оценки:

(.31 + .32 1 +2k33 lANames(C)) • nc.

Вводя обозначение k3 для не зависящего от характеристик КСвыражения С коэффициента k321+2fc33, имеем оценку

(.31 + кз • lANames(C)) • nc

времени работы шага 3.

Для оценки времени работы шага 2 алгоритма 3 существенны временная оценка процедуры Replacement и число ее применений. Последнее равно lANames(C). В самом деле, правила изменения алгоритмом значений величин Building и Storey обеспечивают однократное попадание в Storey каждого имени i G ANames(C) и, следовательно (см. "заголовок цикла", представленного действием 2.1), однократное применение процедуры Replacement для каждого имени i G ANames(C).

Сама процедура Replacement движется одновременно по Sqz и по Embeddings(i), обрабатывая m < (см. вспомогательные обозначения процедуры) вхождений заглушек. Время движения можно считать пропорциональным

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

Итак, время работы шага 2 не превосходит

к2 • ANames(C) • n2-,

где к2 - некоторый не зависящий от характеристик С коэффициент.

Следовательно, время работы алгоритма 3 в целом можно считать пропорцио нальным произведению квадрата длины исходного КС выражения на число имен его гнезд.

Глава 2

ОБ ОПТИМИЗАЦИИ РАСПОЗНАВАНИЯ И СИНТАКСИЧЕСКОГО

АНАЛИЗА БЕСКОНТЕКСТНЫХ ЯЗЫКОВ

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

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

В параграфе 3 даются оригинальные алгоритмы преобразования конечного ав -томата в регулярное выражение и Dграфа в КСвыражение. На их примере показывается, что причиной успеха методов, расщепляющих языковые описания для переработки, является определенное подчинение частей этих описаний; упомяну тое подчинение удобно выразить в терминах сильно связных компонент графов. Указывается, что в силу установленной взаимосвязи грамматик, автоматов и D -графов, техника рассмотренных алгоритмов может быть перенесена, например, на случай преобразования бесконтекстной грамматики в анализатор.

§1. Магазинные автоматы, наполняющие магазин в реальное время

Одна из проблем, связанных с бесконтекстными языками, состоит в построе нии такого магазинного автомата, который допускает язык с наименьшей затратой времени. С точки зрения приложений особенно важно добиваться эффективно сти детерминированных магазинных автоматов (ДМА). ДМА эффективен в том смысле, что имитирующий его алгоритм работает без возвратов. Однако для ДМА допускаются такты, которые не читают входных символов, перерабатывая, воз можно, содержимое магазина. ДМА, действующий в реальное время (ДМАРВ), можно считать идеалом: ему требуется ровно n тактов, чтобы допустить цепочку длины n. Некоторое исследование ДМАРВ проведено еще в [Ginsburg -Greibach

66], где они не имеют какоголибо специального названия; данный термин заимствован из [Романовский 86]. Известно [Ginsburg -Greibach 66], что ДМАРВ составляют собственный подкласс класса ДМА.

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

Рассматриваемый здесь алгоритм отличается от аналогичного алгоритма рабо ты [Кузнецова -Ожиганов -Сагинтаева -Станевичене 90] способом устранения зацикливающих конфигураций (последний термин см., например, в [Aho -Ullman 72]), позволившим упростить как формулировку алгоритма, так и его обоснова -ние.

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

В разделе 1.2 формулируется определение зацикливающей конфигурации мага зинного автомата и рассматривается алгоритм устранения зацикливающих кон фигураций ДМА. По существу, здесь построено новое доказательство однознач -ности детерминированного языка.

В разделе 1.3 дается определение магазинного автомата, наполняющего мага -зин в реальное время (АНРВ), и с помощью результатов предыдущего раздела доказывается, что каждый детерминированный язык допускается некоторым де терминированным АНРВ (ДАНРВ).

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

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

В данном параграфе, если не оговорено особо, полагаем, что след каждой ко манды магазинного автомата

M = (K, Е, Г, Zo, 8, po, F)

имеет один из видов: -Z, Z е Г, или +7, 7 е Г*. Таким образом, запрещаются только следы вида -Z + 7, где Z е Г, 7 е Г+. В остальном магазинный автомат произволен. Рассматриваемые далее преобразования магазинных автоматов не нарушают указанных ограничений на вид следа команды.

Термин "накапливающая", введенный в главе 1, будем теперь применять и к команде со следом +7, где y > 1.