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

13

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

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

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

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

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

В состав блока 5 памяти входит группа реверсивных регистров 11 сдвига.

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

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

Блок 3 управления управляет работой всех элементов устройства. Пример его функционирования для операции + и х описан блок-схемой микропрограммного управления (фиг. З), гд входные сигналы X, s -9 Формируе

492

дешифратор2 лексических единиц, Х. - дешифратор7 приоритетов; ХтХ.Х,р - дешифраторкодов операции; X,., - дешифратор аксиомы. На выходе блока 3 управленияфог)мируются сигналы микроопераций YY ,...,Y и Y , а так-

у Y Y Y Y

1 2 S 6 14

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

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

же сигналы Y Y,

X.

0

15

5

о

Q

-

35

45

50

X

X,

Хе

X,

X.

X.

X,

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

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

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

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

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

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

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

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

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

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

1, если приоритет терминала, занесенного в N-e разряды блока 5 памяти, больше приоритета терминала, находящегося в () разрядах блока памяти;

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

1, если терминал в (N-l) разрядах блока 5 памяти, I есть код знака плюс;

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

1, если терминал в (N-l) разрядах блока 5 памяти есть код знака ум - ожить;

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

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

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

X

10

11

1, если терминал в (N-i) разрядах блока 5 памяти, есть код открывающей скобки;

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

1,если в сумматоре содержится код нетерминала F

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

YI YI . У. , У. , У., У-1; Y,

10

ь 1У1 УЗ У, У4 У«1 2

fyi У4 Y/ у,,; V; у fy« У,, J; Y, у, yj Уи ; Vg у,, ; УЭ у ; У,„

у,э ;Л

- г ; - ; з 1с

Jy9. Y, у, у, у. У

15

1; Y,,

у

t2

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

(нетерминала) в накапливающем сумматоре-вычитателе 9, поступающего из буферного регистра 8; у - запись кода терминала От20

25

крывающая скобка в блок 5 памяти;

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

б

-запись кода нетерминала F в буферный регистр 8;

-запись кода нетерминала основы FxF в буферный регистр 8;

-вычитание кода нетерминала основы из содержимого накапливающего сумматора-вы - читателя 9;

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

-запись кода нетерминала основы

в буферный ре

гистр 8;

-запись кода нетерминала основы F+F в буферный регистр 8;

-сдвиг на 1 разряд .вправо содержимого блока 5 памяти;

-выдача сообщения Ошибка ;

-сдвиг на I разряд влево содержимого блока 5 памяти;

-запись кода терминала Знак плюс в буферный регистр 8;

10

15

0

5

0

5

0

5

0

5

у - запись кода терминала Знаь умножить в буферный регистр 8; у, - запись кода терминала Знак

