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

 

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

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

РЕСПУБЛИН (19) (11) А1 (gg 4 G 06 F 11/28

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

Н А ВТОРСНОМ,Ф СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) ф140863/24-24 (22) 27.10.86 (46) 15.05.88. Бюл. У 18 (72) В. К. Водопьянов, Ю. А. Орлов, В. Н. Цымбал, В. Н. Завьялов и Г. В. Назарьян (53) 681.3(088.8) (56) Авторское свидетельство СССР

11 637818, кл. G 06 F 11/28, 1976.

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

Р 669356, кл. С 06 F 11/28, 1976» (54) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО

КОНТРОЛЯ (57) Изобретение относится к вычислительной технике и может быть использовано в системах преобразования и обработки информации, в частности в многопроцессорных вычислительных комплексах. Целью изобретения является повышение быстродействия. Устройство содержит регистры 1 и 6 текущего символа, дешифраторы 2 и 7 лексических единиц, каналы 3 и 8 синтаксического анализа, блок 4 микропрограммного управления, дешифратор 5 полуоснов. Повышение быстродействия устройства обеспечивается тем, что оба канала синтаксического анализатора работают параллельно и независимо один от другого. 5 ил.

1396146

Изобретение отч3осцтс1- к вычислительной технике и может быть иc30льзовано в системах преобр«зования и

Обработки информации„ в частности, в многопроцессорнъ3х «ычислительных комплексах.

11елью изобретения является повышение быстродействия устройства.

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

«нализа; на фиг. 3 — структурная схема блока памяти, :-3а фиг, 4 — блок - 15 схема микропрограимн JI o управления каналом си таксич = ск зго «нализа; на фиг. 5 — блок-схе;. а микропрограммного управления устройства в целом, устройство для синтаксического 20 конт1 оля (фи3, 1 ) содержит первый регистр 1 текущет о символа, первый дешифратор 2 лексяче: ких единиц, первый канал 3 с33нтаксического анализа, блок 4 микропрэгр«миног 0 управ- 25 ления, дешифратОр1 5 полуоснОВ„ BTo рой регистр 6 текущего символа, вloрой дешифратор 7 лек=ических единиц .I HToDcA канал 8 =ингах .Ического àаализа.

Канал сиптаксичес"<его анапиза (фиг„2) содержит блок э33:.ментов ипр,. блок 10 микропрограимпогo управления, блок 11 памяти и деш,3фратор 12 Осно.в

13 состав блока 11 пìÿòH (фиг. 3)

Входит группа 1 3 из . рек реверсив3ьг< сдвиговых регистров.

Регистры 1 и 6 те:сущегo символа используются для храпения очередных лексических единиц частей исходного выражения, Дешифраторы 2 и 7 вьделя3от из лек сических еципиц И1 ходнст О выражения операнды, онер апии, скобки, а также признаки начала и конца выражения.

При этом отличие» IIHEIKJöî÷åHHH группы выходов дешифратора 7 к группе .

ВХОДОВ признакОВ лексических единиц канала 8 от подкл1очепия группы Вьгходов дешифратора 5 к I"руппе Входов признаков лексиче< ких единиц канала

3 заключается в том, что выход дешифр«тора 7, означающий постуIIJIPHHP иа вход деш33фратора лексической единиць3 (, подключа ет1 я к входу npu1l / l1

l1 1 11

= íàêà лексической единицы ) кан 13а

8, выход де313ифратора 7, означающий поступление на вход дешифратор« лек1! сической единицы ) — к входу IIpH знака лексической единицы "(", а выход дешифратора 5, означающий поступление на вход дешифратора лексической единицы "(", подключается к входу признака лексической единицы "(канала 3, выход дешифратора 5, означающий поступление на вход дешифратора лексической единицы ")11 — к входу признака лексической единицы ")" канала 3.

Каналы 3 и 8 синтаксического анализа осуществляют предварительную свертку частей исходного выражения.

Каналы полностью идентичны по составу., назначению элементов и алгоритму функционирования, Блок 9 элементов ИЛИ используется для объединения группы выходньгх сигналов микроопераций блока 10 микропрограммного управления и группы выходных сигналов микроопераций блока микропрограммного управления по управлечию работой блока 11 памяти.

Блок 11 памяти — это память с пос".. ледовательным безадресным принципом записи и чтения с обеспечением возможности доступа для чтения одновременно к нескольким старшим разряДам.

