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

 

(72) Авторы изобретения

А.И. Захаров, Г.А. Брякалов, В.В. Ковалев и Н.А. Калмаков (7f) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕВОДА ВЫРАКИНИЙ

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

ИЫ!1

Магазинный приоритет

Π— 1 2 3 4 5 6 7 8 9 10

Сравнительный при ори т ет

О I 2 3 4 5 6 7 8 9 lO

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

Известен алгоритм перевода любых

3 по сложности выражений, правильных с точки зрения синтаксиса языка типа

Ограничители I((!% j)),; 1 а не gt

Устройством, реализующим рассмотренные способы перевода выражений в

ПОЛИЗ, является ЦВМ, представляющее собой сложный универсальный комплекс дорогостоящего оборудования, причем осуществление операций перевода про-. граммными способами с помощью ЦВМ треАЛГОЛ, в польскую инверсную запись (ПОЛИЗ). Здесь каждый ограничитель имеет двойной приоритет, заданный таблично: магазинный — для ограничителей, находящихся в магазинной памяти, сравнительнй — для ограничителей, предназначенных для записи в магазинную память ()). бует больших затрат машинного времени.

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

89040 группу элементов И соединены со входами устройства, а выходы через дешифратор подключены к адресным входам блока памяти, выходы которого через регистр выдачи соединены с выходом устройства, а также два элемента И и дополнительный разряд в регистре выдачи, причем единичный и нулевой выходы дополнительного разряда выдачи подключены соответственно к первым входам первого и второго элементов И, вторые входы которых соединены с.управляющим входом устройства, выход первого элемента И соединен со счетным входом регистра приема, выход второго элемента И подключен к управляющим входам элементов И группы, а вход дополнительноrо разряда регистра выдачи соединен с управляющим выходом блока памяти (2).

Данное устройство позволяет за счет обеспечения сопоставления входному выражению эквивалентной последовательности символов получить польскую инверсную запись исходного выражения, однако в этом случае необходима память неограниченного объема, способная вместить в себя эквивалентные

25 последовательности символов для выражений произвольного вида, число кото30 рых практически бесконечно. При этом время преобразования, связанное с поиском, перебором и сравнением эквивалентов, размещенных в памяти большого объема будет велико, что исключает практическое применение такого . устройства для получения ПОЛИЗ.

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

Поставленная цель достигается тем, что устройство для перевода выражений в польскую инверсную запись, содержащее входной регистр, вход которого является входом устройства, дешифратор лексических единиц, группой входов соединенный с группой выходов входного регистра, выходной регистр, группа выходов которого является выходом устройства, магазинную память, 50 четыре группы элементов И, группу элементов ИЛИ, дешифратор кодов операций выражений, дешифратор кодов операций магазинной памяти, регистр кодов операций магазинной памяти, схе- 55 му сравнения приоритетов, блок управления, первая группа входов которого подключена к группе выходов дешифраз 4 тора лексических единиц, соответствующие входы элементов И первой и второй групп и дешифратора кодов oneраций выражений объединены и подключены к соответствующим выходам группы входного регистра, выходы элементов И первой группы подключены соответственно к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И третьей группы, а выходы подключены к группе входов выходного регистра, выходы элементов И второй группы подключены к группе входов магазинной памяти, первая группа выходов которой подключена к первым входам соответствующих элементов И третьей группы, вторая группа выходов магазииной памяти подключена к первым входам соответствующих элементов И четвертой группы, выходы которых подключены к группе соответствующих входов регистра кода операций магазинной памяти, группа выходов которого подключена к группе соответствук|цих входов дешифратора кода операций магазинной памяти, группа выходов дешифратора кодов операций выражений подключена к первой группе входов схемы сравнения приоритетов, вторая группа входов которой подключена к группе выходов дешифратора кодов операций магазинной памяти и ко второй группе входов блока управления, третья группа входов блока управления подключена к схеме сравнения приоритетов, первый, второй, третий, четвертый, пятый, шестой и седьмой выходы блока управления подключены соответственно ко входам "Чтение" и "Запись магазинной памяти, ко вторым входам элементов И четвертой, второй, третьей и первой групп соответственно>к управляющему входу входного регистра; блок управления содержит регистр, счетчик команд, дешифратор микрокоманд, дешифратор команд, микропрограммную память, генератор импульсов, триггер, группу элементов И, элемент И, причем входы регистра являются соответственно первой, второй и третьей группой входов блока управлений, вход счетчика команд соединен с выходом элемента И, первый вход которого соединен с выходом генератора импульсов, а второй— с единичным выходом триггера, нулевой вход которого соединен с выходом первого элемента И группы, а единич890403

