Параллельный синтаксический анализатор

 

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

СОВХОЗ СОВЕТСКИХ

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

РЕСПУБЛИК

А1 (51)4 С 06 - 15/38

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

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

ПРИ ГКНТ СССР (21) 4302078/24-24 (22) 13.07.87 (46) 15.03.89. Бюл. Р 10 (72) В.К.Водопьянов, Ю.A.Îðëîâ, С.Н.Вавилов, В.Н.Волков и С.П.Зайцев (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1130879, кл. G 06 F 15/38, 1982.

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

669356, кл. G 06 F 11/28, 1976, (54) ПАРАЛЛЕЛЬНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР (57) Изобретение относится к вычислительной технике и может быть использовано в быстродействующих системах обработки информации, диалоговой разработки и отладки программ, БЦ;;; 1 465894 а также в аппаратнь х преобразователях и интерпретаторах языков высокого уровня. Цель изобретения — повыHIeHHc бысTродействия. Анализатор осуществ.:яет двухэтапный контроль входного выражения. Первый, предварительньй> этап обработки осуществляете-; двумя идентичными канал»ми 3 и !: синт=-.ксического внял;за работающи:.-1и параллельно и незаГиси-мо друг от друга. Устройство содержит также регистры 1 и, 9 теку:пего символ,",, ;ок 5 микропрограммного управл;ноя„ схемь. 6 и 7 сравнения и дешифр:=. òîð 8 полуоснов, котсрые осуществляют окончательную свертку входного выражения. 1 з.п. ф-лы, 1 табл., 5 ил.

1465894

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

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

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

В фиг. 3 — то же, блока памяти; на фиг. 4- 15 блок-схема микропрограммного управ« ления каналом синтаксического анализа; на фиг.5 — блок-схема микропрограммного управления устройством в целом. 20

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

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

12 микропрограммного управления, дешифратор 13 кода операции, регистр 14 кода операции,, блоки 15 и

16 элементов ИЛИ, коммутатор 17 схе-! му 18 сравнения, блок 19 памяти деЭ шифратор 20 основ.

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

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

Дешифраторы 2 и 10 выделяют из

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

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

ft /1! единицы (— ко входу признака лексической единицы ")" канала 3.

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

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

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

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

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

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

Группы элементов ИЛИ 15 и 16 ре ализуют объединение используемых для управления коммутатором 17 и бло- ком 19 памяти выходных сигналов блоков

12 и 5 микропрограммного управления.

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

Реверсивные сдвигающие регистры

21 блока. 19 памяти реализуют запись кодов лексических единиц в старшие

И разряды, хранение записанной информации, поразрядный сдвиг содер-

1465894 х, 10

Х11

Х4

Х5

Х6

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

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

На фиг.4 приведена блок-схема функционирования блока 12 где входные сигналы Х„ — Х, Х» Х формирует дешифратор 2 (для второго канала — дешифратор 10) лексических единиц; Х, Хб — дешифратор 13 кода операции; Х, Хп — дешифратор 20 основ; X„> — схема 18 сравнения;

Х вЂ” блок 4 элементов ИЛИ.

На выходе блока 12 микропрограммного управления формируются сигналы микроопераций Ъ вЂ” Y„q .

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

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

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

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

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

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

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

1, если лексическая единица

35 исходного выражения есть низкоприоритетная операция.

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

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

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

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

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

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

1, если в разрядах (N-2)

50 (N-1) и N регистров 21 блока 19 памяти содержится основа "Р М F", где

"F" — код, соответству-. ющий операнду, код, соответствующий операции (высоко- или низкоприоритетной);

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

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

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

1, если значение кода, со-. держащегося в регистре

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

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

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

r (F) и.

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

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

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

Y, Yq, Y5 — микр операции, используемые для формирования кодов лексических единиц на первом входе коммутатора 17;

У<4, У,з, Y« — микрооперации, используемые для формирования кодов на входе регистра 14 кода операции;

Y q — микрооперация, соответствую11 l1 щая коду лексической единицы ) скоба закрывающая;

Y 5, Y 6 — совокупность микроопераций, соответствующая коду низ1t 1I коприоритетной операции типа + сложение;

Yqg Yqg > YIg совокупность микроопераций, соответствующая коду высокоприоритетной операции типа

"y. — умножение;

Y, Y — совокупность микроопераций, соответствующая коду начала

11с4 И ° части выражения

Yg — микрооперация, соответствую-!! tf„ щая коду конца части выражения м

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

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

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

5 1465

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

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

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

Yg - микрооперация, разрешающая сдвиг содержимого регистров 2 1 блока ( памяти l9 на один разряд вправо;

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

Yg — микрооперация„ разрешающая ! запись сформированного на информационном входе кода в регистр 14 ко1 да операции

Ф 20

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

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

ИЛИ.

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

19 памяти через коммутатор 17 к первому выходу блока 12 микропрограммного управления.

Ую - микрооперация,, обеспечиваю" щая переключение информационного входа блока 19 памяти через коммутатор

17 на выход регистра 14 кода операции (выдача сигнала микрооперации

Yqq при отсутствии сигнала микрооперации 7ц, означает подачу на управляющий вход коммутатора кода "1" подключение выхода коммутатора к его второму входу);

Yqg — микрооперация, формирующая на входе блока 5 микропрограммного управления сигнал Х, (Х " для

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

Апгоритм функционирования блока

5 микропрограммного управления описан блок-схемой (фиг,5), где входные

I сигналы Х,, Х, и Х,, Х, формируются соответственно первым и вторым каналами синтаксического анализа, Х 4 — Х„4, Хц — дешифратором 8 полуоснов; Xgp - первой схемой

6 сравнения; Xgq — второй схемой

7 сравнения °

На выходе блока 5 микропрограммного управления генерируются сигнаJIbf микроопераций Y)p, Y)g Ygg ф Д

15 Yqg Yrz Y à Y Yfz ° Y

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

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

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

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

О, в противном слуЗО

ХЯО

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

N-м разряде блока 19 памяти второго канала;

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

1, если приоритет операции, код которой содержится в (М-1) -м разряде блока 19 памяти второго канала, больше или равен приоритету операции, код которой содержится в

N-м разряде блока 19 памяти первого канала;

О, в противном случае.

14658

Содержимое (N-2),(Ы-1) и N-ro разрядов блока 19 памяти второго канала

Содержимое (N-2),(N-1) и N-го разрядов блока

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

Формируемъп» сигнал

75F

YFx

Х15 или или

VVF, р+

xF»fxF

П Р и м е ч а н и e° . "b " — код- 30 произвольной лексической единицы.

Нулевые значения входных сигналов.

Х,4 — Х»З, Х » образуются при от.личных от приведенных в таблице содержимых старших трех разрядов бло- З5 ков 19 памяти первого и второго каналов.

Я . у (У ) — микрооперация, используемая для формирования кода лексической единицы "F" — операнд на третьем входе коммутатора 17 первого 40 (второго) канала;

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

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

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

1 Ф

У»7 в Y»g Ж7 ° Y g ) микро операции, используемые для формиро. вания адреса на управляющем входе коммутатора 17 первого (второго) канала, указанные микрооперации поУсловия формирования единичных значений остальных входных сигналов блока 5 микропрограммного управления приведены в таблице.

