Устройство для перевода выражений в польскую инверсную запись

 

1. УСТРОЙСТВО ДЛЯ ПЕРЕВОДА ВЫРАЖЕНИЙ В ПОЛЬСКУЮ ИНВЕРСНУЮ ЗАПИСЬ , содержащее входной регистр, дешифратор лексических единиц,, дешифратор кодов операций входньгх выражений , схему сравнения приоритетов, коммутатор, блок элементов ИПИ, выГходной регистр, блок магазинной памяти , блок контроля и блок микропрограммного упрагвления, состояпщй из регистра адреса микрокоманд, дешифратора адреса микрокоманд, блока памяти микрокоманд, счетчика, дешифратора адреса команд, элемента И, генератора тактовых импульсов, триггера и группы элементов И, первые входы элементов И группы соединены с выходом элемента И и со счетным входом счетчика группа информационных выходов которого соединена с группой входов дешифратора адреса команд, группа выходов которого соединена с группой адресных входов старших разрядов блока памяти микрокоманд , группа адресных входов младших разрядов которого соединена с группой выходов дешифратора адреса микрокоманд, группа входов которого соединена с группой выходов регистра адреса микрокоманд, первый и второй входы элемента И соединены соответст венно с выходом генератора тактовых импульсов и с выходом триггера, вход установки в О которого соединен с выходом первого элемента И группы, вторые входы элементов И группы соединены с информационными выходами блока памяти микрокоманд, выходы .второго, третьего, четвертого и пятого элементов И группы соединены соответственно с входом записи входного регистра, с управляющим входом коммутатора, с входом записи блока % магазинной памяти и с входом чтения блока магазинной памяти, первая СУ ) группа информа1щонных входов регистра адреса микрокоманд соединена с группой выходов дешифратора лексических единиц и с труппой входов, блока контроля, вторая группа информационных входов регистра микрокоманд соединена с группой выходов схеОд мы сравнения приоритетов, вход устао новки в 1 триггера соединен с вхо00 М дом пуска устройства, первая группа входов схемы сравнения приоритетов ;о соединена с группой выходов дешифратора кодов операций входных выражений , первая группа входов блока магазинной памяти соединена с группами входов дешифратора лексических единиц, дешифратора кодов операций входных выражений и коммутатора, а также с группой выходов входного регистра , первая группа выходов блока магазинной памяти соединена с первой группой входов блока элементов ИПИ, вторая группа входов и группа выходов которого соединена соответ

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

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

РЕСПУБЛИН (19) (11) 3(51) 06 5 38

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21} 471240/18-24 (22) 15.07.82 .(46} 23.12.84. Бюл. Р. 47 (72) Г.А.Брякалов, А.А.Булгаков, А.И.Захаров, Н.А.Калмыков и В.В.Ковалев (53) 681.325 (088.8) (56) 1. Авторское свидетельство СССР

Ф 890403, кл. C 06 Р 15/38.

2. Авторское свидетельство СССР по заявке У 331793 1/18-24 (прототип). (54) (57) 1. УСТРОЙСТВО ДЛЯ ПЕРЕВОЛА

ВЫРЮКЕНИЙ В ПОЛЬСКУЮ ИНВЕРСНУЮ 3АПИСЬ, содержащее входной регистр, дешифратор лексических единиц» дешифратор кодов операций входных выражений, схему сравнения приоритетов, коммутатор, блок элементов ИЛИ, вы;ходной регистр, блок магазинной паMHTH блок контроля H блок MHKpollpGграммного управления, состоящий из регистра адреса микрокоманд, дешифратора адреса микрокоманд, блока памяти микрокоманд, счетчика, дешифратора адреса команд, элемента И, генератора тактовых импульсов, триггера и группы элементов И, первые входы элементов И группы соединены с выходом элемента И и со счетным входом счетчика группа информацион) ных выходов которого соединена с группой входов дешифратора адреса команд, группа выходов которого соединена с группой адресных входов старших разрядов блока памяти микрокоманд, группа адресных входов младших разрядов которого соединена с группой выходов дешифратора адреса микрокоманд, группа входов которого соединена с группой выходов регистра адреса микрокоманд, первый и второй входы элемента И соединены соответст венно с выходом генератора тактовых импульсов и с выходом триггера, вход установки в "0" которого соединен с выходом первого элемента И группы, вторые входы элементов И группы соединены с информационными выходами блока памяти микрокоманд, выходы второго, третьего, четвертого и пятого элементов И группы соединены соответственно с входом записи входного регистра, с управляющим входом коммутатора, с входом записи блока магазинной памяти и с входом чтения блока магазинной памяти, первая группа информационных входов регистра адреса микрокоманд соединена с группой выходов дешифратора лексических единиц и с группой входов. блока контроля, вторая группа информационных входов регистра микрокоманд соединена с группой выходов схемы сравнения приоритетов, вход установки в "1" триггера соединен с входом пуска устройства, первая группа входов схемы сравнения приоритетов соединена с группой выходов дешифратора кодов операций входных выражений, первая группа входов блока магазинной памяти соединена с группами входов дешифратора лексических единиц, дешифратора кодов операций входных выражений и коммутатора, а также с группой выходов входного регистра, первая группа выходов блока магазинной памяти соединена с первой группой входов блока элементов

