Устройство для перевода арифметических выражений в линейные регулярные префиксные формы Советский патент 1992 года по МПК G06F15/38 G06F11/00 

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

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

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

Устройство содержит входной ре- . .гистр 1, дешифратор 2 лексических единиц, блок 3 управления,счетчик k операндов, блок 5 памяти, дешифратор 6 блока памяти, выходной регистр 7. Блок 5 памяти построен на реверсивных регистрах сдвига. Выходной

регистр 7 образуют восемь регистров с разрядностью не менее 12 разрядов.

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

с

ю

00

GJ Ю

уют сигналы микроопераций -v , - Y3).. Содержательный смысл входных сигалов следующий.

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

О, если в противном случае; Г1, если очередной символ есть знак конца выражения

О,

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

Х1 у -

А2

X, х4

х

v

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

О,

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

знак ) ;

.0,

{1 , если очередной символ есть операнд; О, в противном случае, {1, если содержимое п-разряда блока 5 памяти есть и ; О, в противном случае, {1 , если содержимое п-разряда блока 5 памяти есть #; О,

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

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

°

1 , если содержимое п-разряда

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

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

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

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

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

1о

41

п

3

4

5

6

п

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

5

Y1 ЧY Y Ye YЈ Y сброс в ноль входного регистра

1;

сброс в ноль регистров блока 5 памяти;

сброс в ноль выходного регистра 7;

занесение в n-разряд регистров блока 5 памяти значение кода знака;

занесение в n-разряд блока 5 памяти значения, $ ; разрешение ввода следующей лексической единицы ш во входной регистр 1;

разрешение записи в блок 5 памяти;

8 YQ Y - выработка сообщения успешный

анализ ;

выработка сообщения ошибка ;

5

0

5

0

5

0

-выработка сообщений во входном выражении неверно расположен знак конца выражения ;

-выработка сообщения во входном выражении неверно размещен знак операции ;

-выработка сообщения во входном выражении неверно размещен знак открывающей скобки ;

Y, - выработка сообщения во входном выражении неверно размещен знак закрывающей скобки ; выработка сообщения конфликт10

11

ft

U

5

16

47

8

19

-го

г

5 Y

гг

УЗ

ное размещение операнда во вход- Ном выражении ; выработка сообщения несоответствие числа открывающих и закрывающих скобок во входном выражении ;

увеличение значения счетчика k операндов;

занесение в n-разряд блока 5 памяти значения входного регистра ;

занесение в n-разряд блока 5 памяти значения счетчика k операндов ;

сдвиг влево на один разряд влево содержимого блока 5 памяти;

сдвиг вправо на один разряд содержимого блока 5 памяти; занесение в 12 разряд выходного регистра 7 значения счетчика операндов;

занесение в 11 разряд выходного регистра 7 значения кода ; занесение в 12 разряд выходного регистра 7 значения выходного регистра 1;

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

( ; .

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

) ;

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

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

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

.V

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

ходного регистра 7 значения

/ ,

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

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

ъг окончание и выдача всех 12 разрядов выходного регистра; окончание работы устройства; Y.4 начало работы устройства.

Счетчик k операндов предназначен для нумерации операндов, встречаемых во входном выражении. Блок 5 памяти предназначен для записи, хранения и считывания кодов лексических единиц. Запись кодов текущих ш производится в старшие n-е разряды регистров блока 5 памяти, сдвиг вправо на k-разрядов равносилен затиранию k последних (старших) разрядов.

Дешифратор 6 блока памяти предназначен для формирования сигналов X - на основе анализа старших разрядов блока 5 памяти. Выходной регистр 7 предназначен для записи, хранения и считывания преобразованных в регулярную форму, входных выражений.

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

При его включении блок 3 управления вырабатывает микрооперацию Y-JA, после чего по управляющим шинам поступает набор микроопераций. YJ - обеспечивающих обнуление вводного регистра 1 (в дальнейшем возможно р1);

Yg - блока 5 памяти, в дальнейшем, Чдзможно р2);

Y - выходного регистра 7 (в дальнейшем возможно рЗ). После этого происходит занесение

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

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

0 производит последующую отработку

исходной информации и производит последовательность микрокоманд и микроопераций, адекватных данному типу лексической операции-, после чего

5 вновь вырабатывается микрооперация Y,, и очередная лексическая единица поступает на вход р1. Такая циклическая работа устройства ПРОИСХОДИТ до тех пор, пока на вход входного

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

5 (микрооперация Y).

Лексические единицы делятся на типы.: операнды (символ типа F , под которым подразумевается любой символ, представимый ЭВМ), операции

® (символ + , # ), скобки открывающие и закрывающие (символы (, ) ); символы, обеспечивающий любую стет пень разряжения пробелами исходного

выражения. 5

Совокупность всех входных символов, поступающих на вход входного регистра 1, и хранящихся в регистрах

0 блока 5 памяти, не выходят за пределы допустимого в любой ЭВМ алфавита. Это значит, что в состав блока памяти 5 входят стандартные 12-разрядные реверсивные регистры 8 сдви5 га. Их количество определяется формулой преобразования, осуществляемого устройством:

()(aVb) и составляет 10 штук.

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

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

В противном случае управляющими средствами блока 3 управления производится обнуление выходного регистра 7 (Y), увеличение значения счетчика и операндов, занесение в 12-й разряд рЗ значение этого счетчика: соответственно микрооперации (Y16 и Ґг() После этого производится выдача содержимого блока 5 памяти по микрооперации Y 32. и занесение в 11-й разряд выходного регистра 7 значение кода символа к ( Y/, Y2z) занесение в 10-й разряд значение входного регистра pi (микрооперация Y, После этого блок, 3 управления формирует микрооперации Y(J (сдвиг вправо содержимого блока 5 памяти на оди разряд) и Yy, Yjg (занесение в старший разряд блока 5 памяти значение счетчика Ц операндов)..

При в поступлении лексической единицы - знака операции (символы

+ , #0 (Х- 1) проверяется значение старшего разряда блока 5 памяти. Если это значение совпадает со значениями символов ц (, + , # , (,X,,a 1), то формируется сообщение об ошибке (микрооперация

В противном случае проверяется значение (п-1)-разряда блока 5 памяти Если это значение не содержит коды знаков операций + , к (X 0), блок управления вырабатывает последовательность микрокоманд и микроопераций для выполнения совокупности действий, которые рассмотрим подробнее.

Сначала увеличивается значение счетчика Ь операндов (Yfg), затем выполняется микрокоманда по занесени в выходной регистр первичного шаблок (совокупность Y, , Y7Ј, ) затем- происходит занесение в 10-й раз рядный рЗ значение символа. (, а в 6-й разряд рЗ - значение символа (соответственно микрооперации и

Ync) ,

5

5

, после чего генерируется микрокоманда по информационному заполнению выходного регистра 7, содержащая совокупность микроопераций: Y12, YZg , Y-3( .После выполнения данной микрокоманды производится выдача сформированного содержимого выходного регистра (Y52), сдвиг вправо на три разряда блока 5 памяти (Y2o, Y2o, Y-ZQ) и занесение в старший разряд блока памяти 5 значение счетчика операндов (Y7, Y1%); чиваются действия по условию X После этого производятся еще 2 микрооперации: сдвиг влево на один разряд блока 5 памяти () и Y7, - занесение в разряд памяти значения входного регистра 1. Этим заканчиваются действия по входной лексической единице типа операции.

Раскроем содержание двух применяемых микрокоманд. Микрокоманда по занесению первичного шаблока состоит из совокупности микроопераций:

Этим закан14- 1

обнуление выходного регистра 7; занесение в 11-й разряд рЗ значение символа г ;

0

L27

28

5

0 г

5

занесение в пятый разряд рЗ

значение символа ( ;

занесение в третий разряд рЗ

значение символа v ;

занесение в первый разряд рЗ

значение символа ) . Микрокоманда по информационному заполнению выходного регистра 7 сос- тоит из совокупности микроопераций: Y - занесение в 12-й разряд рЗ значение счетчика k операндов;

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

30 - занесение в восьмой рЗ значение (п-1) разряда блока 5 па- мяти;

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

51

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

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

YJ- - сдвиг влево на один разряд содержимого блока 5 памяти; Y, Y17 - занесение в n-разряд блока 5 памяти содержимого входного регистра pi.

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

1), то выполняется Yw - сдвиг

40

влево на один разряд содержимого памяти. Если же значение п-разряда блока 5 памяти равно значению лексической единицы типа операнда (X а 1), то блок 3 управления генерирует для выполнения определенную последовательность микрокоманд и микроопераций. Вначале условие X,5 1, если значение () разряда блока 5 памяти равно значению символа ( , Х,2 1, X .t « 1, то выполняется сдвиг вправо на дба разряда содержимого блока 5 памяти n (Y20, YZQ), в противном случае (X г 1 1) проверяется значение РЗ значение (п-1) разряда ти. Если оно равно значению символа ( ( 1, Х45 - О, Х„ - 1), то выполняется совокупность микроопераций и микрокоманд.

Вначале производится увеличение значения ряда содержимого блока 5 памяти (, ) затем выполняется описанная выше микрокоманда по за- несению первичного блока в выходной регистр 7 (Y«, Ґгг, Угб, Y27, YZ8), после чего происходит занесение в 10-й и 6-й разряды рЗ соответственно

значения символов

С и ) (Y

24

24

) после чего выполняется микрокоманда по информационному заполнению рЗ (Yia, Y2q, Yw, YSf) и производится полная выдача сформированного содержимого выходного регистра (Y) После этого происходит сдвиг вправо на четыре разряда содержимого блока 5 памяти (Y, , Y2o 20) В случае невыполнения последнего условия X 42 I i,- О,

П

О производится выполнение

микрооперации Y Этим заканчиваются действия для лексической единицы

fT.

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

5

2832Ю

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

Если значение (п-1) - разряда

10

15

20

25

блока 5 памяти равно LJ (Y 1) , то происходит занесение в п-разряд блока 5 памяти значение символа (Y7, YS-) . Если же значение (п-1)- разряда блока 5 памяти равно значению

символа ( (Х«б 1), формируется сообщение об ошибке (Y1). В противном случае (Х 0,. 0) проверяется значение (п-2)-разряда блока

5 памяти падает с ранд

и, если его содержимое сов- значением символа типа one- происходят

(V), т.е. Y,, 1,

30

45

55

40

следующие действия. Увеличивается значение счетчика k операндов ( ), происходит занесение в рЗ первичного шаблока (Y4, , Y2o, Y2&) ПР°ИС ходит занесение в 10-й и 6-й разряды рЗ значений символов f( и ) соответственно (Y и Y2sr) информационное заполнение рЗ (Y.,2, Y2), Yjo , Y-j|) и выдача сформированного рЗ (Y3Z). После этого происходит сдвиг на три разряда содержимого блока 5 памяти (YZQ, Y2o Y2o) и занесение в n разряд блока 5 памяти значение символа (Y, YgO . Если же значение n-разряда блока 5 памяти равно лексической единице типа операнд ( 0), то происходит обыкновенное занесение в разряд блока 5 памяти символа # (, Yg.).

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

диагностики ошибок: Y

ГО 1«

.-V

).

I ,14- Т t-y

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

л

Поэтому для этого символа, при значении п разряда блока 5 памяти, равном # (Хд 1), или отсутствии Y15 вырабатывается микрооперация v g, успешный перевод и - окончание работы устройства. После возникновения сигналов Y|0, Y , Y15) также вырабатывается микрооперация

Y

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

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

10

соединены с первым и вторым входами дешифратора блока памяти, соответст17 283212 /

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

15

20

25

30

1

ffmcvesf - 0гте -

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

А

X

X

ZT

t -r-TT nLlLl,./L

X St-i;tS9 y/OCrrr7 ypy

ic gtrx0Jtto tyЯ/гыа -rra ssTrts

f ЈZVCfr f r/

n-5 rt-2 n-f rt i .-ii

ГГ-f ГГ

J- ,.. I -.T-l

.

X St-i;tS9 y/OCrrr7 ypy $

/гыа -rra ssTrts

0rrrЈffOArcr Л7/7& 3

Фаг 2

от 5лока M(J4 $ Of cvttrwvta опер&ндеб 4

cm входного регистра I

от Јлок& ftttMjimt/ S