Устройство синтаксически управляемого перевода Советский патент 1988 года по МПК G06F17/27 

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

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

; На фиг. 1 представлена функцио- Iнальная схема устройства синтаксичес- Iки управляемого перевода; на фиг.2 - функциональная схема микропрограммноI го управляющего автомата на фиг. 3 - микропрограмма; на фиг. 4 - временные диаграммы работы устройства. I Устройство синтаксически управля- Iемого перевода содержит (фиг. 1 входной регистр 1, счетчик 2 адреса, I блок 3 постоянной памяти, генератор 4 |4 импульсов, блок 5 магазинной памя- |ти, вход 6 начальный символ, дешиф- ;ратор 7 символов, дешифратор 8 конечного символа, блок 9 управления, вы- Ходной регистр 10, информационный |вход П устройства, информационный выход 12 устройства, выход 13 Готовность обра,ботки текущего символа, выход 14 Готовность символа выход- 1ной цепочки, выход 15 Конец преобра- :зования % выход 16 Ошибка и выход 17 запуска устройства.

При помощи предлагаемого устрой- ства можно.осуществлять любой прос- той синтаксически управляемый перевод, определяемый синтаксически управляемой схемой, входной грамматикой которой служит любая LLП)граммати- ка. В основе алгоритма работы устройства положен 1-предсказывающий алгоритм разбора для LL(К)-грамматик при . Простой синтаксически управляемый перевод, определяемый простой синтаксически управляемой схемой, входной грамматикой которой служит 11(К)-грамматика, можно осуществить детерминированным магазинным преобразователем. Существует способ построения по простой синтаксически управляемой схеме магазинного преобразователя, задающего такой же перевод. Предлагаемое .устройство является детерми

O

s

0 5 0 г

Q j

0

нированным магазинным преобразователем, осуществляющим простой синтаксически управляемый перевод для LL(l)- грамматик. Известен алгоритм построения управляющей таблицы для LL(1)- грамматик 1-предсказывающего алгоритма разбора. Клетки управляющей таблицы магазинного преобразователя в отличие от соответствующего магазинного распознавателя не содержат номеров правил. Клетки управляющей таблицы, соответствующие появлению в вершине магазина магазинного преобразователя символов выходного алфавита, должны содержать признак Выдать. В случае если во время работы магазинного преобразователя значением управляющей таблицы будет признак Вьщать, символ выходного алфавита из вершины магазина вытолкнется и передастся на выходную ленту, входная головка при этом не сместится.

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

Выброс ;

Допуск ;

Ошибка ;

Вьщать.

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

Возможные такты работы магазинного преобразователя следующие:

значением таблицы является цепочка 0 . Верхний символ магазина заменяется цепочкой и . Входная головка не сдвигается;

значением таблицы является Выброс. Верхний символ выбрасывается из магазина. Входная головка сдвигается на один символ вправо;

значением таблицы является Допуск. Работа прекращается и выходная цепочка называется переводом первоначальной входной цепочки;

значением таблицы является Ошибка, Работа прекращается и выдается сообщение об ошибке;

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

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

Изобретение относится к вычисли тельной технике и предназначено для синтаксически управляемого перевода языков, описываемых LL( 1 )-грамматиками Устройство может быть использовано в специализированных процессорах, трансляторах и программно-аппаратных системах, осуществляющих перевод с языков программирования высокого.уровня на машинньй язык, а также в интерпретаторах языков высокого уровня. Цель изобретения - расширение функциональных возможностей за счет расширения классов выполняемых переводов. Для достижения указанной цели в устройство, содержащее входной регистр 1, блок 3 постоянной памяти, счетчик 2 адреса, генератор 4 импульсов, блок 5 магнитной, памяти, дополнительно введены дешифратор 7 символов, дешифратор 8 конечного символа, блок 9 управления и выходной регистр 10. 4 ил., 2 табл. W 00 со со 05 -4j /./

ка магазинного преобразователя распо- ю вует значение Допуск, и нулю в проложена на первом символе входной це тивном случае. Сигнал Непустое пра

почки, а в вершине магазина находитс начальный символ грамматики.

Алгоритм работы предлагаемого устройства во всем подобен описанному алгоритму.

