Устройство для аппаратурной трансляции Советский патент 1985 года по МПК G06F17/27 

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

элемента ИЛИ подключен к выходу третьего элемента И, )зторой вход соединен с выходом первого элемента ИЛИ, третий вход соединен с выходом четвертого элемента И, четвертьй вход подключен к выходу пятого элемента И, выход третьего элемента ИЛИ через пятый элемент задержки соединен с первыми входами восьмого и девятого элементов И, вторые входы которых подключены соответственно к единичному и нулевому выходам второго триггера, выходы восьмого и девятого элементов И подключены соответственно к управляющему входу записи и управляющему входу считывания второго блока памяти, третий выход условий первого блока памяти соединен с разрешающими входами первого и второго переключателей, выходы которых подключены соответственно к счетному входу и к входу разрешения приема второго счетчика адреса, выход несравнеиия схемы сравнения соединен с первыми информационными входами первого и второго переключателей и с первым входом десятого элемента И, В1ссод сравнения схемы сравнения подключен к вторым информационным входам первого и второго переключателей и к первому входу второго элемента ИЛИ, выход которого соединен с входом разрешения приема первого счетчика адреса, четвертый выход условий первого блока памяти подключен к второму входу десятого элемента И, выход которого соединен с вторым входом второго элемента ИЛИ, третий вход которого соединен с выходом пятого элемента И

УСТРОЙСТВО ДЛЯ АППАРАТУРНОЙ ТРАНСЛЯЦИИ, содержащее первый блок памяти, два счетчика адреса, регистр вьщачи, схему сравнения, первый элемент ИЛИ, семь элементов И, четыре элемента задержки, три триггера, дешифратор кода пробела, генератор прямоугольных импульсов и второй блок памяти, подключенный информационнымивыходами к первым группам информационных входов регистра вьщачи и схемы сравнения, вторые группы информационных входов которых соединены с информационными выходами первого блока памяти, подключенными к информационным входам первого и второго счетчика адреса, выходы которого соединены с адресными входами первого блока памяти и с входами первого элемента И, подключенного выходом к единичному входу первого триггера, установочный вход которого и установочные входы первого и второго счетчиков адреса соединены с выходом первого элемента ИЛИ, первый вход первого элемента ИЛИ и установочные входы второго и третьего триггеров подключены к установочному входу устройства, выход второго элемента И соединен с вторым входом первого элемента ИЛИ, нулевой выход второго триггера соединен с первым входом второго элемента И, единичньпг вход второго триггера подключен к второму входу второго элемента И, к первому входу третьего элемента И и к первому синхронизирующему входу устройства, выход третьего элемента И соединен с тактовым входом первого счетчика адреса, второй вход третьего элемента И соединен с единичным выходом второго триггера, группа входов транслируемого языка устройства соединена с информационными входами второго блока памяти и дешифратора кода пробела, выходом соединенного с единичным входом второго триггера и с входом пуска генератора прямоугольных импульсов, выход которого подключен к входу считьшания первого блока памяти, юпА вход записи которого и вход первого CD элемента задержки соединены с вторым .синхронизирующим входом устройства, J единичный выход первого триггера со является выходом ошибки устройства, О5 выход первого элемента задержки соединен с тактовым входом второго счетчика адреса, управляющий вход вьщачи схемы сравнения подключен к выходу четвертого элемента И, выходы первого счетчика адреса соединены ,с адресными входами второго блока памяти, выход пятого элемента И подключен к первому входу разрешения приема регистра выдачи и к входу останова генератора прямоугольньк им

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

Известно устройство для аппаратурной трансляции, выполненное на основе

