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

 

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

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

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

РЕСПУБЛИН

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4236428/24-24 (22) 27.04.87 (46) 23.11.88. Бюл. ¹ 43 (72) В.К.Водопьянов, В.Н.Волков, С.П.Зайцев, Г.В.Назарьян и 10.А.Орлов (53) 681.325(088.8) (56) Авторское свидетельство СССР № 1130879, кл, G 06 F 15/38, 1984.

Авторское свидетельство СССР № 1334149, кл. G 06 P 11/00, 1986. (54) СИНТАКСИЧЕСКИЙ АНЫП4ЗАТОР (57) Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах (д1) 4 G 06 F 11/00, 15/38 обработки данных и производства программ для ЭВМ. Цель изобретения повышение быстродействия и сокращение аппаратурных затрат устройства.

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

3 ил.

1439594

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

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

На фиг.1 прецставлена структурная схема анализатора; на фиг. 2 — структурная схема блока памяти; на фиг,3— блок-схема микропрограммного управлеHHH BHBlIH9ÝTÎPÎÌ

Лнализатор содержит входной регистр 1, дешифратор 2 лексических ециниц, блок 3 микропрограммного управления, шифратор 4 кодов символов, блок 5 TIBNHTH дешифратОI) 6 кодов символов., блок 7 элементов И, щ

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

Терминальным символом или терминалом называется символ, однозначно соответствующий символу входного языка. 25

Нетерминальный символ или нетерминал

Р— это символ, эквивалентный одному или целой группе символов Входного языка.

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

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

Бпок 3 включает регистр адреса, постоянное запоминающее устройство, регистр слов. Входными сигналами является множество Х=(х,,х,...,х„). а выходами Y=Iy у,...,y„ I. Реализация блока 3 микропрограммного управления с помощью приведенного ко" нечного автомата сводится к занесению в ПЗУ информации о микропрограмме блока 3 и уточнении числа входов и выходов в соответствии с числом вхо50 дов и выходов блока 3.

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

Пример функционирования блока 3 для операций "х" умножения и "+" сложения описай на блок-схеме (фиг.3) микропрограммного управления, где входные сигналы x<(,õ,õ,,х,,х,х

I I х, ; х„, формирует дешифратор 2 лексических единиц, сигналы х,х,х

II << х и х формирует дешифратор 6 кодов символов, На выходе блока 3 формируются сигналы микроопераций У8, а также сигналы У<...Ут, являющиеся совокупностями микроопераций.

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

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

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

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

"l

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

1, если содержимое последних трех разрядов регистров бло" ка 5 памяти есть комбинация кодов F+F; х = . <(2

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

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

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

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

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

<<< 1(° х

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

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

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

1ч39594

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

7 х х!О = хн =, (У4 "". У63 s (У1 1 У4 У5 е У4 Y6$

В (У9)

У4 У2 ° узву5 )

У43yto) з

У!

У2

Уз

У4 где у, 2 у4 у6

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

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

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

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

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

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

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

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

1, если лексическая единица входного выражения есть опеаид в противном случае. У4 У обнуление входного регистра 1; разрешение чтения очередной лексической единицы во входной регистр 1; обнуление регистров блока памяти; сдвиг на 1 разряд влево содержимого блока 5 памяти; запись кода нетерминала F в блок 5 памяти; запись кода терминального символа " " в блок 5 памяти, где + F +, x ); сдвиг на 3 разряда вправо содержимого блока 5 памяти; запись кода терминального символа ")" в блок 5 памяти; выдача сообщения "Ошибка"; запись кода нетерминального символа "(" в блок 5 памяти; у — выдача сообщения "Конец и

11 выражения

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

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

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

>О деляет следующие лексические единицы: операнды, знаки операций, открывающую и закрывающую скобки, признак конца выражения

Перед поступлением первого входно35 го символа анализатор устанавливается в исходное состояние: обнуляется вхоцной регистр 1 и блок 5 памяти (микрооперации у, и у ); в N-й разряд блока 5 памяти зано40 сится код нетерминала Р (микрооперация у ); снймается запрет на чтение очередного символа во входной регистр 1 (микрооперация у2).

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

При поступлении на вход символа

"(" открывающей скобки (х =1) деши9 фратор 2 запускает БИПУ, который вы,рабатывает совокупность микроопераций Y3 H Y! осуществляется запись кода открывающей скобки в блок 5 памяти, т.е.

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

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

=-1), выступающий не как символ в конце выражения, а как самостоятель- 1О ный символ (янляющийся частным случаем ныоажения), то БМПУ производит проверку И-I o регистра блока 5 памяти на содержание кода нетерминала Е (который н Начале работы устройства записывается н блок памяти). Если

1 I l1 блок 5 памяти содержит код Е „ та !

