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

 

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

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

Ю

РЕСПУБЛИК

А1.,SUÄÄ 1651298 рр С 06 Р 15/38

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

Н AST0PCH0MY СВИДЕТЕЛЬСТВУ

3l!iИ33. ;Я

4А1 %% - - ,, f>,4

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

fO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

flPH fHHT СССР (21) 4699678/24 (22) 81.06.89 . (46) 23.05.91, Вюл. 9.! 9 (71) Ленинградский электротехнический институт им. В.И.Ульянова (72) И.А.Кузнецов, Г.В.Разумовский и В.С,Фомичев (53) 68!.325(088,8) (56} Авторское свидетельство СССР

Ф 1196899, кл. 0 06 F 15/38, 1985.

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

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

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

2 рования высокого уровня на машинный язык, а также в интерпретаторах языков программирования высокого уровня.

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

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

9 ил. 1 табл.

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

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

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

1 тор 3 импульсов, блок 4 управления, счетчик 5 адреса, блок 6 постоянной

-памяти, блок 7 магазинной памяти, выходной регистр 8, регистр 9 символа, формирователь 1 О кода, информацион5 ный вход 11 устройства, информационный выход 12 устройства, вход 13 запуска устройства, выход 14 устройства"Готовность обработки текущего сим- 1О зола", выход 15 устройства "Готовность символа выходной цепочки", выход 16 устройства "Конец преобразова.ния., выход 17 устройства "Ошибка", первый 18 и второй 1 9 мультиплексоры соответственно, счетчик 20 глубины погружения, счетчик 21 символов, регистр 22 адреса, схему 23 сравнения, символов, первый 24, второй 25 и третий 26 дешифраторы, управляющие выходы 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.

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

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

"Опознание"; "Конец"; "Комбинированное опознание".

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

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

Конфигурация магазинного преобразователя определяется как четверка (S ОС, Н, P ), где S — текущее состояние магазинного автомата; g — непрочитанная часть входной цепочки; Н вЂ” содержимое магазина, P — часть выходной цепочки, выданная к данному моменту времени. Начальная конфигурация есть (S gs Ф0, Ь -, E ), где S — начальное состояние автомата; (— транслируемая цепочка; h — маркер дна магазина; Я вЂ” пустая цепочка. Конечная конфигурация есть ($,, », haI, P<), где

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

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

l 651298 булевых переменных, от которых зависят указанные функции. Построение осуществляется по таблице переходов ° для данной ССП-грамматики. В управляющей таблице имеются клетки шести видов, соответствующие командам "Перение", "Конец", "Комбинированное опознание . Для задания кода команды 10 достаточно, таким образом, inelog<6=

3 бита, хотя можно использовать и другое кодирование (например, унитарное). Соответственно, первый выход вычислителя 2 может состоягь из трех 15 выходов Е1 — f, значения сигналов на которых можно рассматрнвать.как функции логических переменных„ подаваемых на первый и второй входы вычислителя.

Для клеток таблицы, содержащих команды "Замена", "Опознание". и "Комбинированное опознание.", необходимо наличие также второго поля — кода символа для клеток, соответствующих ко: маиде "Замена", и адреса процедуры .опознания для клеток, соответствующих командам Опознание и Комбинированное опознание". Разрядность второго вьгхода определяется как К =

= шах(Г1,N), где М вЂ” разрядность кода 30 символа; N -разрядность адреса працедуры опознания. Таким образом, второй выход состоит из K выходов g<-gl, значения сигналов из которьгх также рассматривать как функции логи 35 ческих переменных, подаваемых на входы вычислителя.

Изложение построения системы функций и -f g 1--g к для блока 2 иллюстрируется построением функций для сле- 0 дую>щей управляющей таблицы (табл.1}.

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

001 010< третья — адрес 0101 ОО, чет- !!5 вертая — адрес ) 00100 .

Выберем коды команд. Пусть код команды "Перенос" равен 001, код коман2

>! ды "Замена" - 010, код команды Опознание" — 011, код команды "Конец" -50 !

00, код команды "Комбинированное опознание" — 101, . код команды

"Ошибка" — ООО .

Сигнал f принимает единичное значение в случае, если выбрана клетка 55 управляющей таблицы, содержащая команду, старший бит кода которой ранен 1 (команды "Конец" и "Комбинированное опознание" в данном примере). Обозначим переменные, соответствующие первому входу вычислителя (код входного символа) через Х -Х 1 переменные, соответствующие второму входу вычислителя,код магазинного символа) — через 7< -7 . Тогда сигнал f можно представить в виде дизъюнктивной нормальной формы (ДНФ):

