Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 49
Текст из файла (страница 49)
Если перевод осуществляется МП-преобразователем или апа. логичным устройством с одним выходным потоком, то проблем с разбиением перевода на фазы не возникает. Символы считаются выходными по мере того, как они вырабатываются устройством. Если предположить, что различные виды выходных потоков отделяются лруг ат друга метаснмволами,то выходной поток можно разделять по мере его образованна.
Например, проллежуточный код передается на фазу оптимизации, диагностика размещается в собственный список, чтобы затем быть напечатанной, а команды по организации информации выполняются немедленно. Предположим, что для обобщенного синтаксически управляе. мого перевода применяется один из наиболее общих вариантов алгоритмов 9.1 — 9.4. Можно было бы дождаться, когда будет полностью сконструировано дерево или ориентированный ацинлический граф, а затем сформировать единый выходной поток. Деление потока на объектный кол и команды могло бы осуществляться точна так же, как и для МП-преобразозателя. Это оз.
начает, что команды по организации информации це выполнялись бы до тех пор, попа не был бы полностью сформирован выходной поток, и что команды выполняются по мере обработки выходного нотона. Такая организация требует дополнвтельного прохода и большой памяти с произвольным доступом, поможет оказаться наиболее приемлемой, если требуется мощность самых общих схем синтаксически управляемого перевода, С другой стороны, можно припя~ь, что команды по организапии информации и другие команды компилятора связаны с от- 7ЬО дельными вершинами дерева разбора и выполняются сразу, как только вершина образована.
Однако, если алгоритм разбора требует возвратов, надо быть осторожным, чтобы не выполнить команды, связаннои с вершиной, не являющейся частью дерева раабора. В этой ситуации необходим механизм для отмены результата такой команды. КЦРАЖМЕИИЯ 9,3.1. Найдите ОСУ-схемы для следующих переводов: (а) ((а", а" )(и ~1), (б) ((а", а'") (л~)1), (в) ((гв, нш)(ш Е (О + 1)').
9.3.2. Покажите, что существуют переводы, определяемые ОСУ-схемой, но не определяемые никакой СУ-схеиой. *А9.3.3. Пусть Т вЂ семантичес однозначная ОСУ-схема с бесконечной областью определения, входная КС-грамматика которой является приведенной. Понажите, что в этом случае должно удовлетворягься одно из следующих услоиий: (1) Существуют константы с, и с„ большие 1 и такие, что если (к, у) Ет(Т), то (у((с',"' и для бесконечного числа цепочек х найдутся такие пары (х, у) Ет(Т), что (у(,мс("!.
(2) Существуют константы с, н см балшние О, н целое число л ) 1, такие, что если (х, у) Ет(Т) и хФЕ, то (у)(с,(А!' и для бесконечного числа цепочек х найдутся такие пары (х, у) Ет(Т), что )у()с,)х(к (3) Множество значений схемы Т конечно 9.3АК Покажите, что перевод ((а", а ) ( ш — целая часть числа ) л) нельзя определять никакой ОСУ-схемой. 9.3.5. Для переводов из упр. 9.8.1 (а) — (в] постройте ориентированные ацпклические графы, вырабатываеллые алгоритмом 9.4 для входов а', а' и 011 соответственно. 9,3.9. Укажите последователылость вершин, по которой про.
ходит алюритм 9.3, примененный к ориентированным апиклическим графам иа упр. 9.3.3 "9.3.7. Дополшше пример 9.16, вктючнв правило вывода 5 мЬПе В бо 5, смысл которого должен заключаться в том, лжо проверяется выражение В, а затем выполняется оператор Я до тех пор, пока значением В не станет ложь. зы гпражнепяя гл. з. пеРевод и генерация кодл В (Е)М Е а, Е)В, 1.)а)В М т,)ю,(..,(жз АГ,=Цо-РЕ(ч92 ' )Ус=2., Е,=-2Е,+В, 1.,-1.,+1 Е,— В, Е,=! В,=О В,=! (у !4п,! и! 34 Е Е ЕВ (= в= т 4-4 лх=-2 В 0 В 1 заз 9.3.3. Следующая грамматика порождает объявления, подобные объявлениям в ПЛД: Терминал а ияображает идентификатор; т„..., ть — это й возможных атрибутов идентификатора в пайке. Терминальными символами являются также запятая и скобки.
Е представляет списон идентификаторов н объявлений; () †э объявление, состоящее из заключенного в скобки списка идентификаторов и объявлений. Атрибут, выведенный из М, должен прил!сняться ко всем идентификаторам, выведенным из Е в правиле вывода () (Е)М, даже если идентификатор находится внутри сложного объЯвлеииа.
НапРимеР, объЯвление (ам (а„а!) ж!) т„назначает идентификаторам а, и а, атрибут лг„ а идезнтйфийаторам ам а и а, атрибут п4,. Используя л4обые типы перевода, постройте схему перевода, переводящую цепочки, выведенные из нетерминала В, в й списков, причем список ! должен содержать в точности те идентификаторы, которым придан атрибут и! 9.3.9. Измените пример 9,17 так, чтобы в команду А)(С4 за. носились не указатели на значения выражений, а сами эти зна. чения.
9.3.10. Рассмотрим схему перевода Во входной грамматике из нетерминала Аг выводятся двоичные числа (возможно, с двоичной точкой). Нетерминал Е представляет список битов, а нетермннал  †б. Элементами перевода являются арифметяческие форьгулы. Элеьгент перевода У! представляет рациональное число †значен двоичного числа, вы. всденного из ЛС Элементы перевода Е, Е„ и В, принимают целые зна4ения. Например, 1!.01 имеет перевод 3'14. Покажите, что т(7) =-((6, б)(Р†двоичн целое, 4( †е значение), 262 "9.3.11.
Рассмотрич следующую схему перевода с входной грамматикой, как в упр. 9.3.10, но содержащую как синтезированные, так и наследственные атрибуты: р) (,п4„!н! р) 9 Е! !4ч Цп =О Ео! 1 в! А! Е 34! =Е! 1.,=-0 В, =).о' Ц" =ЕР4+1 Е В Е, =-В, В, =-Е., 1., =! В О В,=О В 1 В, = 2з Дерево разбора для 11.01 со значениями элементов перевода, соответствующих каждой вершине, изображено на рис, 9.20. Рис, В.во. Дерево разбора с зчреаоламя.
гл з. пи»звон и гене»лция кодл Отметим, что для того, чтобы вычислить элемент перепада йм надо сначала вычислить снизу вверх все Е, справа от разделительной точки, затем сверху вниз все Ьо и, наконец, снизу вверх все Ео Покажите, что эта схема определяет тот же перевод, что и схема из упр, 9.3.10. »9.3.12. Покажите, что всякий перевод, который можно выполнить с помощью наследственного и синтезированного пере. нодон, можно выполнить с помощью только синтезированного перевода. Укаэализг На структуру перевода ограничений нет. Таким образом, перевод, определяемый в некоторой вершине, может быть целым поддеревом. 9.3,13.
Можно ли любой перевод, использующий синтезиро. за~огне переводы, выполнить только с помощью наследственного перевода? **9.3.14. Приведитс алгоритм для проверки, является ли данная схема перевода, содержащая наследственные и синтезированные атрибуты, зацнкленной. 9.8.15. Видоизмеинте пример 9.18 так, чтобы ввести возмож. ности улучшения нада из примера 9.14. "9.3.16. Алгоритм дифференцирования примера 9,!1 позволяет генерировать такие выражения, как 1»сов(х) или 0»л+(1)»1 (формальная производная от !» х).
Можно выявить и исключить выражения, язло разные 0 или 1, где язио определяется следующим образом: (1) 0 явно равен 0; 1 ноно равна 1. (2) Если Е, явно равно О, а Е,— некоторое выражение, то Е, » Е, и Е„» Е, явно равны О. (3) Если Е, и Е, явно равны 1, то Е,» Е, явно равно 1. (4) Если Е, явно равно О, а Е, явйо равно 1, то Е,+Е, и Е,+Е, инно равны 1. (5) Если Е, и Е, явно равны О, то Е,+Е, явно равно О.
Измените ОСУ.схему (в том числе, возможно, и входную грамматику) тан, чтобы в переводе не появлялись выражения, язяо равные О, а в качестве множителей чтобы не пояалялнсь выражения, явно равные 1. 9.3.17. Рессиотрим следующую грамматику для оператора присваивания, включающего переменные с индексом: зпелжнения А- ):=Е Е Е <ансл) Т(Т Т Т<знумн) Р(Е Р (Е)(! 1 а)а(Е) Е-а, б(а <висл) + (— <знумн) »() Примером оператора, генерируемого этой грамматикой, может служить а(а, а): а(а-)-а, а»(а+а))-1-а Вдесь а — ленсема, представляющая идентификатор.
Сконструируйте схему перевода, основанную на этой грамматике н генерирующую необходимые команды языка ассемблера или много. адресного кода для операторов присваивания. 9.3.18. Покажите, что ОСУ.схема из примера 9.11 правильно вырабатывает выражение для производной входного выражения. **9.3.19. Покажите, что перевод ((а,...а Ь!...Ь„,а1Ьо.,а Ь„)(а г1, а,б(0, Ц,Ь ц(2,3)для!~(~а) ие определяется никакой ОСУ-схемой, Проблема длл исследозоиия 9.3.20. Перевод арифметических выражений становится до.
нольно сложным, если допустить в качестве операндов элементы многих различных типов данных, Например, значениями могут быть логические переменные, цепочки, целые, вещественные или комплексные числа †последних грех случаях они могут иметь одинарную, двойную или, возможно, более высокую точность. Кроме того, некоторые значения могут лежать в динамически распределяемой памяти, а некоторые размещаться статически. Число комбинаций вполне может быть настолько большим, что элементы перепада, связанные с таким правилом вывода, как Е Е + Т, станут весьма громоздкими. Можете ли Вы по данному переводу, перечисляющему желаемые коды для каждого случая, придумать способ автоматического упрощения записир Скажем, в примере 9.19 части перевода Еш для 1йеп и е1зе отличаются тол~ко одним символом А или В в конце команды АОО.
Таким образом, если использовать более изощренные механизмы, описание можно сократить почти вдвое. Л ОРГАНИЗАЦИЯ Ю %Ф ИНФОРМАЦИИ Замечания по литературе 10.1. ТАБЛИЦЫ ИМЕН Денные Имя целое ВООР метке вешестисниый массив Рнс. 10.1. Теблице ич ш Гл. е. пеРеВОд н генеРАция кадА Упрозснение но проероммиролпние *9.8.21. Сконструируйте схему перевода, отображаеощуео подмножество Фортрана в промежуточный язык, как в упр. 9.!.10. Напишите программу, реализующую эту схему перевода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
