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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советскнк

Социалмстичесин к

Республик

«»637818 (61) Дополнительное к авт. свид-ву (22) Заявлено 2104.76 (21) 2351066/18-24 с присоединением заявки ¹(23) Приоритет(43) Опубликовано 15.12.78. Бюллетень ¹ 46 (4..з) Дата опубликования описания 15.1278 (51) М. Кл.

С06 F 11/00

Государственный комитет

Coaeta Министров СССР по делам изобретений и открытий (53) УДК 681. 326 (088.8) (72) Авторы изобретения

И.В. Вельбицкий, В. И. Комаровский, Ю.И.Мельник и Н.В.Тимошенко (71) Заявитель

Ордена Ленина институт кибернетики AH Украинской CCP (54) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО КОНТРОЛЯ

ПРОГРАММ И ДЛ,:НЫХ

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

Оно может быть использовано при схемной реализации математического обеспечения, на вычислительных центрах (ВЦ), системах автоматизированного управления, на удаленных терминалах ВЦ коллективного пользования и сетей электронных вычислительных машин (3BM), а также в системах обучения.

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

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

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

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

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

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

637818 оперативный запоминающий блок, подключенные управляющими входами к соответствующим выходам блока управления и соединенные между собой и с блокоМ долгонременной памяти общей магистралью, адресный и информационный входы оперативного запоминающего блока соединены соответственно с выходами регистра адреса и регистра данных, адресный вход блока долговременной памяти соединен с выходами регистра адреса микрокоманд и регистра адреса грам- !О матик, управляющий вход - с соответствующим выходом блока УПравления, выход регистра микрокоманд соединен со входом блока управления, вход и выход устройства подключены соот-IS ветственно к входу и выходу блока связи, Это дает воэможность устранить жестко зафиксированные связи между различными блоками и узлами, обеспечить легкую смену язы- gg кон, работу с различными внешними устройствами и повысить быстродействие.

На фиг. 1 представлена схема устройства; на фиг. 2 - символическая запись типов правил, а также машинная Форма представления этих же правил, реализованная н устройстве; на фиг. 3 — распределение долговременной памяти; на фиг. 4 — распределе- 30 ние оперативной памяти.

Устройство содержит регистр 1 ацреса микрокоманд, регистр 2 адреса грамматик, блок 3 долговременной памяти, регистр 4 микрокоманд, регистр

5 грамматик, регистр б адреса, оперативный запоминающий блок 7, регистр

8 данных, буферный регистр 9, блок 10 управления, блок 11 связи, вход 12 и выход )3 устройства. 40

Для задания грамматик различных языков разработан функционально полный набор типов правил (9 типов).

В этих правилах терм (символ, однозначно соот- 45 ветствующий символу входного языка). синтерм (симнол, синтаксически эквивалентный целой группе символов входного языка), ф — пустой символ; имя (адрес) правила-приемника;

W — параметр, раскрывающий отношение данного правила к работе с магазинной памятью; отношение показывает, что никакой работы с магазинной памятью в данном правиле нет; отношение показывает, что при работе с данным правилом производится запись н магазинную память; 14 — отношение показывает, что при 60 работе с данным правилом есть считывание из магазинной памяти.

Грамматики языков в устройстве представляют собой набор определенных комбинаций выше приведенных типов 65 правил и расположенных н ниде так называемых Р-массинон н долговременной . памяти. Каждому языку соотнетстнует свой массив грамматик: 1 -массив грамматик АСПП-38 (т.е. грамматика языка автоматизированной системы производства программ), р -массив грамматик ДИРЕКТИВ АСПП-38, Рз -массив грамматик АЛГОЛа-60. Таблица соответствия термов синтермам представляет собой одномерный массив, проходящий вертикально через массив грамматик, и обозначена на Фиг. 3 T . В массиве микропрограмм (МИ) расположены микропрограммы, определяющие работу устройства при выполнении правил каждого типа, коммутационная микропрограмма, осуществляющая связь отдельных правил в массиве грамматики в одно целое, и служебная микропрограмма, осуществляющая подготовку устройства к работе с тем или иным языком.

На базе оперативного запоминающего блока 7 организована магазинная память. Кроме того, первые пять ячеек используются н качестве вспомогательных регистров (ВР) и распределены следующим образом: в первой ячейке хранится текущий символ ТС, во второй - начальный адрес грамматики

Сн, в третьей - текущий адрес грамматики С, и четвертой — начальный адрес магазинной памяти М„, в пятойтекущий адрес магазинной памяти М далее располагается магазинная память /МП/.

