УСТРОЙСТВО ДЛЯ ТРАНСЛЯЦИИ ПРОГРАММ Советский патент 1969 года по МПК G06F9/30 

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

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

Пзвестные устройства обладают низким быстродействием, так как внутренним языком является некоторый алгоритмический язык, сложностью перестройки для работы с другим языком, а также большими экономическими затратами для переделки при внесении изменений в грамматику языка. Устройства применимы для узкого класса языков, так как они используют для синтаксического анализа символа Т входной программы только одно иредыдуш,ее состояние блока управления, в то время как для большинства языков при анализе символа TI входной программы необходимо учитывать несколько предыдуш,их состояний блока управления (например, если разные предлол-сения языка имеют одинаковые последовательности символов).

Предлагаемое устройство отличается тем,

что выходной регистр постоянного запоминающего устройства (ПЗУ) разбит на несколько регистров, причем :выход регистра начальных адресов подпрограмм через схему переписи начального адреса нодпрограммы соединен со

входами входных регистров ПЗУ, выход регистра основного кода через схему перезаписи основного кода с первым входом регистра сформированного кода, а выход регистра сформированного кода с первым входо.м блока прерывания и управления и с первым входом схемы сравнения кодов, выхоз, которой соединен со вторым входом блока прерывания и уиравления. Выход регистра допустимых кодов соединен со вторым входом

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

кода, выход блока магазинной памяти соединен со вторым входом регистра сфор у1ировапного кода, а второй н третий БХОДЫ блока иаыяги соединены соответственно с выходом регистра чтения и записи всиомогательного кода.

Ма чертеже представлена блок-схема оиисываемого устройства.

Она состоит из постоянного запоминаюидего устройства (ПЗУ) /, входного регистра 2, дешифратора 3, схемы совиаденмя 4, блока ячеек 5, дешифратора 6, входного регистра 7, схемы переписи 8 начального адреса подпрограммы, выходного регистра 9-, регистра 10 начальных адресов нодирограмм, регистра // основного кода, регистра 12 вспомогательного кода, регнстра /5 донустимых (согласно грамматики языка) кодов, регистра 14 чтения всиомогательного кода, регистра 15 записи вспомогательного кода, регистра 16 прерывания, блока магазинной иамяти (МП) 17, схемы переписи 18 основного кода, регистра 19 сформированного кода, схемы 20 сравнения кодов, блока ирерывания н уиравления 21.

Предлагаемое устройство использует задаиие грамматики языка в виде орпенгированиого графа, дуги которого помечены терминальными символами, а вершины графа-двоичными кодами. Каждый двоичный код в вершине графа определяет некоторое состояние устройства. Переход из вершины /И графа в вершину V графа иод действием некоторого терминального символа /., помечающего дугу, исходяш:ую из вершины М в вершину Л графа, соответствует иереходу устройства из одного состояния в другое иод действием того же символа /. при синтаксическом анализе входной ирограммы. Каждое состояние устройства фиксируется двоичным кодом на регистре сформированного кода. В отличие от известных устройств двоичный код (состояние) в вершине графа состоит из двух частей: основного и вспомогательного кодов. Основной код формируется текущим символом Т входной программы для синтаксического анализа следующего символа ирограммы. Вспомогательный код формируется текущим символом TI для синтаксического анализа символа Tt+t+i программы совместио с основным кодом, сформнрованным символом Ti-i-i программы (где / - число символов одинаковой последовательности символов разных предложений языка). При этом вспомогательный код записывается в МП и не участвует в работе устройства до прихода символов 7/-./ программы. Составленный таки. образом граф заиисывается в анализирующую таблицу.

В основу устройства положена идея трансляции программ при помощи генерирующих подпрограмм (т. е. подпрограмм преобразования проанализированной части входной программы в выходную программу), причем действие каждой генерирующей иодпрограммы определяется определеиной строкой анализирующей таблицы. Строка анализирующей таблицы, для которой отводится одиа ячейка ПЗУ, содержит следующую информацию: донустимый код (т. е. код в вершине Л4 графа для символа /.), формируемый OCHOBHOII и

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

