Параллельный синтаксический анализатор Советский патент 1989 года по МПК G06F17/27 

Сл 00

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

изобретения - повышение бы- стродействия,

На фиг.1 представлена структурна схема анализатора; на фиг.2 - то же канала синтаксического анализа; на фиг.3-то же,блока памяти;на фиг.4- блок-схема, микропрограммного управления каналом синтаксического анализа; на фиг.5 - блок-схема микропрограммного управления устройством в целом.

Параллельны анализатор фиг.1) содержит регистр 1 текущего символа дешифратор 2 лексических единиц в канале 3 синтаксического анализа, элемент ИЛИ 4 в блоке 5 микропрограм много управления, схем,1 6 и 7 сравнения, дешифратор 8 полуоснов, регистр 9 текущего символа, дешифратор 10 лексических единиц в канале

11синтаксического анализа. Кан,ал 3 (11) синтаксического

анализа (фиг.2) содержит также блок

12микропрограммного управления , дешифратор 13 кода операции, регистр 14 кода операции,, блоки 15 и 16 элементов ИЛИ, коммутатор 17,с: сему 18 сравнения, блок 19 памяти, дешифратор 20 основ.

В состав блока 19 памяти (фиг.З) входит группа 21 из трек реверси1з- ных сд зигаю1)щх регистров.

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

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

ю

is ..

25

30

5

вающая, подключается по входу признака лексической единицы ) - скоба закрывающая канала 11, а выход дешифратора 2, означающий поступление на вход дещифратора лексической единицы ( - ко входу признака лексической единицы ) канала 3.

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

Элемент ИЛИ 4 служит для формирования сигнала завершения цикла синтаксическогоконтроля, возвращающего каналы в исходное состояние.

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

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

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

Коммутатор 17 обеспечивает выборочное подключение в зависимости от сигналов на его управляющих входах к входу записи блока 19 памяти вы- ходов регистра 14 кода операции,бло- сов 5 или 12 микропрограмного управления или выхода блока памяти второго канала.

Группы элементов ИЛИ 15 и 16 алйзуют объединение используемых для управления коммутатором 17 и блоком 19 памяти выходных сигналов блоков, 12 к 5 микропрограммного управления.Блок 19 памяти - зто.память с последовательным безадресным принципом записи и чтения, с обеспечением возможности доступа для чтения одновременна к трем старшим разрядам.

Реверсивные сдвигающие регистры 21 блока 19 памяти реализуют запись кодов лексических единиц в старшие N разряды, хранение записанной информации, поразрядный сдвиг содер314

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

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

На фиг.4 приведена блок-схема функционирования блока 12, где

входные сигналы - Х, Х, Хд формирует дешифратор 2 (для второго канала - дешифратор 10) лексических единиц; Х5, Xg - дешифратор 13 кода операции; Xg, Х - дешифратор 20 основ; - схема 18 сравнения; XjT, - блок 4 элементов ИЛИ.

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

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

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

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

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

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

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

1,если регистр кода операции очищен;

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

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

.0, в противном случае; 1, если в разрядах (N-2), (N-1) и N регистров 21 блока 19 памяти содержится основа F4 F, где F - код, соответствующий операнду, Ч - код, соответствующий операции (высоко- или низкоприоритетной); О, в противном случае;

Х

Хп

X.

Хл

Х5

Хс

X,

5 о

5

0

0

XQ

ш

Xi

13

t

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

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

1,если значение кода, со-, держащегося в регистре 14 кода операции, больше значения кода, содержащегося в (N-l)-x разряда регистров 21 блока 19 памяти;

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

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

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

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

0, в противном случае; Yrj, Yj - микроперации, используемые для формирования кодов лексических единиц на первом входе коммутатора 17;

Y/I4 , , - микрооперации, используемые для формирования кодов на входе регистра 14 кода операции;

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

YIS совокупность микроопераций, соответствующая коду низкоприоритетной операции типа - сложение;.

, , YI - совокупность .микроопераций, соответствующая коду высокоприоритетной операции типа V умножение;

YI , Y-i - совокупность микроопе- 5 раций, соответствующая коду начала части вьфажения ;

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

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

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

5