Работа устройства состоит н следующем. В исходном состоянии магазинная память свободна. В ячейках Си и Ст находится адрес начального правила Со грамматики нужного языка. В ячейках Мн н М находится адрес начала магазинной памяти. Заполнение этих ячеек производит служебная микропрограмма по нажатию оператором клавиши с названием соответствующего языка. Эта же микропрограмма производит корректировку и остальных узлов устройства.

Первый символ проверяемой программы принимается на регистр 8 и на время контроля запоминается в ячейке текущего символа блока 7. Поступление сигнала в устройство является сигналом запуска микропрограммного автомата, .который, извлекая адрес, записанный в ячейке Ст (н исходном состоянии там записай адрес первого правила грамматики — С ), обращается по этому адресу к массиву грамматик. В результате этой операции на регистре 5 грамматик оказывается перная ячейка, т.е.

Ж (см.фиг.2) первого пранила массива грамматики. В описываемом устройстве

%-отношение интерпретируется как адрес начала микропрограммы, отрабатывающей данный тип правила.

Если в данный тип правила входит терм или синтерм, то делается сравнение этого терма или синтерма с входным

637818 символом. В случае сравнения символ считается синтаксически верным и че- . рез блок 11 связи выдается на внешнее устройство. Микропрограммный автомат считывает адрес начала следующего комплекса, заносит его в ячейки Сн и

С блока 7, корректирует схемы устройства и останавливается в ожидании при- хода следующего символа.

При несравнении входного символа с .термом или синтермом правила микропрограммный автомат берет следующее правило данного комплекса и далее ра- 10 бота идет, как указано выше.

Каждый комплекс в массиве грамматик оканчивается правилом 9 — г о

Поэтому, если входной символ не сравнится ни с одним правилом комплекса, то микропрограммный автомат попадает на это правило. С этого момента начинается работа устройства в режиме синтаксической ошибки, т.е. режиме СОШ.

Микропрограммный автомат переводит счетчик СОШ блока 10 управления иэ состояния 00 в состояние 01 .

Текущий адрес грамматики возвращается в начало комплекса, т.е. С присваивается значение С„. Оператору выдается звуковой сигнал, а также зажигается табло (на фиг. 1 не показано) ПОВТОРИТЬ ВВОД. Если оператор в состоянии самостоятельно исправить ошибку, то вновь введенный символ сравнится с одним из правил комплекса и будет вы3(1 дан в канал, счетчик СОШ будет сброшен в состояние 00, а табло ПОВТОРИТЬ ВВОД погаснет. Если же вновь введенный символ снова окажетсясинтаксически неверным (т.е. оператор не 35 знает, как исправить ошибку), то он не сравнится ни с одним правилом комплекса и микропрограммный автомат снова попадет на правило Ю вЂ” ч г . В результате вторичного прохода по комп- 40 лексу и попадания на правило ф - г

% гаснет табло ПОВТОРИТЬ ВВОД и зажигается табло ОШИБКА, счетчику COL". присваивается значение 10 . Текущий адрес грамматики снова возвращается в начало комплекса. Микропрограммный автомат сравнивает входной символ с корректи- 48 ровочными правилами (флажковыми) данного комплекса. В случае сравнения, контроль по грамматике считается восстановленным, если сравнения не произошло, микропрограммный автомат снова 50 попадает на правило Ф вЂ” гсс . Счет о чику СОШ присваивается значение 11 и микропрограммный аппарат начинает сравнивать входной символ с правилами комплексов, адреса которых записаны в магазинной памяти. Если сравнение произошло, контроль по грамматике считается восстановленным. Данный символ выдается на печать и в канал. Если же сравнение не произошло, микропрограммный автомат возвращает текущий адрес грамматики в начало того комплекса, где произошел сбой, восстанавливает магазинную память, счетчик СОШ переводится в состояние 10 . Символ выдается только на печать красным цветом, а в канал не поступает. Вновь поступивший символ обрабатывается устройством в режиме

COU так, как было описано выше. В случае ошибки, восстановление контроля по грамматике (для существующих язы" ков программирования) обычно происходит через 2-3 символа.

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

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

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

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

1в н,1г11

2- t.

2-2. а — Йа г+

t Ж Г г

9/у

2-7

8Р

Фиг.5

128

Составитель A.геренов

ТехРед ИаБорисова Кор екто .Мельниченко лай

Тираж 784 Подписное

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

113035 11оаква Н-35 Ракшакан наб. Д.4 5

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

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

1. Авторское свидетельство СССР

9 328640, кл. $06 Г 11f00, 1970, 2. Авторское свидетельство СССР

9 333S58, кл. 606 F 11/00, 1970,