1062721 - Устройство для синтаксически-управляемого перевода

Устройство для синтаксически-управляемого перевода

Иллюстрации

Показать все

Реферат

1. УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКИ-УПРАВЛЯЕМОГО ПЕРЕВОДА, СОдержсицее арифметико-логический блок, блок управления и блок оперативной памяти, причем управляющий выход арифметико-логического блока соединен с первым входом блока управления , отличающееся тем, что, с цельй расширения функциональных возможностей путем увеличения класса выполняеких переводов и обеслечения перепрогрё1м« ирования, в него введены блок формирования команд, блок ассоциативной памяти, блок объединения списков, четыре мультиплексора , блок элементов ИЛИ, счетчик адреса записи и счетчик адреса списка, причем первый вход. блока формирования команд соединен с адресным входом устройства, второй вход блока формирования команд соединен с его первым выходом, с входом опроса блока ассоциативной памяти, с первыми входами первого, второго и третьего мультиплексоров и с первым входом блока элементов ИЛИ, второй выход блока формирования команд соединен с вторяз1м входом блока управления и первым управляющим входом арифметико-логического блока, информационный вход которого соединен с выходом блока элементов ИЛИ, информационный выход арифметико-логического блока соединен с .вторым входом первого мультиплексора , третий вход которого соединен с информационным входом устройства, выход первого мультиплексора соединен с первым информационным входом блока ассоциативной памяти, адресный вход записи которого соединен с выходом счетчика адреса записи, второй информационный вход блока ассоциативной памяти соединен с первым выходом блока объединения -списков, первый информационный выход соединен с первым входом блока объединения списков, с вторымивходами второго и третьего мультиплексоров, с вторым входом блока элементов ИЛИ, второй информационный выход блока ассоциативной памяти соединен с вторым входом блока объединения списков О и с третьим входом второго мульти .плексора, .второй выход блока объеС динения списков подключен к четвертому входу второго мультиплексб-г ра, третий выход подключен к третьему информационному входу блока ассоциативной памяти и к первому входу четвертого мультиплексора, третий вход блока объединения списков подключен к выходу счетчика адреса списка и к второму входу четвертого мультиплексора , выход второго мультиплек-j сора соединен с числовым входом блока оперативной памяти, выход третьего мультиплексора соединен с информационным выходом устройства, выход четвертого мультиплексора соединен С адресным входом блока оперативной памяти, третий вход блока управления соединен с входом готовности устройства, четвертая вход соединен с управляющим выходом блока ассоциативной памяти, первый, второй и третий выходы блока управления соединены соответственно с входа ми управления записью, опросом и стиранием блока ассоциативной памя;Ти , выходы с четвертого по двенадцатый блока управления соединены

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

ЗСЮ 6 06 F 15/38 ь

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3448062/18-24 (22)07.06.82 (46)23.12.83. Бкл. Р 47, (72)А.И. Степанов (71)московский инженерно-физический институт (53) 681.325.5(OSS. 8) (56)1. Авторское свидетельство СССР

Р 519715, кл. G 06 F 15/34; 1974.

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

Р 674028, кл. G 06 Р 15/20, 1976 (п х тотип). (54)(57) 1. УСТРОЙСТВО ДЛЯ СННТАКСИЧЕСКИ-УПРАВЛЯЕМОГО ПЕРЕВОДА, содержащее арифметико-логический блок, блок управления и блок оперативной памяти, причем управлякщий выход арифметико-логического блока соединен с первым входом блока управления, о т л и ч а ю щ е е с я тем, что, с цельЬ расюирения функциональных возмоаностей путем увеличения класса выполняемых переводов и обес.печения перепрограммирования, в него введены блок формирования команд, блок ассоциативной памяти, блок объединения списков, четыре мультиплексора, блок элементов ИЛИ, счетчик адреса записи и счетчик адреса списка, причем первый вход блока формирования команд соединен с адресным входом устройства, второй вход блока формирования .команд соединен с его первым выходом,, с входом опроса блока ассоциативной памяти, с первыми входами первого, второго и третьего мультиплексоров и с первым входом блока элементов