ИЛИ, вторая группа входов и группа выходов которого соединена соответ879

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

2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что блок магазинной памяти содержит первый, второй и третий коммутаторы, магазинную память хранения приоритетов лексических единиц и магазинную память хранения лексических единиц, группа выходов которой соединена с группой входов первого коммутатора, группа выходов которого соединена с первой группой выходов блока, управляющий вход первого коммутатора соединен с входом чтения блока, управляющие входы второго и третьего коммутатора соединены с входом записи блока, входы сдвига "вниз" и "вверх" блока соединены соответственно с входами сдвига "вниз" и "вверх" магазинной памяти хранения приоритетов лексиI ческих единиц и магазинной памяти хранения лексических единиц, группа входов которой соединена с группой выходов второго коммутатора, группа входов которого соединена с первой группой входов блока,. а вторая группа входов блока соединена .с .группой входов третьего коммутатора, группа выходов которого соединена с группой входов магазинной памяти хранения приоритетов лексических единиц, груп па выходов которой соединена с второй группой выходов блока.

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных и производства программ для ЭВМ.

Известно устройство для перевода выражений в польскую инверсную запись. Оно может быть использовано в автоматизированных системах производства программ для ускорения процесса трансляции j1) .

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

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

f5

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

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

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

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

И, элемент И, причем входы регистра являются соответственно первой, второй и, третьей группой входов блока управления, вход счетчика команд соединен с выходом элемента И, первый вход которого соединен с выходом генератора импульсов, а второй — с единичным выходом триггера, нулевой вход которого соединен с выходом первого элемента И группы а единичный является входом "Пуск" блока управления, выходы регистра и счетчика команд соединены соответственно с входами дешифратора микрокоманд и дешифратора команд, выходы которых соединены соответственно с адресными входами первой и второй групп микропрограммной памяти, ин50

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

5 выходу элемента И а выходы являются выходами блока управления с первого по седьмой . Бл ок контроля с одержит реверсивный счетчик, первый, второй и третий элементы ИЛИ, первый и второй элементы И, элемент НЕ, дешифра-, тор состояния, элемент задержки, причем первый и второй входы первого и второго элементов ИЛИ, первый вход первого элемента И и вход элемента задержки соединены с соответствующими выходами дешифратора лексических единиц, выходы первого и второго элементов ИЛИ подключены соответ ственно к входам сложения и вычитания реверсивного счетчика, установочный вход которого подключен к выходу элемента задержки и к входу элемента НЕ, а выход последнего подключен к входу синхронизации реверсивного счетчика и ко второму входу первого элемента И, третий вход кото. рого подключен к выходу дешифратора состояний, выходы первого и второго элементов И подключены соответствен30 но к первому и второму входам третьего элемента ИЛИ, выход которого является выходом "Ошибка" устройства, входы второго элемента И подключены к соответствующим выходам реверсивного счетчика, входы дешифратора состояний подключены к соответствующим инверсным выходам реверсивного счетчика j2) .

Недостатком устройства является

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

Цель изобретения — повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для перевода вы15

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

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

ЗО блока магазинной памяти и с входом чтения блока магазинной памяти, первая группа информационных входов регистра адреса микрокоманд соединена с группой выходов дешифратора лексических единиц и с группой входов блока контроля, вторая группа информационных входов регистра микрокоманд соединена с группой выходов схемы сравнения приоритетов, вход установки в "1" триггера. соединен с входом пуска устройства, первая группа входов схемы сравнения приоритетов соединена с группой выходов дешифратора кодов операций входных выражений, первая группа

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

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

На фиг. 1 представлена структурная схема устройства, на фиг. 2— структурная схема блока магазинной памяти; на фиг. 3 - структурная схема блока микропрограммного управления, на фиг. 4 — структурная схема блока контроля.

