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

 

Изобретение относится к вычислительной технике и может найти практическое применение в автоматизированных системах производства программ для ЦВМ. Целью изобретения является повышение достоверности преобразования информации путем поразрядного контроля по модулю результатов работы устройства. Для достижения этой цели устройство снабжено первым и вторым элементами ИЛИ 16 и 17 и блоком 18 контроля результатов преобразования, который состоит из трех полусумматоров, регистров-аккумуляторов, двух элементов задержки, двух элементов И, элемента ИЛИ-НЕ, элемента ИЛИ. Устройство позволяет осуществлять преобразование выражений в польскую инверсную запись в темпе последовательного чтения входного выражения, осуществляя при этом контроль правильности как исходных выражений, так и преобразований, что значительно повышает надежность и достоверность работы устройства. 2 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ .

РЕСПУБЛИК

„„SU„„1476490 (51)4 С 06 F 15/38

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

К АВТОРСКОМУ СВИДЕТЕЛ6СТВУ (61) 991437 (21) 4331215/24-24 (22) 24.11.87 (46) 30.04.89. Бюл. № 16 (72) Г.А.Брякалов, А.В.Запорожец, А.И.Захаров и С.М.Шептуха (53) 681.325(088.8) (56) Авторское свидетельство СССР № 991437, кл. G 06 F 15/38, 1983. ,,(54) УСТРОЙСТВО ДЛЯ ПЕРЕВОДА ВЫРА ЖЕНИЙ В ПОЛЬСКУЮ ИНВЕРСНУЮ ЗАПИСЬ (57) Изобретение относится к вычислительной технике и может найти практическое применение в автоматизированных системах производства программ для ЦВМ. Целью изобретения является повышение достоверности преобразования информации путем поразрядного контроля по модулю результатов работы устройства. Для достижения этой цели устройство снабжено первым и вторым элементами ИЛИ 16 и

I7 и блоком 18 контроля результатов преобразования, который состоит иэ твех полусумматоров, двух регистроваккумуляторов, двух элементов задержки, двух элементов И, элемента ИЛИ-НЕ, элемента ИЛИ. Устройство позволяет осуществлять преобразование выражений в польскую инверсную запись в темпе последовательного чтения входного выражения, осуществляя при этом контроль правильности как исходных выражений, так и преобразований,что значительно повышает надежность и достоверность работы устройства.2 ил.

1476490

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

Цель изобретения — повышение достоверности преобразования информации путем поразрядного контроля по модулю результатов работы устройства ° lp

На фиг.l представлена структурная схема устройства; на фиг.2 — струк" турная схема блока контроля результатов преобразования.

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

10, вторую ll третью 12 и четвертую 13 группы элементов И, выходной 25 регистр 14, блок 15 проверки исходного выражения на наличие и порядок

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

18 контроля результатов преобразова- 30 ния, который содержит элемент ИЛИ НЕ 19, первый элемент 20 задержки, первый элемент И 21, второй элемент

22 задержки, первый 23 и второй 24 регистры-аккумуляторы, первый 25, второй 26 и третий 27 полусумматоры, третий элемент ИЛИ 28 и второй элемент И 29.

Входной регистр 1 используется 4р для хранения очередной лексической единицы исходного выражения, дешиф" ратор 2 лексических единиц разделяет лексические единицы на операнды, операции, скобки и т.д. Магазинная 45 память 3 о последовательным безадресным принципом записи и чтения, ре гистр 4 и дешифратор 5 кодов операций магазинной памяти совместно с дешифратором 6 кодов операций выражений и схемой 7 сравнения приоритетов реализуют логическую функцию выраотки и сравнения приоритетов. Блок

8 управления организует взаимодействие всех элементов устройства и пред-55 ставляет собой типовую схему микропрограммного управления. Группа элементов ИЛИ 9, группы элементов И 10l3 управляют передачами лексических единиц, а выходной регистр 14 предназначен для хранения очередной лек,сической единицы в форме ПОЛИЗ.

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

Элементы ИЛИ 16 и 17 управляют передачами сигналов при контроле правильности преобразования информации.

