Покажем, что для любой сильно связной компоненты B автомата A и любой ее вершины p регулярное выражение Cycles(p) задает все циклы с концевой вершиной p. Действительно, пусть п - дуга данной сильно связной компоненты и beg(n) = p. Рассмотрим слагаемое Bound(n), используемое для определения выражения Cycles(p). По предположению индукции его подвыражение E(Finite(B,n)) задает все пути из end(n) в beg(n) = p, не содержащие дуги п. Таким образом, выражение Bound(n) задает все циклы с концом p, которые начинаются дугой п и не содержат других ее вхождений. В целом сумма, стоящая под знаком итерации в определении выражения Cycles(p), задает все циклы с концом p, первая дуга которых в них не повторяется. Заметим, что произвольный цикл с концом p - это последовательность таких циклов. Но тогда ясно, что итерация рассматриваемой суммы задает все пути из p в p.

Отсюда следует, что сумма E(A) задает все пути, начальная вершина которых есть p0, а конечная принадлежит множеству заключительных вершин автомата A □

Определение регулярного выражения E(A) влечет рекурсивный алгоритм преобразования конечного автомата в эквивалентное регулярное выражение.

Пример 4. Рассмотрим детерминированный конечный автомат

A = ({po,pi,p2,ps}, {a,t)}, 5, po, {p2}),

где 5 определяется следующим списком команд:

(po,a) - pi, (pi,a) - p2, (pi,b) - p3,

(p3,b) - p1,

(p3,a) - p3.

Ранг автомата равен двум, так как его нетривиальная сильно связная компо нента C (ее вершины - p1, p3, дуги - p1 bp3, p3bp1, p3ap3) имеет ранг 1. Действительно, она содержит нетривиальную сильно связную компоненту и после вычитания любой одной ее дуги.

Множество Lines(A) включает только один путь:

poap1ap2.

Его промежуточная вершина p1 является вершиной сильно связной компоненты

Подвыражение Cycles(p1) регулярного выражения E(A) определяется произведением

(p1bp3)E (B),

B = Finite(C, p1bp3).

Нетрудно вычислить E(B):

E (B) = (p3ap3)*p3bp1

Следовательно,

E (A) = poap1(p1bp3(p3ap3)* p3bp0>1 ap2.

Отображая дуги в их пометки, получаем, что исходному автомату отвечает регулярное выражение

а(Ьа*Ь)*а.

3.2. Преобразование Эграфа в КСвыражение.

Идея обработки формальных синтаксических описаний по частям возникла давно. Наиболее заметные ее воплощения связаны с трудностями реализации LR(k)-анализаторов [Korenjak 69], [Игнатов 87а], [Игнатов 87б]. По сути разработчики компиляторов всегда прибегают к разделению языковых описаний, зачастую отступая от синтаксиса, предложенного создателями языка. Так, синтаксис язы -ка АЛГОЛ68 получил любопытное преломление: рассмотренная в [Мартыненко 98] реализация языка использует систему регулярных выражений, алфавиты ко торых включают "семантические символы- действия по обработке контекстных условий.

Подходы упомянутых выше работ [Korenjak 69], [Игнатов 87а], [Игнатов 87б] ценны тем, что система частей, заменяющих исходную грамматику, не требует особых ухищрений по прослеживанию связи понятий исходного и производного описаний языка. Алгоритм расщепления грамматики, предложенный в [Korenjak 69], рассчитывает на вмешательство человека; в [Игнатов 87а], [Игнатов 87б] работа по расщеплению полностью автоматизирована. В [Korenjak 69], [Игнатов 87а], [Игнатов 87б] показано, что приближения языков программирования КС -грамматиками хорошо поддаются расщеплению, хотя не каждая КСграмматика может быть расщеплена на части, допускающие некоторую независимую их об работку, необходимую для создания анализатора.

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

Наш метод разделения D графа предполагает применение алгоритмов на графах [Рейнгольд - Нивергельт -Део 80], что является, повидимому, новшеством в технике обработки языковых описаний. Большую роль при этом играет понятие сильно связной компоненты графа.

В разделах 3.2.1-3.2.2 изучается состав и взаимозависимость сильно связных компонент D графа в связи с наблюдаемым в D графе явлением парности дуг. Оказывается, D граф может иметь циклы, которые никогда не итерируются в маршрутах, т.е. наряду с маршрутом T{T2T3, где T2 - подобный цикл, не суще -ствует маршрутов вида T[TT для произвольного натурального числа п. Алго -ритм выявления таких циклов вытекает из определения линейной дуги (см. раздел 3.2.1). Он не требует образования каких либо циклов, но требует построения всех сильно связных компонент D графа.

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

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

В разделе 3.2.4 исследуется возможность переноса на случай Dграфов техники расщепления сильно связных компонент, предложенной в разделе 3.1 в качестве основы построения регулярного выражения по конечному автомату. Выясняется, что попытка такого переноса наталкивается на значительные трудности, связан ные с непредсказуемостью числа и характера вхождений парных дуг в циклы формантов. Устанавливаемая здесь верхняя оценка числа вхождений фиксированной пары дуг в схемы велика и влечет долгий перебор вариантов вхождений.

В разделе 3.2.5 дается метод разложения линий и схем, т.е. некоторых очень просто устроенных маршрутов, на элементы, определяющие производимые независимо друг от друга компоненты искомого КСвыражения. Формулируется алгоритм построения КСвыражения по Dграфу.

Эквивалентное Dграфу D КСвыражение, метод построения которого рассматривается в настоящей работе, обозначается через Expr(D). Для построения вы -ражения Expr(D) строится выражение E(D) над алфавитом E(D), определяющее язык Sentences(D).

3.2.1. Лоскуты. Линии

D = (V, Е, P,\,Po,F) есть Dграф, P С P, E С E(D), I, F С V. Тогда назовем пятерку

PD = (D,E, P,I, F)

лоскутом D - графа D. Здесь I - множество входных вершин лоскута PD, F - множество его заключительных вершин.

Пусть T Е E* - маршрут Dграфа D; пусть каждый нейтральный участок маршрута T является цепочкой из Lp. Тогда назовем T маршрутом лоскута PD. Если pair(T) Е I х F, то назовем T предложением лоскута PD.

Пример 5. При определении маршрута лоскута нельзя ограничиться требова -нием T Е E*. Действительно, рассмотрим Dграф

A . B . C

D : -ОО-Ос D множеством

P = {(1, 2), (3, 4), (1, 4), (3, 2)}

и его лоскут

PD = (D, {1, 2, 3, 4}, P - {(3, 2)}, {A}, {C}).

E* содержит все маршруты D графа D, число которых бесконечно; однако данный лоскут имеет только два предложения: 14 и 1234. Понятия, вводимые далее для