Устройство для трансляции программ
О П И С А Н И Е 25715I
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
C0I03 Соеетоиих
Социдлиотичеоких
Республик
Зависимое от авт. свидетельства ¹
Кл. 42m:I, 9/ОО
Заявлено 05Х1!.1968 (Гй 1254412/18-24) с присоединением заявки ¹
Приоритет
Опубликовано 11.Х1,1969. Бюллетень № 35
Дата опубликования описания 7.11 .1970
МПК G 06f
УДК 68! .326.3(088.8) Комитет па делам изобретений и открытий при Совете Министров
СССР
:j. „
Б. Н. Малиновский, Н. Рабеджанов и С. g, Додонов
1. т у л-ч в °Институт кибернетики AH Украинской ССР
Авторы изобретения
Заявитель тр <я . ттКА
УСТРОЙСТВО ДЛЯ ТРАНСЛЯЦИИ ПРОГРАММ
Предлагаемое устройство относится к области использования алгоритмических языков в вычислительной технике и может быть применено для трансляции программ, составленных на алгоритмическом языке.
Известны устройства, позволяющие выполнять программы непосредственно в некотором алгоритмическом языке. Эти устройства используют задание грамматики языка в виде ориентированного графа, дуги которого помечены терминальными символами грамматики языка, а вершины определенными двоичными кодами. Последовательность символов пройденного пути графа от начальной до конечной вершин графа является предложением языка.
Переход из одной вершины графа в другую под действием соответствующего cHir вола языка указывается дугой и означает переход из одного состояния в другое для синтаксического анализа следующего символа входной программы.
Известные устройства обладают низким быстродействием, так как внутренним языком является некоторый алгоритмический язык, сложностью перестройки для работы с другим языком, а также большими зкономическими затратами для переделки при внесении изменений в грамматику языка. Устройства применимы для узкого класса языков, так как они используют для синтаксического анализа символа Т,. входной программы только одно предыдущее состояние блока управления, в то время как для большинства языков при анализе символа Т, входной программы необходимо учитывать несколько предыдущих состояний блока управления (например, если разные предложения языка имеют одинаковые последовательности символов) .
Предлагаемое устройство отличается тем, 10 что выходной регистр постоянного запоминающего устройства (ПЗУ) разбит на несколько регистров, причем выход регистра начальных адресов подпрограмм через схему переписи начального адреса подпрограммы соединен со
15 входами входных регистров ПЗУ, выход регистра основного кода через схему перезаписи основного кода с первым входом регистра сформированного кода, а выход регистра сформированного кода с первым входом бло20 ка прерывания и управления и с первым входом схемы сравнения кодов, выход которой соединен со вторым входом блока прерывания и управления. Выход регистра допустиiIbIx кодов соединен со вторым входом
25 схемы сравнения кодов и третьим входом блока прерывания и управления, а четвертый вход блока прерывания и управления соединен с выходом регистра прерывания, Кроме того, предлагаемое устройство отличается тем, 30 гго первый вход блока магазинной памяти соединен с выходом регистра вспомогательного
257151 кода, выход блока магазинной памяти соединен ccrc вторыч входом регистра сформированого кода, а второй и третий входы блока памяги соединены соответственно с выходом регистра пения и за исп вспомогательного кода.
На чертеже представлена блок-схема описываемого устройства.
OHB состоит из постоянного запоминающего устройства (ПЗУ) 1, входного регистра 2, дешифратора 8, схемы совпадения 4, блока ячеек 5, дешифратора 6, входного регистра 7, схемы переписи 8 начального адреса подпрограммы, выходного регистра 9, регистра 10 начальных адресов подпрограмм. регистра 11 основного кода, регистра 12 вспомогательного кода, регистра 18 допустимы.; (согласно грамматики языка) кодов, регистра 14 чтения вспомогательного кода, регистра 15 записи вспомогательногG кода, регистра lб прерывания, блока магазинной памяти (МП) 17, схемы переписи 18 основного кода, регистра 19 сформированного кода, схемы 20 сраBíåø ë кодов, блока прерывания и управления 21.
Предлагаемое устройство использует задание грамматики языка в виде ориентированного графа, дуги которого помечены терминальными символами, а вершины графа — двоичными кодами. Каждый двоичньш код в вершине графа определяет некоторое состояние устройства. Переход из вершины И графа в вершину V графа под действием i.åêoòîðîãî терминального символа i., помечающего дугу, исходящую из вершины Л в вершину Л графа, соответствует переходу устройства и", одного состояния в другое под действием того же символа i. при синтаксическом анализе входной программы. Каждое состояние устройства фиксируется двоичным кодом на регистре сформированно-о кода, В отличие от известных устройств двоичный код (состояние) в вершине графа состоит из двух частей: основного и вспомогательного кодов. Основной код формируется текущим символом Т, входной программы для синтаксического анализа следующего символа T;+i программы. Вспомогательный код формируется текущим символом
Т, для синтаксического анализа символа
Т + + программы совместно с основным кодом, сформированныч символом Tt-, программы (где l — число символов одинаковой последовательности символов разных предложений языка) . При этом вспомогательньш код записывается в МП и не участвует в работе устройства до прихода символов ? 1.,i программы. Составленный таким образом граф записывается в анализирующую таблицу.
В основу устройства положена идея трансляции программ при помощи генерирующих подпрограмм (т. е. подпрограмм преооразования проанализированной части входной программы в выходную програмчу), причем действие каждой генерирующей подпрограммы определяется определенной строкой анализирующей таблицы. Строка анализирующей таб10
65 л:шы, для которой отводится одна ячейка
ПЗУ, содержит следующую информацшо: допустпчьш код (т. е. код в вершине М графа для символа i.), формируемый основной и вспомогательный коды (сформированный ко д —— код в вершине Л графа для символом i,), информацию о чтении и записи вспомогательного кода из (в) МП, информацию для перехода на определенную генерирующую подпрограмму (для преобразования проанализованной части входной программы в выходную программу) .
Предлагаемое устройство трансляции программы работает следующим образом.
Текущий символ Т, входной программы записывается на входной регистр 2, затем изменениями на единицу содержимого регистра 7 производятся считывания содержимого блока я еек 5 (строк анализирующей таблицы символа Т, ) на выходной регистр 9. После каждого считывания содержимого блока ячеек 5 производится сравнение схемой 20 допустимого кода текущего символа Т; (по входу 22), записанного на регистре 18 допустимых кодов, с двоичным кодом (по входу 23), сформированным предыдущим символом ? i n рограммы и записанным на регистре 19 сформированного кода. При сравнении двоичных кодов производится сброс регистра 7 и формирование нового двоичного кода для синтаксического анализа следующего символа Tc+> программы. Формирование нового основного кода заключается в,переписи содержимого регистра 11 основного кода через схему переписи 18 па первую часть регистра 19 сформированного кода по входу 24. Затем производится последовательно анализ регистра 14 чтения вспомогательного кода, регистра 15 записи вспомогательного кода и регистра lб прерывания.
Если в единичном состоянии находится регистр 14 (т, е. на входе 25 МП будет высокий уровень напряжения), то производится перепись вспомогательного кода из верхней ячейки МП 17 на вторую часть регистра 19 сформированного кода по входу 2б с последующим сдвигом содержимого магазинной памяти вверх на одну ячейку. Если в единичном состоянии .находится регистр 15 (т. е. на входе 27 МП будет высокий уровень напряжения), то производится перепись вспомогательного кода с регистра 12 вспомогательного кода в верхнюю ячейку МП с предварительным сдвигом содержимого МП вниз на одну ячейку. Если в единичном состоянии находится регистр lб прерывания, чо блоком прерывания и управления 21 производится прерывание синтаксического анализа входной программы (так как на входе 28 блока прерывания и управления будет высокий уровень напряжения) и производится переход на генерирующ Io подпрограмму транслятора (например, преобразование уравнения в польскую форму записи и т. п.). В этом случае начальный адрес генерирующей подппогпаммы через схему
257151 переписи 8 переписывается с регистра 10 и;. регистры 2 и 7. Каждая инструкция этой под программы считывается из блока ячеек 5 изменением на единицу содержимого регистра 7, и с выходного регистра 9 поступает в цифровую вычислительную машину (ЦВМ). После выполнения генерирующей подпрограммы производится сброс регистра 7, запись следующего символа + программы на регистр 2 и трансляция программы продолжается как написано выше. Несовпадение двоичного кода, сформированного символом Т программы, ни с одним из допустимых кодов символа программы означает, что текущий символ Т, записан синтаксически неверно. В этом случае производится останов устройства, так как с регистра 18 на вход 29 блока прерывания и управления 21 поступает код «ошибка». Трансляция входной программы прекращается, когда с регистра 19 на вход 80 блока прерывания и управления 21 поступает код «конец программы».
После окончания процесса трансляции производится переход на рабочую программу, которая получена в результате выполнения определенных генерирующих подпрограмм в ЦВМ и которая записана в памяти ЦВМ.
Предложенное устройство применимо для большинства практически используемых алгоритмических языков, так как грамматика языка хранится в матрицах ПЗУ и, следовательно, возможность использования языка определяется только объемом ПЗУ (чтобы внести изменения в язык и использовать устройство для трансляции программ, составленных на новом языке, достаточно сменить матрицы
ПЗУ) .
Зо
Предмет изобретения
1. Устройство для трансляции программ, состоящее из блоков перекодирования входной программы и блоков памяти, отличаю цееся тем, что. с целью повышения быстродействия и хранения строк анализирующей таблицы и кодов генерирующих подпрограмм транслятора в одном постоянном:,",r,омппающем усгройстве, выходной регистр пос. олиного запоминающего устропства разоит па несколько регистров, причем выход рс;истра начальных адре ов подпрограмм через:. е.; у переписи начального адреса: одпрогр:..",, ы соединен со входами входных регпсгров постоянного запомипаище10 уcTpottcTB2, выход pct ttcT; Основного кода через схему перезаписи ос .овного кода соединен с первым входом регистра сформированного кода, а выход регистра сформированного кода соединен с первым входом блока прерывания и управления и с первым входом схемы сравнения кодов, выход которой соединен со вторым входом блока прерывания и управления, выход регистра допустимых кодов соединен со вторым входом схемы сравнения кодов и третьим входом блока прерывания и управления, а четвертьш вход блока прерывания и управления соединен с выходом регистра прерывания.
2. Устройство по и. 1, отлачаюшееся тем, чго, с целью расширения класса языков, применимых для схемной трансляции программ, первый вход блока магазинной памяти соединен с выходом регистра вспомогательного кода, выход блока магазинной памяти соединен со вторым входом регистра сформированного кода, а второй it трепи входы блока па»rt! It соединены соответс "венно с выходом регисгр:i чтения и записи вспомогательного кода.
Составитель Н. Иванеева
Техред Т. II. Курилко
Редактор Е. Семанова
Корректор Г. П, Шильмаи
Заказ 705/2 Тираж 480 Подписное
ЦЕ!ИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР
Москва Ж-35, Раушская наб., д. 4/5
Типография, пр. Сапунова, 2