Сигналы микроопераций Y , Y, Y поступают на информационный вход блока 19 памяти через коммутатор 17.

Сигналы микроопераций Y , ,5 ,й поступают на информационный вх регистра 14 кода операции.

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

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

Y6 - микрооперация,, разрешающая сдвиг содержимого регистров 2 Г бло памяти 19 на один разряд вправо;

Y - микрооперация, разрешающая очистку регистра 14 кода операции;

YI - микрооперация,, разрешающая запись сформированного на информационном входе кода в регистр 14 кода операции;

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

10 Y - микрооперации, используемые для формирования адреса на управляющем.входе коммутатора 17 указанные микрооперации поступают н первые входы группы 15 элементов ИЛИ.

Отсутствие сигналов на управляющем входе коммутатора означает подключение информационного входа блок 19 памяти через коммутатор 17 к первому выходу блока 2 микропрограммного управления.

Y-10 - микрооперация,, обеспечивающая переключение информационного вход блока 19 памяти через коммутатор 17 на выход регистра 14 кода операции (вьщача сигнала микрооперации YIO при отсутствии сигнала микрооперации Y,, означает подачу на управляющий вход коммутатора кода 1 - подключение выхода коммутатора к его второму входу);

Yig, - микрооперация, формирующая на входе блока 5 микропрограммного управления сигнал X,j (Х - для второго канала), означающий нормальное завершение предварительной свертки части входного выражения в канале);

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

n

5

0

5

Алгоритм функционирования блока 5 микропрограммного управления описан блок-схемой (фиг.5), где входные 1г 13 и Х , Х|з формисигналы X

, .7 I } f I lrt