М М г, - >/ ((Лх;>! < A >,>), л где Х (j = 1, 2,..., Г1) есть либо переменйая Х1, либо ее инверсия;

Гъ

7 {j = 1 2,..., Г1) — либо переменная У „ либо ее инверсия; п, — число клеток управляющей -.аблицы, содержац>их команды, старший бит кода которь!х равен единице, т.е. числ Л ло злементарных конъюнкций Х, Х хм7171 Ум

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

Х47! У 7 74

Сигнал f. принимает единичное значение в случае, если выбрана клетка управляющей таблицы, содержащая ко— манду, средний бит кода которой равен 1 (команды "Замена" или "Опознание"). Сигнал f также можно представить в виде ДНФ: . м м !, =л ((A;>! с л ° >1, где n — число клеток управляющей таблицы, содержащих команды, средний бит кода кото рых равен единице.

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

f = (ХХХХ47777)V

Ч {Х Х Х Х47 17Р

V(X1 XòXçX47,%2Y Y4) V

Ч(ХХ Х Х4У 7 7 74)Ч

Ч (Х! Х хзХ47 7 7 74) Ч

Ч (Х, Х Х Х+У !7 7з74) I>

Ч (х, х,х,х,У, 77 74) v

Ч(х,Х.,Х,Х 7,7,7,74) Ч м (х, х,х,х47, Y,Y,у+) ч

4(1 4 1 З 4)

Ч (; x.-x3x47! Y Y374) 1651 298

m! а! =.V 0 у

1=1!!!г

@2 >

45

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

"Комбинированное опознание) ° ; Сигнал f> в виде ДНФ имеет следующий вид: д 1О

, -,v ((,л,) с л,Ц, где п — число клеток управляющей

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

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

f — (Х,Х Х Х47,7гТз74.)Ч

V (Х, Х Х. Х„Y Y Т 74)Ч .Ч (Х ХгХЗХ47,7гТэ74)Ч

Ч(Х!ХгХ Х47(Тг7 74)Ч

Ч(Х Х Х Х47!ТгТз74}Ч

Ч (x„x,х, х,Р,Т,Т,Y+) V

Ч(Х Хг Х Х47!7гТз74) Ч

y(x x x x 7,7,7,7,) Y

Ч (xi хгх р 47 7 гт э7 4) Ч ч (х„х хР 47!ТгтзТа.) Ч

V(X! ХгХз Х4717гТРа) V

Ч (Х1хгх х 47,7гТэТ а) Ч

U(Х(ХгХ Ха7 iY Y Y4)Y

V(X ХгХ Х4717г7374}

Ч (X) ХгХ Х 47 !Т гТз74)"

V (Xi X,Х,X4Yi Y Yç Y4)Если выбрана клетка управляющей

-таблицы, содержащая команду "Замена", "Опознание" или "Комбинированное опознание", то на втором выходе вы- 50 числителя 2 должны появляться сигналы принимающие значения, определяемые кодом нетерминального символа для команды "Замена" или адресом процедуры опознания для команд "Опознание" и "Комбинированное опозна-, ние".-Система булевых функций для HMee V<

1>>к к ак =,V

> к

4 где 0С (1 = 1,2,...,m ; j = 1,2,..., 1 1

К) — элементарная конъюнкция, соответствующая клетке управляющей таблицы, содержащей. команду "Замена", "Опознание" или "Комбинированное опознание", причем-g принимает для этой клетки единичное значение m — чисУ ло таких конъюнкций, Предполагается, что если разрядность кода символа и разрядность адреса процедуры :опознания неодинаковы, то код или адрес, имеющий меньшую разрядность, дополняется до большей разрядами, имеющими произвольное значение.

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

g, = Х,Х,Х,Х47,7,7,т4, g2 (Х! ХгХ3ХФТ !Тг7 71)Ч

VIX! XàXÐ4Y Л 374) Ч

Ч(Х,X X X47„7,7,7 )Q

Ч (Х ХгХ ха 7 7гТз74), 8, = (Х!ХгХ Х47,7г7, +)Ч

Ч(х, ххх,хаТ,Тг7, 74}Y

Ч(Х! ХгхЗХ+717г737ф)

g4 (Х Х ХэХ47,7гТз74) Ч т! XXX XX3XX4YYt YYKYY3YY4) YY

Ч (Xi Х гхоз Х 47 i Y Y 74) Q

v(х, х,х,х,т,ттр,)v

Ч(Х Х Х Х47 7 Т,уа.) g g = (Х !Хгхэх 47 qТгТP4)Ч

V (Х, ХгХ Х47 ТгТэТ+)Ч

Ч (Х, Хгх х+Т,ТгТэ74), g6 = (Х!Хгх х47 !ТгТРа.) У

v(x„õ,X, х47, 7,7,74 ), 1651298

Устройство запускается подачей сигнала на вход 13. По этому сигналу запускается блок 4 управления, который посыпает на вход 29 блока 7 магазинной памяти сигнал, ",ðîèçâîäÿùèé его очистку. После этого в вершину магазина записывается код маркера дна путем подачи сигнала 30 записи при выбраиного четвертом информационном входе 10 второго мультиплексора 19, для чего блок управления подает сигналы 36 и

37, Затем блок управления выдает сигналы на вход 34 разрешения записи входного регистра 1 и на выход 14 устройства "Готовность обработки текущего символа", обеспечивая тем са" мым прием первогo входного символа на входной регистр. Далее блок управления записывает.в регистр 9 код текущего символа вершины магазина, для чего на блок 7 подается сигнал 41 чтения, а на регистр 9 символа — сигнал 33 разрешения записи. Коды текущего входного символа с регистра 1 и верхнего символа магазина с регистра 9 поступают соответственно на первый и второй входы вычислителя 2, на первом выходе 47 которого вырабатывается код команды..В зависимости от кода коман- 30 ды блок управления переходит к выполнению одной из ветвей алгоритма работы.

Если в блок 4 управления поступил код команды "Перенос", то блок управ- 35 леНия подготавливает запись текущего входного символа в магазин путем подачи сигнала подготовки к "=àïèñè 40 на блок 7. Далее блок 4 управления выбирает третий информационный вход второго мультиплексора 19 и записывает код символа .с входного регистра 1 в блок магазинной памяти, для чего подаются сигналы 30 и 37 ° После этого блок 4 принимает на входной регистр 45 код следующего входного символа, записывает в регистр 9 код текущего верхнего символа магазина и повторяет анализ кода команды, Если в блок 4 управления поступает код команды "Замена", то на управляющий вход 36 второго мультиплексора 19 подается единичный сигнал. Код символа с второго выхода вычислителя 2 через второй мультиплексор 19 поступает на информационный вход блока 7 и при

55 подаче сигнала 30 замещает код символа, находящегося в вершине магазина.

Затем блок 4 управления записывает в ре hcTp 9 код веj:õíåò о символа магаpH на и повторяет анализ кода к ",àíäû.

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

Гсли в блок 4 управления поступает код команды "Опознание" то на вход счетчика 5 адреса подается сигнал, осуществляющий запись начального адреса первого пакета, который вырабатывается на втором выходе вычислителя 2 и через первый мультиплексор 18 поступает на информационный вход блока 5.

На:ннается анализ элементов первoro пат -та. Процзводится чтение иэ блока

6 первого элемент"-. пакета — адреса следующего пакета (фиг.3) и запись

ere. н регистр 22 адреса. Для этого . бл.:к 4 управления подает сигналы на входы 43 блока 6 и 46 регистра 22.

Затем из блока б читается следующий элемент пакета — длина цепочки символов, которая sàïèñûâàåòñÿ в счетчик

21 символов. Для этого из блока 4 управления подаются сигналына входы 28 счетчика 5 адреса, 43 блока 6 и 44 счетчика 21 символов. Производится опрос выхода 49 первого дешифратора 24 °

Если сигнал 49 равен единице содержимое счетчика 21 символов равно нуля), то цепочка символов в пакете отсутствует. Такая ситуация соответствует правилу входной грамматики, правая часть которого состоит всего из opFFýãî символа . В этом случае из блока 6 считывается следующий элемент пакета. — выходной символ, записываемый в выходной регистр 8, для чего на управляющие входы 28 счетчика 5 адреса, 43 блока 6 н 32 выходного регистра 8 подаются сигналы из блока 4 управления. Если на выходе 50 второго дешифратора 25 появляется единичный сигнал, то в регистре 8 находится фиктивный нулевой выходной символ (такая ситуация соответствует отсутствии выходного символа в опознанном правиле); в этом случае сигнал на выходе 15 устройства "Готовность символа выходкой цепочки" не появляется.

Если сигнал 50 равен нули, то на выход 15 устройства выдается сигнал из блока управления. После этого осуществляется замена верхнего символа ма"; газина на символ, код которого нахо1651 298

12 дится в следующем элементе пакета. Путем подачи сигнала на управляющие входы 28 счетчика 5 адреса, 43 блока

6 и 30 блока 7 магазинной памяти осуществляется передача кода символа с информационного выхода блока 6 через второй мультиплексор 1 9 в блок 7 ма,газинной памяти. Затем блок 4 управIления записывает в регистр 9 символа код верхнего символа магазина и повторяет анализ кода команды.

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

39 счетчика 20 глубины погружения, 28 счетчика 5 адреса, блока 7 мага20 зинпой памяти, 43 блока 6 и 45 счетчика 21 символов. Если символы не равны, что определяется опросом сигнала 52 с выхода схемы 23 сравнения символов, то проверяется сигнал 51 (равенство нулю регистра 22 адреса).

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

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

Если символы равны, то проверяется значение счетчика 21 сймволов путем опроса сигнала 49.. При ненулевом содержимом счетчика 21 цикл сравнения повторяется для символа, хранящегося в следующем элементе пакета. Если содержимое счетчика 21 символов равно .нулю (пранило опознано), то производится выдача выходного символа так, как это было описано выше. После это:го осуществляется выталкивание симво50 лов из магазина ° .Количество выталкиваемых символов, находящееся в следующем элементе пакета, считывается из блока. 6 и записывается в счетчик 21 символов, для чего подаются сигналы. .28 на счетч п< 5 адреса, 43 на блок 6 ! и 44 на счетчик 21 символов. Символы по одному выталкиваются. из магазина путем подачи управляющих сигналов 31.. на блок 7 магазинной памяти и 45 на счетчик 21 символов до появления единичного сигнала 49. Затем осуществляется запись символа из следующего элемента пакета в магазин. Дпя этого сначала производится подготовка блока 7 путем подачи сигнала 40. Затем код символа из блока 6 через второй мультиплексор 1 9 поступает на информационный вход блока 7 магазинной памяти и записывается в него путем подачи сигналов 28, 30, 43. Далее блок 4 производит чтение верхнего символа магазина на регистр 9 символа и повторяет анализ кода команды.

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

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

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

В единичном полутакте мьп<рокоманда читается из блока 57 по адресу, находящемуся на регистре 56, и записыва ется в регистр 58 микрокоманды. Поле

Y микрокоманды, исключая младший разряд, выдается на выходе автомата. По:ле С микрокоманды выбирает одно из

14

13

1651 298 условий, постунающих на входы мультиплексора 62. Если выбранное условие выполняется (равно логкческок едини-. це) или если выбрано тождественное

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

Работа автомата определяется его микропрограммой, записанной н блоке

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

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

55 адресу, поступающему со счетчика 63 указателя вершины на первый адресный вход ОЗУ 65.

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

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

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

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

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

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

У В

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

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

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

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

ЛЯ BTOPOH ВЫХОД КОТОРОГО ПОДКЛИЧЕН К

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

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

16Я 298

l7

1000

Код

1 001

1 01 0 I 111

Входной символ

Магазинный симКод вол

Опознание 2 Ошибка

Опознание 3

Опознание 3 Опознание 3 Опознание 3

Ошибка

Перенос

Опознание 4 Ошибка

1010

Ошибка

Ошибка

Перенос

Оооо h0

Ошибка

П р и м е ч а н и е. А, I, М, М, Т вЂ” нетерминальные символы, б, ц, терминальные символы; 1. — маркер конца входной цепочки; h — маркер дна магазина.

Я б

1б

1 1

0001 А

001 О Е

0011 К

0100 М

Îl 01 Т

11000 б

1001 ц

Ошибка

Перенос

Ошибка

Ошибка

Ошибка

Опознание 2

Ошибка

Перенос

Ошибка

Перенос

Перенос

Ошибка

Ошибка

Ошибка

Ошибка

Перенос

Конец

Замена А

Замена А

Ошибка

Опознание 1

Опознание 2 1651298

Адрес;

Щ Щ Оффис/

Щ g/7 04 д

ДЯЮЩУИ тадлицы

Фиг.2, 1651 298.l б51 298

1651298

3 65l 298

С/Фщо7

Вкаг а

АФр/ии к. сикйл

Виад 11 kw 1pemvd

Фю& ть!й послоони0 Ф

ОеР3ий Ую сиМ4л ото ои

T отий Юоо Вней

ЯЬщ щюоооаж она мзначсние ст М невежи©

Редактор В.Петраш

Заказ 1 608 Тираж 4)8 Подписное

ВНИИПИ ГосУдарственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-издательский комбинат Патент, r Ужгород, ул. Гагарина, tI It ,0

ЯыкпФФ ныход12

Ныхад1У

Выход1б йод 17

И

40 гу

ЗО

Составитель В.Сячев

Техред М.Дицык Корректор А, Обручар