Устройство содержит входной регистр 1, дешифратор 2 лексических

0879

1p,в выходной регистр.

ЗО

55

7 113 единиц, блок 3 магазинной памяти, дешифратор 4 кодов операций входных выражений, схему 5 сравнения приоритетов, блок 6 микропрограммного управления, блок 7 элементов ИЛИ, коммутатор 8, выходной регистр 9, блок 10 контроля.

В состав блока магазинной памяти входят третий 11, второй 12 и .первый

13 коммутаторы, магазинная память

14 хранения приоритетов лексических единиц и магазинная память 15 хранения лексических единиц.

В состав блока микропрограммного управления входят рerистр 16 адреса микрокоманд, счетчик 17, дешифратор 18 адреса микрокоманд, дешифратор 19.адреса команд, блок 20 памяти микрокоманд, генератор 21 тактовых импульсов, триггер 22, группа элементов И 23 и элемент И 24.

Блок 10 контроля содержит реверсивный счетчик 25, первый 26 и второй 27 элементы ИЛИ, элемент 28 задержки, первый, элемент И 29, дешифра. тор 30, второй элемент И 31, элемент

НЕ 32 и третий элемент ИЛИ 33.

Входной регистр 1 используется для хранения очередной лексической единицы исходного выражения, дешифратор 2 лексических единиц разделяет лексические единицы на операнды, операции, скобки.и т.д. Блок 3 магазинной памяти — это память с после доваФельным безадресным принципом записи и чтения. Дешифратор 4 кодов операций входных выражений совместно со схемой 5 сравнения приоритетов и блоком магазинной памяти реализуют логическую функцию выработки. и сравнения приоритетов

Ц Х4 Ц Х4Х 5 Ц Х4Х Х чЦ» Х М К Х Ч

У Чз" э +у2 х чу4ц<хам „ч з9 "а

Ч4ЧтЧ,ХЗХ, Ч4ЧЗЧ,XqX, < З,Х, v

Ч 1 2 Õ4 Õ " Р.Ч Ч " Х г Х, g lj, Х 4 Х Х < .

Блок 6 микропрограммного управления организует взаимодействие всех элементов устройства и представляет собой типовую схему. микропрограммного управления. Блок 7 элементов ИЛИ и коммутатор. 8 управляют передачами лексических единиц, а выходной регистр 9 предназначен для хранения очередной лексической единицы в форме ПОЛИЗ. Блок 10 контроля проверяет наличие и порядок следования лексических единиц в исходном выражении.

Коммутатор 11 блока магазинной памяти обеспечивает поступление приоритетов лексических единиц в магазинную память 14, а коммутатор

12 обеспечивает поступление лексических единиц в магазинную память 15

Коммутатор 13 блока магазинной памяти обеспечивает поступление лексических единиц из магазинной памяти

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

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

Если очередная- лексическая единица — левая скобка., то дешифратор 2 запускает блок 6 микропрограммного управпения, управляющий сигнал которого разрешает запись этой единицы через коммутатор 12 из входного регистра 1 в магазинную память 15 хранения лексических единиц блока 3 магазинной памяти. Этот же управляющий сигнал разрешает запись приоритета указанной лексической единицы через коммутатор 11 с выхода дешифратора кодов операций 4 в магазинную память 14 хранения приоритетов лексических единиц. Одновременно сигнал с дешифратора 2 подается на блок

10 контроля, где фиксируется наличие и порядок следования лексической единицы.

Если очередная лексическая единица — операнд, то дешифратор 2 запускает блок 6 микропрограммного управпения, управляющий сигнал которого разрешает через коммутатор 8 и блок

7 элементов ИЛИ перепись кода операнда из входного регистра 1 на выходной регистр 9. Одновременно сиг нал с деширратора 2 подается на блок

10 контроля, где снова фиксируется наличие и порядок следования этой лексической единицы.

Если очередная лексическая единица — операция, то сигнал с выхода дешифратора 2 лексических единиц запускает блок 6 микропрограммного управления, а в блоках 4 и 5 с участием магазинной памяти 14 начинается процесс выработки и сравнения приоритетов. Блок 6 блокирует запись очередной лексической единицы на входной регистр 1. Лексическая единиА - В/(С + Д);

