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

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

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

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

На фиг.1 представлена функциональная схема устройства; на фиг.2 - структура таблицы опознания; на фиг. 3 - структура пакета процедуры опознанияj на фиг. 4 - функциональная схема блока управления; на фиг/5- 7 - микропрограмма работы устройства; на фиг.8 - схема блока магазинкой памяти; на фиг.9 - временная диаграмма работы устройства.

Устройство (фиг.1) содержит входной регистр 1, вычислитель 2, генерао

СП

ISD

Ј 00

тор 3 импульсов, блок 4 управления, счетчик 5 адреса, блок 6 постоянной памяти, блок 7 магазинной памяти, выходной регистр 8, регистр 9 символа, формирователь 10 кода, информационный вход II устройства, информационный выход 12 устройства, вход 13 запуска устройства, выход 14 устройст- ва Готовность обработки текущего сим зола, выход 15 устройства Готов- о ность символа выходной цепочки, выход 16 устройства Конец преобразования, выход 17 устройства Ошибка, первьй 18 и второй 19 мультиплексоры соответственно, счетчик 20 глубины погружения, счетчик 21 символов, регистр 22 адреса, схему 23 сравнения символов, первый 24, второй 25 и тре

выполнении свертки, либо адрес процедуры опознания в таблице онозна ния.

В клетках управляющей таблицы могут появиться следующие команды: (Перенос ; Замена ; Ошибка ; Опознание ; Конец ; Комбинированное опознание.

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

Изобретение относится к вычислительной технике, предназначено для аппаратной поддержки процессов трансляции и можат быть использовано в специализированных процессорах или программно-аппаратных средствах, осуществляющих перевод с языков программирования высокого уровня на машинный язык, а также а интерпретаторах языков программирования высокого уровня. Цель изобретения - расширение класса транслируемых входных языков путем обеспечения простого синтаксически управляемого перевода цепочек языков. Устройство содержит входной регистр, вычислитель, генератор импульсов, блок управления, счетчик адреса, блок постоянной памяти, блок магазинной памяти, выходной регистр, регистр символа, формирователь кода, два мультиплексора; счетчик глубины погружения, счетчик символов, регистр адреса, схему сравнения символов, три дешифратора. Устройство организует детерминированное магазинное преобразование на основе метода перенос-опознание путем применения детерминированного автомата с магазинной памятью. 9 ил. 1 табл. Q 5В С

тий 26 дешифраторы, управляющие выхо- 2Q ледовательность символов цепочки, код

30

ды 27-46 блока 4 управления, вход 47 кода команды блока 4 управления, осведомительные входы 48-52 блока 4 управления .

Блок 4 управления реализован в ви- 25 де микропрограммного автомата с использованием блока постоянной памяти (фиг.4). В нем используются горизонтальный формат микрокоманды и принудительная адресация с двумя адресными полями. Каждая микрокоманда имеет операционное поле Y, поле логических условий С и два адресных поля АО и ,А1. Микропрограммный управляющий автомат содержит IK-триггер 53, элемент И 54, элемент НЕ 55, регистр 56 адре- 35 са микрокоманды, блок 57 постоянной памяти, регистр 58 микрокоманды, адресный мультиплексор 59, дешифратор 60 кода команды, формирователь 61 логической единицы, мультиплексор 62 условий.

Блок 7 магазинной памяти (фиг.8) содержит счетчик 63 указателя вершины, вычитателъ 64, двухадресное запоминающее устройство (ОЗУ) 65,

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

40

45

50

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

правила (фиг.3). i

Работа магазинного преобразователя, работающего по методу перенос- опознание, заключается в последовательности сменяющих одна другую конфигураций от начальной до конечной.. Конфигурация магазинного преобразователя определяется как четверка (S,cЈ, Н,ft), где р - текущее состояние магазинного автомата; tf, - непрочитанная часть входной цепочки; Н - содержимое магазина, Р - часть выходной цепочки, выданная к данному моменту времени. Начальная конфигурация есть (S0, Х0 , Ь0, Ј), где S0 - начальное состояние автомата; о(0 транслируемая цепочка; Ь0 - маркер дна магазина; Ј- пустая цепочка. Конечная конфигурация есть (SK, i, h0I, /3), где S jj - заключительное состояние автомата; J. - маркер конца входной цепочки;

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

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

2для некоторого языка. Значения этих функций зависят от кодов входных и магазинных символов. Разряды кода символа можно рассматривать как значения

0

5 5

0

5

0

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

правила (фиг.3). i

Работа магазинного преобразователя, работающего по методу перенос- опознание, заключается в последовательности сменяющих одна другую конфигураций от начальной до конечной.. Конфигурация магазинного преобразователя определяется как четверка (S,cЈ, Н,ft), где р - текущее состояние магазинного автомата; tf, - непрочитанная часть входной цепочки; Н - содержимое магазина, Р - часть выходной цепочки, выданная к данному моменту времени. Начальная конфигурация есть (S0, Х0 , Ь0, Ј), где S0 - начальное состояние автомата; о(0 транслируемая цепочка; Ь0 - маркер дна магазина; Ј- пустая цепочка. Конечная конфигурация есть (SK, i, h0I, /3), где S jj - заключительное состояние автомата; J. - маркер конца входной цепочки;

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

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

2для некоторого языка. Значения этих функций зависят от кодов входных и магазинных символов. Разряды кода символа можно рассматривать как значения

516512986

булевых переменных, от которых -завн-нзчим переменные, соответствующие пор- сят указанные функции. Построениевому входу вычислителя (код входного осуществляется по таблице переходов символа) через X«-XW; переменные, со для данной ССП-грамматики. В управля-, стветствующие второму входу вычисли- ющей таблице имеются клетки шести ви-теля Скод магазинного символа) - че дов, соответствующие командам Пере-рез , Тогда сигнал f можно пред- нос, Ошибка, Замена, Опозна-ставить в виде дизъюнктивной нормаль- ние, Конец, Комбинированное опоэ-ной формы (ДНФ); нание-. Для задания кода командыю

достаточно, таким образом, intlog26 f V Г(ЛХ )Л С Л Y- )1

3 бита, хотя можно использовать и ;,, L j 1 }-., J J

