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

 

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

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

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

РЕСПУБЛИН (sg 4 G 06 F 15/38

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

16

1Х

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

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

К АBTOPCHOMV СВИДЕТЕЛЬСТВУ,(21) 4168)65/24-24 (22) 29.12.86 (46) 30.05.88. Вюп. У 20 (» ) Ленинградский электротехнический институт им. В. И. Ульянова (Ленина) (72) В.С. Фомичев, Г.В. Разумовский и А.И. Познянский (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 1056210, кл. G 06 F 15/38, 1983 °

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

9 1196899, кл. G 06 F 15/38, 1985. (54) УСТРОИСТВО СИНТАКСИЧЕСКИ УПРАВЛЯЕМОГО ПЕРЕВОДА (57) Изобретение относится к вычислительной технике и предназначено для синтаксически управляемого перевода языков, описываемых LL(1)-грамматиками., .80 13997 7 А1

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

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

1, блок 3 постоянной памяти, счетчик

2 адреса, генератор 4 импульсов, блок

5 магнитной памяти, дополнительно введены дешифратор 7 символов, дешиф- д е ратор 8 конечного символа, блок 9 управления и выходной регистр 10.!

399767

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

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

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

l го управляющего автомата; на фиг. 3— микропрограмма; на фиг. 4 — временные диаграммы работы устройства.

Устройство синтаксически управля емого перевода содержит (фиг. 1) 25

". входной регистр 1, счетчик 2 адреса,,блок 3 постоянной памяти, генератор 4 ч импульсов, блок 5 магазинной памя,.ти, вход б "начальный символ", дешиф ратор 7 символов, дешифратор 8 конеч" 3р ного символа, блок 9 управления, выходной регистр 10, информационный вход 11 устройства, информационный

;выход 12 устройства, выход 13 "Готови

;ность обработки текущего символа выход 14 "Готовность символа выходной цепочки, выход 15 "Конец преобразования", выход 16 ."Ошибка" и выход

17 запуска устройства.

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

К=l. Простой синтаксически управляемый перевод, определяемый простой синтаксически управляемой схемой, входной грамматикой которой служит

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

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

Р -цепочка, заносимая в магазины (где — правая часть некоторого пра-., вила с внесенными в нее символами перевода);

"Выбро с";

"Допуск";

"Ошибка";

"Выдать".

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

Возможные такты работы магазинного преобразователя следующие: значением таблицы является цепочка /3 . Верхний символ магазина заменяется цепочкой f3 . Входная головка не сдвигается; значением таблицы является "Выброс". Верхний символ выбрасывается из магазина. Входная головка сдвигается на один символ вправо; значением таблицы является "Допуск". Работа прекращается и выходная цепочка называется переводом первоначальной входной цепочки;

9767

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

2 адреса увеличивает его значение на единицу.

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

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

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

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

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

С выхода регистра .! символ поступает на первый вход дешифратора 7 символов.

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

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

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

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

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

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

Каждая цепочка, записанная в блоке

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

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

5 13997

Блок 5 магазинной памяти выполняет функции магазина МП-преобразователя.

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

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

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

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

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

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

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

В начальный момент магазин является пустым. С входа 6 устройства в вершину магазина поступает начальный символ грамматики. Устройство запускается подачей импульса на вход l7.

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

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

1 поступает код следующего символа цепочки. Затем повторяется опрос

ocBедомительных сигналов комбинационной схемы.

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

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

f (ó, у,у,у,у,) v (ц,ц,ц,ц,Ц,) у (u,у,у, ц,ц,) v (g, у у у ) 7 399

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

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

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

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

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

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

35 языка. Значение этих функций зависит от символов входной цепочки и магазина. Поскольку каждому символу соответствует код, разряды этого кода можно рассматривать как значения булевых переменных, от которых зависят указанные функции. Построение осуществляется по управляющей таблице для данной LL(1)-грамматики. В управляющей таблице имеется пять видов клеток, для клетки "Ошибка" дешифратор 7 сим-Остальные конъюнкции совпадают с приведенными. Сигнал "Выброс" равен единице в случае, если выбрана клетка управляющей таблицы со значением

"Выброс". Значение клетки "Выброс" управляющей таблицы зависит от теку

767

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

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

Построение системы функций для дешифратора 7 символов рассмотрим на основе построения функций- для управляющей таблицы, представленной в табл. !.

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

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

"Выдать" будет формироваться только по значениям второй группы входов комбинационной схемы. Обозначим переменные, которые соответствуют этим входам, через Р . Тогда этот сигнал можно представить как функцию f, в виде дизъюнктивной нормальной формы .(ДНФ):

=(I Л, z, ! где каждое Z; (i = 1,..., n,;

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

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

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

Каждая элементарная конъюнкция, ! (( состоящая из Z;, Z; ... Z; соответствует одной клетке "Вьщать" управляющей таблицы и принимает значение единица" на наборе значений переменных, кОторые соответствуют коду магазинного символа для этой клетки.

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

1399767

=(у у у у у х х х х х )Ч (Y,у у у у х1x .xwx5) Ч (У у<У У У х х х х4х

f — У, У У у у х1х х х х .

4 (У1 У2УЗУ4У%Х, Х Х Х 1Х ) Ч (Y Y у У1 У Х1Х Х х х ) М (Y1 У У У+У Х1Х Х Х Х ) группе входов через х. Тогда этот сигнал можно представить как функцию

Г, в виде ДНФ:

1! где каждое Е; (1 п3 ) — переменная (х) или от рицание переменной (х);

A " "количество разрядов в коде Z символа входной це почки, m - количество клеток "Выброс" управляющей таблицы.

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

Этот сигнал будет формироваться по значениям первой и второй групп вхо" дон комбинационной схемы и его можно представить как функцию f> в виде

ДНФ:

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

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

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

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

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

Каждая элементарная конъюнкция со стоящая из Z. Z 2 Z 1 Z ., Z а а соответствует одной клетке "Выброс" управляющей таблиць1 и принимает знаtl 11 чение единица на наборе значений переменных, которые соответствуют паре кодов символов цепочки и магазина для данной клетки.

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

"Выброс" соответствует f Фида

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

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

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

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

1 1 цепочки, заносимой в магазин, причем это непустая цепочка. Этот сигнал будет формироваться по значениям перll 13997 вой и второй групп входов комбинационной схемь< и его можно представить как функцию в виде ДНФ: где и " количество клеток управляют щей таблицы с непустъ<ми цепочками. 10

Элементарная конъюнкция, состоя(у, у у у4У х х х х х ) V (у у у у у х х х х х ) ч (у у у у у х,х х х,х,)

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

9 (у<ó ó y4ó õ

25 д, 30

9 = (y

4 (y< уiy»у у х. х,х x4x )y (у у узу4у х

9 (y< У У У4У Х<х х,х4х )y

5. (y< y yъУ4У,Х< Х Х Х4Х% }Ч (y

И 24, мультиплексор 25, с первого по десятый выходы 26 автомата, с первого по шестой входы 27 автомата, вход 28

9 — (у< у,у<у4у х, х х4Х4Х ) Ч

55 (y y)y У4У Х< Х Х<Х4Х ) Ч (y, y y y4y x,x x x4x ); где ot . (i I,° .° .° ., n<1 3 1, ° ° ° K) элементарная конъюнкция из или отрицание такой конъюнкции.

Количество о для каждой функции

9 равно количеству клеток с непусты" ми цепочками. Каждая элементарная конъюнкция из fi- прямо входит в 9>

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

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

Система функций, которая задает эти адреса имеет вид:

67

12 ответствует одной клетке управляющей таблицы, значением которой является пустая цепочка, заносимая B магазин, причем эта элементарная конъюнкция принимает значение "единица" на наборе значений переменных, которые соответствуют паре кодов символов для данной клетки. Например, для приведенной управляющей таблицы (см.табл.1) клеткам с непустыми цепочками соответствует f нида

13

13997 запуска автомата и вход 29 тактовых импульсов автомата. . Выходом ПЗУ 18 является регистр 19 микрокоманд. В соответствии со струк5 турой микрокоманды соединены выходы регистра 19 микрокоманд; разряды Y соединены с. соответствующими выходами 26 автомата, разряды Х вЂ” с входом дешифратора. 20, разряды Ау| и А1, управляемые через мультиплексор 25 со— ответственно элементами И-ИЛИ 21 и

НЕ 23,с адресным входом-ПЗУ 18. Выхо ды дешифратора 20 и входы 27 автомата соединены с входами элемента И-HJIH

21. Один разряд из поля Y регистра 19 соединен с К-входом триггера 22, на

,l âõîä которого поступает сигнал за,пуска. прямой выход триггера 22 сое динен с первым входом элемента И 24.

11а второй вход элемента И 24 поступа1от тактовые импульсы. Выход элемента

24 соединен с входом чтения ПЗУ 18.

Микропрограммный управляющий авто- 25 ат работает следующим образом.

В исходном состоянии регистр 19

Йикрлкоманд и триггер 22 находятся в фулевом состоянии, в результате чего устанавливается нулевой адрес ПЗУ. З0 мпульс запуска с входа 28 переключа-т триггер 22 в единичное состояние, результате чего тактовые импульсы роходят на вход чтения ПЗУ 18, возуждая в кажцом такте чтения микрокоманды из ПЗУ 18. Выбранная из ПЗУ

1.8 микрокоманда поступает на регистр

19 микрокоманд и обрабатывается след ющим образом. Поле Y образует управ". л ющие сигналы. Адрес следующей микро-4п к манды определяется полями А9 и Al в зависимости от значения поля Х и логических условий, поступающих по группе входов 27. Если выбранное дешнфратором 20 условие равно 9 или в 45 п<)ле Х указывается условие, тождест.в| нно равное g (микрокоманда беэ про" вЕрки логического условия), то выбирается по входу элемента НЕ 23 адрес

Al, а если указанное в команде усло- 50 вие равно 1, то по выходу элемента

И-ИЛИ 21 выбирается адрес А9 в качест не адреса слецующей микрокоманды. Pa" бота микропрограммного управляющего автомата заканчивается, если указыва" ется специальная микрокоманда останова. Эта микрокоманда имеет единицу в первом разряде регистра 19 и нули в остальных разрядах. По этой микрокоманде из первого разряда регистра

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

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

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

\/„. - объем ПЗУ (блока 3);

R — разрядность слова ПЗУ (блопуу ка 3);

Ч вЂ” объем магазина (блока 5);

R -R — разрядность слова магазипъу на (блока 5); ! — разрядность входного рет гистра (блока 1); — разрядность регистра адре" т са ПЗУ (блока 3) °

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

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

Выдать"

"Выдать"

"Выдать"

"Выдать"

"Выда ть"

"Выдать"

"Выдать"

"Выдать"

10110

01 l I0

"Выдать"

"Выдать"

lll00

"Выдать"

"Выдать"

"Выдать"

"Выдать"

"Выдать"

"Выдать"

01011

"Цепочка Ч"

00011

"Ошибка"

"Выброс". Выброс"

00111 пЦепочка

"Ошибка"

00101 Выброс"

".Ошибка"

"Цепочка 0"

"Ошибка"

"Ошибка"

"Допуск"

"Ошибка"

00000

Дно

П р и м е ч а н и е. Адреса цепочек таблицы в блоке 3 следующие: для

V - адрес О!011; для Ч адрес 11011; для U — адрес 10111.

15 1399

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

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

Устройство синтаксически управляемого перевода, содержащее входной регистр, счетчик адреса, блок постоян- 10 ной памяти, генератор импульсов и блок магазинной памяти, причем информационный вход входного регистра является информационным входом устрой— ства, выход счетчика адреса соединен 15 с адресным входом блока постоянной памяти, выход которого подключен к первому информационному входу блока магазинной памяти, второй информационный вход которого является входом 20 начального символа устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства sa счет расширения класса выполняемых переводов, в него 25 введены дешифратор символов, дешифратор конечного символа, блок управле" ния и выходной регистр, причем выход генератора импульсов подключен к первому входу блока управления, второй 30 вход которого является входом запуска устройства, с первого по четвертый выходы блока управления являются вы767 16 ходами ошибки конца преобраэов ния, готовности символа выходной цепочки и готовности обработки текущего символа устройства соответственно, четвертый выход блока управления подключен к входу синхронизации входного регистра, выход которого подключен к первому входу дешифратора символов, второй вход которого соединен с выходом блока магазинной памяти, первый и второй выходы дешифратора символов подключены к третьему входу блока управления и информационном входу счетчика адреса cooTBpтственно, пятый и шестой выходы блока управления сое.динены с входом записи и счетным входом счетчика адреса соответственно, выход блока постоянной памяти подключен к входу дешифратора конечного символа, выход которого соединен с четвертым входом блока управления, седьмой, восьмой и девятый выходы которого соединены с входом начальной установки, входом записи и входом считывания блока магазинной памяти соответственно, десятый выход блока управления и выход блока магазинной памяти подключены к входу синхронизации и информационному входу выходного регистра соответственно, выход которого является информационным выходом устройства. ! Таблица l

1399767

Таблица2 тип Слово

Пояснение

Р, Вх(1:0,)

ЧТВх

P„A ПЗУ(1:Q,)

1 КС(1:Q, +5) г

ВЫБ=КС (1)

ВЫД=КС (2)

НПП=КС (3) ПП=КС (4) ДОП=КС (5) АПЗУ(1:Q )

=КС (6: Q" +5) О КОН

О ОШ

ПЗУ (1: У„,, ) (1: Й„,„)

ER и fg:v„J(i: в„)

RUSH

Р0Р

1. УСТ

О Р„В,„„(1: Ri4)

О СЛЕД

О ГОТ

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

Поле

Входной регистр (блок 1)

Разрешение записи входного регистра

Регистр адреса ПЗУ (блок 2)

Выходы комбинационной схемы (блок 7)

Выход "Выброс" блока 7

Выход "Выдать" блока 7

Выход "Непустое правило" блока 7

Выход "Пустое правило" блока 7

Выход "Допуск" блока 7

Выходы комбинационной схемы для адреса цепочки из ПЗУ (блок 3) Выход дешифратора (блок 8)

Магазинная память (блок 5) Второй управляющий вход магазина

Третий управляющий вход магазина

Первый управляющий вход магазина

Выходной регистр (блок 1О) Выход 1 3 "Готовность обработки текущего символа" устройства

Выход 14 "Готовность символа выходной цепочки" устройства

Выход 15 "Конец преобразования" устройства

Выход 16 "Ошибка" устройства

) 399767

28

2У

1399767

Лак

Вход 17 июаю дол

Вход б пе 5т Ьоон.ан. дощЫ m итй чтбе nmui постднцо

Вход 11

Восход О диод /2

Ьход f4

Выход Ю

Й!код Ф пе ЬоЬябив тн5сл &о од последнии конем еоброзоюания

Составитель И. Поливода

Редактор А. Лежнина Техред А.Кравчук Корректор А. Тяско

Заказ 2668/50 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий. 133035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4