Устройство для синтаксического анализа программ

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву(22) Заявлено 13,06,80 (21) 2999953/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 07,04.82. Бюллетень М 13 по918950

Союз Советских

Социалистических

Реслублии (5!)М. Кл.

С 06 F 15/20

3Ъсудврстванный квинтет

СССР вв делам нзебуетеннй н етнрытнй (53) УДК 681,32 (088.8) Дата опубликования описания 07.04.82 (72 } Автор изобретения .А. Н. Степанов

1 т (Московский ордена Трудового Красного Знам ни инженерно"- физический институт (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО АНАЛИЗА ПРОГРАММ

1

Изобретение относится к вычислительной технике и может быть использовано

s специализированных процессорах — трансляторах, переводящих текст программы с алгоритмического языка в объектный код.

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

pecos $13.

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

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

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

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

Недостатком известного устройства предлагаемого устройства. является, большой объем ассоциативного 5, Устройство состоит из блока 1 стекозапоминаюшего.устройства и низкая ско- вой памяти, регистра 2 сохранения, блока рость анализа, что объясняется необходи- 3 ассоциативной памяти признаков, ремостью преобразования грамматики язы- гистра 4 опроса, блока 5 задания пака к виду, допускающему анализ по од- чальных условий, блока 6 сравнения адному текущему символу и одному симво- 16 ресов, блока 7 памяти информационных пу из стека. В результате такого преоб- слов, блока 8 памяти операторов, дешифразования увеличивается число синтакси- ратора 9 ошибок, бпока 10 стековой паческих правил, а следовательно, и число мяти адресов возврата и блока 11 управстрок в анализирующей таблице, что впе- пения. чет собой Уменьшение скоРОСТИ ана - is Блок 11 упр в сод 12 управления содержит узеп 12 за из-аа увеличения числа записей в син- памяти микрокоманд деши 1 памяти мик команд, дешифратор z,ç адтакси ческий стек.

Пель изобретения .- повышение быстро- микрокоманд, формироватеп 15 адреса

Регистр 16 команд счетчик 17 узеп

2о 18 сравнения.

Поставленная цепь достигается тем, На чертеже такж б а чертеже также обозначены вход что в устройство введены блок задания устро ства, вход задания начапьначальных условий, блок памяти операто ных условий устр йс ных спови устройства, вход задаров, блок стековой памяти адресов >< - ния коэффициента с ициента устроиства. врата, регистр сохранения, дешифратор у В основе работы и основе ра оты устройства лежит ошибок, узел сравнения и счетчик, выход реализация п дпож еапизация предложении. языка ч нойдакоторого соединен с третьим входом фор- Эванса (яэыка продукц й), ванса языка продукцийу, с помощью мироватепя адресов блока управлений, котоРого можно легко пос отоРого можно легко построить пнюой четвертый вход формирователя адресов работающий по методу "перенос-свертка, соединен с выходом узла сравнения, пер- анализатор, Анализатор (программа анавый вход которого объединен со входом лиза) строится по грамматике языка пиблока стековой памяти и подключен к вы- бо вручную, либо с помощью формапьходу регистра сохранения, управпяюший ных методов на ЭВМ. При построении вход которого объединен с первым входом янапиза Флойда-Эванса исходная граммасчетчика и подключен ко второму выходу гика не претерпевает изменений. Предло35 узла памяти микрокоманд блока управпе- жение языка Флойда«Эванса включает ния, выход верхней ячейки блока стеко- цепочку символов дпя сравнения с цепочвой памяти соединен со входом регистра кой, находящейся в синтаксическом стесохранения, выход блока ассоциативной ке, цепочку дпя замены и набор операпамяти признаков соединен со входом

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

50 дешифратора ошибок и входом динамичес- Количество ячеек стека, участвующих кой установки начальных усповий блока в сравнении, определяется длиной осноэадания начальных условий, вход начапь- a>i, распознаваемой в результате сравненой установки которого является входом ний с правыми частями грамматических начальной установки устройства, второй 55 правил, содержащихся .в предложениях выход блока памяти операторов подкшо- анализатора. С этой целью выходы N чен ко входу регистра команд блока уп- верхних ячеек блока 1 подключены ко равпения, а второй вход узпа сравнения входам регистра 4 опроса. Вепичина

9189 определяет максимальную длину основы вместе с контактом. 1Лепочка, содержашаяся в блоке 1, параллельно сравнивается с цепочками, соответствуюшими предложениям анализатора и записанны» ми в блоке 3 признаков. В каждой ячейке содержится по одной цепочке. Если за-. писанная цепочка короче М, то неиспользованные позиции заполняются специальным кодом (т.е. маскируются). Блок 5 10 задает пространство поиска, т.е. верхний и нижний адреса диапазона, совпадения в котором принимаются во внимание и фиксируются блоком 6. Занесение начальных границ осушествпяется при инициа- 15 ции работы устройства.. По другому входу производится динамическое обновле ние границ. Блок 6 фиксирует номера ячеек, в которых произошли совпадения.

Еспи совпадений нескопько, то выбира- р0 ется первое, соответствуюшее меньшему адресу. Адрес ячейки передается на первый выход. Если совпадений нет, на второй выход передается сигнап отсутствия совпадений, который поступает за- 25 тем в дешифратор ошибок, который по коду границ идентифицирует ошибку и инициирует поиск конца анализируемого оператора блоком 11.

В блоке 7 хранятся информационные слова, где содержится новая цепочка, которой заменяется цепочка, находяшаяся в верхушке блока 1. На необходимость такой замены указывает бит "Признак замены". Длину заменяемой цепочки (т..е. 35 количество ячеек стека) указывает поле

Длина цепочки".

Дпина новой. цепочки дпя многих полезных классов грамматик не превышает одного символа. Новая цепочка в данном случае может содержать топько метасимвол, тогда как стековые цепочки мо гут содержать как терминалы, так и ме тасимволы. Код новой цепочки передается на первый выход.

Программирование на языке ФлойдаЭванса анализаторов по грамматикам слабого предшествования, грамматикам ограниченного правого контакта и др; требует, чтобы в некоторых предложениях верхняя ячейка бпока 1 не участвовапа в замене и сохраняпа свое содержимое.

Для этой цели спужит регистр 2 сохранения, куда временно копируется содержимое верхней ячейки блока 1. Дпя ynIf 55 равления сохранением служит бит Сохранение", в информационном спове. На необходимость сканирования очередного символа программы и занесения его в блок

6О 6

1 после выполнения замены указывает би т Скан ".

Бит Список" указывает, что после замены и других действий выполняются операторы управления, записанные в бло»ке 8. Адрес первого оператора указан в поле "Адрес". Адрес передается на третий выход, а вся остапьная информацияна второй выход блока 7.

Предусмотрено выпопнение спедуюших . операторов:

GOTO - безусловный переход;

ЗЛИ. — вызов подпрограммы синтаксического анапиэа;

R57Ukg " возврат иэ подпрограммы; SFT — установка новых границ;

ЕЙ2 - конец анапиза.

Каждый оператор .содержит бит Признак продолжения", указываюший, что далее спедует еше оператор, и два паля границ "Верх" и "Низ", а также бит

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

Оператор 5 ET — есть переход к следуюшему предложению, если поспе вызова подпрограммы необходимо сканирование, так как оператор RETU RN возвращает управление к следуюшему за оператором CALL оператору. В блоке 10 запоминается адрес возврата - на единицу увепиченный адрес оператора GAL 4.

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

Об окончании работы анализатора свиде тельствует появление в верхушке блока

1 цепочки Ф 2 „ где 4 — дно стека начатп,ный символ, к которому свернут анализируемый оператор языка, .) лежоператорный разделитель.

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

