Устройство синтаксического контроля програмb^ibjii-iotei-ca

Устройство синтаксического контроля програмb^ibjii-iotei-ca

Иллюстрации

Показать все

Реферат

 

328460

О П И С А Н И Е

ИЗОБРЕТЕН Ия

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

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

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

Республик

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

Заявлено 09. Ill.1970 (№ 1412342/18-24) с присоединением заявки №

Приоритет

Опубликовано 02,11.1972. Бюллетень ¹ 6

Дата опубликования описания 27.III.1972

М. Кл. G 06f 11/00

G 06f 15/48

Комитет ао лелем изобретеиий и открытий.ари Совете Микистров,СССР

УДК 681.327(088.8) Авторы изобретения И. В. Вельбицкий, В. Н. Медведева, Г. А. Михайлов и Е. Л. Ющенко

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

Заявитель!

, «." е "ъ р

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

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

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

В,предлагаемом устройстве для упрощения и уменьшения габаритов устройства стековая память соединена с регистром адреса и выходным регистром долговременной памяти.

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

Устройство состоит из входного регистра 1, вспомогательного регистра 2, схемы сравнения 8, выходного регистра 4, долговременной памяти 5, регистра адреса б и стековой памяти .7, В качестве основного символа для описания грамматики языка используется синтерм. Соответствие между термами и синтермами задано специальной таблицей W, занимающей

n(loggk) разрядов, где и — число термов, k— число синтермов в языке. Грамматика языка записана в долговременной памяти в виде двух массивов: R u W.

R-массив условно разбит па некоторые подмассивы, в каждом пз которых расположено несколько (некоторое число) элементов массива, каждый пз которых занимает одно слово долговременной памяти и состоит пз семи кодов:

Rl эквивалентно Rl (занимает (lo< k) разрядов);

R2 эквивалентно R2;

ЯЗ эквивалентно КЗ;

R4 эквивалентно R4;

R5 признак того, что данный подмасспв может быть продолжен, причем адрес продолжения подмасспва указан на вершине стека (занимает 1 разряд);

