Устройство для перевода выражений в польскую инверсную запись Советский патент 1990 года по МПК G06F17/27 

1, если находящаяся в регистре 1 лексическая единица есть операнд;

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

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

Y

Лу

ХГ

V

лексическая единица есть открывающая

V.O, в противном случае;

Г1, если находящаяся в регистре 1

скобка;

10, в противном случае;

1, если находящаяся в регистре 1 лексическая единица есть знак плюс или минус;

0, в противном случае;

лексическая единица есть открывающаяся

J

515716166

1, если содержимое последнего разряда реверсивного регистра блока 4 памяти является кодом операнда или кодом закрывающей скобки;

V

V

0,в противном случае;

1,если в двух последних разрядах блока 4 памяти находится код основы

0,в противном случае;

1,если в трех последних разрядах блока 4 памяти находится код основы

0, в противном случае;

Ц если в двух последних разрядах блока 4 памяти находится код основы

V

х„

1 лексическая единица есть закрывающаяся

,0, в противном случае; 1, если находящаяся в региетре скобка;

.0, в противном случае;

1, если находящаяся в регистре лексическая единица есть знак конца исходного выражения

t

0,в противном случае;

1,если значение кода лексической единицы, содержащейся в (Н-1)-м разряде блока 4 памяти, больше значения кода лексической единицы содержащейся во входном регистре 1;

Мо

0,с противном случае;

1,если в двух последних разрядах блока 4 .

Х« п

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

Y, - сброс в нуль регистров блока 4 памяти;

YJ - ввод очередной лексической единицы во входной регистр 1;

Y. - запись кода нетерминала F в N разряд блока 4 памяти;

Y. - запись содержимого входного регистра 1 в N разряд блока 4 памяти;

Y. - переключение коммутатора 9 на запись лексической единицы из входного регистра 1 в выходной регистр 10;

Y, - переключение коммутатора 9 на запись лексической единицы из (N-1) разряда блока 4 памяти в выходной регистр 10;

Y7 - изменение кода приоритета лексической единицы во входном регистре 1 (устранение неоднозначности лексических единиц);

Y. - сдвиг на 1 разряд вправо (в сторону старших разрядов) содержимого регистров блока 4 памяти;

Y9 - формирование сигнала Входное выражение содержит ошибку ;

YU - формирование сигнала нормального завершения процесса перевода.