руются соответственно первым и вторым каналами синтаксического анализа, Xi4 - , Х(л - дешифратором 8 полуоснов; Х,о - первой схемой

6сравнения; Х - второй схбмой

7сравнения.

На выходе блока 5 микропрограммного управления генерируются сигна- ль1 микроопераций Y; , Y. g , Y,, - , Y,, , Y . Ylg - Y|,, Y«,

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

1, если предвариу fv {г

о.

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

30

35

0

5

0

5

XJ5 (х;)

ь

1.

XQO

-0, 1,

Ч(

О,

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

если приоритет операции, код которой содержится в (N-I)-M разряде блока 19 памяти первого канала, больше или равен приоритету операции, код которой содерл ится в N-M разряде блока 19 ° памяти второго канала; в противном случае;

если приоритет операции, код которой содержится в (N-I)-M разряде блока 19 памяти второго канала, больше или равен приоритету операции, код. которой содержится в N-M разряде блока 19 памяти первого канала; в противном случае.

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

Хь

VoF

VVF

или

Приме.чание, У - код- произвольной лексической единицы.

Нулевые значения входных сигналов- М ig «1 образуются при от- личных от приведенных в таблице со- держимых старших трех разрядов блоков 19 памяти первого и второго каналов . ,|з (23 ) микрооперация, исполь- зуемая для формирования кода лексической единицы F - операнд на третьем входе кo o yтaтopa 17 первого (второго) канала;

Y44(Y) - микрооперация, разрешающая запись сформированного на информационном входе блока 19 памяти первого (второго) канала хода в старшие N-e разряды регистров 21j

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

Y26 (26) микрооперация, разрешающая сдвиг влево на один разряд содержимого регистров 21 блока 19 памяти первого (второго) канала;

Yi7 ,.Y,g (Y,r , Y,g) - микрооперации, используемые для формирования адреса на управляющем входе коммутатора 17 первого (второго) ка нала, указанные микрооперации по

465894

ступают на вторые входы группы ИЛИ;

15

элементов

, 7 ( ) микрооперация, обеспечивающая переключение информационного входа блока 19 памяти первого .(второго) канала через коммутатор 17 на первый (второй) выход блока 5 микропрограммного управления;

10

15

20

25

в- в

30

35

40

45

50

55

Ч

14

(Y

17

Y/g ) - совокупность микроопераций, обеспечивающая переключение информационного входа блока 19 памяти первого (второго) канала через коммутатор 17 на третий вход канала;

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

YQO микрооперация формирования признака ошибочного завершения анализатором цикла синтаксического контроля.I ,

Сигналы микроопераций Yr24 , Yji , Y26 (Y,,, , , еб) поступают на вторые входы группы 16 элементов ИЛИ первого (второго) каналов, выходы элементов ИЛИ группы 16 подключены к управляющим входам блока 19 памяти.

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

Исходное вьфажение перед началом делится внешним устройством в произвольном месте на две примерно равные части. Левая (правая) часть входного выражения справа дополняется признаком конца fr.

Правая (вторая) часть выражения дополняется признаком слева.

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

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

(Х) , нормального завершения свертки во втором канале (х ) ошибочного завершения свертки во втором канале (Х,; ).

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

i xf,

11

. .

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

Каналы 3, 11 осуществляют предварительную свертку частей входного выражения полностью идентично, па- I раллельно и независимо друг от друга, поэтому рассмотрим работу толь- i ко одного из них (первого), Блок 12 микропрограммного управ- i ления в начале цикла своей работы : генерирует микрооперации очистки регистра 14 кода операции (Y),формирования кода признака $ начала выражения (Y, , Y) и разрешения записи сформированного кода в N-й разряд блока 19 памяти (Y). На уп- 1 равляю1цем входе коммутатора 17 сиг- 1 налы отсутств5пот, что соответству- ет подключению информационного вход блока 19 памяти к первому выходу : блока 12 микропрограммного управления

На следующем шаге блок 12 начи- , нает обработку очередной лексической единицы,

БЛОК 12 микропрограммного управления выдает микрооперацию разрешения записи (Yg) в регистр 1 текущего символа.

На выходе дешифратора 2 лексических единиц формируются признаки лексических единиц, являющиеся входными сигналами блока 12 микропрограммного управления (X, - Хл Х-,

V 7 Г J

Хд) .

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

1465894

10

микропрограммного управления микрооперацию (YS), разрешающую сдвиг содержимого регистров 21 блока 19 па- мяти на один разряд влево, тем са-. мым освобождается старший N-й разряд блока памяти для записи в него кода очередной лексической единицы. На следующем шаге блок 12 мйкро- 10 программного управления выдает микрооперации (Y ,Ye) формирования на информационном входе блока 19 памя- ти кода 011 - скобка открывающая и Yz| - разрешение записи сформиро- 15 ванного кода в N-й разряд блока 19 памяти„

Если очередная лексическая единица на входе дешифратора 2 есть операнд, то на его соответствую- 20 щем выходе формируется сигнал (Xj), запускающий в блоке 12 выдачу микрооперации (YS), разрешающей сдвиг содержимого блока 19 памяти на один разряд влево. Затем блоком 12 микро- 25 программного управления выдаются микрооперации формирования (Yj) на информационном входе блока 19 памяти кода операнда F (100) и разрешения записи (Y) сформирован- 30 ного кода в N-й разряд блока 19 памяти.

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

Если очередная лексическая единица на входе дешифратора 2 есть высокоприоритетная операция, то нас его соответствующем выходе формируется сигнал (Х), запускаюпглй в бло- . ке 12 микрооперации формирования 1( , Y45 , ) на информационном входе регистра 14 кода х (111) и разрешения записи (Yj) сформированного кода в регистр 14 кода операции,

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

0

информационном входе регистра 14 кода ) (001.) и разрешения записи (Yg) сформированного кода в регистр 14 кода операции.

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

Если очередной символ входного выражения не является допустимой .лексической единицей, то сигналы на выходах дешифратора 2 (Х - Х, Xf, XJ .отсутствуют. При отсутствии входных сигналов признаков лексических единиц (X, - Х, Х, Xq) блок 12 микропрограммного управления выдает микрооперацию признака ошибочного .завершения предварительной сверки части входного выражения исходного выражения в канале (Yo ).

Указанная микрооперация, формирующая входной сигнал признака ошибочного завершения работы канала (xli, ) блока 5 микропрограммного управления, выдается блоком 12 микропрограммного управления в каждом последующем такте до тех пор, пока блок 5 микропрограммного управления не вьщает одну из микроопераций (У„ или- Y4U ) признаков нормального или ошибочного завершения контроля, формирующих входной сигнал .(Xijj) блока 12 микропрограммного управления. При этом генерация микрооперации Y,, прекращается,и блок 12

5

0

5

0

5

0

5

0

5

микропрограммного управления завершает работу (возвращается в начальное состояние).

После распознавания очередной лексической единицы и запоминания ее кода в N-M разряде блока 19 памяти (коды F и ( или в регистре , 14 кода операции (коды к, + или )) блок 12 микропрограммного управления переходят на анализ входных сигналов, выpaбaтывae tыx схемой 18 сравнения () , дешифратором 13 кода операции (Xs, Хб) и дешифратором 20 основ (Xj, Хц ).

Если на выходе схемы 18 сравнения вырабатывается сигнал (Х(о), означаюишх, что код операции, содержащийся в регистре 14 кода операции, имеет большое значение, чем код операции, содержащийся в (N-I)-M разряде блока 19 памяти, то это означает, что приоритет текущей операции, код которой записан в регистре 14, выше приоритета предыдущей операции, код которой содержится в (N-1)-M разряде блока 19 памяти. В этом случае свертка основы, заключающаяся в замене сочетаний кодов типа FxF, F + F ил51 (F) кодом операнда F невозможна. Свертка допускается лишь тогда, когда приоритет операции, следующей за ос- нов ой, ниже или равен приоритету операции, соединяющей два операнда внутри основы.

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

Если на входе блока 12 микропрограммного управления схемой 8 сравнения сформирован сигнал Х , то блок 12 генерирует микрооперашто (YS), разрешающую сдвиг на один разряд влево содержимого регистров 21 блока 19 памяти. Затем генерируются микрооперации формирования (У/о ) на управляющем входе коммутатора 17 кода 01 переключения его выхода на второй вход, в результате чего информационный вход блока 19 памяти оказывается соединенным с выходом регистра 14 кода операции, и разрешен1-1Я записи (Y4) в блок 19 памяти кода, сформированного на его информационном входе. После пеоезаписи содержимого 14 кода

9 ам

ти блок 12 микропрограммного управ ленвд генерирует микрооперащ (у разрешающую очистку регистра 14 Затем блок 15 микропрограммного управления выполняет действия по вво и обработке следующей лексической единигды исходного зыражения

сигнаГх ™ - ° сравнения сигнал X,, отсутствует, то блок 12

микропрограммного управленга анализирует наличие входного.сигнала X формируемого деиифратором 13 копов операций. .-i.oB

Еспи на входе блока 12 микропрограммного управления дешифратором J кода операции формируется сигн.ял Хб), соответствующий очищенному состоянию регистра 14.. то блок 12 выполняет действия по обработке еле ОТей лексической единицы исходно- го выражения.

При отсутствии входного сигнала Аб, что соответствует непустому состоянию регистра 14 кода операции, блок 12 микропрограммного уг-. Равления анализирует формируемьй де- шифратором 20 основ сигнал (Х«) соответствующий наличшо в старших трех разрядах блока 19 памяти свора- чиваемои основы вида RxF или

Блок 12 микропрограммного управления при налшчии на его входе сиг- нала X,i выдает последовательность микроопераций, осуществляющих сверт- ку основы, т.е. замену сочетания коран а °- ранда F , Свертка осуи,ествляется

путем вьщачи блоком 12 микропрограммного управления шкpooпepaций дв ж™

,

,

входе блока 19 памяти (у,), подключенном к выходу блока 12 микропро- граммного управления через коммутатор 17, и разрешения записи сформированного кода в N-й старший раз-- РЯД блока 19-памяти (У),,

После выполненных действ ий блок 1 микропрограммного управления снова анализирует входной сигнал Сх,п ) формируемый схемой 18 сравнения для определения возможности свертки ооразовавшегося выражения,.

-:

10

15

0

1 6589414

на входе блока 12 микропрограммного управления отсутствует формируемый дешифратором 20 основ сигнал (Xg), что означает отсут- .ствие основы типа РнР в старших трех разрядах блока 19 памяти, где

означает код произвольной операции то в этом случае-в старших N-2), (N-1) и M.,J, разрядах блока 19 памяти могут содержаться только основы типа F Пш« .ли Ос

«на н . Любое другое содержимое данных разрядов свидетельс ву- ет о наличии ошибки во входном выражении. В этом случае на входе блока 12 микропрограммного управления отсутствует сигнал Х-, формируемьм дешифратором 20 основ. При этом анализ части входного вырал ения завершается. Блок 12 микропрограммного -лравления выдает микрооперацию признака ошибочного завершения предварительной свертки части исходного

Р5 - Указанная : Р°операция, формирующая входной сигнал признака ошибочного завершо- ния работы канала (х,, ) блока 5 микропрограммного управления, вьщает- ся блоком 12 в калсдом последующем -Ю такте до тех пор, пока блок 5 микропрограммного управления не вьщаст одну из микроопераций - у,. „DU- знаков нормального или ошибочного завершения контроля, формирующих 35 входной сигнал (х„ ) блока 12 микро- програм много управления. При этом генерация микрооперации У,, прекращается, и блок 12 завершает работу

При наличии в трех старших разря- 40 Дах б.лока 19 памяти кодов, образую- № основу типа (F), де.шифратор и основ формирует сигнал (Хк-) запускающий в блоке 12 микропрограмм много управления последовательность 45 микроопераций, осу,цествляющи:

свертку основы. Блок 12 микропрограммного управления вьщает ми.кро- операции двавды разрешения сдвига на один разряд впраазо содержимого регистров 21 блока 19 памяти (У и формирования кода F (у ) информационном входе блока 19 памя- ™ и разрешения записи сформированного кода в N-й разряд блока 19 памяти. После этого блок 12 микропрограммного управления вьшолняет действия по вводу и обработке следующей лексической единицы игход- ного выражения.

0

5

15 1

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

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

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

г х/; Y . , xf,,

S -

TO блок 5 микропрограммного управле ния вьщает микрооперацию признака ошибочного завершения контроля (Ygo формирующую на входах блоков 12 микропрограммного управления первого и второго каналов сигнала завершения синтаксического контроля (). На этом цикл работы устройства заканчивается.

„

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

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

.Если на входе блока 5 микропро- граг много управления отсутствует формируемый дешифратором 8 сигнал (Х) наличия завершающего выражения в блоках 19 памяти каналов, т.о блок 5 продолжает окончательную свертку выражения. В зависимости от содержания старших разрядов блока 19 памя94

ти дешифратор 8 формирует признаки полуоснов ( - Х,9, Х2.|).

Если в очередном шаге свертктг н входе блока 5 микропрограммного управления одновременно отсутствуют все формируемые дешифратором 8 признаки полуоснов ( - -Х,д И X л

то это свидетельствует о наличии ошибки 30 входном выра кении.

В этом случае блок 5 микропрограммного управления выдает микро- опепацпга (Y.jo) сигнала признака ошбочного завершения контроля,которая формирует на входах блоков 12 микропрограммного управления перво и второго каналов сигнала завер- лепня синтаксического контроля (Х. Яа этом цикл работы анализатора за- oepujaeTCH,

Устройство готово к анализу следующего входного выражения.

Если в очередном шаге свертки i-a выходе дешифратора 8 полуоснов ф формируется сигнал (Xtg), соответ- ст)зую1Ц1 й наличию в трех старших разрядах блока 19 памяти первого канала кодов, образуюищх основу FxF или то блок 5 микропрограммного управления анализирует наличие входного сигнала (Х,2д). формируемого схемой 6 сравнения,

Сигнал Хг2п формируется схемой 6 сравнения в том случае, если значение кода, содержащегося в W-M старшем разряде блока 19 памяти второго канала, больше значения кода, со- дер/кащегося в (N-I)-M разряде блока 19 памяти первого канала. В этом случае приоритет операции, следующей за основой типа F-fF, вьпие кода операции, соединяющего операнды основы. Свертку при этом производить нельзя.

При отсутствии на выходе схемы 6 сравнения сигнала (Хор) блок 5 микропрограммного управления вьщает последовательность микроопераций, осуществляющих свертку основы. Выдаются микрооперации дважды разрешения сдвига вправо на один разряд содержимого регистров 21 блока 19 памяти первого канала (Yj нУ ), формирования кода F на треть ем входе коммутатора 17 первого канала (Y25 ) , формирования на управляющем входе коммутатора 17 кода 10 (Y|5 ) , переклрочающего выход коммутатора на его третш вход, тем самым

it-pii

1465894

18

код F формируется на информацион- ч нЬм входе блока 19 памяти первого канала, и разрешения записи (4) сформированного кода в N-й старший рйзряд б -1ока 19 памяти первого канала.

I Если в очередном шаге свертки на выходе дешифратора В полуоснов фэрмируется сигнал (Х ),, что соот- в гтствует наличию в трех старших разрядах блока 19 памяти второго клнала кодов ,образующих основу 1ГхР или F+F, то блок 5 микро- п)ограммного управления анализирует наличие входного сигнала (Х), формируемого схемой 7 сравнения.

Сигнал 12 формируется схемой 7 сравнения в том случае,если значе- .ние кода, содержащегося в N-M стар- разряде блока 19 памяти первого канала больше значения кода,содержащегося в (N-1)M разряде блока 19 п;1мяти второго канала, В этом случае свертка основы не проигшодится.

При отсутствии на выходе схемы 7 сравнения синала (Xijj) блок микро- П1)ограммнсго управления вьщает пго- а1едовательность микроопераций, осу- Щ|;ствляющих свертку основы. Вьщают- CII микрооперации дважды разрешения сдвига на один разряд вправо содержимого регистров 21 блока 19 памяти второго канала (|ь иУ,) формирования кода операнда (Y|.j ), формирования на управляющем входе коммутатора 17 второго канала кода 10 ( ) переключакяцего выход коммута- тфра на его третий вход, и разрешеН1|1Я записи (Yj4 ) СфОрМИрОВ 1ННОГО

Kitoa в N-й старший разряд блока 19 п,|1мяти второго канала.

Если в очередном шаге свертки на дешифратора 8 полуоснов фортьем входе коммутатора 17 второго канала (Yj,,,), формирования на управляющем входе этого коммутатора g кода 10 (Yf ) переключения выхода коммутатора 17 на его третий вход резрешения записи кода операнда в старший N-й разряд блока 19 памяти второго канала (Y44).

10 Если в очередном шаге свертки на выходе дешифратора 8 полуоснов формируется сигнал (Х), соответ- ствуюудий наличию в старших разрядах блоков 19 памяти первого канала

15 кода F и второго канала - кодов xF+, то блок 5 микропрограммного управления генерирует последовательность микроопераций, осуществляющих совместный сдвиг выражения,

20 левая часть которого находится в бло ке 19 памяти первого канала, а правая часть - в блоке 19 памяти вто- |рого канала, на два разряда влево. Выдаются микрооперации разрешения

25 сдвига на один разряд влево содержимого блока 19 памяти первого канала (), формирования на управляющем входе коммутатора 17 первого канала кода 10 (Y,g ) переключения выхода

30 коммутатора на его третий вход, разрешения (Y24.) записи %ода с информационного входа блока 19 памяти первого канала в N-e разряды регистров 21,

В результате вьтолненных деист- .: ВИЙ код из старшего N-ro разряда блока 19 памяти ВТОРОГО канала переписывается в N-й разряд блока 19 памяти первого канала.

дд Затем вьщаются микрооперации разрешения сдвига на один разряд содержимого блоков 19 памяти первого канала влево (Yjg), второго канала - вправо (Yl), снова выполняется со35

.j,,.,,/„ V 26 / - вынилниетСЯ СО-

Фуется сигнал ( ), соответствую- вокупность микроопераций,осуществля- vsM наличию в старших оазояшах бло-: «mae „-,,.«„„„. ...

vs наличию в старших разрядах бло-. юов 19 памяти первого канала кода Р и второго канала - кодов Fx и)|1и первого канала - кода ( и Btoporo канала - кодов )F, или первого канала - кода F и второ- гф канала - кодов , то блок 5 М1 кропрограммного управления произ- В(|)дит свертку основы. Блок 5 микро- nij orpaMMHoro управления генерирует М1 крооперации разрешения сдвига на оДин разряд вправо содержимого реги- c l-poB 21 блоков 19 памяти первого (t26 ) и второго (Y| ) каналов, фор- М1 1рования кода операнда F на тре50

ющая перезапись кода из старшего N-ro разряда блока 19 памяти первого канала в старший N-й разряд блока 19 памяти второго канала (Y, , 54) и разрешения сдвига на один разряд вправо содержимого блока 19 памяти второго канала (Y),

В результате выполнения совокупности перечисленных микроопераций 55 содержимое блока 19 памяти первого канала сдвигается на два разряда влево, в освободившиеся (N-1) и N-й разряды переписывается содержимое соответственно (К-1)-го разрядов

18

тьем входе коммутатора 17 второго канала (Yj,,,), формирования на управляющем входе этого коммутатора g кода 10 (Yf ) переключения выхода коммутатора 17 на его третий вход резрешения записи кода операнда в старший N-й разряд блока 19 памяти второго канала (Y44).

0 Если в очередном шаге свертки на выходе дешифратора 8 полуоснов формируется сигнал (Х), соответ- ствуюудий наличию в старших разрядах блоков 19 памяти первого канала

5 кода F и второго канала - кодов xF+, то блок 5 микропрограммного управления генерирует последовательность микроопераций, осуществляющих совместный сдвиг выражения,

0 левая часть которого находится в блоке 19 памяти первого канала, а правая часть - в блоке 19 памяти вто- |рого канала, на два разряда влево. Выдаются микрооперации разрешения

5 сдвига на один разряд влево содержимого блока 19 памяти первого канала (), формирования на управляющем входе коммутатора 17 первого канала кода 10 (Y,g ) переключения выхода

0 коммутатора на его третий вход, разрешения (Y24.) записи %ода с информационного входа блока 19 памяти первого канала в N-e разряды регистров 21,

В результате вьтолненных деист- .: ВИЙ код из старшего N-ro разряда блока 19 памяти ВТОРОГО канала переписывается в N-й разряд блока 19 памяти первого канала.

д Затем вьщаются микрооперации разрешения сдвига на один разряд содержимого блоков 19 памяти первого канала влево (Yjg), второго канала - вправо (Yl), снова выполняется со5

f V 26 / - вынилниетСЯ СО-

вокупность микроопераций,осуществля- «mae „-,,.«„„„. ...

вокупность микроопераций,осуществля- «mae „-,,.«„„„. ...

ющая перезапись кода из старшего N-ro разряда блока 19 памяти первого канала в старший N-й разряд блока 19 памяти второго канала (Y, , 54) и разрешения сдвига на один разряд вправо содержимого блока 19 памяти второго канала (Y),

19

блока 19 памяти второго каналов и содержимое блока 19 памяти второго канала сдвигается на два разряда вправо,.вытесняя за пределы регистров 21 содержимое перенесенных в память первого канала двух старших разрядов.

Если в очередном паге свертки на выходе дешифратора 8 полуоснов формируется сигнал (Х,), соответствующий наличию в старших разрядах блоков 19 памяти первого канала кодов F+ и второго канала - кодов xF, то блок 5 микропрограммного управления генерирует последовательность микроопераций, осуществляющих совместный сдвиг выражения левая часть которого находится в блоке 19 памяти первого канала, а правая часть - в блоке 19 второго канала, на один разряд влево.

Выдаются микрооперации разреше- ,ния сдвига на один разряд влево содержимого блока 19 памяти первого канала (YC) формирования на управляющем входе коммутатора 17 первого канала кода 10 (Y/g ) переключения выхода коммутатора на его третий вход, разрешения (Y) записи кода с информационного входа блока 19 памяти первого канала в старшие N-e разряды регистров 21, разрешения .сдвига на один разряд вправо содержимого блока 19 памяти второго канала (Yl).

Если в очередном шаге свертки на выходе дешифратора 8 полуоснов формируется сигнал (KIJ), соответствующий наличию в старших разрядах блока 19 памяти первого канала кодов Fx и второго канала - кода F, или первого канала - кодов (F и . второго канала - кода ), или первого канала кодов F+ и второго канала - кодов , то блок 5 микропрограммного управления производит свертку основы. ВЬщаются микрооперации разрешения сдвига на один разряд вправо содержимого блоков 19 памяти первого (Yj ) и второго (Y каналов, формирования кода операнда F на третьем входе коммутатора 17 первого канала (Y ), формирования на управляющем входе этого коммутатора кода 10 (Y/a ) переключения выхода коммутатора на его третий вход, разрешения записи кода операн10

465894

да в старший N-й разряд блока 19 памяти первого канала (Yj )

Если в очередном шаге свертки на выходе дешифратора 8 полуоснов формируется сигнал () соответствующий наличию на входах дешифратора составляющих завершающего выражения, т.е. в (N-1) и N-M разрядах блока 19 памяти первого канала содержатся коды $F, а в N-M разряде блока 11 памяти второго канала - код или в N-M разряде блока 19 памяти первого канала содержится код f, а в (N-1) и N-M разрядах блока 19 памяти второго канала - коды F, то в блоке 5 микропрограммного управления выдается микрооперация ( ) формирования признака нормального завершения контроля, формирующая на входах блоков 12 микропрограммного управления первого и второго каналов -сигнала завершения синтаксического 25 контроля (Хгз). На этом цикл работы анализатора завершается. Устройство

15

20

30

готово к анализу следующего входного

выражения.

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

5

0

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

5

0

21

второго и первого каналов синтаксического анализа соответственно, втрые выходы формирования полуоснов торых соединены с вторыми входами второй и первой схем сравнения соответственно, выходы которых соединены с входами признаков приоритет операций в втором и первом канале блока микропрограммного управления первые и вторые входы признаков обнаружения ошибки и правильной запис которого подключены к выходам одно- I именных признаков первого и второго каналов синтаксического анализа со- I ответственно, управляющие входы котрых соединены с выходами первой и второй групп блока микропрограммно- |Го управления соответственно, вы- |ход признака обнаружения ошибки ко- (торого соединен с одноименным выходом анализатора, выходы стробирова- :ния ввода первого и второго каналов синтаксического анализа соединены 1C входами записи первого и второго регистров текущего символа соответ- jCTBeHHo

I 2, Анализатор по п,1, о т л и - |чающийся тем, что каждый канал синтаксического анализа содержи ешифратор лексических единиц, инфо Национный вход которого является информационным входом канапа, блок миропрограммного управления, дешифратор кодов операций, регистр кода операции, схему сравнения, коммутатор, блок памяти, дешифратор осно И два блока элементов ИЛИ,, выходы которых соединены с управляющими Входами коммутатора и блока памяти соответственно, с первого по третий Выходы которого соединены с первого.

22

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

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

0 коммутатора, выход которого соединен с информационным входом блока памя- второй выход которого соединен

ти,

с первым входом схемы сравнения, .второй вход которой соединен с выходом

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

5

/3

14

}S

Изобретение относится к вычислительной технике и может быть использовано в быстродействующих системах обработки информации, диалоговой разработки и отладки программ. а также о аппаратных преобразователях и интерпретаторах языков высокого уровня. Цель изобретения - повышение быстродействия. Анализатор осущестс:ляет двухэтапный контроль входного выражения. Первый, предварительный, зтап обработки осуществляется двумя идентичными каналя- ми 3 и i i синтаксического анализа, работающими параллельно и независимо друг от друга. Устройство содержит также регистры 1 и,, 9 текушего символа, ;ijiOK 5 микропрограг 1м1юго управлеыия, схемь; 6 и 7 сравнения и дешифр,атор 8 полу основ, которые осуществляют окончательную свертку входного выражения, 1 з.п„ ф-лы, 1 табл.5 5 ил, о

;г

№

f

JH-l

2}

§

112 №i

w группа It л и

Л

19

Hi f Т

f

JH-l.tHH

Фие.З

г . J

С наголо)

,., У ,

У.У.УШ

1 щdJII

iMisMsM

mMiJС. коней)

1

9i9.3v у

С Мазало

}УМУ| ,У/я {

Иг

ЧЖЗ ЕЖНЭНЭ ЕП С

.iLj;j :

г

ijjififT wEI

Яге

Угз,гу ,

Lj.