Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 83
Текст из файла (страница 83)
Например, по аналогии с алгоритмом 11.8 можно построить таблицу значений Вл)(б, Я), равных 1, если в 1Н(Я) есть определение 3, н 0 в противном случае. Вначале пусть 1(л)(3, Я) = 1 тогда и только тогда, когда нз некоторой вершины Я' ведет дуга в Я н б0ОЕН (Я'). Для каждой единицы, добавленной в таблицу, скажем на элемент (б, Я), помещаем 1 в элемент (с(, Я'), если есть дуга из Я в Я" н Я не убивает И. *11,4,24. Покажите, что приведенный выше алгоритм правильно вычисляет 1К(Я] и занимает 0(лтл)времени на графе управления с н вершинамн, не более чем 2л дугами и гл определениями. *1!.4.25.
Дайте алгоритмы, аналогичные прнзеденному вюпе и решающие те же аадачи, что и в упр. 11.4.!9 и 11.4.20. Как быстро они работают? "*11.4.26. Приведите алгоритмы, тратящие 0(и)ойи) элементарных векторных шагов на вычисление функций Вх алгоритма 11.7 илн упр. 11.4.19 для графов управленвя с л всршннамн. *е11.4.27. Покажите, чта граф управления свалим тогда н только тогда, когда множество его дуг можно разбить на два таких множества Е, н Ем что 1) Е, образует ориентированный ацнн- 44? гл гг оптнмизьция кодл ))раблсжсг д,гя иссмдовиния Замечании ио литературе лический граф и 2) если (и, п) принадлежит Е„ то т =л нлн и доминирует над ш.
**11.4.28. Приведите алгоритм, вычисляющий прямые домина- торы сводимого графа с и вершинами за время 0(п 1ойп). 11.4.29. Предложите дополнительную информацию относи- телы!о потока данных (не упоминаемую в алгоритме П.7 и упр. 11.4.19 н 1)А.20), которая пригодилась бы для целей оптимиаации кода. Дайте алгоритмы, вычисляющие зту инфарьгацию как для сводимых, так и для несводимых графов управления.
11.4ийб. Существуют ли методы вычисления функций ! М алгоритма )).8 или других фуннций, связанных с потоком данных, которые были бы предпочтительнее для расщеплении вершин несводимых графов? Под „предпочтительностью" ыы понимаем, что допустимы операции над ьлемеитарнымн векторами и чта адгпритмы упр. !1.4.24 н 11.4.28 становятся явно оптнмальнымн.
Подход к аптнмнзаця«с тнчк» зрения вналнзз интервалов был оазвнт Коком (|970) н затем разработан Коком н Шварцем (1970) н Лллсном (|970). Кеннеди (1971) рассиагрнваег глобальсмй алгоргим, нспольэующнй апалнз интервалов для распознавания в программа«гнвнмх переменных (упр.! ! 420) Решения упр. Н 4.32 — !|М |О можно нейт» у Хекта н Ульмана (|072а). Упр.
11.4,17 взято нэ работы Хо«крафта н Ульманз [197261. Ответ на узр. ||ЛШ наина нзщ удока |ВТШ ил«шефера(щт33. Унр. 11424 н Н426 езаги у Ульмана 1197263, упр. |1.4.27 — у Хекга ° Ульмана (19726), упр Н 4.28 — у Агю н др. (1972). В риде сгвгей абсуждае ся реалнзасня огпнинзн.
рующьх «смпннягоров. Лаури н Мелло« 319693 привалят нскогорие огинмнэацнн, прнмепненме в «ампнлнгоре053360ГОЯТЯАК Н. Вузам н Энглунд [3969) оцнсмзают методы для распоэнзвання абщнх подвмрзженнй, у«злсння ннзарнангнмк вмснсленнй нз цнклоз н распрслелення регнст|юз ала «ругога компиляторе с Фортране. Кнут (!97|!собрал много программ на Фортране н проаналнгнроеал нскагорыс нх «зрактернст «нг). ') Анализ патоке «анпых, нсяользующнй представление программа з энде операторной схемы, приме ншсн АЛЬФА-граню«торс (Ершов н др. (|9О5)). О прнисненнн грн)юв упрззлсння программ для целей шпнмнззцнн сн, также Касьянов.
Трах с«брат, 1975), [Патгаснн, |973, 1975Ь (Касьянов, 1975).— !знн, мрт. СПИСОК ПИТЕРАТУРЫ К ! и 2 ТОМАМ' ) Лйранс (196!) (1гопз Е. Т.), А зун1зх д|гзс|ед согпр|1ег 1ог Л3.603. 60, Созпю АСМ, 4г1, 51 — 55. Лйронс'(1963з) (!гапз Е. Т.), Ап еггос согсесцпй реже а|баг|Вгп, Сота. АСМ, й:11, 669 — 673. Айроас [!9636) (|гоне Е. Т.) ТЬе з|гцс1«ге апд нт о| |Ье зуп1ах д)мс(ед сшпр|!сг, Днн, йт. Ля|он. Ргодгггт, 5, Лйрапс (!964) (|гааз Е. Т.), З|гнс|нга3 саппесбопэ |п |огню| |анйнвйез, Сотт. АСМ, 7:2, 62 — 67.
Аллар«, ВальФ, Землян 31964) (Аиагд К. Цг., ига!1 К. А., Зешип К. А.), Зоще сбесЬ о1 Ве 6600 сщпри|ег оп 1аойпайе э|гас!иге«, Сава. АСМ, 7:2, Н2 — |27. Аллен | |9693 (Лиеп Р. Е), Ргойгат ор1!пг|заыоп, Алл. Зео. А то и. Ргойпин., 5. Аллен )1970) (А1!еп Р, Е.), Сап|го! Ваге апа1уьЬ, АСМ ЗГСРЬАЮ Ма|!сне, 5: 7, ! — 19.
Аллен, Кок (!072) (Ацеп Р, Е., Сосйе 3.), А са1э)абие а1 ариши д 1гвпз|аппа1|опз, сб. Оез|йп впд Ор1ип|ззцопо1 Сощр||егь, под ред. Кизил К., Ргеп. !!се.Нз)Ь Епй)зиной СЦ|Ь, Н. 3., РР. 1 — ЗО. Ангер (39683 1!)нксг 5. Н.), А 9!оЬа3 раыес Ьг сап|ехщгее РЬгазе ь1гис|аге йгзшшэш, Сотт. АСМ, !|г4, 240 — 246; Н б, 427. Андсосоп (Б64) (Лпдсгюп ). Р.). Л по|с ап занес сощр|бпй а|йогНЬщз, Сола. АСМ, 7.3, 140 — 150.
АНС (|966) (Лю Х3.9), Апгебсап Кацапа! 31апдагдь РОКТКАН, Ашег1сзп Напала! 51апдагдз !пещи|с, Неи Уагй. АНС Пал«синтез (|97И |Апм ЗиЬсацзпгыгс 2373), С|зббсзиоа с| РОКТЯАМ 51апджщ — Зесапд Кераг1, Сати. АСМ, 14г10, 628 — 642. Арбнб (1970) (АгМЬ М. Л.), ТЬсаг|еьа| аЬ«1гзс1 ао!ота|а, Ргеписе-Нзц, |пс„ Епд1югоод Ш|йз, Н. 1. Ахо [3968) (ЛЬо А. Ч.), !пдехед дгашщагз — ап сх1спыоп о1 соп1ск|-1гес Фзщщзгз, Л АСА1, 1б:4, 647 — 671 (Русский переаод: Ахо А., Инцскснис грэм. наги«а — расширение контекстно свободных грзммагнн, в сб. „Язикн н авпгмзгмц нзх-зо „Мнр", М., И75, сгр. 130-|65.) Ахо (В73! (АЬо А. Ч. (ед.)), Сиггсо1з |и 1Ье |Ьеогу а| сощрн1|пй, РгепЦсе-Нан, Еаб!ешоад ШНЬ, Н.
' Аю, Ульман [1968) (Аиа А. Ч., |ЛЬпап 1. О.), ТЬе 1Ьеогу о| 1зггйнзйез, Маы Зрг|. Тамгу, Ь2, 97 — 125. (Русен«0 перевод: А«ау А., Улмен Лж., Твгрнн язмкон, Кнбернетнческня сборник, новая серая, емп. 6, нзд-но,„мнрч М., 1069, сгр. 145 — 133 ) Лхс, Ульман (1969а) (Айа А. Ч., (ЛЬпап 3. О.). 5уп1зх д|гес1ед Ьапь)ацапз зпд Ве рпзидоип зьзещЫег, нд Сони и|. Зу«Г. Зс!., 3:1, 37 — 66.
') Кружочком ' отмечена литература, дабзвленная нрн перевода гомэ 2.— Пр ..Ре . список литлрлтчпы список литппз гулы Лхо, Улыба» [|9696) (А!ю Л. Ч., ОИвап 3. О |, РгорегИез о| аул|а» й|шс1сй ИапшаИапк, 3. Сотри!. Зузт. Зсс, 8:3, 3|9 — 334. Лхо, Улыба»(197|а) (А1ю Л. Н., ИИигагг 3. О.), Тйе саге апй Гсей!пй а! 1.К(й) йгаттагз, Ргас. о1 Зги Аапиз! ЛСМ Зувраы»т ап ТЬеогу о1 Сотри||ив |59 †1 Ако, Ульман [|07|6) (Лйп Л, Ч, !|Иван 3. О.), Тгапь!а|гону аи а сол|ех|йгее бгзвваг, |л(огт, а й Со»1в|, 19;5, 439 — 47а.
Лха, Ульиан (1973а) (Аиа Л. Ч., ПЬпап 3. О.), Ыпеаг ргесейеис Мыс|галь 1ог чез» ргесешпсе бгавтьгз, |л|евг, Л Сошли!. Магд., в печапг Ахо, Ульыаи | №7261 (Лио А. Ч., $Л1пгап 3. О,), Еггаг йс|сссап гп ргссейепсв рагюгь, Мо№. Зуз|. Тйт у, е печати Лхо, Ульман (№72ь) (ЛЬа А. Ч., $ЛЬпап 3. О.), Орбв| а1№п о1 ЬКМ) раг.егз, 3.
Сотрт. 5»з! Зсг'., в печати Аха, Ульман (1972г) (Лио Л. )г., 1Л!тап 3. О ), Л |сейл|»ие Гаг ьртйгпй ир ЬК(й) рвгзегь, Ргос Роиг1Ь Линча| АСМ Зувропшп оп Тйеогу ! СотриИп2. Рр, 25| — 263. Лхо, Ульман )1072д) (Айо Л. Ч., ИИвал 3. О.), Орит|заи п о1 ь| №Ь| Ьпе сойг, 5|АМ 3. ол Сотригглй, И|. ! — 19 Ахо, Ульман (1972е! (АЬо А.
Н., (|Иваы 3, О.), Е»тча|епсе о| ргабгагпь м|1Ь а|гас|вой чапзЫсь, 3. Солар»| Зуь!. Зс., 8:2, !25-|37 Лх, Ульман (1972ж! 1АЬо А. Н., П|тап 3. О.), ГК(й) ьуп1ах илес|ей !ганы |зИои, неопубликованная рукопись, БсИ Сзиггга(ог!аь, Мыпау Н|И, Н. 3. Ахо и др. (№68) (Айо А. Н., Йарсга!! Л Е., ИИпгаи 3. О.), Тггпе зпй |аре сагир|с»Иу а| ризЬашчп аи$ата|оп |апйиабеь, 1 Гшт. тш Сап|го|, $3 Ъ, !86 — 206. (Рушкнй перевод: Ако А., Хапкрофт Дж., Ульман Дж., Временная к лепточна» сложности камков, доыускаамык чшаьииныии евтаматаыи, в сб.
„Языки и автоматы", изд.во „Мир", М., №75, стр. !8! — 197.) Ахо н лр. (1972»! (АЬо Л, Ч., Белл|и» Р. 3., $|иваи 3. О), УРеа!г апй гпгхей Ига|ебу ргесейепсе рагз|пй, 3. АСМ, 19:2, 225 — 243. Ахо н лр. (|9|26) (Ада А. '3., Норсгой 3. Е., П|вап 3. О), Оп 1(пйги» 1омез| согпвап апс»Иогь гп 1геез, неапубликоваина» рукопись, ВеИ Се»ага!ау!еь, Миггау Н|И, Н. 3.
Ахо и лр. (1972в! (Айо А Н., Зе№| К., П|пгав Л О.), Сайс ар||в|хаИоп апй ИпИе Сиигси-Ко»юг ьуь|епп, в сб. Оеыйп апй Ор(гв)хаИоп о$ СаврИегь. пол рол. Киьсп К, РгспИсе-На|1, Еп№еиоай СИ||к Н. 3., рр. 89 — 106. Аха н др. 11975! (Аио А, Ч., уойпьоп 5. С., П!вап Л О.), Ос|сгв|пшбс р гИиб о$ егпЫ»иат йгапкпагз, Готт. АСМ, !8:8, 4И вЂ” 453. Багвелл 11970! (ВебаеИ 3. Т.), Госа1 аРИгпгхаИапь, АСМ ЗГСРЕАУ ЛИ|та, 5:7, 52 — 66. Барнет, Футрель (|952) (ВагпеИ М. Р., РиЬеИе К. Р.), Зуп|асИс аив|ушь Ьу ММЬ| сотрп|ег, Сотт. АСМ, 6: $0, 515 — 526.
Бар-Хнллел (|064! (Ваг-Н|Ие| Н.), 1.апйаабе апй пйаппаиоп, Лйй!зогг-)ус»|ау, Кеа№п», Маьь. Бар.Х»ллт н лр [ЫГИ! (Ва -ИПе| Н., Рег|еь М., Зйати Е ), О 1 пш| ргаре Ие а! |тр| РИ з апн $ г» тгпагь. 2 Рйошг№, Злгасйюсмею юйо)| алй Ко л и№аио з|огюги 8, 14, 143 — 172, См. также.Бар-Хиллел (1964), рр. 1$6 — 150. Бауэр и др. [1968) (Ваисг Н., Весиег 5п Огай»в 5.), АГООГ.
$9 |тр|свеп1а$|ап, 6598, Гопгри1ег Зс|епсе Оер|. 5|ап№гй Ип|чег»Иу, 51зп|агй, Са!И. 'Вежинова М. М., Пот»жни Н. В. (1965). Программирование циклов и индексных выражен»й в Альфа-транслиторе, в сб. „Альфа-система звтоматнзакни программирования" иод ред. А, П. Ершова; В(( СО ЛН СССР, Новосибирск (2-е издание, „Наука", М., 1967). Белл (|969) (ВеИ 3. К.), Л пел гпе|Ьой 1ог йе1егв|п|пй Инсат ргесейепсе |ипс1юпь |ог ргесейепсе йгапипагз, Сотт. АСМ, 12|10, 316 — 333. Белл $1970! (ВеИ 3. К.), ТЬе »иайгаИс Оио|геи1 п|е1йой: а Ьа*Ь ст|е еИпипа. Ипб тсапйагу с)иь(ег)ий, Сотт.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
