Синтаксический анализатор

 

Изобретение относится к вычислительной технике и может быть использовано в автоматизированньпс системах .обработки данных и производства программ ЭВМ. Цель изобретения - повьппение достоверности синтаксического контроля при одновременном повышении быстродействия и сокращении аппаратурных затрат. Для достижения указанной цели в устройство дополнительно введены дешифратор 6 и шифратор 4. Введение указанных элементов и порождаемых ими связей в сочетании с реализацией блока 5 памяти на реверсивных сдвигающих регистрах, а также с усовершенствованными алгоритмами 1|)ункдионирования блока 3 микропрограммного управления позволяет реализовать указанные преимущества и осуществить полный синтаксический анализ входных выражений. 3 ил., 2 табл. а € Л

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

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

РЕСПУБЛИК (19) (112

Уход уар

ЮЯ 30/N

Ошибки" "9саеаный ан7Лигм

Фиг.!

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4218703/24-24 (22) 01,04.87 (46) 23. 11,88, Вюл. Р 43 (72). В.К.Водопьянов, С.П. Зайцев, В.Н.Волков, Г.В,Назарьян и И.A.Îðëîâ (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 637818, кл. G 01 Г 11/00, 1978.

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

Р 1l30879, кл, С 06 F 15/38, l984. (54) СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР (57) Изобретение относится к вычислительной технике и может быть использовано в автоматизированных смстемах обработки данных и производства прог(5D 4 С 06 F 11/00 15/38 рамм 3ВН. Цель изобретения — повышение достоверности синтаксического контроля при одновременном повышении быстродействия и сокращении аппаратурных затрат. Для достижения указанной цели в устройство дополнительно введены дешифратор 6 и шифратор 4.

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

Я входных выражений. 3 ил., 2 табл.

1439591

Х2 1Q

Х7

Изобретение относится к вычисли-! тельнои технике и может быть использовано в автоматичированных системах обработки данных и производства программ ЭВИ.

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

На фиг, 1 представлена структурная схема. синтаксического анализатора; на фиг, 2 -. структурная схема блока памяти; на фиг, 3 — блок-схема микропрограммного управлени синтакСИИE:ÑÊHÌ аНаЛИЗатоРОМ.

Сии такси -1еский анализ з тор (фи1 1 }

ooäepIêFIò входнОй регистр 1, дешифра" тор 2 лексических единив., блок 3 микропрограммноГО управления выпОл пенный, например, на программируемых логических матрицах,- шифратор 4, блок 5 памяти, дешифратор 6, Б сООТВН блока 5 памя TH BllopHT )Iва 25 ревеpc:кэных pегисTpB ? O,ТвигB

Входной регистр 1, дешифратор 2 лек ичес.ких единиц, шифратор 4 и дешифратор 6 могут быть реализованы известным способом IIB. серийнО Выпу! 3Q каемой элементной базе, Входной регистр 1 используется для хранения очередной .".:Bêoè÷eñêoé единицы исхоцного выражения. Дешиф-ратор 2 лексическ.:Ix единиц разделяет лексические ециницы на операнды, Операции, скобки, конец выражения.

Блок 3 микропрограммногo управле40 ния (МНУ) управляет работой всех элементов анализатора. Алгоритм егo функционирования описан блок--схемой микропрограммного управления (фиг. 3), где входные сигналы Х1-Х5 формирует дешифратор 2 лексических единиц (сигналы Х2-Х5) образуют группу выходов дешифратора 2 лексических единиц, сигнал Х1 подается на выход дешифратора), а Хб-Х8 формирует дешифратор 6, причем на выхоц дешифратора 50 б подается сигнал X8 а сигналы Хб и Х7 — на группу выходоь. На выходе блока 3 ИПУ управления формируются сигналы микроопераций 71-У11, а также сигналы микрокоманд 712-715, являющиеся совокупностями микроопераций. Содержательный смысл входных и выходных сигналов следующий:

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

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

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

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

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

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

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

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

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

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

1, если в трех последних разрядах регистров блока памяти находится код основы ГхГ

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

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

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

"Г"; а два предыдущих разХЯ = 1>яда нулевые;

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

У< т

Y2 = y,;

Y3 v

„) У

74 = у, 75 = у

Y6=у

Y7 — у7 у

Y8 = ув, У9 У99

7 1 0

Y11 = yI, У12 =(у: - у

У14. =(у, у1, 1

715 =(б, у1, .

1439591 где

- и у

20 уб у ю

У<» сброс в ноль регистров 7 блока 5 памяти; ввод следующей лексической единицы во входной регистр 1; сдвиг на 1 разряд влево (в сторону младших разрядов) содержимого регистров 7 блока 6 памяти; сдвиг на 2 разряда вправо (в сторону старших разрядов) содержимого регистров 7 блока 5 памяти; выработка кода терминала

"открывающая скобка"; выработка кода нетерминала "F"; выработка кода нетерминала

"Операция", выработка кода терминала

"Закрывающая скобка"; выработка сообщения

"Ошибка"; выработка сообщения "Успешный анализ ; разрешение записи в блок 5 памяти, Блок 3 МПУ может быть реализован на программируемых логических матрицах.

Шифратор 4 формирует коды терминалов "Открывающая скобка", "Закрывающая скобка" и нетерминалов "Операния", "Г" †опера.

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

Блок 5 памяти представляет собой память с безадресным принципом записи и чтения и может быть выполнен на двух реверсивных сдвигающих регист рах 7. Запись терминалов и нетерминалон производится в старшие N-e разряды регистров 7 (фиг. 2). Выходы последних трех разрядов регистров 7 образуют группу выходов, связанную с группой входов дешифратора б. Реверсивные регистры 7 блока 5 памяти поразрядно сдвигают коды терминалов и нетерминалон, причем сдвиг вправо на два разряда равносилен затиранию последних двух записанных кодов.

Дешифратор 6 вырабатывает входные сигналы Хб-Х8 по анализу информации, находящейся в трех старших разрядах регистров 7 блока 5 памяти.

На выход дешифратора б подается сигнал Х8 который анализируется блоком 3 ИПУ во нремя поступления знака конца выражения ф . Сигнал

Х8=1 в том случае, когда в старших разрядах регистров 7 блока 5 памяти находится код нетерминала Е", а два предыдущие разряда нулевые, что свидетельствует об успешном анализе входного выражения. С группы выходов дешиФратора 6 на вторую группу входов блока 3 МПУ поступают сигналы Хб и

Х7, которые равны единице н том случае, если в последних трех разрядах регистров 7 блока 5 памяти находится код ОснОВы "1 + Е" или "(F)" соответственна. Гдиничное значение любого из этих сигналов свидетельствует а вазможности произвести свертку исходнага выражения, т.е. как основ

"F.» 1 " или "(Г) заменить на код нетерминала Г н, l1

Анализатор работает следующим образам.

На первом шаге блок 3 МПУ вырабатывает микраопергцию Y1 — сброс н ноль содержимого регистров 7 блока 5 памяти.

Затем блок 3 МПУ вырабатывает мик" рооперацию Y2 — ввод лексической единицы но входной регистр 1, Лексическая единица поступает на дешифратор 2 лексических единиц и дешифруется дешифратором. Если на вход поступил знак конца выражения "ф, то дешифратор 2 лексических единиц вырабатывает сигнал (Х1=1), который запускает блок 3 МПУ от дешифратора 6.

Если Х8 = 1, т.е. н старшем разряде регистров 7 блока 5 памяти находится код нетерминала "Р", а цва предыдущие разряда нулевые, то блок 3 МПУ вырабатывает микроаперацию 710 — "Успешный анализ" и алгоритм заканчивает свою работу. В противном случае (если

Х8 = 0) блок 3 МПУ вырабатывает микрооперацию Y9 — "Ошибка" и алгоритм заканчивает свою работу.

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

"Ф, то дешифратор 2 лексических единиц вырабатывает сигнал Х1 = О, который запускает блок 3 %ТУ на выработку микрааперации сднига влено на 1 разряд содержимого регистров 7 блока 5 памяти (микрооперация Y3) и на анализ входного сигнала Х2.

39591

10

25 1 разряд влево содержимого регистров

"7 блока 5 памяти, Если лексическая а + (Ь вЂ” с) +с1ф, где а, Ь, с, d операнды; знаки операции; символ конца выра-жения.

5 14

Если Х2 = 1, т.е, входная лексическая единица есть открывающая скоб:ка, то блок 3 КПУ вырабатывает последовательность микроопераций выработки кода открывающей скобки шифратором 4 и записи этого кода в блок 5 памяти (сигнал 712) . Затем блок 3 МПУ производит анализ возможности свертки исходного выражения.

Блок 3 ИПУ анализирует входной сигнал Х6, поступающий от дешифратора

6 на 2 гр.вх.блока 3 ИПУ, Если Хб = 1, т.е. в трех последних разрядах ре" гистров 7 блока 5 памяти находится код основы "Г Ф Г", та блок 3 МПУ вырабатывает последовательность микрокоманд 74, и 713, в результате вы-. полнения которых происходит сдвиг содержимого регистров 7 блока 5 па(.(5(ти на два разряда вправо, выработка негерминала Г ((п(фратороь(4 H зались этого кода в блок 5 памяти.

Затем опять проверяется возможность свернуть исходное выражение, т.е. блок 3 МПУ проверяет входной сигнал

Х6. Если Х6 = О, то анализируется входной сигнал Х7. В случае, если

Х7 -- 1, т.е.. в трех последних разрядах регистров 7 блока 5 памяти находится ксд о новы "Г", блок 3 2ХПУ вырабатывает описанную последователь ность микрокоманд (74, 713), т.е. проводится свертка исходного выражения (код основы,(Г) заменяется ко- дом нетерминала Е ), И опять про-* веряется воэможность свернуть исходное выражение и проводится свертка до тех пор, пока входные сигналы

Хб и Х7 не примут нулевые значнния.

После этого блок 3 МПУ вырабатывает микробперацию ввода следующей лексической единицы исходного выражения во входной регистр 1 (72).

Если лексическая единица ие,есть знак конца выражения (Х1 =- О), то блок 3 МПУ вырабатывает микрооперацию сдвига на 1 разряд влево содержимого регистров 7 блока 5 памяти (микрооперация 73).

Если лексическая единица есть опе.ранд (ХЗ = 1), то блок 3 ИПУ выраба.— тывает микрокоманду 713, т.е. происходит выработка кода нетерминала "Г" шифратором и запись этого кода в блок

5 памяти. Затем блок ИТ(У анализирует

l возможность свертки по описанному алгоритму. После выхода из этого алгоритма блЬк 3 ЙПУ вырабатывает микрооперацию ввода следующей лексической единицы во входной регистр 1.

Если эта лексическая единица не есть знак конца выражения (Х1 = С), блок 3 МПУ выдает микрооперацию сдвига влево на 1 разряд содержимого регистров 7 блока 5 памяти (микрооперапия 73), Если лексическая единица есть операция (X4 = 1), то блок 3 2"(ПУ вырабатывает микрокоманду 714, т.е, происходит выработка кода нетерминала и и .Операция шифратором 4 и запись это го . кода в блок 5 памяти. Затем происходит отработка алгоритма свертки и ввод следующей лекси(еской единицы исходного выражения.

Дешифратор 2,лексических единиц де1((ыфрирует текущую лексическую единицу и запускает блок 3 2 ((ТУ, Если лексическая единица ((e есть знак конца выражения (Х!=О), блок 3 МПУ вь(рабать(вает ми(.роопераци(0 сдвига на единица есть закрывающая скобка (X5 =1)„ то блок 3 ИТУ вырабатывает мчкрокоманду 715, т.е, происхоцит выработка кода терм1(нала Закрывающая скобка" шифратором 4 и запись этого кода в блок 5 памяти. После чего происходит отработка алгоритма свеDT ки и ввода следующей лексической единицы исходного выражения.

Лексическая единица дешифруется дешифратором 2 лексических единиц я запускает блок 3 МПУ. Если эта лек"иеская единица не есть знак конца выражения (Х1 =- О?, то блок " 2ПТУ вырабатывает микрооперацию сдвига:(а

1 разряд влево содержимого регистров

7 блока 5 памяти (микрооперация 73) .

В случае, если эта лексическая единица, есть ни открывающая скобка (Х2 = О), ни операнд (ХЗ = О), ни операция (Х4 = О) и ни закрывающая скобка (X5 =- О), то блок 3 %ТУ выдает сообщение об ошибке (микрооперация 79?, и алгоритм завершает свою работу.

JI р и м е p t, Пусть исходное выражение имеет a»p:

1439591 атора редволы, знавыраа + (b — с) + с Ф.

Таблица 1.

Примечание

Содержимо старших разрядов регистров

7 блока 5

Задейство-, ванные выходные сигналы регист ра 1 памяти

Обнуление блока 5 памяти

2 а Х1, Х2=0

Х3=1

Y39 У13

Запись кода операнда

3 а Хб, X7=0

У2

УЗ, У14

Запись кода операции

Для наглядности работу анализ опишем по укрупненным шагам, п ставленным в табл. 1, причем сим использованные в колонке 5, обо чают следующее:

F — " код операнда;

+ — код операции; (— код открывающей скобки;

) — код закрывающей скобки.

На вход устройства поступает жение

Таким образом анализатор завершил работу на 24-м mare с выдачей сообщения Успешный анализ (микрооперация У10) .

Пример 2. I .óñòü исходное выражение имеет вид а + (Ь вЂ” с)) которое содержит ошибку — имеется лишняя закрывающая скобка.

Процесс синтаксического анализа описан в пошаговом режиме в табл. 2, На 21-и mare анализатор закончил свою работу с выдачей сообщения "Ошиб ка", так как в старших разрядах регистров 7 блока 5 памяти находится код закрывающей скобки (Х8 = О), формула изобретения

Синтаксический анализатор, содержащий входной регистр, дешифратор

Содер Состояние

Шаг жимое задействованных вход- входных сигнало ного

4 + Х1, Х2, Х3 О

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

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

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

З5 блока микропрограммного управления соответственно.

Проход алгоритма сверт-ки и ввод логической единицы

1439591

1 2

5 + Хб, X7=0

6 (Хi 0, Х2 1

Запись кода

УЗ, У12

7 (Хб, Х7 О

У2

8 Ь Х1, Х2=0

Х3--1

Г«(Г

УЗ, У13

Г»(Р

F «(F»

Хб, Х7=0

У2

М1, Х2,ХЗ О

Х4=1

УЗ, У14

Хб,Х7=0

Р«(Р «

F 4(F«F

Х1, Х2=0

X3-=1

УЗ, У13

Х6--1

У4, У13

Хб,Х?=О

Р»(Р

Х1 =X4=0

X5-=1

F«-(F) У3, У15

16 )

17 )

18 )

l9 +

Хб=О X7=1

У4, У13

У4, У l3

F«F

Х6=1

Хб,Х7=0

Y.2

Х1 Х2 X3=0

X4=1

УЗ, У14

Хб,Х7=0

У2

ГФ

Х1,X2=0

X3-=1

Уз, У13

22 d Х6=1

У4, У13

У2

24 Ф Х1,X8-=1

У10

13 с !

4 с

15 ) d Хб,Х7=0

Прополжение ra5J:, 1

Запись кода открывающей скобки

F«(F Свертка F»F -+Г

Свертка (Г) F

Свертка Р 4- Г F

Свертка F«F F

"Успешный анализ"

1439591

Содержимое

Задействованные выШаг ходные сиг налы входного регист ра 1 памяти

71, 72

У3, У13

Х1,Х2=0

Х3=1

Хб,Х7=0

У3, У14

Х1,Х2,ХЗ=О

Х4=1

Хб,Х7=0

Y3,У12

Xi=0 X2=1

F«(72

Хб,Х7=0

Р-а(Р

Х1 X2=0

X3-=1

УЗ, 713

F4(F

Хб,Х7=0

Г«(Г«

73, Y 14

Х1 Х2 ХЗ-0

Х4=1

Хб,Х7=0

УЗ,Y13

Xi,Х2=0

X3=1

1

Г+(Р Свертка Р Г-р

74,713

Х6=1

F+(F

Х6 X7=0

14

F+(F) У3, 715

Х1-Х4=0

Х5--1

Г+Р Свертка (F)-+ F

F Свертка

Х7=1, Хб=О

Х6=1,17

Хб,Х7=0

У3, 715

Хб,Х7=0

F) "Ошибка"

Х1=1, Х8=0

Состояние задействованных. входных сигналов

Х1-Х4=0 Х5=1

74, У13

74,Y13

Содержимо старших разрядов регистров

7 блока 5

F«(F IFW(FwF

Таблица 2

Примечайие

Обнуление блока 5 памяти

1439591

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

Редактор А. Ворович Техред M.Õoäàíè÷ Корректор М. Шароши

Заказ 6078/48

Тираж 704 Подписное

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

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

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