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

F

Ж

7

СО СО О5

4;

05

фиг.

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

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

На фиг, 1 представлена структур- ная схема устройства для синтакси- NecKoro контроля; на фиг, 2 - струк- И: урная схема канала синтаксического ;анализа; на фиг„ 3 - структурная :ма блока памяти; на фиг 4 - блок-схема микропрограммного управления jKajiajioM синтаксического анализа; на :фиг 5 - микропрограммно- :го управления устройства в целом, : Устройство для синтаксического контроля (фиг, О содержит первый :регистр текущего символа, первый ;дешифратор 2 лексическшс единиц, перв1,й канал 3 синтаксического ана- ьииза, блок 4 микропрограммного управ ;ления, дешифратор 5 полуосков,, вто- рой регистр 6 теку1це1: о символа, второй де .шифратор 7 .лексичеOKI-DC и второй канал 8 синтаксического ана - лиза о

Канал синтакси ч;ес;хог() ангьчиза :(фиг;2) содержит блок 9 элементов ИЛИ. блок 0 микропрограммного управления, :блок 11 памяти и дешифра | Ор 12 основ

В состав блока 11 памяти (фиг. З) входит 13 .из трех реверсивш.гх сдвиговых регистров«

Регистры 1 и 6 текущего символа используются для хранения очередньпс j eKCH4:ecKHX единиц частей исходного выражения

Дешифрач оры 2 :и 7 вьщеля.ют из лексических единиц исходного выражения операнды операции, скобкид а также признаки начала и конца вырая-сения. При этом отличие :в подключенрш груп- пь выходов дешифратора 7 к группе . входов признаков лексическр1х единиц канала 8 от подключения группы выходов дешифратора 5 к группе входов признаков лексиче ;ки/с единиц канала 3 заключается в том, что выход дешифратора 7, означающий постунление на вход деишфратора лексической еди- НИЩ1 ( подключается к входу признака лексической единицы ) канадца 8, вьтход деишфратора 7, означающий поступление на вход дешифратора лексической единицы ) - к входу признака лексической единицы ( а выход дешифратора 5, означающий постунление на вход дешифратора лексичес- кой единицы (j подключается к входу признака лексической единицы ( канала 3, выход дешифратора 5, означающий поступление на вход дешифратора лексической единицы ) - к входу

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

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

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

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

Блок 11 памяти - это память с посг. ледовательньи безадресшзМ принципом записи и чтения с обеспечением возможности доступа для чтения одновременно к нескольким старшим разрядам.

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

Реверсивные сдвигающие регистры 13 блока 11 памяти осуществляют за-

пись кодов лексических единиц в старшие N-1 разряды5 хранение записанной информации, поразрядньш сдвиг содержимого .вправо или влево, а также выдачу записанной информации из (N-2)-X

(W-l)-X и И Х разрядов на дешифратор 12 основ при предварительной свертке частей исходного выражения в каналах или из (N-l)-X и 1-Х разрядов на дешифратор 5 полуоснов при окончательной свертке выражения.

Блок 10 микропрограммного управления управляет работой всех элементов канала,

На фиг о 4 приведена блок-схема

функционирования блока, где входные сигналы Х,-Х5 формирует дешифратор 2 (для второго канала - дешифратор 7) лексических единиц, Х - дешифратор

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

Y Y J- g , 9

3- 13961

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

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

М-

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

0,в противном слз чае ;

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

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

операции;

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

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

, если в разрядах (N-2), (Н-1) ,и N блока 11 памяти содержится основа F F или (F);- 0, в противном случае;

20

30

25

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

Y - микрооперации, используемые для формирования кодов лексических единиц на информационном входе блока 1 памяти;

-микрооперация, соответствующая коду лексической единицы s начала части выражения;

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

- совокупность микроопераций, соответствукщая коду лексической единицы ) - скобка закрьшаинцая;

- микрооперация, соответствующая коду лексической единицы « - знак операции;

Y,j , совокупность микроопераций, соответствующая коYig

46

ду лексическои единицы Р - операнд.

Сигналы микроопераций У, , Y, , Y, поступают на первые входы первого, второго и третьего элементов ШШ блока 9, выходы которых соединены с информационными входами регистров 13 блока 11 памяти.

0

0

5

Y - микрооперация, разрешающая запись сформированного на информационном входе блока 11 памяти кода в N-1 разряды регистров 13;

У - .- - микрооперация разрешения

записи следующей лексической единицы в регистр 2 (для второго канала - в регистр 6);

Y - микрооперация, разрешающая сдвиг содержимого регистров 13 блока 11 памяти на один разряд влево;

Y, - микрооперация, формирующая на входе блока 4 микропрограммного управления сигнал х1 (Х„ - для второго кана ч 8

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

Yg - микрооперация, разрешающая сдвиг содержимого регистров 13 блоки. 11 памяти на один разряд вправо. g Сигналы микроопераций Y и Yg подаются на первые входы соответственно четвертого и пятого элементов ИЛИ блока 9, выходы которых подключены к входам разрешения записи и сдвига 0 вправо блока 11 памяти. Сигнал микрооперации Y подается на вход разре- сдвига влево блока 11 памяти. Yg - микрооперация, формирующая на входе блока 4 микропро- 5 граммного управления сигнал Х (Х - для второго канала), означающий нормальное завершение предварительной свертки части входного вы- Qражения в канале.

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

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

завершена предварителъная свертка частей выражения в кангшах 3 и 8 синтаксического анализа.

Апгоритм функционкрования блока А описан блок-схемой (фиг. 5), где входные сигналы Xj, Xg, Х и Х , Xj; , Хо формируются соответственно первым и вторым каналами синтаксического (анализа, а Х„ , , Х,, - дешифра- тором 5 полуоснов.

; На выходе блока 4 микропрограммного управления генерируются сигналы Микроопераций l , -У , Y -УД , Y,y

I Содержательный смысл перечисленных входных и сигналов еле- рукшдай;

1J.если предварительная

свертка части входного вы- ражения в первом-(во вторс:

(х ),

ром) канале завершилась

нормально;

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

25

30

35

40

1S если при предварительной свертке части входного /выражения в первом (во вто- 8 8 Vpow) канале обнаружена

ошибка; 05 в противном случае;

1, если в (№-2)-м, (N-l)-M

и N-M разрядах блока 11 па- о (Хо)-/мяти первого (второго) канала содержится основа F

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

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

.коды лексических единиц $F, а в (N-l)-M и N-M разрядазс блока 11 памяти второго канала - коды V5, или если в (N-1)-м и N-M 45 разрядах блока 11 памяти первого канала содержатся коды 0, а в (N-i)-M и N-M разрядах блока 11 памяти второго канала - коды 50 F, где код произвольной лексической единшдыу 0, в противном случае;

, если (N-1)M и N-M разрядах.блока П памяти 55 первого канала содержатся коды YF. а в (N-1)-м к N-M разрядах блока 11 па,

Х t }

д

5

п

0

5

0

5

0

5 0

5

yV (Y )

(n V - In

10

10

Y / (I

(и

. э у2 IZ

И

(Y)

М5

16

мяти второго канала - по- луоснова F или в (N-l)-M и N-M разрядах блока 11 памяти первого канала содержатся коды М , а в (N-)-M и N-M разрядах блока 11 памяти второго ка- канала - полуоснова )

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

1,если в (N-l)-M -и N-M разрядах блока 11 памяти первого канала содержится полуоснова F-x, а в (N1)-м и N-разрядах блока 11 памяти второго канала- полуоснова Г ,или в (N-l)-M и N-M разрядах блока 11 памяти первого канала содержится полуоснова (F, а в (К-1)-м и N-M разрядах блока 11 памяти второго канала - полуоснова ); 0, в противном случае;

микрооперация, разрешающая сдвиг впра- во на один разряд со держимого регистров 13 блока 11 памйти первого (второго) канала;

У, з - микрооперации, исполь - Y Jj) зуемые для формирования кода лексической единицы F на информационном входе блока 11 памяти первого (второго) канала;

-микрооперация, разрешающая запись сформированного на информационном входе блока 11 памяти кода в N-1 разряды регистров 13 первого (второго) ка. нала;

-микрооперация формирования признака ошибочного завершения контроля устройством;

-микрооперация формирования признака нормального завершения контроля устройством;

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

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

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

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

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

справа влево, т.. е. с конца вьфажения.

После включения устройства блок 4 микропрограммного управления анализирует входные сигналы нормального завершения свертки части входного выражения в первом канале (Уi ), ошибочного завершения свертки части входного выражения в первом канапе .(Xg ), нормального завершения свертки во втором канале (Xg ), ошибочного завершения свертки во втором канапе ( }

1 л я J .

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

х; & х; V х & V х Лх V х 1 Xg

0

5 0

5 О

5

Q

0

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

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

Блок 10 микропрограммного управления генерирует микрооперации формирования кода признака начала выражения (Y ) и разрешения записи сформированного кода в N-й разряд блока 11 памяти (Y).

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

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

Если очередная лексическая единица на входе дешифратора 2 есть (, то На его выходе, соответствующем приз- Наку открывающей скобки, формируется сигнал (Xj)5 запускающий выдачу в блоке 10 микропрограммного управления | икроопераций формирования кода ( ) и разрешения записи в N-й разряд 0лока П памяти (Y,,}.

; Если очередная лексическая единица на входе дешифратора 2 есть операнд,, iro на его выходе-, соответствующем |1ризнаку операнда, формируется сиг- 1ал (Xj), запускароций в блоке 10 мик;эопрограммного управления выдачу мик- ;:)Оопераций формирования кода г (Y, , Tj, Y) и разрешения записи сформиро- |занного кода в М-й разряд блока 1 1 Памяти (Y ,,).

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

Если очередная лексическая единица на входе дешифратора 2 есть ), то на его выходе, соответствующем

признаку закрывающей скобки форми/,г -

руется сигнал IX I, запускаю1ции в

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

После записи кода очередной лексической единицы в блок i1 памяти в блоке 0 микропрограммного управления анализируется входной сигнал (Х), формируемьи дешифратором 12 основ. Если в (К-2)-м, (N-l)-M и N-M разрядах блока 11 памяти содержатся коды лексических единиц, образуюшд-гх основу F Р или основу (F), то на выходе дешифратора формируется сигнал (Х) признака основы, который ;}апускает в блоке 10 микропрограммно- 1 о управления последовательность мик

j

0 5

„

и

5

5

5

роопераций, осу1цествляю1чих свертку основы, т.е. зг1мену основы кодом опе- равда F. Свертка осуществляется путем выдачи блоком 10 микропрограммного управления микроопераций дважды разрешения сдвига на один разряд вправо содержимого регистров 13 блока 1 памяти (Yg и Yg), формирования кода операнда- F на .информационном входе блока 1 памяти (Y, , Y, Y,) и разрешения записи сформированного кода в N-й разряд блока 1 памяти (Y), После этого блоком 10 микро- програ)много управления проверяется значение входного сигнала признака основы (Xg). При наличии сигнала (Xg) признака основы на выходе дешифратора 12 основ блоком 1 О микропрограммного управления снова вьщаются микрооперации, осуществляющие свертку основы, содержащейся в трех старших блока 11 памяти. При отсутствии сигнала признака основы (Xg) на выходе дешифратора 12 блок 10 микропрограммного управления переходит к обработке очередной лексической единицы входного выражения.

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

