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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 0) 519715 Союз Советских Социалистических(51) М. Кл е 6 06 Г 15/04 Государственный комитет Совета Министров СССР 23) Приоритет ковано 30,06.76, Бюллетень24 Опуб ДК 681.326,3) УСТРОЙСТВО ДЛЯ ОБРАБОТКИ ВЫРАЖЕНИПРОГРАММИРОВАНИЯ Изобретение относится к области вычислительной техники и может быть использовано в качестве специализированного устройства обработки информации при построении многопроцессорных вычислительных систем.Известны устройства, содержащие блок управления, арифметический блок, блок стековой памяти операндов, счетчик операндов, первый регистр операнда, второй регистр операнда, триггеры занятости обоих регистров операндов, блок чтения программы и предназначенные для реализации арифметических и логических вычислений с использованием Польской инверсной записи без адресации промежуточных результатов в процессе вычисления.Недостатком известных устройств являются большие затраты времени и сложность трансляции с языков высокого уровня на внутренний язык устройства, а также неудобство ручного программирования на этом языке.Целью изобретения является упрощение трансляции с языков высокого уровня и сокращение времени трансляции.Сущность изобретения заключается в том, что в устройство вводятся блок стековой памяти управляющих символов, блок анализа управляющих символов, счетчик управляющих символов, блок формирования адресов и операндов, счетчик индексных позиций и регистр номера массивакоторые позволяют существен но усовершенствовать внутренний языкпредлагаемого устройства,Практически устройство является аппараратурной реализацией нового языка, близкого5 языкам высокого уровня и обеспечивающегозапись программы в естественнои и компактной форме. При этом программисту предоставляются такие удобства, как возможность работы с многомерными массивами, специаль 10 пые средства для организации цикла и т. д.Реализация указанного языка позволяет исключить этап трансляции программ арифметических и логических выражений, сведя еек аппаратной замене идентификаторов пере 15 менных на адреса, индентификаторов массива на номера и к перекодировке символовопераций и скобок в соответствующие управляющие символы.К преимуществам предлагаемого устройст 20 ва можно отнести и то, что подобие междупрограммой на языке высокого уровня и соответствующей программой на внутреннем языке процессора существенно облегчает задачуконтролирования выполнения программ при25 откл адке.Схема устройства представлена на чертсже.Она содержит блок чтения программы 1,блок формирования адресов и операндов 2,блок управления 3, блок анализа управляю.30 щих символов 4, счетчик управляющих симво 5197153лов 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 регистров высокоскоростной части главной памяти.Вид 1 - три разряда - код 001, пять разрядов - код номер массива, двадцать четыре разряда - код номера элемента. Задает адрес элемента массива.,Вид 11 - три разряда - код 010, тринадцать разрядов - операнд.Задает непосредственный операнд. 5 1 О 15 20 25 зо 35 40 45 50 55 60 65 Вид 111 - три разряда - 011, тринадцать разрядов - номер элемента.Обращение к массивуО. Сообщается номер элемента массива.Вид И - три разряда - 100, пять разрядов - номер массива.Адресуется текущий элемент массива.Вид Ч - три разряда - 101, пять разрядов - номер массива,Этот вид эквивалентен паре знаков АЛГОЛа: М , т, е. указывает номер массива и одновременно служит левой границей индексного выражения.Вид И - три разряда - 1 О, пять разрядов - номер регистра.Этот вид осуществляет индексацию при обращении к массивуО, т. е, эквивалентен следующей последовательности знаков АЛГОЛа: М Я (М - идентификатор нулевого массива, Я - регистра),За этим элементом следует продолжение индексного выражения.Вид И 1 - три разряда - П 1, пять разрядов - управляющий символ,Этот вид обозначает управляющие символы.Основными конструкциями языка являются арифметическое и логическое выражения, Их синтаксис подобен синтаксису аналогичных конструкций в языке АЛГОЛ, одиночные переменные изображаются с помощью видов О, 1, Е.1 и И, переменные с индексами с помощьк видов И и Ъ, а знаки операций с помощьк вида И 1. Вместо символаиспользуется символ ), Кроме того, отсутствует аппарат обращения к процедурам - функциям (его лишь до некоторой степени может заменить операция саП - переход с возвратом),Общая структура программы на языке формул описывается следующим образом:программа= (оператор)оператор=арифметическое выражение (логическое выражение) присваивание (цикл) оператор, оператор,Оператор цикл имеет следующий вид: ао оператор ыййе логическое выражение.Внутренний оператор выполняется до тех пор, пока выполняется условие, представленное логическим выражением.Оператор присваивание имеет такой же вид, как аналогичный оператор в АЛГОЛе,Условный переход:логическое выражение, программный адрес. Если логическое выражение равно аЬе, то происходит переход по программному адресу (программный адрес не является видом и никак не помечается, состоит из номера массива и номера байта),Безусловный переход: до 1 о программный адрес.Переход с возвратом; сай программный ад. рес.Эта операция запоминает адрес возврата и осуществляет переход по программному адресу. Возврат вызывается операцией ген,5197 5Блок чтения программы 1 осуществляет последовательное чтение программы на языке формул из главной памяти (на чертеже не показана). Очередной байт программы поступает на выход блока чтения программы 1. Три первых разряда очередного байта поступают в блок управления 3 и по ним определяется вид каждой новой элементарной записи. В зависимости от вида элементарной записи производятся следующие операции.Если элементарная запись является непосредственным операндом (вид 11) или адресом (виды О, 1, 111), то она посылается в блок формирования адресов и операндов 2, где операнды и адреса приводятся к соответствующему формату (см. ниже).Сформированный операнд или адрес пересылаются во второй регистр операнда 12.В случае элементарной записи вида 17 (обращение к текущему элементу массива) номер адресуемого массива посылается в регистр номера массива 17. Далее производится обращение к паспорту массива за адресом текущего элемента массива, Прочитанный адрес вместе с номером массива посылаются во второй регистр операнда 12.В случае элементарной записи вида Ч номер адресуемого массива посылается в регистр номера массива 17, причем содержимое этого регистра и счетчика индексных позиций 16 засылается в блок стековой памяти управляющих символов 7. После этого в блок стековой памяти управляющих символов из блока управления заносится управляющий символ и счетчик индексных позиций 16 обнуляется.В случае элементарной записи вида Ч 1 производится то же, что и в предыдущем случае, но в регистр номера массива 17 заносится нулевое значение, После этого во второй регистр операнда 12 с выхода блока 2 заносится номер регистра, указанный в элементарной записи,Занесение во второй регистр операнда производится по следующим правилам. Если триггер занятости 13 второго регистра операнда установлен в О (второй регистр операнда 12 свободен), то производится запись во второй регистр операнда 12. После этого анализируется состояние триггера занятости 14 первого регистра операнда, Если триггер находится в состоянии 1 (первый регистр операнда 11 занят), то триггер занятости 13 второго регистра операнда устанавливается в 1. Если триггер занятости 14 первого регистра операнда находится в О, то производится перезапись из второго регистра операнда 12 в первый пегистр операнда 11 и триггер занятости 14 первого регистра операнда устанавливается в 1.Если триггер занятости второго регистра операнда установлен в 1, то производится предварительная перезапись содержимого первого регистра операнда П в блок стековой памяти операндов 10 и перезапись содержимого второго регистра операнда 12 в первый регистр операнда 11. 56Информация в первом и втором регистрах операндов 11 и 12 мояет быть четырех типов (номер типа записывается в двух левых разрядах регистра): операнд с фиксированной запятой, занимает половину регистра (одно машинное слово); операнд с плавающей запятой, занимает весь регистр (два слова); адрес (номер) регистра, номер регистра записан в правых пяти разрядах левой половины регистра; адрес элемента массива, который состоит из номера элемента и номера массива, номер массива записан в правых пяти разрядах левой половины регистра, в остальных разрядах записан номер элемента.Логические значения представляются с помощью типа 1 1 гие - все единицы, аЬе - все нули.Длина ячейки блока стековой памяти операндов - одно машинное слово (четыре байта).При записи содержимого первого регистра операндов 11 в блок стековой памяти операндов 10 в случае первого, третьего и четвертого типов записывается содеряимое только левой половины этого регистра, а в случае второго типа - сначала содержимое правой, а затем левой половины. Перед записью каждого слова к счетчику операндов 8 прибавляется единица. Запись производится в ячейку, адрес которой содержится в этом счетчике.Аналогично, перед записью в блок стековой памяти управляющих символов 7 прибавляется единица к счетчику управляющих символов 5.Если элементарная запись является управляющим символом (вид Ч 11), то работа процессора целиком определяется прочитанным управляющим символом и управляющим символом, находящимся к этому времени в вершине управляющего стека, т. е. в ячейке блока стековой памяти управляющих символом 7, адрес которой содержится в счетчике управляющих символов 5.Оба вышеуказанных управляющих символа подаются на вход блока анализа управляющих символов 4, Этот блок представляет собой ассоциативную память, в которой записаны правила расшифровки языка. Оба управляюгцих символа поступают на шины опроса ассоциативной памяти. С выхода блока анализа управляющих символов 4 считывается управляющий код, который подается в блок управления 3 и вызывает переход к микропрограмме, соответствующей данной паре управляюгцих символов5 10 15 20 25 30 35 40 45 50 60 55 Действия процессора в общем случае могут быть следующими: выполнить операцию, соответствующую управляющему символу в вершине управляющего стека, вычесть единицу из счетчика управляющих символов 5 и вернуться к фазе анализа; занести прочитанный управляющий символ в блок стековой памяти управляющих символов 7 и продолжить чте. ние программы,/Выбор для каждой пары управляющих символов одного из двух указанных вариантов делается в соответствии с приоритетами управляющих символов,Для пары а, в (а - управляющий 5символ из вершины управляющего стека,в - прочитанный из программы); если приоритет а больше, чем приоритет в или равен ему, то выбирается вариант 1; если приоритет в больше, чем приоритет а, то выбирается вариант 2.Например, в случае пары "+ выбираетсяпервый вариант, в случае пары ф (выбирается второй вариант.Отметим, что некоторые управляющие символы в позиции прочитанного из программысимвола имеют один приоритет, а в позициисимвола из вершины управляющего стека -другой (стековый),В некотором случае действия могут отличаться от вышеуказанных вариантов. Например, если прочитанный из программы символявляется символом типа перехода фо 1 о, саП),то сразу же выполняется соответствующий переход, т. е, блок чтения программы 1 продолжает дальнейшее чтение программы, начинаяс адреса, сообщаемого в операции перехода.В случае операции саП производится такжезанесение адреса возврата из блока чтенияпрограммы 1 в блок стоковой памяти управля- ЗОющих символов 7 (в пять последовательных ячеек). При выполнении операции ген(возврат) информация из пяти верхних ячеекуправляющего стека заносится в блок чтенияпрограммы 1,35Для выполнения арифметических и логических операций производится обращение карифметическому блоку 15. Арифметическиеи логические операции всегда производятсянад величинами в первом и втором регистрах 4операндов 11 и 12, которые используются каквнутренние регистры арифметического блока15. Для большинства арифметических и логических операций (для двуместных) необходимо, чтобы оба регистра были заняты. Поэтому, 45если триггер занятости 13 второго регистраоперанда находится в О (второй регистропеоанда 12 пуст), а триггер занятости первого регистра операнда находится в 1, топроизводится предварительная перепись из 5 Опервого регистра операнда 11 во второй регистр операнда 12, перепись из блока стековой памяти операндов 10 в первый регистроперанда 11 (из ячейки, адрес которой содержится в счетчике операндов 8) и триггер занятости второго регистра операнда устанавливается в 1,При этом если считываемая из блока стековой памяти операндов 10 информация относится к типам 1, 3 или 4, то производится чтение 60одного слова, которое заносится в левую половину первого регистоа операнда, если жеона относитсятипу . то производится чтение д:;у:, с.х. о: р.е аносятся в левую ив правую поло:и:ну этого регистра, После чте 8ния каждого слова из счетчика операндов 8вычитается единица.Если оба триггера занятости 13 и 14 находятся в О, то вышеуказанная операция повторяется два раза, пока не заполняется первыи и второй регистры операндов 11 и 12,после чего эти триггеры устанавливаютсяв 1.1 сли при выполнении арифметической илилогической операции в первом регистре операнда 11 или втором регистре операнда 12 находится адрес, то производится предварительная выборка операндов в эти регистры изглавной памяти. Адрес подается на информационный выход 19 и считанный из главнойпамяти операнд поступает на информационный вход 18, Согласование работы главнойпамяти и предлагаемого устройства производится с помощью управляющего выхода 20 иуправляющего входа 21 устройства.Результат операции помещается в первыйрегистр операнда 11, Триггер занятости второго регистра операнда 13 устанавливается вО. Тип результата совпадает с типом операндов, если же один операнд имеет тип 1,а другой тип 2, то результат получается типа 2.При операции присваивания в первом регистре операндов 11 должен находиться адрес,а во втором регистре операндов 12 - записываемое значение. После записи значения повышеуказанному адресу обе величины уничтожаются (триггер занятости первого регистра операндов и триггер занятости второго регистра операндов устанавливаются в О).Адреса в регистры 11 и 12 попадают или изпрограммы (виды О, 1, 111 и 17) или в результате некоторого вычисления в случае обращения к массиву с индексным выражением (виды Чи Л).В этом случае номер массива заносится врегистр номера массива 17, а в блок стековойпамяти управляющих символов 7 - символ ,означающий начало индексного выражения.Далее производится вычисление всех индексов(как обычных арифметических выражений) ивычисление номера элемента массива по индексам и размерам массива по всем измерениям, если массив многомерный,После вычисления каждого индекса (на окончание вычисления индекса указывает пара , (производится обращение к памяти (к паспорту массива). за размером массива по соответствующему измерению. Для этого на шины связи с памятью подается номер массива из регистра номера массива 17 и номер индексной позиции из счетчика индексных позиций 16.Считанная величина заносится во второй регистр операнда 12 и далее производятся действия умножения и сложения. В результате, после обработки носледнего индекса (на это указывает пара , в первом регистре операнда 11 будет записана величина, равная:.О; - размер массива по -му измерению.Эта величина - номер элемента массива. После ее вычисления производится запись номера массива из регистра номера массива 17 в соответствующее поле первого регистра операнда 11 и информация в этом регистре помечается, как адрес элемента массива,Если при вычислении индекса снова встретится обращение к массиву с индексным выражением, то производится запись регистра номера массива 17 и счетчика индексных позиций 16 в блок стековой памяти управляющих символов 7. После окончания обработки вложенного обращения старое содержимое этого регистра и счетчика восстанавливается.В случае переполнения блока стековой памяти управляющих символов 7 или блока стековой памяти операндов 10 производится перепись соответствующего стека в главную паь ять. Момент переполнения устанавливается с помощью сигнала из индикатора нуля б или индикатора нуля 9.Если при обращении к блоку стековой памяти операндоз 10 или блоку стековой памяти управляющих символов 7 за операндом или управляющим символом он оказывается пустым (это устанавливается также с помощью сигнала из индикатора нуля б или индикатора нуля 9), то производится перепись из памяти в этот блок его старого содержимого. Формула изобретенияУстройство для обработки выражений языков программирования, содержащее блок управления, управляющие вход и выход которого соединены с одноименными входом и выходом устройства, арифметический блок, управляющий вход которого соединен с первым выходом блока управления, первый управляющий выход соединен с первым;входом блока управления, два триггера занятости, входы установки в ноль которых подключены ко второму управляющему выходу арифметического блока, входы установки в единиц подключены ко второму выходу блока управления, выходы соединены со вторым входом блока управления, блок стековой памяти операндов, управляющий вход которого соединен с третьим выходом блока управления, счетчик операндов, счетный вход которого подключен к третьему выходу блока управления, выход - к адресному входу блока стеко вой памяти операндов, первый регистр операнда., вход которого соединен с информационным выходом блока стековой памяти операндов, с информационным выходом арифметического блока, с информационным входом устройства, первый управляющий вход подключен к третьему управляющему выходу арифметического блока, второй управляющий9715 5 10 15 20 25 30 35 40 45 50 55 60 65 10вход соединен с третьим выходом блока у)правления, выход признака - подключен к третьему входу блока управления, информационный выход соединен с информационным входом блока стековой памяти операндов, с информационным выходом устройства и с первым информационным входом арифметического блока, второй регистр операнда, информационный вход которого соединен с информационным выходом первого регистра операнда, с информационным входом устройства, первый управляющий вход подключен к третьему управляющему выходу арифметического блока, второй управляющий вход соединен с третьим выходом блока управления, выход приз)нака соединен с четвертым входом блока управления, информационный выход соединен с информационным входом первого регистра операнда, с информационным выходом устройства и со вторым информационным входом арифметического блока, блок чтения программы, первый информационный вход которого соединен с информационным входом устройства, адресный выход подключен к информационному выходу устройства, информационный выход соепинен с пятым входом блока упрагления, управляющий вход подключен к четвертому выходу блока управления, отл и ч а ю щ е е с я тем, что, с целгяо упрощения трансляции с языков высокого уровня и сокрашения времени трансляции, в него введены блок формирования адресов и операндов, информационный вход которого подключен к информационному выходу блока чтения програм;, ы, )п",авля)ощий вход подключен к четверн тому выходу блока управления, первыи инфопмациониый выход соединен со вторым информационным входом блока чтения программы, второй информационный выход подключен к информационному входу второго регистра операнда, блок стековой памяти управляющих символов, управляющий вход котооого соединен с пятым выходом блока управ.пения, информационный вход соединен с инфоомациопным выходом блока чтения ппограммы, информационный выход соединен с третьим информационным входом блока чтения программы, счетчик управляющих символов, счетный вход которого соединен с пятым выходом блока управления, выход - с адресным входом блока стековой памяти управляющих символов, первый индикатор нуля, вход которого подключен к выходу счетчика упавляющих символов, выход - к шестому у )входу блока управления, блок анализа управляющих символов, первый инфор лационный вход которого соединен с информационным ыхолом блока чтения программы, второй инск оп) а),ионный вход подключен к ннформанционному выходу блока стековои памяти управляюц)цх символо)в, гыход соединен с сс",):мь)м гходом блока управления, второй индикатор нуля, вход которого подключен к выходу с)егчика огеранлов, выход соединен с ):осьмым входом блока управления, счетчик519715 12 Составитель А, ЖереновТехред 3. Тараненко Редактор Н. Коляда Корректор О Тюрина Заказ 1582/9 Изд,1465 Тираж 864 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, Ж.35, Раушская наб., д. 4/5Типография, пр, Сапунова, 2 индексных позиций, счетный вход которого подключен к третьему выходу блока управления, информационный вход соединен с информационным выходом блока чтения программы и с информационным Выходом блока стековой памяти управляющих символов, вы- ХОД СОЕДИНЕН С ИпфоРМаЦИОННЫМ ВЫХОДОМ устройства и с информационным входом блока стековой памяти управляющих символов,регистр номера массива, вход которого подключсн к информационному выходу блока чтения программы и к информационному выходу блока стековой памяти управляющих симво лов, выход соединен с информационным выходом устройства, с информационным входом блока стековой памяти управляющих символов и с информационным входом первого регистра операнда.