Блок 11 ннмяти может быть выполнен известным способом на реверсивных

1 сдвигавших регистрах, Реверсивные сдвигающие регистры

13 блока 11 памяти осуществляют запись кодов лексических единиц в стар-! шие N-1 разряды, хранение записанной информ ации, поразрядный сдвиг сод ержимого вправо или влево„а также выдачу записанной информации из (N-2)-Х (N-1)-Х и N-X разрядов на дешифратор

12 основ при предварительной свертке частей исходного выражения в каналах или из (N-1)-Х и N-Х разрядов на де" шифратор 5 полуоснов при окончательной свертке выражения, Блок 10 микропрограммного управления управляет работой всех элементов канала, На фиг. 4 приведена бло к-схема функционирования блока, где входные сигналы Х,-Х формирует дешифратор 2 (для второго канала — дешифратор 7) лексических единиц, Х 6 — дешифратор

12 основ, Х, — блок 4 микропрограм-, много управления. На выходе блока 10 микропрограммного управления формируются сигналы микроопераций У, -У, и > 9

1396146

Содержательный смысл входных и выходных сигналов следующий:

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

5 конца части выражения Ф;

9, в противном случае;

1, если лексическая единица исходного выражения есть открыва-. ющая скобка (для второго кана- 10 ла — закрывающая скобка);

9, в противном случае ;

Х L

1, если лексическая единица исходного выражения есть операнд;

И, в противном случае;

1, если лексическая единица исходного выражения есть знак операции;

g в противном случае;

Х

1, если лексическая единица исходного выражения есть закрывающая скобка (для второго канала — открывающая скобка);

9, в противном случае;

Х

l, если в разрядах (И-2), (N-l ) и N блока 1 памяти содержится основа Г » F или (F);

9, в противном случае; 30

1, если блоком 4 микропрограммного управления была выдана микрооперация У,, т.е. устройство завершило работу;

9, в противном случае;

Х ш

У1Р 1м з микрооперации, используемые для формирования кодов лексических единиц на информационном входе 40 блока 11 памяти; микрооперация, соответствующая коду лексической единицы "Я" начала части выражения; 45 микрооперация, соответствующая коду лексической единицы "(" — скобка открывающая; совокупность микроопераций, соответствующая коду лексической единицы

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

Р— операнд.

Сигналы микроопера ций Y,, Y., Y

Ъ поступают на первые входы первого, второго и третьего элементов ИЫ блока 9, выходы которых соединены с информационными входами регистров 13 блока 11 памяти.

У вЂ” микрооперация, разрешающая запись сформированного на информационном входе блока

11 памяти кода в N-1 разряды регистров 13; — микрооперация разрешения записи следующей лексической единицы в регистр 2 (для второго канала — в регистр 6); — микрооперация, разрешающая сдвиг содержимого регистров

13 блока !1 памяти на один разряд влево; — микрооперация, формирующая на входе блока 4 микропрограммного управления сигнал г

X (Х вЂ” для второго кана8 8 ла), означающий,, что при предварительной свертке входного выражения в канале обнаружена ошибка;

У8 — микрооперация, разрешающая сдвиг содержимого регистров

13 блока 11 памяти на один разряд вправо.

Сигналы микроопераций У4 и У8 подаются на первые входы соответственно четвертого и пятого элементов ИЛИ блока 9, выходы которых подключены к входам разрешения записи и сдвига вправо блока 11 памяти. Сигнал микрооперации У< подается на вход разрешения сдвига влево блока 11 памяти.

Y - микрооперация, формирующая на входе блока 4 микропрограммного управления сигнал

I 2

Х7 (Х вЂ” для второго канала), означающий нормальное завершение предварительной свертки части входного выражения в канале.

Дешифратор 5 полуоснов предназначен для выделения основ, составляемых из полуоснов, содержащихся в (N-1)-м и Я-м разрядах блоков 11 памяти первого и второго каналов синтаксического анализа.

Блок 4 микропрограммного управления управляет работой устройства в целом, в частности, после того как

1396146

15

XA =, 1, если пред.варительная свертка части входного выражения в первом (во втором) канале завершилась нормально;

g в противном случае;

1, если при предваритель"ной свертке части входного выражения в первом (во втором) канале обнаружена ошибка;

И, в противном случае;

:X (Х ) 30

