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

О П И С-А-Н И Е ИЗОБР ЕТЕ НИЯ 247628 Саюэ Соеетвкиэ Социалистическиэ РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ т. свидетельства23 б симо 11/02 Заявлено 19.11.1968 ( 1220026/18-24)с присоединением заявкиК б оритет Комитет по делам эобретений и открытий при Совете Министров СССР, В. Вельбицкий некой ССР ститут кибернетики А аявител ЕСКОГО КОНТРО ТРОЙСТВО ДЛЯ СИНТАКС ПРОГРАМдолговременн и стековой п за тика языка запи го Л-массива, Ве некоторые подур располагается нес ементов массива,Предлагаемое устройство предназначается для проверки последовательностей символов, построенных по определенной совокупности правил, называемых грамматикой языка.Известно устройство для синтаксического контроля программ, записанных на алгоритмическом языке, состоящее из входного ре гистра, схемы сравнения, выходного регистра, долговременной памяти, регистра адреса и стековой памяти (авт. св.23 б 8 б 1).Известное устройство имеет следующие не достатки:а) массив грамматики языка нимаег много бит долговременной памяти;б) на синтаксический контроль одного символа проверяемой программы затрачивается много времени, так как в одном подуровне массива содержится много элементов.В предлагаемое устройство, с целью его упрощения, уменьшения габаритов и повышения быстродействия, введен вспомогательный регистр, входы которого соединены с выходами выходного регистра, а выходы - со входами схемы сравнения. Выходы входного регистра соединены со входами долговременной памяти,На чертеже изображена блок-схема устройства.Устройстввспомогател о состоит из входного регистра 1. ьного регистра 2, схемы сравнения 3, выходного рег 4, ои памяти 5, регистра др бамяти 7.В качестве основного символа для описания 5 грамматики языка используют так называемый синтерм (синтаксический терм). Одному синтерму могут соответствовать несколько основных символов (термов) языка, каждый из которых имеет тот же синтаксис использо вания в языке. Это значит, что для любогопредложения языка замена одного символа другим, соответствующим одному и тому же синтерму языка, не выводит это предложение из языка, т. е, не превращает его в непред ложение данного языка. Соответствие междутермами и синтермами задается специальной таблицей ы, каждой строке которой соответствует терм языка (номер строки совпадает с кодом соответствующего терма). В каждой 20 строке записан соответствующий этой строкесинтерм языка. В долговременной памяти устройства синтаксического контроля таблица ю, очевидно, занимает и 1 одэК разрядов, где и - число термов, К - число синтермов в язы 25 ке.Грамма сывается в ДЗУ ввиде одно сь массив условно разбит на овни, в каждом из которых колько (некоторое ЗО число) эл Каждый элементмассива занимает одно слово ДЗУ и состоитиз семи частей:Я, - код синтерма языка (занимает 1 од,Кразрядов);Рз - эквивалентно Рз; 5Рз - эквивалентно РзР 4 в эквивалент Й 4,Ьз эквивалентно РзЙз в эквивалент Рз (занимает в общемслучае 1 од,У разрядов, где Ж - Я 7 длина всего массива Р);Я, эквивалентно Р 7 (в общем случае Р,также занимает 1 одЖ разрядов элементамассива Р).В общем случае элемент указанного массива Я занимает (1 од К+ 4+21 озМ) разрядов,Таким образом, в долтовременной памятиисходные данные задаются в виде двух массивов - з и Я и занимают в общем случае 20п 1 одзК+М (1 орК+4+21 оязЧ) разрядов.Работа устройства заключается в следующем,В исходном состоянии стековая память свободна, регистр адреса отмечает адрес начального подуровня массива Й, у которого в Р записаны коды синтермов, которые могут быть З 0первыми в программе данного алгоритмического языка.Первый символ проверяемой программы записывается на входной регистр 1. Затем изв-таблицы ДЗУ по адресу на регистресчитывается соответствующий этому символусинтерм, записываемый после считывания навспомогательный регистр 2. После этогоиз Р-массива ДЗУ по адресу на регистре 6считывается первый элемент начального подуровня массива Я, записываемый на выходной регистр 4. Затем код Р на выходном регистре сравнивается при помощи схемы 3 скодом на регистре 2. Если эти коды не сравнились, к коду адреса на регистре 6 прибавляется единица и считывается следующий элементначального подуровня массива. Указанныедействия продолжаются до элемента, у которого в Л 4 стоит признак, либо до элемента, укоторого код Р на регистре 4 совпал с кодом 50на регистре 2. В первом случае вырабатывается сигнал синтаксической ошибки (СОШ), таккак ни один из элементов в Я, начальногоподуровня массива не сравнился с первымсинтермом проверяемой программы, Напомним, что в Я, начального подуровнямассива записаны коды синтермов, которые могут быть первыми в программеданного алгоритмического языка. Если первыйсинтерм проверяемой программы, полученный 60при помощи таблицы ы из первого символапрограммы, не сравнился ни с одним из синтермов в Я, данного подуровня, это значит,что он ошибочно написан первым, т. е, написан синтаксически неверно. Во втором случае, когда код Л, на регистре 4 совпал с кодом на регистре 2, на регистр 6 переписывается код Р, с выходного регистра. Тем самым на регистр 6 записывается адрес начального элемента подуровня Я массива, у которого в Р записаны коды синтермов, которые в проверяемой программе могут идти следом за синтермом на регистре 2.После этого на регистр 1 вызывается следующий символ проверяемой программы, по которому из ДЗУ на регистр 2 считывается код соответствующего синтерма, затем на выходной регистр 4 по адресу на регистре 6 считываются элементы Я массива Я коды которых сравниваются с кодом на регистре 2 и т. д. аналогично описанному.Перечисленные действия соответствуют элементам массива ДЗУ, у которых отсутствуют признаки Р и ЯзЕсли элемент на регистре 4, у которого Р совпал с кодом на регистре 2, имеет в И признак записи в стековую память, записи кода Я, на регистр 6 предшествует запись текущего значения кода на регистре 6 в стековую память, В остальном действия не отличаются от вышеописанных.Если элемент на регистре 4, у которого Я совпал с кодом на регистре 2, имеет в Йз признак, то записи кода Р, на регистр 6 предшествует сравнение кода на вершине стековой памяти с кодом Й 7 на выходном регистре 4. Если эти коды совпали, содержимое верхней ячейки стека удаляется и производятся описанные выше действия по переписи кода Рб на регистр 6 и т. д. Если эти коды не совпали, к содержимому регистра 6 прибавляется единица, и описанные выше действия производятся с новым, следующим элементом данного подуровня массива.В конце проверки последний синтерм проверяемой программы обязательно сравнится с таким элементом соответствующего подуровня массива, у которого в Яз стоит признак (соответствующий Р, триггер на выходном регистре 4 стоит в единице). В противном случае проверяемая программа считается недописанной, что соответствует также условию выработки сигнала синтаксической ошибки.Предмет изобретения1. Устройство для синтаксического контро. ля программ по авт. св, Мо 236861, отличающееся тем, что, с целью упрощения, уменьшения габаритов и увеличения быстродействия, оно содержит вспомогательный регистр, входы которого. соединены с выходами выходного регистра, а выходы - со входами схемы сравнения,2. Устройство по и. 1, отличающееся тем, что выходы входного регистра соединены со входами долговременной памяти.Заказ 3393 Тираж 480 Подписное ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва Ж, Раушская наб д, 4/5 Типография, пр, Сапунова, 2