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

вишКяа

фи&1

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

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

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

Анализатор содержит входной ре J5 гистр 15 дешифратор 2 лексических единиц, блок 3 микропрограммного управления j шифратор 4 кодов символов, блок 5 памяти, -дешифратор б кодов символов, блок 7 элементов L 20

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

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

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

Блок 3 включает регистр адреса, постоянное запоминающее устройство, регистр слов, Входньми сигналами является мноясество jjX,.,, о .. . а выходами Y у, ,у , ...,у . Реали- д зация блока 3 микропрограммного управления с помощью приведенного конечного автомата сводится к занесению в ПЗУ информации о микропрограмме блока 3 и уточнении числа входов и выходов в соответствии с числом вхо- , дов и вь ходов блока 3.

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

35

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

Пример функционирования блока 3 для операций х умножения и + сложения описай на блок-схеме (фиг.З) микропрограммного управления, где входные сигналы х,х ,х ,х..,х ,х , x,Q , х формирует дешифратор 2 лексических единиц, сигналы к ,х, , х и Xg формирует дешифратор 6 кодов символов. На выходе блока 3 формируются сигналы микроопераций Yg, а также сигналы Y,,..YTJ являющиеся совокупностями микроопераций.

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

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

знак

.

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

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

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

X,

знак к

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

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

15 если лексическая единица входного выражения есть (|

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

1, если содержимое последних трех разрядов регистров блока 5 памяти есть комбинация кодов FxF;

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

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

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

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

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

143959А

15 если содержимое последних

-rt

,

трех разрядов регистров блока 5 памяти есть комбинация кодов (F);

О в противном случае; 15 если содержимое N-ro разряда регистра блока 5 памяти есть код нетерминала F;

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

О в противном случае; 13 если содержимое последних трех разрядов регистров блока 5 памяти есть комбинация кодов F-K-F,

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

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

у - выдача сообщения

0

Конец выражения.

Шифратор 4 кодов символов формирует коды терминалов и нетерминалов.

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

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

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных и производства программ для ЭВМ, Цель изобретения - повышение быстродействия и сокращение аппаратурных затрат устройства. Для дост 1жения указанной цели в устройство дополнительно введен блок 7 элементов И. Введение данного элемента и порожденных им связей позволит значительно упростить управление процессом синтаксического анализа, сократить объем микропрограммного обес- пе.чения устройства, а также отказаться от буферного регистра, сумматора и дешифраторов аксиомы и приоритетов, 3 ил.

входного выражения есть тт - 25 разом.

к

Y 1

V 2

Y3 Y.

де у

4У.,У6У,УЮ признак конца выражения;

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

15 если лексическая единица

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

0; В противном случае, У1 Уг г ,ГУ4.УЛ ;

У,Уз}; , Y У7.

