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

1

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

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

i fiEiiOKSiS

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

Сравнительный приоритет Устройством, реализующим рассмотренные способы перевода выражений в ПОЛИЗ, является ЦВМ, представляющее собой сложный универсальный комплекс дорогостоящего оборудования, причем осуществление операций перевода программными cпocoбa ш с помощью ЦВМ тре

АЛГОЛ, в польскую инверсную запись (подав). Здесь каяздый ограничитель имеет двойной приоритет, заданный таблично: магазинный - для ограничителей, находящихся в магазинной памяти, сравнительнй - для ограничителей, предназначенных для записи в магазинную память l .

3456789 10

3456789 10 бует больших затрат машинного времени. Наиболее близким к данному изобретению техническим решением является устройство для преобразования кодов с одного языка на другой, содержащее регистр приема, входы которого через 3 группу элементов И соединены со входами устройства, а выходы через дешиф ратор подключены к адресным входам блока памяти, выходы которого через регистр вьщачи соединены с выходом устройства, а также два элемента И и дополнительный разряд в регистре выдачи, причем единичный и нулевой выходы дополнительного разряда вьщачи подключены соответственно к первым входам первого и второго элементов И вторые входы которых соединены с управляющим входом устройства, выход первого элемента И соединен со счетным входом регистра приема, выход второго элемента И подключен к управляющим входам элементов И группы, а вход дополнительного разряда регистра вьщачи соединен с управляющим выходом блока памяти 21 . Данное устройство позволяет за счет обеспечения сопоставления входному выражению эквивалентной последовательности символов получить польскую инверсную запись исходного выражения, однако в этом случае необходима память неограниченного объема, спо собная вместить в себя эквивалентные последовательности символов для выражений произвольного вида, число которых практически бесконечно. При этом время преобразования, связанное с поиском, перебором и сравнением эквивалентов, размещенных в памяти большого объема будет велико, что исключает практическое применение такого . устройства для получения ПОЛИЗ. Цель изобретения - уменьшение времени перевода выражений в польскую инверсную запись, т.е. повышение быст родействия устройства. Поставленная цель достигается тем что устройство для перевода выражений в польскую инверсную запись, содержащее входной регистр, вход которого является входом устройства, дешифратор лексических единиц, группой входов соединенный с группой выходов входного регистра, выходной регистр, группа выходов которого является выходом устройства, магазинную память, четыре группы элементов И, группу эле ментов ИЛИ, дешифратор кодов операций выражений, дешифратор кодов операций магазинной памяти, регистр кодов операций магазинной памяти, схему сравнения приоритетов, блок управления, первая группа входов которого подключена к группе выходов дешифра3тора лексических единиц, соответствующие входы элементов И первой и второй групп и дешифратора кодов операций выражений объединены и подключены к соответствующим выходам группы входного регистра, выходы элементов И первой группы подключены соответственно к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходам соответствующих Элементов И третьей группы, а выходы подключены к группе входов выходного регистра, выходы элементов И второй группы подключены к группе входов магазинной памяти, первая группа выходов которой подключена к первым входам соответствующих элементов И третьей группы, вторая группа выходов магазиНной памяти подключена к первым входам соответствующих элементов И четвертой группы, выходы которых подключены к группе соответствующих входов регистра кода операций магазинной памяти, группа выходов которого подключена к группе соответствующих входов дешифратора кода операций магазинной памяти, группа выходов дешифратора кодов операций выражений подключена к первой группе входов схемы сравнения приоритетов, вторая группа входов которой подключена к группе выходов депшфратора кодов операций магазинной памяти и ко второй группе входов блока управления, третья rpynnd входов блока управления подключена к схеме сравнения приоритетов, первый, второй, третий, четвертый, пятый, шестой и седьмой выходы блока управления подключены соответственно ко входам Чтение и Запись магазинной памяти, ко вторым входам элементов И четвертой, второй, третьей и первой групп соответственно ,к управляющему входу входного регистра; блок управления содержит регистр, счетчик команд, дешифратор микрокоманд, дешифратор команд, микропрограммную память, генератор импульсов, триггер, группу элементов И, элемент И, причем входы регистра являются соответственно первой, второй и третьей группой входов блока управлений, вход счетчика команд соединен с выходом элемента И, первый вход которого соединен с выходом генератора импульсов, а второй с единичным выходом триггера, нулевой вход которого соединен с выходом первого элемента И группы, а единичный является входом Пуск блока управления, выходы регистра и счетчика команд соединены соответственно со входами дешифратора микрокоманд и дешифратора команд, выходы которых соединены соответственно с адресными входами первой и второй групп микропрограммной памяти, информационные выходы которой соединены с первыми входами соответствующих элементов И группы, вторые входы которых объединены и подключены к выходу элемента И, а выходы являются выходами блока управления с первого по седьмой,

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

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

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