взаимосвязанных регистра выдачи, блока памяти, регистров символа, элемента ИЛИ, шести элементов И, схемы сравнения, двух регистров адреса, дешифратора кода пробела, двух триггеров, генератора прямоугольных импульсов, четьфех элементов задержки и дешифратора. Аппаратурная реализация данного устройства является независимой от используемых языков. Настройка его на конкретные языки программирования осуществляется путем составления карты заполнения блока памяти на основе несложного преобразования таблиц соответствия символических и двоичных кодов входного и выходного языков с помощью графа lj Недостатками данного технического решения являются невозможность выявления недопустимых входных конструкций, а также невозможность выбора следующего символа конструкции входного языка в случае несовпадения сравниваемых символов. Наиболее близким по технической сущности к изобретению является устройство для аппаратурной трансляции, содержащее блок памяти, два регистра адреса, регистр вьщачи, схему сравнения, элемент ИЛИ, семь элементов И, четыре элемента задержки, три триггера, дешифратор кода пробела, генератор прямоугольных импульсов и блок записи, хранения и вы борки символов конструкции входного языка, выполненный в вцце группы регистров символа и дешифратора, подключенного своими входами и выходами .соответственно к адресным входам блока и к управляющим входам регистров символа, входы выбора приема вьщачи, информационные входы и инфор ма1щонные выходы которьк соответственно соединены с входом выбора, приема-вьщачи, информационными входами и информационными выходами блока записи, хранения и выборки символов конструкции входного языка, подключенного информационными выходами к первьм группам входов регистра вьщачи и схемы сравнения, вторые группы входов которых соединены с выходами блока памяти, подключенными также к входам первого и второго регистра адреса, выходы которого соединены с адресными входами блока памяти и входами первого элемента И, подключенного своим выходом к входу первог триггера, установочный вход которого соединен с установочными входами первого и второго регистров адреса и с выходом элемента ИЛИ, первый и второй входы элемента ИЛИ подключены соответственно к установочным входам первого и второго триггеров и к выходу второго элемента И, ниверсный выход второго триггера соединен с первым входом второго элем(ента первый вход второго триггера подключен к второму входу второго элемента и и к первому входу третьего элемента И, выход которого соединен со счетным входом первого регистра адреса, второй вход - с прямым выходом второго триггера и с входом выбора приема-вьщачи блока записи, хранения и выборки символов конструкции входного языка, информационные входы которого подключены к входам дешифратора кода пробела, выходом соединенного с вторым входом второго триггера и с первым входом генератора прямоугольных импульсов, выход которого подключен к входу считывания блока памяти, вход записи которого через первый элемент задержки соединен с первым счетным входом второго регистра адреса, вход приема второго регистра адреса подключен к выходу несовпадения схемы сравнения, управляющий вход и выход совпадения которой соединены соответственно с выходом четвертого элемента И и с вторым счетньм входом второго и первым входом приема первого регистра адреса, подключенного выходами и вторым входом приема соответственно к адресным входам блока записи, хранения, и выборки символов конструкции входного языка и к выходу пятого элемента И, входу приема с второй группы входов регистра выдачи и второму входу генератора прямоугольных импульсов, выход которого соединен через второй элемент задержки с входом третьего элемента задержки и с первыми входами четвертого и пятого элементов И, инверсный выход третьего триггера подключен к второму входу I четвертого элемента И, прямой выход к второму входу пятого элемента И и к первым В5содам шестого и седьмого элементов И, выход седьмого элемента И соединен с входом вьщачи регистра вьщачи и с первым входом третьего триггера, второй вход которого подключен к первому выходу условий блока памяти, второй выход условий которого соединен с вторым входом шестого элемента И, выход которого и третий вход соответственно подключе- . ны к входу приема с первой группы входов регистра вьщачи и к выходу третьего элемента задержки, соединенного также через четвертый элемент задержки с вторым входом седьмого элемента И fzl. 51 Однако известное устройство также не позволяет выбирать следуинций символ конструкции входного языка в случа несовпадения сравниваемых символов, в чем может возникнуть необходимость, если в анализируеных узлах содержатся символы, имешцне полный набор дво ичных эквивалентов (2k, где k - разрядность кодов) на выходном языке (например, номер регистра илп непосредственный операнд). Следовательно, устройство не позволяет изменять условие перехода в группе регистров символа. Это приводит к необходимости перебирать все возможные значения двоичных эквивалентов входной конструкции, в противном случае процесс трансляции не может быть про должен. При этом следует учесть, что перебор всех двоичных эквивалентов (в котором, как правило, нет смысла) односимвольного непосредственного операнда в случае восьмиразрядного регистра символа потребует не менее 256 ячеек памяти. Если подобных узлов в графе, например, четьфе, то необходимо более тысячи дополнительных ячеек памяти. Это приводит к нерациональному ее расходу, усложнению процесса написания и отладки карты памяти, процесса заполнения информацией запоминаюп го устройству как в случае постоянного, так и оперативного его исполнения. При этом следует иметь в виду, что увеличение необходимого объема блока памяти повышает вероятность появления ошибки при записи в него информации Кроме того, при составлении карты памяти по графу переход к следующей по порядку строке карты памяти удобно производить в одних случаях по несовпадению (например, при анализе символов узлов, имеющих неполный набор двоичных эквивалентов из числа всех возможных двоичных комбинаций при заданной разрядности), а в других случаях - по совпадению (при , последовательном анализе символов отдельных ветвей). Первое известное устройство обладает первой возможностью, но не обладает второй, второе известное устройство, наоборот, обладает второй возможностью из названных, но не обладает первой. Таким образом, рассмотренные устройства не обладают функцией изменения условия перехода в блоке 6 Памяти при организации процесса трансляции. Результатом этого является усложнение, процесса составления карты памяти и изменения ее при модификации языка программирования, его меньшая наглядность, что приводит к большему числу ошибок при построении карты, большим затратам времени на ее отладку, к большему объему необходимой памяти. Кроме того, в указанных устройствах для хранения кодового символа входных конструкций предназначен отдельный регистр символа. Такое исполнение является оправданным как правило лишь в случае; необходимости одновременного досту1::а к нескольким регистрам. В противном случае это приводит к излишним аппаратурным затратам и потреблению дополнительной энергии. Цель изобретения - расширение функциональных возможностей за счет обеспечения изменений условий перехода и упрощения процесса подготовки и редактирования данных, записываемых в память при модификации языков программирования. Поставленная цель достигается тем, что в устройство, содержащее первый блок памяти, дза счетчика адреса, регистр выдачи, схему сравнения, первый элемент ИЛИ, семь элементов И, четыре элемента задержки, три триггера, дешифратор кода пробела, генератор прямоугольных импульсов и второй блок памяти, подключенный информационными выходами к первым группам информационных входов регистра вьщачи и схемы сравнения, вторые группы информационных входов которых соединены с информационными выходами первого блока памяти, подключенными к информационным входам первого и второго счетчика адреса, выходы которого соединены с адресными входами первого блока памяти и с входами первого элемента И, подключенного выходом к. единичному входу первого триггера., установочный вход которого и установочные входы первого и второго счетчиков адреса соединены с выходом первого элемента ИЛИ, первьй вход первого элемента ИЛИ и установочные входы второго и третьего триггеров подключены к установочному входу устройства, выход второго элемента И соединен с вторым входом первого элемента ИЛИ, нулевой выход второго триггера соединен с первым входом второго элемента И, единичный вход второго триггера подключен к второму входу второго элемента И, к первому входу третьего элемента Ник первому синкронизир5Ш) щему входу устройства, выход третьего элемента И соединен с тактовым входом первого счетчика адреса, второй вход третьего элемента И соедине с единичным выходом второго триггера, группа входов транслируемого язы ка устройства соединена с информационными входами второго блока памяти и дешифратора кода пробела, выходом соединенного с единичным входом второго триггера и с входом пуска генератора прямоугольных импульсов, выход которого подключен, к входу считы вания первого блока памяти, вход записи которого и вход первого элемента задержки соединены с вторым синхронизирующим входом устройства, единичныйвыход первого триггера является выходом ошибки устройства, выход первого элемента задержки соединен с тактовым входом второго счетчика адреса, управляющий вход выдачи схемы сравнения подключен к ВЫХОДУ четвертого элемента И, выходы первого счетчика адреса соединены с адресными входами второго блока.памяти, выход пятого элемента И подклю чен к первому входу разрешения прием регистра вьщачи и к входу останова генератора прямоугольных импульсов, выход которого соединен через второй элемент задержки с входом третьего элемента задержки и с первыми входами четвертого и пятого элементов И, нулевой выход третьего триггера подключен к второму входу четвертого элемента И, единичный выход подключен к второму входу пятого элемента И и к первым входам шестого и седьмого элементов И, выход седьмо го элемента И соединен с входом выдачи регистра вьщачи и с первым единичным входом третьего триггера, второй единичный вход которого подключен к первому выходу условий первого блока памяти, второй выход усло вий которого соединен с вторым .входом шестого элемента И, выход и третий вход которого подключены соответственно к второму входу разрешения приема регистра выдачи и к выходу третьего элемента задержки, выход которого через четвертый элемент задержки соединен с вторьм входом седьмого элемента И, информационные входы первого блока памяти являются группой входов информации настройки устройства, выходы регистра выдачи являются выходами устройства, введены два переключателя, восьмой, девятый и десятый элементы И, второй и третий элементы ИЛИ, первый вход третьего элемента ИЖ подключен к выходу третьего элемента И, второй вход соединен с выходом первого элемента ИЛИ, третий вход соединен с выходом четвертого элемента И, четвертый вход подключен к выходу пятого элемента И, выход третьего элемента ИЛИ через пятьй элемент задержки соединен с первыми входами восьмого и девятого элементов И, вторые входы которых подключены соответственно к единичному и нулевому выходам второго триггера-, выходы восьмого и девятого элементов И подключены соответственно к управляющему входу записи и управляющему входу считьгоания второго блока памяти, третий выход условий первого блока памяти соединен с разрешающими входами первого и второго переключателей, выходы которых подключены соответственно к счетному входу и к входу разрешения приема второго счетчика адреса, выход несравнения схемы сравнения соединен ,с первыми информационными входами первого и второго переключателей и с первым входом десятого элемента И, выход сравнения схемы сравнения подключен к вторым информационным входам первого и второго переключателей и к первому входу второго элемента ИЛИ, выход которого соединен с входом разрешения приема первого счетчика адреса, четвертый выход условий первого блока памяти подклюён к второму входу десятого элемена И, выход которого соединеи с втоым входом второго элемента ИЖ, треий вход которого соединен с выходом ятого элемента И. На чертеже изображена схема предагаемого устройства. Схема устройства содержит блоки 1 и 2 памяти, счетчики 3 и 4 адреса, егистр 5 выдачи, схему 6 сравнения, переключатели 7 и 8, элементы 9,10, и 11 ШМ, элементы 12-21 И, элемент 22-26 задержки, дешифратор 27 кода про&ела, триггеры 28-30, генератор прямоугольных импульсов, вход 32 установки исходного состояния, первую 33 и вторую 34 группы информаци онных входов устройства, входы 35 и 36синхроимпульсов устройства, выхо 37индикации ошибки и группу 38 информационных выходов устройства. Входы 33 и 35, 34 и 36 могут, на пример, подключаться к стандартному инте }фейсу вычислительной машины типа 2К, к наборной клавиатуре на пульте управления устройства или к пишущей мгшинке типа Консул, вход 32 и выход 37 - соответственно к кнопке начальной установки и к свет вому индикатору на пульте управлени устройства, выходы 38 - к информаци онный входам внешнего для устройств блока памяти, хранящего двоичную программу на выходном языке. Перед началом работы в блок 1 памяти заносится информация, позволяющая установить взаимно-однозначное соответствие между кодами входного и выходного языков. Для зтого на основе анализа конструкций входного языка, представленных в символическом виде, строится граф, узлах которого находятся отдельные символы алфавита входного языка, а связи между узлами (ветви графа) указывают на символы, являющиеся соседними в символическом коде конструкции. В конечных узлах графа (листьях) помещается двоичный код выходного языка, соответствующий од ной из конструкций входного языка. Узел, имеювц1й исходявц1е ветви, является порождающим, более одной исходящей ветви - ветвящимся. По графу составляется карта заполнения блока 1 памяти. С целью упрощения и упорядочение процесса решения данной задачи для рассматриваемой модификации устройства трансляции необходимо руководствоваться следзпсядей методикой. Методика настройки аппаратурного транслятора на выбранный язык программирования : 1. Если построение графа для выбранного языка программирования не проводилось, то идти к 2. Иначе тре буется достройка дополнительно введенными конструкциями идти к 2,9. 2. Строится граф для выбранного языка программирования следующим образом. 2.-1. Строится начальный узел графа - корень. 2.2.Выбирается произвольная символическая конструкция входного языка. 2.3.Выбирается первый символ конструкции. 2.4.Граф достраивается узлом, который соединяется ветвью с последним из построенных узлов и имеет на единицу больший ранг. Идти к 2.6. 2.5. Производится достройка графа узлом, который соединяется ветвью с породившими последний из рассмотренных узлов и имеет тот же , ранг, что и 1зассмотренный. Узлы, порожденные ветвящимся, должны располагаться в следующем порядке. Левая группа - узлы, символы которых имеют один двоичнБЙ эквивалент. Достраиваемый узел, относящийся к данной группе,должен быть крайним правым в группе. Средняя группа - узлы, символы которых имеют различающиеся неполные наборы двоичных эквивалентов Из числа допустимых двоичных кодов конструкции выходного языка при заданной ее разрядности k (меньше чем 2k). В данной группе узлы располагаются в порядке возрастания количества двоичных эквивалентов слеванаправо. Правая группа содержит узел, символ которого имеет полный набор двоичных эквивалентов (равный 2k). 2.6.Если построенный узел не является листом, так как ему не соответствует пробел, то он помечается выбранным символом и выбирается следующий символ. Одти к 2.4. Иначе идти к 2.7. 2.7.В лист записывается двоичный код конструкции выходного языка, являющийся двоичным эквивалентом рассмотренной конструкции входного языка. 2.8.Если рассмотрены все к.онструкции входного языка, то идти к 3, иначе идти к 2.9. 2.9.Выбирается следующая конструкция входного языка. 2.10.Выбирается первый символ констрзпсции. 2.11.Выбирается узел нулевого ранга, если таких узлов несколько, то - крайний левый. П 2.12.Если символ конструкции со падает с символом выбранного узла то идти к 2.13. Иначе идти к 2.15. 2.13.Выбирается следующий симво конструкции. 2.14.Выбирается крайний левый узел из порожденных рассмотренным узлом, являющийся листом. Идти к 2.12. Иначе идти к 2.5. 2.15.Если рассмотренный узел им ет справа узлы, порожденные тем же узлом, что и он сам, то выбирается соседний справа. Идти к 2.12. Иначе идти к 2.5. 3.Если предполагается организовать процесс трансляции с проведени ем частичного контроля входных конструкций на наличие недопустимых символических обозначений, то идти к 7. Если же необходик полный контроль, идти к 4. Для предварительной оценки объем необходимой памяти и времени трансляции по графу можно воспользовать ся формулами, приведенными в конце методики. 4.Если основная численная разметка графа не проводилась,. то идти к 5. В противном случае (проводилась достройка графа) идти к 4о1. 4.1.Выбирается узел из имеющих порожденные непомеченные узлы, значение Н1 основной разметки которого наименьшее. 4.2.Переменной М приписывается значение основной разметки листка, находящегося в конце маршрута, начинающегося узлом, порожденным узлом HI и являющимся соседним с край ним левым из непомеченных, порожден ных тем же узлом. 4.3.Уничтожается основная разметка всех узлов, величины HI которых больше М. 4.4.Выбирается крайний правый из порожденных узлом HI, имеющий основную разметку. Значение HI полагается равным его основной разметке. Идти к 5.7. 5.Проводится основная разметка графа. 5.1 Узел нулевого ранга (если их несколько, то крайний левый) помеча ется числом (корень дерева нулем).- . 5.2. Первый узел, символ которог не имеет полного набора двоичных эквивалентов, относящийся к крайней 612 левой ветви, порожденной последним помеченным узлом, помечается числом . 5.3.Если помеченный узел не является листом, то идти к 5.2. Иначе запоминается значение HI ().Идти к 5.4. 5.4.Если узел Н1 является ближайшим из помеченных к породившему эту ветвь, то выбирается узел . Идти к 5.4. Иначе идти к 5.5. 5.5.Если ветвь узла HI является крайней правой среди порожденных общим узлом, то выбирается породивший ветвь узел (если он не помечен, то ближайший из помеченных в направлении к корню) и HI полагается равным его основной разметке. Идти к 5.5. Иначе идти к 5.7. 5.6 Если выбранный узел помечен числом , то идти к 6. Иначе идти к 5.4. 5.7. Ближайший к породившему узел HI из соседней справа ветви, порожденной тем же узлом, помечается числом . Идти к 5.3. 6. Составляется карта памяти для случая сплошного контроля входных конструкций на наличие недопустимых символических обозначений. 6.1.Номер А строки карты памяти (т.е. адрес соответствующей ячейки памяти) основного блока памяти принимается равным нулю (). 6.2.Выбирается узел, помеченный номером . 6.3.Если символ выбранного узла имеет К двоичных эквивалентов, то в первые поля строк А...А+К-1 последовательно заносятся все К двоичных эквивалентов, если символ - лист, то - код пробела. 6.4. Если символ узла HI имеет один двоичный эквивалент, то идти к 6.5. Иначе во вторые поля строк А...А+К-2 заносится код числа А+К. При этом признаки перехода во всех строках (крайний правый разряд поля) принимаются равными нулю - переход по совпадению. Заполнение строки А+ +К-1 описано в следующем пункте. Идти к 6.5. 6.5 Если узел HI порожден ветвящимся узлом и не является крайним правым среди порожденных этим узлом, то во второе поле заносится двоичный код величины д ,Н1пм где л, п - индексы, обозначающие принадлежность переменны соответственно узлу HI (левому) и соседнему спр ва от него (Ад - адрес первого двоичного эквивалента левого узла) количество двоичных экви валентов к-го узла; количество узлов.от Н1ц Ч1д,.1 и до Н1. включительно являкщихся листьями. В противном случае во второе пол заносится код 1... 1. Признак перехода устанавливается равным единице . 6.6. В том случае, если выбранны узел является листом, заполнение третьего поля произвольно (однако младший разряд должен быть равен нулю), иначе в него заносится (для всех строк от А до А+К-1 включитель но, где К - число двоичных эквивале тов узла) двоичное значение ранга узла Н1+1, если HI не порожден ветв щимся узлом или порожден, но не имеет соседнего справа узла, порожденного тем же ветвящимся и имеющего полный набор двоичных эквивалентов. При этом крайний правый разряд поля (признак перехода в блоке памя ти символов конструкции входного языка) устанавливается- равным нулю переход по совпадению. В противном случае заполнение строк А...А+К-2 аналогично, а в третье поле строки А+К-1 записьгоается код ранга ближай шего помеченного узла к породившему соседний справа от узла HI в направ лении от корня дерева, признак перехода принимается равным единице переход по несовпадению. 6.7.В четвертое поле записьшает ся признак типа формата заполненной строки - ноль. 6.8.Если узел HI не лист, то вы бирается строка (К - число двоичных эквивалентов узла HI) и узел . Идти к 6.3. Иначе идти к 6,9. 6.9.В первое поле строки заносится выбранный двоичный код конструкции выходного языка. 6.10.Второе поле предназначено для признака вставки: если в код 61 конструкции выходного языка не требуется вставлять код какого-либо символа конструкции входного языка, то в .поле записывается нулевой код, иначе - единичный. 6.11.Если признак вставки равен нулю, то в третье поле записывается произвольный код, иначе в него заносится двоичный код ранга узла, в котором находится вставляемый символ. 6.12.В четвертое поле записывается признак формата заполненной строCH - 1единица. 6.13. Если при составлении карты использованы не все узлы графа ( ° выбирается узел + 1 и строка .1. Р1дти к 6.3. Иначе идти к 10. 7. Если вспомогательная численная разметка не проводилась, то идти к 8. Иначе (проводилась достройка графа) идти к 7.1i 7.1. Выбирается ветвящийся узел из имеющих порожденные неразмеченные узлы, для которого наименьшим является значение разметки Н2 среди узлов двух типов: крайнего правого из размеченных порожденньк им и ближайшего верхнего в направлении от упомянутого ветвящегося узлак корню дерева (если нет порояоденных помеченных узлов). 7.2.Уничтожается нспомогательная численная разметка всех узлов от Н2+1 до Н2ддд р включительно. 7.3.В первом случае идти к 8.5. Иначе выбрать узел Н2 и идти к 8.2. 8. Выполняется вспомогательная численная разметка графа, 8.1. Узел нулевого ранга (если их несколько, то крайний левый) помечается числом (.корень дерева - нулем). 8.2. Выбирается крайний левый узел из порожденных выбранным ранее, 8.3.Если узел, породивший выбранный, является ветвящимся, то выбранньй узел помечается числом (-1. 8.4.Если выбранньй узел не является листом, то идти к 8.2. Иначе идти к 8.5. 8.5.Выбирается узел Н2, Запоминается значение его разметки (). 8.6.Если выбранный узел имеет справа от себя непомеч еиные узлы, порожденные тем же узлом, что и он 5 сам, то выбирается крайний левый и них (если символ этого узла имеет полньй набор двоичных эквивалентов то выбирается первый из имеющих од или неполный набор двоичных эквива лентов в направлении от корня) и помечается номером . Идти к 8.4. Иначе идти к 8.7. 8.7. Выбирается узел, ближайший от Н2 в направлении к корню, имеющий справа от себя непомеченные уз лы, порожденные тем же, что и он с Ццти к 8.6. Если таких узлов.нет, то идти к 9. 9. Строится карта памяти для сл чая организации процесса трансляци с частичным контролем входных КОНСТРУКЦИЙ на наличие недопустимых с волических обозначений. 9.1.Номер строки карты памяти принимается равным нулю (). 9.2.Выбирается узел, помеченный номером . 9.3.В первое поле строки А запи сывается код символа узла Н2, если узел Н2 является листом, то - код пробела. Если символ имеет К двоич ных эквивалентов, то в первые поля строк А...А+К-1 последовательно заносятся все К двоичных эквивалентов 9.4.Если символ узла Н2 имеет один двоичный эквивалент, то идти к 9.5. Иначе во вторые поля строк А...А+К-2 заносится код числа А+К. При этом признаки перехода во всех строках принимаются равными нулю переход по совпадению. Заполнение строки А+К-1 описано в следующем пункте. Идти к 9.5. 9.5.Если выбранньй узел не имеет справа от себя узлов, порожденных тем же ветвящимся, что и выбран ный, то во второе поле заносится код 1... 1. Признак перехода устанав ливается равным единице. Иначе в не го записывается двоичный код числа, определяемого по формуле 42rt,H2«.i } где л, п - индексы, обозначающие принадлежность переменны соответственно левому и правому узлу из рассматриваемой пары узлов (Ад адрес первого двоичнргоэквивалента левого узла) 6 .. - количество двоичных эквивалентов к-го узла , количество листьев, ,МСп-Г положенных в конце всех маршрутов, проходящих через узлы Н2д...Н2 J,., , но. не проходящих через узлы со значениями разметки, большими Н2пи9.6.Заполнение третьего поля строк А...А+К-1 произвольно, если ранг узла Н2+1 не превьш1ает ранга узла Н2 (однако младший разряд должен быть равен нулю), иначе в него записывается двоичный код ранга узла Н2+1. Причем признак перехода принимается равным нулю, если узел Н2+1 приходится в направлении от корня, и единице, в противном случае. 9.7.Четвертое поле предназначено для записи .признака типа формата заполнения строки - О. 9.8.Если ранг узла Н2+1 больше ранга узла Н2, то выбирается строка (к - количество двоичных эквивалентов символа узла Н2) и узел . Идти к 9.3. Иначе идти к 9.8. 9.9.В первое поле строки заносится выбранный двоичный код конструкции выходного языка. 9.10.Второе поле предназначено для признака ставки: если в код конструкции выходного языка не требуется вставлять код какого-либо символа конструкции входного языка, то в поле записывается нулевой код, иначе - единичный. 9.11.Если.признак вставки равен нулю, то в третье поле записывается произвольный код, иначе в него записывается двоичный код ранга узла, в котором находится вставляемый символ. 9.12.В четвертое поле записьгоа- ется признак формата заполненной строки - 1. 9.13.Если при составлении карты использованы на все узлы графа (Н2 ,, то выбирается узел и строка . Идти к 9.3. Иначе идти к 10. 10. Конец. Оценка объема занимаемой памяти и времени трансляции по графу может быть проведена с помощью формул:ц,Ч Т.,с СНксма,с-И+ (Ку,+К /2) .T«j,Tj IZ т.о. где Е объем необходимой памяти в ячейках основного блока памяти мо максимальное значение разметки графа; 1C д.- колифество дзвоичных элементов символа i -го узла§ Кд - количество листьев графа; - время трансляции конструкТур - длительность такта устройст ва (генератора импульсов) Ни„(Н.,„ значение разметки узлов гра (С Смакс .ера, в которых записаны символы рассматриваемой конструкции (максимальное значение)J Кцд- количество узлов, располо женных левее узлов, имеющих разметки Н, и имеющих тот же порождающий узел Т...,.-- среднее время трансляции конструкции при разных частотах использования отдель- пьЕХ конструкций, о - частоты использования отдельных конструкций время трансляции программы М количество конструкций в программе; Т длительность такта ввода символа в утсройство К - количество символов в коде ой конструкции входного язьша. Указанные . имеют одинаковый вид для обо-их вариантов составле ния карты памяти. При выборе конкрет ного варианта переменная Н заменяется на соответствующую переменную HI или Н2, Устройство работает следующим образом. При включении устройства на вход 32 подается сигнаи, устанавливающий триггеры 28 и 29 в нулевое состояние и поступающий через элемент 10 ШШ для установки в ноль счетчика 3 адре са Затем производится запись инфор- мации в блок 1 памяти. На информационные входы 33 поступает первое слово для записи в нулевую ячейку па мяти, адрес которой установлен в счетчике 3 адреса. Сопровождающий данное слово синхроимпульс по входу 35 поступает на вход элемента 22 задержки и на вход управления записью в блок 1 памяти,, в результате чего происходит прием слова в соответствующую ячейку памяти. После этого на счетном входе счетчика 3 адреса появляется сигнал, прошедший через элемент 22 задержки, и значение адреса увеличивается на единицу. В следующем такте поступает очередное слово по входам 33 и сопровождающий его синхроимпульс по входу 35. Запись данного слова в блок 1 памяти и увеличение значения адреса в счетчике 3 адреса выполняется та:к же, как и в предьщз ем такте. Этот процесс продолжается до заполнения блока 1 памяти, после чего устройство считается подготовленным к работе. Если блок 1 памяти выполнен не в виде программируемого, а в виде постоянного запоминаюш;его устройства, то подготовка устройства к работе заключается в установке платы из некоторого набора плат, каждая из которых ориентирована на определенную пару входного и выходного языков, и в подаче сигнала начальной установки на вход 32 для установки в ноль триггеров 28 и 30 и счетчика 3 адреса аналогично указанному. В режиме записи конструкции входного языка в блок 2 памяти с входов 34 последовательно друг за другом поступают символы конструкции входного языка, а по входу 36 - сопровож-: дающие их синхроимпульсы. По первому синхроимпульсу происходит запись символа в нулевую ячейку блока 2 памяти следующим образом. Так как на нулевом выходе триггера 28 единица, то первый синхроимпульс через элемент 15 И и элемент 10 ШШ проходит для установки в ноль регистров 3 и 4 адреса и триггера 30. Этот же синхроимпульс поступает на единичный вход триггера 28, К моменту появления импульса на одном из входов элемента 13 И, прошедшего с элемента 10 ИЛИ через элементы 11 ИЛИ и 26 задержки, триггер 28 переключается в единичное состояние, и на выходе элемента 13 И появляет- , ся сигнал записи в блок 2 памяти, К

19

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

Второй синхроимпульс с входа 36 проходит уже через элемент 14 И, та как триггер 28 находится в единичном состоянии,поступает на счетный вход счетчика 4, увеличивая адрес на единицу, и через элементы 11 ИЛИ 26 задержки и 13 И - на вход записи блока 2 памяти. В результате -этого производится запись кода очередного символа в следующую ячейку блока 2 памяти. Все следующие символы обра батьшаются аналогичным образом до тех пор, пока не поступит код пробела.

По коду пробела на выходе дешифратора 27 появляется сигнал, переводящий триггер 28 в нулевое состояние и производящий запуск генератора 31 прямоугольных импульсов. Синхроимпульс с входа 36, поступивший с символом Пробел, проходит через элемент 15 И и 10 ИЛИ и устанавливает в ноль счетчик 4 адреса. На этом режим приема конструкции

входного языка заканчивается. 1

Б режиме трансляции по сигналу,

прошедшему с элемента 10 ИЛИ через элементы It ИЛИ, 26 задержки и 12 И на вход считьшания блока 2 памяти, с его выхода на схему 6 сравнения вьщается код символа. Кроме того, по сигналу с генератора 31 прямоугольных импульсов считьшается информация из блока 1 памяти. Через элемент 23 задержки и элемент 17 И сигнал с генератора поступает на управляющий вход схемы 6 сравнения, в результате чего сравниваются коды с выходом блоков 1 и 2 памяти. При совпадении символов сигнал появляется на соответствующем выходе, схемы сравнения и в зависимости от значения признака перехода в блоке 1 памяти проходит либо через переключатель 7 (если признак равен единице) на счетный вход счетчика 3 адреса (при этом адрес увеличивается на единицу), либо через переключатель 8 (признак равен нулю) на вход приема счетчика адреса (при этом в него принимается адрес перехода с выходов блока 1 памяти), Кроме того, сигнал совпадения проходит

3620

через элемент 9 ИЛИ на вход приема счетчика 4 адреса и в него принимается адрес следующего сигнала с выходов блока 1 памяти,

При несовпадении символов сигнал с соответствующего выхода схемы 6 сравнения проходит через переключатели 7 и 8 уже при других значениях признака перехода в блоке 1

памяти. Если признак перехода в блоке 2 памяти равен единице, то сигнал несовпадения проходит также через элементы 16 И и 9 ИЛИ на вход приема регистра 4 адреса и в него

принимается адрес следующего символа. В противном случае содержимое счетчика 4 адреса не меняется.

Сигнал, появляющийся на выходе элемента 17 И, проходит также через

элементы 11 ИЛИ, 26 задержки и 12 И, в результате чего из блока 2 памяти считьюается код символа.

По следующему сигналу с выхода генератора 31 прямоугольных импульсов указанные действия, связанные с выдачей из блоков 1 и 2 памяти, повторяются.

Режим трансляции продолжается до

тех пор, пока при считывании информации из блока 1 памяти на выходе условий, соединенном с входом триггера 29 (четвертое поле ячейки), не появится единица, переводящая триггер в единичное состояние. Высокий уровень напряжения с единичного выхода триггера 29 открывает стробирующие входы элементов 17-20 И, В результате этого сигнал с выхода эле-

мента 23 задержки проходит через

элемент 18 И на вход приема с второй группы входов регистра 5 выдачи и двоичный крд конструкции выходного языка принимается в регистр вьщачи,

Этот же сигнал приводит к приему

в счетчик 4 адреса номера вставляемого символа, код которого выдается с выходов блока 2 памяти на группу входов регистра 5 если на выходе

условий блока 1 памяти, соединенном с входом элемента 19 И (признак вставки - второе поле ячейки памяти), единица, то сигнал с выхода элемента 24 задержки проходит на вход приема

регистра 5 выдачи и код вставля-емого символа принимается в регистр вьщачи. Затем сигнал с выхода.элемента 25 задержки проходит через элемент 20 И, 211 на другом входе которого йрисутствует единица с вьвсода триггера 29, на управляемый вход регистра 5 вьщачи. На этом трансляция конструкции входного языка закончена, и устройство может приступать к трансляции следут нщей. Если в процессе трансляции с выхо счетчика 4 адреса появится код 1. . 1 то элемент 21 И переключается в единичное состояние и на выходе 37 индикации ошибки появляется сигнал, говорящий о том, что введенная в блок 2 памяти конструкция является недопустимой и результат трансляции ошибочный. Изобретение в отличие от известного устройства позволяет существен6но упростить и ускорить процесс разработки трансляторов для языков программирования, отдельные символы конструкций которых (непосредственный операнд, номер регистра, модификатор и до. ) имеют более одного двоичного эквивалента, обладает дополнительной возможностью изменения условий перехода в обоих блоках памяти при построении алгоритмов трансляции. Это приводит к более рациональному расходу памяти, объем которой может быть уменьшен в отдельных случаях на порядок, сокращению числа допускаемых ошибок как при построении карты памяти, так и при занесении ее в блок памяти;