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

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

Иллюстрации

Показать все

Реферат

 

Оп ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ, СВИДЕТЕЛЬСТВУ (»>991437

Союз Советскик

Социапнстичесиик

Республик (61) Дополнительное к авт. сеид-ву 11" 890403 (22)Заявлено 17.07.81 (21) 3317931/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 23 . 01.83. 1ь»оллетень .Ре 3

Ката опубликования опнсания23.01.83 (5I)M. Кл.

G 06 F 15/38

ГесудлрстллккыВ кемктет

СССР вв аллам кзевретеккй к лтлрытик (53) УД,К681. 325 (088.8) /

А.И.Захаров, Г.А.Брякалов, В, В.Ковалев и Н.А.Калицкое> : =

> .> т™ > (72) Авторы изобретения (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕВОДА ВЫРАЖЕНИИ

В ПОЛЬСКУЮ ИНВЕРСНУЮ ЗАПИСЬ

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

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

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

"Чтение" и "Запись" магазинной памяти, к вторым входам элементов и четвертой, второй, третьей .и первой групп соответственно, к управляющему входу входного регистра, а также блок управления, содержащий регистр команд, дешифратор микрокоманд, дешифратор команд, микропрограммную память, генератор импульсов, триггер, группу элементов И, элемент И, причем входы регистра являются соответственно первой, второй и третьей груп пой входов блока управления, вход счетчика команд соединен с выходом элемента И, первый вход которого сое" динен с выходом генератора импульсов, а второй — с единичным выходом триг" гера, нулевой вход которого соединен с выходом первого элемента И группы, а единичный является входом

"Пуск" блока управления, выходы регистра и счетчика команд соединены соответственно с входами дешифратора микрокоманд и дешифратора команд, выходы которых соединены соответствен но с адресными входами первой и второй групп микропрограммной памяти, информационные выходы которой соединены с первыми входами соответствующих элементов И группы, вторые входы которых обьединены и подключены к .выходу элемента И, а выходы являются выходами блока управления с первого по седьмой $1 3.

Недостатком известного устройства является отсутствие контроля наличия и порядка следования лексических единиц в исходном выражении.

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

1437

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

ИЛИ, первый. вход первого элемента

И и вход элемента задержки соединены с соответствующими выходами дешифратора лексических единиц, выходы первого и второго элементов ИЛИ подключены соответственно ко входам сложения и вычитания реверсивного счетчика, установочный вход которого подключен к выходу элемента задержки и к входу элемента НЕ, выход котородешифратор 21 состояний, первый weго подключен к входу синхронизации реверсивного счетчика и к второму входу первого элемента И, третий вход которого подключен к выходу дешифратора состояний, выходы первого и второго элементов И подключены соответственно- к первому и второму входам третьего элемента ИЛИ, выход которого является выходом "Ошибка" устрой1 ства, входы второгб элемента И подключены к соответствующим выходам реверсивного счетчика, входы дешифратора состояний подключены к соответствующим инверсным входам реверсивно.го счетчика.

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

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

4 кодов операций магазинной памяти, дешифратор 5 кодов операций магазинной памяти, дешифратор 6 кодов операций выражений, схему 7 сравнения приоритетов, блок 8 управления, группу элементов ИЛИ 9, первую, вторую, третью и четвертую группы элементов

И 10-13, выходной регистр 14, блок

15 проверки исходного выражения на наличие и порядок следования лексических .единиц, который содержит реверсивный счетчик 16, первый и второй элементы ИЛИ 17 и 18,элемент

19 задержки, второй элемент И 20, 9914

5 мент И 22, элемент HE 23, элемент

ИЛИ 24.

Входной регистр 1 используется для хранения очередной лексической единицы исходного выражения, дешиф". ратор 2 лексических единиц разделяет лексические единицы на операнды, операции, скобки и т.д. Иагазинная память 3 - это память с последовательным безадресным приципом записи ie и чтения, регистр 4 и дешифратор 5 кодов операций магазинной памяти совместно с дешифратором 6 кодов операций выражений и схемой 7 сравнения приоритетов реализуют логическую функ-is цию выработки и сравнения приоритетов. Блок 8 управления организует, взаимодействие всех элементов устройства и представляет собой типовую схему микропрограммного управле- zo ния. Группа элементов ИЛИ 9, первая, вторая, третья и четвертая группы элементов И 1D-13 управляют передачами лексических единиц, а выходной регистр 14 предназначен для хранения 2s очередной лексической единицы в форме ПОЛИЗ.

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

Лексическим единицам присваиваются следующие веса: операнд "+Р, n - местная операция (функция) "1-n", скобка открывающая "+1", скобка закрывающая "-1" и т.д.

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

Реверсивный двоичный счетчик 16 используется для суммирования весов лексических единиц с учетом их знаков, элемент ИЛИ 17 обеспечивает поступление сигналов на суммирующий вход счетчика, а элемент ИЛИ 18ss на вычитающий. Элемент 19 задержки предназначен для получения временной задержки сигнала, соответствующего лексической единице "конец выраже37 е ния". С помощью этого сигнала осуществляется установка реверсивного счетчика в нулевое состояние. Значение текущей суммы на выходе реверсивного счетчика контролируется с помощью элемента И 20, а суммы, получаемой в конце преобразования исходного выражения — с помощью элеУ мента дешифратора 2l состояния и элемента И 22. Элемент НЕ 23 блокирует выдачу ложного сигнала ошибки, а элемент ИЛИ 24 обеспечивает поступление сигнала ошибки на выход блока проверки исходного выражения на наличие и порядок следования лексических единиц.

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

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

Если очередная лексическая единица - левая скобка, то дешифратор 2 запускает блок 8 управления, управляющий сигнал которого разрешает за- пись этой единицы через rpynny элементов И 11 из входного регистра 1 в магазинную память 3. Одновременно сигнал с дешифратора 2 подается на блок 15 и, пройдя в нем через элемент ИЛИ 17, поступает на реверсивный двоичный счетчик 16. Поскольку лексической единице - левой скобке ранее присвоен вес ".+1", то сигнал с дешифратора 2 поступает на. суммирующий вход реверсивного счетчика 16. ,Если очередная лексическая единица - операнд, то дешифратор 2 запускает блок 8 управления, управляющий сигнал которого разрешает через группы элементов И 10 и ИЛИ 9 перепись кода операнда из входного регистра 1 на выходной регистр 14. Одновременно сигнал с дешифратора 2 подается на блок 15 и, пройдя в нем через элемент

ИЛИ 17 поступает на реверсивный двоич1 ный счетчик 16. Поскольку лексический единице - операнду присвоен вес

"+1" то сигнал с дешифратора 2 посту1

naei на суммирующий вход реверсивного счетчика 16, к содержимому которого прибавляется единица.

Если очередная лексическая единица - операция, то сигнал с выхода дешифратора 2 лексических единиц запус7,. 9914 кает блок 8 управлений, а в блоках

4-7 начинается процесс выработки и . сравнен ия пр иоритетов. По результату работы схемы 7 сравнения приоритетов лексических единиц - операции S блок 8 управления организует либо запись через группу элементов И 11 в магазинную память, либо чтение из нее лексических единиц с большим приоритетом. В режиме чтения лексическая единица - операция записывается через группы элементов И 12 и ИЛИ 9 в выходной регистр 14.

Одновременно сигнал с дешифрато» ра 2 подается на блок 15 и, пройдя IS в нем через элемент ИЛИ 18, поступает на вычитающий вход реверсивного счетчика 16.

Когда на входном регистре 1 появляется лексическая единица - правая 20 скобка, блок 8 управления блокирует входной регистр 1 и организует режим чтения из магазинной памяти 3 и запись ее содержимого в выходной регистр 14 до тех пор, пока на регистр 2S кодов операций магазинной памяти не поступит код лексической единицылевой скобки.

Одновременно с этим сигнал с дешифратора 2 подается на блок 15 и, зо пройдя в нем через элемент ИЛИ 18, поступает на вычитающий вход реверсивного счетчика 16, из показаний ко" торого вычитается единица, В процессе преобразования выра- 35 жений непрерывно контролируется текущая сумма весов лексических единиц на выходе реверсивного счетчика 16, а поступление сигналов на его вход обеспечивается разрешающим потенциалом, подаваемым на вход синхронизации счетчика с выхода элемент га НЕ 23.

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

Вследствие этого сигнал на выходе элемента И 20 отсутствует.

Как только сумма весов лексичес« ких единиц станет отрицательной, что свидетельствует о нарушении по- рядка следования или отсутствии каких-либо лексических единиц в исход55 ном выражении, на выходе реверсивного счетчика 16 формируется код, в разрядах которогб содержатся одни единицы. В. этом случае .на выходе элемента

37 8

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

Преобразование входного выражения в форму ПОЛИЗ происходит до тех пор, пока в регистре l не окажется лекси» ческая единица "Конец выражения".

При этом блок управления осуществляет последовательное чтение содержимого магазинной памяти 3 и запись s выходной регистр 14. После полного . освобождения магазинной памяти 3 регистр 1 разблокируется и на него могут поступать лексические единицы следующего выражения. Цикл работы устройства повторяется.

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

Если сумма весов в конце преобразования отличается от плюс единицы, то на выходе реверсивного счетчика будет другая кодовая комбинация. В этом случае сигнал с выхода дешифратора состояния подается на третий вход элемента И 22, на второй вход которого поступает сигнал с выхода элемента НЕ 23, а.на первый - сигнал с входа блока 15, соответствующий лексической единице "Конец выражения". Сигнал, появившийся на выходе элемента И 22, пройдя через элемент

ИЛИ;24, воспринимается на выходе блока 15 в виде сигнала ошибки.

Поскольку сигналом "Конец выражения осуществляется сброс в нулевое состояние содержимого реверсивного счетчика 16, для предотвращения появления ложного сигнала ошибки на входе блока 15 контроля сигнал "Конец выражения" подается на счетчик через элемент 19 задержки. Одновременно сигнал .с выхода элемента 19 задержки подается на вход элемента HE 23.

Отсутствие сигнала на втором входе элемента" И 22 исключает, появление ложного сигнала ошибки.

7 10 ких единиц, выходы первого и второго элементов ИЛИ подключены соответственно к входам сложения.и вычитания реверсивного счетчика, установочный вход которого подключен к выходу элемента задержки и к входу элемента

НЕ, выход которого подключен к входу синхронизации реверсивного счетчика и к второму входу первого элемента

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

ИЛИ, выход которого является выхо.дом нОшьйка" устройства, входы второ-го элемента И подключены к соответствующим выходам реверсивного счетчика, входы дешифратора состояний подключены к соответствующим инверс- ным входам реверсивного счетчика.

9 99143

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

Устройство для перевода выраже- . 10 ний s польскую инверсную запись по авт. св. 11 890403, о т л и ч а ющ е е с я тем, что, с целью повышения достоверности. s работе, в него введен блок проверки исходного выра- д жения на. наличие и порядок следова: ния лексических единиц, содержащий реверсивный счетчик, первый, второй и третий элементы ИЛИ, первый и второй элементы И, элемент НЕ, дешиф- «О ратор:состояний и элемент задержки, причем первый и второй входы первого и второго элементов И/И, первый вход первого элемента И и вход элемента задержки соединены с соответству- 2 ющими выходами дешифратора лексичесИсточники информации, принятые во внимание при экспертизе

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

И 890403, кл. G 06 F 15/38, 1981.

991437

Составитель В. Евстигнеев

Редактор С.Патруаева Техред А. Бабинец Корректор И.Демчик Заказ 136/68 Тираж 704 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная 4