Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 62
Текст из файла (страница 62)
Интерпретатор должен добавлять к этому так называемому смеи(гнию базовый адрес соответствующего сегмента данных. Если переменная локальна и процедуре, интерпретируемой в данный момент, то этот базовый адрес задается регистром В. В противном случае его можно получить, спускаясь по цепочке сегментов данных. Однако транслятору может быть известна только статическая глубина пути доступа к переменной, тогда как динамическая цепочка (цепочка динамических связок) отражает динамическую истори>о обращений к процедурам. К сожалеишо, эти два пути доступа нс обязательно одинаковы. Например, пусть процедура Л обращается к процедуре В, описанной как локальная в Л, процсдура В вызывает С, опК. зло.
гтрачессар тта710 санную как локальная в В, а С вызывает В рекурсивно. Мы говорим, что А описана на уровне 1,  — на уровне 2, С вЂ” на уровне 3 (см. рпс. 5.7). Если в В имеется обращение к переменной о, описанной как локальная в А, то транслятору известно, что между А и В супцествует разница уровней, равная 1. Однако один шзг по динамической цепочке приводит ь переменной, локальной в С! оь нА яь Рис.
5.7. Стек иашииы дхя Гхгцо. Поэтому ясно, что нужно иметь вторую цепочку связей, которая связывает сегменты данных таким способом, чтобы транслятор мог правильно воспринимать ситуацию. Мы назовем элементы этой цепочки статической связкой 81., Итак, адреса формируются в виде пар чисел, указывающих статическую разность уровней и относительное смещение внутри сегмента данных. Мы счятаем, что каждая ячейка памяти может содержать адрес илн целое число. Множество команд машины ПЛ/О приспособлено к требованиям языка ПЛ/О. Оно содсрлсит такие команды: 1. Засылки чисел (констант) в стек (Е1Т), 2. Считывания переменных в вершину стека (ЕОР).
3. Записи значения, находящегося в вершине стека (ЬТО), (Соответствует оператору присваивания.) 4. Команда актпвашш подпрограммы, соответствующая об- ращению к процедуре (СЛь), 376 Ю. Структура языков и трансляторы 5. Выделение памяти для стека путем увеличения указателя стека Т (15)Т). 6. Команды условной и безусловной передачи управления, ис. пользуемые в условных операторах и циклах ()Л1Р, )РС), 7. Команда, выполняющая арифметические действия и сравнения (ОРК). Так как в команду должны входить трп компоненты, то она имеет следующий формат (см, рис.
5.8). Здесь присут- Ряс. 6.8. Формат команды. ствуют код операции ()) и параметр, состоящий из одной или двух частей (а и Ь либо только п)*). В случае команды ОРЙ, выполняющей некоторое действие, параметр а задает это действие; в других случаях это либо число (1.1Т, 15)Т), либо адрес в программе ()Л1Р, )РС, СА1.), либо адрес данных (1.ОТ), ЯТО).
Подробно работа машины ПЛ/О определяется процедурой, называемой (пгегртег, которая является частью программы 5.6, объединяющей законченный транслятор с интерпретаторам в систему, которая транслирует, а затем выполняет программы на ПЛ/О. Л(ы предлагаем в качестве упражнения модифицировать эту программу, чтобы она формировала рабочую программу для какого-либо существующего процессора.
Необходимое для этого увеличение йрограммы можно считать мерой того, насколько выбранная вычислительная машина подходит для поставленной задачи. Безусловно, представленную вычислительную машину ПЛ/О можно было бы организовать более искусно, с тем чтобы некоторые операпии выполнялись эффективнее. Например, можно было бы улучшить механизм адресации. Принятая схема была выбрана нз-за ее простоты, а также потому, что все усовершенствования должны фактически основываться на ней и из нее выводиться. ЗЛИ ФОРМИРОВАНИЕ КОМАНД Чтобы транслятор мог сформировать команду, ему должны быть известны ее код операции и параметр, который представляет собой либо число (саму константу), либо адрес. Эти значения транслятор связывает с соответствующими иденти- ") Поле у в команде (или параметре) всволвзустся для указююя уровня (зеве)).— Прим. ред, 5.11.
Формирование команд 377 фнкаторамн при обработке описаний констант, переменных н процедур. Для этой цели таблица идентификаторов дополнена атрибутами, присущими каждому идентификатору. Если идентификатор обозначает константу, то его атрибутом является значение этой константы, если идентификатор обозна~ает переменную, то его атрибутом является ее адрес, состояший из смещения и уровня, а если он обозначает процедуру, то его атрибутами являются адрес входа в эту процедуру и ее уровень. Расширенное соответствующим образом описание переменной 1иЫе («таблица») показано в программе 5.6.
Это наглядный пример поэтапного уточнення (или дополнения) описания данных, происходящего одновременно с уточнением операторной части программы. В то время как значения констант задаются в тексте программы, определять адреса транслятор должен самостоятельно. Язык ПЛ/О достаточно прост, поэтому переменные и команды размещаются в памяти последовательно. Следовательно, кагкдое описание переменной сопровождается увеличением индекса размещенпя данных на 1 (так как каждая переменная по определению машины ПЛ/О занимает ровно одну ячейку памяти). 1Лндекс размещения данных г(х должен инициироваться в начале трансляции любой процедуры, поскольку ее сегмент данных первоначально пуст, [В действительности г)х получает начальное значение 3, так как каждый сегмент данных содержит по крайней мере три внутренние переменные 1(А, 111., 5( (см.
предыдущий раздел).[ Соответствующие вычисления, позволяющие определить атрибуты идентификатора, включены в процедуру еи1ег, которая добавляет в таблицу новые идентификаторы, При наличии этой информации об операндах команды формируются довольно просто. Благодаря стековой организации машины ПЛ/О существует практически однозначное соответствие между операндами н операциямн исходного языка, с одноп стороны, и командами раоочсй программы, с другой стороньь['гранслятор лишь должен вйючпить необходимое преобразование в погггдикеную форму~Достфнксная форма означает, что знаки операции всегда следуют за своими операндами, а нс гставляются между ними, как в обычной инфиксной Форме. Постфнксную форму иногда также называют польской записью (так как ее «изобрел» поляк Лукасевнч) нлн бесскобонной записью, так как она делает скобки излишними.
Примеры соответствия между иификсной и постфиксной формами записи выражений приведены в табл. 5.4 (см. также разд, 4.4.2). (Очень простой способ выполнения такого преобразования: описан в процедурах ехргезз(ои и 1егт из программы 5.6. Он состоит в том, что передача знака арифметической операции 878 5. Структура нвиков и трансляторы Таблица 5.4. Выражения в инфиксноя и постфиксной элвисах просто задерживаетси.,",В этот момент читатель должен убедиться, что взацмная связь процедур грамматического разбора учитывает соответствующую интерпретацию принятыс правял приоритета различных операций, ' Трансляция условных операторов и циклов несколько менее тривиальна. В этом случае нужно формировать команды перехода, для которых сам адрес перехода иногда еще неизвестен.
Если обязательно, чтобы формируемые команды располагались строго последовательно в виде выходного файла, то необходима двупроходная схема транслятора. На втором проходе неполные команды перехода дополняются адресами. Друтое решение, реализованное в данном трансляторе, — это помещение команды в массив, т. е. в память с непосредственным доступом, что позволяе~ вставлять недостающие адреса, как только онн становятся известны. Такую операцию иногда называют фиксацией фхир). Единственное дополнптельное действие, которое нужно выполнять при формировании такого перехода вперед, — это запоминание его местоположения, т.
е. индекса в памяти для программы. Затем во время фиксации этот адрес используется для нахождения неполной команды. Детали опять можно видеть в программе 5.6 (см. процедуры, обрабатывающие операторы условия и цикла). Команды, соответствующие этим операторам, формируются па следующему шаблону (1.1 и 1.2 означают адреса команд): ИСИэеп5 1.1: команды для С 3РС Е2 команды для Я 2МР 1.1 1.2:... Для удобства вводи~ся вспомогательная процедура, называемая йеп.
Ей задаются три параметра, из которых она формирует команду. При этом автоматически увеличивается индекс сх, указывающий место, куда помещается очередная команда. 5.77. Формированив команд 879 Ниже в мнемонической форме приведена программа, полученная при трансляции процедуры умножения (5.14). Комментарии с правой стороны добавлены лишь для пояснения, 1нт 0,5 видеяияь линять дмг е8лввквлвкальньм ле~еменльгл 3 1.00 1,3 х 4 8ТО 03 а 5 йоо 14 у б ЗТО 04 Ь 7 ЫТ 00 0 8 ЗТО 1,5 9 ЬОО 04 Ь 1О ИТ 00 О !1 Орн 0,12 12 ЗРС О 29 13 100 04 Ь 14 ОРН 0,7 не«влгкд 15 ЗРС 0 20 16 1.00 1,5 17 1.00 0,3 , 18 ОРИ 0,2 ' 19 ЗТО 1,5 20 ЫТ 0,2 21 1.00 0,3 22 ОРЯ 04 23 8ТО 0,3 24 1.00 0,4 25 й17 0,2 26 ОРЯ 0,5 27 8ТО 0,4 28 ЗМР 09 29 ори о,о ддздрьгл7 Рабочаа программа, соотаотстпуюгцаа процедуре ПЛ!О (5.14).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