плюс в блок(5 памяти; у - запись кода терминала V3HaK

умножить в блок 5 памяти; у - запись кода терминала - Закрывающая скобка в блок .5 памяти;

у - запись кода терминала Конец исходного выражения (знак в блок 5 памяти. Шифратор 4.основ формирует коды терминалов и нетерминалов.

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

Реверсивные регистры 1I сдвига блока 5 памяти поразрядно сдвигают коды терминалов и совместно с дешифратором 7 приоритетов осуществляют сравнение приоритетов терминалов, а также совместно с дешифратором 6 кодов операций производят выбор основы для свертки исходного выражения.

Буферный 8 регистр используется для хранения кодов терминалов и нетерминалов.

Накапливающий сумматор-вычитатель 9 вьшолняет либо -функцию сложения кодов терминалов и нетерминалов, либо функцию вычитания кодов нетерминала оснЬв.

Дешифратор 10 аксиомы выделяет код нетерминала . F, определенньш в качестве начального нетерминала (или аксиомы) и соответствующего успешному завершению синтаксического анализа.

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

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

При поступлении лексической единицы, например, открывающей скобки (Xj О, X, 1) дешифратор 2 лексических единиц запускает блок 3 управления, который вырабатывает совокупность микрооперации (У,). Управляющие сигналы с блока 3 управления по1.334149

ступают на вход шифратора 4 основ и формируют код терминала, открывающей Ькобки, а затем разре1П ают запись кода терминала в буферный регистр 8 (микрооперация у. ) и сложение его с содержимым накапливающего сумматора- вычитателя 9 (микрооперация у), а также осуществляют сдвиг на 1 разряд влево содержимого блока 5 памяти (микрооперация у ), запись в N-e разряды блока 5 памяти кода терминального символа и разрешает чтение следующей лексической единицы из выходного регистра 1 (микрооперация

у,)..

Если следующая лексическая единица есть операнд (Xj Os Х О, Xj l), то блок 3 управления вьтол няет совокупность микрооперации (У YJ): на шифраторе 4 основ формируется код нетерминала F, производится запись кода нетерминального символа F в буферный регистр 8 (микрооперация Ус) происходит сложение содер- жимого накапливающего сумматора-вы- читателя 9 и кода, выполняется сдвиг на 1 разряд влево содержимого блока

5 памяти(микроопера1 ;ня У.,) и вырабатывается- разрешаюп1ий сигнал на чтение очередной лексической единицы из входного регистра 1, Если лексическая единица; не опе рация (Х О, Х/ о), то происходит формирование сигнала ( ) , сообщс1.ющего об ошибке

После записи кода терминала в старшие разрядь реверсивных регистров сдвига блока 5 памяти, содержимое N-X и (N-l)-x разрядов поступает на дешифратор 7 приоритета,-который формирует логический сигнал отношения приоритетов текущего терминального символа и предшествующего. Если код терминала, занесенный в М-е разряды реверсивных регистров сдвига блока 5 памяти, имеет приоритет меньший или равный приорк тету кода терминала, занесенного в (N-l)-e разряды .(Xj 0), то код терминала с (N-l)-x разрядов блока 5 памяти поступает на вход дешифратора 6 кедов операции,, который формирует.сигнал, определяющий вид основы для свертки исходного вьфажения. Депшфратор б кодов операции запускает блок 3 управления, ко- торый разрешает выполнение сигналов (Y,). Если в (N-)-X разрядах реверсивных сдвигающих регистров находится, например, код терминала

5i

5

Знак плюс (Х О, Xj ), то в буферный регистр 8 записывается код нетермингзла основы F+F (микрооперация у ), затем из содержимого накапливающего сумматора - вычитателя 9 вычитается код нетерминала основы (микрооперация у ), а в буферный регистр 8 заносится код нетерминала F (микрооперация У,)9 после чего производится сложение кода нетерминала с содержимым накапливающего сум- матора-вычитателя 9 (микрооперация у ) и осуществляется сдвиг на 2 разряда вправо содержимого реверсивных сдвигающих регистров блока 5 памяти . (микрооперация у), Сигнал с дешифратора 2 лексических единиц, соответствующий текун5ей .пексической единице,

0

0

0

5

0

например, знаку плюс

(Ху О, Хэ О,

Xj 1), инициирует блок 3 управления, управляющие сигналы которого разрешают сдвиг на 1 разряд влево содержимого реверсивньк сдвигающих регистров блока 5 памяти и вьшолнение совокупностей микрооперации (Y, У).

Если код терминала, занесенный в N-e разряды реверсивных сдвигающих регистров блока 5 ггамяти, имеет боль- П1ий приоритет., чем код терминала, содержащийся в (N-l)-x разрядах .X, 1 5 то дешифратор 7 приоритетов не разрешает прохождение на блок 3 управления сигнгала с дешифратора 6 кодов операции Содержимое блока 5 памяти (сдвигаемых) сдвигается на 1f- разряд вправо., код терминала выталкивается из N-X разрядов в реверсивных регистрах сдвига (микрооперация у ) , блок 5 памяти подготавливается к .приему кода терминала (Yj): содержимое блока 5 пгшяти сдвигается влево на 1 разряд (микрооперация У j)« Текущая .лексическая единица с дешифратора 2 с помощью блока 3 управления формирует код терминала, кот орый заносится .в буферный регистр 8 и блок 5 памяти, добавляется к содержимому накапливающую сумматора-вычитателя 9, а затем происходит переход к очередной лексической единице.

Ес.пи следующая лексическая единица есть закрывающая скобка (Хj О, Хф О, Xf i). То дешифратор 2 лексических единиц запускает блок 3 управления, управляющие сигналы которого разрешают формирование на шифраторе 4 основ кода тевминала Закры- в;1ющая скобка и запись кода терми5

1

нала в блок 5 памяти (микрооперация у ), откуда код терминала поступает также на вход дешифратора 7 приоритетов. Дешифратор 7 приоритетов разрешает (Xg о) прохождение сигнала с дешифратора 6 кодов операции, ко- торьй определяет выбор вида основы. Если в (N-I)-X разрядах реверсивных регистров сдвига находится, напри- мер, код терминала Открывающая скобка (Х О, Хд 0, Х 1), то дешифратор 6 кодов операции возбуждает блок 3 управления, выходные сигналы ( 15 которого выполняют запись нетерминала основы (р) в буферный регистр 8 (микрооперация у,), разрешает чтение очередной лексической единицы из выходного регистра 2 (микрооперация У) вычитание из содер- жимого нак.апливающего сумматора-вычи тателя 9 кода нетерминала основы (микрооперация затем в буферный регистр 8 заносится код нетерминала F (микрооперация у ), производится сложение содержимого накапливающего сумматора-вьгчитателя 9 с кодом нетерминала (микрооперация У2) и осуществляется сдвиг на 2 разряда вправо содержимого реверсивных сдвигающих регистров блока 5 памяти (микрооперация Уд). Если текущая лексическая единица есть закрывающая скобка X

, то дешифратор 2 лексических единиц запускает блок 3 управления, который выполняет (Yj) сдвиг на 1 разряд влево содержимого реверсивных сдвигающих регистров (микрооперация ), а затем на шифраторе 4 основ происходит формирование кода термина- ла Закрывающая скобка и запись (Yg) кода терминала в блок 5 памяти (микрооперация Y j ). Далее работа устройства повторяется.

Если очередная лексическая едини- ца есть конец выражения # (Xj 0., Х О, Xj О, Х5 1), то дешифратор 2 лексических единиц запускает блок 3, выходные сигналы которого разрешают шифратору 4 основ формиро- вания кода терминала Конец выражения и запись (Y,J,) кода терминала в старшие разряды реверсивных регистров сдвига блока 5 (микрооперация у ). С.блока 5 памяти коды терминалов из N-ro и (N-l)-ro разрядов реверсивных регистров сдвига поступают на дешифратор 7 приоритетов, с которого снимается сигнал (Х ( 0),

5 0 5 о

5

0

ц Q

5

49° .

разрешающий прием сигнала от. дешифратора 6 кодов операции, которь1Й анализирует код терминала, содержащийся в (N-I)-X разрядах реверсивных сдвигающих регистров, и формирует сигнал выбора вида основы. Если выбрана несуществующая основа (Х-, О Xg О У о) , то в блоке 3 управления формируется управляющий сигнал вьща- чи ошибки (Y,J ). Если, например, выбрана основа FxF (Х, 1), то блок 3 управления формирует выходные сигналы (Y , Y ), которые опреде,- ляют последовательность работы устройства. Далее дешифратор 2 лексичес- ких единиц анализирует текущую лексическую единицу - конец выражения i( (Xj О Xg l) - и запускает блок 3 управления, который передает на вход дешифратора 10 аксиомы содержимое сумматора - вычитателя 9. Если в накапливающем сумматоре-вычитателе 9 находится код нетерминала F (х 1), то дешифратор 10 аксиомы возбуждает в блоке 3 управления сигнал, по которому процесс синтаксического анализа завершается успещно. Если содержимое накапливающего сумматора-вы- читателя 9 отлично от кода нетерминала F ( 0), то дешифратор 10 аксиомы возбужает бпок 3 управления, управляющие сигналы которого формируют сигнал ошибки (Y).

I. .

Пример 1. Пусть входное выражение имеет вид (А + (в + С)) «

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

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

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

13

лексической единицы исходного выражения.

Лексическая единица А дешифриру ется дешифратором 2 как операид (Xj « 1) и выдается сигнал на запуск блока 3 управления, который разрешает формирование на шифраторе 4 основ кода нетерминала F, заносит его в буферный регистр 8, суммирует содер- жимое накапливающего сумматора-вычи- тателя 9 с кодом нетерминала, производит сдвиг на один разряд влево содержимого блока 5 цамяти и снимает блокировку с входного регистра 1, с которого поступает очередная лексическая единица +.

Дешифратор 2 лексических единиц распознает ее как операцию (Х 1) и возбуждает блок 3 управления, ко- торый запускает шифратор 4 основ, формирующий код терминала Знак плюс записываемый в буферный регистр 8 и в N-6 разряды реверсивных сдвигающих регистров блока 5 памяти, проис- ходит сложение кода терминала с содержимым накапливающего сумматора- вычитателя 9. Код терминала (+) Знак плюс с раэТрядов и код терминала Открывающая скобка с (N-1)разрядов реверсивные регистров сдвига поступает на дешифратор 7 приоритета. Так как приоритет терминала Знак плюс больше приоритета терминала Открывающая скобка (Х 1), то дешифратор 7 приоритетов блокирует запуск дешифратора 6 кодов операции блока 3 управления, которы разрешает ввод и анализ следующей .лексической единицы (.

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

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

910

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

Поступившая на дешифратор 2 лексическая единица, +, есть операция (Х% l). Блок 3 управления на шифраторе 4 основ формирует код терминаа Знак плюс и записывает его в старшие разряды блока 5 памяти, откуа код терминала поступает также на дешифратор 7 приоритета, на второй вход которого поступает из (N-l)-x разрядов блока 5 памяти код терминала Открывающая скобка, Дешифратор 7 (Х 1) блокирует прием сигнала с дешифратора 6 кодов операции блоком 3 управления. В блоке 5 памяти производится сдвиг на один разряд вправо содержимого реверсивных сдвигающих регистров, а затем сдвиг содержимого блока 5 памяти влево на 1 разряд, Дешифратор 2 дешифрирует текущую лексическую единицу + (Xj 1) и запускает шифратор 4 основ, с которого код терминала (+) Знак плюс од- повременно заносится в буферный ре- 8 и блок 5 памяти, а затем . складывается содержимым накапливающего сумматора-вычитотеля 9. После зто- го происходит считывание очередной лексической единицы с входного регистра 1 ,

Лексическая единица С - операнд, который формирует на шифраторе 4 код нетерминала F . Код нетерминала записывается в буферный регистр 8, и одновременно, сдвигается содержимое блока 5 памяти влево на один разряд, затем код нетерминала суммируется с содержимым накапливающего сумматора- вычитателя 9.

Очередная лексическая единица )г поступает на дешифратор 2 и определяется как закрывающая скобка, блокируется входной регистр 1,. формируется код терминала Закрывающая скобка, который записывается в блок 5 памяти и поступает на дешифратор 7 приоритетов, который по приоритетам кодов текущего (Закрывающая скобка) и предыдущего (Знак плюс) терминалов формирует сигнал (Х О), разрешаю- П5ИЙ выбор вида основы свертки. Дешифратор 6 кодов операции по коду предыдущего терминала определяет вид основы -(Xg )„ Код нетерминала осиоII1

вы F+F заносится в буферный регист 8 и вычитается из содержимого накапливающего сумматора-вычитателя 9, а содержимое блока 5 памяти сдвигается на 2 разряда вправо. Код нетерминала F заносится в буферный регистр 8 и складывается с содержимым накапливающего сумматора-вычитателя 9. Дешифратор 2 определяет текущую лексичес- кую единицу как закрывающую скобку. Блок 3 управления формирует си гнал, который производит сдвиг влево на один разряд содержимого блока памяти и запись кода терминала Закрывающая скобка в старшие разряды реверсив- но сдвигающих регистров. Дешифратор 7 приоритетов разрешает выбор основы (F) (Х, 1), так как в (N-l)-x разрядах реверсивных регистрах сдвига содержится код терминала Открывающая скобка. Код нетерминала основы записывается в буферный:.-регистр 8 и -вычитается из содержимого накапливающего сумматора-вычитателя 9, Одновре- менно сдвигается содержимое блока 5 памяти на два разряда вправо и снимается блокировка с входного регистра 1 , с которого на дешифратор 2 поступает лексическая единица ). В буферный регистр 8 заносится код нетерминала F и складывается С содер- жимым накапливающего сумматора-вьгчи- тателя 9.

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

Текущая лексическая единица Х определяется дешифратором 2 как операция (Х 1). Сформированный шиф- ратором 4 код терминала Знак умно- жить заносится в блок 5 памяти, запускается дешифратор 7 приоритетов, формирующий запрещающий си.гнал (х, 1). Код терминала заносится в блок 5 памяти, складывается с содержимым накапливающего сумматора-вычитателя 9 и осуществляется переход к следующей лексической единице.

Очередная лексическая единица D - операнд, В накапливающем сум- маторе-вычитателе 9 добавляется код нетерминала F, производится сдвиг влево на один разряд содержимого блока 5 памяти и выбирается следующая

49

12

лексическая единица - конец выражени

Itji М

Дешифратор 2 выделяет лексическую единицу и запускает шифратор 4 основ формирующий код терминала Конец выражения, который заносится в блок 5 памяти и запускает дешифратор 7 приоритетов. Последний разрешает выбор основы вида F+F (х, 1). Сначала код Нетерминала основы вычитается из содержимого накапливающего сумматора вычитателя 9, а затем к содержимому добавляется код нетерминала F, далее дешифратор 2 определяет текущую лексическую единицу как конец выражения (х 3 1). Блок 3 управления разрешает выдачу содержимого накапливающего сумматора-вычитателя 9 на дешифратор 10 аксиомы. Так как в накапливающем сумматор -вычитателе 9 находится код нетерминала F, то дешифратор 10 аксиомы запускает блок 3 управления, который успешно завер - шает синтаксический анализ исходного выражения.

Пример 2. Пусть исходное выражение имеет вид ({А +. В) х С# , которое содержит ошибку - нет закрывающей скобки.

Лексическая единица ( поступает через входной регистр 1 на дешифратор 2 и определяется как открывающая скобка. Запускается блок 3 управления, который блокирует входной регистр 1, формирует на шифраторе 4 основ код терминала Открывающая скобка, который записывается в буферный регистр 8, сдвигает содержимое блока 5 памяти на один разряд влево. Код терминала заносится в блок 5 памяти, одновременно суммируется с содержимым накапливающего сумматора-вычитателя 9, затем снимается блокировка с входного регистра 1 и следующая логическая i единица ( поступает на дешифратор 2 лексических единиц, Лексическая единица ( есть открывающая , и цикл работы устройства повторяется.

Очередная лексическая единица А дешифрируется-как операнд. На шифраторе 4 формируется код нетерминала F, :который поступает в буферный регистр 8, суммируется с содержимым накапливающего сумыагорагвычитателя 9, содержимое блока 5 памяти сдвигается на один разряд и происходит переход к следующей лексической единиII .11

це - +. + - операция ,. формируется код соответствующего термингша, который заносится в блок 5 памяти, откуда поступает на дешифратор 7 приори- тетов,- блокирующий приегм сигнала блоком 3 управления с дешифратора 6 кодов операции. Код терминала записывается в буферньй регистр 8 и складывается с содержимым накапливающего сум- матора-вьгчитателя 9, после выбирается очередная лексическая единица В.

Дешифратор 2 определяет ее как операнд. Содержимое накапливающего сум- матора-вычитателя 9 увеличивается на значение кода нетерминала F , блок 5 памяти подготавливается к приему очередного кода термингша.

Следующая лексическая единица ) дешифрируется как закрывающая скобка Шифратор 4 формирует код терминала Закрывающая скобка, который записывается в блок 5 памяти и поступает на вход дешифратора 7, в который по при- оритетам текущего кода терминала и предьщутцего (Знак плюс) разрешает блоку 3 управления выбор основы F-f . Код нетерминала основы вычитается из содержимого накапливающего сум

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

Текущая лексическая единица Х - операция. Код терминала Знак умножить записывается в блок 5 памяти, складывается с содержимым накапливающего сумматора-вычитателя, 9 и происходит переход к анализу следз ющей лек- сической единицы С.

с операнд, код нетерминала F суммируется с содержимым накапливающего сумматора-вычитателя 9, а

блок 5 памяти сдвигает содержимое на 1 разряд влево.

Очередная лексическая единица - конец выражения #. Код терминала записывается в блок 5 памяти, поступает на дешифратор 7 приоритетов. Возбуждается блок 3 управления и выбирается основа FxF, код нетерминала , который вычитается из содержимого накапливающего суммато{)а-вычита- теля 9, сбрасывается 2 старших разряда блока 5 памяти,, а содержимое на капливающего сумматора-вычитателя 9 увеличивается на код нетерминала F

Дешифратор 2 определяет, что текущая лексическая единица - конец выражения и содержимое накапливающего сумматора-вычитателя 9 по сигналу с блока 3 микропрограммного управления поступает на дешифратор 10 аксиомы, который опредешяет что содержимое сумматора отлично от кода нетерминала F и возбуждает в блоке 3 микропрограммного управления сигнал ошибки,

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

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

513

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

РкберсиКный

сддигаюций peiucmp

/I 2 I

1 г

1/1

916

которого являются выходами npHSHa k oB Ошибка и Конец анализа устройства соответственно.

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

am wuippamefia всно9 ,yj,yiS:yif,yil

Л

K- У

,Л -/, N

Уа

г .

п

1 I 2 I

ТТ f

к дешидзратору приоритета

дешисрратерап nogoS операций приоритета

Фиг. 2

lA -/ N

L-.

JL

СЗЕ

YtT XZL-ZJ

Составитель А. Ушаков Редактор Е, Копча Техред И.Попович Корректор М. Демчик

„,...J-- - - - -.---- - -« - -- --- -

Заказ 3964/ 6 Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Фив,3

онец)

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных и производства программ для ЭВМ в условиях с жесткими требованиями к быстродействию и аппаратурным затратам. Цель изобретения - повышение быстродействия, сокращение аппаратурных затрат и расширение функциональных возможностей за счет обеспечения полного синтаксического анализа исходных вьфажений. Для достижения указанной цели в устройство введены шифратор 4 основ, буферный регистр 8, накапливающий сумматор- вычитатель 9 и дешифратор 10 аксиомы. Реализация блока памяти на реверсивных сдвигающих регистрах, введение накапливающего сумматора-вычитателя и дешифратора аксиомы приводит к сокращению аппаратурных затрат и существенному повьш1ению быстродействия синтаксического анализатора. Применение шифратора основ, дешифратора приоритетов в сочетании с дешифратором аксиомы и другими блоками синтаксического анализатора обеспечивает полный синтаксический анализ вводимого текста. з.п. ф-лы, 3 ил. с б (Л с