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

 

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

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

Рвсп

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

<11 807299 (61) Дополнительное к авт. свид-ву -. (22) Заявлено 220578 (21) 2618588/18-24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 2302.81. Бюллетень Йо 7

Дата опубликования описания 230231 (51)М. Кл.З

G 06 F 11/00

Государственный комитет

СССР но делам нзобретеннй н открытнй (53) УДК 681. 326 (088.8) (72) Авторы изобретения

А.А., Гужавин и О.Г. Кокаев (71) Заявитель

Ульяновский политехнический институт — -=.:

М (54) УСТРОИСТВО 1ЛЯ СИН1АКСИЧЕСКОГО КОНТРОЛЯ

ПРОГРАММ

Изобретение относится к использованию в вычислительной технике языков для представления программ и предназначено для проверки последовательностей символов, построенных по определенной совокупности правил, называемых грамматикой языка программирования в форме диаграмьы перехода (R PRS грамматики, RS - грамматики).

Известны устройства синтаксичес- кого контроля, применяемые как субблоки устройств подготовки данных и ввода программ в ЭВМ (1) и (21.

Недостатком известных устройств 15 является низкое быстродействие, которое объясняется необходимостью полного пвребора синтермов в фиксированном множестве правил грамматики контролируемой программы, 20

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

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

Однако такая организация процесса контроля приводит к значительным затратам времени.

807299

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

Поставленная цель достигается тем, что в устройство для синтаксического контроля программ, содержащее входной регистр, блок долговремен;ной памяти, блок сравнения, выходной регистр, регистр адреса, блок индикации и блок стековой памяти, причем первый вход входного регистра является входом устройства, выход регист- о ра адреса .соединен со входом блока долговременной памяти, выход которого соединен с первым входом выходного регистра, первый выход выходного регистра .соединен с первым входом 15 блока сравнения, первый и второй . выход которого соединен соответственно со вторым входом выходного регистра, с первым входом блока индикации, выход блока стековой памяти сое- 2О динен со вторым входом блока сравнения, введен блок ассоциативной долговременной памяти и дешифратор операций, причем выход входного регистра соединен со входом блока ассоциативной долговременной памяти, выход которого соединен со входом регистра адреса, первый и второй выходы регистра адреса соединены соответстгврнно с первым входом входного регистра, со вторым входом блока индикации, второй и третий выходы выходного регистра соединены соответственно со вторым входом входного регистра, со входом дешифратора операций, выход которого соединен со вторым входом блока стековой памяти.

На фиг. 1 представлена блок»схема ассоциативного устройства для

Контроля программ; а на фиг. 2 — F, G - массивы грамматики алгоритми- 4О ческого языка.

Устройство содержит вход 1, входной регистр 2, блок 3 ассоциативной долговременной памяти, регистр 4 адреса, блок 5 долговременной па- 45 мяти, выходной регистр б, дешифратор 7 операций, блок 8 сравнения, блок 9 стековой памяти и блок 10 индикации.

Грамматика языка, записанная в блоке 3 ассоциативной долговременной памяти и в блоке 5 долговременной памяти, содержит два основных массива F и. 6. Массив F представляет собой. таблицу соответствия термов и синтермов, размещается только в блоке 3 и занимает и((! оя К ) +(log g и)) бит, где n — число термов, а К вЂ” число синтермов в алгоритмическом язы-. ке.

G — массив состоит из пяти подмас- @) сизов G„, G, G>, 6,, G<, расположенных вертикально, причем горизонтальное сечение всех подмассивов . образует одно правило грамматики, ва из них - G и G занимают одно у слово в блоке 3, а три других — G>, G и G соответствующее слово в блоке 5. G< содержит ассоциативный признак подмножества правил грамматики и занимает P og > r ) бит, где ,г - общее число подмножеств правил в грамматике данного алгоритмического языка, G - содержит код синтерма и занимает flog К ) бит,"

G - содержит ассоциативный призз нак подмножества правил-приемников для подмножества с признаком указанным в 6 и занимает (!од г ) бит;

G - содержит код операции со стековой памятью и занимает 2 бита;

G - содержит операнд операций с кодом укаэанным в 64 и занимает (l og < г ) бит.

Горизонтальное сечение G - массива в общем составляет 3 (log r )+