Блок 18 контролирует правильность преобразования информации путем поразрядного контроля по модулю результатов работы устройства. Элемент

ИЛИ"НЕ 19, первый элемент 20 задержки, первый элемент И 21 и второй элемент 22 задержки управляют работой регистров-аккумуляторов, предназначенных для накопления поразрядных сумм по модулю два входной и выходной информации устройства. Первый полусумматор 25 с помощью регистрааккумулятора 23 осуществляет поразрядное суммирование по модулю два выходной информации, а второй полусумматор 26 с помощью регистра-аккумулятора 24 осуществляет поразрядное су:актирование по модулю два входной информации. Третий полусумматор 27 предназначен для сравнения кодов, хранящихся на регистрах-аккумулято-. рах 23 и 24, которое выполняется совместно с элементом ИЛИ 28. Наличие единицы на выходе элемента ИЛИ 28 свидетельствует о несовпадении кодов, хранящихся на регистрах-аккумуляторах 23 и 24. Второй элемент И 29 служит для пропуска на выход блока

18 сигнала "Ошибка преобразования" по окончании выполнения преобразований устройством.

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

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

Если очередная лексическая единица — левая скобка, то дешифратор

1476490

2 запускает блок 8 управления, управляющий сигнал которого разрешает запись этой единицы через группу элементов И 11 из входного регистра 1 в магазинную память 3. Одновременно

5 сигнал с дешифратора 2 подается на блок 15, где фиксируется ее наличие . в исходном выражении. Поскольку в выходном регистре 14 формируется бесскобочная форма записи выраженк4, то лексические единицы входного выражения — левая и правая скобки, а также лексическая единица — конец выраже ния, должны быть исключены из процесса контроля. С этой целью сигнал с дешифратора 2, соответствующий левой скобке, подается в блок !8 контроля результатов преобразования на первый вход элемента ИЛИ-НЕ 19 и через первый элемент И 21 блокирует работу второго регистра-аккумулятора

24. В этом случае код лексической единицы — левой скобки, поступает с входного регистра 1 на второй полу- 25 сумматор 26, но в регистре-аккумуляторе 24 не зафиксируется. Так как эта лексическая единица записывается только в магазинную память 3 и в выходном регистре 14 никогда не бывает, 3О в первом полусумматоре 25 никаких изменений не происходит.

Если очередная лексическая единица — операнд, то дешифратор 2 запускает блок 8 управления, управляющий

35 сигнал которого разрешает через группу элементов И 10 и ИЛИ 9 перепись кода операнда из входного, регистра 1 на выходной регистр 14, Одновременно сигнал с дешифратора 2 подается на 4О блок 15 и фиксируется им. В это же время код лексической единицы — one" ранда, с группы выходов входного регистра 1 поступает на первую группу входов второго полусумматора 26 бло- 45 ка контроля 18. Поскольку с дешифратора 2 лексических единиц в этом случае на элемент ИЛИ-НЕ 19 ничего не поступает, он готовит к работе первый элемент И 21. По сигналу с седьмого выхода блока 8 управления, задержанному первым элементом 20 задержки и прошедшему через первый элемент И 21, во втором регистре-аккумуляторе 24 фиксируется код лексической единицы — операнда, поступивший с выхода второго полусумматора.

Так как этот же код лексической единицы — операнда, находится уже в выходном регистре 14, он поступает на первую группу входов первого полусумматора и фиксируется в первом регистре-аккумуляторе 23 с помощью сигнала с шестого выхода блока 8 управления, прошедшего через второй элемент ИЛИ 17 и задержанного вторым элементом 22 задержки.

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

ИЛИ 9 в выходной регистр 14.

Одновременно сигнал с дешифратора

2 подается на блок 15 и фиксируется в нем, В зто же время код лексической единицы — операции, с группы выходов входного регистра 1 поступает в блок контроля 18 на первую группу входов второго полусумматора 26, где с помощью регистра-.аккумулятора 24 осуществляется поразрядное суммирование по модулю два накопленной в регистре-аккумуляторе и вновь поступившей входной информации. Этот процесс управляется сигналом с седьмого выхода блока управления 8, как и в случае прихода лексической единицы— операнда.

