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

(54) УСТРОЙСТВО ДЛЯ ПЕРЕВОДА ВЫРАКИНИЙ В ПОЛЬСКУЮ ИНВЕРСНУЮ ЗАПИСЬ АЛГОЛ, в польскую инверсную запись (ПОЛИЗ). Здесь каждый ограничитель имеет двойной приоритет, заданный таблично: магазинный - для ограничителей, находящихся в магазинной памяти, сравнительнй - для ограничителей, предназначенных для записи в ма-. газинную память 1. ограничители % ),1 трнтМагазинный приоритет О - 1 2 3 4 5 6 7 8 9 10 Сравнительныйприоритет О2 3 4 5 6 7 8 9 О Изобретение .относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных и производства программ для ЭВМИзвестен алгоритм перевода любых3 по сложности выражений, правильных с точки зрения синтаксиса языка типа Устройством, реализующим рассмотренные способы перевода выражений в ПОЛИЗ, является ЦВМ, представляющее собой сложный универсальный комплекс дорогостоящего оборудования, причем осуществление операций перевода про-. граммными способами с помощью ЦВМ требует больших затрат машинного времени.Наиболее близким к данному изобре" тению техническим решением является устройство для преобразования кодов с одного языка на другой, содержащее регистр приема, входы которого через89040 группу элементов И соединены со входами устройства, а выходы через дешифратор подключены к адресным входам блока памяти, выходы которого через регистр выдачи соединены с выходом устройства, а также два элемента И и дополнительный разряд в регистре выдачи, причем единичный и нулевой выходы дополнительного разряда выдачи подключены соответственно к первым входам первого и второго элементов И, вторые входы которых соединены с управляющим входом устройства, выход первого элемента И соединен со счетным входом регистра приема, выход второго элемента И подключен к управляющим входам элементов И группы, а вход дополнительного разряда регистра выдачи соединен с управляющим выходом блока памяти 2.Данное устройство позволяет за счет обеспечения сопоставления входному выражению эквивалентной последовательности символов получить польскую инверсную запись исходного выражения, однако в этом случае необходима память неограниченного объема, способная вместить в себя эквивалентные 25 последовательности символов для выражений произвольного вида, число кото 30 рых практически бесконечно, При этом время преобразования, связанное с поиском, перебором и сравнением эквивалентов, размещенных в памяти большого объема будет велико, что исключает практическое применение такого, устройства для получения ПОЛИЗ.Цель изобретения - уменьшение времени перевода выражений в польскую инверсную запись, т.е. повышение быстродействия устройства.Поставленная цель достигается тем, что устройство для перевода выражений в польскую инверсную запись, содержащее входной регистр, вход которого является входом устройства, дешифратор лексических единиц, группой входов соединенный с группой выходов входного регистра, выходной регистр, группа выходов которого является выходом устройства, магазинную память, 50 четыре группы элементов И, группу элементов ИЛИ, дешифратор кодов операций выражений, дешифратор кодов операций магазинной памяти, регистр кодов операций магазинной памяти, схе му сравнения приоритетов, блок управления, первая группа входов которого подключена к группе выходов дешифраз 4тора лексических единиц, соответствующие входы элементов И первой ивторой групп и дешифратора кодов операций выражений объединены и подключены к соответствующим выходам группы входного регистра, выходы элементов И первой группы подключены соответственно к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходам соответствующихэлементов И третьей группы, а выходыподключены к группе входов выходногорегистра, выходы элементов И второйгруппы подключены к группе входов магазинной памяти, первая группа выходов которой подключена к первым входамсоответствующих элементов И третьей группы, вторая группа выходов магазииной памяти подключена к первымвходам соответствующих элементов Ичетвертой группы, выходы которых подключены к группе соответствующих входов регистра кода операций магазинной памяти, группа выходов которого подключена к группе соответствукцих входов дешифратора кода операций магазинной памяти, группа выходов дешифратора кодов операций выраженийподключена к первой группе входов схемы сравнения приоритетов, вторая группа входов которой подключена к группе выходов дешифратора кодов операций магазинной памяти и ко второй группе входов блока управления, третья группа входов блока управления подключена к схеме сравнения приоритетов, первый, второй, третий, четвертый, пятый, шестой и седьмой выходы блока управления подключены соответственно ко входам "Чтение" и "Запись магазинной памяти, ко вторым входам элементов И четвертой, второй,третьей и первой групп соответственно,к управляющему входу входного регистра; блок управления содержит регистр, счетчик команд, дешифратор микрокоманд, дешифратор команд, микропрограммную память, генератор импульсов, триггер, группу элементов И, элемент И, причем входи регистра являются соответственно первой, второй и третьей группой входовблока управлений, вход счетчика команд соединен с выходом элемента И,первый вход которого соединен с выходом генератора импульсов, а второй - с единичным выходом триггера, нулевой вход которого соединен с выходом первого элемента И группы, а единич890403 5ный является входом "Пуск" блока управления, выходы регистра и счетчикакоманд соединены соответственно совходами дешифратора микрокоманд и дешифратора команд, выходы которых со- Вединены соответственно с адреснымивходами первой и второй групп микропрограммной памяти, информационные выходы которой соединены с первыми входами соответствующих элементов И груп фпы, вторые входы которых объединеныи подключены к выходу элемента И, авыходы являются выходами блока управления с первого по седьмой.На Фиг. 1 представлена блок-схема 1устройства на фиг. 2 - блок-схемаблока управления.Устройство содержит входной. регистр 1, дешифратор 2 лексических единиц, магазинную память 3, регистр 4 ЗЭкодов операций магазинной памяти,дешифратор 5 кодов операций магазиннойпамяти, дешифратор 6 кодов операцийвыражений, схему 7 сравнения приоритетов, блок 8 управления, группу эле- Иментов ИЛИ 9, первую, вторую, третьюи четвертую группы элементов И 1 О,11, 12 и 3, выходной регистр 14, регистр 15, счетчик 16 команд, дешифратор 17 микрокоманд, дешифратор 18 ко- щманд, микропрограммную память 19,генератор 20 импульсов, триггер 21,группу элементов И 22, элемент И 23,Входной регистр 1 используется дляхранения очередной анализируемой лексической единицы входного выражения,дешифратор 2 лексических единиц разделяет лексические единицы на операнды, операции и скобки, магазиннаяпамять 3 - это память с последователь Фным безадресным принципом записи ичтения, регистр 4 и дешифратор 5 кодов операций магазинной памяти совместно с дешифратором б кодов операций выражений и схемой 7 сравненияприоритетов реализуют Функцию выработ 4 Вки и сравнения приоритетов5 уууЯу х Ячу,хх,хгде 5 - управляющий сигнал схемы сравнения приоритетов; Му - приоритеты кодов операцийвходного выражения;х - приоритеты кодов операций магазинной памяти. ИБлок 8 управления организует взаимодействие всех элементов устройства и представляет собой типовую схему микропрограммного управления. Устройство работает следующим образом.Лексические единицы исходного выражения последовательно поступают навходной регистр 1, а затем на дешифраторы 2 и 6, которые разделяют их наоперанды, операции и скобки.Если очередная лексическая единица - левая скобка, то дешифратор 2запускает блок 8 управления, управляющий сигнал которого разрешает через группу элементов И 11 запись этойединицы из входного регистра 1 в магазинную память 3.Если очередная лексическая едини- .ца - операнд, то дешифратор 2 запускает блок 8 управления, управляющийсигнал которого разрешает через группы элементов И 10 и ИЛИ 9 переписькода операнда входного регистра 1 навыходной регистр 14.Если очередная лексическая единица - операция, то управляющий сигналс выхода дешифратора 2 лексическихединиц запускает блок 8 управления,а в блоках 4-7 начинается процесс выработки и сравнения приоритетов.Блок 8 управления блокирует записьочередной лексической единицы вовходной регистр 1. Лексические еди"ннцы - операции со входного регистра 1, а нз магазинной памяти 3 черезрегистр 4 поступают соответственнона дешифраторы 6 и 5, где определяются их приоритеты,По результату работы схемы 7 сравнения приоритетов лексических еди- "ниц-операций блок 8 управления организует либо запись через группу элементов И 11 в магазинную память, либо чтение из нее лексических единицс большим приоритетом, В режиме чтения лексическая единица-операция записывается через группы элементов И 12и ИЛИ 9 в выходной регистр 4, послечего производится разблокировка входного регистра 1Когда во входном регистре 1 нахо"дится правая скобка, блок 8 управления блокирует входной регистри организует режим чтения из магазиннойпамяти 3 и запись ее содержимого ввыходной регистр 14 до тех пор, покана регистр 4 кодов операций магазинной памяти не поступит левая скобка. После этого блок 8 управленияразблокирует входной регистрПреобразование входного выражения в форму ПОЛИЗ происходит до техпор, пока н регистре 1 не окажется лексическая единицаКонец выраже 1 шя". При этом блок 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 запускаетблок 8 управления и начинается процесс выработки и сравнения приоритетов. Входной регистр 1 блокируется.Так как приоритет операции "+" вышевнутримагазинного приоритета левойскобки, то "+ записывается в магазинную память 3. Входной регистр 1 разблокируется и на него принимается лексическая единица "Т" - операнд, которая записывается в выходной регистр 14,Очередная лексическая единицавходного выражения принимается навходной регистр 1. Дешифратор 2 определяет, что на входном регистре 1 находится правая скобка. Входной регистр 1 блокируется и блок 8 управления анализирует содержимое регистра 4кодов операций магазинной памяти 3.К этому моменту в магазинную памятьзаписаны следующие единицы: в , /,+, причем в "верхушкемагазинной памяти находится "+". Лексическая единица "+" читается из магазинной памятии записывается в выходной регистр 14.Блок 8 управления вновь анализируетсодержимое "верхушки" магазинной памяти, и, так как теперь в ней находится левая скобка, то производитсяее чтение в регистр 4 беэ записи ввыходной регистр 4 стирание из "верхушки" магазинной памяти). Входнойрегистр 1 разблокируется и на негопринимается очередная лексическаяединица входного выражения "Конец выражения". Дешифратор 2 запускаетблок 8 управления, входной регистр 1блокируется и лексические единицы,записанные в магазинную память, последовательно читаются в выходной регистр 14. Когда магазинная память 3освобождается полностью, входной регистр 1 разблокируется и на его входы может поступать лексическая единица следующего выражения. Э О 1 Э ЗФ ЭЭ М ЭЭЭ Следовательно, на входной регистр поступило выражение А-В/(С+2); а на выходном регистре выдано выражение А,В,С,Р,+,/, в , Этот порядок следования символов соответствует польской инверсной записи входного выражения. Таким образом, устройство позволяет осуществлять преобразование выраного чтения входного выражения, чтозначительно ускоряет процесс преобразования и существенно экономит машинное время ЦВМ. ЭЭ . жений в ПОЛИЗ в темпе последовательформула изобретения Э1 Ф Э ЭФ ЭЭ ЭФ ЭЭФ 4 ЭФ 1. Устройство для перевода выражений н польскую инверсную запись, содержащее входной регистр, вход которого является входом устройства, дешифратор лексических единиц, группой входов соединенный с группой выходов входного регистра, выходной регистр, группа выходов которого является выходом устройства, магазинную память, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия оно содержит четыре группы элементов И, группу элементов ИЛИ, дешифраторкоВдов операции выражений, дешифратор кодов операций магазинной памятй,регистр кодов операций магазинной памяти, схему сравнения приоритетов, блок управления, первая группа входов которого подключена к группе выходов дешифратора лексических единиц, соответствующие входы элементов И первой и второй групп и дешифратора кодов операций выражений объединены и подключены к соответствующим выходам группы входного регистра, выходы элементов И первой группы подключены соответственно к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И третьей группы, а выходы подключены к группе входов выходного регистра, выходы элементов И второй группы подключены к группе входов магазинной памяти, первая группа выходов которой подключена к первым входам соответствукицих элементов И третьей группы, вторая группа выходов магазинной памяти подключена к первым входам соответствующих элементов И четвертой группы, выходы которых подключены к группе соответствующих входов регистра кода операций магазинной памяти, группа выходов которого подключена к группе соответствующих входов дешифратора кода операций магазинной памяти, группа выходов дешифратора кодов операций выражений подключена к первой группе входов схемы сравнения приоритетов, вторая группа входов которой подключена к группе выходов дешифратора кодов операциймагазинной памяти и ко второй группевходов блока управления, третья группа входов блока управления подключенак схеме сравнения приоритетов, первый,второй, третий, четвертый, гятый, шестой и седьмой выходы блока управленияподключены соответственно ко входам"Чтение" и "Запись" магазинной памяти, ко вторым входам элементов И четвертой, второй, третьей и первойгрупп соответственно, к управляющему входу входного регистра. 2. Устройство по п. 1, о т л и ч аю щ е е с я тем, что блок управления.содержит регистр, счетчик команд, дешифратор микрокоманд, дешифратор команд, микропрограммную память, генератор импульсов, триггер, группу элементов И, элемент И, причем входы регистра являются соответственно первой, второй и третьей группой входовблока управления, вход счетчика команд соединен с выходом элемента И,первый вход которого соединен с выходом генератора импульсов, а второй -с единичным выходом триггера, нулевой вход которого соединен с выходомпервого элемента И группы, а единичный является входом "Пуск" блока управления, выходы регистра и счетчикакоманд соединены соответственно совходами дешифратора микрокоманд идешифратора команд, выходы которыхсоединены соответственно с адреснымивходами первой и второй групп микропрограммной памяти, информационныевыходы которой соединены с первымивходами соответствующих элементов Игруппы, вторые входы которых объединены и подключены к выходу элемента И,а выходы являются выходами блока управления с первого по седьмой.Источники информации,принятые во внимание при экспертизе1. Лебедев В,Н. Введение в системы программирования, М., "Статистика",1975, с. 137-139.2. Авторское свидетельство СССРУ 611931, кл. С 06 Г 7/38, 1978Т дак каз 1100 8/79 Тираж 748ВНИИПИ Государственного комитетапо делам изобретений и открытий113035, Москва, ХРаушская наб. д. 4/5филиал ППП Патент", г. Ужгород, ул. Проектная, 4 Составитель В. Евстиская Техред М. Надь неевКорректор Подписное СССР Бутяга- ФФ %