+ (!о9 КJ+ 2 бит, а весь G - массив L (3ЬОя, "1 + (ОДА KJ+ бит, где Ь вЂ” длина всего массива G, т.е. количество правил в грамматике алгоритмического языка. Общий обьем памяти под массивы F u G составит

n(Eloge К) + Llog и)) + Ь(3 (Iog2 г) + (logy К)+ 2).

Причем на долю блока 3 приходится (flog < K) + 0О9д и3) +

+ Ь ((logy Г + Llog z К)) у а на долю блока 5 соответственно

2L(I log > r ) + 1) бит.

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

В исходном состоянии стековая память свободна. На входном регистре

2, состоящем из двух частей, в первой части, содержащей (log r ) разрядов записан ассоциативный признак начального подмножества правил грамматики, а на вторую часть, содержащую (log2 и ) разрядов в первом такте работй устройства по входу 1 подается первый символ (терм) проверяемой программы. В первом такте работы участвует только вторая часть входного регистра 2. Поступивший на нее терм служит ассоциативным признаком для поиска в массиве F и во время первого такта иэ блока 3 с помощью ассоциативной выборки считывается соответствующий данному терму синтерм, который с выхода регистра

4 адреса поступает вновь на входной регистр, заменяя собой находящийся там терм. таким образом,к концу первого такта работы на регистре 2 комбинация "ассоциативный признак текущего подмножества правил грамматики +

+ терм" преобразуется к виду "ассоциативный признак текущего подмножества правил, грамматики + синтерм".

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

807299 ему синтерм. В противном случае, если сигнал на выходе регистра 4 адреса равен 0 с инверсных выходов регистра 4 адресов на блок 10 индикации поступает сигнал, соответствующий ошибке типа "недопустимый символ" в проверяемой программе.

В случае отсутствия ошибок в следующем такте работы содержимое обоих частей регистра 2 служит признаком для ассоциативного поиска соответствующего синтерма в фиксированном подмножестве правил грамматики, т.е. подмассивах G< и 6 . Если укаэанные коды совпали, то на регистре 4 возникает код возбуждения для блока 5 долговременной памяти, по которому из блока 5 на выходной регистр

6 будут выданы коды G>, G u G .. В противном случае, если сигнал йа выходе регистра равен нулю, с инверсных выходов .регистра 4 на блок 10. поступает сигнал, соответствующий ошибке типа "недопустимое сочетание допустимых символов" в проверяемой программе.

В случае отсутствия ошибок код

G4 поступает на дешифратор 7 операции. Если код G4 означает "пустую, операцию", то код G переписывается в. первую часть регистра 2; если код

,64 означает "запись в сток", то в

;верхнюю ячейку блока 9 стековой памяти производится запись кода 6 после чего код G> переписывается в первую часть регистра 2; если код

6 означает "чтение из стека", то из верхней ячейки стековой памяти на блок 8 сравнения подается код, который сравнивается в блоке 8 с кодом G . В случае Их совпадения сигнал с выходов блока 8 переписывает

5 код G в первую часть регистра 2, а содержимое верхней ячейки стековой памяти удаляется. В противном случае символ с инверсных выходов блока

8 поступает в блок 10, что соответствует ошибке типа "нарушение скобочной структуры" в проверяемой программе (например не для всех begin имеются соответствующие end).

В случае отсутствия ошибок код

G всегда переписывается с выходного регистра 6 на входной регистр 2, подготавливая устройство к приему следующего терма, и описанные выше действия производятся с новым фикси- роваинвм подмножеством правил грамматики, ассоциативный признак которого и представляется кодом G> . Таким образом длительность поиска в массиве F u G в предлагаемом устройстве не зависит .от размеров этих массивов и является величиной постоянной.

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

Формула изобретения ды выходного регистра соединены соответственно со вторым входом входного регистра, со входом дешифратора oneраций, выход которого соединен со вторым входом блока стековой памяти.

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

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

Р 247628, кл. G 06 F 11/00, 1970.

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

9 333558, кл. G 06 F 11/00 °

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

9 328460, кл. G 06 F 11/00, 1970 (прототип).

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

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

40 соответственно с первым входом входного регистра, со вторым входом блока индикации, второй и третий выхо