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

Союз Советских Социалистическими РеспубликОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ 11807299(61) Дополнительное к авт. свид-ву(22) Заявлено 220578 (21) 2618588/18-24с присоединением заявки йо(51)М. Кл. 6 06 Г 11/00 Государствеииый комитет СССР ло делам изобретеиий и открытий(71) Заявитель яновский ехнический инстит ОИСТВО ДЛЯ СИНТАКСИЧЕСКОГО КОНТРО ПРОГРАММ 54) Изобретение относится к использованию в вычислительной техникеязыков для представления программи предназначено для проверки последовательностей символов, построенных по определенной совокупностиправил, называемых грамматикой языка программирования в форме диаграмьы перехода (Р - грамматики, РВ 5грамматики, Рб - грамматики),Известны устройства синтаксичес-кого контроля, применяемые как субблоки устройств подготовки данныхи ввода програми в ЭВМ 11 и (21.Недостатком известных устройствявляется низкое быстродействие, которое объясняется необходимостью полного пвребора синтермов в фиксиро"ванном множестве правил грамматикиконтролируемой программы,Наиболее близким по техническойсущности к предлагаемому являетсяустройство, содержащее входной регистр проверяемой программы, вспомогательный регистр, долговременную истекрвую памяти, регистр адреса, выходной регистр и схему сравнения.В этом устройстве очередной проверяемый символ (терм) программыпоступает на входной регистр. Затем из первой части долговременной памяти по адресу, указанному в регистре адреса считывается соответствующий этому терму синтерм (обобщенный символ соответствующий целому синтаксическому классу термов), который записывается на вспомогательный регистр после чего из второй части долговременной памяти считывается синтерм из фиксированного подмножества правил грамматики языка и записывается на выходной регистр, после чего производится сравнение содержимых выходного и вспомогательного регистров 15 на схеме сравнения. Если сравнениепроизошло, то анализируется следующий символ программы, в противном случае, на выходной регистр поступает следующий синтерм фиксированного под множества правил грамматики и вновьпроизводится сравнение содержимого выходного и вспомогательного регистров. В том случае, если это фиксированное подмножество правил граьмати 2 з ки исчерпано, а сравнение не произошло, выдается сигнал синтаксической ошибки 3 ,Однако такая организация процеса контроля приводит к значительныматратам времени.Цель изобретения - повьииение быстродействия, т.е, уменьшение времени синтаксического контроля программ.Поставленная цель достигается тем, что в устройство для синтаксического контроля программ, содержащее входной регистр, блок долговремен;ной памяти, блок сравнения, выходной регистр, регистр адреса, блок индикации и блок стековой памяти, причем первый вход входного регистра является входом устройства, выход регист О ра адреса соединен со входом блока долговременной памяти, выход которого соединен с первым входом выходного регистра, первый выход выходного регистра .соединен с первымвходом 15 блока сравнения, первый и второй . выход которого соединен соответственно со вторым входом выходного регистра, с первым входом блока индикации, выход блока стековой памяти сое О динен со вторым входом блока сравнения, введен блок ассоциативной долговременной памяти и дешифратор операций, причем выход входного регистра соединен со входом блока ассоциативной долговременной памяти, выход которого соединен со входом регистра адреса, первый и второй выходы регистра адреса соединены соответств 1 знно с первым входом входного регистра, со вторым входом блока индикации, второй и третий выходы выходного регистра соединены соответственно со вторым входом входного регистра, со входом дешифратора операций, выход которого соединен со вторым входом блока стековой памяти.На фиг. 1 представлена блоксхема ассоциативного устройства для Контроля программ; а на фиг. 2 - Г,6 - массивы грамматики алгоритми ческого языка.устройство содержит вход 1, входной регистр 2, блок 3 ассоциативной долговременной памяти, регистр 4 адреса, блок 5 долговременной памяти, выходной регистр б, дешифратор 7 операций, блок 8 сравнения,блок 9 стековой памяти и блок 10индикации.Грамматика языка, записанная в блоке 3 ассоциативной долговременной памяти и в блоке 5 долговременной памяти, содержит два основных массиву Г и. 6. Массив Г представляет собой таблицу соответствия термов исинтермов, размещается только в бло- зоке 3 и занимает и( 109 К+09и ) бит, где и - число термов, а К - число синтермов в алгоритмическом язы-.ке.С - массив состоит из пяти подмас- р сизов 6, С, Сз, 6,1, С, расположенных вертикально, причем горизонтальное сечение всех подмассивов . образует одно правило грамматики,3 ва из них - 6, и С занимают одно у слово в блоке 3, а три других - 0,С и 6 соответствующее слово в блоке 5. 6 содержит ассоциативныйпризнак подмножества правил грамматики и занимает 109 1 гбит, где,г - общее число подмножеств правилв грамматике данного алгоритмического языка,6- содержит код синтерма и занимает 1,одКбит,"6 - содержит ассоциативный приззнак подмножества правил-приемниковдля подмножества с признаком указанным в 6, и занимает 109 г 1 бит;6 - содержит код операции состековой памятью и занимает 2 бита;6 - содержит операнд операцийс кодом укаэанным в 64 и занимаетод г бит,Горизонтальное сечение 6 - массива в общем составляет 3 109 г++ 109 К + 2 бит, а весь С - массив Ь (3 0092 г 1 + ой К 3+ 2)бит, где ( - длина всего массива С,т.е, количество правил в грамматике алгоритмического языка. Общийобьемпамяти под массивы Г и 6 составити(Е 1 о 92 К 3 + Е 109 иЗ) + Ь(3092 г + 1 о 9 1 К+ 2),Причем на долю блока 3 приходитсяи ( 1109К + 110 дд и) + + Ь (109 г+ 109К 1) у а на долю блока 5 соответственно 2 109г ) + 1) бит.Работа устройства происходит следующим образом.В исходном состоянии стековая память свободна, На входном регистре 2, состоящем из двух частей, в первой части, содержащей 09 гразрядов записан ассоциативный признак начального подмножества правил грамматики, а на вторую часть, содержащую 1092 иразрядов в первом такте работы устройства по входу 1 подается первый символ (терм) проверяемой программы. В первом такте работы участвует только вторая часть входного регистра 2. Поступивший на нее терм служит ассоциативным признаком для поиска в массиве Е и во время первого такта иэ блока 3 с помощью ассоциативной выборки считывается соответствующий данному терму синтерм, который с выхода регистра 4 адреса поступает вновь на входной регистр, заменяя собой находящийся там терм, таким образом,к концу первого такта работы на регистре 2 комбинация "ассоциативный признак текущего подмножества правил грамматики + + терм" преобразуется к виду "ассоциативный признак текущего подмножества правил, грамматики + синтерм", Так происходит в том случае,. если сравнение произошло и для поступившего терма найдется соответствующийему синтерм, В противном случае, если сигнал на выходе регистра 4 адреса равен 0 с инверсных выходоврегистра 4 адресов на блок 10 индикации поступает сигнал, соответствующий ошибке типа 1 недопустимый символ"в проверяемой программе.В случае отсутствия ошибок в следующем такте работы содержимое обоихчастей регистра 2 служит признакомдля ассоциативного поиска соответствующего синтерма в фиксированномподмножестве правил грамматики, т.е.подмассивах С 1 и 6. Если укаэанные коды совпали, то на регистре 4возникает код возбуждения для блока 5 долговременной памяти, по которому из блока 5 на выходной регистр6 будут выданы коды С, С и 6Впротивном случае, если сигнал йа выходе регистра равен нулю, с инверсных выходов регистра 4 на блок 10поступает сигнал, соответствующийошибке типа "недопустимое сочетаниедопустимых символов" в проверяемойпрограмме,В случае отсутствия ошибок код64 поступает на дешифратор 7 операции. Если код 64 означает пустую,операциюф, то код 6 переписываетсяв. первую часть регистра 2; если код;верхнюю ячейку блока 9 стековой памяти производится запись кода Спосле чего код С переписывается впервую часть регистра 2; если кодС означает "чтение из. стекаф, тоиз верхней ячейки стековой памятина блок 8 сравнения подается код, который сравнивается в блоке 8 с кодом 6 . В случае Их совпадения сигнал с выходов блока 8 переписываеткод 6 в первую часть регистра 2, асодержимое верхней ячейки стековойпамяти удаляется. В противном случае символ с инверсных выходов блока8 поступает в блок 10, что соответствует ошибке типа "нарушение скобочной структуры" в проверяемой программе (например не для всех Ьедоимеются соответствующие епд).В случае отсутствия ошибок код6 всегда переписывается с выходного регистра 6 на входной регистр 2,подготавливая устройство к приемуследующего терма, и описанные вышедействия производятся с новым фикси-роваинвм подмножеством правил грамматики, ассоциативный признак которого и представляется кодом Сз, Таким образом длительность поиска в массиве Р и 6 в предлагаемом устройстве не зависит .от размеров этих массивов и является величиной постоянной.Предлагаемое устройство для синтаксического контроля программ обладает быстродействием в 1,5 раза большим, чем известное.Формула изобретенияУстройство для синтаксическогоконтроля программ, содержащее входной регистр, блок долговременной па,мяти, блок сравнения, выходной ре 1 гистр, регистр адреса, блок индикации и блок стековой памяти, причем первый вход входного регистра является входом устройства, выход регист О ра адреса соединен со входом блокадолговременной памяти, выход которого соединен с.первым входом выходного регистра, первый выход выходного регистра соединен с первым входом блока сравнения, первый и второй выход которого соединены соответственно со вторым входом выходного регистра, с первым входом блока индикации, выход блока стековой памяти соединен со вторым входом блока срав 1 невия, о т л и ч а ю щ в е с я тем, что, с целью повышения быстродейст;вия в устройство введен блок ассоциативной долговременной памяти и дешифратор операций, причем выход входного регистра соединен со входом блока ассоциативной. долговременной памяти, выход которого соединен со входом регистра адреса, первый и второй выходы регистра адреса соединены 40 соответственно с первым входом входного регистра, со вторым входом блока индикации, второй и третий выходы выходного регистра соединены соответственно со вторым входом входного регистра, со входом дешифратора операций, выход которого соединен совторым входом блока стековой памяти.ИстОчники инфОрмации рпринятые во внимание .при экспертизе1. Авторское свидетельство СССРР 247628, кл. 6 06 Г 11/00, 1970.2. Авторское свидетельство СССР9 333558, кл. 6 06 Г 11/00.3. Авторское свидетельство СССРО 328460, кл. 6 06 Е 11/00, 1970