ИЛИ, второй выход блока формирования команд соединен с вторым вхо-. дом блока управления и первым управлякщим входом арифметико-логического блока, информационный вход которого соединен с выходом блока элементов ИЛИ, информационный выход ариФметико-логического блока соединен с вторым входом первого мультиплекSU«2721 A сора, третий вход которого соединен с информационным входом устройства, выход первого мультиплексора соединен с первым информационным входом блока ассоциативной памяти, адресный вход записи которого соединен с выходом счетчика адреса записи, второй информационный вход блока ассоциативной памяти соединен с первым выходом блока объединения .списков, первый информационный выход соединен с первым входом блока объединения списков, с вторыми входами второго и третьего мультиплексоров, с вторым входом блока элементов ИЛИ, второй информационный выхОд блока ассоциативной памяти соединен с вто- щ рым входом блока объединения списков и с третьим входом второго мульти,плексора, второй выход блока объе..динения списков подключен к четвертому входу второго мультиплексб-. ра, третий выход подключен к третье- Я му информационному входу блока ассоциативной памяти и к первому входу четвертого мультиплексора, третий вход блока объединения списков подключен к выходу счетчика адреса списе ка и к второму входу четвертого мультиплексора, выход второго мультиплексора соединен с числовым входом блока оперативной памяти, выход третьего мультиплексора соединен с информационным выходом устройства, выход четвертого мультиплексора соединен с адресным входом блока опера« тивной памяти, третий вход блока управления соединен с входом готовности устройства, четвертый вход соединен с управляющим выходом блока ассоциативной памяти, первый, второй и третий выходы блока управления соединены соответственно с входа ми управления записью, опросом и стиранием блока ассоциативной памяти, выходы с четвертого по двенадцатый блока управления соединены

1062721 соответственно с управляющими входами блока формирования команд, блока объединения списков, с вторым управляющим входом арифметико-логического блока, с управляющими входами четы рех мультиплексоров, счетчика адреса записи и счетчика адреса списка, тринадцатый выход блока управления соединен с выходом готовности устройства.

2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что блок форми» рования команд содержит узел памяти. команд, счетчик адреса команды, счетчик сдвигов и регистр команды, причем первый вход счетчика адреса команды соединен с первым входом блока, а второй вход - с вторым входом блока, выход счетчика адреса команды подключен к адресному входу узла памяти команд, счетный вход соединен с выходом переполнения счетчика сдвигов, вход разрешения приема кода соединен с управляющим входом блока, выход узла памяти команд .соединен с входом регистра команды, выход. старших разрядов которого соединен с вторым выходом блока, выход младших разрядов соединен с первым выходом блока, вход сдвига регистра команды соединен с счетным входом счетчика сдвигов и с управляющим входом блока.

3. Устройство по и. 1, о т л ич а ю щ е е С я тем, что блок объединения списков содержит первый и второй мультиплексоры и четыре реги; стра, причем первые входы первого и второго мультиплексоров соединены соответственно с первым и вторым входами, блока, вторые входы подключены к третьему входу блока, выход первого мультиплексора соединен с вхо» дом первого регистра, выход второго мультиплексора соединен с входом второго регистра, выход первого регистра соединен с входом третьего регистра и с третьим выходом блока, выход второго регистра соединен с входом четвертого регистра и с первым выходом блока, выход третьего регистра подключен к третьему входу первого мультиплексора, выход четвер того регистра подключеи к второму выходу блока, входы разрешения приема и выдачи кода третьего и четвертого регистров и управляющие входы мультиплексоров соединены с управляющим, входом блока.

4. Устройство по и. 1, о т л ич а ю щ е е с я тем, что блок управления содержит узел памяти микрокоманд, регистр адреса команды,дешифратор адреса, дешифратор тега,. первый и второй мульгиплексоры, причем входы первого мультиплексора соединены соответственно с первым, третьим, и четвертым входами блока и с выходами дешифратора тега, вход которого соединен с вторым входом блока и с входом старших разрядов ре.гистра адреса команды, выход первого мультиплексора подключен к управлякщему входу второго мультиплек сора, первый и второй входы которого соединены соответственно с первым и вторым выходами узла памяти микрокоманд, выход соединен с входом младших разрядов регистра адреса коман- ды, выход регистра адреса команды подключен к входу дешифратора адреса, выход которого подключен к адресному входу узла памяти микрокоманд, третий выход которого подключен к управляющему входу регистра адреса команды, четвертый выход узла памяти микрокоманд подключен к .Управляк щему входу первого мультиплексора выходы, начиная с пятого, подключены соответственно к выходам блока, начиная с первого выхода.

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

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

1062721

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

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

