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

ИН1. Sx. Вход упраЬле- J,

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

Ошибка Успешный

aHQjjus

ОО

СО

О1

со

спешный

aHQjjus

Фиг.

114

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

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

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

Синтаксический анализатор (фиг„ 1) содержит входной регистр 1, дешифра™ тор 2 лексических единиц, блок 3 микропрограммного управления, выполненный , например 5 на программируемых логических матрицах,- шифратор 4, блок 5 памяти, дешифратор 6,

В состав блока 5 входят два реверсивных регистра 7 сдвига о

Входной регистр 1,-дешифратор 2 лексических единиц, шифратор 4 и дешифратор 6 могут быть реализованы известным способом па серийно вып ус- кавмой элементной базе.

Входной регистр 1 используется для хранения очередной лексической единицы исходного выражения. Дешифратор 2 лексических единиц разделяет лексические единицы на. операнды операции, скобки/ конец выражения„

Блок 3 микропрограммного управле

ния (1У1Ш ) управляет работой всех элементов анализатора. Алгоритм его функционирования описан блок-схемой микропрограммного управления (фиг, З где входные сигналы Х1-Х5 формирует дешифратор 2 лексических единиц (сигналы Х2-Х5) образуют группу выходов дешифратора 2 лексических еди- ницд сигнал Х1 подается на выход дешифратора) 5 а Х6-Х8 формирует дешифратор 6, причем на выход дешифратор б подается сигнал Х8, а сигналы Х6 и Х7 - на группу выходов. На выходе блока 3 управления формируются сигналы микроопераций Y1-Y11, а также сигналы микрокоманд YIZ-YIS, являюцщеся совокупностями микроопераций „ Содержательный сг-люл входньк и выходных сигналов следующий: .

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

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

0

5

О

5

0

ХЗ

Х4

Х5

Хб

Х7

Х8

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

исходного выражения есть

операнд;

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

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

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

1, если в трех последних разрядах регистров блока памяти находится код основы F X О в противном случае;

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

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

31А3959

де Y - сброс в ноль регистров 7 блока 5 памяти;

у - ввод следующей лексической единицы во входной регистр 1;

у - сдвиг на 1 разряд влево

(в сторону младших разрядов)

содержимого регистров 7

блока 6 памяти; Q

у. - сдвиг на 2 разряда вправо

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

у - выработка кода терминала 15 открывающая скобка ;

у - выработка кода нетерминала

y-j выработка кода нетерминала

Операция,20

у - выработка кода терминала Закрывающая скобка ;

Уд выработка сообщения Ошибка ;

- выработка сообщения Успеш- 25 ный анализ ;