другое кодирование (например, унитар- Xj (j 1 ,2,. . . , М) есть либо пе- ное) . Соответственно, первый выход ,, , ременная Х4, либо ее инверсия;

вычислителя 2 может состоять из трех 15 / , - ,„ ,. ,.Y1. (j 1 .2,. . ., М) - либо переменвыходов ft - f, значения сигналов на Л.

ная Y, либо ее инверсия;

которых можно рассматривать как функ- „

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

лицы, содержащих команды, ставший оит

на первый и второй входы вычислителя.

„vt кода которых ранен единице, т.е. чисДля клеток таблицы, содержащих коман- о

Пг „ „п || м,, - ло элементарных конъюнкции Х.Х,... ды Замена , Опознание и Комби- х Y Y Y нированное опознание, необходимо м «

Для приведенной управляющей табли- наличие также второго поля - кода сим- / ,- . л

цы {табл.) и кодов команд выражение вола для клеток, соответствующих ко- ,

.. .,-,с для f . имеет вид:

манде Замена , и адреса процедуры -

опознания для клеток, соответствую- f( X, , .

щих командам Опознание и Комби- ,.

п Сигнал т л принимает единичное знанированное опознание . РазрядностьL

,.чение в случае, если выбрана клетка второго выхода определяется как К

, . ч ..управляющей таблицы, содержащая ко- max(M.N), где М - разрядность кода 30«

„манду, средний бит кода которой ра- символа; N -разрядность адреса проце- . ,- Мг. „ „,.

„ вен 1 (командо Замена или Опозна- дуры опознания. Таким образом, вто- n г

„„ние ;.. Сигнал г, также можно предрои ВЫХОД СОСТОИТ ИЗ К ВЫХОДОВ g|-gfc „„J

to к ставить в виде значения сигналов из которых также

пг м м можно рассматривать как функции логи- ,- .-...

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

Изложение построения системы функ-таблицы, содержащих команций f, -f3, Ј -§кдля блока 2 иллюст-ды, средний бит кода кото

рируется построением функций для еле-40 рых Равен единице.

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

Пусть первая процедура опознанияимеет

имеет адрес 0000002, вторая - адресf (X, ХгХ3Х4У,)V

001010, третья - адрес 010100, чет-45 v СХ X X X Y Y Y Y )Y

вертая - адрес 100100-,.. 4 1 i э

Выберем коды команд. Пусть код ко-V(X, ХгХ3Х Ґ г YjY) V

манды Перенос равен 001,, , код коман- //v v v v v v v v /

.. „ n, nll/iV (.Л. А,Л.,Лч I i 14 I 1л /

ды Замена - 010, код команды Опоз-

нание - ОН 4, код команды Конец -50V (X, ХгХ 3X4Y,Y2Y3Y4) V

Ошибка - 0002.У(Х,)У

Сигнал f принимает единичное зна- jT Y Y Y Y )V чение в случае, если выбрана клетка 55 3

управляющей таблицы, содержащая коман-V (Х

ду, старший бит кода которой равен 1M/V TTV v v v v v

,... |, ,..,if Л. .1 j I, 1 ild.J V

(команды Конец и Комбинированное1

опознание в данном примере). Обоз- V (Х ,,Yp .

n-i „ м М л, -,

ft V Г(А Х;)А ( Л Y;)J, u j, J J

вить в виде

пг м м .-...

п - число клеток управляю

n-i „ м М л, -,

ft V Г(А Х;)А ( Л Y;)J, u j, J J

7 1651298

Сигнал f принимает единичное значение в случае, если выбрана клетка управляющей таблицы, содержащая команду, младший бит кода которой равен 1 (для приведенных выше кодов это команды Перенос, Опознание и Комбинированное опознание). , Сигнал fj в виде ДНФ имеет следующий вид:

ГЬ мАА (О

т.

8, .V ; ,

2

85 -.V/

тк

,У..

ГЬ г- М л,М -I

Ј5 -V Г(Л VA (Л VJ

Э, 1 L- , J

где ОС. (i 1,2,...,mj; j 1,2,. К) - элементарная конъюнкция, соотв ствующая клетке управляющей таблицы содержащей команду Замена, Опозн ние или Комбинированное опозна где и - число клеток управляющей

таблицы, содержащих команду, младший бит кода кото- 15 причем-gj принимает для этой рой равен единице.

Например, для приведенной выше управляющей таблицы и команд выражение для f3 имеет вид:

клетки единичное значение; mj - чис

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

Ј3 1(3c,XiX,X4Y1YtY3Y4.)V

v( у(х,хгх3х4У1ҐЛҐ)у

V xJtjX YjYiYjY V V(X,XfX,X4Y1YtYjY4)Y V(X1XaX,X4Y1YtY,Y4)V

(.

V(X(,)V .

VCXiX YjX YjY Y V

V(X13TIX3X4Y1Y4Y,Y4)V

У(х;т х3х4уД 4)у

V(X1Y1X3X4Y1Y2Y3Y4)V V(,X4Y(YeY,Y4)V V(X,X2X}X4Y,Y.,Y3Y4)V . VdTJtXjX jY YjY).

Если выбрана клетка управляющей , таблицы, содержащая команду Замена, Опознание или Комбинированное , опознание, то на втором выходе вы- числнтёл я 2 должны появляться сигналы принимающие значения, опреде-7 ляемые кодом нетерминального символа для команды Замена или адресом процедуры опознания для команд Опоз- 5 нание и Комбинированное опозна- , ние. Система булевых функций для имеет вид:

т.

2

85 -.V/

тк

,У..

где ОС. (i 1,2,...,mj; j 1,2,..., К) - элементарная конъюнкция, соответствующая клетке управляющей таблицы, содержащей команду Замена, Опознание или Комбинированное опознан 1е причем-gj принимает для этой

причем-gj принимает для этой

клетки единичное значение; mj - чис

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

Для проведенной выше управляющей .

таблицы и адресов процедур опознания меньшую разрядность имеет код символа. Дополнив недостающие разряды кода символа нулями слева, имеет код символа А, равным 000001. Величина К для этого примера равна 6. Система функций g gg имеет следующий вид:

8, X,,, gЈ .(XtX X3X4Y,YtY%Y4)V V(X1XiX3X4Y,YiYJY4)V

у(х,х2х}х4уДг 3У4)у

VCX.), 83 (X.

V(X1X4X,X4Y,YiY5Y4)V

V(X,X2.XjX4Y1Y4 Y3 4), g4

V(X X1X X4Y{Y Y3Y4)V

у(х,хгхД4уДг 5у4)у

V(X,X X3X4Y,Y2Y3Y4)V

УСх.),

8s- ( YC XiXjX Y Y V

V (X, X2.X3X4Y .ТДэ) , e6 (

УСх..дД),

Устройство запускается подачей сигнала на вход 13. По этому сигналу запускается блок 4 управления, который посыпает на вход 29 блока 7 магазин- ной памяти сигнал, производящий его очистку. После этого в вершину магазина записывается код маркера дна путем подачи сигнала 30 записи при выбранном четвертом информационном входе второго мультиплексора 19, для чего блок управления подает сигналы 36 и 37. Затем блок управления выдает сигналы на вход 34 разрешения записи входного регистра 1 и на выход 14 устройства Готовность обработки текущего символа, обеспечивая тем самым прием первого входного символа на входной регистр.Далее блок управления записьюает-в регистр 9 кор текущего символа вершины магазина, для чего на блок 7 подается сигнал 41 чтения, а на регистр 9 символа - сигнал 33 разрешения записи. Коды текущего входного символа с регистра I и верхнего символа магазина с регистра 9 поступают соответственно на первый и второй входы вычислителя 2, на первом выходе 47 которого вырабатывается код команды. В зависимости от кода коман- ды блок управления переходит к выполнению одной из ветвей алгоритма работы.

Если в блок 4 управпения поступил код команды Перенос, то блок упргв- ле#ия подготавливает запись текущего входного символа в магазин путем подачи сигнала подготовки к записи 0 на блок 7. Далее блок 4 управления выбирает третий информационный вход второго мультиплексора 19 и записывает код символа с входного регистра 1 в блок магазинной памяти, для чего подаются сигналы 30 и 37. После этого блок 4 принимает на входной регистр код следующего входного символа, записывает в регистр 9 код текущего верхнего символа магазина и повторяет анализ кода команды.

Если в блок 4 управления поступает код команды Замена, то на управляющий вход 36 второго мультиплексора J 9 подается единичный сигнал. Код символа с второго выхода вычислителя 2 через второй мультиплексор 19 поступает на информационный вход блока 7 и при подаче сигнала 30 замещает код символа, находящегося в вершине магазина. Затем блок 4 управления записывает в

г ю 15 20 25 30

35 до 5

-„

5

регистр 9 TVOA верхнего символа магазина и повторяет анализ кода команды.

Если в блок 4 управлонт поступил код команды Ошибка, то блок 4 управления выдает сигнал на выход 1 7 . устройства Ошибка, и устройство заканчивает свсго рабо гу.

Если в блок 4 управления поступает код команды Опознание то на сход счетчика 5 адреса подается сигнал, осуществляющий запись начального адреса первого пакета, который вырабатывается на втором выходе вычислителя 2 и через первый мультгапексор 18 поступает на информационный вход блока 5. Начинается анализ элементов первого пяг -та. Производится чтение чз блока 6 первого элемент, пакета - адреса следующего пакета (Лшг.З) и запись его в регистр 22 адреса. Для этого блок 4 управления подает сигналы на входы 43 блока 6 и 46 регистра 22. Затем из блока 6 читается следующий элемент пакета - длина цеточки стволов, которая записывается в счетчик 21 символов. Дпя этого из блска 4 управления подаются снгнали на входы 28 счетчика 5 адреса5 +3 блока 6 и 44 счетчика 2 символов. Производится опрос выхода 49 первого дешифратора 24. Если сигнал 49 равен единице содержимое счетчика 2 символов равно нулю), то цепочка символов в пакете отсутствует. Такая ситуация соответствует правилу входной грамматики, правая часть которого состоит всего из одного символа. В этом случае из блока 6 считывается следующий элемент пакета - выходной символ, записываемый в выходной регистр 8, для чего на управляющие входы 28 счетчика 5 адре- са} 43 блока 6 и 32 выходного регистра 8 подаются сигналы из блока 4 управления. Если на выходе 50 второго дешифратора 25 появляется единичный сигнал, то в регистре 8 находится фиктивный нулевой выходной символ (такая ситуация соответствует отсутствию выходного символа в опознанном правиле); в этом случае сигнал на выходе 15 устройства Готовность символа выходной цепочки не появляется. Если сигнал 50 равен нулю, то на выход 15 устройства выдается сигнал из блока управления. После этого осуществляется замена верхнего символа маг rassma на симяол, код которого находится в следующем элементе пакета. Путем подачи сигнал а на управляющие входы 28 счетчика 5 адреса, 43 блока 6 и 30 блока 7 магазинной памяти осуществляется передача кода символа с информационного выхода блока 6 через второй мультиплексор 19 в блок 7 ма ,газипной памяти. Затем блок 4 управ- 1ления записывает в регистр 9 символа код верхнего символа магазина и повторяет анализ кода команды.

Если сигнал 49 равен нулю, то подачей сигнала на вход 38 счетчик 20 глубины погружения устанавливается в нуль. Осуществляется сравнение первого символа из пакета с символом, находящимся в магазине, для чего блок 4 управления подает сигналы на входы 39 счетчика 20 глубины погружения, 28 счетчика 5 адреса, блока 7 магазинной памяти, 43 блока б и 45 счетчика 21 символов. Если символы не равны, что определяется опросом сиг

нала 52 с выхода схемы 23 сравнения символов, то проверяется сигнал 51 (равенство нупю регистра 22 адреса). Если этот сигнал также равен нулю, то производится переход к анализу следующего пакета путем занесения его адреса из регистра 22 через первый мультиплексор 18 в счетчик 5 адреса. При этом подаются сигналы 35 на первый мультиплексор 18 и 27 на счётчик 5 адреса.

Если сигнал 51 равен единице, то пакет.в процедуре был последним; на выход 17 устройства Ошибка выдается сигнал, и устройство заканчивает свою работу.

Если символы равны, то проверяется значение счетчика 21 символов путем опроса сигнала 49. При ненулевом содержимом счетчика 21 цикл сравнения повторяется для символа, хранящегося в следующем элементе пакета. Если содержимое счетчика 21 символов равно нулю (правило опознано), то производится выдача выходного символа так, как это было описано выше. После этого осуществляется выталкивание символов из магазина. Количество выталкиваемых символов, находящееся в следу ющем элементе пакета, считывается из блока 6 и записывается в счетчик 21 символов, для чего подаются сигналы 28 на счетчик 5 адреса, 43 на блок 6 и 44 на счетчик 21 символов. Символы по одному выталкиваются из магазина

10

15

20

25

30

40

АС

путем подачи управляющих сигналов 31 на блок 7 магазинной памяти и 45 на счетчик 21 символов до появления единичного сигнала 49. Затем осуществляется запись символа из следующего элемента пакета в магазин. Для этого сначала производится подготовка блока 7 путем подачи сигнала 40. Затем код символа из блока 6 через второй мультиплексор 19 поступает на информационный вход блока 7 магазинной памяти и записывается в него путем подачи сигналов 28, 30, 43. Далее блок 4 производит чтение верхнего символа магазина на регистр 9 символа и повторяет анализ кода команды.

Если в блок 4 управления поступил код команды Конец или Комбинированное опознание, то подачей сигнала на вход 38 счетчика 20 глубины погружения производится его обнуление, после чего двукратной подачей сигнала на вход 39 этого же счетчика в нем устанавливается адрес - два. Затем осуществляется просмотр магазина путем подачи сигнала 42 на блок 7 магазинной памяти. Если при отом произошел выход за дно магазина (сигнал 48 принял единичное значение), то блок 4 управления выдает сигнал на выход 16 устройства Конец преобразования и устройство заканчивает свою работу.

Если при нулевом сигнале 48 на первом выходе 47 вычислителя 2 присутст- 35 вует код команды Конец, то на выходе 17 устройства Ошибка выдается логическая единица и устройство заканчивает свою работу. В противном случае производится переход к выполнению команды Опознание.

В исходном состоянии триггер 53 находится в нулевом состоянии, на информационный вход регистра 56 адреса микрокоманды поступает нулевой адрес, являющийся начальным для микропрограммы. Импульс запуска устанавливает триггер 53 в единицу, разрешая прохождение импульсов через элемент И 54 на вход чтения блока 57 постоянной памяти, на вход записи регистра 58 микрокоманды и на вход элемента НЕ 55. В единичном полутакте микрокоманда читается из блока 57 по адресу, находящемуся на регистре 56, и записывается в регистр 58 микрокоманды. Поле Y микрокоманды, исключая младший разряд, выдается на выходе автомата. По - ле С микрокоманды выбирает одно из

50

5

условий, поступающих на входы мультиплексора 62. Если выбранное-условие выполняется (равно логической единиц це) или если выбрано тождестренное условие, то на вход выбора направления мультиплексора 59 поступает единица, чем обеспечивается прохождение адресного поля А1 микрокоманды на регистр 56 адреса микрокоманды. Если выбранное условие равно нулю, то выбирается поле АО микрокоманды. Таким образом9 на выходе мультиплексора 59 вырабатывается адрес следующей микрокоманды, который в нулевом полутакте записывается в регистр 56v и цикл работы микропрограммного автомата повторяется. Работа автомата заканчивается, если на регистр 58 считывается специальная микрокоманда останова, содержащая единицу в младшем разряде поля Y и нули во всех остальных, по которой на информационный вход регистра 56 адреса микрокоманды подается нулевой адрес, а на вход установки в нуль триггера 53 поступает единица, которая устанавливает его в нулевое состояние и, тем самым, запрещает прохождение тактовых импульсов через элемент И 54.

Работа автомата определяется его микропрограммой, записанной в блоке 57, Функциональная микропрограмма содержит в себе как сведения о форма- те и типе слов, с которыми оперирует микропрограмма, так и алгоритм выполнения микропрограммы.

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

Запись символа в магазин осуществ- ляется за два такта. В первом такте на вход 40 подготовки к записи в магазин подается единичный сигнал, который увеличивает содержимое счетчика 63 на единшг/, после чего в нем находится адрес следующей (пустой) ячейки оперативной памяти. Во втором такте код символа, поступающий с информационного входа магазина, по сигналу, подаваемому на вход 30 записи в магазин, записывается в ОЗУ 65, по адресу, поступающему со счетчика 63 указателя вершины на первый адресный вход ОЗУ 65.

jg TQ 5 jg

35

,,.

.

0

5

Замена а ро из водит с я гго сигналу, подаваемому на вход 30 записи в магазин. При этом содержимое счетчика 63 не менгетгя т.е. на первый адресный вход ОЗУ 65 подается адрес текущей верхней ячейки, и код символа, поступающий с информационного входа магазина, записывается в ОЗУ 65.

При подаче единичного сигнала на вход 41 чтения из магазина производится чтение ячейки ОЗУ 65, адрес которой поступает на первый адресный вход со счетчика 63. На первом информационном выхода ОЗУ 65 появляется код верхнего сиквола, который передается ка первый информационным выход блока магазинной памяти.

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

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

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

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

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

20

«« ., - 25™

35

40

45

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

Примечание. A, I, N, M, Т- нетерминальные символы, б, ц, , - терминальные символы; 1 - маркер конца входной цепочки; Ь0 - маркер дна магазина.

W 45 52 1 -ttt-t

за«-г

Lr

rt

I

й/г. /

Адрес : процедуры из управляющей

таблицы

О

Адрес следую- щего пакета или О

Длина цепочки (п)

1-й символ цепочки

2-й символ цепочки

п-й символ цепочки

Код 8ь/ходяого символа или О

а Число вытал/fuBt

ании

Код за лисыва- емого символа

1-6. пакет процедуры

D

2-й пакет процедуры

3)

т-и пакет процедуры

Фиг.2;

Адрес сяевдюшЈ w пакета или О

Код дь/хойнаго символа или О

Код записывав- мого символа

фиг.З

ОЧ Ul

N9 VO 00

ШШ

|1 Й

/

У

WflCT5 .«U

явяомб: 1;

WRRbW.-Г)

ШСГ5: 1 лвяомб: г, iYRcr2J: sf;

ГА/ Tjref; шомб: «,

Vfl 58Js::J;

тст5 - Г, й)яомб: 1;

WK&fMH к /;

7 N/

шстз: -П Шайб 1; киям: -П

г.5

U

т

wccrs: -r,

ЪОЯОНб .гяГ,

тст2Г.г,

ШГСГ27: т; / 0Р5Ш7: 7;

PUSHSTtt7: 1 ,

JNCCT5: - If ЪШМ6: Г, 1УЯ5ТМ7: 7;

7 Ч/

Фиг. 7

Ш2Ф П

1НССТ2Ф .Г,

ШСТ20: Т,

YJEIVSTM « . 1.

it

. .. ,

-Л риптмт п Комбинированное опознание

{Конец j

77

72

а к охов 13 J v

nepStiuВх.

Вход 11 ВыходП

Первый вь/х. символ

Л

в

55

«ЙЬ

Ь8

Фиг.8

Четвертый Х /Н СледюО ГЧХ Jf

А

второй Третий XIЯослеИниь .,

ААА

-конец пре- 1 о разоВания

Фиг.9

xst/avc/wf ce/r/агла не taw