Устройство для перевода арифметических выражений в линейные регулярные префиксные формы

 

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных, производства программ и разработки трансляторов ЭВМ. Цель изобретения - расширение возможностей за счет определения типов ошибок при одновременном повышении быстродействия. Для этого в устройство введены счетчик 4 операндов и ходной регистр 7. Введение этих элементов , а также использование в блоке 5 памяти реверсивных сдвигающих регистров оптимизирует алгоритм работы устройства. 3 ил.

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

СОЦИАЛИСТИЧЕСКИХ . РЕСПУБЛИК

Ь1,)5 o6 F 15/38 11/00

И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ fHHT СССР,:(21) 4"97247/24 (22) 24,10 88 (46) 23.06,92. . Бюл. 23 (72)..В.К.Водопьянов, Г.В.Назарьян, А.А.Домрачев и С.П.Зайцев (53) 681.325(088.8) (56) Авторское свидетельство СССР

V 1130879, кл. G .06 F 15/38, 1985.

Авторское свидетельство СССР

Н 1439591, кл. G 06 F 15/38, 11/00, 1987. (54) УСТРОЙСТВО ДЛЯ ПЕРЕВОДА АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ В ЛИНЕЙНЫЕ РЕГУЛЯРНЫЕ ПРЕФИКСНЫЕ ФОРМЫ

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

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

Устройство содержит входной ре-:. .гистр 1,- дешифратор 2 лексических единиц, блок 3 управления, счетчик

4 операндов, блок 5 памяти, дешифратор Ь блока памяти, выходной регистр

7. Блок 5 памяти построен на реверсивных регистрах сдвига. Выходной

„„SU „„1742832 А1

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

Цель изобретения - расширение возможностей за счет определения типов ошибок при одновременном повышении быстродействия. Для этого в устройство введены счетчик 4 операндов и вы", ходной регистр 7. Введение этих элементов, а также использование в блоке

5 памяти реверсивных сдвигающих регистров оптимизирует алгоритм работы устройства. 3 ил. регистр 7 .образуют восемь регистров с разрядностью не менее 12 разрядов.

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

Х вЂ” Х из Лешифратора 2 лексических единицы, а на вторую. группу входовсигналы Х7 - Х 7 из дешифратора 6 блока памяти. На семи выходах блока

3 микропрограммного управления Форми32

Y) 2

Уэ"

Yg

У9

<о

Y)g

15 f6

Х!Э =

22 29

Хп =

Соде си гнало

7428 руют сигналы микроопераций " —

Содержательный смысл входных сигналов следующий.

1, если очередной символ есть

° ° знак UХ, = О, если в противном случае;

1, если очередной символ есть

I знак конца выражения ф

О, 10

1, если очередной символ есть знак операции;

Х = 0, 1, если очередной символ есть

I 1 ° знак

15 х = о, 1, если очередной символ есть знак );

Х = О, 1, если очередной символ есть операнд;

Х = О, в йротивном случае, Х = О, в пРотивном случае, 1, если содержимое и-разряда

1 блока 5 памяти есть»»;

1, если содержимое и-разряда блока 5 памяти есть ф;

Х„ = О, 1, если содержимое п-разряда. блока 5 памяти есть знак опе-. рации;

О, 1, если содержимое и-разряда блока 5 памяти есть С;

О, если содержимое и-разряда 3з

I блока 5 памяти есть );

О, 1, если содержимое и-разряда блока 5 памяти есть F

О в противном случае, 16

1, если значение (и-1) разряда блока 5 памяти есть

О в противном случае, 1, если значение (n- 1) разряда . блока 5 памяти есть знак one- g$ рации;

