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

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авт. свидетельства №

Заявлено 20ЛХ.1968 (¹ 1270855/18-24) с присоединением заявки №

Приоритет

Опубликовано 17.!Ч.1973. Бюллетень ¹ 18

Дата опуоликования описания 29.VI.1973

Ы. Кл. G 061 9/00

Комитет по лелем изобретений и открытий при Совете Министров

СССР

УДК 681.326.3 (088.8) Авторы изобретения

Б. Н. Малиновский, С. Б. Додонов и Л. Г. Козлов

Институт кибернетики АН Украинской ССР

Заявитель

УСТРОЙСТВО СИНТАКСИЧЕСКОГО АНАЛИЗА ПРОГРАММ

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

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

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

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

На фиг. 1 показана блок-схема предлагаемого устройства синтаксического анализа программ; на фиг. 2 — анализирующая таблица.

Оно состоит из постоянного ассоциативно5 го запоминающего устройства 1, регистра опроса, состоящего из входного регистра 2 и регистра 8 сформированного кода, блока 4 ассоциативных признаков, блока 5 индикаторов, блока б рабочих ячеек, выходного ре10 гистра 7 постоянного ассоциативного запоминающего устройства, схемы 8 контроля, регистра 9 ошибки, блока 10 прерывания и управления, регистра 11 основного тоода, регистра 12 чтения, регистра 18 записи, регистра

15 14 прерывания, регистра 15 адресов подпрограмм, регистра 1б Bcnoмогательного кода, блока 17 магазинной памяти.

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

25 фнг. 2 (- анись ПАЗУ означает постоянное ассоциативное запоминающее устройство, а номер столбца определяется номером регистра на фиг. 1).

Строка анализирующей таблицы содержит

30 код текущего символа Т; (столбец 2 табли377774 цы) для поиска необходимой строки совместно с кодом (столбец 3 таблицы), сформированным предыдущим символом Т, i программы.

Каждая строка таблицы содержит дополнительный разряд «ОШ» (ошибка), в котором всегда записана единица. Данный разряд используется для проверки текущего символа Т, программы.

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

Текущий символ Т; программы записывается на входной регистр 2 регистра опроса постоянного ассоциативного запоминающего устройства 1.

Затем производится поиск кода путем сравнения ассоциативного признака, записанного на регистре опроса (регистры 2 и 3) с ассоциативным признаком, записанным в блоке 4 ассоциативных признаков. При сравнении кодов, очевидно, только один из индикаторов блока 5 индикаторов останется в нулевом состоянии, и из блока б,рабочих ячеек .на выходной регистр 7 будет считан рабочий код, соответствующий найденному ассоциативному признаку. Затем схемой 8 контроля производится анализ регистра 9 ошибки. Поскольку произошло чтение некоторого кода на выходной регистр 7, то в регистре 9 ошибки будет записана единица:и, следовательно, работа устройства будет продолжаться. Если текущий символ Т; записан синтаксически неверно (т. е. символ

Т;) не соответствует коду, записанному на регистре 3), то соответствующий ассоциативный признак не будет найден, и поскольку чтения кода на выходной регистр 7 не происходит, регистр 9 ошибки останется в нулевом состоянии. В этом случае схема 8 контроля выдает, сигнал в блок 10 прерывания и управления, который прекращает работу устройства, а следовательно, и синтаксичес5 кий анализ программы. После чтения кода на выходной регистр 7 и анализа содержимого регистра 9 ошибки выполняемые действия — формирование основного кода, анализ регистра чтения, регистра записи, регистра

10 прерывания — аналогичны действиям прототипа.

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

15 регистре 15 для выбора соответствующей генерирующей подпрограммы. Блок 10 прерывания и управления прекращает работу уст ройства, когда на его вход с регистра 11 поступает код «Конец программы», 20

Предмет изобретения

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

377774

1 !

I !

Сигналы прерывания и упраЬ ения

Фиъ, 1

Фиг 2

Составитель Е. Иванеева

Техред Т. Курилко

Корректор Н. Стельмах

Редактор И. Гавренкова

Заказ 1741 7 Изд. Ма 1394 Тираж 647 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров CC(.1Москва, 5К-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2