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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (19) (11) 4Р1) G 06 F 15/38

/ ф

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ с 1

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

А0 ДЕЛА (ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3689256/24-24 (22) .13.0!.84 (46) 30.06.85. Вюл. N - 24 (72) С.С.Ефимов, В,И.Потапов

И В.Ф.Нестерук (71) Омский политехнический институт (53). 681.325(088.8) (563 1. Авторское свидетельство СССР

9 .993272, кл. G 06 F. 15/38, 1981.

2. Авторское свидетельство СССР по заявке У 3500457/24, кл. G 06 Г 15/38, 1983 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ АППАРАТУРНОЙ

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

И, подключенного выходом к единичному входу первого триггера, устано-вочный вход которого и установочные входы первого и второго счетчиков адреса соединены с выходом первого элемента ИЛИ, первый вход первого элемента ИЛИ и установочные входы второго и третьего триггеров подключены к установочному входу устройства, выход второго элемента И соединен с вторым входом первого элемента ИЛИ, нулевой выход второго триггера соединен с первым входом второго элемента И, единичный вход второго триггера подключен к второму входу второго элемента И, к первому входу третьего элемента И и к первому синхронизирующему входу устройства, выход третьего элемента

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

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

36 элемента ИЛИ подключен к выходу третьего элемента И, второй вход соединен с выходом первого элемента

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

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

Известно устройство для аппаратур-,1О ной трансляции, выполненное на основа взаимосвязанных регистра выдачи, бло-, ка памяти, регистров символа, элемента ИЛИ, шести элементов И, схемы сравнения, двух регистров адреса, дешифратора кода пробела, двух триггеров, генератора прямоугольных импульсов, четырех элементов задержки и дешифратора. Аппаратурная реализация данного устройства является независимой от используемых языков. Настройка его на конкретные языки проз 1164 граммирования осуществляется путем составления карты заполнения блока памяти на основе несложного преобразования таблиц соответствия символических и дВОичных КОДОВ ВхОднОГО и выходного языков о помощью говФв (1) .

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

Наиболее близким по технической сущности к изобретению является

15 устройство для аппаратурной трансляции, содержащее блок памяти, два регистра адреса, регистр выдачи, схему сравнения, элемент ИЛИ, семь элементов И, четыре элемента задержки, три триггера, дешифратор кода пробела, генератор прямоугольных импульсов и блок записи, хранения и выборки символов конструкции входного языка, выполненный в виде группы регистров символа и дешифратора, подключенного своими входами и выходами .соответственно к адресным входам блока и к управляющим входам регистров символа, входы выбора приема-ЗО выдачи, информационные входы и информационные выходы которых соответственно соединены с входом выбора, приема»выдачи, информационными входами и информационными выходами блока Зз записи, хранения и выборки символов конструкции входного языка, подключенного информационными выходами к первым группам входов регистра вьдачи и схемы сравнения, вторые группы 40 входов которых соединены с выходами блока памяти, подключенными также к входам первого и второго регистра адреса, выходы которого соединены с адресными входами блока памяти и 4> входами первого элемента И, подключенного своим выходом к входу первого триггера, установочный вход которого соединен с установочными входами первого и второго регистров адреса 50 и с выходом элемента ИЛИ, первый и второй входы элемента ИЛИ подключены соответственно к установочным входам первого и второго триггеров и к выходу второго элемента И, ин- 55 версный выход второго триггера соединен с первым входом второго элемента И, первый вход второго триггера подклю736 4 чен к второму входу второго элемента И и к первому входу третьего элемента И, выход которого соединен со счетным входом первого регистра адреса, второй вход — с прямым выходом второго триггера и с входом выбора приема-вьдачн блока записи, хранения и выборки символов конструкции входного языка, информационные входы которого подключены к входам дешифратора кода пробела, выходом соединенного с вторым входом второго триггера и с первым входом генератора прямоугольных импульсов, выход которого подключен к входу считывания блока памяти, вход записи которого через первый элемент задержки соединен с первым счетным входом второго регистра адреса, вход приема второго регистра адреса подключен к выходу несовпадения схемы сравнения, управляющий вход и выход совпадения .которой соединены соответственно с выходом четвертого элемента И н с вторым счетным входом второго и первым входом приема первого регистра адреса, подключенного выходами и вторым входом приема соответственно к адресным входам блока записи, хранения.H выборки символов конструкции входного языка и к выходу пятого элемента И, входу приема с второй группы входов регистра вьдачи н второму входу генератора прямоугольных импульсов, выход которого соединен через второй элемент задержки с входом третьего элемента задержки и с первыми входами четвертого и пятого элементов И, инверсный выход третьего триггера подключен к второму входу

I четвертого элемента И, прямой выход— к второму входу пятого элемента И и к первым входам шестого и седьмого элементов И, выход седьмого элемента

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

5 11647

Однако известное устройство также не позволяет выбирать следующий символ конструкции входного языка в случае несовпадения сравниваемых символов, в чем может возникнуть необходимость, 5 если в анализируемых узлах содержатся символы, имеющие полный набор двоичных эквивалентов (2k, где k — разрядность кодов) на выходном языке (например, номер регистра или непосредственный операнд). Следовательно, устройство не позволяет изменять условие перехода в группе регистров символа. Это приводит к необходимости перебирать все возможные 5 значения двоичных эквивалентов входной конструкции, в противном случае процесс трансляции не может быть продолжен. При этом следует учесть, что перебор всех двоичных эквивалентов 20 (в котором, как правило, нет смысла) односимвольного непосредственного операнда в случае восьмиразрядного регистра символа потребует не менее

256 ячеек памяти. Если подобных узлов в графе, например, четыре, то необходимо более тысячи дополнительных ячеек памяти. Это приводит к нерациональному ее расходу, усложнению процесса написания и отладки 30 карты памяти, процесса заполнения информацией запоминающего устройства как в случае постоянного, так и оперативного его исполнения. При этом следует иметь в виду, что увеличение необходимого объема блока памяти повышает вероятность появления ошибки при записи в него информации.

Кроме того, рн составлении карты памяти по графу переход к следующей 40 по порядку строке карты памяти удобно производить в одних случаях по несовпадению (например, при анализе символов узлов, имеющих неполный набор двоичных эквивалентов из числа всех возможных двоичных комбинаций при заданной разрядности), а в других случаях — по совпадению (при последовательном анализе символов отдельных ветвей). Первое известное устройство обладает первой возможностью, но не обладает второй, второе известное устройство, наоборот, обладает второй возможностью из названных, но не обладает первой.

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

Кроме того, в указанных устройствах для хранения кодового символа входных конструкций предназначен отдельный регистр символа. Такое исполнение является оправданным как правило лишь в случае необходимости одновременного доступа к нескольким регистрам. В противнсм случае это приводит к излишним аппаратурным затратам и потреблению дополнительной энергии.

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

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

ИЛИ, первый вход первого элемента

ИЛИ и установочные входы второго н третьего триггеров подключены к установочному входу устройства, выход второго элемента И соецинен с вторым

1164736 8 входом первого элемента ИЛИ, нулевой ходу третьего элемента задержки, выход второго триггера соединен с выход которого через четвертый эле- первым входом второго элемента И, мент задержки соединен с вторым вхоединичный вход второго триггера под- дом седьмого элемента И инйормаЭ ключен к второму входу второго эле- 5 ционные входы первого блока памяти мента И, к первому входу третьего являются группой входов информации элемента И и к первому синхронизирую- настройки устройства, выходы регистщему входу устройства, выход третье- ра выдачи являются выходами устройго элемента И соединен с тактовым ства, введены два переключателя, входом первого счетчика адреса, вто- 10 восьмой, девятый и десятый элементы рой вход третьего элемента И соединен И, второй и третий элементы ИЛИ, с единичным выходом второго тригге- первый вход третьего элемента ИЛИ ра, группа входов транслируемого язы- подключен к выходу третьего элемента ка устройства соединена с информаци- И, второй вход соединен с выходом онными входами второго блока памяти f5 первого элемента ИЛИ, третий вход сои дешифратора кода пробела, выходом единен с выходом четвертого элеменсоединенного с единичным входом вто- та И, четвертый вход подключен к рого триггера и с входом пуска гене- выходу пятого элемента И, выход ратора прямоугольных импульсов, вы-. третьего элемента ИЛИ через пятый ход которого подключен, к входу считы- 20 элемент задержки соединен с первывания первого блока памяти, вход за- ми входами восьмого и девятого элеписи которого и вход первого эле- ментов И, вторые входы которых подмента задержки соединены с вторым ключены соответственно к единичносинхронизирующим входом устройства, му и нулевому выходам второго триггеединичный выход первого триггера яв- 25 ра, выходы восьмого и девятого элеляется выходом ошибки устройства, ментов И подключены соответственно выход первого элемента задержки со- к управляющему входу записи и управединен с тактовым входом второго ляющему входу считывания второго блосчетчика адреса, управляющий вход ка памяти, третий выход условий выдачи схемы сравнения подключен к З0 первого блока памяти соединен с развыходу четвертого элемента И, выходы Решающими входами первого и второго первого счетчика адреса соединены с переключателей, выходы которых подадресными входами второго блока. па- ключены соответственно к счетному мяти, выход пятого элемента И подклю- входу и к входу разрешения приема чен к первому входу разрешения приема- второго счетчика адреса, выход не"5 регистра выдачи и к входу останова сравнения схемы сравнения соединен генератора прямоугольных импульсов, с первыми информационными входами выход которого соединен через вто- первого и второго переключателей рой элемент задержки с входом тре- н с первым входом десятого элемента тьего элемента задержки и с первыми 40 w выход сРавнения схемы сравнения входами четвертого и пятого элемен- подключен к вторым информационным тов И, нулевой выход третьего триг- входам первого и второго переключагера подключен к второму входу чет- телей и к первому входу второго элевертого элемента И, единичный выход ента ИЛИ выход которого соединен подключен к второму входу пятого 45 входом Разрешения приема первого элемента И и к первым входам шестого счетчика адреса, четвертый выход и седьмого элементов И, выход седьмо- У ловий пеРвого блока памяти подклюго элемента И соединен с входом вычен к вт второму входу десятого элемен. дачи регистра выдачи и с первым та И вых выход которого соединен с втоединичным входом третьего триггера 50 ходом второго элемента ИЛИ, тРеЭ тий вхо второй единичн и вход которого под- ий вход которого соединен с выходом ключен к первому в„„оду условий пер- ПЯтого элемента И. вого блока памяти, второй выход усло- На чертеже изображена схема предвий которого соединен с вторым лагаемого устройства. ,входом шестого элемента И, выход и 55 Схема устройства содержит блоки третий вход которого подключены со- 1 и 2 памяти, счетчики 3 и 4 адреса, ответственно к второму входу разре- регистр 5 выдачи, схему 6 сравнения, шения приема регистра выдачи и к вы- переключатели 7 и 8, элементы 9, 10, 9

1164 н 11 ИДИ, элементы 12-21 И, элементы

22-26 задержки, дешифратор 27 кода пробела, триггеры 28-30, генератор 31 прямоугольных импульсов, вход 32 установки исходного состояния, пер- 5 вую 33 и вторую 34 группы информационных входов устройства, входы 35 и

36 синхроимпульсов устройства, выход

37 индикации ошибки и группу 38 информационных выходов устройства.

Входы 33 и 35, 34 и 36 могут, например, подключаться к стандартному интерфейсу вычислительной машины типа 2К, к наборной клавиатуре на пульте управления устройства нли к пишущей машинке типа "Консул", вход

32 и выход 37 — соответственно к кнопке начальной установки и к световому индикатору на пульте управления устройства, выходы 38 — к информаци- 20 онным входам внешнего для устройства блока памяти, хранящего двоичную программу на выхОдном языке.

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

Узел, имеющий исходящие ветви, является порождающим, более одной исходящей ветви — ветвящимся. По графу составляется карта заполнения блока 1 памяти. 45

С целью упрощения и упорядочение процесса решения данной задачи для рассматриваемой модификации устройства трансляции необходимо руководствоваться следующей методикой. 50

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

1. Если построение графа для выбранного языка программирования не Ы проводилось, то идти к 2. Иначе требуется достройка дополнительно введенньии конструкциями идти к 2.9.

736 10

2. Строится граф для выбранного языка программирования следующим образом.

2.1. Строится начальный узел графа — корень.

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

2.3. Выбирается первый символ конструкции.

2.4. Граф достраивается узлом, который соединяется ветвью с последним из построенных узлов и имеет на единицу больший ранг. Идти к 2.6, 2.5. Производится достройка графа узлом, который соедйняется ветвью с породившими последний из рассмотренных узлов и имеет тот же ранг, что н рассмотренный. Узлы, порожденные ветвящимся, должны располагаться в следующем порядке. Левая группа — узлы, символы которых имеют один двоичный эквивалент. Достраиваемый узел, относящийся к данной группе, должен быть крайним правым в группе. Средняя группа — узлы,. символы которых имеют различающиеся неполные наборы двоичных эквивалентов из числа допустимых двоичных кодов конструкции выходного языка при заданной ее разрядности k (меньше еМ 2i<). В данной группе узлы располагаются в порядке возрастания количества двоичных эквивалентов слеванаправо. Правая группа содержит узел, символ которого имеет полный набор двоичных эквиваленто:в (равный 2k).

2,6. Если построенный узел не является листом, так как ему не соответствует пробел, то он помечается выбранным символом и выбирается следующий символ. Одти к 2.4. Иначе идти к 2.7.

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

2,8. Если рассмотрены все конструкции входного языка, то идти к 3, иначе идти к 2. 9.

2.9. Выбирается следующая конструкция входного языка.

2.10. Выбирается первый символ конструкции.

2.11. Выбирается узел нулевого ранга, если таких узлов несколько, . то — крайний левый.

1!64736

2. 12. Если символ конструкции совпадает с символом выбранного узла то идти к 2.13. Иначе идти к 2.15.

2.13. Выбирается следующий символ конструкции. 5

2.14. Выбирается крайний левый узел из порожденных рассмотренным узлом, являющийся листом. Идти к

2.12. Иначе идти к 2.5.

2.15. Если рассмотренный узел име-10 ет справа узлы, порожденные тем же узлом, что и он сам, то выбирается соседний справа. Идти к 2.12. Иначе идти к 2.5.

3. Если предполагается организо- 15 вать процесс трансляции с проведением частичного контроля входных конструкций на наличие недопустимых символических обозначений, то идти к 7. Если же необходим полный кон- 20 троль, идти к 4.

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

4. Если основная численная разметка графа не проводилась, то идти к 5. В противном случае (проводилась достройка графа) идти к 4.1. 50

4.1. Выбирается узел из имеющих порожденные непомеченные узлы, значение Н1 основной разметки которого наименьшее.

4.2. Переменной M приписывается

35 значение основной разметки листка, находящегося в конце маршрута, начинающегося узлом, порожденным узлом Н1 и являющимся соседним с крайним левым из непомеченных, порожден- 40 иых тем же узлом.

4.3. Уничтожается основная разметка всех узлов, величины Н1 которых больше N.

4.4. Выбирается крайний правый 45 из порожденных узлом Н1, имеющий основную разметку. Значение Н1 полагается равным его основной разметке. Идти к 5.7.

5. Проводится основная разметка графа.

5.1 Узел нулевого ранга (если их несколько, то крайний левый) помечается числом Н1=1 (корень дерева— нулем).

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

Н1=Н1+1.

5.3, Если помеченный узел не является листом, то идти к 5.2. Иначе запоминается значение Н1 (Н=Н1)..

Идти к 5.4.

5.4. Если узел Н1 является ближайшим из помеченных к породившему эту ветвь, то выбирается узел Н1=Н1-1.

Идти к 5.4. Иначе идти к 5.5.

5.5. Если ветвь узла Н1 является крайней правой среди порожденных общим узлом, то выбирается породивший ветвь узел (если он не помечен, то— ближайший из помеченных в направлении к корню) и Н1 полагается равным

его основной разметке. Идти к 5.5.

Иначе идти к 5.7.

5.6 Если выбранный узел помечен числом H1=0, то идти к 6. Иначе идти к 5,4.

5.7. Ближайший к породившему узел

Н1 из соседней справа ветви, порожденной тем же узлом, помечается числом Н1=Н+1. Идти к 5.3.

6. Составляется карта памяти для случая сплошного контроля входных конструкций на наличие недопустимых символических обозначений.

6 ° 1.Номер А строки карты памяти (т.е. адрес соответствующей ячейки памяти) основного блока памяти принимается равным нулю (А=О).

6.2. Выбирается узел, помеченный номером Н1=1.

6.3 ° Если символ выбранного узла имеет К двоичных эквивалентов, то в первые поля строк А...А+К-1 последовательно заносятся все К двоичных эквивалентов, если символ — лист, то — код пробела.

6.4. Если символ узла Н1 имеет один двоичный эквивалент, то идти к

6.5. Иначе во вторые поля строк

А...А+К-2 заносится код числа А+К.

При этом признаки перехода во всех строках (крайний правый разряд поля) принимаются равными нулю — переход по совпадению. Заполнение строки А+

+К-1 описано в следующем пункте. Идти к 6.5.

6.5 Если узел Н1 порожден ветвящимся узлом и не является крайним правым среди порожденных этим узлом, то во второе поле заносится двоичный код величины

14

1164736

Н<п-1

Pi6 Ал+ С вЂ” КАэ„+Кл

3,.Н1„Аэк и нФ„, Н1 „7

О где л, и — индексы, обозначающие принадлежность переменных соответственно узлу Н1 (левому) и соседнему справа от него (А — адрес первого двоичного эквивалента левого узла);

К вЂ” количество двоичных эквиДэ„ валентов к-ro узла;

K, - количество узлов.от Н1

Н л > n-л и до Н11,,1 включительно, являющихся листьями.

В противном случае во второе поле заносится код 1...1. Признак перехода устанавливается равным единице.

6 ° 6. В том случае, если выбранный узел является листом, заполнение третьего поля произвольно (однако младший разряд должен быть равен нулю), иначе в него заносится (для всех строк от А до А+К-1 включительно, где К вЂ” число двоичных эквивалентов узла) двоичное значение ранга узла Н1+1, если Н1 не порожден ветвящимся узлом или порожден, но не имеет соседнего справа узла, порожденного тем же ветвящимся и имеющего полный набор двоичных эквивалентов. При этом крайний правый разряд поля (признак перехода в блоке памяти симВОлОВ кОнструкции ВхОднОГО 35 языка) устанавливается. равным нулю— переход по совпадению. В противном случае заполнение строк А...А+К-2 аналогично, а в третье поле строки

А+К-1 записывается код ранга ближай- 40

mего помеченного узла к породившему соседний справа от узла Н1 в направлении от корня дерева, признак перехода принимается равным единице— переход по несовпадению. 45

6.7. В четвертое поле записывается признак типа формата заполненной строки — "ноль".

6.8. Если узел Н1 не лист, то выбирается строка А А+К (К вЂ” число 50 двоичных эквивалентов узла Н1) и узел Н1Н1+1. Идти к 6.3. Иначе идти к 6.9.

6.9. В первое поле строки А=А+К заносится выбранный двоичный код 55 конструкции выходного языка.

6.10. Второе поле предназначено для признака вставки: если в код конструкции выходного языка не требуется вставлять код какого-либо символа конструкции входного языка, то в .поле записывается нулевой код, иначе — единичный.

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

6.12. В четвертое поле записывается признак формата заполненной строки вЂ,"единица".

6.13. Если при составлении карты использованы не все узлы графа (Н11

ФН„,л„ ), то выбирается узел Н1=Н1+1 и строка А=А+1. Идти к 6.3. Иначе идти к 10.

7. Если вспомогательная численная разметка не проводилась, то идти к 8. Иначе (проводилась достройка графа) идти к 7.1;

7.1. Выбирается ветвящийся узел из имеющих порожденные неразмеченные узлы, для которого наименьшим является значение разметки Н2 среди узлов двух тинов: крайнего правого из размеченных порожденных им и ближайшего верхнего в направлении от упомянутого ветвящегося узла к корню дерева (если нет порожденных помеченных узлов).

7.2. Уничтожается вспомогательная численная разметка всех узлов от Н2+1 до Н2 ц, включительно.

7.3. В первом случае идти к 8.5.

Иначе выбрать узел Н2 и идти к 8.2.

8. Выполняется вспомогательная численная разметка графа.

8.1. Узел нулевого ранга (если их несколько, то =крайний левый) помечается числом Н2=1 (корень дерева — нулем).

8,2. Выбирается крайний левый узел из порожденных выбранным ранее.

8.3. Если узел, породивший выбранный, является ветвящимся, то выбранный узел помечается числом

Н2=Н2+1.

8.4. Если выбранный узел не является листом, то идти к 8.2. Иначе идти к 8.5.

8.5. Выбирается узел Н2, Запоминается значение его разметки (НН2).

8.6. Если выбранный узел имеет справа от себя непомеченные узлы, порожденные тем же узлом, что и он

15

Н2па дз„+Ки

, 112 " Н2л>Н2П-< >

1!647 сам, то выбирается крайний левый из них (если символ этого узла имеет полный набор двоичных эквивалентов, то выбирается первый из имеющих один или неполный набор двоичных эквивалентов в направлении от корня) и помечается номером Н2=Н+1. Идти к

8.4. Иначе идти к 8.7.

8.7. Выбирается узел, ближайший от Н2 в направлении к корню, имею- 10 щий справа от себя непомеченные узлы, порожденные тем же, что и он сам.

Идти к 8.6. Если таких узлов.нет, то идти к 9.

9. Строится карта памяти для слу- 15 чая организации процесса трансляции с частичным контролем входных конструкций на наличие недопустимых символических обозначений.

9.1. Номер строки карты памяти 20 принимается равным нулю (А=О).

9.2. Выбирается узел, помеченный номером Н2=1.

9.3. В первое поле строки А записывается код символа узла Н2, если узел Н2 является листом, то — код пробела. Если символ имеет К двоичных эквивалентов, то в первые поля строк A. А+К-1 последовательно заносятся все К двоичных эквивалентов. 30

9.4. Если символ узла Н2 имеет один двоичный эквивалент, то идти к 9.5 ° Иначе во вторые поля строк

А...А+К-2 заносится код числа А+К.

При этом признаки перехода во всех строках принимаются равными нулю— переход по совпадению. Заполнение строки А+К-1 описано в следующем пункте. Идти к 9.5 °

9.5. Если выбранный узел не име- 4р ет справа от себя узлов, порожденных тем же ветвящимся, что и выбранный, то во второе поле заносится код 1 ° ..1 ° Признак перехода устанавливается равным единице. Иначе в него записывается двоичныи код числа, определяемого по формуле где л, п — индексы, обозначающие принадлежность переменных соответственно левому и правому узлу из рассматриваемой пары узлов (А адрес первого двоичного. эквивалента левого узла), — количество двоичных эквиИк валентов к-ro узла; — количество листьев, расН,„,до„, положенных в конце всех маршрутов, проходящих через узлы H2„...Í2,, но, не проходящих через узлы со значениями разметки, большими Н2„ .

9.6. Заполнение третьего поля строк А...A+K-1 произвольно, если ранг узла Н2+1 не превышает ранга узла Н2 (однако младший разряд должен быть равен нулю), иначе в него записывается двоичный код ранга узла Н2+1. Причем признак перехода принимается равным нулю, если узел

H2+i приходится в направлении от корня, и единице, в противном случае.

9.7. Четвертое поле предназначено для записи. признака типа формата заполнения строки — "0".

9.8. Если ранг узла Н2+1 больше ранга узла Н2, то выбирается строка

А=А+К (К вЂ” количество двоичных эквивалентов символа узла Н2) и узел

H2=H2+1. Идти к 9,3. Иначе идти к 9.8.

9.9. В первое поле строки А=А+К заносится выбранный двоичный код конструкции выходного языка.

9.10. Второе поле предназначено для признака ставки: если в код конструкции выходного языка не требуется вставлять код какого-либо символа конструкции входного языка, то в поле записывается нулевой код, иначе — единичный.

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

9.12. В четвертое поле записывается признак формата заполненной строки — "1".

9.13. Если при составлении карты использованы на все узлы графа (Н2Ф

ФН2„к1 то выбирается узел Н2=Н2+1 и строка А=А+1. Идти к 9.3. Иначе идти к 10.

10. Конец.

Оценка объема занимаемой памяти и времени трансляции по графу может быть проведена с помощью формул: йакс K*, + Kn

t-1

18

17

1164736

""Сюже

Т«, =(Hkceakc+1+ Е (Ky+KA,/2) «ТМ 1

Нкс 1

К»

TKc = Х:: Т„, ° о„; азсср к=

5 где Š— объем необходимой памяти в ячейках основного блока памяти"„

Н вЂ” максимальное значение разМО метки графа, К д, — колифество двоичных элементов символа -го узла", K — количество листьев графа;

Т1, — время трансляции конструкции", Т вЂ” длительность такта устройст)CT ва (генератора импульсов), Н (Н вЂ” значение разметки узлов гра С Ъсц, фа, в которых записаны

20 символы рассматриваемой конструкции (максимальное значение);

K — количество узлов располоtJh

9 женных левее узлов, имеющих разметки Н„ и имеющих тот же порождающий узел, 1„, †: среднее время трансляции конструкции при разных частотах использования отдель- 3О пых конструкций, Π— частоты использования отдельных конструкций;

Т р„ — время трансляции программьц

N — количество конструкций в программе

Т вЂ” длительность такта ввода

8 символа в утсройство, Кс„ - количество символов в коде I-ой конструкции входного 40 языка.

Укаэанные формулы имеют одинако-, вый вид для обоих вариантов составления карты памяти. При выборе конкретного варианта переменная Н заменя- 45 ется на соответствующую переменную

Н1 или Н2.

Устройство работает следующим образом.

При включении устройства на вход 50

32 поцается сигнал, устанавливающий триггеры 28 и 29 в нулевое состояние и поступаюший через элемент 10 ИЛИ для установки в ноль счетчика 3 адре.са. Затем производится запись инфор- 55 мации в блок 1 памяти. На информационные входы 33 поступает первое слово для записи в нулевую ячейку памяти, адрес которой установлен в счетчике 3 адреса. Сопровождающий данное слово синхроимпульс IIO входу

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 памяти, К

1!64736

10

25

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

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

По коду пробела на выходе дешифратора 27 появляется сигнал, переводящий триггер 28 в нулевое состояние и производящий запуск генератора 31 прямоугольных импульсов.

Синхроимпульс с входа 36, поступивший с символом "Пробел", проходит через элемент 15 И и 10 ИЛИ и устанавливает в ноль счетчик 4 адреса.

На этом режим приема конструкции входного языка заканчивается.

B режиме трансляции по сигналу, прошедшему с элемента 10 ИЛИ через элементы 11 ИЛИ, 26 задержки и 12 И на вход считывания блока 2 памяти, с его выхода на схему 6 сравнения вьдается код символа. Кроме того, по сигналу с генератора 31 прямоугольных импульсов считывается информация из блока 1 памяти. Через элемент 23 задержки и элемент t7 H сигнал с генератора поступает на управляющий вход схемы 6 сравнения, .в результате чего сравниваются коды с выходом блоков 1 и 2 памяти.

При совпадении символов сигнал появляется на соответствующем выходе.схемы сравнения и в зависимости от значения признака перехода в блоке 1 памяти проходит либо через переключатель 7 (если признак равен единице) на счетный вход счетчика 3 адреса (при этом адрес увеличивается на единицу), либо через переключатель 8 (признак равен нулю) на вход приема счетчика адреса (при этом в него принимается адрес перехода с выходов блока 1 памяти). Кроме того, сигнал совпадения проходит через элемент 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 И, 22 но упростить и ускорить процесс разработки трансляторов для языков программирования, отдельные символы конструкций которых (непосредственный операнд, номер регистра, модификатор и др. ) имеют более одного двоичного эквивалента, обладает дополнительной воэможностью изменения условий перехода в обоих блоках памяти при построении алгоритмов трансляции. Это приводит к более рациональному расходу памяти, объем которой может быть уменьшен в отдельных случаях на порядок, сокращению числа допускаемых ошибок как при построении карты памяти, так и при занесении ее в блок памяTH

21 1164736 на другом входе которого присутствует единица с выхода триггера 29, на управляемый вход регистра 5 выдачи.

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

Если в процессе трансляции с выхода счетчика 4 адреса появится код 1... 1, то элемент 21 И переключается в еди- 10 ничное состояние и на выходе 37 индикации ошибки появляется сигнал, говорящий о том, что введенная в блок 2 памяти конструкция является недопустимой и результат трансляции 15 ошибочный.

Изобретение в отличие от известного устройства позволяет существен!

164736

Составитель А.Жеренов

Техред А.Бабинец Корректор А.Тяско.

Редактор И.Дьшын

Тираж 710 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и о ткрытий

1l3035, Москва, Ж-35 Раушская наб., д, 4/5

Заказ 4933

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

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

 

Похожие патенты:

Изобретение относится к компьютерной системе создания и перевода документов, к системе подготовки текста на языке ограничений и перевода на иностранный язык

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

Изобретение относится к обработке информационных естественно-языковых текстовых материалов

Изобретение относится к системам классификации текстовых сообщений

Изобретение относится к автоматизированному синтезу текстовых документов

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

Изобретение относится к распознаванию образов из графического изображения, и в частности к распознаванию текста на изображении документа в электронном виде

Изобретение относится к устройствам распознавания написанных знаков
Наверх