Устройство для трансляции программ

О П И С А Н И Е 25715ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ бойз Советоиих Социдлиотицеоиих Реоптблик.1968 (Ло аявлено 05 Х м заявки Х присоединени МПК 6 061 Комитет па делам риорит зобретений и аткрытипри Совете МинистровСССР ллетень М Опубликован ДК 68,326,3(088 1.Х 1,1969, Б.11.1970 та опублико ания описан 1 Л вторыизобретени Н, Малиновский, Н. Рабед анов и С. Б. Додон 1 тГ Ртт 1 т,РИР 1 1. тр я .МГКА Заявител Украинской СС нститут кибернетики УСТРОЙСТВО ДЛЯ ТРА ПРОГ Л состояние блокас для большинств ола Т, входной п тывать несколько лока управленияедложения языка тельности символ дыдущее время ка лизе сив димо уч стояний разные п последов правления, языков пр ограммы н предыдущ 1 (например, 1 еют одина в то т ана. еобхо- соесли ковые Предлагаемое устройство относится к области использования алгоритмических языков в вычислительной технике и может быть применено для трансляции программ, составленных на алгоритмическом языке.Известны устройства, позволяющие выполнять программы непосредственно в некотором алгоритмическом языке. Эти устройства используют задание грамматики языка в виде ориентированного графа, дуги которого помечены терминальными символами грамматики языка, а вершины определенными двоичными кодами. Последовательность символов пройденного пути графа от начальной до конечной вершин графа является предложением языка. Переход из одной вершины графа в друтую под действием соответствующего сим вола языка указывается дугой и означает переход из одного состояния в другое для синтаксического анализа следующего символа входной программы.Известные устройства обладают низким быстродействием, так как внутренним языком является некоторый алгоритмический язык, сложностью перестройки для работы с друтим языком, а также Оольшими экономи 1 ескР 1 м и затратами для переделки при внесении изменений в грамматику языка. Устройства применимы для узкого класса языков, так как они используют для синтаксического анализа символа Т, входной программы только одно пре 10 15 20 25 30 Предлагаемое устройство отличается тем, что выходной регистр постоянного запоминающего устройства (ПЗУ) разбит на несколько регистров, причем выход регистра начальных адресов подпрограмм через схему переписи начального адреса подпрограммы соединен со входами входных регистров ПЗУ, выход регистра основного кода через схему перезаписи основного кода с первым входом регистра сформированного кода, а выход регистра сформированного кода с первым входом блока прерывания и управления и с первым входом схемы сравнения кодов, выход которой соединен со вторым входом блока прерывания и управления. Выход регистра допустимых кодов соединен со вторым входом схемы сравнения кодов и третьим входом блока прерывания и управления, а четвертый вход блока прерывания и управления соединен с выходом регистра прерывания, Кроме того, предлагаемое устройство отличается тем, что первый вход блока магазинной памяти соединен с выходом регистра вспомогательногокода, выход блока магазинной памяти соединен со вторым Входом регистра сформировав ного кода, а второй и третий входы блока памяги соединены соответственно с выходом регистра пения и завпсп вспомогательного кода,11 а чертеже представлена блок-схема описываемого устроиства.Она состоит из постоянного запоминающего устройства (ПЗУ) 1, входного рспистра 2, дешифратора 3, схемы совпадения 4, блока ячеек 5, дешифратора 6, входного регистра 7, схемы переписи 8 начального адреса подпрограммы, выходного регистра 9, регистра 10 начальных адресов подпрограмм. регистра 11 основного кода, регистра 12 вспомогательного кода, регистра И допустимых (согласно грамматики языка) кодов, регистра 14 чтения вспомогательного кода, регистра 15 записи вспомогательного кода, регистра 1 б прерывания, блока магазинной памяти (МП) 17, схемы переписи 18 основного кода, регистра 19 сформированного кода, схемы 20 сравнения кодов, блока прерывания и управления 21.Предлагаемое устройство использует задание грамматики языка в виде ориентированного графа, дуги которого помечены терминальными символами, а вершины графа - двоичными кодами. Каждый двоичньш код в вершине графа определяет некоторое состояние устройства. Переход из вершины И графа в вершину Я графа под действием екоторого терминального символа ., помечающего дугу, исходящую из вершины Л 1 в вершину Л графа, соответствует переходу устройства из одного состояния в другое под действием того же символа . при синтаксическом анализе входной программы. Каждое состояние устройства фиксируется двоичным кодом на регистре сформированно о кода, В отличие от известных устройств двоичный код (состояние) в вершине графа состоит из двух частей: основного и вспомогательного кодов. Основной код формируется текущим символом Т, входной программы для синтаксического анализа следующего символа Т;+1 программы, Вспомогательнып код формируется текущим символом Т, для синтаксического анализа символа Т+,+т программы совместно с основным кодом, сформированным символом Тс., программы (где 1 - число символов одинаковой последовательности символов разных предложений языка) . При этом вспомогательньш код записывается в МП и не участвует в работе устройства до прихода символов 1.,г программы, Составленный таким образом граф записывается в анализирующую таблицу.В основу устройства положена идея трансляции программ при помощи генерирующих подпрограмм (т. е. подпрограмм преооразования проанализированной части входной программы в выходную программу), причем действие каждой генерирующей подпрограммы определяется определенной строкой анализирующей таблицы. Строка анализирующей таб 10 15 20 25 30 35 40 45 50 55 60 65 л:шы, для которой отводится одна ячейка ПЗУ, содержит следующую информацшо; допустпмьш код (т. е. код в вершине Л 1 графа для символа .), формируемый основной и вспомогательный коды (сформированный код --код в вершине Л графа для символом ,), информацию о чтении и записи вспомогательного кода из (в) МП, информацию для перехода на определенную генерирующую подпрограмму (для преобразования проанализованной части входной программы в выходную программу).Предлагаемое устройство трансляции программы работает следующим образом.Текущий символ Т, входной программы записывается на входной регистр 2, затем изменениями на единицу содержимого регистра 7 производятся считывания содержимого блока я еек 5 (строк анализирующей таблицы символа , ) на выходной регистр 9. После каждого считывания содеркимого блока ячеек 5 производится сравнение схемой 20 допустимого кода текущего символа Т; (по входу 22), записанного на регистре 13 допустимых кодов, с двоичным кодом (по входу 23), сформированным предыдущим символом Тпрограммы и записанным на регистре 19 сформированного кода, При сравнении двоичных кодов производится сброс регистра 7 и формирование нового двоичного кода для синтаксического анализа следующего символа Тс+1 программы. Формирование нового основного кода заключается в переписи содержимого регистра 11 основного кода через схему переписи 1 Ь па первую часть регистра 19 сформированного кода по входу 24. Затем производится последовательно анализ регистра 14 чтения вспомогательного кода, регистра 15 записи вопомогательного кода и регистра 1 б прерывания.Если в единичном состоянии находится регистр 14 (т, е. на входе 25 МП будет высокий уровень напряжения), то производится перепись вспомогательного кода из верхней ячейки МП 17 на вторую часть регистра 19 сформированного кода по входу 2 б с последующим сдвигом содержимого магазинной памяти вверх на одну ячейку, Если в единичном состоянии находится регистр 15 (т. е, на входе 27 МП будет высокий уровень напряжения), то производится перепись вспомогательного кода с регистра 12 вспомогательного кода в верхнюю ячейку МП с предварительным сдвигом содержимого МП вниз на одну ячейку. Если в единичном состоянии находится регистр 16 прерывания, 1 о блоком прерывания и управления 21 производится прерывание синтаксического анализа входной программы (так как на входе 28 блока прерывания и управления будет высокий уровень напряжения) и производится переход на генерирующу ю подпрограмму транслятора (например, преобразование уравнения в польскую форму записи и т. п,), В этом случае начальный адрес генерирующей подппограммы через схемупереписи 8 переписывается с регистра 10 и;, регистры 2 и 7, Кажда инструкция этой подпрограммы считывается из блока ячеек 5 изменением на единицу содеркимого регистра 7, и с выходного регистра 9 поступает в цифровую вычислительную машину (ЦВМ), После выполнения генерирующей подпрограммы производится сброс регистра 7, запись следующего символа У 1+1 программы на регистр 2 и трансляция программы продолжается как написано выше. Несовпадение двоичного кода, сформированного символом Т 1программы, ни с одним из допустимых кодов символа программы означает, что текущий символ Т, записан синтаксически неверно. В этом случае производится останов устройства, так как с регистра 13 на вход 29 блока прерывания и управления 21 поступает код ошибка, Трансляция входной программы прекращается, когда с регистра 19 на вход 30 блока прерывания и управления 21 поступает код конец программы,После окончания процесса трансляции производится переход на рабочую программу, которая получена в результате выполнения определенных генерирующих подпрограмм в ЦВМ и которая записана в памяти ЦВМ. Предложенное устройство применимо для большинства практически используемых алгоритмических языков, так как грамматика языка хранится в матрицах ПЗУ и, следовательно, возможность использования языка определяется только объемом ПЗУ (чтобы внести изменения в язык и использовать устройство для трансляции программ, составленных на новом языке, достаточно сменить матрицы ПЗУ) . 5 ьо 15 20 25 Зо 35 Предмет изобретения 1, Устройство для трансляции программ, состоящее из блоков перекодирования входной программы и блоков памяти, отличаюцееся тем, что, с целью повышения быстродействия и хранения строк анализирующей таблицы и кодов генерирующих подпрограмм транслятора в одном постояннох 1;,",Омппающем усгройстве, выходной регистр пос.олиного запо. м 1 нлОщего устропства раз 011 т па несколько регистров, причем выход рс;истра начальных адресов подпрограмм через . е.;у переписи начальнога адреса: одпрогр:. х. соединен со входами входных регпсгро. встоянного запоми 1 аи 1 це 10 устр 01 ства, выход регст с Ос 10 ВНОГО КОДа ЧЕРЕЗ СХЕМУ ПЕРЕЗаППСИ ОСНОВНОСО кода соединен с первым входом регистра сформированного кода, а выход регистра сформированного кода соединен с первым входом блока прерывания и управления и с первым входом схемы сравнения кодов, выход которой соединен со вторым входом блока прерывания и управления, выход регистра допустимых кодов соединен со вторым входом схемы сравнения кодов и третьим входом блока прерывания и управления, а четвертьш вход блока прерывания и управления соединен с выходом регистра прерывания,2. Устройство по и. 1, от.ачаюшееся тем, чго, с целью расширения класса языков, применимых для схемной трансляции программ, первый вход блока магазинной памяти соединен с выходом регистра вспомогательного кода, выход блока магазинной памяти соединен со вторым входом регистра сформированного кода, а второй и трепи входы блока памяги СОЕДППЕНЫ СООтВЕТСГВЕННО С ВЫХОДОМ РЕГ 1 СРа чтения и записи вспомогательного кода.Семанова ед Составитель Н. ИванееваТехред Т. П. Курилко Корректор Г. П, ШильмаиЗаказЦНИИ 5/2И КомитетаТираж 480елам изобретений и открытий при Советмосква Ж, Ратшская наб., д. 4/5 Типография, пр. Сапунова,Подпис ое1 инпстров СССР