R6 эквивалентно R6 (занимает в общем случае (log2L) разрядов, где l — длина всего

®о массива Р;

R7. Если в ЛЗ данного элемента есть признак чтения из стековой памяти, то R7 — адрес соответствующего данному элементу элемента R-массива, у которого в R2 стоит при25 знак записи в стековую память; в противном случае R7 либо пусто, либо является адресом

«возврата», т. е. адресом, записываемым в стек и являющимся адресом продолжения соответствующего данному элементу подмасси30 ва, содержащего признак R5 в своем послед3 8460

25 нем элементе (в общем случае R7 занимает (log 1.) разрядов элемента R-массива). В общем случае элемент R-массива занимает ((1о k) +4+2 (1од Ц) разрядов, а вся R-грамматика — (@(log k)+L ((log k)+4+2(log L) ) бит долговременной памяти.

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

R7. Окончание каждой подграмматики отмечается признаком М.

Для приведенного выше примера языка Rграмматика (см. фиг. 1) занимает (16 4»+24 (4+4+2 6) =544 бит долговременной памяти.

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

В исходном состоянии стековая память свободна, регистр адреса отмечает адрес начального подмассива R-грамматики, у которого в

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

Первый символ, проверяемой программы записывается на входной регистр. Затем из таблицы И долговременной памяти по адресу на регистре адреса б считывается соответствующий этому символу синтерм и записывается на вспомогательный регистр, после чего из R-массива долговременной памяти по адресу на регистре адреса б считывается первый элемент начального подмассива и записывается на выходной регистр. Затем производится сравнение кода Rl на выходном регистре с кодом на вспомогательном регистре. Сравнение производится с помощью схемы 3. Если указанные коды не сравнялись, то к коду адреса на регистре адреса прибавляется единица и считывается следующий элемент начального подмассива. Указанные действия продолжаются до элемента, у которого в R4 стоит признак либо до элемента, у которого код R l на регистре выходном совпал с кодом на вспомогательном регистре.

В первом случае вырабатывается сигнал синтаксической ошибки (СОШ), так как ни один из элементов в Rl начального подмассива не сравнился с первым синтермом проверяемой программы. Напомним, что в Rl начального подмассива записаны коды синтермов, «оторые могут быть первыми в программе данного алгоритмического языка. Если первый синтерм проверяемой программы, полученный с помощью таблицы В из первого символа программы, не сравнился ни с одним из синтермов в Rl данного подмассива, следовательно, он ошибочно написан первым, т. е. синтаксически неверно.

Во втором случае, когда код Rl на выходном регистре 4 совпал с кодом на вспомогательном регистре, анализируется содержимое

R7 на выходном регистре 4. Если R7 пусто, производится передача кода Rá с выходного регистра долговременной памяти на регистр

55 б0

65 адреса, т. е. на этот регистр записывается адрес начального элемента подмассива, у которого в Rl записаны коды синтермов, которые в проверяемой программе могут идти следом за синтермом на вспомогательном регистре.

Если R7 не пусто, производится запись кода

R7 в стековую память и тем самым подготавливается адрес возврата, т. е. адрес продолжения R-массива после некоторой подграмматики. Затем производится передача кода R6 с выходного регистра, долговременной памяти на регистр адреса.

После этого на входной регистр вызывается следующий символ проверяемой программы, по которому из долговременной памяти на вспомогательный регистр считывается код соответствующего синтерма, затем на выходной регистр по адресу на регистре адреса считываются элементы R-массива, коды Rl которых сравниваются с кодом на вспомогательном регистре. Если просмотрен весь подмассив, т. е. проанализирован элемент, содержащий признак в R4, и не получено сравнение кода

Rl с содержимым вспомогательного регистра, анализируется R5 текущего элемента R-массива.

При отсутствии признака R5 устройством вырабатывается сигнал синтаксической ошибки, при наличии признака производится чтение из стековой памяти и передача на регистр адреса считанного адреса продолжения текущего подмассива. По новому адресу на регистре адреса на выходной регистр считывается элемент R-массива, коды Rl которых сравниваются с кодом на вспомогательном регистре и т. д., аналогично описанному.

Указанные действия соответствуют элементам массива долговременной памяти, у которых отсутствуют признаки R2, R3.

В случае, если элемент на выходном регистре, у которого Rl совпал с кодом на вспомогательном регистре, имеет в R2 признак записи в стековую память, то замене кода на регистре адреса на код Rá предшествует запись текущего значения кода на этом регистре и признака ЛЗ в стековую память. B остальном действия не отличаются от вышеописанных.

В случае, если элемента на выходном регистре, у которого код R l совпал с кодом на вспомогательном регистре, имеет в ЯЗ признак, то записи кода Rá на регистр адреса предшествует сравнение кода на вершине стековой памяти с кодом R7 и R3 на выходном регистре. Если эти коды совпали, то содержимое верхней ячейки стека удаляется и производятся описанные выше действия по переписи кода Яб на регистр адреса и т. д. Если же эти коды не совпали, то к содержимому стековой памяти прибавляется единица и описанные выше действия производятся с новым, следующим элементом данного подмассива.

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

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

R а2 Яз ю

Ю

h

Р

Р

1

3

5 И б 11

10 х

Я ир

27

Щ а

29 ф у9

Л л

%ф ею

86

37

38

Я

+71 л ъ (РУ3 1

Составитель В. Богатырев

Техреду Т. Ускова

Корректор И. Шматова

Редактор А. Батыгин

Заказ 667/10 Изд. № 173 Тираж 448 Подписное

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

Москва, K-35, Раугпская наб., д. 4/5

Типография, пр. Сапунова, 2 жении приведенного выше алгоритмического языка могут быть i, b, р, n,, t.

Устройство синтаксического контроля программ, содержащее входной регистр прове95 Рб ! 22

19

23

И

36

23 оя за

23

1ф

1Ф

32

19

19

1 ЗЮ

11 33 зе 25

1 35