9 1 ца — операция с входного регистра 1поступает на дешифратор 4, где определяется ее приоритет, который далее поступает на схему 5 сравнения приоритетов. Туда же иэ магазинной памяти 14 хранения приоритетов поступает приоритет лексической единицы, ранее записанной в блоке 3 магазинной памя ти. По результату работы схемы 5 сравнения приоритетов лексических единиц блок 6 организует запись через коммутатор 11 в магазинную память 14 приоритета записываемой лексической единицы, а через коммута тор 12 в магазинную память 15 самой лексической единицы. Одновременно с этим блок 6 микропрограммного управления вырабатывает сигнал

"Сдвиг вниз" или "Сдвиг вверх", по которым осуществляется сдвиг информации, хранящейся в блоке 3 магазинной памяти. B режиме чтения лексическая единица — операция записы.вается через блок 7 элементов ИЛИ в выходной регистр 9, после чего про изводится разблокировка входного регистра 1.

Одновременно сигнал с дешифратора 2 подается на блок 10 контроля и организует его работу.

Когда на входном регистре 1 по1 явится лексическая единица — правая скобка, то по сигналу с дешифратора

2 лексических единиц блок 6 микропрограммного управления блокирует входной регистр организует режим чтения из блока 3 магазинной памяти и организует зались содержимого магазинной памяти 15 через коммутатор 13 и блок 7 элементов ИЛИ в выходной регистр 9 до тех пор, пока в

"верхушке" магазинной памяти не окажется код лексической единицы левой скобки. Одновременно по сигналу с дешнфратора 2 лексических единиц осуществляется работа блока 1О контроля.

Преобразование входного выражения в форму ПОЛИЗ происхоит до тех пор, пока в регистре 1 не окажется лексическая единица — конец виражения.

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

130879 о могут поступать лексические единицы с лед ующе го выр аже ни я .

Цикл работы устройства повторяется.

Работу предлагаемого устройства можно дополнительно проиллюстрировать на примере.

Пусть входное выражение имеет вид

10 ют. и где; используется как лексическая единица — конец выражения.

Процесс перевода вь:ражения в польскую инверсную запись протекает следующим образом.

На входной регистр 1 поступает лексическая единица "А", которая определяется дешифратором 2 как операнд и с помощью блока 6 микропрог"

70 раммного управления з исывае ся че реэ коммутатор 8 и блок 7 элементов

ИЛИ в выходной регистр 9, На входной регистр принимается очередная лексическая единица

Это операция. Входной регистр 1 блокируется. На дешифраторе 4 вырабатывается приоритет лексической едини цы, который на салеме 5 сравнения приоритетов сравнивается с приоритетом лексической единицы, записанной в "верхушку" магазинной памяти.

Этот приоритет хранится в "верхушке" блока 14 хранеьжя приоритетов лексических единиц.

Так как в исходном состоянии магазинная память свободна, то в результате сравнения лексическая едите ет ница — записывается в маг аэинную память 1 5, а ее приоритет — в маг аэинную память 1 4 . После этого. вход40 ной р е гистр 1 разблокируется .

Очередная лексическая единица

1I l t

 †..операнд. Она записывается во входной регистр 1, а затем переписывается в выходной регистр 9.

Очередная лексическая единица

II /t1

/ записывается во входной регистр

1 и определяется дешифратором 2 как операция. Блокируется входной регистр 1. На схеме 5 сравнения приори тетов сравниваются приоритеты лексических единиц, подтупающие с дешифратора 4 и из магазинной памяти 14.

Так как приоритет операции "/" выше приоритета операции "-", блок 6 мик5 ропрограммного управления формирует сигнал Сдвиг вниз" и Запись" и лексическая единица "/" со своим приоритетом записывается B верхуш-, 1130879