Таким образом, эа счет использования блока задания начальных условий, блока операторов, блока стеновой памяти адресов возврата, регистра сохранения, соединения нескольких верхних яче ек синтаксического стека с регистром опроса и других ыовых связей удается

7 9189 существенно уменьшить число предложений анализатора, Уменьшение числа предложений анализатора происходит также за счет использования блока границ в сочетании со схемой дешифрации оши» бок так как это позволяет исипочи ть ряд диагностических сравнений с целью идентификации ошибок, что в данном слу чае производится автоматически по коду границ. Уменьшение числа предложений ., ф анализатора приводит s свою очередь к уменьшению числа замен, т.е. числа записей в синтаксический стек, что ловы шает скорость анализа пропорционально уменьшению объема анализатора. !5

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

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

50 8

-тем, что, с целью повышения быстродей ствия, в него введены блок задания начальных условий, блок памяти операторов; блок стековой памяти адресов возврата, регистр сохранения, дешифратор ошибок, узел сравнения и счетчик, выход которого соединен с третьим входом формирователя адресов блока управления, четвертый вход формирователя адресов соединен с выходом узла сравнения, первый вход которого объединен со входом блока стековой памяти и подключен к выходу регистра сохранения, управляющий вход которого соединен с первым входом счетчика и подключен к второму выходу узла памяти микрокоманд блока управления, выход верхней ячейки блока стековой памяти соединен с входом регистра сохранения, выход блока ассоциативной памяти признаков соединен с входом блока задания,начальных условий, выход ко» торого соединен с входом блока сравне.ния адресов, второй выход которого подключен к дешифратору ошибок, выход ко« торого объединен с вторым выходом блока памяти информационных cnos, третий выход которого подключен к входу блока памяти операторов и соединен с входомвыходом блока стековой памяти адресов возврата, первый выход блока памяти операторов соединен с входом дешифратора ошибок и входом динамической установки начальных условий блока задания начальных условий, вход начальной установки которого является входом начальной установки,устройства, второй выход блока памяти операторов подключен к входу регистра команд блока управления, а второй вход узла сравнения является входом задания константы устройства.

Источники информации, принятые во внимание при экспертизе

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

М 674028, кл. 6 06 F 15/20, 1976.

2. Авторское свидетепьство СССР

Яо 377774, кл. 5 06 Р 9/00, 1 968 (прототип ) .

21

Составитель А. Баранов

Редактор П. Макаревич ТехредЕ.Харитончик Корректор О. Билак

Заказ 2143/33 Тираж 732 Подписное

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

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

Фипиап ППП "Патент", r, Ужгород, уп. Проектная, 4