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

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

Иллюстрации

Показать все

Реферат

 

О ПИ С-А Н И Е

ИЗОБР ЕТЕ НИЯ

247628

Саюэ Соеетвкиэ

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

Республик

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

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

Заявлено 19.11.1968 (№ 1220026/18-24) с присоединением заявки №

Приоритет

Опубликовано 04.VI1.1969. Бюллетень № 22

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

Кл. 42mз, 11/02

МПК G 061

УД К 681.326.77 (088.8) Комитет по делам изобретений и открытий при Совете Министров

СССР

Автор изобретения

И. В. Вельбицкий

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

Заявитель

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

ПРОГРАММ

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

Известно устройство для синтаксического контроля программ, записанных на алгоритмическом языке, состоящее из входного ре гистра, схемы сравнения, выходного регистра, долговременной памяти, регистра адреса и стековой памяти (авт. св. № 236861).

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

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

На чертеже изображена блок-схема устройства.

Устройство состоит из входного регистра 1. вспомогательного регистра 2, схемы сравнения 8, выходного регистра 4, долговременной памяти 5, регистра адреса б и стековой памяти 7.

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

5 грамматики языка используют так называемый синтерм (синтаксический терм). Одному синтерму могут соответствовать несколько основных символов (термов) языка, каждый из которых имеет тот же синтаксис использо10 вания в языке. Это значит, что для любого предложения языка замена одного символа другим, соответствующим одному и тому же синтерму языка, не выводит это предложение из языка, т. е. не превращает его в «непред15 ложение» данного языка. Соответствие между термами и синтермами задается специальной таблицей ы, каждой строке которой соответствует терм языка (номер строки совпадает с кодом соответствующего тер ма) . В каждой

20 строке записан соответствующий этой строке синтерм языка. В долговременной памяти устройства синтаксического контроля таблица ю, очевидно, занимает n(1og К) разрядов, где и — число термов, К вЂ” число синтермов в язы.

25 ке.

Грамматика языка записывается в ДЗУ в виде одного R-массива. Весь массив условно разбит на некоторые подуровни, в каждом из которых располагается несколько (некоторое

50 число) элементов массива. Каждый элемент

247628 массива занимает одно слово ДЗУ и состоит из семи ч астей:

R> — код синтерма языка (занимает (1од К) разрядов);

R — эквивалентно R 5

Rg — эквивалентно R, R4 — эквивалентно R4,.

R5 — эквивалентно R„.-;

Re — эквивалентно Rg (занимает в общем случае (loggNI разрядов, где N — R-, длина все- 10

ro массива R);

Я, эквивалентно R-, (в общем случае R> также занимает (log„ .N) разрядов элемента массива R).

В общем случае элемент указанного массива R занимает ((1одК) + 4+ 2(log>N)) разрядов.

Таким образом, в долтовременной памяти исходные данные задаются в виде двух массивов — и и R и занимают в общем случае >0

n(log>K)+N ((log>K)+ 4+2(log> V)) разрядов.

Работа устройства заключается в следующем.

В исходном состоянии стековая память свободна, регистр адреса отмечает адрес начального подуровня массива R, у которого в R> записаны коды синтермов, которые могут быть ®О первыми в программе данного алгоритмического языка.

Первый символ проверяемой программы записывается на входной регистр I. Затем из

w-таблицы ДЗУ по адресу на регистре считывается соответствующий этому символу синтерм, записываемый после считывания на вспомогательный регистр 2. После этого из R-массива ДЗУ по адресу на регистре 6 считывается первый элемент начального под- 40 уровня массива R, записываемый на выходной регистр 4. Затем код R> на выходном регистре сравнивается при помощи схемы 8 с кодом на регистре 2. Если эти коды не сравнились, к коду адреса на регистре б прибавляет- 45 ся единица и считывается следующий элемент начального подуровня массива. Указанные действия продолжаются до элемента, у которого в R4 стоит признак, либо до элемента, у которого код R на регистре 4 совпал с кодом на регистре 2. В первом случае вырабатывается сигнал синтаксической ошибки (СОШ), так как ни один из элементов в R1 начального подуровня массива не сравнился с первым синтермом проверяемой программы. Напомним, что в Я начального подуровня массива записаны коды синтермов, которые могут быть первыми в программе данного алгоритмического языка. Если первый синтерм проверяемой программы, полученный 60 при помощи таблицы wr из первого символа программы, не сравнился ни с одним из синтермов в Я1 данного подуровня, это значит, что он ошибочно написан первым, т. е. написан синтаксически неверно. Во втором случае, когда код Л на регистре 4 совпал с кодом на регистре 2, на регистр б переписывается код R< с выходного регистра. Тем самым на регистр б записывается адрес начального элемента подуровня R массива, у которого в R записаны коды синтермов, которые в проверяемой программе могут идти следом за синтермом на регистре 2.

После этого на регистр 1 вызывается следующий символ проверяемой программы, по которому из ДЗУ на регистр 2 считывается код соответствующего синтерма, затем на выходной регистр 4 по адресу на регистре б считываются элементы R массива R, коды которых сравниваются с кодом на регистре 2 и т. д. аналогично описанному.

Перечисленные действия соответствуют элементам массива ДЗУ, у которых отсутствуют признаки R2 и Rg.

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

Если элемент на регистре 4, у которого R< совпал с кодом на регистре 2, имеет в R3 признак, то записи кода R< на регистр 6 предшествует сравнение кода на вершине стековой памяти с кодом R-, на выходном регистре 4.

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

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

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

1. Устройство для синтаксического контроля программ по авт. св. Мю 236861, отличающееся тем, что, с целью упрощения, уменьшения габаритов и увеличения быстродействия, оно содержит вспомогательный регистр, входы которого. соединены с выходами выходного. регистра, а выходы — со входами схемы сравнения.

2. Устройство по и. 1, отличающееся тем, что выходы входного регистра соединены со входами долговременной памяти.

247628

Составитель В. М. Шумский

Редактор Б, Б. Федотов Техред Т. П. Курилко Корректор А. С. Колабин

Заказ 339/3 Тираж 480 Подписное

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

Москва Ж-35, Раушская наб., д, 4/5

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