О в противном случае, 1, если значение (и-1)-разряда ! блока 5 памяти есть (О в противном случае

1, если значение (и-2)-разряда блока 5 памяти есть

О в противном случае, 1, если значение (и-3)-разряда блока 5 памяти есть (;

О в противном случае. ржательный смысл выходных

B следующий: сброс в ноль входного регистра

1 ° сброс в ноль регистров блока 5 памяти; сброс в ноль выходного регистра 7; занесение в и-разряд регистров блока 5 памяти значение кода знака; занесение в и-разряд блока 5 памяти значения, ф»; разрешение ввода следующей лексической единицы "ш" во входной регистр 1; разрешение записи в блок 5 па" мяти; выработка сообщения. "успешный анализ"; выработка сообщения "ошибка"; выработка сообщений "во входном выражении неверно расположен знак конца выражения", выработка сообщения "во входном выражении неверно размещен знак операции", выработка сообщения "во входном выражении неверно размещен знак открывающей скобки"; выработка сообщения "во входном выражении неверно размещен знак закрывающей скобки"; выработка сообщения "конфликтное размещение операнда во входном выражении"; выработка сообщения "несоответствие числа открывающих и закрывающих скобок во входном выражении"; увеличение значения счетчика 4 операндов; занесение в и-разряд блока 5 памяти значения входного регистра; занесение в и-разряд блока 5 памяти значения счетчика 4 операндов; сдвиг влево на один разряд влево содержимого .блока 5 памяти; сдвиг enpaso на один разряд содержимого блока 5 памяти; занесение в 12 разряд выходного регистра 7 значения счетчика операндов; занесение в 11 разряд выходного регистра 7 значения кода =, занесение в 12 разряд выходного регистра 7 значения выходного регистра 1;

1742832 з

Y - занесение в 10 разряд выходного регистра 7 значения кода

I(l

Y - занесение в 16 разряд выходного регистра 7 значения кода

I) I

Y - занесение в пятый разряд выход" г6 ) ) ного регистра 7 значения (;

Y g - занесение в третий разряд выходного регистра 7 значения с Ъ

Y - занесение в первый разряд вы28 ходного регистра 7 значения

) г/ э ю

Y - занесение в девятый и второй

2Я разряды выходного регистра 7 значения (п-2.) разряда блока 5 памяти;

У - занесение в восьмой разряд выходного регистра значение .(n-1) разряда блока памяти;

Y - занесение в седьмой и четвертый разряды выходного регистра значение и-разряда блока памяти;

У - окончание и выдача всех 12 разрядов выходного регистра;

Y q . - окончание работы устройства;

Y>< - начало работы устройства.

Счетчик 4 операндов предназначен для нумерации операндов, встречаемых во входном выражении. Блок 5 памяти предназначен для записи, хранения и считывания кодов лексических единиц.

Запись кодой текущих "ш" производится в старшие и-е разряды регистров блока 5 памяти, сдвиг вправо на

k-разрядов равносилен затиранию k" .последних (старших) разрядов.

Дешифратор 6 блока памяти предназначен для формирования сигналов Хт - .

Х 4 на основе анализа старших разрядов блока 5 памяти. Выходной регистр

7 предназначен для записи, хранения и считывания преобразованных в peiyлярную форму, входных выражений..

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

При его включении блок 3 управле.ния вырабатывает микрооперацию УЗ<, после чего по управляющим шинам пос-. тупает набор микроопераций.

Y - обеспечивающих обнуление вход-

5 ного, регистра 1 (в дальнейшем возможно р1); . Y - блока 5 памяти, в дальнейшем, возможно р2); б

У - выходного регистра 7 (в дальнейшем возможно р3).

После этого происходит занесение в старший (n-й) разряд блока 5 памяти кода символа Ll (микрооперации Y ) по управляющей шине, связывающей блок

3 управления и блок 5 памяти. После этого вырабатывается микрооперация

У, разрешающая ввод очередной лексической единицы о входной регистра

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

