Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

няется графом в соответствии с правилами

грамматики.

Процесс

преобразований продолжается до тех

пор, пока не останется ни

одной нетерминальной вершины.

Определим теперь парные грамматики. Под парной

граммати­

кой понимается пара графовых грамматик

над одними и теми же

алфавитами вместе с соответствиями,

установленными

между

правилами этих грамматик и между

нетерминальными

вершинами

в правилах.

Пусть заданы:

1)

алфавиты AN, Ат, Ам\

2)

графы G и Н из множества Gl

(AN,

Ат,

Ам);

3)

нетерминальные вершины графа G •—

Nl={ne=NG\VG{n)

е Л „ } ;

4)

нетерминальные вершины графа Н —

NH={n^NH\VH(n)^AN}

,

V „ e / V o .

VG(n)

= Vn(h(n))

•

Парная

грамматика

определяется

как Г=

(AN,

Ат, Ам,

S,

Q),

где

AN,

Ат,

Ам — соответственно

алфавиты нетерминальных, тер­

минальных

символов и

меток

дуг, S^AN

— начальный

символ, а

Q —конечное

множество

наборов

(/, q,

к).

В этих

наборах /, q —

правила

таких графовых грамматик,

что

если

/

есть

правило

А—^G'o

и q — правило А1—>HTV,

то А=А'

и h — нетерминальная

вершина спаренных графов G и Н.

Пусть Г— (AN, AT, AM, S,

Q) — парная

грамматика.

Если

q =

= (/, р, / i ) & Q , то / называется левым правилом

q,

а

р — правым

правилом q, h — спаренная нетерминальная вершина q.

вой

Графовая

грамматика Г=

(AN, Ат, Ам,

S,

Р)

называется

ле­

(правой)

грамматикой,

если

Р представляет

собой

множест­

во левых (правых) правил Q.

Г,

Язык,

порождаемый

левой

(правой)

грамматикой

называ­

ется левым

(правым) языком.

Язык, порождаемый парной грамматикой Г, состоит из упоря­

доченных пар графов левого и правого языков.

Парная грамматика определяет пары графов, получаемые из

одного и того же начального

графа параллельно. На

каждом

эта­

пе преобразований имеется пара графов,

каждый

из

которых

включает

несколько нетерминальных вершин и соответствия

меж­

ду

этими

нетерминальными

вершинами. При каждом

преобразо­

вании пара

соответствующих

нетерминальных

вершин,

по одной

из графа,

заменяется в соответствии

с правилами

парной

грамма-

Спаренный граф X над алфавитами AN,

Ат,

Ам

определяется

как

X=(G, Я, h), где G и H^Gl

(AN{jAT,

Ам),

a

h — нетерми­

нальная вершина спаренных графов G и Я.

AN, Ат,

Терминальный спаренный граф Z

над

алфавитами

Ам

— это спаренный граф вида

Z={G,

Я,

А), в котором все вер­

шины графов G и Я являются

терминальными.

В

этом

случае

можно записать как Z— (G,

Н).

Пусть задана парная грамматика r=(AN,

Ат, Ам,

S,

Q) и па­

ра графов X=(GX,

Нх, hx)

и У = (Gy,

Ну, hy)

над алфавитами

AN,

Ат, AM-

выводится из X,

сле­

Будем говорить, что У непосредственно

дуя грамматике Г X=> У, если существует

правило

(/,

р,

h)^P,

нетерминальная

вершина п

в графе

G и нетерминальная

вершина

Будем

говорить, что

У выводится

из

X,

следуя грамматике Г

#

X

г<=>У,

если

существует

такая

последовательность

опарен-

ных

графов

2 Ь

Z2,...,Zn

над

алфавитом

(AN,

А-г, Ам),

что

Х =

— Z\,

y=Zn

и Zi

Z j + i

для

i=

1, 2, 3,...,

ft—

1.

Язык,

порождаемый

грамматикой

Г,

называется спаренным

языком, если он

определяется

как

L={X\X

— терминальный

спа-

*

ренный граф над алфавитами AN, АТ,

А

М И Sr

=> X).

Парная

грамматика

Г — однозначная,

если и левая и правая

грамматики,

принадлежащие

Г, — однозначны

и грамматика

Г не

Используя однозначную парную грамматику,

можно достаточ­

но легко

найти

элемент правого языка, соответствующий данному

элементу

левого

языка. Пусть Г — однозначная

парная граммати­

ка, левый

язык

которой — множество строк, а правый язык —мно-

ван следующим образом. Прежде всего для

строки X выполняется

грамматический разбор на основе правил

левой грамматики, ре­

зультат которого представляется в виде вывода

S=> Zx=> Z 2 = ^ . . .=>Zn

= X •

После этого, используя правила правой

грамматики и

соответст­

вия парной грамматики, строку X преобразуют в граф X'. Процесс

преобразования начинается с графа 5,

содержащего

единствен­

ную вершину, и включает точно п шагов.

Таким образом, парные грамматики

дают формальный аппа­

Изучение парных грамматик является

перспективным

не толь­

ко с точки

зрения формализации процессов трансляции, но и в

связи с широким применением графов как

в теории программиро­

вания,

так

и в организации процессов обработки информации.

В

этой

связи рассмотрим следующее

расширение

графовой

над алфавитами Ау,

Ам;

3) Я , (AV,

Ам)

=G\(AV,

Л м ) — набор всех Я-графов

первого

уровня;

над алфавитами Л у, Ам

4) Я-граф

к-го

уровня

— это

граф над

Hi

(Лу, Ам), Ам, содержащий хотя бы одну вер­

шину Нк-\\

5) Нк (Av,

Ам)

= {Х\Х — это Я-граф/с-го уровня};

6) Н(Ау, Ам) =\Зк2(Ип — это множество всех Я-графов

над ал­

фавитами Av,

АМ-

Введем теперь для каждой терминальной вершины дополни­

тельный параметр — метку. Теперь каждая терминальная

вершина

одинаковыми метками разрешается производить только

в

одном

и том же графе в пределах иерархии. Таким образом,

не

могут

Я-графа, а также

вершины,

расположенные в различных графах

одного уровня.

Введение меток облегчает процесс компиляции из строчного

языка в язык графов. В этом случае метки вершин

выполняют

примерно те же функции, что и таблица

символов.

В заключение

приведем

пример

представления

АЛГОЛ-про-

граммы (рис. 41)

в виде блок-схемного графа

(рис. 42) .получен­

ного в результате

преобразований по правилам

соответствующей

for

q.== I step 1 unti I m do

if

abs (af p, q.]) > у then

begin у : = abslafp, a])\i

.~p; k:~o end

etstg: = y

end

Рис. 41. Пример

АЛГОЛ-пропраммы

Следует особо подчеркнуть

перспективность

использования