Устройство для обработки выражений языков программирования

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (i i1 5 l 97I5

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 12.02.74 (21) 1995907/24 с пписоединением заявки № (23) Приоритет

Опубликовано 30.06.76. Бюллетень № 24

Дата опубликования описания 26.07.76 (51) М. Кл е G 06F 15/04

Государственный комитет

Совета Министров СССР по аелам изобретений и открытий (53) УДК 681.326.3 (088.8) (72) Авторы изобретения Г. М. Адельсон-Вельский, В. Л. Арлазаров, Р. 3. Асратян, А. Ф. Волков, В. Н. Деза, E. А. Диниц, H. В. Дагурова, Н. Е. Емельянов, Н. Г. Зенкина, В. T. Лысиков и И. А. Фараджев

Вд -

Ордена Ленина институт проблем управлен (71) Заявитель

Д @ у рИВ (54) УСТРОЙСТВО ДЛЯ ОБРАБОТКИ ВЫРАЖЕНИЙ ЯЗЫКОВ

ПРОГРАММИРОВАНИЯ

Изобретение относится к области вычислительной техники и может быть использовано в качестве специализированного устройства обработки информации при построении многопроцессорных вычислительных систем.

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

Недостатком известных устройств являются большие затраты времени и сложность трансляции с языков высокого уровня на внутренний язык устройства, а также неудобство

«ручного» программирования на этом языке.

Целью изобретения является упрощение трансляции с языков высокого уровня и сокращение времени трансляции.

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

Практически устройство является аппараратурной реализацией нового языка, близкого

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

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

К преимуществам предлагаемого устройст20 ва можно отнести и то, что подобие между программой на языке высокого уровня и соответствующей программой на внутреннем языке процессора существенно облегчает задачу контролирования выполнения программ при

25 откл адке.

Схема устройства представлена на чертсже.

Она содержит блок чтения программы 1, блок формирования адресов и операндов 2, блок управления 3, блок анализа управляю30 щих символов 4, счетчик управляющих симво519715

3 лов 5, индикатор нуля 6, блок стековой памяти управляющих символов 7, счетчик операндов

8, индикатор нуля 9, блок стековой памяти операндов 10, первый регистр операнда 11, второй регистр операнда 12, триггеры занятости 13, 14, арифметический блок 15, счетчик индексных позиций 16, регистр номера массива 17, информационные вход 18 и выход 19 устройства, управляющие выход 20 и вход 21 устройства.

Устройство работает следующим образом.

Адресация главной памяти (на чертеже не показана) производится по математическим адресам. Математический адрес состоит из номера массива и номера элемента в массиве.

В каждый момент для непосредственной адресации доступны лишь 32 массива, которым присваиваются номера от 0 до 31. Для каждого массива существует паспорт, в котором содержится информация о месте расположения массива, его длине, номере «текущего» элемента и т. д. Функции хранения паспортов и преобразования математического адреса в физический возложены на память.

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

Главная память (на чертеже не показана) содержит высокоскоростную часть из 32 регистров, в которых хранится наиболее часто используемая информация. Адресация высокоскоростной части проводится по номерам регистров.

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

Форматы видов элементарных записей и их функциональное назначение рассмотрены ниже.

Вид 0 — первые три разряда содержат код

000, следующие 5 разрядов — код номера регистра. Адресуется один из 32 регистров высокоскоростной части главной памяти.

Вид I — три разряда — код 001, пять разрядов — код номер массива, двадцать четыре разряда — код номера элемента. Задает адрес элемента массива., Вид II — три разряда — код 010, тринадцать разрядов — операнд.

Задает непосредственный операнд.

Зо

Вид 111 — три разряда — 011, тринадцать разрядов — номер элемента.

Обращение к массиву № О. Сообщается номер элемента массива.

Вид IV — три разряда — 100, пять разрядов — номер массива.

Адресуется текущий элемент массива.

Вид V — три разряда — 101, пять разрядов — номер массива.

Этот вид эквивалентен паре знаков АЛГОЛа:

М (, т. е. указывает номер массива и одновременно служит левой границей индексного выражения.

Вид Vl — три разряда — 110, пять разрядов — номер регистра.

Этот вид осуществляет индексацию при обращении к массиву № О, т. е. эквивалентен следующей последовательности знаков

АЛГОЛа: М (R (М вЂ” идентификатор нулевого массива, R — регистра) .

За этим элементом следует продолжение индексного выражения.

Вид VII — три разряда — Ш, пять разрядов — управляющий символ.

Этот вид обозначает управляющие символы.

Основными конструкциями языка являются арифметическое и логическое выражения. Их синтаксис подобен синтаксису аналогичных конструкций в языке АЛГОЛ, одиночные переменные изображаются с помощью видов О, 1, 111 и IV, переменные с индексами с помощьк видов VI и V, а знаки операций с помощью вида VII. Вместо символа «)» используется символ «)». Кроме того, отсутствует аппарат обращения к процедурам — функциям (его лишь до некоторой степени может заменить операция call — переход с возвратом).

Общая структура программы на языке формул описывается следующим образом: программа::= (оператор) оператор::=арифметическое выражение (логическое выражение) присваивание (цикл) операгор, оператор.

Оператор «цикл» имеет следующий вид:

do оператор while логическое выражение.

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

Оператор «присваивание» имеет такой же вид, как аналогичный оператор в АЛГОЛе, Условный переход:

if логическое выражение, программный адрес. Если логическое выражение равно false, то происходит переход по программному адресу (программный адрес не является видом и никак не помечается, состоит из номера массива и номера байта).

Безусловный переход: go lo программный адрес.

Переход с возвратом; call программный адрес.

Эта операция запоминает адрес возврата и осуществляет переход по программному адресу. Возврат вызывается операцией fef, 51971

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

Если элементарная запись является непосредственным операндом (вид II) или адресом (виды О, I, Ш1, то она посылается в блок формирования адресов и операндов 2, где операнды и адреса приводятся к соответствующему формату (см. ниже) .

Сформированный операнд или адрес пересылаются во второй регистр операнда 12.

В случае элементарной записи вида IV (обращение к текущему элементу массива) номер адресуемого массива посылается в регистр номера массива 17. Далее производится обращение к паспорту массива за адресом текущего элемента массива. Прочитанный адрес вместе с номером массива посылаются во второй регистр операнда 12.

В случае элементарной записи вида V номер адресуемого массива посылается в регистр номера массива 17, причем содержимое этого регистра и счетчика индексных позиций 16 засылается в блок стековой памяти управляющих символов 7. После этого в блок стековой памяти управляющих символов из блока управления заносится управляющий символ и счетчик индексных позиций 16 обнуляется.

В случае элементарной записи вида VI производится то же, что и в предыдущем случае, но в регистр номера массива 17 заносится нулевое значение. После этого во второй регистр операнда 12 с выхода блока 2 заносится номер регистра, указанный в элементарной записи.

Занесение во второй регистр операнда производится по следующим правилам. Если триггер занятости 13 второго регистра операнда установлен в «О» (второй регистр операнда 12 свободен), то производится запись во второй регистр операнда 12. После этого анализируется состояние триггера занятости 14 первого регистра операнда. Если триггер находится в состоянии «1» (первый регистр операнда 11 занят), то триггер занятости 13 второго регистра операнда устанавливается в «1». Если триггер занятости 14 первого регистра операнда находится в «О», то производится перезапись из второго регистра операнда 12 в первый пегистр операнда 11 и триггер занятости

14 первого регистра операнда устанавливается в «1».

Если триггер занятости второго регистра операнда установлен в «1», то производится предварительная перезапись содержимого первого регистра операнда П в блок стековой памяти операндов 10 и перезапись содержимого второго регистра операнда 12 в первый регистр операнда 11.,5

5

Информация в первом и втором регистрах операндов 11 и 12 может быть четырех типов (номер типа записывается в двух левых разрядах регистра): операнд с фиксировачной запятой, занимает половину регистра (одно машинное слово); операнд с плавающей запятой, занимает весь регистр (два слова); адрес (номер) регистра, номер регистра записан в правых пяти разрядах левой половины регистра; адрес элемента массива, который состоит из номера элемента и номера массива, номер массива записан в правых пяти разрядах левой половины регистра, в остальных разрядах записан номер элемента.

Логические значения представляются с помощью типа 1 true — все единицы, false — все нули.

Длина ячейки блока стековой памяти операндов — одно машинное слово (четыре байта).

При записи содержимого первого регистра операндов 11 в блок стековой памяти операндов 10 в случае первого, третьего и четвертого типов записывается содержимое только левой половины этого регистра, а в случае второго типа — сначала содержимое правой, а затем левой половины. Перед записью каждого слова к счетчику операндов 8 прибавляется единица. Запись производится в ячейку, адрес которой содержится в этом счетчике.

Аналогично, перед записью в блок стековой памяти управляющих символов 7 прибавляется единица к счетчику управляющих символов 5.

Если элементарная запись является управляющим символом (вид VII), то работа процессора целиком определяется прочитанным управляющим символом и управляющим символом, находящимся к этому времени в вершине управляющего стека, т. е. в ячейке блока стековой памяти управляющих символом 7, адрес которой содержится в счетчике управляющих символов 5.

Оба вышеуказанных управляющих символа подаются на вход блока анализа управляющих символов 4. Этот блок представляет собой ассоциативную память, в которой записаны правила расшифровки языка. Оба управляющих символа поступают на шины опроса ассоциативной памяти. С выхода блока анализа управляющих символов 4 считывается управляющий код, который подается в блок управления 3 п вызывает переход к микропрограмме, соответствующей данной паре управляющих символов, Действия процессора в общем случае могут быть следующими: выполнить операцию, соответствующую управляющему символу в вершине управляющего стека, вычесть единицу из счетчика управляющих символов 5 и вернуться к фазе анализа; занести прочитанный управляющий символ в блок стековой памяти управляющих символов 7 и продолжить чтение программы, 519715

Выоор для каждой пары управляющих символов одного из двух указанных вариантов делается в соответствии с приоритетами управляющих символов.

Для пары «а», «в» («a» — управляющий 5 символ из вершины управляющего стека, «в» — прочитанный из программы); если приоритет «а» больше, чем приоритет «в» или равен ему, то выбирается вариант 1; если приоритет «в» больше, чем приоритет «а», то вы- 10 бирается вариант 2.

Например, в случае пары «" +» выбирается первый вариант, в случае пары « "» (выбирается второй вариант.

Отметим, что некоторые управляющие сим- 15 волы в позиции прочитанного из программы символа имеют один приоритет, а в позиции символа из вершины управляющего стека— другой (стековый).

В некотором случае действия могут отли- 2п чаться от вышеуказанных вариантов. Например, если прочитанный из программы символ является символом типа перехода (go to, call), то сразу же выполняется соответствующий переход, т. е. блок чтения программы 1 продол- 25 жает дальнейшее чтение программы, начиная с адреса, сообщаемого в операции перехода.

В случае операции call производится также занесение адреса возврата из блока чтения программы 1 в блок стоковой памяти управля- 30 ющих символов 7 (в пять последовательных ячеек). При выполнении операции ref (возврат) информация из пяти верхних ячеек управляющего стека заносится в блок чтения программы 1.

Для выполнения арифметических и логических операций производится обращение к арифметическому блоку 15. Арифметические и логические операции всегда производятся над величинами в первом и втором регистрах 4 операндов 11 и 12, которые используются как внутренние регистры арифметического блока

15. Для большинства арифметических и логических операций (для двуместных) необходимо, чтобы оба регистра были заняты. Поэтому, 45 если триггер занятости 13 второго регистра операнда находится в «О» (второй регистр опеоанда 12 пуст), а триггер занятости первого регистра операнда находится в «1», то производится предварительная перепись из первого регистра операнда 11 во второй регистр операнда 12, перепись из блока стековой памяти операндов 10 в первый регистр операнда 11 (из ячейки, адрес которой содержится в счетчике операндов 8) и триггер занятости второго регистра операнда устанавливается в «1», При этом если считываемая из блока стековой памяти операндов 10 информация относится к типам 1, 3 или 4, то производится чтение 50 одного слова, которое заносится в левую половину первого регистоа операнда, если же она отплатится 1 типу?. то производится чтение д:;у-:, c.,,I .. г.". рве::аносятся в левую и

B правую и л<:: nну . того регистра. После чте8 ния каждого слова из счетчика операндов 8 вычитается единица.

Если ооа триггера занятости 13 и 14 находятся в «О», то вышеуказанная операция повторяется два раза, пока не заполняется первьш и второй регистры операндов 11 и 12, после чего эти триггеры устанавливаются в «1».

Если при выполнении арифметической или логической операции в первом регистре операнда 11 или втором регистре операнда 12 находится адрес, то производится предварительная выборка операндов в эти регистры из главной памяти. Адрес подается на информационный выход 19 и считанный из главной памяти операнд поступает на информационный вход 18. Согласование работы главной памяти и предлагаемого устройства производится с помощью управляющего выхода 20 и управляющего входа 21 устройства.

Результат операции помещается в первый регистр операнда 11, Триггер занятости второго регистра операнда 13 устанавливается в

«О». Тип результата совпадает с типом операндов, если же один операнд имеет тип 1, а другой тип 2, то результат получается типа 2.

При операции присваивания в первом регистре операндов 11 должен находиться адрес, а во втором регистре операндов 12 — записываемое значение. После записи значения по вьш.еуказанному адресу обе величины уничтожаются (триггер занятости первого регистра операндов и триггер занятости второго регистра операндов устанавливаются в «О»).

Адреса в регистры 11 и 12 попадают или из программы (виды О, I, III и IV) или в результате некоторого вычисления в случае обращения к массиву с индексным выражением (виды V и VI).

В этом случае номер массива заносится в регистр номера массива 17, а в блок стековой памяти управляющих символов 7 — символ (, означающий начало индексного выражения.

Далее производится вычисление всех индексов (как обычных арифметических выражений) и вычисление номера элемента массива по индексам и размерам массива по всем измерениям, если массив многомерный.

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

Считанная величина заносится во второй регистр операнда 12 и далее производятся действия умножения и сложения. В результате, после обработки носледнего индекса (на это указывает пара «()»), в первом регистре операнда 11 будет записана величина, равная:

51

;«".1, D; !

=1

1, — величина i ãî индекса, D; — размер массива по i-му измерению.

Эта величина — номер элемента массива.

После ее вычисления производится запись номера массива из регистра номера массива 17 в соответствующее поле первого регистра операнда 11 и информация в этом регистре помечается, как адрес элемента массива, Если при вычислении индекса снова встретится обращение к массиву с индексным выражением, то производится запись регистра номера массива 17 и счетчика индексных позиций 16 в блок стековой памяти управляющих символов 7. После окончания обработки вложенного обращения старое содержимое этого регистра и счетчика восстанавливается.

В случае переполнения блока стековой памяти управляющих символов 7 или блока стековой памяти операндов 10 производится перепись соответствующего стека в главную паь ять. Момент переполнения устанавливается с помощью сигнала из индикатора нуля б или индикатора нуля 9.

Если при обращении к блоку стековой памяти операндоз 10 или блоку стековой памяти управляющих символов 7 за операндом или управляющим символом он оказывается пустым (это устанавливается также с помощью сигнала из индикатора нуля б или индикатора нуля 9), то производится перепись из памяти в этот блок его старого содержимого.

Формула изобретения

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

9715

10 вход соединен с третьим выходом блока у)правления, выход признака — подключен к третьему входу блока управления, информационный выход соединен с информационным входом блока стековой памяти операндов, с информационным выходом устройства и с первым информационным входом арифметического блока, второй регистр операнда, информационный вход которого соединен с информационным выходом первого регистра операнда, с информационным входом устройства, первый управляющий вход подключен к третьему управляющему выходу арифметического блока, второй управляющий вход соединен с третьим выходом блока управления, выход признака соединен с четвертым входом блока упра вления, информационный выход соединен с информационным входом первого регистра операнда, с информационным выходом устройства и со вторым информационным входом арифметического блока, блок чтения программы, первый информационный вход которого соединен с информационным входом устройства, адресный выход подключен к информационному выходу устройства, информационный вы: од соединен с пятым входом блока упрагления, управляющий вход подключен к четвертому выходу блока управления, о тл и ч а ю щ е е с я тем, что, с целгяо упрощения трансляции с языков высокого уровня и сокрашения времени трансляции, в него введены блок формирования адресов и операндов, информационный вход которого подключен к информационному выходу блока чтения програм;;.ь), )правля)ощпй вход подключен к четвертому выходу блока управления, первыи инфо мационный выход соединен со вторым информационным входом блока чтения программы, второй информационный выход подключен к информационному входу второго регистра операнда, блок стековой памяти управляющих символов, управляющий вход котооого соединен с пятым выходом блока управ.. ения. информационный вход соединен с инфоомациопным выходом блока чтения програмх)ы, информационный выход соединен с третьим информационным входом блока чтения программы, счетчик управляющих символов, счетный вход которого соединен с пятым выходом блока управления, выход — с адресным входом блока стековой памяти управляющих символов, первый индикатор нуля, вход которого подключен к выходу счетчика уп авляющих символов, выход — к шестому у ) входу блока управления, блок анализа управляющих символов, первый инфор лационный вход которого соединен с информационным ь)хо))ом блока чтения программы, второй инс! оома))ионный вход подключен к ннформаj ционному выходу блока стековои памяти управляющих символов, гыхол соединен с сс",, мым гходом блока управления, второй индикатор нуля, вход которого подключен к выходу i i.!÷èêà огеранло, Bbiход соединен с

):осьмым входом блока управления, счетчик

519715!

Составитель А. Жеренов

Техред 3. Тараненко

Редактор Н. Коляда

Корректор О. Тюрина

Заказ 1582/9 Изд. № 1465 Тираж 864 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, 5К-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2 индексных позиций, счетный вход которого подключен к третьему выходу блока управления, информационный вход соединен с информационным выходом блока чтения программы и с информационным выходом блока стековой памяти управляющих символов, выход соедин=-н с информационным выходом устройства и с информационным входом блока стековой памяти управляющих символов, регистр номера массива, вход которого подключсн к информационному выходу блока чтения программы и к информационному выходу блока стековой памяти управляющих симво",ñâ, выход соединен с информационным выходом устройства, с информационным входом блока стековой памяти управляющих символов и с информационным входом первого регистра операнда.