5 ный является входом "Пуск" блока управления, выходы регистра и счетчика команд соединены соответственно со входами дешифратора микрокоманд и дешифратора команд, выходы которых со- В единены соответственно с адресными входами первой и второй групп микропрограммной памяти, информационные вы— ходы которой соединены с первыми входами соответствующих элементов И груп- )4 пы, вторые входы которых объединены и подключены к выходу элемента И, а выходы являются выходами блока управления с первого по седьмой.

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

Устройство содержит входной. регистр 1, дешифратор 2 лексических единиц, магазинную память 3, регистр 4 34 кодов операций магазинной памяти,дешифратор 5 кодов операций магазинной памяти, дешифратор 6 кодов операций выражений, схему 7 сравнения приоритетов, блок 8 управления, группу эле- Я ментов ИЛИ 9, первую, вторую, третью и четвертую группы элементов И 10, l1, 12 и !3, выходной регистр 14, регистр 15, счетчик 16 команд, дешифратор 17 микрокоманд, дешифратор 18 ко- щ манд, микропрограммную память 19, генератор 20 импульсов, триггер 21, группу элементов И 22, элемент И 23.

Входной регистр 1 используется для хранения очередной анализируемой лексической единицы входного выражения, дешифратор 2 лексических единиц разделяет лексические единицы на операнды, операции и скобки, магазинная память 3 - это память с последователь° Ф ным безадресным принципом записи и чтения, регистр 4 и дешифратор 5 кодов операций магазинной памяти совместно с дешифратором 6 кодов операций выражений и схемой 7 сравнения приоритетов реализуют функцию выработ44 ки и сравнения приоритетов

S y y y< 7< v y> «х1 ч у, х„х, х где S — - управляющий сигнал схемы сравнения приоритетов; 50 у. — приоритеты кодов операций входного выражения;

x„ — приоритеты кодов операций магазинной памяти.

И

Блок 8 управления организует взаимодействие всех элементов устройства и представляет собой типовую схему микропрограммного управления.

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

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

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

Если очередная лексическая едини- . ца — операнд, то дешифратор 2 запускает блок 8 управления, управляющий сигнал которого разрешает через группы элементов И )О и ИЛИ 9 перепись кода операнда входного регистра 1 на выходной регистр 14.

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

Блок 8 управления блокирует запись очередной лексической единицы во входной регистр l. Лексические единицы — операции со входного регистра 1, а нз магазинной памяти 3 через регистр 4 поступают соответственно на дешифраторы 6 и 5, где определяются их приоритеты.

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

Когда во входном регистре ) находится правая скобка, блок 8 управления блокирует входной регистр l и организует режим чтения из магазинной памяти 3 и запись ее содержимого в выходной регистр 14 до тех пор, пока на регистр 4 кодов операций магазинной памяти не поступит левая скобка. После этого блок 8 управления разблокирует входной регистр ).

Преобразование входного выраже ния в форму ПОЛИЗ происходит до тех

890403 пор, floKd. н регистре 1 не окажется лексическая единица Конец выраже>шя". 11ри этом блок 8 управления блокирует входной регистр 1 и осуществляет последовательное чтение содержимого магазинной памяти 3 и запись в выходной регистр !4. После полного освобождения магазинной памяти 3 регистр 1 разблокируется и на него могут поступать лексические единицы следующего выражения. Цикл работы устройства повторяется.

Пример, Пусть входное выражение имеет вид А-В/(С+ Р); где используется как символ "Конец выражения".

На входной регистр 1 поступает лексическая единица "А", которая оп— ределяется дешифратором 2 как олеранд и с помощью блока управления 8 записывается через группу элементов И 10 н выходной регистр 14. На входной регистр 1 принимается очередная лексическая единица "-". Это операция.

Входной регистр 1 блокируется °

На дешифраторах 6 и 5 производится выработка приоритетов входного выражения и магазинной памяти 3 соответственно, которые сравниваются на схеме сравнения 7.

