Устройство для синтаксическогоКОНТРОля пРОгРАММ Советский патент 1981 года по МПК G06F11/263 

1

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

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

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

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

В этом устройстве очередной проверяемый символ (терм) программы поступает на входной регистр. Затем

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

0 фиксированного подмножества правил грс1мматики языка и записывается на выходной регистр, после чего производится сравнение содержимых выходного и всп я4огательного регистров

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

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

Q затратам времени. Цель изобретения - повьииение быст родействия , т.е. уменьшение времени синтаксического контроля программ. Поставленная цель достигается тем, что в устройство для синтаксического контроля программ, содержащее входной регистр, блок долговреме ,ной памяти, блок сравнения, выходной регистр, регистр адреса, блок индикации и блок стековой памяти, причем первый вход входного регистра является входом устройства, выход регист ра адреса соединен со входом блока долговременной памяти, выход которого соединен с первым входом выходног регистра, первый выход выходного регистра соединен с первымвходом блока сравнения, первый и второй выход которого соединен соответственно со вторым входом выходного ре гистра, с первым входом блока индика ции, выхсй блока стековой памяти сое динен со вторым входом блока сравнения, введен блок ассоциативной долго временной памяти и дешифратор опера ций, причем выход входного регистра соединен со входом блока ассоидаативной долговременной памяти, выход которого соединен со входом регистра адреса, первый и второй вьгходы регис ра адреса соединены соответственно с первым входом входного регистра, со вторым входом блока индикации, второй и третий выходы выходного регистра соединены соответственно со вторым входом входного регистра, со входом дешифратора операций, выход которого соединен со вторым входом блока стековой памяти. На фиг. 1 представлена блок-схема ассоциативного устройства для контроля программ; а на фиг. 2 - F, G - массивы грамматики алгоритмического языка. Устройство содержит вход 1, входной регистр 2, блок 3 ассоциативной долговременной памяти, регистр 4 адреса, блок 5 долговременной памяти , выходной регистр б, дешифратор 7 операций, блок 8 сравнения, блок 9 стековой памяти и блок 10 индикации. Грамматика языка, записанная в блоке 3 ассоциативной долговременной памяти и в блоке 5 долговременной памяти, содержит два основных массива F и 6, Массив F представляет собой таблицу соответствия термов и синтермов, размещается только в бло ке 3 и занимает п( logj, К -«-Оод а п бит, где п - число термов, а К - чис ло синтермов в алгоритмическом . G - массив состоит из пяти подмас сивов G , 6-2, 65, G, Gj, расположенных вертикально, причем горизонтальное сечение всех подмассивов . рбразует одно правило грамматики, Вва из них - G и G занимают одно слово в блоке 3, а три других - G , i Сд и Gj соответствующее слово в блоке 5. G. содержит ассоциативный признак подмножества правил грамматики и занимает flog j г бит, где ,г - общее число подмножеств правил в грамматике данного алгоритмического языка; G 2 содержит код синтерма и занимает flog 2 к бит; GJ - содержит ассоциативный признак подмножества правил-приемников для подмножества с признаком указанным в G и занимает log, г бит;G. - содержит код операции со стековой памятью и занимает ;2 бита; Gj - содержит операнд операции с кодом указанным в G и занимает р од 2. г бит. Горизонтальное сечение G - массива в общем составляет 3 logg г + + ft 092 К 1 -f 2 бит, а весь G - массив L(3Uog2r + logg ) бит, где L- длина всего массива G, т.е. количество правил в грамматике алгоритмического языка. Общий объемпамяти под массивы Г и G составитп( logj к + bog-i п) + 1(3 у од 2 г + logj К + 2) . Причем на долю блока 3 приходится п ( log 2 к + logo п) + + Ь (logj rj + log 2 К), . а на долю блока 5 соответственно 2L( log 2 г + 1) бит. Работа устройства происходит следующим образом. В исходном состоянии стековая память свободна. На входном регистре 2, состоящем из двух частей, в первой части, содержащей log2 г разрядов записан ассоциативный признак начального подмножества правил грамматики, а на вторую часть, содержащую {log2 п разрядов в первом такте работы устройства по входу 1 подается первый символ (терм) проверяемой программы, в первом такте работы участвует только вторая часть входного регистра 2. Поступивший на нее терм служит ассоциативным признаком для поиска в массиве F и во время первого такта из блока 3 с помощью ассоциативной выборки считывается соответствующий данному терму синтерм, который с выхода регистра 4 адреса поступает вновь на входной регистр, заменяя собой находящийся там терм. Таким образом,к концу первого такта работы на регистре 2 комбинация ассоциативный признак текущего подмножества правил грамматики + + терм преобразуется к виду ассоциативный признак текущего подмножества правил, грамматики + синтерм. Так происходит в том случае, если сравнение произошло и для поступившего терма найдется соответствующий

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

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

В случае отсутствия сидибок код G поступает на дешифратор 7 операдии. Если код G означает пустую юперацшй, то код G2пepeпиcывaeтcя в первую часть регистра 2/ если код IG означает запись в сток, то в |верхнюю ячейку блока 9 стековой:памяти производится запись кода Gg, после чего код G переписывается в первую часть регистра 2, если код GA означает чтение иЗ:стека, то из верхней ячейки стековой памяти на блок 8 сравнения подается код, который сравнивается в блоке 8 с кодом Gf. В случае их совпадения сигнал с выходов блока 8 переписывает код Gj в первую часть регистра 2, а содержимое верхней ячейки стековой памяти удаляется. В противном случае символ с инверсных выходов блока 8 поступает в блок 10, что соответствует ошибке типа нарушение скобочной структуры в проверяемой программе (например не для всех begin имеются соответствующие end).

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

Таким Образом длительность поиска в массиве F и G в предлагаемом устройстве не зависит .от размеров этих массивов- и является величиной постоянной.

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

10

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

Устройство для синтаксического контроля программ, содержащее входной регистр, блок долговременной па,мяти, блок сравнения, выходной ре:Гистр, регистр адреса, блок индикации и блок стековой па1мяти, причем (первый вход входного регистра является входом устройства, выход регистРа адреса соединен со входом блока долговременной памяти, выход которого соединен с.первым входом выходного регистра, первый выход выходного регистра соединен с первым входом

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

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

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

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

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

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

1.Авторское свидетельство СССР 247628, кл. о Об F 11/00, 1970.

2.Аззторское свидетельство СССР № 333558, кл. G Об F 11/00.

3. Авторское свидетельство СССР 328460, кл. G 06 F 11/00, 1970 (прототип).