AOP_Tom1 (1021736), страница 123
Текст из файла (страница 123)
Третий, и последний, из нужных иам алгоритмов имеет отиошсние к команде МОЧЕ СОБКЕБРОМО1МО. Прежде чем приступить к созданию алгоритма, нужно четко сформулировать его назначение. В языке СОВОГО выражение МОЧЕ СОНЕЕБРОМО1МО а ТО Д, (7) где а и Д вЂ” ссылки наподобие (б) иа элементы данных, обозначает сокращенную запись множества всех выражений типа МОЧЕ а' ТО Д', для которых существует такое целое число и > О и такие и имен Ае, Аы, .., А -ы что а'=Ас ОРА1 ОР ... ОБА„1 ОРа, (8) д' = А, ОР А1 ОР... ОР А„, ОР )у и либо а', либо,9' является простейшим элемеитом (а не группой элементов). Более того, иеобходимо, чтобы в (8) была указана полная квалификация первых уровней, а именно — что А +1 является родителем А для 0 < ) < и.
а' и Д' должвы располагаться в дереве на и уровней виже, чем а и Д. Для рассматриваемого здесь примера (4) выражение МОЧЕ СОВВЕБРОМО1МО А ТО Н является сокращенной формой записи выражений МОЧЕ В ОР А ТО В ОР Н МОЧЕ 6 ОР Р ОР А ТО 0 ОР Р ОР Н Алгоритм- для распознавания соответствующих пар а',,8' несмотря на свою простоту довольно интересен, т. е. необходимо совершить обход дерева с корнем а в прямом порядке, одновременно выискивая в дереве 8 совпадающие имена и пропуская поддеревья, в которых появление соответствующих элементов невозможно. Имена Ло,...,Л„~ из (8) располагаются в обратном порядке: Л„ы...,Ло.
Алгоритм С (Поиск соошоеплсплоующпх пар). Для заданных РО и ЦО, которые указывают иа позиции таблицы данных для а и 8 соответственно, этот алгоритм последовательно находит все пары указателей (Р, Ц) на элементы (а', ))'), удовлетворяющие упомянутым выше требованиям. С1. [Инициализация.] Установить Р ~ — РО, Ц е — ЦО. (В оставшейся части этого алгоритма указательные. переменные Р и Ц совершают обход деревьев с корнями а и ~3 соответственно.) С2.
[Простейший элемент?] Если СН1ЕО(Р) = Л или СН1ЕО(Ц) = Л, то вывести (Р, Ц) как одну из искомых пар и перейти к шагу С5. В противном случае установить Р ( — СН1ЕО(Р), Ц +- СН1ЕР(Ц). (На этом шаге Р и Ц указывают на элементы а' и ЛЧ', удовлетворяющие (8), а команду МОЧЕ а' ТО Д' необходимо выполнять тогда и только тогда, когда либо а', либо ))' (или оба сразу) — простейший элемент.) СЗ. [Сравнение имен.] (Р и Ц указывают на элементы данных, которые соответственно имеют квалификацию в виде Л ОРЛлОР...ОРЛ„ и В ОРЛИНОЕ...ОРЛо ~ОР,З. Теперь задача заключается в том, чтобы узнать, можно ли сделать так, чтобы Ве = .4о, проверяя все имена в группе Л~ ОР...
ОР .4„, ОР )).) Если МАМЕ(Р) = МАМЕ(Ц), то перейти к шагу С2 (найдено совладение). В противном случае, если Б1В(Ц) Э~ Л, установить Ц <- Б1В(Ц) и повторить шаг СЗ. (Если БХВ(Ц) = Л, значит, в этой группе иет соответствующего имени и следует перейти к шагу С4.) С4. [Продвижение.] Если Б1В(Р) ф Л, то установить значения Р < — Б1В(Р), Ц <— СН1ЕО(РАВЕМТ(Ц)) и вернуться к шагу СЗ. Если Б1В(Р) = Л, то установить Р ~- РАВЕМТ(Р) и Ц ~ — РАКЕМТ(Ц) Сб. [Готово?] Если Р = РО, то прекратить выполнение алгоритма; в противном случае перейти к шагу С4. 3 Блок-схема этого алгоритма показана на рис. 41.
Доказательство корректности алгоритма можно легко получить с помощью метода индукции по размеру обрабатываемых деревьев (см. упр. 9). ответств найдено Рис. 41. Алгоритм для выполнения команды ИОЧЕ ООААЕБРОМО1МО. Теперь рассмотрим способы применения пяти полей евязи (РЕЕЧ, РАЕЕМТ, МАМЕ, СИ11.О и Б1В) в алгоритмах В и С. Замечательно то, что эти связи образуют "полный набор" в том смысле, что алгоритмы В и С действительно выполняют минимальный объем работы при продвижении по таблице данных. И всякий раз, когда нужно сослаться на другую позицию таблицы данных, ее адрес сразу же становится доступным, поэтому нет необходимости проводить дополнительный поиск. Трудно представить, как можно было бы сделать алгоритмы В и С более быстрыми, включив в таблицу дополнительную иггформацггю о связях (см., однако, упр.
11). Каждое поле связи может рассматриваться как ключ к этой программе, который используется длн ускорения работы алгоритмов, (Конечно, алгоритм для построения таблиц, т. е, алгоритм А, выполняется медленнее, поскольку он имеет больше связей, которые необходимо заполнить. Но таблица строится лишь один раз,) С другой стороньг, ясно, что в построенной выше таблице данных содержится гораздо больше избыточной информации.
Посмотрим, что произойдет, если ггдалцпгь некоторые поля связи. Связь РВЕЧ, хотя она и не используется в алгоритме С, имеет большое значение в алгоритме В и, похоже, является существенной частью любого компилятора языка СОВОГО, за исключением случаев, когда требуется выполнять длительные операции поиска, Следовательно, поле, которое связывает все элементы с одинаковыми именами, имеет большое значение для эффективной работы.
Поэтому стратегию действий в такой ситуации можно слегка модифицировать и вместо связи Л в когще каждого списка применить циклическое связывание. Но этого не стоит делать, когда поля связи не изменяются и не удаляются. Связь РАМЕМТ используется в алгоритмах В и С, хотя можно обойтись и без нее, если в алгоритме С применить вспомогательный стек или добавить связь Б1В так, чтобы задействовать связи-нити (как в разделе 2.3,2). Таким образом, становится ясно, что связь РАИЕМТ используется только е алгоритме В.
Если бы поле Б1В было связью-нитью, чтобы элементы со значением поля связи Б1В = Л содержалн вместо него значение Б1В = РАВЕМТ, можно было бы найти родителя любого элемента данных, следуя по связям Б1В. Добавлеггггые связи-нити можно отличить либо с помощью нового поля ТАО в каждом узле, в которокг указывалось бы, что поле Б1В содержит снязь-нить, либо с помощью условия Б1В(Р) < Р, если позиции таблицы данных хранятся последовательно в памяти в порядке появления, Это значит, что на шаге В5 придется выполнить короткий поиск, а сам алгоритм соответственно станет работать медленнее, Связь МАМЕ используется в этих алгоритмах только на шагах Вб и СЗ.
В обоих сггучанх можно было бы выполнить проверку МАМЕ(Б) = Р» и МАИЕСР) = МАИЕЯ) иначе, если бы связь ИЛИЕ отсутствовала (см, упр, 10), ио это существеиио замедлила бы выполнение внутренних циклов в алгоритмах В и С. Ясна, чта здесь снова имеет место компромисс между экономией пространства для связи и скоростью выполнения алгоритмов. (Скорость работы алгоритма С ие так уж важна для компиляторов языка СОВОЬ, если рассматривать типичные способы употребления команд ИбтЕ СОЯЯЕВРСНЭХНС, Однако алгоритм В должен работать быстро.) Известно, что связи ИЛИЕ используются и для выполнения других важных задач в компиляторе языка СОВ01., особенно при выводе диагностической информации.
Алгоритм А постепенно создает таблицу данных, причем никогда ие приходится возвращать узлы в область свободной памяти, Поэтому позиции таблицы данных обычно располагаются в последовательных ячейках памяти в порядке появления элементов даииых в исходиой программе иа языке СОВОЬ, Таким образом, в нашем примере (б) ячейки А1, ВЗ, ... будут располагаться одна за другаЯ, Такой последовательный харахтер размещения ячеек в таблице даипых позволяет существенна упростить работу. Например, связь СН1Ю каждого узла либо раева Л, либо указывает иа узел, который следует сразу же эа пим, поэтому пале СН1Ы можно сократить до размера 1 бит, Или поле СН1Ы можно удалить и вместо нега проверить условие РЛНЕНТ(Р+ с) я: Р, где с — размер узла в таблице данных. Таким образом, необязательно испольэовать сразу все пять полей связи, хата оии очень палезиы для ускорения работы алгоритмов В и С, Эта ситуация весьма типична для большинства многосвязных структур, Иитересио отметить, что по крайней мере полдюжины разработчиков компиля.
торов СОВО1 в начале 60-х гадов независимо пришли к одному способу оргаиизеции таблицы данных с помощью пяти связей (или четырех из пяти, так как связь СН100 обычно це испальзуетсв), Впервые описание такога метода было опубликовапа Г. В. Лоусоном (мл.) (Н. %. 1азуэап,,1г.) [см, АСМ А2аг)опа1 Сапйегепсе 0!Наес (Вугаспэе, ХХл 1060]. Одиако Дэвид Дам (йау!б Ов)зщ) в 1063 гсщу предложил оригинальный метод, который позволяет получить тат же результат, что и при работе с алгоритмами В и С, ио с использованием двух полей связи и паследовательиога распределения позиций в таблице данных беэ существенного снижения скорости выпалиеиия (см.
упр. 10-14), УПРАЖНЕНИЯ 1. 100] Если конфигурации даииых в языке ООВОь рягсмятрияать как древовидные структуры, то в каком порядке оии записяиы: в прямом, обратном или ии в одном из иих2 й. ]!О] Оцените время вьщолиоиия алгоритме А, 3. ]яб] Структуры дяииых языка Рь/! подобны структурам языка ООВО1., ио в иик допугтимя любая последоватольиость номеров уровией.
Например, последовательность 1 Л 1 Л 3 В 3 В Б С зкеивялеития последовательности 3 С 4 и 3 б 3 В 3 В В итоге правило (а) изменяется таким образом: "Элементы группы должны имать иезозрастзющую послоловательиогть номеров уровиой, причем вге оии должны быть болыпе номере уровия группы ляпиоя группы". Кяк иообхсдимо измаиигь ялгоритм А, чтобы выполнить переход от соглашений, принятых для языка СОВОЬ, к соглашениям, принятым для языка Р1./1? 4. [35) Алгоритм А не позволит обнаружить ошибку, если программист в СОВО1.-программе нарушит упомянутое в этом разделе правило (с). Как следует изменить алгоритм А, чтобы принимались только те структуры, которые удовлетворяют правилу (с)? б. [30) На практике алгоритм В может получать из входного потока связанный список ссылок на таблицу символов, а не то, что прежде называлось "Ра,Ры,Р„".
Пусть Т является такой указательной переменной, что ТМРО(Т) гя Ра, ТЕРО(ЕЬТМБ(Т)) = — Р„ ..., ТЕРО(БЬТМЕ1"1(Т)) = Р„, БЬТМБ("+О(Т) = А. Покажите, как изменить алгоритм В, чтобы в нем в качестве входного потока можно было использовать связанный список. 6. (23) В языке Р1./1 допускается использование структур данных, которые во многом подобны структурам языка СОВОЬ, на без применения ограничения (с). Вместо этого получим правило, по которому квалифицированная ссылка (Б) является однозначной, если Указана "полнаЯ" квалификациЯ, т. е. если Аз<.~ — Родитель А~ длЯ О < 1 < и и если А„не имеет родителя. Ограничение (с) теперь сведено к простому условию, согласно которому никакие два элемента данных группы не могут иметь одно и то же имя, На второе появление СС в (2) можно было бы недвусмысленно сослаться с помощью ссылки "СС ОР АА", а на трн элемента данных 1 А 2 А 3 А можно было бы в соответствии с соглашениями, принятыми в языке РЬ/1, сослаться в такой форме: "А", "А ОР А", "А ОР А ОР А".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
