Устройство для синтаксического анализа программ Советский патент 1982 года по МПК G06F17/21 

(54) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО АНАЛИЗА ПРОГРАММ

Изобретение относится к вычисгатепь ной технике и может быть использовано в специализированных процессорах - тран пяторах, переводящих текст программьт с алгоритмического языка в объектный код. Известна система для трансляции с проблемно-ориентированного языка, пред назначенная для аппаратурной реализа- ции всех фаз трансляции, состоящая из оперативного запоминающего устройства, вычислительного устройства, внещнего запоминающего устройства, символьного анализатора, оперативного анализатора, блока перекодировки чисел, блока обработки ошибок и ряда модификаторов (адресов tl. Недостатком системы является большой объем оборудования и ограниченный набор транслируемых инструкций, трудно поддающийся расширению. Наиболее близким к предлагаел ому является устройство для синтаксического анализа программ, содержащее ассоциативное запоминающее устройство, состоящее из накопителя ассоциативных признаков, блока индикаторов, регистра . опроса, выходного регистра и блока рабочих ячеек, а также схему контроля, синтаксический стек, выход верхней ячейки которого подключен к регистру опроса, и блок управления 2. Синтаксический анатшз чзсуществляетсэ с помощью анализирующей таблицы, xjia нящейся в накопителе ассоциативных признаков и блоке рабочих ячеек. В блоке ассоциативных признаков осуществляется быстрый поиск строк анализирующей таблицы по признаку,,образуемому текущим символом программы и одним символом из синтаксического стека. При нахождении соответствующего признака осущест вляется выборка содержимого одной иэ рабочих ячеек и выполнение действий, указанных там: запись в стек или его , сдвиг вверх, вызов семантической процедуры. При отсутствии искомого признака в накопителе ассоциативных признаков 3 91 фиксируется ошибка в анализируемой программе, приводящая к прерыванию работы устройства. Недостатком известного устройства является .большой объем ассоциативного запоминающего устройства и низкая скорость анализа, что объясняется необходимостью преобразования грамматики языка к виду, допускающему анализ по одному текущему символу и одному символу из стека. В результате такого преобразования увеличивается число синтаксических правил, а следовательно, и число строк в анализирующей таблице, что влечет за собой уменьшение скорости анали- за из-за увеличения числа записей в син таксический стек. Цель изобретения .- повьпиение быстро действия. Поставленная цель достигается тем, что в устройство введены блок задания начальных условий, блок памяти операторов, блок стековой памяти адресов возврата, регистр сохранения, дешифратор ошибок, узел сравнения и счетчик, выход которого соединен с третьим входом формирователя адресов блока управлений, четвертый вход формирователя адресов соединен с выходом узла сравнения, первый вход которого объединен со входом

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

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

Количество ячеек стека, участвующих в сравнении, определяется длиной основы, распознаваемой в результате сравнений с правыми частями грамматических правил, содержащихся -в предложениях анализатора. С этой целью выходы N верхних ячеек блока 1 подключены ко входам регистра 4 опроса. Величина 0 является входом задания константы устройства. На чертеже представлена блок схема предлагаемого устройства. . Устройство состоит из блока 1 стековой памяти, регистра 2 сохранения, блока 3 ассоциативной памяти признаков, регистра 4 опроса, блока 5. задания начальных условий, блока 6 сравнения адресов, блока 7 памяти информационных слов, блока 8 памяти операторов, дешифратора 9 ошибок, блока 10 стековой памяти адресов возврата и блока 11 управления. Блок 11 управления содержит узел 12 памяти микрокоманд, дешифратор 13 адреса микрокоманд, регистр 14 адреса микрокоманд, формирователь 15 адреса, регистр 16 команд, счетчик 17, узеп 18 сравнения. На чертеже также обозначены вход 19 устройства, вход 20 задания начальных условий устройства, вход 21 задания коэффициента устройства. В основе работы устройства лежит реализация предложений, языка ФлойдаЭванса (языка продукций), с помощью которого можно легко построить любой аботающий по методу перенос-свертка. нализатор, Анализатор (программа анаиза) строится по грамматике языка лиопределяет максимальную длину основы вместе с контактом. Цепочка, содержащаяся Б блоке 1, параллельно сравнивается с цепочками, соответствующими предложениям анализатора и записанны- ми в блоке 3 признаков. В каждой ячейке содержится по одной цепочке. Если aa .писанная цепочка короче N, то неисполь зованные позиции заполняются специальным кодом (т.е. маскируются). Блок 5 задает пространство поиска, т.е. верхний и нижний адреса диапазона, совпадения в котором принимаются во внимание и фиксируются блоком 6.Занесение начальных границ осуществляется при Иницийции работы устройства.- По другому входу производится динамическое обновление границ. Блок 6 фиксирует номера ячеек, в которых произошли совпадения. Если совпадений несколько, то выбирается первое, соответствующее меньшему адресу. Адрес ячейки передается на первый выход. Если совпадений нет, на второй выход передается сигнал отсу.тст Вия совпадений, который поступает затем в дешифратор ошибок, который по ко ду границ идентифицирует ошибку и иницииг ет поиск конца анализируемого оператора блоком 11. В блоке 7 хранятся информационные слова, где содержится новая цепочка, ко заменяется цепочка, находящаяся в верхущке блока 1. На необходимость такой замены указывает бит Признак замены. Длину заменяемой цепочки (т..е количество ячеек стека) указывает поле Длина цепочки. Длина новой, цепочки для многих полезных классов грамматик не превышает одного символа. Новая цепочка в данном случае может содержать только метасим вол, тогда как стековые цепочки мо гут содержать как терминапьт, так и метасимволы. Код новой цепочки -передается на первый выход. Программирование на языке Флойда- Эванса анализаторов по грамматикам сла бого предшествования, грамматикам ограниченного правого контакта и др; требует, чтобы в некоторых предложениях верхняя ячейка блока 1 не участвовала в замене и сохраняла свое содержимое. Для этой цели служит регистр 2 сохранения, куда временно копируется содержимое верхней ячейки блока 1. Для управления сохранением служит бит Сохра нение, в информационном слове. На необходимость сканирования очередного сим вола программы и занесения его в блок 1 после выполнения замены указывает бит Скан. Бит Список указывает, что после замены и других действий вьшолняются операторы управления, записанные в блоке 8. Адрес первого оператора указан в поле Адрес, Адрес передается на третий выход, а вся остальная информация на второй выход блока 7. Предусмотрено выполнение следующих . операторов: QOTO - безусловный переход; GALL - вызов подпрограммы синтаксического анализа; - возврат из подпрюграммы; SS-T .- установка новых границ; EMU - конец анализа. Каждый оператор .содержит бит Признак продолжения, указывающий, что далее следует еще оператор, и два поля границ Верх и Низ, а также бит Скан, указывающий на необходимость сканирования очередного символа после выполнения оператора. Коды границ передаются на первый выход блока 8, а вся остальная информация - на второй выход. Оператор 5 ВТ - есть переход к следующему предложению, если после вызова подпрограммы необходимо сканирование, так как оператор RETURN возвращает управление к следующему за оператором CAL L оператору. В блоке 10 запоминается адрес возврата - на единицу увеличенный адрес оператора CALU. В исходном состоянии в блоке 1 содержится терминал - признак дна стека. Об окончании работьт анализатора свидетельствует появление в верхущке блока 1 цепочки # 2 где it - дно стека 2 начальный символ, к которому свернут анализируемый оператор языка, i - межоператорный разделитель. Терминальные символы программы первоначально распознаются и обрабатываются лексическим анализатором, передающим их на вход 19 устройства. Для семантического анализа и генерации кода можно воспользоваться теми же средствами, что и в известием устройстве, т.е. указанием адресов семантических процедур в информационных словах. Таким образом, за счет использования блока задания начальных условий, блока операторов, блока стеновой памяти адресов возврата, регистра сохранения, соединения нескольких верхних ячеек синтаксического стека с регистром опроса и других новых связей удается существенно уменьишть число г редложений анализатора. Уменьшение числа пред ложений анализатора происходит также за счет использования блока границ в сочетании со схемой дешифрации ошибок так как это позволяет исключить ряд диагностических сравнений с целью идентификации ошибок, что в данном случае производится автоматически по коду границ. Уменьшение числа предложений анализатора приводит в свою очередь к уменьшению числа замен, т.е. числа записей в синтаксический стек, что повышает скорость анализа пропорционально уменьшению объема анапизатора. Формула изоб ре т е н и Устройство для синтаксического анализа программ, содержащее бгюк стековой памяти, регистр опроса, блок ассоциативной памяти признаков, блок срав: нёнйя адресов, блок памяти информацион ных слов и блок управления, содержащий ; регистр команд, выход которого соедине с входом формирователя адреса, выход которого подключен к входу регис ра адреса микрокоманд, выход которого соединен с входом дешифратора адреса микрокоманд, выход которого подключен к входу узла памяти микрокоманд, первьШ выход которого подключен к вто(рому входу формирователя адреса, второй выход узла памяти микрокоманд соединен с управляющим входом блока стековой памяти, вход последнего соединен с первым выходом блока памяти информационных слов и является входом, устройства выходы Ы верхних ячеек блока стековой памяти соединены с входами регистра опроса, выход которого подклю чен к входу блока ассоциативной памяти признаков, выход блока сравнения адресов соединен с входом блока памяти информационных слов, второй илход которо го подключен к третьему входу формирователя адреса, отличающееся -гем,.что, с целью повышения быстродействия, в него введены блок задания начальных условий, блок памяти операторов блок стековой памяти адресов возврата, регистр сохранения, дешифратор ошибок, узел сравнения и счетчик,, выход которого соединен с третьим входом формирователя адресов блока управления, четвертый вход формирователя адресов соединен с выходом узла сравнения, первый вход которого объединен со входом блока стековой памяти и подключен к выходу регистра сохранения, управляющий вход которого соединен с первым входом счетчика и подключен к второму выходу узла памяти микрокоманд блока управления, выход верхней ячейки блока стековой памяти соединен с входом регистра сохранения, выход блока ассоциативной памяти признаков соединен с входом блока задания , начальнь1х условий, выход которого соединен с входом блока сравнения адресов, второй выход которого подключен к дешифратору-ошибок, выход которого объединен с вторым выходом блока памяти информационных слов, третий выход которого подключен к входу блока памяти операторов и соединен с входомотходом блока стековой памяти адресов возврата, первый выход блока памяти one- раторов соединен с входом дешифратора ошибок; и входом динамической установки начальных условий блока задания началзь- ных условий, вход начальной установки которого является входом начальной устайовки усгройства торой выход блока памяти операгоров подключен к входу регистра команд блока управления, а второй вход узла сравнения является входом задания константы устройства. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР .№ 674028. кл. G Об F 15/20, 1976. 2. Авторское свидетельство СССР № 377774, кл. Gi 06 F 9/ОО, 1968 (прототип).