У(( разрешение записи в блок 5 памяти,

Блок 3 МПУ может быть реализован

на программируемых логических матрицах.

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

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

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

Q

5

0

5

0

0

5

5

0

5

Fla выход дешифратора 6 подается сигнал Х8, который анализируется блоком 3 МЛУ во время поступления знака конца выражения . Сигнал в том случае, когда в старших разрядах регистров 7 блока 5 памяти находится код нетерминала F, а два предыдущие разряда нулевые, что свидетельствует об успешном анализе входного выражения, С группы выходов дешифратора 6 на вторую группу входов блока 3 МПУ поступают сигналы Хб и - Х7 S которые равны единице в том случае, если в последних трех разрядах регистров 7 блока 5 памяти находится код основы F -JS- F или iF) соответственно. Единичное значение любого из этих сигналов свидетельствует о возможности произвести свертку исходного выражения, т.е. как основ F4F или (F) заменить на код

нетерминала F.

I

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

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

Затем блок 3 МПУ вырабатывает микрооперацию Y2 - ввод лексической единицы во входной регистр 1. Лексическая единица поступает на дешифратор 2 лексических единиц и дешифруется дешифратором. Если на вход поступил знак конца выражения , то дешифратор 2 лексических единиц вырабатывает сигнал (), который запускает блок 3 МПУ от дешифратора 6. Если Х8 1, т.е. в старшем разряде регистров 7 блока 5 памяти находится код нетерминала F, а два предыдущие разряда нулевые, то блок 3 МПУ вырабатывает микрооперацию Y10 - Успешный анализ и алгоритм заканчивает свою работу. В . противном случае (если Х8 0) блок 3 МШ вырабатывает микрооперацию Y9 - Ошибка и алгоритм заканчивает свою работу.

Если же входная лексическая единица есть не знак конца выражения , то дешифратор 2 лексических единиц вырабатывает сигнал XI 0, который запускает блок 3 МПУ на выработку микрооперации сдвига влево на 1 разряд содержимого регистров 7 блока 5 памяти (микрооперация Y3) и на анализ входного сигнала Х2.

5U395916

Если Х2 1, т.е. входная лекси- рооперацию ввода следующей лексической ческая единица есть открывающая скоб- единицы во входной регистр 1.

:ка,, то блок 3 МПУ вырабатывает последовательность микроопераций выработки кода открывающей скобки шифратором 4 и записи этого кода в блок 5 памяти (сигнал Y12), Затем блок 3 ГШУ про,изводит анализ возможности свертки исходного выражения.

Блок 3 Miiy анализирует входной сигнал Хб, поступающий от дешифратора 6 на 2 гр.вх.блока 3 МПУ. Если Х6 1, Тов. в трех последних разрядах регистров 7 блока 5 памяти находится код основы , то блок 3 ШУ вырабатывает последовательность мик-; рокоманд Y4 . и Y13,, в результате выполнения которых происходит сдвиг

содержимого регистров 7 блока 5 памяг- 20 дешифрирует текущую лексическую едити на два разряда вправо, выраоотка : кода нетерш нала F шифратором 4 и запись этого кода в блок 5 памяти. Затем опять проверяется возможность свернуть исходное выражение, т,е, .блок 3 ЫШ проверяет входной сигнал Х6, Если Х6 О, то а нализируется входной сигнал Х7. В случаеj если Х7 I, т„е. в трех последних разрядах регистров 7 блока 5 памяти находится код основы F, блок 3 МПУ вырабатывает описанную последователь- ность микрокоманд (4, Y13), проводится свертка исходного выраже- ния (код основы (F) заменяется ко- ; дом нетерминала F), К опять про- I веряется. возможность свернуть исход- : Ное выражение и проводится свертка до тех nopj пока входные сигналы.

3 ШУ. Если есть знак

ницу и запускает олок лексическая единица не конца выражения (), блок 3 МПУ вырабатывает микрооперацию сдвига

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

30 работка кода терм лкала Закрызаюша скобка шифратором 4 и запись этог кода в блок 5 памяти. После чего происходит отра.ботка алгоритма све ки и ввода следующей лексической е

„.- ницы исходного вырал ения. 5

Лексическая единица дешифруется

дешифратором 2 лексических единиц запускает блок 3 ЮТУ. Если эта лек ческая единица не есть знак конца

Х6 и Х7 не примут нулевые значения, 40 выражения (Х1 0), то блок 3 МБ

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

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

Если лексическая единица есть опе- :ранд (ХЗ 1) то блок 3 ЖУ вырабатывает микрокоманду Y13s т.е« происходит выработка кода нетерминала F шифратдром и запись этого кода в блок 5 памяти. Затем блок МПУ анализирует возможность свертки по описанному алгоритму. После выхода из этого .алгоритма блЬк 3 МПУ вырабатывает микЕсли эта лексическая единица не есть знак конца выражения (XI 0), блок 3 МПУ выдает микрооперацию сдвига влево на 1 разряд содержимого регистров 7 блока 5 памяти (микроопе- рапия Y3).

Если лексическая единица есть операция (Х4 1), то блок 3 МШ вырабатывает микрокоманду Y145 т,е происходит выработка кода нетерг-шнала Операция шифратором 4 и запись этоТо , кода в блок 5 памяти. Затем происходит отработка алгоритма свертки и ввод следующей лексической единицы исходного выражения.

Дешифратор 2 лексических единиц

3 ШУ. Если есть знак

ницу и запускает олок лексическая единица не конца выражения (), блок 3 МПУ вырабатывает микрооперацию сдвига на

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

Лексическая единица дешифруется

дешифратором 2 лексических единиц л запускает блок 3 ЮТУ. Если эта лексическая единица не есть знак конца

вы.рабатывает микрооперацию сдвига на 1 разряд влево содержимого регистр(эв

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

8случае, если эта лексическая едиии- 45 Ца, есть ни открывающая скобка (Х2 0),

ни операнд (ХЗ 0), ни операция (Х4 0) и ни закрывающая скобка (Х5 0), то блок 3 fffly выдает сообщение об ошибке (микрооперация Y9) ., gQ и алгоритм завершает свою работу. Пример 1. Пусть исходное выражение имеет вид:

а + (Ь - с) + d 1,

а, Ь, с, d - онеранды;

-I-, - - знаки операции; - символ конца выражения ,

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

- код операнда; код операции;

( - код открывающей скобки;

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

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

F

а

(Ь - с) + с .

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

Пример 2, Пусть исходное выражение имеет вид а + (Ь - с)) , которое содержит ошибку - имеется лишняя закрывающая скобка.

Процесс синтаксического анализа описан в пошаговом режиме в табл. 2.

На 21-м шаге анализатор закончил свою работу с выдачей сообщения Ошиб- :ка, так как в старших разрядах регист ров 7 блока 5 памяти находится код закрывающей скобки (Х8 0).

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

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

Y3, Y13

Y2

XI, Х2,

Y3, Y14

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

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

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

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

Таблица 1

памяти

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

F

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

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

11

Х1,

1439591

Y1, Y2

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

Y3, Y13

Свертка

Свертка (F) Свертка

Ошибка

.y,g

вт utiiffHf fcf o4

С начала

Фие.3