При записи лексической единицы— ,операции, в магазинную память 3 она отсутствует в выходном регистре 14., и, следовательно, на первой группе входов первого полусумматора 25. Кроме того, блокируется сигнал с пятого выхода блока 8 управления, поэтому ,никаких изменений в регистре-аккумуляторе 23 не происходит.

И наоборот, при чтении лексических единиц — операций, из магазинной памяти 3 они поступают в выходной регистр 14. По сигналу с пятого выхода блока 8 управления, прошедщему через второй элемент ИЛИ 17, в первом регистре-аккумуляторе 23 фиксируется результат п9разрядного суммирования по модулю два выходной информации, 6490 6

45

55

5 147 которое выполняет первый полусумматор 25.

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

4 кодов операций магазинной памяти не поступит код лексической единицы— левой скобки.

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

И 21 блокирует второй регистр-аккумулятор 24.

Наоборот, при чтении из магазинной памяти 3 в выходной регистр 14 осуществляется поразрядное суммирование по модулю два содержимого первого полусумматора 25 и первого регистрааккумулятора 23, как было описано выше.

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

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

15, а в блоке 18 выполняются завер" шающие операции по контролю преобразованной информации. Так как магазинная память 3 полностью освобождается и ее содержимое переписывается в выходной регистр 14 (кроме левой скобки ), первый полусумматор 25 продолжает поразрядное суммирование по модулю два кодов поступающих на него лексических единиц с содержимым первого регистра-аккумулятора 23.

На протяжении всей работы блока

18 контроля содержимое первого и вто" рого регистров-аккумуляторов 23 и 24 поступает соответственно на первую и втррую группы входов третьего полу5

35 сумматора, где тоже осуществляется поразрядное суммирование, а совместно с элементом СЛИ 28 и сравнение кодов результатов. Наличие единицы на выходе элемента ИЛИ 28 свидетельствует о несовпадении кодов, хранящихся в регистрах-аккумуляторах 23 и 24, и об ошибке преобразования выражений.

С помощью второго элемента И 29 сигнал ошибки поступает на выход блока

18, когда с инверсного выхода триггера блока 8 управления поступает сигнал опроса. Затем сигнал ошибки через первый элемент ИЛИ 16 поступает на вход "Останов" блока 8 управления. На этот же элемент ИЛИ в слу" чае необходимости поступают сигналы с блока 15 проверки исходного выражения на наличие и порядок следования лексических единиц.

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

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

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

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

)476490

Составитель Ю.Тисленко

Техред М.Ходанич Корректор Н.Король

Редактор Л.Пчолинская

Заказ 2158/50 Тираж 669 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 1О1 первого регистра-аккумулятора и первой группой входов третьего полусумматора, группа выходов первого полусумматора соединена с группой инфор5 мационных входов первого регистрааккумулятора, управляющий вход кото-,. рого через второй элемент задержки подключен к выходу второго элемента ИЛИ, входы которого подключены к пятому и шестому выходам блока управления, первая группа входов второго полусумматора йодключена к группе выходов входного регистра, вторая группа входов второго полусумма- 15 тора соединена с группой выходов второго регистра-аккумулятора . и второй группой входов третьего полусумматора, группа выходов второго полусумматора соединена с . 20 группой информационных входов второго регистра-аккумулятора, управляющий вход которого подключен к выходу первого элемента И, первый вход которого через первый элемент задержки подключен к седьмому выходу блока управления, а второй вход — к выходу элемента ИЛИ-HE первый, второй и третий входы которого соединены с соответствующими выходами дешифратора лексических единиц, выходы группы третьего полусумматора подключены к соответствующим входам третьего элемента ИЛИ, выход которого соединен с первым входом второго элемента И,вто" рой вход которого подключен к инверсному выходу триггера блока управления, а выход элемента И является выходом "Ошибка преобразования" устройства и подключен к первому входу первого элемента ИЛИ, второй вход которого подключен к выходу пОшибка" блока проверки исходного выражения на наличие и порядок следования лексических единиц, а выход первого элемента ИЛИ подключен к входу "Останов" блока управления.