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

(Я)5 г 06 Р 15/38 11/00 И АВТОРСКОМУ СВИДЕТОЗЬСТВУ регистр 7 .образуют восемь регистровс разрядностью не менее 12 разрядов.Входной регистр 1 используетсядля хранения очередной лексическойединицы вхрднаго. выражения (в дальнейшем будем обозначать.ее специальным символом "ш"), Дешифратор 2 лексических единиц разделяет поступающие "ш" на символы; пробел, знаки Ы операций, открывающие и закрываю- ОО щие скобки, знак конца выражения, (Гд операнды и вырабатывают,значение ко- Я . доя этих символов. Блок 3 управлениз управляет работой всех элементов ус 1 ройства, На первую группу входов д блока 3 управления поступают сигналы Х 1 - Х из лешифратора 2 лексических единицы, а на вторую группу входов- сигналы Х 7 - Х 7 из дешифратора 6блока памяти. На семи выходах блока 3 микропрограммного управления ФормиГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И СОНРЫТИЯМПРИ ЖНТ СССР(56) Авторское свидетельство СССРУ 1130879, кл, С 06 Р 15/38, 1.985,Авторское свидетельство СССРй 1439591, кл. С 06 Р 15/38, 11/00,1987.(54) УСТРОЙСТВО ДЛЯ ПЕРЕВОДА АРИФМЕТИЧЕСКИХ ВЫРАЖЕНИЙ В ЛИНЕЙНЫЕ РЕ"ГУЛЯРНЫЕ ПРЕФИКСНЫЕ ФОРМЫ Изобретение относится к вычисли-. тельной технике и может быть использовано в автоматизированных системах обработки данных, производства программ и разработки трансляторов ЭВМ.Целью изобретения является расши" рение функциональных возможностейустройства за счет определения типов ошибок при одновременном повышении быстродействия.На Фиг,1 представлена структурнаясхема устройства; на Фиг,2 - то же, блока памяти; на фиг,3 - то же, выходного регистра.Устройство содержит входной ре-:. ,гистр 1,. дешифратор 2 лексических единиц, блок 3 управления,счетчик 4 операндов, блок 5 памяти, дешифра" тор Ь блока памяти, выходной регистр 7. Блок 5 памяти построен на реверсивных регистрах сдвига. Выходной БО 1742832 А 11 2(57) Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных, производства программ и разработки трансляторов ЭВМ. Цель изобретения - расширение возможностей за счет определения типов ошибок при одновременном повышении быстродействия. Для этого в устройство введены счетчик 4 операндов и вы", ходной регистр 7. Введение этих элементов, а также использование в блоке 5 памяти реверсивных сдвигающих регистров оптимизирует алгоритм работы устройства, 3 ил.У,1о 15 Хц 2 г гю Хц Соде сигнала3 17428 руют сигналы микроопераций "- У.Содержательный смысл входных сигналов следующий. 1, если очередной символ естьзнак О; Х, = О, если в противном случае; 1, если очередной символ есть знак конца выражения ф Х = О,10 1, если очередной символ есть знак операции; 1, если очередной символ есть1знак15 х: о, 1, если очередной символ есть знак ф); Х = О, 1, если очередной символ есть операнд; Х 6 = О, в йротивном случае, Х = О, в противном случае, если содержимое и-разряда/ блока 5 памяти есть ;251, если содержимое и-.разряда блока 5 памяти естьф;О,1, если содержимое и-разряда,блока 5 памяти есть знак опе. - .рации;О,1, если содержимое и-разрядаблока 5 памяти есть С;Офесли содержимое и-разряда 351блока 5 памяти есть );О,1, если содержимое и-разрядаблока 5 памяти есть Р0 в противном случае, 461, если знацение (и) разряда блока 5 памяти есть 2;0 в противном случае,1, если значение (и) разряда .блока 5 памяти есть знак операции;0 в противном случае,1, если значение (и)-разрядаблока 5 памяти есть (0 в противном случае1, если значение (и)-разрядаблока 5 памяти есть 10 в противном случае,1, если значение (и)-разряда блока 5 памяти есть (; 550 в противном случае. ржательный смысл выходных следующий: сброс в ноль входного регистра1;сброс в ноль регистров блока 5памяти;сброс в ноль выходного регистзанесение в и-разряд регистровблока 5 памяти значение кодазнака;занесение в и-разряд блока 5памяти значения, ф;разрешение ввода следующей лексической единицы "ш" во входнойрегистр 1;разрешение записи в блок 5 па"мяти;выработка сообщения. "успешныйанализ";выработка сообщения "ошибка";выработка сообщений "во входномвыражении неверно расположензнак конца выражения",выработка сообщения "во входномвыражении неверно размещензнак операции";выработка сообщения "во входномвыражении неверно размещен знакоткрывающей скобки";выработка сообщения "во входномвыражении неверно размещен знакзакрывающей скобки";выработка сообщения "конфликтное размещение операнда во входном выражении";выработка сообщения "несоответствие числа открывающих изакрывающих скобок во входномвыражении";увеличение значения счетчика 4операндов;занесение в и-разряд блока 5памяти значения входного регистра;занесение в и-разряд блока 5памяти значения счетчика 4 операндов;сдвиг влево на один разрядвлево содержимого .блока 5 па"мяти;сдвиг вправо на один разрядсодержимого блока 5 памяти;занесение в 12 разряд выходногорегистра 7 значения счетчикаоперандов;занесение в 11 разряд выходногорегистра 7 значения кода: ,занесение в 12 разряд выходного регистра 7 значения выходного регистра 1;)(ФУ - занесение в 16 разряд выходного регистра 7 значения кода.У - занесение в пятый разряд выход"г 6 ) )ного регистра 7 значения (; у т - занесение в третий разрядвыходного регистра 7 значениясЪУ - занесение в первый разряд вы 28ходного регистра 7 значения(и) разряда блока памяти;7 - занесение в седьмой и четвертый разряды выходного регистразначение и-разряда блока памятиУ - окончание и выдача всех 12 разрядов выходного регистра; У- окончание работы устройства; У,1 - начало работы устройства.Счетчик 4 операндов предназначен для нумерации операндов, встречаемых во входном выражении, Блок 5 памяти предназначен для записи, хранения и считывания кодов лексических единиц, Запись кодой текущих "ш" производится в старшие и-е разряды регистров блока 5 памяти, сдвиг вправо на К-разрядов равносилен затиранию Ъ" .последних (старших) разрядов.Дешифратор б блока памяти предназначен для формирования сигналов МтХна основе анализа старших разрядов блока 5 памяти. Выходной регистр 7 предназначен для записи, хранения и считывания преобразованных в регулярную форму, входных .выраженийУстройство работает следующим., образом. При его включении блок 3 управле.ния вырабатывает микрооперацию УЗ,после чего по управляющим шинам поступает набор микроопераций,У - обеспечивающих обнуление вход"5,ного, регистра 1 (в дальнейшемвозможно р 1);.щрможно р 2); бУ - выходного регистра 7(в дальнейшем возможно р 3).После этого происходит занесение в старший (и-й) разряд блока 5 памяти кода символа О(микрооперации У) по управляющей шине, связывающей блок 3 управления и блок 5 памяти, После этого вырабатывается микрооперация У, разрешающая ввод очередной лексической единицы о входной регистра 1. Лексические единицы исходного выражения последовательно поступают на входной регистр 1 и затем - на дешифратор 2 лексических единиц, который вырабатывает их коды и йересылает значения последних в блок 3 управления. В зависимости от типа лексической единицы блок 3 управления производит последующую отработку ф исходной информации и производит последовательность микрокоманд и микро- операций, адекватных данному типу лексической операции, после чего вновь вырабатывается микрооперация У и очередная лексическая единица бпоступает на вход р 1, Такая циклическая работа устройства происходит до тех пор, пока на вход входного регистра не поступит символ ф (приз" нак конца исходного выражения, и блок 3 управления не произведет специальные действия для лексической единицы типа ф , после чего проис" ходит окончание работы устройства (микрооперация У) .Лексические единицы делятся на . типы: операнды (символ типа 1 Р , под которым подразумевается любой символ, представимый ЭВМ), операции (символ + )+) скобки. открывающиеФи закрывающие (символы ( ,символ О, обеспечивающий любую сте", пень разряжения пробелами исходного выражения. Совокупность всех входных символов, поступающих на вход входного регистра 1, и хранящихся в регистрах блока 5 памяти, не выходят за пре- делы допустимого в любой ЭВМ алфави" та. Это значит, что в состав блока памяти 5 входят стандартные 12-раз-, рядные реверсивные регистры 8 сдвига, Их количество определяется формулой преобразования, осуществляемого устройством:амЪ = (а+Ь)(аМЬ)и составляет 10 штук.1742832 81), после чего генерируется микрокоманда по информационному заполнениювыходного регистра 7., содержащаясовокупность микроопераций: У, УУО, У .После выполнения данноймикрокоманды производится выдачасформированного содержимого выходногорегистра (У), сдвиг вправо на триразряда блока 5 памяти (У 2 о гоУ, ) и занесение в старший разрядблока памяти 5 значение счетчика .операндов 4 (У 7, 71); Этим заканчиваются действияпо условию Х 1 = 1,После этого производятся еще 2 микрооперации: сдвиг влево на один разрядблока 5 паияти (") и Ут, У - занесение в разряд памяти значениявходного регистра 1. Этим заканчи 20 ваются действия по входной лексической единице типа операции,Раскроем содержание двух приме"няемых иикрокоманд. Микрокоманда позанесению первичного шаблока состоит25 иэ совокупности микроопераций;7- обнуление выходного регистра 7;Ф " занесение в 1-й разряд р 3 значение символа =;у- занесение в пятый разряд р 3Зо значение символа (У - занесение в третий разряд Р 3значение символа ч;занесение в первь 1 й разряд р 31значение символа )35Микрокоманда по информационномузаполнению выходного регистра 7 сос"тоит из совокупности иикроопераций:у - занесение в 12-й разряд р 3 значение счетчика 4 операндов;У - занесение в девятый и второйразряды р 3 значение (и) разряда блока 5 памяти;У - занесение в восьмойр 3 значение (и) разряда блока 5 па-4мяти;7, - занесение в седьмой и четвертыйразряды р 3 значения (и) разряда блока 5 памяти. Рассмотрии работу устройства взависимости от типа поступающих входных лексических единиц,При поступлении лексической единицы-операнда (Х=1) проверяется:,значение старшего разряда блока 5памяти. Если это значение равно о- ному из символов; Р (операнд), )= 1), то блок 3 управления формируетмикрооперацию У.В противном случае управляющимисредствами блока 3 управления производится обнуление выходного регистра7 (У), увеличение значения счетчика4 и операндов, занесение в 12-й разряд р 3 значение этого счетчика: соответственно микрооперации (7и УПосле этого производится выдача содержимого блока 5 памяти по микрооперации Уи занесение в 11"й разрядвыходного регистра 7 значение кодасиивола, = , ( Уу, У), занесениев 10-й разряд значение входного регистра р 1 (микрооперация У, Уд).После этого блок,"3 управления формирует микрооперации У (сдвиг вправо содержимого блока 5 памяти на одиразряд) и У 7, Ущ (занесение в старший разряд блока 5 памяти значениесчетчика 4 операндов) .При в поступлении лексическойединицы - знака операции (символы1+, Ф) (Х= 1) проверяется значение старшего разряда блока 5 памяти. Если это значение совпадает созначениями символов 1( +(Х 7 ХчХ 1 д - 1) 1 то Формируетсясообщение об ошибке (микрооперацияУ, )ф. В противном случае проверяется значение (п"1)"разряда блока 5 памяти.Если это значение не содержит кодызнаков операций +,М (Х 1 = О),блок управления вырабатывает последовательность микрокоманд и микроопераций для выполнения совокупностидействий, которые рассмотрим подробнее.3,Снацала увеличивается значениесчетчика 4 операндов (У), затемвыполняется микрокоманда по занесениюв выходной регистр первичного шаблока. (совокупность У, У, У 6, Урв) затем происходит занесение в 10-й разрядный р 3 значение символа. ( , а вб-й разряд р 3 " значение символа(соответственно микрооперации У и Устройство работает следующим об разом.При поступлении лексической единицы ф( (открывающей скобки) происхо"дит генерация и выполнение двух микроопераций:55 У 9 - сдвиг влево на один разряд содержимого блока 5 памяти:.ут, у,т - занесение в п-разряд блока5 памяти содержимого входного регистра р 1.Э 17При поступлении лексической единицы ) (закрывающей скобки) проверяется значение старшего и-го раз"ряда блока 5 памяти. Если это значение равно значению символа ( (Х о10= 1), то выполняется У - сдвигвлево на один разряд содержимогопамяти, Если же значение и-разрядаблока 5 памяти равно значению лексической единицы типа операнда (Х 1 == 1), то блок 3 управления генерируетдля выполнения определенную последовательность микрокоманд и микроопераций. Вначале условие Х, = 1, еслизначение (и) разряда блока 5 памятиравно значению символа ( , Х,г, = 1,Х=. 1, то выполняется сдвиг вправона дваразряда содержимого блока 5памяти и (У, Уг), в противномслучае. (Х-- 1, Х. = 1) проверяетсязначение р 3 значение (и) разрядати. Если оно равно значению символа( (Х 1.= 1, Х = О, Х = 1), товыполняется совокупность микроопераций и микрокоманд,Вначале производится увеличениезначения ряда содержимого блока 5 памяти (Уо, У ), затем выполняетсяописанная выше микрокоманда по занесению первичного блока в выходнойрегистр 7 (УФ, Уггф Угб Угу Уу 8) фпосле чего происходит занесение в10-й и 6-й разряды р 3 соответственнозначения символов (и ) (У,. Уг), после чего выполняется микрокоманда по информационному заполнению РЗ (Ур У 29 У о Уупроизводитсяполная выдача сформиро ванного содержимого выходного ре-гистра (У). После этого происходитсдвиг вправо на четыре разряда содержимого блока 5 памяти (У У,Уго, Уго). В случае невыполйейия последнего условия Х= 1, Х 1 = О,Х 1 = 0 производится выполнениемикрооперации У. Этим заканчивают"ся действия для лексической единицыа)юуРассмотрим работу устройства при поступлении специальных символов О, 3. Если лексическая единица представлена символом О, то блок 3 управления не вырабатывает никаких микроопераций по обработке данной лексической единицы, Если же лексическая единица представлена симвоФ,и.йлом ж - знаком окончания исходного выражения, блок 3 управления выра 42832 10 батывает следующую совокупностьдействий. Сначала проверяется старший разряд блока 5 памяти. Если егосодержимое равно значению одного из 5символов О 1 или Г (лексическаяУГ Фединица типа операнд) (Х= 1 илиХ 7 = 1), то выполняется совокупностьмикрокоманд и микроопераций для лексрсическои единицыи выдается сообщение об ошибке (У,1). В случаекорректности значения старшего разряда блока 5 памяти эта совокупностьдействий представлена следующим 15 обра,зом.Если значение (и) - разрядаблока 5 памяти равно 13 (У-- 1),то происходит занесение в и-разрядблока 5 памяти значение символа20 (Ут, У)Если же значение (и)- разряда блока 5 памяти равно значениюс ксимвола ( (Х 6 = 1) . формируетслсообщение об ошибке (У, ). В противном случае (Х 1 = О,. Х 16 = 0) прове"рлется значение (и)-разряда блока5 памяти и, если его содержимое сов"падает с значением символа типа опе- .равд ( Р ), т.е, У= 1, происходятслеиующие действия, Увеличиваетсязначение счетчика 4 операндов.(У 1 ),происходит занесение в р 3 первичногошаблока (У Угу, УгоУг ), происходит занесение в 1 О-й и о-й разряды р 3 значений. символов ( и )соответственно (Уг и Уг) информа ционное заполнение р 3 (У , У, УУз,) и выдача сформированного р 3(Уг). После этого происходит сдвигна три разряда содержимого блока 5памяти (Уг, Уго, Уго) и занесение 4 О в и разряд блока 5 памяти значение .символа ф(У, У ). Если же значе"ние и-разряда блока 5 памяти равнолексической единице типа операнд(Х . = О), то происходит обыкновен ное занесение в разряд блока 5 памяти символ.а ф (У, -)После генерации совокупностидействий длл различных лексическихединиц, кроме символа ф блок 3 уп- И равления вырабатывает сигнал Уlразрешение ввода следующей лексической единицы в р 1) лишь в том случае если исходное выражение доэтой лексической единицы является 5 корректным (т.е, не возникли сигналыдиагностики ошибок: У У ,У ),цре 1 у ю 1 фДля символа ф сигналй У не вырабатываются, хотя сигналы диагностики ошибок могут возникнуть (сигнал У),1712832 ОлеюжФ 8 1 5 юобча,го релгстрс . Составитель Г. Смирнова1 актор И,Ванюшкина Техред М,Моргентал Корректор О.Кравцов КИТ ССС роизводственно в издательск комбинат "Патент", г,ужгород, ул. Гагарина,10 Яаказ 2287ВНИИПИ Государс Тираженного комитета по изо13035, Москва, Ж, Р Подписноеетениям и открытиям пушская наб., д, 4 Л