(У.Ую ; Y {У,

fy, Yg у,,

-обнуление входного регистра 1;

-разрешение чтения очередной лексической единицы во входной регистр 1;

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

сдвиг на 1 разряд влево содержимого блока 5 памяти; запись кода нетерминала F в блок 5 памяти; запись кода терминального символа и блок 5 па мяти, ,х|; сдвиг на 3 разряда вправо содержимого блока 5 памяти; запись кода терминального еимвола ) в блок 5 памяти; выдача сообщения Ошибка ; запись кода нетерминального символа ( в блок 5 памяти:

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

Перед поступлением первого входно- го символа анализатор устанавливается в исходное состояние:

обнуляется входной регистр 1 и блок 5 памяти (микрооперации у и у);

в N-Й разряд блока 5 памяти заносится код нетерминала F (микрооперация у,,);

снимается запрет на чтение очередного символа во входной регистр 1 (микрооперация У.)Для сокращения записи условимся в дальнейщем обозначать блок 3 микропрограммного управления как БМПУ.

При поступлении на вход символа ( открывающей скобки () деши фратор 2 запускает БМПУ, который вы- (Рабатывает совокупность микроопераций Y и Y :

55

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

чтение следующей лексической единицы, т.е„ обнуляется входной регистр (YJ), затем снимается запрет на чтение очередной лексической еди- ницы (у,)

Если входной лексической единицей является с1-швол :# 0, х., : 1), выступаюцщй не как символ в конце выражения, а как самостоятель- ный символ (являющийся частным случаем выра кения) 5 то БМПУ производит проверку регистра блока 5 памяти на содерл ание кода нетерминала F : (который в начале работы устройства : записывается в блок памяти), Если ; блок 5 памяти содержит код F, то происходит выдача сообшеггая Конец выражения ( ) , Если блок 5 памяти ке содерзкит код F()5 то происхо- . дит выдача с-ообщенргя Ошибка (у ) , ;Такое же сообщение Ошибка (у„) вы- ; дается и Б случае х 0. Это происхо дит, если входной символ не onepai-ps iне знак операции и не знак Конец; выражения ,. т.е. знак, не принадле- лсащий входному алфавиту.

Если очередная лексическая едини

то операдий Y и Y

производится сдвиг влево на 1 раз- 5 памяти содерлсат комбинацию 4X9

;ряд содержимого блока 5 памяти ( ) s

; . осуществляется запись, кода нетерминала. F в блок 5 памяти (у)з

; производится обнуление входного

: регистра 1 (у )|

снимается запрет на чтение очеред;ного символа (у)

Читается очередной символ. Если

; очередная .лексическая единица () есть знак операции сложения + или умнолчения х, то БШУ вырабатывает совокушгасть операций Y. и Y :

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

1

щз

35

к

Э CJ

ствляет свертку. После свертки в

В этом случае БШУ осу

каждом из трех

-7

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

Если на входе знак операции а последние три разряда блока 5 памяти содерл ат комбинацию F+F (х, 0, х 1, х 1)S то в этом случае БМПУ вы- 45 рабатывает последовательность опера- дни Y и Y :

запись кода знака операций х в блок 5 памяти;

чтение очередного символа.

5Q В данном случае операция свертки rie производится, так как приоритет операции умножения х выше, чем операции сложения 4.

Если очередной символ закрывающая При прочтении следующего операнда gg скобка ) и возможные операции сверт- и соответственно при занесении кода ки выполнены (), то БШ1У осуществляет операцию (у. ) s

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

нетерминала F в блок 5 памяти три последние разряда блока памяти будут содержать комбинацию , Эти три

последних разряда .подаются на блок 7 элементов И и в зависимости от вида очередного входного символа (также попадающего на блок 7 элементов И) БМПУ выработает одну из трех операций. Рассмотрим последовательно все эти три случая:.

1 На входе знак операции - (т.е. плюс или умножить), последние три разряда, блока памяти содержат комбинацию FxF (х, 0, , х , ), БМПУ вырабатывает совокупность микроопераций Yg, производящих опера- 5 цию свертки, т,е, операцию замены комбинации FxF кодом F:

сдвиг содерлчимого блока 5 памяти на три разряда вправо (у-. );

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

запись в М-й разряд блока памяти кода нетерминала F,

2,На входе знак онерадии -J-, последние три разряда блока 5 памяти содерлсат комбинацию F+F (х., 0 х.. к, 5 х 1). В этом случае ЕМПУ вырабатывает совокупность микроопераций Y,5, т е„ осуществляет свертку,

30 щей скобки или признака конца выражения. Последние три разряда блока

5 памяти содерлсат комбинацию 4X9

1

щз

5

к

Э CJ

ствляет свертку. После свертки в

В этом случае БШУ осу

каждом из трех

-7

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

Если на входе знак операции а последние три разряда блока 5 памяти содерл ат комбинацию F+F (х, 0, х 1, х 1)S то в этом случае БМПУ вы- 45 рабатывает последовательность опера- дни Y и Y :

запись кода знака операций х в блок 5 памяти;

чтение очередного символа.

запись кода ) в N-й разряд блока памяти.

После этого БМ1У производит просмотр комбинации кодов последних трех разрядов блока памяти. Если это не комбинация (F), то выдается сообщние об ошибке ( ) .

Если последние три кода блока 5 пмяти есть комбинация (F), то БМГО пр изводит последовательность операции YfeHY, :

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

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

запись кода нетерминала F в N-й разряд блока памяти;

чтение очередного символа.

Если входным символом является # - признак -конца выражения - и произведены свертки комбинаций кодов и (F) в блоке 5 памяти, тогда БМПУ производит проверку содержимого последнего N-ro разряда блока памяти. Если содержимое блока памяти есть код нетерминала F (х 1 ), то БМПУ выдает сооби(ение Ко- .выражения (у,), т.е. выражение .в синтаксическом отношении составлен правильно. Если содержимое последнего разряда блока 5 памяти не есть код нетерминального символа F (х 1 X 0), то вьщается сообще,ние об ошибке (у.,).

Пример 1, Рассмотрим работу устройства при поступлении на вход синтаксически правильного выражения (А+ВхС)#, .

Устройство устанавливается в начальное состояние; регистр 1 (обнулен, N-й разряд блока 5 памяти содержит код нетерминала F.

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

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

Очередной символ А дешифратором 2 определяется как операнд (х,, 1). БМПУ вырабатывает операции Yx и Y - запись кода нетерминала F в блок 5 памяти и чтение очередного символа.

0

5

о

Очередной символ + дешифрато5

ром 2 лексических единиц определяется как знак операции сложение (х 1, ).

Так как последние три разряда блока 5 памяти не содержат комбинацию FK-F (, 0), то БМПУ вырабатывает последовательность микроопераций Y 5- и Y :

запись в N-й разряд блока 5 памяти кода

чтение очередного символа. Очередной символ В дешифратором 2 лексических единиц определяется как операнд. Тогда БМПУ производит запись кода F нетерминала в N-й разряд блока 5 памяти и чтение очередного символа (операции Y4 и Y,). Очередной симвох х дешифрато- ,ром 2 лексических единиц определяется как знак умножения (, ), Последние три разряда блока 5 памяти содержат комбинацию кодов F+F (). Свертка F+F не производится, так как приоритет операции х - выше, чем опео

. Код знака х записывается

памяти и читается очередной

V ч 5aV.Y,)5

рации + Б блок 5 символ

Очередной символ С дешифратором 2 лексических единиц определяется как операнд. БМПУ производит запись кода нетерминала F в блок 5 памяти и чтение очередного символа.

Очередным символом является лексическая единица ( - закрывающая скобка (, ). Так как последние три разряда блока 5 памяти содерто БМПУ

жат комбинацию FxF (х 1), 0 производит свертку:

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

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

5 записывает в N-й разряд код нетерминала F.

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

На входе ), а блок памяти содержит комбинацию F+F (,х 1). БМПУ производит свертку. Чтение

5

очередного символа не происходит, а происходит просмотр кодов входного регистра 1 и последних трех разрядов блока 5 памяти. Теперь х 0, .

Xrj 0 и свертка невозможна. Поэтому код ) записывается в блок 5 памяти (х 1) и сразу же производится анаb

ЛИЗ последних трех разрядов блока 5 памяти. Так как последние три разряда есть комбинации (F) (), то вновь производится;свертка, т.е. (Р)заменя- ется на F и читается очередной символ.

Очередной символ есть : знак конца выражения 1, ).. Так как последние три разряда блока 5 памяти не содержат комбинацию F4fF (х 0) J а последний N-й разряд содержит код F (), то БЖ1У вырабатывает микрооперацию у, - -конец выражения, которая означает, что исходное зьфажение синтаксически правильно,