Предлагаемое устройство трансляции программы работает следующим образом.

Текущий символ Т входной программы заиисывается на входной регистр 2, затем изменениями на еднницу содержимого регистра 7 иро;1зводятся считывания содержимого блока ячеек 5 (строк анализирующей таблицы символа 7 ) на выходной регистр 9. После каждого считываиия содержимого блока ячеек 5 производится сравнение схемой 20 допустимого кода текущего символа Т (по входу 22), запнсанного на регистре 13 допустимых кодов,

с двоичным кодом (по входу 23), сформированным предыдущим символом программы и заиисанным на регистре 19 сформированного кода. При сравнении двоичных кодов производится сброс регистра 7 и формирование нового двоичного кода лТ,ля синтаксического анализа следующего символа Tc+i программы. Формирование нового основного кода за1ключается в шерениси содержимого регистра 11 основного кода через схему переписи 18 на первую часть регистра 19 сформированного кода по входу 24. Затем производится последовательно анализ регистра 14 чтения вспомогательного кода, регистра 15 залиси Вспомогательного кода и регистра 16 прерывания.

Если в единичном состоянии находится регистр 14 (т. е. на входе 25 МП будет высокий уровень напряжения), то производится переинсь всиомогательного кода из верхней ячейки МП 17 на вторую часть регистра 19 сформированного кода по входу 26 с последующим сдвигом содержимого магазинной памяти вверх на одну ячейку. Если в единичном состоянии находится регистр 15 (т. е. на входе 27 МП будет высокий уровень напряжения), то производится Перепись вспомогательного кода с регистра 12 вспомогательного кода в верхнюю ячейку МП с нредварительным сдвигом содержимого МП вниз на одну ячейку. Если в единичном состоянии находится регистр 16 нрерывания, то блоком прерывания и управления 21 производится прерывание синтаксического анализа входной программы (так как на входе 28 блока прерывания и

уиравления будет высокий уровень напряжения) и производится переход на генерирующую подпрограмму транслятора (например, преобразование уравнения в польскую форму записи и т. п.). В этом случае начальный адпереписи 8 переписывается с регистра 10 Па регистры 2 и 7. Каждая инструкция этой подпрограммы считывается изблока ячеек 5 изменением на единицу содержимого регистра 7, и с выходного регистра 9 поступает в цифровую вычислительную машину (ЦВМ). После выполнения генерирующей подпрограммы производится сброс регистра 7, запись следующего символа Jt+i программы на регистр 2 и трансляция программы продолжается как написано выше. Несовпадение двоичного кода, сформированного символом T(-i программы, ни с одним из допустимых кодов символа j программы означает, что текущий символ Т записан синтаксически неверно. В этом случае производится останов устройства, так как с регистра 13 на вход 29 блока прерывания и управления 21 поступает код «ошибка. Трансляция входной нрограммы прекращается, когда с регистра J9 на вход 30 блока прерывания и управления 21 поступает код «конец программы.

После окончания процесса трансляции производится переход на рабочую программу, которая получена в результате выполнения определенных генерирующих подпрограмм в ЦВМ и которая записана в памяти ЦВМ.

Предложенное устройство применимо для большинства практически используемых алгоритмических языков, так как грамматика языка хранится в матрицах ПЗУ и, следовательно, возможность использования языка определяется только объемом ПЗУ (чтобы внести изменения в язык и использовать устройство для трансляции программ, составленных па новом языке, достаточно сменить матрицы ПЗУ).

6 Предмет изобретения

1. Устройство для трансляции программ, состоящее из блоков перекодирования входной

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

входами входных регистрои остояпного запомипа О1ДС10 устройства, выход рег11ст|а осаэпного кода через схему перезаписи основного кода соединен с первым входом регистра сформированного кода, а выход регистра

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

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

.

i I

V V ,: x.;:

i8 1 f

..

.--..-- 1

i I 1 7/7 7 1 7 i

Ж

4

I;S

-й

f-- 0.

;

/7

Z5T-T27

:i3..

,