Так как магазинная память 3 и регистр 4 кодов операций магазинной памяти свободны, то в результате сравнения "-" записывается в магазинную память. После этого входной регистр 1 разблокируется. Очередная лексическая единица В записывается во входной регистр 1 и, так как она является операндом, то переписывается в выходной регистр 14. Очередная лексическая единица "/" записывается, во входной регистр 1 и определяется дс=ифратором 2 как операция. Блокируется входной регистр 1. Блоки 4, 5, 5, 7 осуществляют процесс выработки и сравнения приоритетов. Так как приоритет операции "/" вьппе приоритета операции "-", то "/" записывается в магазинную память 3. Входной регистр 1 разблокируется и принимает очередную лексическую единицу "(".

Дешифратор 2 опознает ее как левую скобку и производится запись в магазинную память. На входной регистр 1 принимается очередная лексическая единица "С". Она является операндом. и записывается в выходной регистр 14.

Далее на входной регистр 1 принимается "+". Дешифратор 2 запускает

lO

ЗФ

5Ф

° Э

5ф блок 8 управления и начинается процесс выработки и сравнения приоритетов. Входной регистр 1 блокируется.

Так как приоритет операции "+" выше внутримагазинного приоритета левой скобки, то "+" записывается в магазинную память 3. Входной регистр 1 разблокируется и на него принимается лексическая единица "Т!" — операнд, которая записывается в выходной регистр 14.

Очередная лексическая единица ">" входного выражения принимается на входной регистр 1. Дешифратор 2 определяет, что на входном регистре 1 находится правая скобка. Входной регистр 1 блокируется и блок 8 управления анализирует содержимое регистра 4 кодов операций магазинной памяти 3.

К этому моменту в магазинную память записаны следующие единицы: вЂ, /, 1, +, причем в "верхушке магазинной памяти находится "+". Лексическая единица "+" читается из магазинной памяти и записывается в выходной регистр 14.

Блок 8 управления вновь анализирует содержимое "верхушки" магазинной памяти, и, так как теперь в ней находится левая скобка, то производится ее чтение в регистр 4 беэ записи в выходной регистр 14 (стирание из "верхушки" магазинной памяти). Входной регистр 1 разблокируется и на него принимается очередная лексическая единица входного выражения "Конец выражения". Дешифратор 2 запускает блок 8 управления, входной регистр 1 блокируется и лексические единицы, записанные в магазинную память, последовательно читаются в выходной регистр 14. Когда магазинная память 3 освобождается полностью, входной регистр 1 разблокируется и на его входы может поступать лексическая единица следующего выражения.

Следовательно, на входнои регистр поступило выражение А-В/(С+2); а на выходном регистре выдано выражение

А,В,С,D,+,/, â€, Этот порядок следования символов соответствует польской инверсной записи входного выражения.

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

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

1Ф

1. Устройство для перевода выражений н польскую инверсную запись, содержащее входной регистр, вход которого является входом устройства, дешифратор лексических единиц, группой входов соединенный с группой выходов входного регистра, выходной регистр, группа выходов которого является выходом устройства, магазинную память, отличающееся тем, что, с целью повышения быстродействия оно содержит четыре группы элементов И, группу элементов ИЛИ, дешифратор коВ дов операции выражений, дешифратор кодов операций магазинной памятй,регистр кодов операций магазинной памяти, схему сравнения приоритетов, блок управления, первая группа входов которого подключена к группе выходов дешифратора лексических единиц, соответствующие входы элементов И первой и второй групп и дешифратора кодов операций выражений объединены и подключены к соответствующим выходам группы входного регистра, выходы элементов И первой группы подключены соответственно к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И третьей группы, а выходы подключены к группе входов выходного регистра, выходы элементов И второй группы подключены к группе входов магазинной памяти, первая группа выходов которой подключена к первым входам соответствукицих элементов И третьей группы, вторая группа выходов магазинной памяти подключена к первым входам соответствующих элементов И четвертой группы, выходы которых подключены к группе соответствующих входов регистра кода операций магазинной памяти, группа выходов которого подключена к группе соответствующих входов дешифратора кода операций магазинной памяти, группа выходов дешифратора кодов операций выражений подключена к первой группе входов схемы сравнения приоритетов, вторая группа входов которой подключена к групIS

)Ф

))

)Ф

)5

° Ф

iS

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Лебедев В.Н. Введение в системы программирования, М., "Статистика", 1975, с. 137-139.

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

У 611931, кл. G 06 F 7/38, 1978 (прототип).

890403

4Ьг

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

Редактор T. Веселовская Техред M. Надь Корректор В. Бутяга

Заказ 11008/79 Тираж 748 Подписное

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

113035, ?1осква, >Х-35 Раушская наб. д. 4/5

2 2

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