11 ку" магазинной памяти . Входной р егистр 1 разблокируется и принимает очередную лексическую единицу "(" °

Дешифратор 2 опознает ее как левую скобку, блок 6 микропрограммного управлеыя вырабатывает сигнал

"Сдвиг вниз" и "Запись" и лексичесР кая единица со своим приоритетом записывается в блок 3 магазинной памяти. с

На входной регистр 1 принимается очередная лексическая единица С".

Она является операндом и записывается в выходной регистр 9.

Далее на входной регистр 1 принимается лексическая. единица "+".

Дешифратор 2 запускает блок 6 микропрограммного управления и начинается процесс выработки и сравнения приоритетов. Входной регистр 1 блокируется. Так как приоритет операции "+" выше внутримагазинного приоритета левой скобки, то "+" вместе со своим приоритетом записывается в блок 3 магазинной памяти. Входной регистр 1 разблокируется и на него принимается очередная лексическая единица..

Это.операнд "Д", он записывается в выходной регистр 9.

Очередная лексическая единица

")" входного выражения -принимается на входной регистр 1. Дешифратор 2 определяет, что это правая скобка и запускает блок б микропрограммного управления. Входной регистр 1 блокируется. К этому моменту в блок магазинной памяти записаны следующие лексические единицы: "-", "/", "(", "+", причем в "верхушке" магазинной памяти находится "+". Блок

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

"+" из блока магазинной памяти и запись ее в выходной регистр 9.

Под воздействием сигнала "Сдвиг вверх" осуществляется перемещение . всей информации, хранящейся к этому времени в магазинной памяти на одну ячейку. Вновь анализируется содержи-. мое "верхушки" магазинной памяти и, так как теперь в ней находится левая скобка со своим приоритетом, то производится ее чтение без записи в выходной регистр 9 (стирание из

"верхушки 1 магазинной памяти). Входной регистр разблокируется и на него принимается очередная лексическая единица — конец выражения.

1 э

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

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

Итак, на входной регистр поступило выражение А — В/(С + Д); а через выходной регистр на выход устройства оно поступило уже в виде

А,В,С,Д +, /, †. Этот порядок следования символов соответствует польс кой инверсной записи входного выражения.

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

Сигналы с генератора 21 тактовых импульсов при наличии разрешающего потенциала на единичном выходе триггера 22 (положение "Пуск" ) поступают на вход счетчика 17 команд с коэффициентом пересчета четыре и периодически заполняют его.

Кодовые комбинации с регистра 16 и счетчика 17 подаются соответственно на дешифратор 18 и дешифратор 19, с выходов которых сигналы поступают на входы блока 20 памяти.

В итоге на выходе блока 20 памяти образуется пространственно-временная последовательность управляющих сигналов, которая через группу элементов И 23 появляется на соответствующих выходах блока 6 микропрограммного управления. Работа группы элементов И 23 синхрониэируется генератором 21 импульсов.

Блок 10.контроля работает следующим образом.

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

Если очередная лексическая единица — операнд, то соответствующий ей сигнал с дешифратора 2 подается на блок 10 контроля и,. пройдя в нем через элемент ИПИ 26, поступает на реверсивный двоичный счетчик 25.

Поскольку лексической единице — операнду присвоен вес +1, то сигнал с дешифратора 2 поступает на суммиl3 рующий вход реверсивного счетчика

25, к содержимому которого прибавляется единица.

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

Если очередная лексическая единица — левая скобка, то сигнал с дешифратора 2 поступает на суммирующий вход реверсивного счетчика 25, а в случае, если это правая скобкана вычитающнй.

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

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

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

ИЛИ 23, появляется на выходе блока

10 контроля в виде сигнала ошибки.

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

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

30879 1É

50 инверсных выходах остальных разрядов реверсивного счетчика появится единичные сигналы, вследствие чего сигнал на выходе дешифратора 30 будет отсутствовать. Не будет сигнала и на выходе элемента И 31.

Если сумма весов в конце преобразования отличается от плюс единицы, то на выходе реверсивного счетчика будет другая кодовая комбинация. В этом случае сигнал с выхода дешифра. тора 30 состояний подается на перsbN вход элемента И 31, на второй вход которого поступает сигнал с выхода элемента НЕ 32, а на третий— сигнал с входа блока 10 контроля, соответствующий лексической единице — конец выражения. Сигнал, появившийся на выходе элемента И 31, пройдя через элемент ИЛИ 33, воспринимается на выходе блока 10 контроля в виде сигнала ошибки.

Поскольку сигналом — конец выражения осуществляется сброс в нулевое состояние содержимого реверсивного счетчика 25, для предотвращения появления ложного сигнала ошибки на выходе блока контроля сигнал— конец выражения подается на счетчик через элемент 28 задержки. Одновременно сигнал с выхода элемента 28 задержки подается на вход элемента

НЕ 32. Отсутствие сигнала на втором входе элемента И 31 исключает появле ние ложного сигнала ошибки.

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

1130879

1130879

В бтКа уаробяения

Put.2

1 >nna Рейд йа Вешу оратора уьЯ але ауии

ыр

2 гаруна РхпоЬЮ (ю ЮУО Ь020 регисмра ) it30879

mrna®

1130879

Составитель Ю.Панцов

Редактор С.Патрушева Техред Т.Фанта Корректор А.Обручар

Заказ 9б12/36 Тираж 698 Подпис ное

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

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

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