2.4. МНОГОСВЯЗНЫЕ СТРУКТУРЫ

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

"Многосвязная структура" состоит из узлов с несколькими полями связи в каждом узле, а не только с одним или двумя в структурах из предыдущих примеров. Примеры использования множественных связей приводились выше, например, при моделировании работы лифта в разделе 2.2.5 и работе с полиномами по многим переменным в разделе 2.3.3.

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

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

1 SALES 1 PURCHASES

2 DATE 2 DATE

3 MONTH 3 DAY

3 DAY 3 MONTH

3 YEAR 3 YEAR

2 TRANSACTION 2 TRANSACTION

3 ITEM 3 ITEM (1)

3 QUANTITY 3 QUANTITY

3 PRICE 3 PRICE

3 TAX 3 TAX

3 BUYER 3 SHIPPER

4 NAME 4 NAME

4 ADDRESS 4 ADDRESS

Ha этой схеме некоторой конфигурации данных показано, что каждый элемент файла SALES (продажи) состоит из двух частей: DATE (дата) и TRANSACTION (транзакция). Причем DATE подразделяется на три части, а TRANSACTION - на пять частей. Аналогичные замечания относятся и к файлу PURCHASES (покупки). Относительный порядок имен указывает порядок, в котором эти величины предстают во внешних представлениях файла (например, на магнитной ленте или распечатанных формах). Обратите внимание на то, что DAY и MONTH в этих двух файлах представлены в разном порядке. Программист приводит и другую не показанную здесь информацию, которая сообщает о том, какое пространство в памяти занимает каждый элемент данных и в каком формате эти данные представлены. Подобные соображения несущественны для темы данного раздела, а потому не будут рассматриваться.

Программист при работе с языком COBOL описывает сначала формат файла и другие переменные программы, а затем - алгоритмы, которые оперируют этими величинами. Для ссыяки на отдельную переменную в приведенном выше примере было бы недостаточно просто указать имя DAY, так как не существует способа указания, в каком файле она находится: в SALES или PURCHASES. Следовательно, при работе с языком COBOL можно с помощью выражения DAY OF SALES указать, что элемент DAY является частью элемента SALES. Программист мог бы также записать в более полной форме, что

DAY OF DATE OF SALES,

HO, вообще-то, не следует придавать величинам больше квалификащш (описаний), чем это действительно необходимо, во избежание неоднозначности. Таким образом, выражение

NAME OF SHIPPER OF TRANSACTION OF PURCHASES

можно сократить до

NAME OF SHIPPER, поскольку существует только одна часть данных с именем SHIPPER.

Эти правила языка COBOL могут быть выражены более точно в следующей форме.

a) Каждому имени предшествует некоторое связанное с ним положительное целое число, которое называется номером уровня. Имя относится либо к простейшему элементу, либо к группе из одного или нескольких элементов со своими именами. В последнем случае все элементы группы должны иметь один номер уровня, который должен быть выше, че.м номер уровня для и.мени группы. (Например, элементы DATE и TRANSACTION в приведенно.м примере имеют уровень 2, который выше уровня 1 для элемента SALES.)

b) Для ссылки на простейший элемент или группу элементов с именем Ао используется общая форма

Ао OF Al OF ... OF A„,

где n > О, a Aj является именем элемента, который прямо или косвенно содержится внутри группы с именем Aj+i для О < j < п. Должен существовать только один элемент Ло, который удовлетворяет этому условию.

c) Если одно и то же имя Ло появляется в нескольких местах, должен существовать способ ссылки на каждый случай использования такого имени с помощью квалификации (описания).

Например, согласно правилу (с) конфигурация данных

1 АА 2 ВВ

3 СС (2)

3 DD 2 СС

недопусти.ма, так как при втором появлении эле.мента СС не существует однозначного способа ссылки на элементы с таким именем (см. упр. 4).

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

MOVE CORRESPONDING q ТО /3,

что приведет к перемещению всех элементов с соответствующими именами из области данных q в область данных /3. Например, команда языка cobol

MOVE CORRESPONDING DATE OF SALES TO DATE OF PURCHASES означает, что значениями переменных MONTH, DAY и YEAR из файла SALES нужно заменить значения переменных DAY, MONTH, YEAR в файле PUfiCHASES. (Относительный порядок DAY и MONTH при этом изменяется.)

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

Операция 1. Обработать описания имен и номеров уровней, подобных показанным на схеме (1), разместив соответствующ>ю информацию в таблицах внутри компилятора для использования в операциях 2 и 3.

Операция 2. Определить, справедлива ли заданная ссылка, квалифицированная согласно правилу (Ь), и, если справедлива, найти соответствующий элемент данных.

Операция 3. Найти все соответствующие пары элементов, которые указаны в команде CORRESPONDING.

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

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

Для определения значения ссылки на языке cobol

Ло OF Л1 OF ... OF An, n > О, (3)

сначала необходимо найти имя Ло в таблице символов. Причем должен существовать ряд связей от позиции таблицы символов ко всем позициям таблицы данных, которые относятся к этому имени. Затем для каждой позиции таблицы данных потребуется установить связь с эле.ментом-группой, в которую он входит. Тогда, если существует поле связи от позиций таблицы данных к таблице символов, нетрудно сообразить, как следует организовать обработку ссылок наподобие (3). Более того, чтобы найти пары, заданные в команде MOVE CORRESPONDING, потребуется установить некоторые связи от позиций таблицы данных для каждого элемента-группы к отдельным элементам этой группы.