Входной регистр 1 предназначен дл приема символов входной цепочки. С информационного входа 11 устройства на информационный вход регистра 1 поступает очередной символ входной цепочки. Этот символ запоминается в регистре 1 в случае, если на вход разрешения записи регистра 1 будет подан импульс, в противном случае информация в регистре 1 не меняется. С выхода регистра 1 символ поступает на первый вход дешифратора 7 симао- лов.

Счетчик 2 адреса предназначен для хранения адреса цепочки, заносимой в магазин, которая хранится в блоке 3 постоянной памяти. Адрес цепочки

Блок 3 постоянной памяти содержит непустые цепочки, заносимые в магазин. Кгшдьй символ этой цепочки хра3 по.поступает с первой группы выходов

комбинационной схемы через информаци- 35 отдельной ячейке блока онный вход счетчика 2 адреса. Этот стоянной памяти. Ячейки блока 3 по- адрес запоминается в счетчике 2 адре- стоянной памяти, содержащие символы са в случае подачи импульса на вход цепочки, имеют последователь- разрешения записей счетчика 2 адреса, ЗДреса, причем последнему симво- в противном случае информация в счет- 40 У Цепочки соответствует ячейка с чике 2 адреса не меняется. Подача им- младшим адресом, а первому символу

цепочки - ячейка со старшим адресом. Каждая цепочка, записанная в блоке 3 постоянной памяти, ограничивается специальным маркером, который может иметь любой код, отличный от кодов символов цепочек. Этот маркер записан в ячейке, адрес которой на единицу больше адреса ячейки с первым симвходной цепочки,из вершины магазина.На 50 ° ° Адрес символа цепочки первую группу входов комбинационной схе- поступает с информационного выхода мы поступает код входного символа, а

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

Блок 3 постоянной памяти и дешифратор 7 символов служат для непосредственной выработки значений управляющей таблицей. Это значение должно формироваться по паре символов -символ

45

счетчика 2 адреса на адресный вход блока 3 постоянной памяти. В том случае на информационном выходе блока 3 постоянной памяти появляется код выбранного символа, f

на вторую группу входов - код символа из вершины магазина. Дешифратор 7 символов для каждой такой пары вырабатывает пять осведомительных сигналов, которые поступают на вторую группу выходов. Сигнал Выброс равен единице, если в управляющей таб

вило равен единице в случае, если в заправляющей таблице данной паре соответствует цепочка, которая не явля- ется пустой цепочкой, и нулю в противном случае. Сигнал Пустое правило равен единице в случае, если в управляющей таблице данной паре соответствует цепочка, которая является пустой цепочкой, и нулю в противном случае.

Если сигнал Непустое правило равен единице, то одновременно на первой группе выходов комбинационной

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

постоянной памяти, в которых хранится данная цепочка.

Блок 3 постоянной памяти содержит непустые цепочки, заносимые в магазин. Кгшдьй символ этой цепочки хра3 отдельной ячейке блока стоянной памяти. Ячейки блока 3 по- стоянной памяти, содержащие символы цепочки, имеют последователь- ЗДреса, причем последнему симво- У Цепочки соответствует ячейка с младшим адресом, а первому символу

45

50 ° ° Адрес символа цепочки поступает с информационного выхода

55

счетчика 2 адреса на адресный вход блока 3 постоянной памяти. В том случае на информационном выходе блока 3 постоянной памяти появляется код выбранного символа, f

Генератор 4 импульсов вырабатывает

тактовые импульсы для блока 9 управления .

Клук 5 магазинной памяти выполняет функции магазина МП-преобразователя,. Он имеет второй информационный вход, через который поступают заталкиваемые в магазин символы в случае пэдачи импульса на второй управляющий вход блока 3 постоянной памяти. На информационный выход блока 5 магазинной памяти постоянно выдается код симвора,, находящегося в вершине магазина. В случае выталкивания из магазина, т.е подачи импульса на третий управляющий вход блока 5 магазинной памяти, верхним, становится символ, находяпшйся непосредственно под вершиной. Началь- ;пая установка магазина осуществляется подачей импульса на первый управляющий вход блока 5 магазинной памяти, при этом ячейки магазинной памяти обнуляются и магазин становится пустым В случае подачи на первый информаци- онньш вход блока 5 магазинной памяти кода начального символа грамматики (код должен быть отличен от нулевого кода) , этот код записывается в шину магазина.

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

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

Выходной регистр 10 служит для хранения текущего символа выходной цепочки .

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

