Устройство для перевода выражений в польскую инверсную запись Советский патент 1983 года по МПК G06F17/27 

.1 .

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

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

единиц, соответствующие вхЬды элементов И первой и второй групп и дешифратора кодов операций выражений объединены и подключены к соответствующим выходам входного регистра, выходы элементовИ первой группы подключены соответственно к первым входам группы элементов ИЛИ, вторые входы которых подключены к выходам соответствующих элементов И третьей группы, а выходы - к группе входов ,выходного регистра, выходы элементов И второй группы подключены к группе входов магазинной памяти, первая группа выходов которой подключена к первым входам соответствующих элементов И третьей группы, вторая группа выходов магазинной памяти подключена к первым входам соответствующих элементов И четвертой группы, выходы которых подключены к группе соответствующих входов регистра кодов операций магазинной памяти, группа выходов которого подключена 3 .9 к группе соответствующих входов дешифратора кодов операций магазинной памяти , группа выходов дешифратора кодов операций выражений подключена к первой группе входов схемы сравнения приоритетов, вторая группа входов которой подключена к группе выходов дешифратора кодов операций магазинной памяти и к второй группе входов блока управления, третья группа входов блока управления подключена к выходу схемы сравнения приоритетов, первый,второй, третий (Четвертый, пятый, шестой и седьмой выходы блока управления подключены соответственно к входам Чтение и Запись магазинной памяти, к вторым входам элементов и четвертой, второй, третьей .и первой групп соответственно, к управляющему входу входного регистра, а также блок управления, содержащий регистр команд, дешифратор микрокоманд, дешифратор команд, микропрограммную память, генератор импульсов, триггер группу элементов И, элемент И, причем входы регистра являются соответственно первой, второй и третьей гру пой входов блока управления, вход счетчика команд соединен с выходом з/Темента И, первый вход которого сое динен с выходом генератора импульсов а второй - с единичным выходом триггера, нулевой вход которого соединен с выходом первого элемента И группы, а единичный является входом Пуск блока управления, выходы регистра и счетчика команд соединены соответственно с входами дешифратора микрокоманд и дешифратора команд, выходы которых соединены соответстве но с адресными входами первой и второй групп микропрограммной памяти информационные выходы которой соединены с первыми входами соответствующих элементов И группы, вторые входы которых объединены и подключены к .выходу элемента И, а выходы являются выходами блока управления с пер вого по седьмой l. Недостатком известного устройства является отсутствие контроля наличия и порядка следования лексических еди ниц в исходном выражении. Цель изобретения - повышение достоверности в работе путем более ран него прекращения преобразования неправильных выражений и переход к пре образованию следующих выражений. Поставленная цель достигается тем, что в устройство введен блок проверки исходного выражения на наличие и порядок следования лексических единиц, содержащий реверсивный счетчик, первый, второй и третий элементы ИЛИ, первый и второй элементы И, элемент НЕ, дешифратор состояний и элемент задержки, причем первый и второй входы первого и второго элементов ИЛИ, первый вход первого элемента И и вход элемента задержки соединены с соответствующими выходами дешифратора лексических единиц, выходы первого и второго элементов ИЛИ подключены соответственно ко входам сложения и вычитания реверсивного счетчика, установочный вход которого подключен к выходу элемента задержки . и к входу элемента НЕ, выход которого подключен к входу синхронизации реверсивного счетчика и к второму входу первого элемента И, третий вход которого подключен к выходу дешифратора состояний, выходы первого и второго элементов W подключены соответственно к первому и второму входам третьего элемента ИЛИ выход которого является выходом Ошибка устройства, входы второго элемента И подключены к соответствующим выходам реверсивного счетчика, входы дешифратора состояний подключены к соответствующим инверсным входам реверсивного счетчика. На фиг. 1 представлена структурная схема устройства, на фиг. 2 структурная схема блока проверки исходного выражения на и порядок следования лексических единиц. Устройство содержит входной регистр 1, дешифратор 2 лексических единиц, магазинную память 3, регистр кодов операций магазинной памяти, дешифратор 5 кодов операций магазинной памяти, дешифратор 6 кодов операций выражений, схему 7 сравнения приоритетов, блок 8 управления, группу элементов ИЛИ 9, первую,вторую, третью и четвертую группы элементов И 10-13, выходной регистр I, блок 15 проверки исходного выражения на наличие и порядок следования лексических .единиц, который содержит реверсивный счетчик 16, первый и второй элементы ИЛИ 17 и 18,элемент 19 задержки, второй элемент И 20, дешифратор 21 состояний, первый элемент И 22, элемент НЕ 23, элемент ИЛИ . Входной регистр 1 используется для хранения очередной лексической единицы исходного выражения, дешифратор 2 лексических единиц разделяет лексические единицы на операнды, операции, скобки и т.д. Магазинная память 3 - это память с последовательным безадресным приципом записи и чteния, регистр Ц и дешифратор 5 кодов операций магазинной памяти совместно с дешифратором 6 кодов опе раций выражений и схемой 7 сравнения приоритетов реализуют логическую фу цию выработки и сравнения приоритетов. Блок 8 управления организует, взаимодействие всех элементов устройства и представляет собой типовую схему микропрограммного управления. Группа элементов ИЛИ 9, первая вторая, третья и четвертая группы элементов И 10-13 управляют передачами лексических единиц, а выходной регистр предназначен для хранения очередной лексической единицы в фор ме ПОЛИЗ. Блок 15 проверяет наличие и поря док следования лексических единиц в исходном выражении. Работа блока основана на методе подсчета весов логических единиц исходного выражения, назначаемых таким образом, что бы их сумма указывала на парность скобок и текущее число операндов « формируемой польской записи, включа промежуточные результаты, нёд которыми еще не выполнены операции. Лексическим единицам присваивают Ся следующие веса: операнд +1, п - местная операция (функция) 1-п скобка открывающая +1, скобка закрывающая -1 и т.д. В процессе преобразования правил ных выражений сумма весов лексических единиц не должна быть отрицательной, а в конце преобразования к дого выражения равняться плюс едини Реверсивный двоичный счетчик 16 используется для суммирования весов лексических единиц с учетом их знаков, элемент ИЛИ 17 обеспечивает по ступление сигналов на суммирующий вход счетчика, а элемент ИЛИ 18 на вычитающий. Элемент 19 задержки предназначен для получения временно задержки сигнала, соответствующего лексической единице конец выражения. с помощью этого сигнала осуществляется установка реверсивного счетчика в нулевое состояние. Значение текущей суммы на выходе реверсивного счетчика контролируется с помощью элемента И 20, а суммы, получаемой в конце преобразования исходного выражения - с помощью элемента дешифратора 21 состояния и элемента И 22. Элемент НЕ 23 блокирует выдачу ложного сигнала ошибки, а элемент ИЛИ обеспечивает поступление сигнала ошибки на выход блока проверки исходного выражения на наличие и порядок следования лексических единиц. Устройство работает следующим образом. Лексические единицы исходного выражения последовательно поступают на входной регистр 1, а затем на дешифраторы 2 и 6, причем первый разделяет их -на операнды, операции и скобки.,. Если очередная лексическая единица - левая скобка, то дешифратор 2 запускает блок 8 управления , управ- . ляющий сигнал которого разрешает за- пись этой единицы через группу э/ieментов И 11 из входного регистра 1 в магазинную память 3. Одновременно сигнал с дешифратора 2 подается на блок 15 и, пройдя в нем через элемент ИЛИ 17, поступает на реверсивный двоичный счетчик 16. Поскольку лексической единице - левой скобке ранее присвоен вес +1, то сигнал с дешифратора 2 поступает на. суммирующий вход реверсивного счетчика 1б. .Если очередная лексическая единица - операнд, то дешифратор 2 запускает блок 8 управления, управляющий сигнал которого разрешает через группы элементов И 10 и ИЛИ 9 перепись кода операнда из входного регистра 1 на выходной регистр Ц, Одновременно сигнал с дешифратора 2 подается на блок 15 и, пройдя в нем через элемент ИЛИ 17j поступает на реверсивный двоичный счетчик 16. Поскольку лексический единице - операнду присвоен вес +1 то сигнал с дешифратора 2 постуnaet на суммирующий вход реверсивного счетчика 16, к содержимому которого прибавляется единица. Если очередная лексическая единица - операция, то сигнал с выхода дешифратора 2 лексических единиц запускает блок 8 управления, а в блоках 4-7 начинается процесс выработки и сравнения приоритетов. По результату работы схемы 7 сравнения приоритетов лексических единиц - операции блок 8 управления организует либо запись через группу элементов И 11 в магазинную память, либо чтение из нее лексических единиц с большим пр оритетом. В режиме чтения лексическая единица - операция записывается через группы элементов И 12 и ИЛИ 9 в выходной регистр 1, Одновременно сигнал с дешифратора 2 подается на блок 15 и, пройдя в нем через элемент ИЛИ 18, поступает на вычитающий вход реверсивного счетчика Мб. Когда на входном регистре 1 появляется лексическая единица - правая Скобка, блок 8 управления блокирует входной регистр 1 и организует режим чтения из магазинной памяти 3 и запись ее содержимого в выходной регистр Ц до тех пор, пока на регистр k кодов операций магазинной памяти не поступит код лексической единицы левой скобки. Одновременно с этим сигнал с дешифратора 2 подается на блок 15 и, пройдя в нем через элемент ИЛИ 18, поступает на вычитающий вход реверсивного счетчика 16, из показаний ко торого вычитается единица. В процессе преобразования выражений непрерывно контролируется текущая сумма весов лексических единиц на выходе реверсивного счетчика 1б., а поступление сигналов на его вход обеспечивается разрешающим потенциалом, подаваемым на вход синхронизации счетчика с выхода элемента НЕ 23 Когда сумма весов лексических, еди ниц равна нулю или положительна при достаточной емкости счетчика 16, на его прямых выходах всегда формируетс код этой суммы, содержащий нули или единицы в соответствующих разрядах. Вследствие этого сигнал на выходе элемента И 20 отсутствует. Как только сумма весов лексических единиц станет отрицательной что свидетельствует о нарушении порядка следования или отсутствии каких-либо лексических единиц в исходном выражении, на выходе реверсивного счетчика 16 .формируется код, в ра рядах которого содержатсяодни едини цы. В этом случае .на выходе элемента И 20 формируется сигнал, который, пройдя через элемент ИЛИ 24, появляется на выходе блока 15 в виде сигнала ошибки. Преобразование входного выражения в форму ПОЛИЗ происходит до тех пор, пока в регистре 1 не окажется лексическая единица Конец выражения. При этом блок управления осуществляет последовательное чтение содержимого магазинной памяти 3 и запись в выходной регистр 14. После полного, освобождения магазинной памяти 3 ре-. гистр 1 разблокируется ина него могут поступать лексические единицы следующего выражения. Цикл работы устройства повторяется. Одновременно с этим проверяется значение суммы весов лексических единиц в конце преобразования выражения. Если эта сумма равна плюс единице, то на прямом выходе младшего разряда и на инверсных выходах остальных разрядов реверсивного счетчика 16 появляются единичные сигналы, вследствие чего сигнал на выходе дешифратора состояний будет отсутствовать. Не будет сигнала и на выходе элемента И 22. Если сумма весов в конце преобразования отличается от плюс единицы, то на выходе реверсивного счетчика будет другая кодовая комбинация. В этом случае сигнал с выхода дешифратора состояния подается на третий вход элемента И 22, на второй вход которого поступает сигнал с выхода элемента НЕ 23, а на первый - сигнал с входа блока 15, соответствующий лексической единице Конец выражения. Сигнал, появившийся на выходе элемента И 22, пройдя через элемент ИЛИ.24, воспринимается на выходе блока 15 в виде сигнала ошибки, Поскольку сигналом Конец выражения осуществляется сброс в нулевое состояние содержимого реверсивного счетчика 16, для предотвращения появления ложного сигнала ошибки на входе блока t5 контроля сигнал Конец выражения подается на счетчик через элемент 19 задержки. Одновременно сигнал с выхода элемента 19 задержки подается на вход элемента НЕ 23. Отсутствие сигнала на втором входе элемента И 22 исключает. появление ложного сигнала ошибки. Таким образом, введение в состав устройства блока проверки исходного выражения на наличие и порядок следования лексических единиц улучшает использование оборудования. Формула изобретения Устройство для перевода выражеНИИ в польскую инверсную запись по авт. св. If , о т л и ч а ю щ е ее я тем, что, с целью повышения достоверности в работе, в него введен блок проверки исходного выражения на. наличие и порядок следования лексических единиц, содержащий реверсивный счетчик, первый, второй и третий элементы ИЛИ, первый и элементы И, элемент НЕ, дешифратор состояний и элемент задержки/ причем первый и второй входы Первого и второго элементов ИЛИ, первый вход первого элемента И и вход элемен та задержки соединены с соответствующими выходами дешифратора лексических единиц, выходы первого и второго элементов ИЛИ подключены соответственно к входам сложения и вычитания реверсивного счетчика, установочный вход которого подключен к выходу элемента задержки и к входу элемента НЕ, выход которого подключен к входу синхронизации реверсивного счетчика и к второму входу первого элемента и, третий вход которого подключен к выходу дешифратора состояний, вы ходы первЪгр и второго элементов И подключены соответственно к первому и второму входам третьего элемента ИЛИ, выход которого является выходом Ошибка устройства, входы второго элемента И подключены к соответствующим выходам реверсивного счетчика, входы дешифратора состояний подключены к соответствующим инверсным входам реверсивного счетчика, Источники информации, принятые во внимание при экспертизе Авторское свидетельство СССР ff , кл, G Об F 15/38, 1981.

tsi