1 происходит выдача соабшеиня 1(опец выражения! (у!,„ Если Олок 5 памяти не содержит код F(x =0), то праисхо- зО дит ны!1ача сообщения Ош11б!ка™ (у, )11

Такое же сообщение Ошибка" (у ) вы9

C. I"J BB Х 1„ =G .:! I O дкт. если входной символ -::е апера11д, не знак !»перании и не знак "1(онец 2Б вь1ра1жепия, т. е. знак, не принадлежащий входному алфавиту, Если Очередная лексическая единина ес.,;.; о11еранд (х =-О,. х, — -1), то

Б11!1У нь1рабатывает совокупность опе- 3О ра1ЛIй Yd И 71 . производится сдвиг влево на 1 разряд содержимого блока 5 памяти (у )," осуществляется запись, кода нетер минала Г н блок 5 памяти (у ); производится обнуление входного регистра I (у,); снимается запрет на чтение ОчередИОгО символа (у )

Читается очередной символ, Если очередная лексическая еди1.кца (х1=1) есть знак операции сложения +" илк умножения х, то БМПУ вырабатывает совокупность операций У к У . запись кода знака н блок 5 памяти,; чтение очереднога символа.

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

При прочтении следующего операнда и соответственно при занесении кода нетерминала Е в блок 5 памяти три последние разряда блока памяти будут содержать комбинацию F4"F. Эти три последних разряда .подаются на блок 7 элементов И к в зависимости от вида очередного входного символа (также попадающего на блок 7 элементов И)

БИ1У выработает одну из трех операций.

Рассмотрим последовательно все эти три случая:.

1. На входе знак операции "+" (т.е. плюс или умножить), последние три разряда, блока памяти содержат комбинацию FxF (х< =О, х =О, х„=1 х =1), БМПУ вырабатывает совокупность микроапераций 1, производящих операцию свертки, т.е. операцию замены ко1-1бинации ЕхЕ кодом Е: сдвиг содержимого блока 5 памяти на трк разряда вправо (у ); сдвиг содержимого блока 5 памя=и нн один разряд влево (у,); запись в П-й разряд Ьл<»ка памяти кода нетермкнала Е.

2, На входе !Нак Операции "-. ", последние ттги разряда блока 5 памяти сОдержат комбинацию 1 +1. (х1 =0р хz !»!

/! х = х =! ), Б этом случае БГ П» вь1 .Р рабатыв1!!т совокупность микраопераций т.е„ осуществляет свертку, T 11 !1

3. rIB входе символы, закрывающей скОбки клк ф" пРизнака КОнца ныI I 11 ( раженкя. Последние трк газряда блока

5 памяти содержат комбинацию F+F (х = у

=1, x> =1). Б этом случае БЭППУ осу" свертку.

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

Если на входе знак Операции "х", B последние три разряда блока 5 памяти содержат комбинацию Г+Е (х„ =О, х

=1„ х " =1), то н этом случае БЭППУ вырабатывает последовательность операЦий Ур И У„ запись када знака операций "х в блок 5 памяти; чтение очередного символа.

Б данном случае операция свертки пе производится, так как приоритет операции умножения х выше, чем операции сложения "+".

Если очередной символ закрывающая скобка ")" и возможные операции свертки выполнены (х =1), та БЮ1У осуществляет операцию (у ): сдвиг влево на 1 разряд содержимого блока 5 памяти;

1439594

")" в N-й разряд бло"

35 запись кода ка памяти.

После этого БМ11У производит просмотр комбинации кодов послецних

5 трех разрядов блока памяти. Если это не комбинация (Г), то выдается сообщение об ошибке (у ).

Если последние три кода блока 5 памяти есть комбинация (F), то БМПУ про-1п изводит последовательность операции

У6 и У1. сдвиг вправо на три разряда содержимого блока 5 памяти; сдвиг влево на 1 разряд содер>кимого блока 5 памя ги; запись кода нетерминала Г в N-й разряд блока памяти; чтение îчередногQ символа, Если входным символом является 20

"Ф вЂ” признак конца выражения — и произведены свертки комбинаций кодов 1" 1 и (F) в блоке 5 памяти, тогда Iii1115 производит проверку содержимого последнего И-го разряда блока памяти. Если содержимое блока памяти есть код нетерминала Г (х, =1, х =1), -о БМПУ выдает сообщение "Ко-. нец выражения" (у „, ), т.е. выражение .в синтаксическом отношении составлено б правильно. Если содержимое последнего разряда блока 5 памяти не есть код нетерминального символа Е (х, =-1, х =О), то выдается сообщение об ошибке (у„) .

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

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

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

Очередной символ "А" дешифратором 2 определяется как операнд (х„ =

=1). БМПУ вырабатывает операции Y и Y — запись кода нетерминала F в блок 5 памяти и чтение очередного символа.

Очередной символ "+" дешифрато- ром 2 лексических единиц определяется как знак операции сложение (х, =

=1, х =1).

Так как последние три разряца блока 5 памяти не содержат комбинацию FtF (х+=О, х" =0), то БМПУ вырабатывает последовательность микроопераций У < и Y< . запись в N-й разряд блока 5 памяти кода "+ чтение очередного символа, Очередной символ "В" дешифратором 2 лексических единиц определяется как операнд. Тогда БМПУ производит за lIfch Kollà Г нетерминала в И-й разряд блока 5 памяти и чтение очередного символа (операции У4 и Y,).

Очередной символ х дешифрато,ром 2 лексических единиц определяетt f ся как знак умножения (х4 =1, х =1) .

Последние три разряда блока 5 памяти содержат комбинацию кодов 1 +Г (х " =1).

Свертка F+F »e производится, так как приоритет операции "х" выше, чем операции "+". 1<од знака "х" записывается в блок 5 памяти и читается очередной символ (У,Y,).

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

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

Очередным символом является лексическая единица (— закрывающая скобка (х =1, х =1). Так как последние три разряда блока 5 памяти содержат комбинацию FxF (х =1), то БМПУ производит свертку: сдвигает содержимое блока 5 памяти на 3 разряда вправо; сдвигает содержимое блока 5 памяти на 1 разряд влево; записывает в И-й разряд код нетерминала Г.

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

На входе ")", а блок памяти содержит комбинацию F+F (x =1,х" =1).

БМПУ производит свертку. Чтение очередного символа не происходит, а происходит просмотр кодов входного регистра 1 и последних трех разрядов блока 5 памяти. Теперь х =О, к =О, I/

1439594

io х„ =-О и снертка невозможна. Поэтому код ")" записывается в блок 5 памяти (х =i) и сразу же производится ана6 лиз последних трех разрядов блока 5 памяти, Так как последние три разряда есть комбинации (Г) (х =-i), то вно:зь производится свертка, т.е (P)заменя- ется IIa F и читается очередной симнол. !

Очередной символ есть " — знак конца выражения (х о=1, х =1).. Так как последние три разряда блока 5 памяти не содержат комбинацию "2+1 " (х =0), а последний N-й разряд содержит код Г (х„=.1), то !311ПУ вырабатывает микросперацию уя — конец выражения, которая означает, -ITo исходное выражение синтаксически правильно, Пример 2. Рассмс грим работу ,. 1 устройства при г1оступлении на вход синтаксически неправильного выражения (Л+В))ф., В этом вь|ражении нарушен балBIIc скобОк Отсутствует о Гкрыва!о"" щая сIIoáкс! Или лишн11я зaкръ|ва!Ощая скобка .

Устройство перед работай устанавливается в. начальное состояние: вх:одной регистр 1 обнуляется, a N-й разряд блока 5 памяти занасIIтся Кор ,)Р нетерминала Р, Снимается запрет на

ЧТЕНИЕ СИМВОЛа. !

На входной регистр 1 поступает символ "(", который дешифратаром 2 определяется как открывающая скобка (х =1) . Б11ПУ сдвигает на адин разряд влево содержимое блока 5 памяти (у ) и зались!вает код "(! (у ).

Затем снимается запрет и:. чтение следующего символа (у,, у, ): Блок 5 памяти соцержит ксмбинацй!о "(Очередной символ А" дешифратором 2 определяется как операнд.

В блок 5 памяти записывается код нетерминала Е и читается следующий символ. Блок 5 памяти содержит комбинацию 1"(Г.

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

2 определяется как знак сгерации сложения, кад "+" записывается н блок 5

56 памяти и читается следуюший символ. ,Блок 5 памяти содержит комбинацию коро, P(P+., Очередной символ "B дешифраторсм

2 лексических единиц определяется

55 как операнд, в блок 5 памяти записывается код нетерминала Р и читается очередной символ. Блок 5 памяти содержит комбинацию кодов Г(Р+Г.

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

2 лексических единиц определяется

ff как закрывающая скобка (х! =1, х> =1).

Так как последние три разряда блока 5 памяти содержат комбинацию кодов Г+Е (х =1), BKD производит спераци!о свертки: содержимое блока 5 памяти сдвигается вправо на 3 разряда; содержимое сдвигается в,Лево на разряд; в последний разряд записывается код нетерминала Г.

Теперь блок памяти содержит комбинацию кодов P(F. Опять производится просмотр содержимого входного регистра 1 и,комбинации блока 5 памяти,.

Входной регистр 1 содержит )", блок

5 памяти — комбинацию 1(Г (х =1,! °

HKD записы1- ае1 код ")" мяти. Теперь блок 5 памяти содержит комбинацию, кодов Г(Г).

Так как x =-1 тс БИПУ производит

7 операц1по свертки, т. е, комбинацик (F, заменяет кодом нетерминала 11 (у,у 7 - с« у ),. Затем читается очередной символ.

Блок 5 памяти содержит ксмоинаци;.о ко=дав PF.

С!чередной символ ) део!Ифратсpсм

2 лексических ециниц определяется как закрывающая скобка (х =1, х =1).

Так как ссдер>кимсе блока памяти

ff не есть комбинация кодов F . Г Г х,- =О) 9 тс БК1У записывает кад )" в блок 5 памяти, который трперь содержит комбинацию кодов FF). И теперь, так как последние три разряда блока 5 памяти не содержат комбинаци!о (F),- т,е х =О, БМПУ выдает сообщение Ошибка (у,). Это означает, что исходное

/ выражение синтаксически неправильно, формула изобретения

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

lI

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

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

1439594

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

Редактор A.Âoðoâè÷ Техред M.Õoäàíè÷ Корректор 0 ° Кравцова

Заказ б078/48 Тираж 704 Подписное

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

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

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