В начальный момент магазин является пустым, С входа 6 устройства в вершину магазина цоступает начальный символ грамматики. Устройство запускается подачей импульса на вход 7. По этому импульсу запускается блок 9 управления, который посылает импульс на вход разрешения записи входного регистра 1, и с входа 1 1 устройства поступает первый символ входной цепочки. Коды символа входной цепочки и символа из вершины поступают на входы дешифратора 7 символов, на второй группе выходов которого вырабатываются осведомительные сигналы. Эти сиг- последовательно анализируются управляющим автоматом. В случае если сигнал Выдать равен единице, код верхнего символа магазина передается в выходной регистр подачей импульса на вход разращения записи выходного регистра. На выходе 14 устройства появляется сигнал, свидетельствующий о готовности символа выходной цепочки на выходном регистре. Затем производится выталкивание из магазина подачей импульса на третий управляющий

вход блока 5 магазинной памяти. После этого повторяется опрос осведомительных сигналов комбинационной схемы.

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

выход 13 устройства, при этом с входа 11 устройства во входной регистр 1 поступает код следующего символа цепочки. Затем повторяется опрос осведомительных сигналов комбинационной схемы.

В случае если сигнал Непустое правило равен единице, адрес цепочки с первой группы выходов комбинационной схемы поступает в счетчик 2 адреса. Из блока 3 постоянной памяти производится чтение. В случае если прочитанный символ не является .маркером конца цепочки, заносимой в магаЗИН (это определяется опросом выхода дешифратора 8 конечного символа), символ заталкивается в вершину магазина путем подачи импульса на второй управляющий вход блока 5 магазинной

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

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

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

Сигнал Выдать равен единице в

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

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

импульс, осуществляющий начальную i. j i j

установку блока 5 магазинной памяти, зо где каждое Z;: (i 1 , . . . , п,; j

4 J/ ,

ПО значениям второй группы входов комбинационной схемы. Обозначим переменные, которые соответствуют этим входам, через . Тогда этот сигнал 25 можно представить как функцию f в

виде дизъюнктивной нормальной формы (ДНФ):

-v:. л;. z;:

На этом работа устройства заканчивается .

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

1 , . . . , FTij) - переменная ( 1 ) или отрицание переменной (у);

т - количество разрядов в коде магазинного символа;

п, - количество клеток Выдать управляющей таблицы.

Каждая элементарная конъюнкция.

состоящая из Z;, Z|

tz

Zmi

соответствует одной клетке Выдать упуказанные функции. Построение осуществляется по управляющей таблице для данной LL(1)-грамматики. В управляюможно рассматривать как значения бу- Q равляющей таблицы и принимает значелевых переменных, от которых зависят

ременных, которые соответствуют коду магазинного символа для этой клетки. Например, для приведенной управляющей таблицы (см. табл. l) клетка Вы

щей таблице имеется пять видов клеток,,

для клетки Ошибка дешифратор 7 сим- дать соответствует f, вида