1, если в (N-2)-м, (n-1)-м и N-м разрядах блока 11 памяти первого (второго) ка-" нала содержится основа

ItF % FII „ ф, в противном случае;

x, (х,)= ( (1 9 1 9

Yz

35 Г!1

1, если в (N-l)-м и N-м разрядах блока 11 памяти первого канала содержатся 40 коды лексических единиц

"gF™9 а в (N-1)-м и М-м разрядах блока ll памяти второго канала — коды "Vg" или если в (N-l)-м и И-м 45 разрядах, блока 11 памяти первого канала содержатся коды 1 2411, а B (И-1)-м и

Н-м разрядах блока 11 памяти второго канала — коды 50

"gF", где "9" -- код произвольной лексической единицы, 9, в противном случае; (6 (YÄ, х, если (М-1)-м и И-м разрядах. блока 11 памяти первого канала содержатся коды yF"., а в (И-1)-и и

N-м разрядах блока 11 па55 и завершена предварительная свертка частей выражения в каналах 3 и 8 синтаксического анализа. . Алгоритм функционирования блока 4 описан блок-схемой (фиг. 5), где

I (2 входные сигналы Х „X» Х и Х,, Х ;, а (Х 11 формируются соответственно первым и вторым каналами синтаксического анализа, а Х„, Х„, Х,, — дешифратором 5 полуоснов.

На выходе блока 4 микропрограммного управления генерируются сигналы

Микроопераций YI -Y«9 Y,9 -Y<< 9 17

Содержательный смысл перечисленнык входных и выходных сигналов след ующий а мяти второго канала — полуоснова "F+ или в (N-1)-м и N-м разрядах блок.а 11 памяти первого канала содержатся коды " Р(", а в (N-l)-м и И-м разрядах блока 11 памяти второго каканала — полуоснова ")F

9 в противном случае;

1, если в (N-1)-м и N-м разрядах блока 11 памяти первого канала содержится полуоснова "F411, а в (N1)-м и N-разрядах блока

11 памяти второго канала— полуоснова "9F(1 или в (N-1)-м и N-м разрядах блока 11 памяти первого канала содержится полуоснова "(F", à B (N-1)-м и

И-м разрядах блока 11 памяти второго канала— полуоснова "Ч)";

9 в противном случае; микрооперация, разрешающая сдвиг вправо на один разряд содержимого регистров

l3 блока 11 памяти первого (второго) канала;

Y, — микрооперации, испольУ ) зуемые для формирования кода лексической единицы "F" на информационном входе блока

ll памяти первого (второго) канала;

) — микрооперация, разрешающая запись сформированного на информационном входе блока

11 памяти кода в N-1 разряды регистров 13 первого (второго) канала; — микрооперация формирования признака ошибочногоо з ав ершения контроля устройством; — микрооперация формирования признака нормального завершения контроля устройством; микрооперация формирования на входах блоков 10 микропроl 396146 граммнбго управления первого и второго каналов входньгх сигналов нходньж сигналов завершения цикла работы устройства {Х<о ).

Сигналы микроопераций У,<, YIz, У, (Y „, Y У.< ) поступают на вторые входы первого, второго и третье- 10 го элементов ИЛИ блока 9, выходы которых соединены с информационными входами регистров 13 блока 11 памяти первого (второго) канала.

< <

Сигналы микроопераций У<„ и У< 15 (Y <о и Y< ) подаются на вторые входы

2 2 соответственно пятого и четвертого элементов ИЛИ блока 9, выходы которых подключены к входам разрешения сдвига вправо и записи блока 11 памяти пер- 20 вого (второго) канала.

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

Исходное выражение перед началом работы делится в произвольном месте 25 на две примерно равные части. Левая (правая) часть исходного выражения справа дополняется признаком конца ф ", правая (вторая) часть выражения слева дополняется признаком "«. ". 30

Лексические единицы левой части исходного выражения поступают в регистр 1 текущего символа слева направо, лексические единицы правой части — в регистр 6 текущего символа справа влево, т.е. с конца выражения.

После включения устройства блок 4 микропрограммного управления анализирует входные сигналы нормального 40 завершения свертки части входного выI ражения в первом канале (Х< ), ошибочного завершения свертки части входного выражения в первом канале (Хв ), нормального завершения свертки45 во втором канале (Х2 ), ошибочнОго завершения свертки во втором канале (X«).

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

Хт K Х-< Ч Х7 3 Х Ч Х 3< Х< Ч Х 3< Х8

Перечисленные входные сигналь< блока 4 микропрограммного управления формируются блоками 10 микропрограммного управления каналов синтаксического анализа по завершении предварительной свертки частей входного вы— ражения.

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

Блок 1 0 микропрограммного управления генерирует микрооперации формирования кода признака начала выражения

Я (У„ ) и разрешения записи сформированного кода в N-й разряд блока

ll памяти (Х4)

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

5 очередной лексической единицы в регистр 1 текущего символа. На выходе дешифратора 2 лексических единиц формируются входные сигналы признаков лексических единиц канала, являющиеся входами блока 10 микропрограммного управления (Х -Х ). Если на выходе дешифратора 2, соответствующем поступлению на его вход признака конца выражения "g ", формируется сигнал (Х, ) то блок 10 микропрограммного управления вьщает микрооперацию признака нормального завершения предварительной свертки части входного выражения в канале (Y ). Эта микрооперация, формирующая входной сигнал признака нормального завершения работы первого канала (Х1 ) блока 4 микропрограммного управления, выдается блоком 10 микропрограммного управления в каждом последующем такте до тех пор, пока блок 4 микропрограммного управления не выдаст микрооперацию завершения цикла работы устройства (Y« ), формирующую входной сигнал (Х, ) блока

10 микропрограммного управления. При этом генерация микрооперации Y > прекращается и блок 10 микропрограммного управления завершает работу (возвращается в исходное состояние).

Если очередная лексическая единица на входе дешифратора 2 не есть признак конца выражения "ф ", то блок 10 микропрограммного управления вьщает мик9 1396146 !о рооперацию, разрешающую сдвиг влево иа оцин разряд содержимо. о блока 1! памяти (У6), освобождая тем самым старший N-й разряд блока памяти для

5 записи кода очередной лексической единицы.

Если очередная лексическая единица на входе дешифратора 2 есть "(", то

На его выходе, соответствующем при=-- !О

Яаку открывающей скоб к и, фо рм ируе т ся сигнал (Х ), запускающий выдачу в блоке 10 микропрограммного управления чикроопераций формирования кода "(" (Y ) и разрешения записи в N-й разряд 1 блока 11 памяти (Y,,) ..

Если очередная лексическая единица

На входе дешифратора 2 есть операнп, ro на его выходе-, соответствующем

1 ризнаку операнда, формируется сигнал (Х ), запускающий н блоке 10 микропрограммного управления выдачу мик—

Э коопераций формирования кода F" (Y,, Yq) и разрешения записи сформиро-! ванного кода в N-й разряд блока 11 памяти (Y,).

Если очередная лексическая единица на входе дешифратора 2 есть знак операции, то на его выходе, соответrВующем призна«у ОГ! epации фоpr!иру ется сигнал (Х ), запускающий в блоке 4 микропрограммного управления выдачу микрооперации формирования кода (Y ) и разрешения .- аписи сформированного кода в К-й разряд блока 11 памяти (Y ).

Если очередная лексическая единица на входе дешифратора 2 есть ")", то на его выходе, соответствующем .признаку закрывающей скобки; формируется сигнал (Х ), запускающий н блоке 10 микропрограммного управления выдачу микроопераций формирования кода ")" (Х,, У ) и разрешения записи сформированного коца в N-й разряд

45 блока 11 памяти (Y<) .

После записи кода очередной лексической единицы в блок 11 памяти в блоке 1 0 микропрограммного управления анализируется входной сигнал .,Х6), формируемый дешифратором 1? ос- 0 ион. Если в (11-2)-м, (Б-1)-м и N-м разрядах блока 11 памяти содержатся коды лексических единиц, образующих основу "I F" или основу "(F)", то

Hé выходе дешифратора формируется сигнал (Х„) признака основы, который запускает н блоке 10 микропрограммного управления последовательность микроопераций, осуществляющих свертку основы, т. е. замену основы кодом операнда "F"1. .Свертка осуществляется пу— тем выдачи блоком )0 микропрограммного управления микроопераций дважды разрешения сдвига на один разряд вправо содержимого регистров 13 бло11 памяти (Ув H Уь), формирования кода операнда. "FЯ на информационном входе блока 11 памяти (У,, У, Y ) и разрешения записи сформированного кода в N-й разряд блока 11 памяти (У,!). После этого блоком 10 микропрограммного управления проверяется значение входного сигнала признака

ocHoBbt (Х ). IIpH наличии cHT HBJIB (Х ) признака основы на выходе дешифратора 12 основ блоком 10 микропрограммного управления снова выдаются микрооперации, осуществляющие свертку основы, содержащейся в трех старших разрядах блока 11 памяти. При отсутствии сигнала признака основы (Х ) на выходе дешифратора 12 блок 10 мик-. ропрограммного управления переходит к обработке очередной лексической единицы входного выражения.

Если очередной символ входного выражения не является допустимой лексической единицей, то сигналы на выходах дешифратора 2 (Х,-Х ) отсутствуют. При отсутствии входных сигналон признаков лексических единиц (Х, -Х ) блок 10 микропрограммного управления выдает микрооперацию признака ошибочного завершения предварительной свертки части исходного выражения в канале (Y,). Указанная микрооперация, формирующая входной сигнал признака ошибочного завершения работы канала (Х ) блока 4 микропрограммного управления, выдается блоком 10 микропрограммного управления в каждом последующем такте до тех пор, пока блок 4 микропрограммного управления не выдаст микрооперацию завершения цикла работы устройства (У, ), формирукщую входной сигнал (Х ® ) блока 10 микропрограммного управления. После этого генерация микрооперации У прекращается и блок

10 микропрограммного управления завершает работу.

Окончательная свертка входного выражения производится под управлением блока 4 микропрограммного управления. При этом в результате предварительной свертки частей вход139Ь!46 ного выражения в каналах синтаксического анализа длина анализируемого выражения существенно уменьшена, что обеспечивает повышение быстродейст5 вия устройства.

Блок 4 микропрограммного управления продолжает анализировать формируемые блоками 10 микропрограммного управления каналов признаки нормаль- 10 ного (Х и X, ) и ошибочного (Х, и

Х ) завершения предварительной свертки части входного выражения до тех пор, пока не завершится работа обоих каналов. !5

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

ХЗХvXI|,XvХКХ

25 блок 4 микропрограммного управления выдает микрооперации признака ошибочного завершения контроля (Y ) и формирования (Y „10 микропрограммного управления первого З0 и второго каналов сигнала завершения цикла работы устройства (Х „ ). На этом цикл работы устройства завершается.

В случае нормального завершения

35 предварительной свертки частей входного выражения в обоих каналах, т.е. иа входе блока 4 микропрограммного ( управления сформированы первым (Х ) и BTopb(M (Х ) каналами cHI" налы нор 40 г мального завершения предварительной свертки, блок 4 микропрограммного управления выполняет цикл микроопераций по окончательной свертке частей входного выражения.

Если на выходе дешифратора 5 полуоснов формируется сигнал (Х „ ), соответствующий наличию на входах дешифратора составляющих завершающего выражения, т.е. в (N-1)-м и N-м разрядах блока ll памяти первого канала содержатся коды lIgF1l а в Б-м . разряде блока 11 памяти второго канала — код "g", или в N-м разряде блока 11 памяти первого канала содержится код "g(а в (N-1)-м и N-м разрядах блока 11 памяти второго канала— коды "g", то в блоке 4 микропрограммного управления выдаются микрооперации признака нормального за вери(е(п(я контроля (1 (b ) и формирования (Y „) на входах блоков 10 микро(рограммного управления первого и второго каналов сигнала завершения цикла работы устройства (Х, ). На этом цикле работа устройства завершается. Устройство готово к следующему циклу синтаксического анализа.

Если на выходе дешифратора 5 полуоснов формируется сигнал (Х, ), означающий наличие на его входах полуоснов, образуемых содержащимися в (N-1 )-м и N-м разрядах блока !1 памяти первого канала кодами "F«" и в М-м разряде блока 11 памяти второго канала кодом "F или содержащимися в (N-1)-м и N-м разрядах блока

11 памяти первого канала кодами "(F и в N — м разряде блока 11 памяти второго канала кодом "(", то блоком 4 микропрограммного управления выдаются микрооперации сдвига вправо на один разряд содержимого блоков !1 ! 2 памяти первого (У, ) и второго (Y, ) каналов, формирования кода операнда

"F(на информационном входе блока !1 памяти первого канала (Y „, Y,, Y ) и разрешения записи сформированного кода в N-й разряд блока 11 памяти первого канала (Y ). Затем блок 4 (( микропрограммного управления снова анализирует состояние выходных сигналов дешифратора 5 полуоснов.

Если на выходе дешифратора 5 полуоснов формируется сигнал (Х, ), означающий наличие на его входах полуоснов, образуемых содержащимися в N-м разряде блока 11 памяти первого канала кодом "F" и в (N-1)-м и N-и разрядах блока 11 памяти второго канала кодами "F« H o ep ((tHMHc N-м разряде блока 11 памяти первого канала кодом "{" и в (N-l)-м и N-м разрядах блока ll памяти второго канала кодами ")F" то блоком 4 микропрограммного управления выдаются микрооперации сдвига вправо на один разряд содержимого блоков 11 памяти первого (1, ) и второго (У „,) каналов, формирования кода операнда "F" на информационном входе блока 11 памяти второго канала (Х „, Y,, Y, ) и раз-.

2 2 2 решения записи сформированного кода в N-й разряд блока 11 памяти второго канала (Y() . г

Таким образом производится свертка основ вида "F+ F или "(F(" o6—

139б1 раэованных содержащимися в блоках ll памяти первого и второго каналов полуосновами, т.е. замена основы кодом операнда Р".

После свертки составной основы блок 4 микропрограммного управления снова анализирует выходные сигналы дешифратора 5 полуоснов.

Если на выходах дешифратора 5 сиг- 1О

HGJlbl (Х f2 и Х ) oTc 7TcTB T у что Означает отсутствие в блоках 11 памяти

:каналов полуоснов,, составляющих сворачиваемую основу,, то блок 4 микролрограммного управления анализирует

: выходные сигналы дешифраторов 12 Ос нов первого (X ) II »Toporo (Х ) каналов.

Если на выходе дешифратора 12 ос:нов первого канала формируется сигнал 2О

:(X> ), означающий напичие в (Ь-2)-м (N-1)-м и N-м разрядах блока 11 паияти первого канала кодов, образующих основу "Р » F"., то блоком 4 микропрограммного управления выдаются и микрооперации сдвига дважды на один разряд вправо содержимого блока 11 памяти первого канала (Y и, ) ! т.е. производится свертка основы nyff If тем замены ее кодом операнда F

Если на выходе дешифратора 12 основы второго канала формируется сигнал (Х ), означающий чаличие в (И-Z)-м, (И-1)-м и N--м разрядах блока 11 памяти второго канала кодов, об-разующих основу "F «- Г", то блоком микропрограммного управления выдаются микрооперации сдвига дважды на один разряд вправо содержимого блока

2 2

11 памяти втоРого канала (Y, и Y„) ., 4О т. е. производится свертка основы.

После свертки основы блок 4 микропрограммного управления снова анализирует выходные сигналы дешифратора.

5 полуоснов (X„, Х „и Х,> ) и деl шифраторов 12 основ первого (Х9) и ,г второго (Х ) каналов °

Если при очередном анализе входьых сигналов блока 4 микропрограммного управления возникает ситуация, когда одновременно отсутствуют сигналы, формируемые дешифратором 5 полуоснов (Х „, Х 12 и Х д ) и дешифраторами 12 осНоВ первого (Х9 ) ll втОРОГО (Х9 ) каналов, что означает отсутствие в блоках ll памяти пер»ого и второго

55 каналов сворачиваемых основ, то блок

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

4б 14 завершения контроля (Yt< ) и формирования (Yö ) на входах блоков 10 мик-ропрограммного управления первого и второго каналов сигналов завершения цикла работы устройства (X„ ). На этом цикл работы устройства заверша— ется.

Устройство готово к следующему циклу синтаксического анализа, Пример I. Пусть входное выражение имеет вид (а + (Ь + с + (d. + 1 х 6) +

+g+Ь))

Внешним устройством данное выражени е делит ся в пр о из в оль ном ме с те на две части. Каждая часть помечается признаком конца "Ф".

1) (а, + (Ь + с + (+

2) 41 х Я-)+ g + 11))

На вход первого канала подается левая (первая) часть исходного выражения. На первом шаге в И-й разряд блока ll памяти заносится код признака начала выражения "g".

На следующих шагах содержимое блока 11 памяти первого канала формируется следующим образом.

Входная лекси- Содержимое блока ческая единица ll памяти первого канала

8(F ф(н»

g(F » (8(F (1

8(F (Е:

g(F »(» Е

На этом шаге дешифратором 12 ос— нов формируется сигнал (Х 6), означающий, что в (N-2)-м, (N-1)-м и N-M разрядах блока 11 памяти первого канала находится основа. Этот сигнал (Х6) запускает в блоке 10 микропрограммного управления последовательность микроопераций, осуществляющих свертку основы, дважды сдвиг содержимого блока 11 памяти вправо (Уff и Уs,f, 1396146

Содержимое блока

11 памяти первого канала формирование кода "F" на информационном входе блока 11 памяти (Y . Y

Y ) и разрешение записи сформированного кода в N-й разряд блока 11 па5 мяти (Yg) ° В результате свертки в блоке 11 памяти первого канала содержится выражение "g(F «(F ".

Дальнейшая обработки левой части выражения производится следующим образом:

Входная лексическая единица

8((F«

8((F>(g((F«(F

8((F«(F« ф((F«(F+1 х

llроизводится свертка основы:

8(F«(F+

g(F«(F«( (г+(Р «(г

+ 8(г«-((г+ и

При поступлении на вход дешифрато- 25 ра 2 лексических единиц признака

И -Д- t1 конца части выражения У на его выходе формируется сигнал (Х, ), который запускает в блоке 1 О мик р опрограммного управления выдачу микро операции 30 (Y ), формирующей в блоке 4 микропрогpBMMHQI о управления сигHBJI. (Х ), означающий нормальное завершение предварительной свертки части входного выражения в первом канале. 35

Работа второго канала синтаксического анализа производится параллельно с работой первого канала. На вход регистра 6 текущего символа подается 40 правая часть выражения посимвольно справа налево.

Формирование содержимого блока 11 памяти второго канала происходит в следующем порядке ° 45

Входная лекси- Содержимое блока ческая единица 11 памяти второго канала

g((F«

8((1 производится свертка основы:

Ф

fl

Конец работы второго канала, Иа выходе декифратора.7 лексических единиц, означающем поступление на его вход признака конца части входного выражения иФ., формируется сигнал (Х,), запускающий в блоке 10 микропрограммного управления выдачу микрооперации (Y ), формирующей в блоке 4 микропрограммного управления сигнал (X ), означающий нормальное завершение предварительной свертки части входного выражения во втором канале.

Входные сигналы, поступившие на блок 4 микропрограммного управления из первого (Х, ) и второго (Х, ) каналов, вызывают переход. блока 4 на ачализ входных сигналов, формируемых дешифратором полуоснов (Х «, X<<, Х,q ) и дешифраторами основ каналов (Х,, и Х ).

1I0 завершении предварительной . свертки частей входного выражения содержимое блока 11 памяти первого канала ф(Р«(У«(Р«" содержимое блока

11 памяти второго канала: "ф((Р+(Р

На вход дешифратора 5 полуоснов поступают иэ первого канала коды

"F«" из второго канала - коды (Р".

B соответствии со значениями входных сигналов дешифратор 5 полуоснов формирует сигнал (Х, ) на входе блока

4 микропрограммного управления, разрешающий в указанном блоке выдачу микроопераций сдвига вправо содержимого блока 11 памяти первого (Y, ) и

1 второго (Y, ) каналов, формирования на информационном входе блока 1! па/ мяти первого кода операнда F (Y«

Y,, Х, ) и разрешения записи сформи-! рованного кода в N-й разряд блока 11 памяти первого канала (7,,! ).

1396146

Содержимое блока 11 памяти первогс канала становится равным "ф(Г -(Г a(F содержимое блока 11 памяти второго канала — "Ф((F<(".

Содержимое блока Формируемые сигналы

11 памяти второго канала

g(F (I «(1

8(I (1«1

g(F (F «

8(I"+(I"

8((F+(8((F

8((F

g>(F

На выходе дешифратора 5 нолуоснов сформирован сигнал (Х,„), соответствующий наличию на вхоцах дешифратора

Завершающего выражения, т. е. в ¹1-м

30 и N-м разрядах блока 11 памяти первого канала содержатся коды gF а и

If-м разряде второго канала — код "g", В блоке 4 микропрограммного управления сигналом (Х я } запускаются микро- З5

Операции признака нормального заверщения контроля (Уп, ) и формирования (Yд ) на входах блоко.в 10 микропрограммного управления первого и второго каналов сигнала завершения цикла

40 работы устройства (Х „> ) .

8((F

g((F

g((F4tF

Свертка основы

"р г" 0((г

На этом работа устройства завершается.

Пример 2, Пусть исходное выражение имеет вид: ((a + b) х с +

+Йх1.

Выражение содержит ошибку — отсут"твует закрывающая скобка.

8((F) 45

Свертка основы

tt(F) ll g(F

В первый канал подается левая часть выражения: . ((а + д} х ф Во второй канал посимвольно оправо налево подается правая часть выражения

pc+ йх1 55

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

Содержимое блока 11 памяти первого канала

Дальнейшая обработка входного вь: ражения производится следующим образом:

Деш.5: Х„

Деш.5: Х, Деш.S: Х, деш.5: Х, К нал: Х

Деш. 5: Х, Деш.5: Х„

Первый канал

Входная лекси- Блок 11 памяти ческая единица

Дешифратор 2 лексических единиц формирует сигнал (Х,), в соответствии с которым блок 1О микропрограммного управления выдает микрооперацию (У ), формирующую на входе блока

4 микропрограммного управления сигнал (X, ), означающий нормальное завер1396146

Свертка основы х 1 1"

Свертка основы

Я1 +1 II

gF

Содержимое блока Содержимое блока Формируемые

11 памяти первого 11 памяти второго сигналы канала канала

8(F« шение предварительной свертки входного выражения в первом канале.

Второй канал

Входная лекси- Блок 11 памяти ческая единица

При поступлении на входы дешифратора 5 полуоснов из первого канала

"g(" из второго канала — кода пфп сигналы на выходе дешифратора (X„—

X ) отсутствуют. Сигналы на выходах

13

I дешифраторов 12 основ первого (Х ) и второго (Х ) каналов также отсут7 ствуют, так как. коды, содержащиеся в старших разрядах блоков ll памяти, не образуют основу вида "F+F, Блок 4 микропрограммного управления при отсутствии перечисленных входных сигналов выдает микрооперации формирования признака ошибочного завершения контроля (Y« ) и формирования на входах блоков 10 микропрограммного управления первого и второго каналов входных сигналов завершения цикла работы устройства (Х„ ).

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

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

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

Окончательная свертка происходит под управлением блока 4 микропрограммного управления в следующем порядке: мяти,отличающееся тем, что, с целью повышения быстродействия, в устройство введены первый и второй дешифраторы лексических единиц, дешифратор полуоснов, а в каждый канал синтаксического анализа введены блок элементов ИЛИ, дешифратор основ и блок микропрограммного управления, причем информационные выходы первого и второго регистров текущего символа соединены с входами соответственно первого и второго дешифраторов лексических единиц, выходы которых соединены с входами логических условий блока микропрограммного управления соответствующего канала синтаксического анализа, первые выходы микроопераций блока микропрограммного управления первого и второго каналов соединены с входами записи соответственно первого и второго регистров текущего символа, второй выход блока микропрограммного управления каждого канала синтаксического анализа соединен с первым вхбдом блока элементов ИЛИ, выход которого соединен с входом записи блока памяти канала синтаксического анализа, первый и второй выходы блока микропрограммного управления соединены с вто1396! 46

10

pblMH входами блоков злементов ИЛИ соответственно первого и второго каналов синтаксического анализа, первые выходы дешифраторов основ каналов синтаксического анализа соединены соответственно с первым и вторым входами логическйх условий блока микропрограммного управления, третьи выходы блоков микропрограммного уп- равления каналов синтаксического анализа соединены соответственно с третьим и четвертым входами логических условий блока миKpoпрограммного управления, первые информационные выходы блоков памяти каналов синтаксического анализа соединены соответственно с первым и вторым информационными входами дешифратора полуоснов, выход которого соединен с пятым входом логических условий блока микропрограммного управления, второй выход блока памяти каждого канала синтаксического анализа соединен с информационным входом дешифратора основ, второй выход которого соединен с вторым входом логических условий блока микропрограммного управления канала синтаксического анализа. 396I 46

ga У rO 6

l 396146! 396! 46

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

Редактор А. Лежнина Техред М.Дидык Корректор .Пожо

М.Пожо

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

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

П оектная 4