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

(51)М. Кл. 6 06 Г 15/38 Гкудлрстееякый кемктет СССР вв делам кзфвретеккй к етлрытик(54) УСТРОИСТВО ДЛЯ ПЕРЕВО 8 ПОЛЬСКУ 6 ИНВЕРСНУ 10 ВЫРАЖЕНИИ ПИСЬ элемен" Изобретение относится к вычислительной технике и может быть исполь"зовано в автоматизированных систе-мах обработки данныхи производствапрограмм для ЭВИ,По основному. авт. св. )г 890403известно устройство для перевода выражений в польскую инверсную запись,содержащее входной регистр, вход которого является входом устройства,дешифратор лексических единиц, груп"пой входов соединенный с группойвыходов входного регистра, выходнойрегистр, группа выходов которогоявляется выходом устройства, магазинную память; четыре группы элементовИ, группу элементов ИЛИ, дешифраторкодов операций выражений, дешифратор кодов операций магазинной памяти, регистр кодов операций магазинной памяти, схему сравнения приоритетов, блок управления, первая группа входов которого подключена к группе выходов дешифратора лексических единиц, соответствующие входытов И первой и второй групп и дешифратора кодов операций выраженийобъединены и подключены к соответствующим выходам входного регистра, выходы элементов:И первой группыподключены соответственно к первымвходам группы элементов ИЛИ, вторыевходы которых подключены к выходам соответствующих элементов И третьейгруппы, а выходы - к группе входоввыходного регистра, выходы элементов И второй группы подключены кгруппе входов магазинной памяти, первая группа выходов которой подключена к первым входам соответствующихэлементов И третьей группы, втораягруппа выходов магазинной памятиподключена к первым входам соответ 2 о ствующих элементов И четвертой группы, выходы которых подключены к группе соответствующих входов регистракодов операций магазинной памяти,группа выходов которого подключенак группе соответствующих входов дешифратора кодов операций магазинной памяти , группа выходов дешифратора кодов операций выражений подключена к первой группе входов схемы сравнения приоритетов, вторая группа входов которой подключена к группе выходов дешифратора кодов операций магазинной памяти и к второй группе входов блока управления, третья группа входов блока управления подключена к выходу схемы сравнения приоритетов, первый, второй, третий, четвертый, пятый, шестой и седьмой выходы блока управления подключены соответственно к входам "Чтение" и "Запись" магазинной памяти, к вторым входам элементов и четвертой, второй, третьей .и первой групп соответственно, к управляющему входу входного регистра, а также блок управления, содержащий регистр команд, дешифратор микрокоманд, дешифратор команд, микропрограммную память, генератор импульсов, триггер, группу элементов И, элемент И, причем входы регистра являются соответственно первой, второй и третьей груп пой входов блока управления, вход счетчика команд соединен с выходом элемента И, первый вход которого сое" динен с выходом генератора импульсов, а второй - с единичным выходом триг" гера, нулевой вход которого соединен с выходом первого элемента И группы, а единичный является входом "Пуск" блока управления, выходы ре" гистра и счетчика команд соединены соответственно с входами дешифратора микрокоманд и дешифратора команд, выходы которых соединены соответствен но с адресными входами первой и второй групп микропрограммной памяти, информационные выходы которой соединены с первыми входами соответствующих элементов И группы, вторые входы которых обьединены и подключены к,выходу элемента И, а выходы являются выходами блока управления с первого по седьмой 1 .Недостатком известного устройства является отсутствие контроля наличия и порядка следования лексических единиц в исходном выражении.Цель изобретения - повышение достоверности в работе путем более раннего прекращения преобразования неправильных выражений и переход к преобразованию следующих выражений. 1437Поставленная цель достигается тем, что в устройство введен блок проверки исходного выражения на наличие и порядок следования лексических единиц, содержащий реверсивный счетчик, первый, второй и третий элементы ИЛИ, первый и второй элементы И, элемент НЕ, дещифратор состояний и элемент задержки, причем первый и второйвходы первого и второго элементовИЛИ, первый. вход первого элемента И и вход элемента задержки соединены с соответствующими выходами дешифратора лексических единиц, выходы первого й второго элементов ИЛИ подклюцены соответственно ко входам сложения и вычитания реверсивного счетчика, установочный вход которого подключен к выходу элемента задержки и к входу элемента НЕ, выход которого подключен к входу синхронизации реверсивного счетчика и к второму входу первого элемента И, третий вход которого подключен к выходу дешифратора состояний, выходы первого и второго элементов И подключены соответственно к первому и второму входам третьего элемента ИЛИ, выход которого является выходом "Ошибка" устройства, входы второгб элемента И подключены к соответствующим выходам реверсивного счетчика, входы дешифратора состояний подключены к соответствующим инверсным входам реверсивно,го счетчика.На фиг, 1 представлена структурная схема устройства, на фиг, 2 структурная схема блока проверки исходного выражения на наличие и порядок следования лексических единиц.Устройство содержит входной регистр 1, дешифратор 2 лексическихединиц, магазинную память 3, регистр 4 кодов операций магазинной памяти, дешифратор 5 кодов операций магазинной памяти, дешифратор 6 кодов операций выражений, схему 7 сравнения приоритетов, блок 8 управления, группу элементов ИЛИ 9 первую, вторую, третью и четвертую группы элементов И 10-13, выходной регистр 14, блок 15 проверки исходного выражения на наличие и порядок следования лексических .единиц, который содержит реверсивный счетчик 16, первый и второй элементы ИЛИ 17 и 18,элемент19 задержки, второй элемент И 20,дешифратор 21 состояний, первый эле9914 5мент И 22, элемент НЕ 23, элемент ИЛИ 24.Входной регистр 1 используется для хранения очередной лексической единицы исходного выражения, дешиф".ратор 2 лексических единиц разделяет лексические единицы на операнды, операции, скобки и т.д. Иагазинная память 3 - это память с последовательным безадресным приципом записи 1 О и чтения, регистр 4 и дешифратор 5 кодов операций магазинной памяти совместно с дешифратором 6 кодов операций выражений и схемой 7 сравнения приоритетов реализуют логическую функцию выработки и сравнения приоритетов, Блок 8 управления организует, взаимодействие всех элементов устройства и представляет собой типовую схему микропрограммного управле- ю ния. Группа элементов ИЛИ 9, первая, вторая, третья и четвертая группы элементов И 10-13 управляют передачами лексических единиц, а выходной регистр 14 предназначен для хранения 25 очередной лексической единицы в форме ПОЛИЗ.Блок 15 проверяет наличие и поря" док следования лексических единиц в исходном выражении. Работа блока зв основана на методе подсчета весов логических единиц исходного выражения, назначаемых таким образом, чтобы их сумма указывала на парность скобок и текущее число операндов а формируемой польской записи, включая промежуточйые результаты, над которыми еще не выполнены операции. Лексическим единицам присваиваются следующие веса: операнд "+Р, и - местная операция (функция) "1-и", скобка открывающая "+1", скобка закрывающая "-1" и т,д.В процессе преобразования правильных выражений сумма весов лексических единиц не должна быть отрицательной а в конце преобразования каждого выражения равняться опас единице.Реверсивный двоичный счетчик 16 используется для суммирования весов лексических единиц с учетом их знаков, элемент ИЛИ 17 обеспечивает поступление сигналов на суммирующий вход счетчика, а элемент ИЛИ 1855 на вычитающий. Элемент 19 задержки предназначен для получения временной задержки сигнала, соответствующего лексической единице "конец выраже 37 ь ния". С помощью этого сигнала осуществляется установка реверсивногосчетчика в нулевое состояние. Значение текущей суммы на выходе реверсивного счетчика контролируется с по"мощью элемента И 20, а суммы, получаемой в конце преобразования исходного выражения - с помощью элеУмента дешифратора 21 состояния иэлемента И 22. Элемент НЕ 23 блокирует выдачу ложного сигнала ошибки,а элемент ИЛИ 24 обеспечивает поступление сигнала ошибки на выход блокапроверки исходного выражения на наличие и порядок следования лексическихединиц.Устройство работает следующим образом.Лексические единицы исходного выражения последовательно поступают навходной регистр 1, а затем на дешиф"раторы 2 и 6, причем первый разделяет их на операнды, операции и скобки,Если очередная лексическая единица - левая скобка, то дешифратор 2запускает блок 8 управления, управляющий сигнал которого разрешает за-пись этой единицы через группу эле.ментов И 11 из входного регистра 1в магазинную память 3. Одновременносигнал с дешифратора 2 подаетсяна блок 15 и, пройдя в нем через элемент ИЛИ 17, поступает на реверсивный двоичный счетчик 16. Посколькулексической единице - левой скобкеранее присвоен вес ".+1", то сигнал сдешифратора 2 поступает на. суммирующий вход реверсивного счетчика 16.,Если очередная лексическая единица - операнд, то дешифратор 2 запускает блок 8 управления, управляющийсигнал которого разрешает через группы элементов И 10 и ИЛИ 9 переписькода операнда из входного регистра 1на выходной регистр 14, Одновременносигнал с дешифратора 2 подается наблок 15 и, пройдя в нем через элементИЛИ 17 поступает на реверсивный двоичный счетчик 16. Поскольку лексический единице - операнду присвоен вес"+1" то сигнал с дешифратора 2 поступает на суммирующий вход реверсивно-го счетчика 16, к содержимому которого прибавляется единица. Если очередная лексическая единица - операция, то сигнал с выхода дешифратора 2 лексических единиц запус7, 9914кает блок 8 управлений, а в блоках4-7 начинается процесс выработки и.сравнения приоритетов, По результатуработы схемы 7 сравнения приоритетов лексических единиц - операции 3блок 8 управления организует либозапись через группу элементов И 11в магазинную память, либо чтение изнее лексических единиц с большим при"оритетом. В режиме чтения лексичес"кая единица - операция записываетсячерез группы элементов И 12 и ИЛИ 9в выходной регистр 14,Одновременно сигнал с дешифратора 2 подается на блок 15 и, пройдя 15в нем через элемент ИЛИ 18, поступает на вычитающий вход реверсивного счетчика 16.Когда на входном регистре 1 появляется лексическая единица - правая 20скобка, блок 8 управления блокируетвходной регистр 1 и организует режим чтения из магазинной памяти 3 изапись ее содержимого в выходной ре"гистр 14 до тех пор, пока на регистр 2 зкодов операций магазинной памятине поступит код лексической единицылевой скобки,Одновременно с этим сигнал с дешифратора 2 подается на блок 15 и, з 0пройдя в нем через элемент ИЛИ 18,поступает на вычитающий вход реверсивного счетчика 16, из показаний ко"торого вычитается единица,В процессе преобразования выражений непрерывно контролируется те"кущая сумма весов лексических единицна выходе реверсивного счетчика 16.,а поступление сигналов на его входобеспечивается разрешающим потенциалом, подаваемым на вход синхронизации счетчика с выхода элемеа НЕ 23.Когда сумма весов лексических.еди".ниц равна нулю или положительна придостаточной емкости счетчика 16, наего прямых выходах всегда формируется. код этой суммы, содержащий нули илиединицы в соответствующих разрядах,Вследствие этого сигнал на выходеэлемента И 20 отсутствует.Как только сумма весов лексичес"ких единиц станет отрицательной,что свидетельствует о нарушении по-рядка следования или отсутствии каких-либо лексических единиц в исход"Яном выражении, на выходе реверсивного счетчика 16 формируется код, в раз-рядах которогб содержатся одни единицы. В. этом случае .на выходе элемента 37 8И 20 формируется сигнал который, пройдя через элемент ИЛИ 24, появляется на выходе блока 15 в виде сигнала ошибки. Преобразование входного выраженияв форму ПОЛИЗ происходит до тех пор,пока в регистре 1 не окажется лексическая единица "Конец выражения".При этом блок управления осуществля"ет последовательное чтение содержимого магазинной памяти 3 и запись ввыходной регистр 14. После полного .освобождения магазинной памяти 3 ре-.гистр 1 разблокируется и на него могут поступать лексические единицыследующего выражения, Цикл работыустройства повторяется.Одновременно с этим проверяетсязначение суммы весов лексических единиц в конце преобразования выражения. Если эта сумма равна плюс единице, то на прямом выходе младшегоразряда и на инверсных выходах остальных разрядов реверсивного счетчика 16 появляются единичные сигналы, вследствие чего сигнал на выходе дещифратора состояний будет отсутствовать, Не будет сигнала и на вы-.ходе элемента И 22,Если сумма весов в конце преобразования отличается от плюс единицы,то на выходе реверсивного счетчикабудет другая кодовая комбинация, Вэтом случае сигнал с выхода дешифратора состояния подается на третийвход элемента И 22, на второй вход которого поступает сигнал с выходаэлемента НЕ 23, а.на первый - сигналс входа блока 15, соответствующийлексической единице "Конец выражения". Сигнал, появившийся на выходеэлемента И 22, пройдя через элементИЛИ;24, воспринимаетсяна выходеблока 15 в виде сигнала ошибки. Поскольку сигналом "Конец выражения осуществляется сброс в нулевое состояние содержимого реверсивного счетчика 16, для предотвращения появления ложного сигнала ошибки на входе блока 15 контроля сигнал "Конец выражения" подается на счетчик через элемент 19 задержки. Одновременно сигнал .с выхода элемента 19 задержкиподается на вход элемента НЕ 23. Отсутствие сигнала на втором входе элемента" И 22 исключает, появление ложного сигнала ошибки,7 10ких единиц, выходы первого и второгоэлементов ИЛИ подключены соответственно к входам сложения .и вычитанияреверсивного счетчика, установочныйвход которого подключен к выходу элемента задержки и к входу элементаНЕ, выход которого подключен к входусинхронизации реверсивного счетчикаи к второму входу первого элементаИ, третий вход которого подключенк выходу дешифратора состояний, вы-.ходы первого и второго элементов Иподключены соответственно к первомуи второму входам третьего элементаИЛИ, выход которого является выхо.дом нОшбка" устройства, входы второ-.го элемента И подключены к соответствующим выходам реверсивного счетчика, входы дешифратора состоянийподключены к соответствующим инверс-ным входам реверсивного счетчика,9, 991 ЦТаким образом, введение в состав устройства блока проверки исходного выражения на наличие и порядок следования лексических единиц улучшает использование оборудования. 5 формула изобретения Устройство для перевода выраже- , 10 ний в польскую инверсную запись по авт. св. 11 890103, о т л и ч а ющ е е с я . тем, что, с целью повышения достоверности. в работе, в него введен блок проверки исходного выра- д жения на. наличие и порядок следова: ния лексических единиц, содержащий реверсивный счетчик, первый, второй и третий элементы ИЛИ, первый и второй элементы И, элемент НЕ дешиф- щ ратор состояний и элемент задержки, причем первый и второй входы первого и второго элементов ИФ, первый вход первого элемента И и вход элемента задержки соединены с соответству" и ющими выходами дешифратора лексичесИсточники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР М 890103 ф кл 6 06 Г 1 /38 1981/68 аз 1 дф илиал ППП Патент", г. Ужгород, ул. Проектная Тираж 704 ИПИ Государственн по делам иэобретеМосква, Ж,го комите ий и откры аушская н ПодписиСССРй