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

(19) 111)51)5 С 06 Р 15 1616 РЕТЕ ТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТЙЯМПРИ ГКНТ СССР ОПИСАНИЕ Н АВТОРСНОМУ СВ 1(56) Авторское свидетельство СССР Нф 890403, кл. С 06 Р 15/38, 1978.Авторскде свидетельство СССР В 1130879, кл. С 06 Г 15/38, 1982. (54) УСТРОЙСТВО ДЛЯ ПЕРЕВОДА .ВЬ)РАИ. - НИИ В ПОЛЬСКУЮ ИНВЕРСНУЮ ЗАПИСЬ (57) Изобретение относится к вычисли тельной технике и может быть использовайо в автоматизированных системах обработки данных и производства программ для ЭВИ. Цель изобретения - расширение Функциональных возможностей за счет обеспечения преобразова 2 ния арифметических выражений, содержащих кроме бинарных операций двух приоритетов (сложение, вычитание - первый приоритет; умножение, деление - второй приоритет) бинарную операцию третьего приоритета (возведение в степень), унарные операции (знаки "плюс" и "минус") и логические операции "И", "ИЛИ", "НЕ", а также обеспечение полноты контроля, повышение быстродействия и сокращение аппаратурных затрат. Для достижения цели в устройство введены три дешиАратора 5, 6 и 7 и блок 11 элементов И. Благода ря совмещению процессов преобразования выражении и обнаружения ошибок, а также существенному упрощению блока Я 3 микропрограммного управления в устройстве реализованы указанные преиму- Я ф щества, 3 ил 5 табл.1571616 1, если находящаяся в регистре 1 лексическая единица есть операнд; О, в противном случае;1, если находящаяся в регистрескобка; .О, в противном случае; 1, если находящаяся в регистре 1 лексическая единица есть энак плюсили минус; О, в противном случае; Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных и производства программ для ЭВМ.Цель изобретения - расширение Функциональных возможностей устройства эа счет обеспечения преобразования арифметических выражений с тремя уровнями приоритета бинарных операЦий; с логическими и унарными операциями, при одновременном обеспечении Полноты контроля, повышении быстродействия и сокращении аппаратурных Эатрат.На фиг. 1 представлена структурная схема предлагаемого устройства; на Фиг. 2 - структурная схема блока памяти; на Фиг. 3 - блок-схема микро" 20 программного управления устройством.1Устройство (фиг. 1) содержит входной регистр 1, дешифратор 2 лексических единиц, блок 3 микропрограммного управления, блок 4 памяти,пер вый дешифратор 5 (основ), второй дешифратор 6 (основ), третий дешифратор 7 (основ), блок 8 сравнения, коммутатор 9, выходной регистр 10, блок 11 элементов И. Входной регистр 1 хранит очередную лексическую епиницу исходного выражения. Дешифратор 2 лексических единиц разделяет единицы на,операнды, операции и скобки. 135Блок 4 памяти -память с последовательным безадресным принципом чтения с обеспечением возможности доступа для чтения к трем старшим разрядам, Блок 4 памяти может быть выпол нен на реверсивных регистрах сдвига, которые осуществляют запись формируемых. блоком 3 микропрограммного управления и входным регистром 1 кодов лексических единиц в старшие И-е раз ряды, хранение записанной информацйи,поразрядный сдвиг содержимого влевоили вправо, выдачу записанной информации из И (И), (И) разрядовПервый дешифратор 5 (основ) выделяет основы анализируемого выражения,включающие группу из трех единицн, нГР , где Р - код операнда; символ- код бинарной операции.Второй дешифратор 6 (основ) выделяет основы анализируемого выраженияследующих видов: "Р", "(Г", "ОГ",где символ - код унарной операции; (Р - код открывающей скобки;О - код пустого символа,Третий дешифратор 7 (основ) выделяет основы вида "Г" и " )", гдесимвол ")" - код закрывающей скобки,Блок 8 сравнения осуществляетсравнение приоритетов текущего и пре. -дыдущего кодов лексических единиц,хранящихся соответственно в (И)-мразряде блока 4 памяти и во входномрегистре 1.Коммутатор 9 управляет передачамилексических единиц между блоками устрой -ства и обеспечивает поступлениелексических единиц иэ входного регистра 1 иблока 4 памяти в выходной регистр 10..Выходнои регистр 10 предназначендля хранения лексической единицы,которая может поступать иэ входногорегистра 1 или из (И)-го разрядаблока 4 памяти. Поступление лексической единицы в регистр 10 осуществляется в том порядке, который имеетместо для польской инверсной записиисходного выражения.Блок 3 микропрограммного управления (ИПУ) управляет работой всех элементов устройства. Алгоритм функционирования бпока, 3 ИЛУ описан блоксхемой микропрограммного управления(фиг.З), где содержательный смыслвходных (Х) и выходных сигналов Уследующий: лексическая единица есть открывающаяся1571616 1, если содержимое последнего разряда реверсивного регистра блока 4памяти является кодом операнда или кодом закрывающей скобки; О, в противном1, если в двухосновы "фР";О, в противном1, если в трехИранслучае;последних разрядах блока 4 памяти находится код случае;последних разрядах блока 4 памяти находится код основы О, в противном случае;1., если в двух последних разрядах блока 4 памяти находится код основын(1 7 О, в противном случае;1, если находящаяся в региетрескобка; О, в противном случае;1, если находящаяся в региходкого выражения "ф; е лексическая единица есть знак конца ис" е; О, в противном слу 1, если значение к ряде блока 4 памят жащейся во входном я в (К" 1)-м раз единицы, содерлексическои единицы, содержащебольше значения кода лексическо гистре 1; О, с противном случа1, если в двух после1 ОР 1 разрядах блока 4 памяти содержится код основы и О, в противном случае;У, - сброс в нуль регистров блока 4 памятУ - ввод очередной лексической единицы вУ - запись кода нетерминала "Г в И раз3У - запись содержимого входного регистраФУ - переключение коммутатора 9 на запись лрегистра 1 в выходной регистр 10;У - переключение коммутатора 9 на записьряда блока 4 памяти в выходной регисУ - изменение кода приоритета лексическо(устранение неоднозначности лексичесУ - сдвиг на 1 разряд вправо (в сторону1гистров блока 4 памяти;Уз - формирование сигнала "Входное вырУ, - формирование сигнала нормального входной регист яд блока 4 памя 1 в И разряд бл ексической един и; ка 4 памяти;цы из входного з (М) ра ской единицы лекси р 10; един цы во входном регистре 1ниц);разрядов) содержимого ре тарши ажение содержит ошибку";завершения процесса перево связи с тем, что встречаемая в дном выражении унарная операция нарная операция определяются оди тем же символом входного алфато их различать можно только и и ним в Входные сигналы Х(,ХтвХЗФ Х и Х 5 формируются дешиФратором 2 лексичес ких единиц. Сигнал Х формируется третьим дешифратором 7 (основ), сигналы Х,Х,Х , - вторым дешифратором 6 (основ), сигнал Х- первым дешифратором 5 (основ), сигнал Х 1 - бло1 оком 8 сравнения. Выходные сигналы (микрокоманды) с У., по У формируются блоком 3 микропрограммного управления. лексическая единица есть закрывающаяся Алгоритмом функционирования предусматривается бинарный четырехраэрядный код лексических единиц (табл. 1) . При этом первые три разряда однозначно определяют код приоритета лексической единицы, 1571616контексту. Для .устранения этой неоднозначности входных выражений в устройстве предусматривается проверка условия (ХЛХ ) и выполнение команды УВ случае истинности условия Х ЛХ (т,е. когда операция по контексту является унарной) производится формирование кода унарной операции путем из- О вменения приоритета (инвертированием значения разрядов регистра 1, содер- .1 кащих код приоритета). Такие же процедурыустранения неоднозначности входных выражений выполняются и для унарной операггии +.Устройство работает следующим образом.При включении устройства блок 3 ИПУ вырабатывает управляющий сигнал г - сброс в нуль содержимого регистров блока 4 памяти, На следующем шаге блок, 3 вырабатывает управляющий сигНал г - ввод очередной лексической единицы исходного выражения во вход ной регистр 1. Затем лексическая единица поступает на дешифратор 2 лексических единиц и блок 8 сравнения. При .этом дешифратор разделяет их на операнды, операции, скобки открывающие, скобки .закрывающие и конец выражения.Если поступавшая во входной регистр 1 лексическая единица есть операнд, то дешифратор 2 лексических единиц вырабатывает сигнал Х,=1, который запускает блок 3 МНУ. Управляющие сиг.налы (микрокоманды г и У ) блока 3 ИПУ переключают коммутатор 9 на запись операнда иэ регистра 1 в выходной регистр 19 и осуществляют эаггись 40 кода нетерминала "Р" в И разряд блока 4 памяти. Затем блок 3 МПУ вырабатывает управляющий сигнал ввода следующей лексической единицы но входной регистр 1 (микрокоманду г г).Если поступившая во входной регистр 1 лексическая единица есть открывающая скобка, то дешифратор 2 лексических единиц вырабатывает сигнал Х 1=1, который запускает блок 3 МПУ на выработку управляющих сигналов записи открывающейся скобки извходного регистра 1 в И разряд блока 4 памяти (микрокоманда г.г) и ввода следующей лексической единицы во входной регистр 1 (микрокоманда У).Если поступившая во входной регистр 1 лексическая единица есть закрывающая скобка нли произвольная операция, эа исключением операции плюс и минус то дешифратор 2 лексических единиц вырабатывает сигнал Х =О, Выполняемые н этом случае действия по управлению процессом записи лексических единиц иэ входного регистра 1 в блок 4 памяти или записи иэ блока 4 памяти в выходной регистр 10 осуществляются в зависимости от значения входных сигналов Х,Х ,ХХ и Хг Формируемых соответственно дешифраторами (оснон) 5 и 6 (Х ,Х7 и Х), дешифратором 2 лексических единиц и блоком 8 сравнения.Если поступившая во входной регистр 1 лексическая единица есть операция плюс или минус, то дешифратор 2 лексических единиц вырабатывает сигнал (Х =1), который указывает на возможную неоднозначность поступившей на вход операции. Последующие действия выполняются н зависимости зт значения входного сигнала Х, формируемого дешифратором 7 (оснон).Если Х=1, т.е. содержимое И-го разряда блока 4 памяти является кодом нетерминала "Г" или закрывающей скобкой, то операция плюс или минус идентифицируется как бинарная и последующие действия выполняются устройством н зависимости от значения входных сигналов Х ,Х , Хи Х;, формируемьп соответственно дешифратором 6 и 5 (основ) и блоком 8 сраннения. Это действия по управлению процессом записи%операции из входного регистра н блок 4 памяти и из блока 4 памяти н выходной регистр 10. Они описываются ниже. идентифицируется как унарная и блок 3 МПУ вырабатывает микрокоманду г изменение кода приоритета операции, находящейся во входном регистре 1, а затем выполняются те же описываемые ниже действия, что и при Х.Действия устройства по управлению процесса записи операции из входного регистра 1 н блок 4 памяти и из блока 4 памяти н выходной регистр О являются следующими.Если Х =1, т.е. в (М-) и И разрядах блока 4 памяти содержится код основы "Р", то блок 3 11 ПУ вырабатывает микрокоманду Уг, в соответствии с которой коммутатор 9 переключается на запись кода операции из (И) -го разряда блока 4 памяти н выходной регистр 1), а затем осуществляет сверт 1571616 1,Оку основы "фГ" в "Г" (микрокоижща У Уэ). Свертка производится пущем сдвига содержимого регистра блока 4 памяти йа один разряд вправо что соответствует затиранию .самой старшей лексическоч единицы основы "фГ" и последующей записи кода нетерминана "Г" в .И разряд блока 4 памяти. Выполнение микрокоманд У и УУз повторяет- О10 ся до тех пор, пока дешифратор основ 6 не выработает сигнал Х .=О.Если Х=), Х=1, Х=1, те. в трех старших разрядах блока 4 памяти содержится код основы "ГГ" и приори,15 тет операции ", находящейся в (И) разряде блока 4 памяти, .больше приоритета лексической единицы входного регистра 1, то блок 3 ИПУ вырабатывает микрокоманду УУ 87, В соответствии 2 О с эточ командой коммутатор 9 переключается на запись кода операции из .(М)-го разряда блока 4 памяти в выходной регистр 1 О и затем осуществляется свертка кода основы "ГГ" в "Г". Эта свертка производится путем сдвига содержимого регистров блока 4 памяти на 2 разряда вправо (микрокоманда У У) . Выполнение микрокоманды УУУ повторяется до тех пор, пока не будет сформирован один иэ трех сигналов: Хэ=1, Х =О и Х, =О.Если Х =1, то выполняются действия, описанные выше. Если Х =О и Х =О или Х =О и Х=1, при этом Х .=Л, т.е. приоритет кода операции ", находящейся в (И) -м разряде блока 4 памяти, меньше приоритета лексической единицы входного регистра 1, то блок 3 ИПУ вырабатывает микрокоман О ду У. - запись содержимого регистра 1 в старший разряд блока 4 памяти, а затем вырабатывает микрокоманду У ввод следующей лексической единицы во входной регистр 1.45Если Х-О и Х-О, но значения входных сигналов Х. и Х равны единице, т.е. в (11-1) и М разрядах блока 4 па 1 / 1 мяти содержится код основы ( Г , а во входном регистре 1 находится лексиче ск ая единица - закрывающаяся скобка , то блок 3 ИПУ вырабатывает микро- команду у у. э - свертку основы вида с " ( Г " в Г , а затем вырабатывает микрокоманду У- ввод очередной лекснче ской единицы во входной регистр 1,Устройство осуществляет перевод входного выражения в инв ерсную польскую запись до тех пор , пока дешифра" тор 2 лаКсЮЧасщвведр 9 щне вЫработаетсижал Х, Ф и дщщфрутор":б (:основ) не выработает,сигнал Х д 1, т.е, пока во входной регистр 1 не поступит знак конца,выражения ф и пока в блоке 4 памяти не будет произведен сброс в нудь всех разрядов,;цачимая от 1 до (И) включительно,. Выработка сигнала Х =1 определяется необходимостью записи всех находящихся в блоке 4 памяти кодов операций в выходной регистр 10.Запись операций в регистр 1 О осуществляется из (0-1) разряда блока 4 памяти, При этом каждая такая запись сопровождается освобождением старших разрядов блока 4 памяти от кодов логических единиц, используя свертку "Г" в "Г" или свертку "ГГ" в "Г в зависимости от сформированного в текущий момент одного из двух сигналов: Х д 1 или Х=1.В том случае, если во входном регистре находится знак конца выражения, а в (Я) разрядах блока памяти не содермются лексических единиц, т.е. Х=1 и Х=1, то блок 3 ЗПУ формирует сигнал Нормальное завершение процесса" (микрокоманда У), вырабатывается сигнал "Останов" и процесс перевода исходного выражения в инверсную польскую запись прекращается.В том числе, если во входной регистр поступил знак конца выражения, но (Л) младших разряда не освобождены от лексических единиц (Х =О) и при этом дешифраторами 5 и 6 (основ) сформированы сигналы Х =О и Х =О, т.е. не выполняется ни одна из разрешенных сверток, то блок 3 МПУ вырабатывает сигнал Входное выражение содержит ошибку" (микрокоманда У), формируется сигнал Останов и устройство прекращает работу.Работу предлагаемого устройства дополнительно проиллюстрируем на нескольких примерах. Лля наглядности процесс преобразования исходных выражений будем описывать пошагово, представляя на каждом шаге содержимые: входного регистра 1,. блока 4 памяти и выходного регистра 1 Л, а также задействованные при этом входные сигналы и микрокоманды.П р и м е р 1. Пусть исходное выражение имеет вид (а+Ь)хсзр, где а,Ь,с - операнды; "+","х" - знаки операций; Ф - символ конца выражения.13 1571616 10 Таблица 1 Лексические Код лексической Приоритет Примечаниеединицы единицы Несущест- Используется в кавен честве кода пустого символа 0000 0001 Несуществен112 0010 0011 О 00 Коды бинарных операций + ив 2 3 3 4 Несуществен5 0101 0110 0111 1000 1001 х Код не используетсяКоды унарных опе раций + и -1010 5 6 Несущест- вен 1011 1100 1101 Используется в качестве кода операнда (Г)7Несущест- вен 1110 1111 Т а б л и ц а 2 Содержимоевыходногорегистра 10 Задействованные выходныесигналы Содержимое блока 4 паСостояние Сое ржико евходногорегистра Шаг входныхсигналов мяти УУФУ 1РзУ 0операциями, при одновременном обеспечении полноты контроля, повышениибыстродействия и сокращении аппаратурных затрат, в устройство введены тридешишратора и блок элементов И, причем первый вход блока элементов И соединен с выходом входного регистра,шестой выход блока микропрограммногоуправления соединен с вторым входомблока элементов И, выход которогосоединен с информационным входом блока памяти, второй выход которого соединен с входом первого деширатора ипервым входом второго дешираторасоответственно, первый выход блокапамяти соединен с входом третьего дешийратора и вторым входом второго дешиАратора соответственно, третий выход блока памяти соединен с третьимвходом второго дешийратора, выходыпервого, второго и третьего дешиФраторов соединены с третьим, четвертым ишестым входами блока микропрограммного управления соответственно,. Продолжение табл. 2 15 1571616 Состояниевходных сигналов Содержимое Содержимое блока 4 па- выходного мяти регистра 1 0 ррррррррсьрррррррр 4 5 Ъ Ь аЬаЪсаЬс 7 с.8 Ф910, Ф11. Ф ХЛХ 1 ХЬЛХэ 1 1Ьс-хЪс-х+Ьс-х+ Содержимо выходного Состоянивходныхсигналов Со бл па жим т егистра(р а М аЪЧ аЬч аЬч апч чаЬч 1 7 ) 8 ) 9 Ф 0 Ф ица 5 Т 2 Х =1 Х =1 Х,=О ррррГрррррр 5 Х 2=1Х,-1, ХаЬ аЬсаЬсаЪс 7 с 3 4 9 Ф Х =1Х,ЛХ -1 Х =1,Х =0 6 ) 7 . ) 8 х 9 с 10 В 11, Ф 1 баг Содержимоевходногорегистра 1 Наг Содержимовходного регистра Х 1 Х ЛХ,1Х 0зХЛХ ЛХЬ, 1Х ИХ,. =1 11,Х 11Х =1,1 Х =0эХ 2=1Х щ 1Х,=1Х,Х,ЛХ=Х,1 Х =1Х 1 Х =1Х,ЛХ,=1 в УвУэТ 2 2 Э 2 Э 22 " 2 В 2 В 16 . Задействованные выходныесигналы 7142757 зУвам1 тТ 2РЗ 2Рз,вТЬУ 7 уУв16 Задействованные выходныесигналы Рз 2767253 2сУьВ с в 2с 16 РР 2 сЮУ 2 УьУ 2 5 Р УЬУ 2 1ТЗ,Ь с" Р У1511616 дфащралщвд 6 Составитель И.Поливодереда Техред М,Дидьпс ректор М,Пожо Редакто роизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,Заказ 1514 Тираж 572НИИПИ Государственного комитета113035, Москва Ж Подписноеизобретениям и открытиям при ГКНТ С Раушская наб д, 4/5