,(у.УгУ,У4Уу) V (ц,,) V (t., ti4tiJ V (t,n

Остальные конъюнкции совпадают с приведенными. Сигнал Выброс равен единице в случае, если выбрана клетка, управляющей таблицы со значением Выброс. Значение клетки Выброс управляющей таблицы зависит от теку

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

На второй группе выходов дешифраторов 7 сиьшолов формируются пять видов сигналов.

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

i. j i j

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

виде дизъюнктивной нормальной формы (ДНФ):

-v:. л;. z;:

о где каждое Z;: (i 1 , . . . , п,; j

4 J/ ,

1 , . . . , FTij) - переменная ( 1 ) или отрицание переменной (у);

т - количество разрядов в коде магазинного символа;

п, - количество клеток Выдать управляющей таблицы.

Каждая элементарная конъюнкция.

состоящая из Z;, Z|

tz

Zmi

соответствует одной клетке Выдать уп55

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

91399767

входов через х. Тогда этот можно представить как функцию

g у ч п п н

fn в виде ДНО:

Л 7 Ml ( tTI-j М

fa V;., /Aj., Z;. Aj, Zij),

где каждое Z;j (1 1 , , j 1,..., m) - переменная (x) или отрицание переменной (x);

n - количество разрядов в коде символа входной цепочки;

т.

- количество кпеток Выброс

управляющей таблицы.

fj Y-УгУ,У4У5-.) V (У, ) V (у, УгУ,,х,х.,х,Х4Х5,) .

Сигнал Допуск равен е; инице в :случае, если выбрана клетка управляю

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

дов комбинационной схемы и его можно

представить как функцию f в виде

ДНФ:

z;

z z z

I- , , .

Элементарная конъюнкция, состоящая 4 II

Zm соответ71т|-

ИЗ z, Zj .„ . Z Z, Z,

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

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

4 (У У1УэУ.УИ.) V (У,,У, УуХ,,Х4Ху) V (у, УвУэУ УуХ.).

I.„ I

Сигнал Непустое правило равен цепочки, заносимой в магазин, причем

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

Каждая элементарная конъюнкция со- стоящая из Zl Zl Zi Z- z:- ... Z.:, соответствует одной клетке Выброс управляющей таблицы и принимает значение единица на наборе значений переменных, которые соответствуют паре кодов символов цепочки и магазина для данной клетки.

Например, для приведенной управляющей таблицы (см. табл. 1) клеткам Выброс соответствует f, йида

Пусть, например, код символа конца входной цепочки имеет вид 11111, тог- 20 да fj примет вид

f, 7, УгУ,

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

тг

f.. V; - (С .A

,.

где n - количество клеток управляющей таблицы с пустыми цепочками.

Элементарная конъюнкция, состоящая из Z;VZ ; ...Zj Z ...Z; ,, соответствует одной клетке управляющей таблицы, значением которой является пустая цепочка, заносимая в магазин, причем эта элементарная конъюнкция принимает значение единица на набо- ре значений переменных, которые соот ветствуют паре кодов символов для анной клетки.

Например, для приведенной управля- ющей таблицы (см, табл. 1) клеткам с пустыми цепочками соответствует f вида

1399767

вой и второй групп входов комбинаци- ответствует одной клетке управляющей

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

данной клетки. Например, для приве10 денной управлякяцей таблицы (см.табл.1)

клеткам с непустыми цепочками соотонной схемы и его можно представить как функцию f в виде ДНФ:

.

щей таблицы с непустыми цепочками.

Элементарная конъюнкция, состоящая из Z;, Z| . . ., Z j.j . . .Z, со- ветствует fy вида

у У ,У1У,У4У-гХ,1Г.,х,х,7,) V { Y,y.,y,,l,,,) V (у, .) .

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

,; )

Qi - , i

vr:,«ir,

где el. (i 1,..., j 1,...,K) элементарная конъюнкция из fj. или отрицание такой ко1|ъюнкции.

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

Например, дпя приведенной управляющей таблицы (табл. l) непустым цепочкам клеток таблицы соответствуют указанные в табл. 1 адреса блока 3. Система функций, которая задает эти адреса имеет вид:

9, 1У, У1У ,У4У5 .)

(7, ,y4yyX,x,x,)V

. (у, Yjy,y«yjX,,x,Xy);

91 (У.У2У,У4У5Х.ХгХ)4Х5)

(у.Ут.. ,)v

(У«У2У У4У5 «г.,4Х5). 9, (у, У2У,У 4У5: « 5 4)

(у, ,,)

(у, У1У 74У5 1 3 4 5)

9 (,У4Уг.гХ5Х,х,)у

(у. УгУ 1У4У5 г з 4 у)У (.УяУ,,4Х5);

9j (У,У:.У ,У4Уу5с,,)У (у; УаУ,У4УуХ,Х2Х,)

(У.гУ,)

Блок 9 управления может быть реализован в виде микропрограммного автомата с использованием постоянного запоминающего устройства (ПЗУ). В нем используются принудительная адресация и два адресных поля. Каждая микрокоманда имеет операционное пое Y, поле логических условий X и два адресных поля А0 и А1. Микропрограммный управляющий автомат,содержит ПЗУ J8, регистр 19 микрокоманд, .

дешифратор 20, элемент И-ИЛИ 21, IК- триггер 22, элемент НЕ 23, элемент И 24, мультиплексор 25, с первого по десятый выходы 26 автомата, с первого по шестой входы 27 автомата, вход 28

запуска автомата и вход 29 тактовых импульсов автомата.