94 8 ступают на вторые входы группы 15 элементов ИЛИ;

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

17 на первый (второй) выход блока

5 микропрограммного управления;

Я 2

У«, Yö (Y<<, Y,8 ) — совокупность микроопераций, обеспечивающая переключение информационного входа блока 19 памяти первого (второго) канала через коммутатор 17 на третий вход канала;

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

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

I (Сигналы микроопераций Уда, Ус> )

У (У,,», Yz» Y zb) поступают на вторые входы группы 16 элементов ИЛИ первого (второго) каналов, выходы элементов ИЛИ группы 16 подключены к управляющим входам блока 19 памяти.

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

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

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

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

После включения устройства блок 5

50 микропрограммного выражения анализирует входные сигналы нормального завершения свертки части входного выl ражения в первом канале (X«), ошибочного завершения свертки части входного выражения в первом канале

55 (Х» ), нормального завершения свертки во втором канале {Х„ ), ошибочно2 го завершения свертки во втором

2 канале (Х,> ) .

65894 мяти.

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

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

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

45 высокоприоритетная операция то на °

9 его соответствующем выходе формируется сигнал (Х ), запускающий в блоке 12 микрооперации формирования (7 ((У У ь ) на информационном входе регистра 14 кода "х" ("111")

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

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

9 14

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

ы„Ф

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

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

Блок t2 микропрограммного управления в начале цикла своей работы генерирует микрооперации очистки регистра 14 кода операции (Y>),формирования кода признака " " начала выражения (71, Y ) и разрешения записи сформированного кода в N-й разряд блока 19 памяти (7,1). На управляющем входе коммутатора 17 сигналы отсутствуют, что соответствует подключению информационного входа блока 19 памяти к первому выходу блока 12 микропрограммного управления.

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

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

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

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

5 l0 l5

ЗО микропрограммного управления микрооперацию (Yg ), разрешающую сдвиг содержимого регистров 2 1 блока 19 памяти на один разряд влево, тем са-, мым освобождается старший N-й разряд блока памяти для записи в него кода очередной лексической единицы.

На следующем шаге блок 12 микропрограммного управления выдает микрооперации (Y,,Yg) формирования на информационном входе блока 19 памяти кода "011" — скобка открывающая и Y4 — разрешение записи сформированного кода в N-й разряд блока t9 памяти.

Если очередная лексическая единица на входе дешифратора 2 есть операнд, то на его соответствующем выходе формируется сигнал (Х ), запускающий в блоке 12 выдачу микрооперации (Yg), разрешающей сдвиг содержимого блока 19 памяти на один разряд влево ° Затем блоком 12 микропрограммного управления выдаются микрооперации формирования (Y ) на информационном входе блока 19 памяти кода операнда "Р" ("100") и разрешения записи (Yq) сформированного кода в N-й разряд блока 19 па1465894 информационном входе регистра 14 кода ")" ("001") и разрешения записи (Yg) сформированного кода в регистр

14 кода операции.

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

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

Если очередной символ входного выражения не является допустимой лексической единицей, то сигналы на выходах дешифратора 2 (Х1 — Х, Х, X ) отсутствуют ° При отсутствии входных сигналов признаков лексических единиц (Х, — Х, Х, Xg) блок

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

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

После распознавания очередной лексической единицы и запоминания ее кода в N-м раэряде блока 19 памяти (коды "F" и "(") или в регистре

14 кода операции (коды "х", "+" или

")") блок 12 микропрограммного управления переходит на анализ входных сигналов, вырабатываемых схемой

18 сравнения {Х<о ), дешифратором 13 кода операции (Хэ, Х6) и дешифратором 20 основ (Xg, X«) .

Если на выходе схемы 18 сравнения вырабатывается сигнал (X

30 кодОВ типа Г"Е Р + F или (Ь) кодом операнда "F", невозможна. Свертка допускается лишь тогда, когда приоритет операции. следующей за основой, ниже или равен приоритету операции, соединяющей два операнда внутри основы.

Xpor

40 код закрывающей скобки ")" или нулевое значение (после операции очистки).

Если на входе блока 12 микропрограммного управления схемой 8 . сравнения сформирован сигнал Х, то

45 блок 12 генерирует микрооперацию (Y ), разрешающую сдвиг на один разряд влево содержимого регистров 2 1 блока 19 памяти. Затем генерируются микрооперации формирования (Y< ) на управляющем входе коммутатора 17 кода "01" переключения его выхода на второй вход, в результате чего информационный вход блока 19 памяти оказывается соединенным с выходом регистра 14 кода операции, и разрешения записи (Y4) в блок 19 памяти кода, сформированного на его информационном входе ° После пеоеза 3

1465894

14 писк содержимого рег « 14 коI а ода Если на входе блока 12 микропрооперации в N-й раэ я, блок р д а 19 памя- граммного управления отсутств ти б,пок 12 мик оп гэ твует ления гене ет ро рограммного управ- формируемый дешиф ат 20 ерирует микрооперацию (X7) . сигнал (Х ), что означает отсутраз р< шающую очистку регистра 14 ствие основы типа "F>

Затем блок 1> мик оп > р .вления выполняет действия по вво а ропрограммного уп- трех разрядах б 19

>> оп > - — лока памяти г е ия по вводу означает код произвольной операи о ра отке следующей,пексической ци и, то в этом случае в старших

1 э 1О (-2) (-)

Если на выхо, (- ) и N-x разрядах блока 19 на выходе схемы сравнения памяти мог г со. е >. сигнал Х отс тс ь могут содержаться только о .отсутствует,, то блок 12 микропрограммного vnp типа . . обое другое содержиавления анали- мое данных заз я эирует наличие вхо н >

> 1 зрядов свидетельствуичие входного .сигнала (Хб), ет о наличии ошибки во вхо н формируемого дешиф >а > I 3 ратором кодов 15 ражении. В эт < и оши ки во входном выопераций.

>а >,; . ом случае на входе блоЕспи на д б о(а с и на входе блока ка 12 микропрограммного управления с и на д б .о(а 12 микропрограммноrо управления ешиф с гнал o„ формируемый

13 ко а ия дени ратором дешифратором 20 осн П.

3 д операции формируется сигнал ия еши . ос ов. ри этом анализ части входного выражения заве— (Х ), соответствующий очищенному р в ерсостоянию регистра 14, то б шается„ Блок 12 мик ропрограммного выполняет дейстьзия по < о то лок 12 вы- управления вы ает д микрооперацию при".ьзия по ооработке сле- знака ошибочного эа е дующей лексиче ской единицы исходно- ительн ого завершения предваго выражения. р ь ои свертки части исходного выражения. в .канале (Y ). Указ н< .< гнала микрооперация фо ми ю

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

> ов с.-<г>- ал (Хg > „ 30 такте о тех д пор, пока блок 5 микщии наличию в старших трех раз ии н; ропрограммного управления не выдаст

-зрядах блока 19 памяти свграF>> одну из мик сопе

<>Е < У<< вида > х или знаков нормального или ошибочного завершения контроля, форм ю«их

Блок 12 микропрограммного упра:пра:в- входной сигнал (Х ) б

3, .ир ующих пения при наличии на .г

) лока 12 микронала Х; вы ает и на его входе сиг- и огра р < ммного управления. При этом выдает последовательность микроопе.таций генерация микрооперации 7„ прекращаий, осуществляющих сверт- ется б 1" к о я, и лок 1 завершает работ у основы, т.е. замену сочетан

<я ко- П ри наличии в т

У ° дов, о<>разующих осно>зу, кодом one- ах бло рех старших разряранда "Г". Све д . пока 19 памяти кодов„ образуюа . вертка осуществляется щих основ путем выд . б . 2 п ачи локом 1" мик оп о:ову типа (Г), дешифратор 2 .. р програм- 20 основ формирует сигнал (Х ) з много управления микроопераций важ". ал 5, зады разрешения сдвига на один аз я .

: ий дваж- пускающий B блоке 12 мик оп ог р ро рамодин разряд много управления после овате вправо содержимого регистров 21 бло- м д тельность тров ло-, микроопераций, осуществляющих

> . и св ртку ы ° Блок 1 микропрО, а на инфсрмационном граммного и авле входе блока 19 : (Y ), памяти,. 0, ) ПОдклю.оцерации два ы управления выдает микроченном к выходу блока 12 оце ации дважды разрешения сдвига лока < микропроия через комму-,- регистров 21 блока 19 памяти (У татор 17, и разрешения записи сфо — Y ) (.<> и мированного кода в И-й старши"

>ор- р формирования кО а F д (Y3) на ий раз- инфо мап. рмационном входе блока 19 памяПосле выполненных ей . б ти и разрешения з записи сформированного кода в N-й заз я б е1". - б . в -и разряд блока 19 пава анализирует входной сигнал (Х10 ), програмз

<ия сно-,. мяти. После этого блок l2 .> действия по вводу и об для определения возможности све тки ду работке слеобразовавшегося выражения,.

>.и свертки дующей лексической .кой единицы исходного выражения, 17 14 код "F формируется на информацион- ) ном входе блока 19 памяти первого канала, и разрешения записи (Yq4 ) сформированного кода в N-й старший разряд блока 19 памяти первого к нала.

Если в очередном шаге свертки н выходе дешифратора 8 полуоснов, рмируется сигнал (Xrp! ), что соотв тствует наличию в трех старших р эрядах блока 19 памяти второго к нала кодов, образующих основу

" xF" или "F+F" то блок 5 микроограммного управления анализируе наличие входного сигнала (Х) ), ф рмируемого схемой 7 сравнения.

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

При отсутствии на выходе схемы (7)сравнения синала (Xqg} блок микроограммного управления выдает поедовательность микроопераций, осущ ствляющих свертку основы. Выдаютс микрооперации дважды разрешения с вига на один разряд вправо содермого регистров 21 блока 19 памяти . B орого канала (Ygg и Y g) формиро ? 9 в ния кода операнда (Yz ), формир вания на управляющем входе коммут тора 17 второго канала кода "10" 2 (,g ), переключающего выход коммутатфра на его третий вход, и разрешенйя записи (Yqg ) сформированного ф к)>да в Ю-й старший разряд блока 19 памяти второго канала.

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

"P" и второго канала - кодов "Fx" ш и первого канала - кода "(" и второго канала - кодов ")Г", или первого канала - кода "Р" и второr<> канала - кодов "5F+" то блок 5 мйкропрограммного управления производит свертку основы. Блок 5 микропрограммного управления генерирует . ж крооперации разрешения сдвига на о4ин разряд вправо содержимого регис. ров 21 блоков 19 памяти первого (1 6 } и второго (Y

65894 тьем входе коммутатора 17 второго канала (Y }, формирования на упЯ равляющем входе этого коммутатора кода "10" (7„ ) переключения выхода коммутатора 17 на его третий вход резрешения записи кода операнда в старший М-й разряд блока 19 памяти второго канала (Yap). ф

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

"xF+" то блок 5 микропрограммного управления генерирует последовательность микроопераций, осуществляющих совместный сдвиг выражения, о левая часть которого находится в блоке 19 памяти первого канала, а правая часть — в блоке 19 памяти вто)рого канала, на два разряда влево.

Выдаются микрооперации разрешения сдвига на один разряд влево содержимого блока 19 памяти первого канала (Yqq ) формирования на управляющем входе коммутатора 17 первого канала кода "10" (7,8 ) переключения выхода

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

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

Затем выдаются микрооперации разрешении сдвига на один разряд содержимого блоков 19 памяти первого

) канала влево (Y ), второго канала— вправо (Yj ), снова выполняется совокупность микроопераций,осуществляющая перезапись кода из старшего

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

Э

7 4.), и разрешения сдвига на один разряд вправо содержимого блока 19 памяти второго канала (Y, ).

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

19

1465894 выражения.

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

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

"F+" и второго канала — кодов хР то блок 5 микропрограммного управления генерирует последовательность микроопераций, осуществляющих совместный сдвиг выражения, левая часть которого находится в блоке 19 памяти первого канала, а правая частьв блоке 19 второго канала, на один разряд влево.

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

1 вход, разрешения (Y<4 ) записи кода с информационного входа блока 19 памяти первого канала в старшие N-e разряды регистров 21, разрешения .сдвига на один разряд вправо содержимого блока 19 памяти второго канала (Yae)

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

11 н

"Fx" и второго канала — кода F

tt/ 11 или первого канала - кодов (F и второго канала — кода ")", или первого канала кодов "Р+" и второго канала — кодов "$F", то блок 5 микропрограммного управления производит свертку основы. Выдаются мйкрооперации разрешения сдвига на один разряд вправо содержимого блоков 19 памяти первого (Ygg ) и BTopoFG (Ygg ) каналов, формирования кода операнда

"F" на третьем входе коммутатора 17

I первого канала (Y ), формирования на управляющем входе этого коммутатора кода "10" (Y< > ) переключения выхода коммутатора на его третий вход, разрешения записи кода операнда в старший N-й разряд блока 19 па1 мяти первого канала (Yg4 ).

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

25 контроля (Хд ). На этом цикл работы анализатора завершается. устройство готово к анализу следующего входного формулаизобретения

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

14б58 второго и первого каналов синтаксического анализа соответственно, вторые выходы формирования полуоснов которых соединены с вторыми входами второй и первой схем сравнения соответственно, выходы которых соединены с входами признаков приоритета операций s втором и первом канале блока микропрограммного управления, первые и вторые входы признаков об: наружения ошибки и правильной записи . которого подключены к выходам одноименных признаков первого и второго каналов синтаксического анализа со35 ответственно, управляющие входы которых соединены с выходами первой и второй групп блока микропрограммного управления соответственно, вы20 ход признака обнаружения ошибки ко TOPOFO COe HH H 0 H HMeHHb BblXO

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

2. Анализатор по п.1, о т л ич а ю шийся тем, что каждый канал синтаксического анализа содержит дешифратор лексических единиц, инфор30

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

И два блока элементов ИЛИ,, выходы которых соединены с управляющими

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

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

1465894

Фиг.2

Ю

b

:ъ)

1 ъ

) г s

14б5894

1465894

Составитель В.Куленкаап

Редактор И.Келемеш Техред А.Кравчук Корректор В.Романенко

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

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

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

tl fT

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