Окончательная св.ертка входного выражения производится под управлением блока 4 микропрограммного управления. При этом в результате предварительной свертки частей входного выражения в каналах синтаксического анализа длина анализируемого выражения существенно уменьшена, что обеспечивает повышение быстродейст- ВИЯ устройства.

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

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

Х , I Xg V Xg i Х V Х g X

г

8 f

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

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

Если на выходе дешифратора 5 по- луоснов формируется сигнал (Х4, ), . соответствующий наличию на входах дешифратора составляющих завершакще- го выражения, т.е. в (N-l)-M и N-M разрядах блока 11 памяти первого канала содержатся коды F, а в N-M . разряде блока 11 памяти второго канала - код , или в N-M разряде блока 11 памяти первого канала содержится код , а в (N-l)-M и N-M разрядах блока 11 памяти второго канала - коды 0, то в блоке 4 микропрограммного управления выдаются микроопера

5

0

5

0

5

0

5

0

5

ции признака нормального завершения контроля (YI ) и формирования ( ) на входах блоков 10 микропрограммного управления первого и второго каншюв сигнала завершения цикла работы устройства CX|g ). На этом цикле работа устройства завершается. Устройство готово к следующему циклу синтаксического анализа.

Если на выходе дешифратора 5 полу- осноБ формируется сигнал (X, ), означающий наличие на его входах полуоснов, образуемых содержащимися в (N-lJ-M и N-M разрядах блока 1 памяти первого канала кодами P lf и в N-M разряде блока 11 памяти второго канала кодом F или содержащимися в (W-l)-M и N-м разрядах блока 1 1 памяти первого канала кодами (l и в N-M разряде блока 1I памяти второго канала кодом (, то блоком 4 микропрограммного управления выдаются микрооперации сдвига вправо на один разряд содержимого блоков 11 памяти первого (Yj ) и второго (Y,o) каналов, формирования кода операнда F на информационном входе блока 11 памяти первого канала (Y, , Y, , Y ) и разрешения записи сформированного кода в N-й разряд блока 11 памяти первого канала (). Затем блок 4 микропрограммного управления снова анализирует состояние выходных сигналов дешифратора 5 полуоснов.

Если на выходе дешифратора 5 полуоснов формируется сигнал (Х, ), означающий наличие на его входах полуоснов, образуемых содержащимися в N-M разряде блока 11 памяти первого какала кодом F и в (N-l)-M и N-M разрядах блока 11 памяти второго канала кодами F« или содержащимися в N-M разряде блока 11 памяти первого канала кодом ( и в (N-l)-M и N-M разрядах блока 11 памяти второго канала кодами )F, то блоком 4 микропро- граммного управления выдаются микрооперации сдвига вправо на один раз- . ряд содержимого блоков П памяти первого (Y, P ) и второго (Y fo ) каналов, формирования кода операнда F на информационном входе блока 11 памяти второго канала (Yf, , Y , ) и раз-. решения записи сформированного кода в N-й разряд блока 11 памяти второго канала (Y, ).

Таким образом производится свертка основ вида F F или (F(, об1313961

разованных содержащимися в блоках 11 памяти первого и второго каналов полуосновами, т.е. замена основы кодом операнда F,

После свертки составной основы

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

дешифратора 5 полуоснов.

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

налы (Х., и X,, ) отсутствуют, что 03;Начает отсутствие в блоках 11 памяти |каналов полуоснов., составляющих сво- ;рачиваемую основу., то блок 4 микро- Программного управления анализирует |выходные сигналы дешифраторов 12 ос- |нов первого (Х ) и второго (Х ) ка :налов.

; Если на выходе дешифратора 12 ос- IHOB первого канала формируется сигна КХл ), означающий наличие в (N-2)-M |(N-1 )-м и разрядах блока 1 1 памяти первого канала кодов, образующих основу F F ., то блоком 4 мик- :ропрограммного управления выдаются и iN HKpoonepaij;HH сдвига дважды на один разряд вправо содержимого блока 11 памяти первого канала {У, и У,д ) т.е. производится свертка основы пу- тем замены ее кодом операнда Р. : Если на выходе дешифратора 12 ос- ковы -второго канала формируется сиг- Кал (Х ), означающий наличие в (И- |-2)-м, (N-1)м и N-м разрядах блока ;1 1 памяти второго канала кодов, об |разующих основу , то блоком - микропрограммного управления вьщают- ся микрооперации сдвига дважды на один разряд вправо содержимого

10

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

После свертки основы блок 4 микропрограммного управления снова, анализирует выходные сигналы дешифратора 5 полуоснов (Х, , X,,,, и X ,3 ) и дешифраторов 12 основ первого (Х,) и второго (Х) канаг(ов.

Если при очередном анализе входкзы сигнапо в блока 4 микропрограммного управления возникает ситуация, когда одновременно отсутствуют сигналы, формируемые дешифратором 5 полуоснов (Х„ , X ,2. и X ,j ) и дешифраторами 12 основ первого (Х ) и второго {х| ) каналов, что означает отсутствие в блоках 11 памяти первого и второго каналов сворачиваемьпс основ, то блок 4 микропрограммного управления выдает микрооперации признака ошибочного

0

0 5

0

5

0

5

0

5

завершения контроля (Y(j ) и формирования (Y ) на входах блоков 10 мик- ропрограммного управления первого и второго каналов сигналов завершения цикла работы устройства (Х,д ). На этом цикл работы устройства завершается.

Устройство готово к следующему циклу синтаксического анализа.

Пример I. Пусть входное выражение имеет вид

(а + (Ъ + с + (d + 1 X -6-) + + g + h))

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

1)(а + (Ъ + с + (d + ;

2) X &)+ g + h))

На вход первого канала подается левая (первая) часть исходного выражения,, На первом шаге в N-й разряд блока 11 памяти заносится код признака начала выражения §(.

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

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

канала (

а. (

+ .(Р

((F

b$(F (

+5(F (F

(FV(F

c(F )t(F F

Ha .этом шаге дешифратором 12 основ формируется сигнал (Xg), означающий, что в (N-2)-M, (N-l)-M и N-M разрядах блока 11 памяти первого канала находится основа. Этот сигнал (Хй) запускает в блоке 10 микропрограммного управления последователь- но.сть микроопераций, осуществляющих свертку основы, дважды сдвиг содержимого блока 11 памяти вправо (Уд и Yg)

1513961

. формирование кода F на информационном входе блока 11 памяти (Y, , У , У,) и разрешение записи сформированного кода в N-й разряд блока 11 памяти (У4). В результате свертки в блоке 11 памяти первого канала содержится выражение (F (F ,

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

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

канала

((F«- . (( 0(F(F(F

(F(F(F

#

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

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

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

Входная лекси- Содержимое блока

ческая единица 11 памяти второго

канала

Й(

((

$((F

((F 55((

Производится свертка основы: +((F

) . ((F 5«({F(

6-((Fif(F

(F-){(F«

1 (((

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

.1/, n

0

5 0 ,

0

5

0

5

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

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

(х; и хр.

По завершении предварительной . свертки частей входного выражения содержимое блока 11 памяти первого канала S5(F(F(F содержимое блока 11 памяти второго канала: ((F(F ,

На вход дешифратора 5 полуоснов поступают из первого канала коды F, из второго канала - коды (F,

В соответствии со значениями входных сигналов дешифратор 5 полуоснов формирует сигнал (Х,, ) на входе блока 4 микропрограммного управления, разрешающий в указанном блоке выдачу микроопераций сдвига вправо содержимого блока 11 памяти первого (У ) и второго (у,о) каналов, формирования на информационном входе блока 11 памяти первого кода операнда F (У, , 17 раз.решения записи сформированного кода в N-й разряд блока 11 памяти первого канала (У, ).

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

Дальнейшая обработка входного вь

канала становится равным (F(F(F ражения производится следующим обсодержимое блока 11 памяти второго канала - ((Г(.

разом:

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

канала

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

((F(

((F

((F

0((

(

(

0

На выходе дешифратора 5 полуоснов Сформирован сигнал (Х„ ), соответствующий наличию на входах дешифратора завершающего выражения, т.е, в N-l-M и N-M разрядах блока 11 памяти перво- Г о канала содержатся коды F, а в И-м разряде второго канала - код В блоке 4 микропрограммного управления сигналом (Х,| ) запускаются микро Операции признака нормального завершения контроля (УК, ) и формирования (Y,-, ) па входах блоков 10 микропрограммного управления первого и второго каналов сигн ала завершения цикла работы устройства (Х,о).

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

Пример 2. Пусть исходное выражение имеет вид: ((а + Ь). х с + + d X 1.

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

В первьй капал подается левая тасть выражения: ((а + Ъ) х. Во второй канал посимвольно оправо налево подается правая часть выражения # с + d X 1Предварительная свертка частей исходного выражения в каналах происходит следующим образом.

-

Дальнейшая обработка входного вь,

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

Деш.5: X

n

Деш.5: Х,г Деш.5: X,, Деш.5: X ij Канал 1: х

Деш.5: X

п

Деш.5: X,

30

35

40

45

Первьй канал

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

( с а + Ъ

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

(

.Ш

((F

55((F

$((

((F ((F)

X

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

(F) (F (F

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

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

ческая единица

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

F

F

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

(F (

При поступлении на входы дешифратора 5 полуоснов из первого канала (, из второго канала - кода j сигналы на выходе дешифратора (Х, - X ,j ) отсутствуют. Сигналы на выходах дешифраторов 12 основ первого (Х ) и второго (Х ) каналов также отсутствуют, так как коды, содержащиеся в старших разрядах блоков 11 памяти, не образуют основу вида .

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

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

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

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

F p

F

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

Окончательная свертка происходит . под управлением блока 4 микропрограммного управления в следующем порядке:

0F

Деш.5: X

«3

0

5

0

0

5

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

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

выходы блоков микропрограммного уп-; равления каналов синтаксического

; анализа соединены соответственно с

третьим и четвертым входами логичес,-

ких условий блока микропрограммного

: управления первые информационные

л

ю

Фt/г.2

46

22

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

J2

ФиеЗ

тг тг

Г Начало}

о

.

х,

Г

Х5

1

ьУ

Х|

Us