С использованием данного. устройства может быть осуществлен синтаксический анализ выполняемой програюы. В основе его работы лежит обычный алгоритм грамматического разбора с использованием стека операций, стека операндов и отношений предшествования между символами операций (1 3.

Однако в устройстве не предусмотрены средства перепрограммирования для выполнения различных схем перевода.

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

Данная система предназначена для трансляции алгебраических выражений языков программирования типа АЛГОЛа и ФОРТРАНа в объектные коды электронной вычислительной машины (ЭВМ).

Трансляция осуществляется с помощью двух стеков: стека уровней и стека невыполненных операций. При этом выражение разделяется на уровни в зависимости от вложенности скобок, а уровни делятся на подуровни в зависимости от старшинства операций, Таким образом, система выполняет лексический анализ: чтение символов выражения и распознавание лексических единиц, синтаксический анализразбор выражения с помощью стеков, и генерацию кода посредством усовершенствованного метода перевода выражений в инверснук польскую запись (2 3.

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

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

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

ИЛИ, второй выход блока формирования команд соединен с вторым входом блока управления и первым управляющим

З5 входом арифметико-логического блока, информационный вход которого соединен с выходом. блока элементов ИЛИ, информационный выход арифметико-логического блока соединен с вторым

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

5О блока объединения списков, первый информационный выход вЂ” соединен с первым входом блока объединения списков, с вторыми входами второго и третьего мультиплексоров, с вторым входом блока элементов ИЛИ, второй ,информационный выход блока ассоци ативной памяти соединен с вторым вхо- дом блока объединения списков и с третьим входом второго мультиплексора, второй выход блока объединения

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

65 мультиплексора, третий вход блока

1062721 объединения списков подключен к выходу счетчика адреса списка и к второму входу четвертого мультиплексора, выход второго мультиплексора соединен с числовым входом блока оперативной памяти, выход третьего мультиплексора со- 5 единен с информационным выходом устройства, выход четвертого мультиплексора соединен с адресным входом блока оперативной памяти, третий вход блока управления соединен с входом готовности устройства, четвертый вход соединен с управляющим выходом блока ассоциативной памяти, первый, второй н третий выходы блока управления соединены соответственно с входами .управления записью, опросом и стиранием блока ассоциативной памяти, выходы с четвертого по двенадцатый блока управления соединены соответственной с управляющими входами блока фор- 9 мирования команд, блока объединения списков, с вторым управляющим входом арифметико-логического блока, с управляющими входами четырех мультиплексоров, счетчика адреса записи и 25 счетчика, адреса списка, тринадцатый выход блока управления соединен с выходом готовности устройства.

Кроме того, блок формироваНИЯ команд содержит узел памяти команд, счетчик адреса команды, счетчик сдвиros и регистр команды, причем первый вход счетчика адреса команды соединен с первым входом блока, второй вход вЂ” с вторым входом блока, выход счетчика адреса команды подключен к адресному входу узла памяти команд, счетный вход соединен с выходом переполнения счетчика сдвигов, вход разрешения приема кода соеди нен с управляющим входом блока, вы- 4О ход узла памяти команд соединен с входом регистра команды, выход старших разрядов которого соединен с вторым выходом блока, выход младших разрядов соединен с первым вйходом 45. блока, вход сдвига регистра команды соединен с счетным входом счетчика сдвигов. и с управляющим входом- блока.

Причем блок объединения списков содержит первый и второй мультиплексоры и четыре регистра причем первые входы первого и второго мультиплексоров соединены соответственно с> первым и вторым входами блока, вторые55 входы подключены к третьему входу блока, выход первого мультиплексора соединен с входом первого регистра, выход второго мультиплексора соединен с вхбдом второго регистра, вы- 60 ход первого регистра соединен с входом третьего регистра и с третьим выходом блока, выход второго регистра соединен с входом четвертого регистра и с первым выходом блока, 65 выход третьего регистра подключен к

- третьему входу первого мультиплексора, выход четвертого регистра под» ключен к второму выходу блока, входы разрешения приема и выдачи кода третьего и.четвертого регистров и управляющие входы мультиплексоров соединены с управляющим входом блока.

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

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

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

1062721 стековой памяти соединен с информационным выходом блока, второй выход сумматора-вцчитателя соединен с управляющим выходом блока.

На фиг. 1 представлена структурная схема устройства; на фиг. 2то же, блок формирования команд; на фиг. 3 - то же, блок объединения списков; на фиг. 4 вЂ” то же, блок управления; на фиг. 5 вЂ” то же, арифметико-логического блока; на фиг. 6 форматы команд, выполняемых устрой» ством; на фиг..7 вЂ” блок -схема микропрограммы выполнения команды объединения списков (СПС ).

Устройство содержит блок 1 фор- 15 мнрования команд, арифметико-логический блок 2,. блок 3 ассоциативной памяти, блок 4 объединения списков, блок 5 оперативной памяти, блок 6 управления, счетчик 7 адреса записи, 2О счетчик 8 адреса списка, мультиплексоре 9-12, блок 13 элементов ИЛИ.

При этом устройство имеет адресный вход 14, информационный вход 15, вход 16 готовности, выход 17 FoToaности и информационный выход 18 устройства, адресный вход 19 и два выхода 20 и 21 блока формирования команд, входы 22-24 и выходы 25-27 блока объединения списков, управляющий вход 28, информационный вход

29, информационный 30 и управляющий 31 выходы арифметико-логического блока, входы 32 и 33 блока управления, выходы 34 и 45 блока управления, входы 46-48 блока ассоциативной памяти-, узел 49 памяти команд, регистр

50 команды; счетчик 51 адреса коман« ды, счетчик 52 сдвигов, мультиплексоры 53 и 54, регистры 55-58, узел

59 памяти микрокоманд,.дешифратор 40

60 тега, мультиплексоры 61 и 62, регистр 63 адреса команды, дешифратор 64 адреса, выходы 65-68 узза 59, узел 69 стековой памяти, сумматорвычнтатель 70, мультиплексор 71, 45 дешифратор, 72 кода операции, элементы И 73, ИЛИ 74 и НЕ 75.

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

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

Ниже рассматриваются схемы, ориенти 4 рованные на восходящий синтаксический анализ (так называемые S-атри» бутные схемы). При каждой редукции, выполняемой синтаксическим анализа- 65 тором, происходит вызов семантической подпрограммы, которая в данном случае задается набором правил перевода.

Переменные, входящие в правила перевода, называктся атрибутами перевода, Каждому нетерминалу входной грамматики, таким образом, соответствует набор атрибутов перевода. Правила перевода представляют собой операторы присваивания атрибутам новых зна чений, задаваемых константами или эыражениями„ условные операторы типа

if-fi или if-then-else и управляющие операторы. Все эти операторы легко представляются командами, приведенными на фнг. б. Атрибуты могут принимать строчные, числовые или логические значения. Таким образом, на адресный вход 14 устройства поступает адрес семантической подпрограмма, заданной посредством схемы перевода и записанной в виДе последователь- ности команд в блоке 1 . Имена атрибутов вместе с их значениями хранятся в блоке 3. Для атрибутов, имевщих строчное значение, в блоке 3 вместе с именами атрибутов хранятся ссылки на начало и конец списка, в виде которого в блоке 5 хранятся стро-. ки-переводы. Это делается для удобства при работе со строками при выполнении правил перевода. Список содержит лишь терминальную крону дерева (графа) перевода. Совокупность блока 3 и счетчика 7 образуют аппаратнув реализацию так называемой

ИП-таблицы (структуры данных ), сочетающей свойства стека и таблицыг за« пись производится только в головной элемент, а считывание возможно Hs первого элемента, начиная от головного, содержимое поля признака которо-. го совпало с признаком опроса. В качестве признаков выступают имена атрибутов. Числовые значения атрибутОв обрабатываются в блоке 2.

Рассмотрим выполнение каждой иэ команд, приведенных на фиг. б.

ПЕР вЂ” переход. По этсф команде осуществляется безусловная передача управления на указанный в команде адрес. Для этого код адреса с выхода

21 передается на вход 19.

СПС вЂ” объединение списков. По этой команде происходит сборка строки из строк-значений, заданных атрибутами, и строк-констант, записанных в самой команде. В результате дешифрации тега операнда в блоке б определяется его тип. Сперандом может быть имя атрибута или константа.

Ter указывает также тнп значения атрибута: строчное, числовое или логическое и последнкю запись в команде переменного формата (признак конца). Если операнд вЂ” имя атрибута, то оно передается на вход опроса бло1062721 ка 3, далее происходит поиск данного узла в блоке ассоциативной памяти, считывание соответствукшей ему информации и передача ее на входы 22 и 23 блока 4. Информация эта представляет собой ссылки (адреса) на начало и конец списка, содержащего строчное значение данного атрибута.

В блоке 4 адреса записываются на регистры 55 и 56. Далее производится считывание следующего операнда. Если операнд вЂ” имя атрибута, то повторяются описанные действия, адреса первого (предыдущего ) списка переписывактся на регистры 57 и 58 блока 4, далее производится объединение 15 списков, для чего адрес конца первого списка записывается в головной элемент второго списка. Для этого содержимое регистра 58 передается на вход мультиплексора 10, а содержимое регистра 55 вЂ” на вход мультиплексора

11. Адреса начала и конца результирукщего списка записаны в регистрах

55 и 56. Если операнд вЂ . строка вЂ” константа, то для нее формируется эле- 75 ментарный список, ссылки на начало и конец которого записывактся в регистры блока 4. При этом строка посимвольно передается из блока 1 на один из входов мультиплексора 10, а на адресный вход блока 5 через мультиплексор 11 подается содержимое счетчика 8, которое увеличивается на единицу при записи каждого нового слова в блок 5. Содержимое счетчика

8 до и после записи символа строки передается на вход 24 и записывается s регистры 55 и 56 блока 4 для дальнейшего объединения списков.

Если в команде встречается имя атрибута, имеющего нестрочное значение, 40 то оно преобразуется в строку, и для нее генерируется. элементарный список как для строки-константы. Если тег указывает, что имя атрибута появляется в правиле повторно, то в блок 5 45 записывается элементарный списокуказатель на начало и конец повто" ряемого участка результирующего списка. Для этого указанный в команде атрибут отыскивается в блоке 4, и, соответствующие ему ссылки запйсы-: вактся в блок 5 по адресу, задаваемому счетчиком 8. Содержимое счетчика 8 также заносится в регистры блока 4 для дальнейшего объединения списков. Ссылки на полученный в конце выполнения команды результирующий список записываются в блок 3 под именем атрибута, указанного в команде.

ЗГР вЂ” загрузка значения операнда в блок 2. Операндом может быть или имя атрибута, тогда загружается значение (числовое.)атрибута или целая константа. Если операнд вЂ” имя атрибу-65 та, то оно отыскивается в блоке 3, значение передается с входа 22 через элемент ИЛИ 13 на вход 29 блока 2, где заносится в узел 69. Если операнд вЂ” константа, то ее значение поступает в блок 2 из блока 1 (выход 21 ).

Арифметические и логические команды. Как показывает опыт построения схем перевода, минимальный набор арифметико-логических команд должен содержать операции сложения (СЛЖ ), вычитания(ВЧТ), конъккции (KOH), дизъюнкции (ДИЗj, инферсии (ИНВ ). Этот набор может быть расширен в целях повышения эффективности реализации схем перевода.. При выполнении этих команд с выхода 20 блока 1 на вход 28 блока 2 передается код операции. Результат выполнения операции остается в блоке 2.

СРВ вЂ” сравнение. При выполнении этой команды происходит сравнение двух операндов, хранящихся в узле

69 блока 2. Над операндами выполня" ется операция отношения, укаэанная в команде. Результатом этой команды может быть значение "Истина", если отношение выполняется, или "Ложь", если не выполняется. Результат также остается в узле 69.

УСЛ вЂ” условный переход. Если результат выполнения предыдущей команды вЂ” "Ложь" (сигнал на выходе 31), то выполняется переход по указанному адресу, если - "Истина", то выполняется следующая команда.

ЗПМ вЂ” запись результата выполнения операции из блока 2 в блок 3 под именем атрибута, укаэанного в команде. Для этого код с выхода 30 через мультиплексор 9 передается на информационный вход 47 блока 3.

ЗГС - загрузка значения атрибута извне. Для внешнего оборудования указывается адрес устройства и смещение. Адрес и смещение последовательно передаются на выход 18 через мультиплексор 12, а информация, принимаемая на вход 16, поступает затем в блок 3. Внешним источником информации может быть, например, таблица символов. Признаком готовности внешнего оборудования служит сигнал на входе 16.

TAB - запись информации в таблицу символов. На выход 18 сначала передается адрес элемента таблицы символов, хранимый под именем атрибута в блоке 3, затем смещение из блока 1, затем значение операндаатрибута или константы. Далее устройство переходит в режим ожидания сигнала готовности по входу 16. с

ПРА вЂ” присваиванке значения атрибута. Если операнд вЂ” константа, то она передается с выхода 21 блока 1

1062721

10 на вход блока 3, если вЂ” атрибут, то

его значение отыскивается в блоке 3, эаписывается на регистры 55 и 56 блока 4, а затем запоминается в блоке 3 под указанным именем атрибута.

CTP вЂ” стирание атрибутов, перечисленных в команде. Имена атрибутов последовательно подаются на вход опроса блока 3 синхронно с подачей сигналов с выхода 36. фИН вЂ” конец семантической подпро- 10 граммы. На выход 17 выдается сигнал готовности устройства.

На фиг. 7 приведена блок-схема микропрограммы выполнения, команды

СПС, где использованы мневмонические обозначения блоков. Верхний индекс обозначает номер блока, а нижнийвЂ” номер шины. Кроме пересылок указаны также шины, на которые подаются управляющие сигналы. Остальные микропрограммы, хранимые в блоке 6, существенно проще.

Так как команды имеют переменный формат, регистр 50 блока 1 является регистром сдвига.. Величина сдвига определяется сигналом по входу 37.

Для своевременной подкачки информации из узла 49 служит счетчик 52, подсчитывающий число раврядов сдвига.

Особенность работы арифметико-логического блока 2 заключается в том, что операции выполняются над содержимым двух верхних регистров узла

69. Код операции управляет выбором источника информации для записи в узел 69 с помощью мультиплексора 71. 35

Для управления сдвигом информации в узле 69 используется как управлякщий сигнал по входу 39, так и код операции с выхода дешифратора 72. Признак результата выполнения арифметических gg операций или результат выполнения логических операций или операции сравнения сохраняются также в сумматоре-вычитателе 70.

-Адрес на вход 14 может быть подан с аппаратного синтаксического анализатора или загружен из программа синтаксического анализа при вызове соответствующей семантической подпрограюв.

Результирующий перевод (или переводы) накапливается в блоке 5 в виде списка, ссылка на начало и конец которого хранится в блоке 3. В конце работы транслятора в блоке 3 должны остаться атрибуты, связанные с нетерминалом S-аксиомой грамматики входного языка.

Для примера приведем схему перевода оператора цикла АЛГОЛа в эквивалентную последовательность опера- 60 торов PL/1, не содержащую оператор цикла, а также программу в описанных команда .. о2 Е t Егз о2 1ог (Z >:= (v>=< E„); (H>:(V>=(U>i(E >; (S>

?Е<Ч><(Е )then goto cN>;

Ч-а (ч):=a

Предполагается, что атрибуты Е1, Е2, Е и 5 уже есть в ИП-таблице.

Программа

1! ЭГС адр. 1, 1, N .. (>=(E„);(N>;(V)=(V)+(E >;

СПС

C5)IF(V>«E )then goto(H>; )Z

СТР И, Е „, Е2, ЕЗ 5, 11

ФИН

2) ЗГС адр. 2, 1, V

ФИН

V означает повторное вхождение атрибута V в перевод (только для атрибутов, имеющих строчное значение), в угловых скоб <ах заключены имена атрибутов в тех случаях, когда их можно спутать со строчными константами.

Составление программы в описанных командах по схеме синтаксическиуправляемого перевода осуществляется вручную или с помощью электронных вычислительных машин (ЭВМ).

Таким образом, данное устройство позволяет решить задачу эффективной реализации схем синтаксически-управляемого перевода. устройство становится универсальным и церепрограммиpyemia, что черезвычайно важно при изменении входного или выходного языка.

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

По сравнению с программной реализацией семантических подпрограмм на ЭВИ с традиционной системой команд программы для предлагаемого устройства гораздо короче и быстрее выполняются Это достигается использованием команды объединения списков - основной команды перевода и введением аппаратных средств для ее ускорения: блока ассоциативной памяти и блока объединения списков, что позволит повысить быстродействие устройства не менее, чем в 10 раз.

1062721

1062723

1062721! / / б / г /

1062721

f AEP

2 ОС

Фг йнл атриб mu

Хоп Тег Опера ид Тк

597

ЮЮ ьа ииВ

Ю чу

5 Nlf

d ТИ Фп - Фю nm и а Внесение Ж Операнд

g HN

Ю t7P fjdrl ти ulrjf атрибута

)Ъа Уи а придута

1f Фин

7 ЯУ Ми pe успфюйстба Общение err атриума

106272)

0220/51

Подпи оное ирам

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

Устройство для синтаксически-управляемого перевода

Патент 1062721