Y и очередная лексическая единица б поступает на вход р1. Такая циклическая работа устройства происходит до тех пор, пока на вход входного регистра не поступит символ ф (признак конца исходного выражения, и блок 3 управления не произведет crieциальные действия для лексической единицы типа ф, после чего происходит окончание работы устройства (микрооперация Y>>).

Лексические единицы делятся на . типь1: операнды (символ типа Г, под

I которым подразумевается любой символ, представимый ЭВМ), операции (симй6л + + ) скобки. открывающие

Ф у с у ( и закрывающие (символы (, ) символLj, обеспечивающий любую сте-, пень разряжения пробелами исходного выражения.

Совокупность всех входных символов, поступающих на вход входного регистра 1, и хранящихся в регистрах блока 5 памяти, не выходят за пределы допустимого в любой ЗВМ алфавита. Это значит, что в состав блока памяти 5 входят стандартные 12-раз-, рядные реверсивные регистры 8 сдвига. Их количество определяется формулой преобразования, осуществляемого устройством: аМЬ (а+Ь)(аМЬ) и составляет 10 штук.

1742832 8

9<>), после чего генерируется микрокоманда по информационному заполнению выходного регистра 7., содержащая совокупность микроопераций: Y Z, Y

Y, Y>< .После выполнения данной микрокоманды производится выдача сформированного содержимого выходного регистра {Y>>), сдвиг вправо на три разряд блока 5. t4RT (Yzo Y«

У, ) и занесение в старший разряд блока памяти 5 значение счетчика . операндов 4 (Yy, Y ) Этим заканциваются действия по условию Х1 = 1.

После этого производятся еще 2 микрооперации: сдвиг влево на один разряд блока 5 памяти ("q>) и Ут, Y< - занесение в разряд памяти значения входного регистра 1. Этим заканчи20 ваются действия по входной лексической единице типа операции, Раскроем содержание двух применяемых микрокоманд. Микрокоманда по занесению первичного шаблока состоит

25 иэ совокупности микроопераций:

Y g - обнуление выходного регистра 7;

У - занесение в 11-й разряд р3 значение символа = ;

Y<+ - занесение в пятый разряд р3

ЗО значение символа (Y - занесение в третий разряд РЗ значение символа v, у - занесение в первый разряд р3

I значение символа )

Микрокоманда по информационному заполнению выходного регистра 7 состоит из совокупности микроопераций:

У. - занесение в 12-й разряд р3 значение сцетцика 4 операндов;

У - занесение в девятый и второй разряды р3 значение (n-2) разряда блока 5 памяти;

Y — занесение в восьмой(р3 значение (n-1) разряда блока 5 па-

45 мяти;

Y - занесение в седьмой и четвертый разряды р3 значения (n) разряда блока 5 памяти.

Рассмотрим работу устройства в зависимости оТ типа поступающих вход ных лексических единиц.

При поступлении лексической единицы-операнда (X=1) проверяется :,значение старшего разряда блока 5 памяти. Если это знацение равно одному из символов; F {операнд), ) (закрывающая скобка), {X qz = 1, Хц =

= 1), то блок 3 управления формирует микрооперацию У <

В противном случае управляющими срелствами блока 3 управления производится обнуление выходного регистра

7 {У ), увеличение значения счетчика

4 и операндов, занесение в 12-й разряд р3 значение этого счетчика: соот ветственно микрооперации (Y „ и. Yz<

После этого производится выдача содержимого блока 5 памяти по микроопе рации Y qZ и занесение в 11-й разряд выходного регистра 7 значение кода символа, =, (Уу, У ), занесение в 10-й разряд значение входного регистра pl (микрооперация Yp, Y>g) °

После этого блок," 3 управления форми рует микрооперации Yq< (сдвиг вправо содержимого блока 5 памяти на оди разряд) и Уу, Y 8 (занесение в старший разряд блока 5 памяти значение счетчика 4 операндов) .

При в поступлении лексической единицы - знака операции (символы +, Ф) (X> = 1) проверяется значение старшего разряда блока 5 памяти. Если это значение совпадает со значениями символов (+ (Хт,Х,Х1 = 1), то формируется сообщение об ошибке (микрооперация у, () °

В противном случае проверяется зна цение (п-1)"разряда блока 5 памяти.

Если это значение не содержит коды знаков операций +, М (Х y = О), блок управления вырабатывает последовательность микрокоманд и микроопераций для выполнения совокупности действий, которые рассмотрим подробнее.

I .

Сначала увеличивается значение счетчика 4 операндов (Y <6 ), затем выполняется микрокоманда по занесению в выходной регистр первичного шаблока (совокупность Y, Y

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

При поступлении лексической единицы ((открывающей скобки) происходит генерация и выполнение двух микроопераций: у У19 - сдвиг влево на один разряд содержимого блока 5 памяти;

Ут, У т - занесение в и-разряд блока

5 памяти содержимого входного регистра pl.

9 17

При поступлении лексической единицы ) (закрывающей скобки) проверяется значение старшего и-ro разряда блока 5 памяти. Если это значение равно значению символа ((Х о о

= 1), то выполняется Y - сдвиг влево на один разряд содержимого памяти. Если же значение и-разряда блока 5 памяти равно значению лексической единицы типа операнда (Х 1 =

= 1), то блок 3 управления генерирует для выполнения определенную последовательность микрокоманд и микроопераций. Вначале условие Х, = 1, если значение (и-3) разряда блока 5 памяти равно значению символа (, Х1г = 1, Х „ =- 1, то выполняется сдвиг вправо на два разряда содержимого блока 5 памяти и (Yz0 Yt0) в противном случае. (Х < — — 1, X.< = 1) проверлется значение р3 значение (n-1) разрядати. Если оно равно значению символа ((Х1 .= 1, Х = О, Х I = 1), то выполняется совокупность микроопераций и микрокоманд.

Вначале производится увеличение значения ряда содержимого блока 5 памяти (У2о, У ), затем выполняется описанная выше микрокоманда по залесению первичного блока в выходной регистр 7 (УФ Угг Уи Yzz У28) после чего происходит занесение в

10-й и 6-й разряды р3 соответственно значения символов (и ) (У,, Уг ), после чего выполняется микрокоманда по информационному запол. нению р3 (Y, У2ч» Уо Уз1) " . производится полная выдача сформиро ванного содержимого выходного ре- гистра (Yqq). После этого происходит сдвиг вправо на четыре разряда содержимого блока 5 памяти (Y, Y, У2О, Уг>). В слУчае невыполйенил последнего условия Х << = 1, X« = 0, Х 11 = О производится выполнение микрооперации Y << . Этим заканчиваются действия для лексической единицы а)юу

Рассмотрим работу устройства при поступлении специальных символов Lt, .l ф . Если лексическая единица представлена символом ъ1, то .блок 3 управления не вырабатывает никаких микроопераций по обработке данной лексической единицы, Если же лексическая единица представлена симвоУ м.А лом у- - знаком окончания исходного выражения, блок 3 управления выра42832 l0 батывает следующую совокупность действий. Сначала проверяется старший разряд блока 5 памяти. Если его содержимое равно значению одного из

5 символов Lt или F (лексическая !. кф единица типа операнд) (Х = 1 или

Х7 = 1), то выполняется совокупность микрокоманд и микроопераций для лекI сическои единицы g и выдается сообщение об ошибке (Y ). В случае корректности значения старшего разряда блока 5 памяти эта совокупность. действий представлена следующим

5 образом.

Если значение (и-1) — разряда блока 5 памяти равно u (Y 1 = 1), то происходит занесение в и-разряд блока 5 памяти значение символа ф

2О (YÄ Y ) .. Если же значение (и-1)разряда блока 5 памяти равно значению с ф символа ((Х <6 = 1), формируетсл сообщение об ошибке (У,5) . В противном случае (Хgg = О,. Х16 = О) прове рлется значение (и-2)-разряда блока

5 памяти и, если его содержимое совпадает с значением символа типа one-l Ф равд (F ), т.е. Y<<= 1, происходят слелующие действия. Увеличивается значение счетчика 4 операндов. {Y1 ), происходит занесение в р3 первичного шаблока (У, Yzz Yzo Y2 ), происходит занесение в 1О-й и о-й разряды р3 значений. символов { и ) соответственно (Yz и Yz ) информа35 ционное заполнение р3 (Y, Y 2, Y

Уз,) и выдача сформированного р3

{v г). После этого происходит сдвиг на три разряда содержимого блока 5 памяти (У2, Yzo, Yzо) и занесение в и разряд блока 5 памяти значение . символа ф (Y<, Y ). .Если же значение и-разряда блока 5 памяти равно лексической единице типа операнд (Х .= О), то происходит обыкновен45 ное занесение в разряд блока 5 памяти символа ф (У, ).

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

55 корректным (т.е. не возникли сигналы диагностики ошибок: Y o Y Y ).

Я ° фф Ф

Для символа ф сигналй У не вырабатываются, хотя сигналы диагностики ошибок могут возникнуть (сигнал Y ).

1742832

12 /

Поэтому для этого символа, при значении и разряда блока 5 памяти, pRBHoM 4 (X8 — 1 ) ) или отсутствии

Y „ вырабатывается микрооперация успешный перевод и Y - оконцание работы устройства, После возникновения сигналов Y 3a Y <3, Y<< ) также вырабатывается микрооперация

У 53.

Этой микрооперацией устройство завершает работу, Ф о р м у л а изобретения

Устройство для перевода арифмети-! ческих выражений s линейные регулярные префиксные формы, содержащее входной регистр, дешифратор входного регистра, блок управления, блок памяти и дешифратор блока памяти, причем информационный вход входного регист-; 20 ра является входом устройства, первый выход входного регистра соединен с входом дешифратора входного регистра, выход которого подключен к первому входу блока управления, первый выход которого соединен с управляющим входом входного регистра, второй и третий выходы блока управления являются выходами "Ошибка" и "Успешный перевод" устройства, соответственно, чет.вертый выход блока управления соеди30 нен с управляющим входом блока памяти, первый и второй выходы которого соединены с первым и вторым входами дешифратора блока памяти, соответственно, выход дешифратора блока памяти соединен с вторым входом блока управления, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения типов ошибок при одновременном повышении быстродействия, устройство содержит счетчик операндов и выходной регистр, причем второй выход входного регистра соединен с первым информационным входом выходного регистра, пятый выход блока управления подключен к первому управляющему входу выходного регйстра, шестой выход блока управления соединен с BTopblM третьим, четвертым, пятым, шестым и седьмым управляющими входами выходного регистра, третий выход блока памяти соединен с вторым информационным входом выходного регистра, четвертый выход блока памяти соединен с третьим и четвертым информационными. входами выходного регистра, пятый-выход блока памяти соединен с пятым и шестым информа-: ционными входами выходного регистра, выход которого является информационным выходом устройства, седьмой выход блока управления соединен со счетным входом счетчика операндов, выход которого подключен к седьмому информационному входу выходного регистра и информационному входу блока памяти.

1742832

Фиг. 2

Составитель Г. Смирнова

Ре1актор И,Ванюшкина Техред М.Моргентал Корректор О.Кравцова

Яаказ 2287 Тираж Подписное

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

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

Производственно †издательск комбинат "Патент", г.У@город, ул. Гагарина,101