П р и м е р 2. Рассмотрим работу устройства при поступлении на вход синтаксически неправильного выражения (А+В))-, В этом выражении нарушен баланс скобок - отсутствует открывающая скобка или лишняя закрывающая скобка,

З стройство перед работой устанавливается в, начальное сост-ояние; входной регистр 1 обнуляется,, в N-й разряд блока 5 памяти заносится код нетерминала Б . Снимается запрет на чтение символа.

На входной регистр 1 поступает символ (, которьш делшфратором 2 определяется как открывающая скобка (х, 1), БЖУ сдвигает на один раз-ряд влево содержимое блока 5 памяти (у) и записывает код ( (у,о ) . Затем снимается запрет Hf, чтение следующего символа (у,, у,,) Блок 5 памяти содержит комбинацию (.

Очередной сх-гмвол А дешифратором 2 определяется как операнд, В блок 5 памяти записьшается код, нетерминала F и читается следую:ций символ. Блок 5 памяти содержит комбинацию F(F,

Очередной символ -f дешифратором 2 определяется как знак операции сложения, код + записьшается в блок 5 памяти и читается следующий символ, .Блок 5 памяти содержит комбинацию кодов F(F+,,

Очередной символ В дешифратором 2 лексических единиц определяется как операнд, в блок 5 памяти записывается код нетерминала 1 и читается очередной символ. Блок 5 памяти содержит комбинаци10 кодов F(F+F,

0

5

0

5

Очередной символ ) дешифратором 2 лексических единиц определяется как закрывающая скобка (yiL 1, х 1). Так как последние три разряда блока 5 памяти содержат комбинацию кодов F-t-F ( 1), БМТУ производит операцию свертки;

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

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

в последний разряд записывается код нетерминала F,

Теперь блок памяти содержит комбрг- нацию кодов F(F. Опять производится просмотр содержимого входного регистра 1 и .комбинации блока 5 памяти. Входной регистр 1 содержит )э блок 5-памяти - комбинацию F(F (), БЖ1У запис лзает код ) в блок 5 памяти. Теперь блок 5 памяти содерлсит комбинацию ;кодов F(F),

Так как то БШУ производит операцию сверткиj т.е. комбинацию (F) заменяет кодом нетерминала F (у ,у

У,)

т я,

Затем читается очередной символ. Блок 5 памяти содержит ког бинацию кодов FF.

Очередной символ ) дешифратором 2 лексических единиц определяется как закрывающая скобка ( 1, )o Так как содержимое блока 5 памяти не есть комбинация кодов F-№ i xt 0),, то БМПУ записывает код ) в блок 5 памяти, которьй теперь содержит комбинацию кодов FF) „ PI теперь, так как последние три разряда блока 5 памяти не содерлсат комбинацию (F) т.е БЬ ШУ выдает сообщение Ошибка (УО). Это означает, что исходное выралсение. синтаксически неправильно.

Формула

и

обре

е н и я

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

11

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

к дешифратору 6

3959412

чающийся тем, что, с целыо

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

10

но, а выходы блока элементов И подключены к входам второй группы блока микропрограммного управления.

I 5,% 7 JA

Фиг. 2