Выходом ПЗУ 18 является регистр 19 микрокоманд. В соответствии со структурой микрокоманды соединены выходы регистра 19 микрокоманд; разряды Y соединены с соответствующими выходами 26 автомата, разряды X - с входом дешифратора 20, разряды А0 и А1, уп- равляемые через мультиплексор 25 соответственно элементами И-ИЛИ 21 и НЕ 23,с адресным входом-ПЗУ 18. Выходы дешифратора 20 и входы 27 автомата ;соединены с входами элемента И-ИЛИ :21. Один разряд из поля Y регистра 19 |соединен с К-входом триггера 22, на II-вход которого поступает сигнал за- Ьуска, прямой выход триггера 22 сое- ринен с первым входом элемента И 24. 1а второй вход элемента И 2U поступа от тактовые импульсы. Выход элемента i 24 соединен с входом чтения ПЗУ 18

Микропрограммный управляющий автопат работает следующим образом. I В исходном состоянии регистр 19 Микрокоманд и триггер 22 находятся в рулевом состоянии, в результате чего 5 cтaнaвливaeтcя нулевой адрес ПЗУ. Импульс запуска с входа 28 переключа- €Т триггер 22 в единичное состояние, в результате чего тактовые импульсы проходят на вход чтения ПЗУ 18, воз- буждая в каждом такте чтения микро- команды из ПЗУ 18. Выбранная из ПЗУ & микрокоманда поступает на регистр Ш микрокоманд и обрабатывается следующим образом. Поле Y образует управ ллющие сигналы. Адрес следующей микро команды определяется полями А0 и А1 в;зависимости от значения поля X и л Ьгических з словнй, поступающих по г|)уппе входов 27. Если выбранное-дешифратором 20 условие равно 0 или в пфле X указывается условие, тождест- вйнно равное 0 (микрокоманда без проверки логического условия), то выби- р4ется по входу элемента НЕ 23 адрес А1, а если указанное в команде уело- вйе равно 1, то по выходу элемента 21 выбирается адрес А0 в качест вб адреса следующей микрокоманды, Рабата микропрограммного управляющего автомата заканчивается, если указьгоа- етЬя специальная микрокоманда останова:. Эта микрокоманда имеет единицу в первом разряде регистра 19 и нули в остальных разрядах. По этой микро

команде из первого разряда регистра 19 поступает сигнал на вход К триггера 22, переводящий его в нулевое состояние и тем самь1м запрещающий проход тактовых импульсов через элемент И 24.

Если в качестве блока 9 управления выбрать микропрограммный управляемый автомат, работа устройства будет определяться микропрограммой для этого автомата. При описании микропрограммы используют язык функционального микропрограммирования (- язык), который является средством описания функций операционных устройств на уровне микропрограммы безотносительно к структуре (аппаратуре), которая может быть использована для реализации этих функций. Функциональная микропрограмма содержит в себе два ряда сведений, две части:

описание слов и массивов, устанавливающее типы и форматы слов, с которыми оперирует микрокоманда;

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

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

- объем ПЗУ (блока 3) ;,

- разрядность слова ПЗУ (блока З) ;

V - объем магазина (блока 5); ,, - разрядность слова магазина (блока 5);

Q - разрядность входного регистра (блока J);

Q - разрядность регистра адреса ПЗУ (блока 3).

Множество слов и массивов, с которыми оперирует микропрограмма, описывается в виде табл. 2.

. Предполагается, что запуск микропрограммного автомата 9, начальная установка магазина (блок 5) и установки начального символа грамматики (блок 5) осуществляются до начала работы микропрограммы подачей импульса на вход 17 и кода на вход 6, поэтому в микропрограмме не отражаются,

Содержательный граф микропрограммы, соот)йетствующий алгоритму работы устройства, изображен на фиг. 3.

Временная диаграмма работы упрой- ства во время преобразования допустимой цепочки показана на фиг. 4.

Формула изобретения

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

V - адрес ОЮ11; для W адрес 11011; для U - адрес 10111.

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

Описание слов и массивов

Таблица 2

( Коней

Фиг.З

Запуск

п

Вход 17.

нач.сип6ол

RtaUB I I

первый 8xobn.tuM. Bmopni третий уетбертый ГII II

Выход 13.

выход/2П

П

П

П

перВый быховной синбоп ffmopoO последний

П

BuxoSfu

п

Выход fSВ ыход16П

П

П

пп

лреобразоУения

П

ФигЛ