S y,Yy, 4,X3

где S - управляющий сигнал схемы сранения приоритетов;

- приоритеты кодов операций входного выражения;

х - приоритеты кодов операций магазинной памяти.

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

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

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

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

S

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

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

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

чего производится разблокировка входного регистра ,

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

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

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

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

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

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

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

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

Следовательно, на входной регистр поступило выраж;ение A-B/(C+D); а на выходном регистре выдано выражение А,В,С,и,+ ,/,-, Этрт порядок следования символов соответствует польской инверсной записи входного выражения.

Таким образом, устройство позволяет осуществлять преобразование выражений в ПОЛИЗ в темпе последовательного чтения входного выражения, что значительно ускоряет процесс преобразования и существенно экономит машинное время ЦВМ. Формула изобретения I. Устройство для перевода выражений в польскую инверсную запись, содержащее входной регистр, вход которого является входом устройства, дешифратор лексических единиц, группой входов соединенный с группой выходов входного регистра, выходной регистр, группа выходов которого является выходом устройства, магазинную память, отличающееся тем, что, с целью повышения быстродействия оно содержит четыре группы элементов И, группу элементов ИЛИ, дешифраторкодов операции выражений, дешифратор кодов операций магазинной памяти,регистр кодов операций магазинной памяти, схему сравнения приоритетов, блок управления, первая группа входов которого подключена к группе выходов дешифратора лексических единиц, соответствующие входы элементов И первой и второй групп и дешифратора кодов операций выражений объединены и подключены к соответствующим выходам группы входного регистра, выходы элементов И первой группы подключены соответственно к первым входам элементов ИЛИ группы, вторые входы которых подключат) к выходам соответствующих элементов И третьей группы, а выходы подключены к группе входов выходного регистра, выходы элементов И второй группы подключены к группе входов магазинной памяти, первая группа выходов которой подключена к первым входам соответствующих элементов И третьей группы, вторая группа выходов магазинной памяти подключена к первым входам соответствующих элементов И четвертой группы, выходы которых подключены к группе соответствующих входов регистра кода операций магазинной памяти, группа выходов которого подключена к группе соответствую щих входов дешифратора кода операций магазинной памяти, группа выходов дешифратора кодов операций выражений подключена к первой группе входов схе мы сравнения приоритетов, вторая груп па входов которой подключена к груп310пе выходов дешифратора кодов операций магазинной памяти и ко второй группе входов блока управления, третья группа входов блока управления подключена к схеме сравнения приоритетов, первый, второй, третий, четвертый, пятый, шестой и седьмой выходы блока управления подключены соответственно ко входам Чтение и Запись магазинной памяти, ко вторым входам элементов И четвертой, второй, третьей и первой групп соответственно, к управляющему входу входного регистра. 2. Устройство по п. 1, отличающееся тем, что блок управления, содержит регистр, счетчик команд, дешифратор микрокоманд, дешифратор команд, микропрограммную память, генератор импульсов, триггер, группу элементов И, элемент И, причем входы регистра являются соответственно первой, второй и третьей группой входов блока управления, вход счетчика команд соединен с выходом элемента И, первый вход которого соединен с выходом генератора импульсов, а второй с единичным выходом триггера, нулевой вход которого соединен с выходом первого элемента И группы, а единичный является входом Пуск блока управления, выходы регистра и счетчика команд соединены соответственно со входами дешифратора микрокоманд и дешифратора команд, выходы которых соединены соответственно с адресными входами первой и второй групп микропрограммной памяти, информационные выходы которой соединены с первыми входами соответствующих элементов И группы, вторые входы которых объединены и подключены к выходу элемента И, а выходы являются выходами блока управления с первого по седьмой. Источники информации, принятые во внимание при экспертизе 1.Лебедев В.Н. Введение в системы программирования. М., Статистика, 1975, с. 137-139. 2.Авторское свидетельство СССР № 611931, кл. G 06 F 7/38, 1978 (прототип).

Фг/.

fit

/

/7

V V fФ

/y

f IT

- - -

/

I

0,