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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советскнк Сфцюааистичесинк Республик. Кл.СОб Государственный комитетСовета Министров СССРпо делам изобретениИи открытий Приорит3) Опубликовано 15,12.78. Бюллетень К 5) Дата опубликования описания 15,1 8(72) Авторы ельбицкий, В.И.КомаровскМельник и Н,В,Тимошенко Ю Заявител дена Ленина институт кибернетики АН Украинской ССР 4) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО КОНТРОЛЯ ПРОГРАММ И ДМНЫХ о р г иния. 20 ср па ги Изобретение относится к области вычислительной техники и, в частности к аппаратным средствам, осуществляющим схемный контроль последовательности символов, порядок записи которых задается совокупностью правил, называемых грамматикой языка.Оно может быть использовано при схемной реализации математического беспечения, на вычислительных центах (ВЦ), системах автоматизированноо управления, на удаленных терминалах ВЦ коллективного пользования и сетей электронных вычислительных маш (ЭВМ), а также в системах обучеИзвестно устройство для синтаксического контроля программ, содержащее входной регистр проверяемой програмвспомогательный регистр, схемуавнения, долговременную и стековую мяти, регистр адреса и выходной рестр долговременной памяти (1 .В связи с несовершенством алгоритм устройство имеет низкую скорость распознавания входного текста (программ) а следовательно, и малое быстродействие, сложность схематических решений, большие габариты. Из известных устройств наиболее близким по технической сущности к изобретению является устройство,содержащее блок долговременной памяти. Кроме того, в его состав входят входной регистр, схема сравнения, выходной регистр, регистр адреса, стековая память, регистр типа синтерма и логическая схема выбора синтерма соответствующего типа 21. Данное устройство имеет более высокую скорость распознавания входного текста.Однако у этого устройства сложная структурная схема, жестко зафиксирован ная связь между различными блоками и функциональными узлами, большие габариты, а также и то, что устройство рассчитано на работу с одним языком и одним определенным внешним устройствомЦелью изобретения является повышение быстродействия и расширение функциональных возможностей устройства путем обеспечения проверки программ, записанных на различных языках и вводимых с различных внешних устройств.Цель достигается тем, что предлагаемое устройство содержит регистры микрокоманд, адреса микрокоманд, грамматик, адреса грамматик, данных, адреса, буферный регистр, блок связи иоперативный запоминающий блок, подключенные управляющими входами к соответствующим выходам блока управления исоединенные между собой и с блокоМдолгонременной памяти общей магистралью, адресный и информационный входыоперативного запоминающего блока соединены соответственно с выходами регистра адреса и регистра данных, адресный вход блока долговременной памятисоединен с выходами регистра адресамикрокоманд и регистра адреса грам- Оматик, управляющий вход - с соответствующим выходом блока УПравления,выход регистра микрокоманд соединенсо входом блока управления, входи выход устройства подключены соот ветственно к входу и выходу бло"ка связи, Это дает воэможностьустранить жестко зафиксированныесвязи между различными блоками иузлами, обеспечить легкую смену язы- р)кон, работу с различными внешнимиустройствами и повысить быстродействие,На Фиг. 1 представлена схема уст" ройстна; на фиг. 2 - символическая М запись типов правил, а также машинная Форма представления этих же правил, реализованная н устройстве; на фиг. 3 - распределение долговременной памяти; на фиг, 4 - распределе ие оперативной памяти.Устройство содержит регистр 1 ацреса микрокоманд, регистр 2 адреса грамматик, блок 3 долговременной памяти, регистр 4 микрокоманд, регистр 5 грамматик, регистр б адреса, оперативный запоминающий блок 7, регистр 8 данных, буферный регистр 9, блок 10 управления, блок 11 связи, вход 12 и выход 13 устройства, 40Для задания грамматик различных языков разработан функционально полный набор типов правил (9 типов). В этих правилахтерм (символ, однозначно соот ветствующий символу входного языка)д - синтерм (симнол, синтаксически эквивалентный целой группе символов входного языка)1ф - пустой символ;Г - имя (адрес) правила-приемника; 50% - параметр, раскрывающий отношение данного правила к работе с магазинной памятью;Во- отношение показывает, что никакой работы с магазинной памятью в данном правиле нет;%- отношение показывает, что при работе с данным правилом производится запись н магазинную память;Ф - отношение показывает, что при 60 работе с данным правилом есть считывание из магазинной памяти,Грамматики языков в устройствепредставляют собой набор определенных комбинаций выше приведенных типов Я правил и расположенных н ниде так называемых Р-массинон н долговременнойпамяти. Каждому языку соотнетстнуетсвой массив грамматик: Р -массивграмматик АСПП(т.е. грамматикаязыка автоматизированной системы производства программ), рг -массив грамматик ДИРЕКТИВ АСПП, Рз -массивграмматик АЛГОЛа-бО, Таблица соответствия термов синтермам представляетсобой одномерный массив, проходящийвертикально через массив грамматик, иобозначена на Фиг, 3 Т . В массивемикропрограмм (ММ) расположены микропрограммы, определяющие работу устройства при выполнении правил каждого типа, коммутационная микропрограмма, осуществляющая связь отдельных правил в массиве грамматики в одно целое, и служебная микропрограмма,осуществляющая подготовку устройствак работе с тем или иным языком,На базе оперативного запоминающегоблока 7 организована магазинная память. Кроме того, первые пять ячеекиспользуются н качестве вспомогательных регистров (ВР) и распределеныследующим образом: в первой ячейкехранится текущий символ ТС, вовторой - начальный адрес грамматикиСн , в третьей - текущий адрес грамматики Ст, и четвертой - начальныйадрес магазинной памяти М, в пятойтекущий адрес магазинной памяти Мдалее располагается магазинная память /МП/,Работа устройства состоит н следующем. В исходном состоянии магазиннаяпамять свободна. В ячейках Си и Стнаходится адрес начального правила Сграмматики нужного языка, В ячейках Мнн Мт находится адрес начала магазиннойпамяти. Заполнение этих ячеек производит служебная микропрограмма понажатию оператором клавиши с названием соответствующего языка. Эта жемикропрограмма производит корректировку и остальных узлов устройства.Первый символ проверяемой программы принимается на регистр 8 и на времяконтроля запоминается в ячейке текущего символа блока 7, Поступлениесигнала в устройство является сигналомзапуска микропрограммного автомата,который, извлекая адрес, записанныйв ячейке Ст (н исходном состояниитам записай адрес первого правилаграмматики - С ), обращается по этомуадресу к массиву грамматик. В результате этой операции на регистре 5 грамматик оказывается перная ячейка, т.е.Ж (см.фиг.2) первого пранила массиваграмматики. В описываемом устройстве%-отношение интерпретируется как адрес начала микропрограммы, отрабатывающей данный тип правила,Если в данный тип правила входиттерм или синтерм, то делается сравнение этого терма или синтерма с входнымсимволом. В случае сравнения символсчитается синтаксически верным и через блок 11 связи выдается на внешнееустройство. Микропрограммный автоматсчитывает адрес начала следующегокомплекса, заносит его в ячейки Сн иСт блока 7, корректирует схемы устройства и останавливается в ожидании прихода следующего символа,При несравнении входного символа стермом или синтермом правила микропрограммный автомат берет следующееправило данного комплекса и далее ра Обота идет, как указано выше,Каждый комплекс в массиве грамматик оканчивается правилом 6 в ф,ЮоПоэтому, если входной символ не сравнится ни с одним правилом комплекса, )5то микропрограммный автомат попадаетна это правило, С этого момента начинается работа устройства в режиме синтаксической ошибки, т.е, режиме СОШ,Микропрограммный автомат переводитсчетчик СОШ блока 10 управления изсостояния 00 в состояние 101.Текущий адрес грамматики возвращаетсяв начало комплекса, т.е, С присваивается значение С. Оператору выдаетсязвуковой сигнал, а также зажигаетсятабло (на фиг. 1 не показано) ПОВТОРИТЬ ВВОД, Если оператор в состояниисамостоятельно исправить ошибку, товновь введенный символ сравнится содним из правил комплекса и будет вы 31дан в канал, счетчик СОШ будет сброшен в состояние 001, а табло ПОВТОРИТЬ ВВОД погаснет, Если же вновьвведенный символ снова окажетсясинтаксически неверным (т.е. оператор не 35знает, как исправить ошибку), то онне сравнится ни с одним правилом комплекса и микропрограммный автомат сновапопадет на правило Ю - ч 4 гсо . В результате вторичного прохода по комплексу и попадания на правило Ф -2 чьг%гаснет табло ПОВТОРИТЬ ВВОД и зажигается табло ОШИБКА, счетчику СОР. присваивается значение 10 ф. Текущий адресграмматики снова возвращается в началокомплекса. Микропрограммный автоматсравнивает входной символ с корректировочными правилами (флажковыми) данного комплекса. В случае сравнения,контроль по грамматике считается восстановленным, если сравнения не произошло, микропрограммный автомат снова 50попадает на правило Ф - э- гс . Счет%очику СОШ присваивается значение 11и микропрограммный аппарат начинаетсравнивать входной символ с правиламикомплексов, адреса которых записаныв магазинной памяти. Если сравнениепроизошло, контроль по грамматикесчитается восстановленным. Данныйсимвол выдается на печать и в канал. Если же сравнение не прои"зошло, микропрограммный автомат возвращает текущий адрес грамматики в началотого комплекса, где произошел сбой, , 65 восстанавливает магазинную память,счетчик СОШ переводится в состояние10. Символ выдается только напечать красным цветом, а в канал непоступает, Вновь поступивший символобрабатывается устройством в режимеСОШ так, как было описано выше. В случае ошибки, восстановление контроляпо грамматике (для существующих язы"ков программирования) обычно происходит через 2-3 символа,Смена граматики языка, с помощью которой осуществляется контроль входной информации, производят нажатием соответствующей клавиши на пульте блока 10 управления, или же, если в блоке 3 долговременной памяти необходимой грамматики нет, заменой последнего другим, Так как этот блок выполнен в виде сменного блока и предусмотрена воэможность легкого доступа к нему, то операция проста и бистро выполнима.Применение устройства позволяет ускорить процесс получения синтаксически правильных программ пользователем, освободить вычислительную машину от необходимости транслировать и проверять синтаксически правильные программы, разгрузить каналы связи с терминалами от перекачки неправильной информации, потому что процесс контроля и исправление делаются непосредственно на месте генерации и ввода информации. Облегчается режим работы, устройств перфорации за счет освобождения их от переработки исправленной информации и, вследствие этого, сокращается расход перфоматериалов.Формула изобретенияУстройство для синтактического контроля программ и данных, содержащее блок долговременной памяти, о т л и ч а ющ е е с я тем,что,с целью повышения быстродействия и расширения функциональных возможностей путем обеспечения проверки программ,записанных на различных языках и вводимых с различных внешних устройств,оно содержит регистры микрокоманд,адреса микрокоманд,грамматик,адреса грамматик, данных, адреса,буферный регистр, блок связи и оперативный запоминающий блок, подключенные управляющими входами к соответствующим выходам блока управления и соединенные между собой и с блоком долговременной памяти обшей магистралью, адресный и информационный входы оперативного запоминающего блока соединены соответственно с выходами регистра адреса и регистра данных, адресный вход блока долговременной памяти соединен с выходами регистра адреса микрокоманд и регистра адреса грамматик, управляю37818 8Источники информации, принятые вовнимание при экспертизе:1. Авторское свидетельство СССР9 328640, кл, Ц 06 Г 11/00, 1970,2. Авторское свидетельство СССРМ 333558, кл, 606 Г 11/00, 1970,2.Я. дВ Фис. гФиаФ тавитель А.Жеренов ред МаБорисова кор екто вМельничен л Тираж 784 Государственного комитет по делам изобретений и о 113035 11 оаава В.-35 Ра ф ПППР дписноеминистров ССС ЦНИИПИ ове ыти ш каяаб. д. 4 / Патент лиа щий вход - с соответствующим выходомблока управления, выход регистра микрокоманд соединен со входом блока управления, вход и выход устройстваподключены соответственно к входу ивыходу блока связи,.Ужгород, ул.Проектная, 4