Входные сигналы X(,X1,XJ, Xg и Х формируются дешифратором 2 лексических единиц. Сигнал Х4 формируется третьим дешифратором 7 (основ), сигналы Xj,X.j,X и - вторым дешифратором 6 (основ), сигнал X - первым дешифратором 5 (основ), сигнал Х1о - бло- ком 8 сравнения. Выходные сигналы (микрокоманды) с Y, no vjt формируются блоком 3 микропрограммного управления.

1 лексическая единица есть закрывающаяся

памяти содержится код основы

Алгоритмом функционирования преду- сматривается бинарный четырехразряд- ный код лексических единиц (табл.1). При этом первые три разряда однозначно определяют код приоритета лексической единицы.

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

контексту. Для -устранения этой неоднозначности входных выражений в устройстве предусматривается проверка условия (.) и выполнение команды YJ.

В случае истинности условия Х,ЛХа

/

{т.е. когда операция по контексту является унарной) производится формирование кода унарной операции путем из- менения приоритета (инвертированием Значения разрядов регистра 1, содер- Јащих код приоритета). Такие же процедуры i устранения неоднозначности входных выражений выполняются и для унарной операции +.

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

При включении устройства блок 3 МПУ вырабатывает управляющий сигнал Y, - сб.рос в нуль содержимого регистров блока 4 памяти. На следующем шаге блок. 3 вырабатывает управляющий сиг- Нал Y - ввод очередной лексической единицы исходного выражения во вход- ной регистр 1. Затем лексическая единица поступает на дешифратор 2 лексических единиц и блок 8 сравнения. При этом дешифратор разделяет их на операнды, операции, скобки открывающие, скобки закрывающие и конец выражения.

Если поступавшая во входной регистр 1 лексическая единица есть операнд, то дешифратор 2 лексических единиц вырабатывает сигнал , который запускает блок 3 МНУ. Управляющие сигналы (микрокоманды Y и Y ) блока 3 МПУ переключают коммутатор 9 на запись операнда из регистра 1 в выходно регистр 19 и осуществляют запись кода нетерминала F в N разряд блока 4 памяти. Затем блок 3 МПУ вырабатывает управляющий сигнал ввода следующей лексической единицы во входной регистр 1 (микрокоманду уг).

Если поступившая во входной регистр 1 лексическая единица есть открывающая скобка, то дешифратор 2 лексических единиц вырабатывает сигнал , который запускает блок 3 МПУ на выработку управляющих сигналов записи открывающейся скобки из входного регистра 1 в N разряд блока 4 памяти (микрокоманда YT) и ввода следующей лексической единицы во входной регистр 1 (микрокоманда Y.J).

Если поступившая во входной регистр 1 лексическая единица есть закрывающая скобка или произвольная

операция, за исключением операции плюс и минус, то дешифратор 2 лексических единиц вырабатывает сигнал . Выполняемые в этом случае действия по управлению процессом записи лексических единиц из входного регистра 1 в блок 4 памяти или записи из блока 4 памяти в выходной регистр 10 осуществляются в зависимости от значения входных сигналов Х5,Х4,Х7, Xj и X ,f0, формируемых соответственно дешифраторами (основ) 5 и 6 (Х5, X . и Х6), дешифратором 2 лексических единиц и блоком 8 сравнения.

Если поступившая во входной регистр 1 лексическая единица есть операция плюс или минус, то дешифратор 2 лексических единиц вырабатывает сигнал (), который указывает на возможную неоднозначность поступившей на вход операции. Последующие действия выполняются в зависимости эт значения входного сигнала Х4, формируемого дешифратором 7 (основ).

Если , т.е. содержимое N-ro разряда блока 4 памяти является кодом нетерминала F или закрывающей скобкой, то операция плюс или минус идентифицируется как бинарная и последующие действия выполняются устройством в зависимости от значения входных сигналов Х5,Х, X., и X fo, формируемых соответственно дешифратором b и 5 (основ) и блоком 8 сравнения. Это действия по управлению процессом записи операции из входного регистра в блок 4 памяти и из блока 4 памяти в выходной регистр 10. Они описываются ниже.

Если , то операция плюс или минус идентифицируется как унарная и блок 3 МПУ вырабатывает микрокоманду Y7 - изменение кода приоритета операции, находящейся во входном регистре 1, а затем выполняются те же описываемые ниже действия, что и при Х4-1.

Действия устройства по управлению процесса записи операции из входного регистра 1 в блок 4 памяти и из блока 4 памяти в выходной регистр 10 являются следующими.

Если , т.е. в (N-1) и N разрядах блока 4 памяти содержится код основы F, то блок 3 :ШУ вырабатывает микрокоманду в соответствии с которой коммутатор 9 переключается на запись кода операции из (N-l)-ro разряда блока 4 памяти в выходной регистр 10, а затем осуществляет сверту15

ку основы F в F (микрокоманда YgYj). Свертка производится щздем сдвига содержимого регистра блока 4 памяти на один разряд вправо, что соответствует затиранию самой старшей лексической единицы основы F™ и последующей записи кода нетерминала F в N разряд блока 4 памяти. Выполнение микрокоманд У4 и Y{Y3 повторяет ся до тех пор, пока дешифратор основ 6 не выработает сигнал .

Если Х5-0, , Х(, т.е. в трех старших разрядах бдока 4 памяти содержится код основы и приори- тет операции , находящейся в (N-1) разряде блока 4 памяти, больше приоритета лексической единицы входного регистра 1, то блок 3 МПУ вырабатывает микрокоманду . В соответствии с этой командой коммутатор 9 переключается на запись кода операции из (N-1)-ro разряда блока 4 памяти в выходной регистр Ю и затем осуществляется свертка кода основы в F. Эта свертка производится путем сдвига содержимого регистров блока 4 памяти на 2 разряда вправо (микрокоманда Y0Y«). Выполнение микрокоманды V/Y.V.

X б О 9

повторяется до тех пор, пока не будет сформирован один из трех сигналов: Х5-1, Х(0 и .

Если , то выполняются действия описанные выше. Если ) и или и Xj 1, при этом , т.е. приоритет кода операции , находящейся в (N-1)-M разряде блока 4 памяти, меньше приоритета лексической единицы входного регистра 1, то блок 3 1ШУ вырабатывает микрокоман- ду Yv - запись содержимого регистра 1 в старший разряд блока 4 памяти, а затем вырабатывает микрокоманду v ввод следующей лексической единицы вО входной регистр 1.

Если Ху-0 и Х(-0, но значения входных сигналов Х и Xj равны единице, т.е. в (N-1) и N разрядах блока 4 памяти содержится код основы (F1 , a во входном регистре 1 находится лек- сическая единица - закрывающаяся скобка, то блок 3 МПУ вырабатывает микрокоманду YgYj - свертку основы вида с (F в F, а затем вырабатывает микрокоманду Y,j - ввод очередной лекси- ческой единицы во входной регистр 1.

Устройство осуществляет перевод входного выражения в инверсную польскую запись до тех пор, пока дешифра6W3

тор 2 ле#он«®с д Х1ея0йШмНе выработает сданал X,j $ № йРайИфрфтхф 6 основ) не в $ аботает сигнал Хи 1, т.е. пока во входной регистр 1 не поступит знак конца выражения # и пока в блоке 4 памяти не будет произведен сброс в нуль -всех разрядов, начиная от 1 до (N-1) в-ключительно.. Выработка сигнала определяется необходимостью записи всех находящихся в блоке 4 памяти кодов операций в выходной регистр 10.

Запись операций в регистр 10 осуществляется из (N-1) разряда блока 4 памяти. При этом каждая такая запись сопровождается освобождением старших разрядов блока 4 памяти от кодов логических единиц, используя свертку F в F или свертку в F в зависимости от сформированного в текущий момент одного из двух сигналов: или .

В том случае, если во входном регистре находится знак конца выражения, а в (N-1) разрядах блока памяти не содержится лексических единиц, т.е. Xj-1 и Х„ 1, то блок 3 МПУ формирует сигнал Нормальное завершение процесса (микрокоманда Y ,а ) , вырабатывается сигнал Останов и процесс перевода исходного выражения в инверсную польскую запись прекращается.

В том числе, если во входной регистр поступил знак конца выражения, но (N-1) младших разряда не освобождены от лексических единиц () и при этом дешифраторами 5 и 6 (основ) сформированы сигналы и Х(0, т.е. не выполняется ни одна из разрешенных сверток, то блок 3 МПУ вырабатывает сигнал Входное выражение содержит ошибку (микрокоманда Y«), формируется сигнал Останов и устройство прекращает работу.

Работу предлагаемого устройства дополнительно проиллюстрируем на нескольких примерах. Для наглядности процесс преобразования исходных выражений будем описывать пошагово, представляя на каждом шаге содержимые: входного регистра 1,.блока 4 памяти и выходного регистра 10, а также заействованные при этом входные сигналы и микрокоманды.

Пример 1. Пусть исходное выражение имеет вид (а+Ь)хс#, где а,Ь,с - операнды; +,х - знаки операций; # - символ конца выражения.

Ы15

Цо&а швое -пр е;9б;ра-зо В ание дазпшго выраже ния приведено в та бэъ. 2, рде для представления содержимых старших разрядов блока 4 памяти (столбец 5) используются следующие обозначения:

F - код операнда ;

- код бинарлой операции,;

( - код отафнвающей скобки;

Х - код закрывающей скобки,;

|Г 0 - код геуг&Т-оро символа.

ЩНЯ&ща устройсггва начинается со o6popav B 3rtH H ffc&x ра%рядов блока 4 п4м&йн.(крошманда Y ) и завершает- о Jij ЭД чегаксда G вира бготюай ©икнала $$ШрйКЯэ 3&eetRffleffitfe гсрещезееа (имик р йШрйда,-У 1А),. Шуже осжалов-а у&т-- р {|йё$||& «на ввпзоаднэм ресисщре Ш записано выр ажелие в виде ,, Эягокг по- рйдок Скгщдовшш Я оиивоэтов е оо«ше«1йс-т- вует полк&кой инвер&ной записи исходного выражения.

П р и м е р 2. Пу-ста исходное вы- рфкение имеет вид а Ьх--с#. Это выражение в отличие от прим&ра 1, где ис- пфльз-уют.еет би-нарные операции дВух приоритетов, включает унаржую операцию минус. ИЪшаговое преобразование данного выражения представлено в табл. 3, где в графе 5 символ (у обозначает код унарной операции, а символ - код бинарной операции.

Преобразование исходного выражения завершается за 11 шагов с выработкой сигнала Нормальное завершение процесса. Содерзчимое выходного регистра 10 после останова имеет вид abc-x+ что соответствует польской инверсной записи исходного выражения.

П р и м е р 3. Пусть исходное выражение имее/r вид l(aVb) . В отличие от примеров 1 и 2 данное выражение используе-т булевы операции i и V.

Пошаговое описание работы устройства приведено .в т,абл.-4,где в графе 5 символы

© и обозначают коды унарной логической операции НЕ и бинарной логической операции ИЛИ соответственно.

Преобразование данного выражения завершается за 10 ша-ров с выработкой сигнала Нормальное завершение про- uecdsa. бадержимое выэшдно,го регист- ра са / 0 ©отв-ета2тв55е|т польской инверсной зщгаои ивЕшдаочго вырлаакени.

м е р 4. Пусщь исходное выражение имеет йид аи- зйЪ«-еМ&, тле. со- рержит ошибку - проп.удден опер ащ между операциями + и х. С формальных

1616,2

позиций выражение а+хЪ-с#может рассматриваться ршибочным, а ошибкой типа перестановки символов операнда и операции (в сравнении с выражением примера 2).

Пошаговое описание работы устройства приведено в табл. 5.

5

0

5

0

5

0

5

Устройство завершило работу на 9 шаге с выработкой сигнала Входное выражение содержит ошибку (микрокоманда Yg) . При не произошло освобождение старших разрядов блока 4 памяти от кодов лексических единиц входного выражения. По этой информации леджо локализ е-т-ся место ошибки.

Формула изобретения

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

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

( а

+

Ъ

xt-i

Х,1

ХдДХ; 1

х,Г

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

Таблица2

О

(

(F

(F

(

a a ab

15

15/1616

16 Продолжение табл. 2

Кдешифоторуб

ОяЪюдноы .Mtucmpa 1 JF

Фа I

Фт.9