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

(54) ГЕНГРАТОР ПЗИЕМОГО СИНТАКСИ(5/) Изобретениелительной техник РА 1 Й Д.15( У 11 РА 1- КОГО КОНТРО:Я носится к вычиг может быть исЕ пользовано в быстро ствующиастности опер ционных системах, в темах с диалоговым р ки, отпайки и выполи также в ЭВМ с языком Цель изобретения - р сисжимом рания прог высокого сширение работрамм, а .ровня. функОСУДАРСТВЕННЬЙ КОМИТЕТО ИЗОБРНЕНИЯМ И ОТКРЫТИЯМРИ ГННТ СССР циональных возможностеи эа счет обеспечения самонастраиваемости на различные планы грамматик при одновременном повышении достоверности контроля эа счет выявления ошибок во входной грамматике, а также повышениебыстродействия устройства. Для достижения укаэанной цели в устройство дополнительно введены входной регистр1, дешифратор 4 адреса, блок / контроля, коммутатор 8 и выходной регистр 9. Использование аппарата алгоритмических алгебр для представлений входной грамматики, оптимизацияалгоритма работы блока 3 управления,а также введение блока / контролявходной грамматики обеспечивают эФфективную генерацию программ контроля, делают устройство универсальным и самонастраиваемым. При этомисключение блока памяти грамматик пгволяет повысить быстродействие и упростить устройство. 3 ил., 6 табл.1672461 Продолжение табл.6 Распознаваемый видошибки Текущийсимвол И 23 И 24 ИЛИ 25 ИЛИ 21 И 30 ИЛИ 32 И 3 входного регистра Замена ( на Ч Замена ц на Ч Замена Р на Ч Замена (3 Замена Л нана Замена Р на "ф Замена Ч на ф П р и м е ч а н и е. Знакопределяет один из следукщих символов:скобку (открывающую и закрывакщую), знак конца уравнения (;) или ф) илн символ Ф - букву другого (не используемого грамматикой) алфавита. Выходные сигналы элементов блока контроля Ч О О 1 Ч О О О Ч О ООО О О О О0 0 О Лропуск ЧЗамена йЗамена РЗамена Ч на 3 на (3 на э161246/ дт Оеширрст рХ ХзХХхпХбХцХХ Ц оставитель Г.Поливодаехред Л.Сердюкова К ектор М.Демч ктор В.Даик Заказ 2841 ТиражВНИИПИ Гогу;арстнснцого комитет11303, Москва,КНТ СССР Производственно-издательский комбинат "Патент", г, Ужгород, ул, Гагарина, 101 ф о ф 8) Д 91 Подписное по изобретениям и открыти -35, Раушская наб д, 4/1672461 Р = н (чн Р,Ч 3 (рРЧ.ЧЬ И,Рк Ч Ь, +, (Ч,п Р+,Ч Х) Ю Рг = Ро ИьР,ЧР.И. Р; ЧЧЬ ИРЧ,(Ч,.1 Р;., ЧЯ); переменная (оператор регулярной схемы микропрограммы,определяемой заданным уравнением; оператор Р , включаемый в левую часть регулярной схемы, синтаксически определяют номер этой схемь)у 401, если переменной Р; сопоставляется некоторьд терми"нал входной грамматики,"О, в противном случае; где Р граммах Вирта, формах Бэкуса-Наураи др. 1, если переменной Р; сопоставляется макрокоманда вгенерируемой программе;О, в противном случае,Изобретение относится к вычислительной технике и может быть использовано в быстродействующих операционных системах обработки информации, в частности в системах с диалоговым режимом разработки, отладки и выполнения программ, а также в ЭВМ с языком высокого уровня.Цель изобретения - расширение функциональных воэможностей за счет обеспечения самонастраиваемости на различные классы грамматик при одновременном повьпнении достоверности контроля за счет выявления ошибок во входной грамматике, а также повьппение быстродействия.Генератор, получая на вход Грамматику, записанную в специальной форме, выдает в результате своей работы программу синтаксического контроля на выходном языке. Генерируемая программа зависит, в основном, от особенностей входной грамматики, определяющей структурные свойства языка пользователя (арифметических, логи 1 О 15 20 25 д=1,К501=1, К+1,Х - постоянная, определяющаяпустой оператор.Под терминалом входной грамматикипонимается некоторая конструкция,например знаки операций +, -, х, имя,цифра, буква, ключевые слова типа1 Г, СОТО: РКОСКАМ и т,д спользуемая для описания синтаксиса в диаческих, регулярных, автоматных и других выражений, подлежащих контролю). Учитывая, что не каждая грамматика обеспечивает полноту контроля входных напряжений, устройство за счет специальной формы представления грамматики позволяет включать в генерируемую программу макрокоманды, определяющие выход на подпрограммы семантического контроля. Последние могут храниться во внешнем блоке памяти и доопределяться пользователем в зависимости от требуемой полноты контроля. В этом плане генератор допускает построение программ контроля, структура которых может изменяться (управляться) не только синтаксисом, но и семантикой входных выражений.Теоретической базой генератора является представление входной грамматики в виде системы уравнений в алгоритмических алгебрах, записываемой в следующей дизъюнктивной скобочной Форме Приведенная форма представления входной грамматики является независимой от используемых языков и более компактной (сжатой) по сравнению с традиционно используемыми формами. Генерация на ее основе программ контроля может осуществляться в темпе последовательного чтения входной грамматики, что повьппает быстродействие и исключает необходимость хранения входной грамматики в памяти ге" нератора.На Фиг.1 представлена структурная схема устройства; на фиг,2 - структурная схема блока управления; на фиг.З - структурная схема блока контроля.Устройство (Фиг.1) содержит входной регистр 1, дешифратор 2 операторов, блок 3 управления, дешифратор 4 адреса, блок 5 памяти, счетчик 6 меток, блок / контроля, коммутатор 8 и выходной регистр 9,5 16/В состав блока 3 упранления (фиг.2)входят программируемая логическаяматрица И 10, программируемая логическая матрица ИЛИ 11, узел 12 памяти, элемент ИЛИ 13, генератор 14 тактовых импульсов, триггер 15, элемент16 задержки, элемент И 1/.,Блок контроля (фиг.3) содержит реверсивный счетчик 18, первый элементИЛИ 19, первый элемент И 20, второйэлемент ИЛИ 21, первый триггер 22,второй 23 и третий 24 элементы И,третий элемент ИЛИ 25, второй триггер26, четвертый элемент ИЛИ 2/, третийтриггер 28, пятый. элемент ИЛИ 29,четвертый 30 и пятый 31 элементы И,шес.ой элемент ИЛИ 32Входной регистр 1 предназначендля хранения текущего символа подаваемой на вход устройства дизъюнктивной формы представления входной грамматики и может быть выполнен, например, на микросхеме 155 ТН 2. Дешифратор 2 операторов предназначен дляанализа текущего символа, хранящегося во входном регистре,Блок 3 управления организуетвзаимодействие всех элементов устройства и может быть выполнен на много 246/ 10 15 20 кратно программируемых логическихФматрицах.Блок 5 памяти предназначен ляхранения базовых конструкций вхоцногоязыка (в частности языка ассемблера),непосредственно используемых в процессе формирования генерируемой программы в выходном регистре. Записьинформации из блока памяти в выходной регистр осуществляется по командам блока 3 управления. При этом адрес опрашиваемой ячейки памяти формируется дешифратором 4 адреса,Для схемной реализации блока 5памяти может быть использовано репрограммируемое постоянно запоминающее устройство с длительным срокомхранения при включенном и выключенномисточнике питания.Счетчик 6 меток предназначен дляформирования меток, используемых ввыходной программе. Блок / контроля предназначен для выявления ошибок путем проверки наличия и порядка следования символов в дизъюнктивной скобочной форме входной грамматики, поступающей на вход генератора. 30 35 40 45 50 55 Коммутатор 8 обеспечивдст поступление элементов генерируемой программы из входного регистра 1, блока 5 памяти и счетчика 6 меток в выходной регистр 9.Генератор работает следующим образом.При включении генератора запускается блок 3 управления, управляющий сигнал которого подается на входы сброса в нуль счетчика Ь меток и одновременно на блок / контроля, где устанавливаются в нулевое состояние реверсинный счетчик 18 и триггеры 22, 26 и 28. Этот же 1.прднляющгн( сигнал произнодит рдзблакиронку входного регистра 1 для ввода гекущего символа входной грамматики. Текущий симьол грамматики поступает но входной регистр 1, а затем на дешифратор 2 операторов. Дешифратор 2 производит анализ текущего символа и вырабатывает соответствующий этому символу выходной сигнал, который поступает на блок / контроля, где проверяется наличие и порядок следования анализируемого символа, и одновременно на блок 3 управления,Если текущий символ является оператором Р, то блок управления вырабатывает управляющие сигндгп 1, которыеразличаются н зависимости от выходного сигнала счетчика 6 меток., В томслучае, когда счетчик 6 меток сброшен в нулевое состояние, то упрдвляющий сигнал блока 3 управления переключает коммутатор 8 на запись текущегосимвола из входного регистра 1 в выходной регистр 9. В том случае, когдасостояние счетчика отлично от нулевого, то управляющий сигнал блока 3 управления блокирует поступление новходной регистр 1 очередного символаграьюатики, переключает коммутатор 8на запись соответствующей операторуР конструкции выходного языка из блока 5 памяти в выходной регистр 9, азатем переключает коммутатор 8 назапись оператора Р из входного регистра 1 в выходной регистр 9. Послеэтого управляющий сигнал с блока 3управления поступает на блок 7 контроля, где производится изменениесостояния триггера 22, и на ьходнойрегистр 1, для его разблокирования иввода в него очердиого символа грамматики,/167246Если текущий символ является цифрой, то блок 3 управления переключает коммутатор 8 на запись этой цифры из входного регистра 1 в выходной5регистр 9 и переходит к анализу следующего текущего символа.Если текущий символ является знаком =, сператором М, признакомилис 1, то блок 3 управления блокируетзапись во входной регистр 1 очередного символа грамматики, переключаеткоммутатор 8 на запись соответствующей текущему символу конструкции выходного языка чз блока 5 памяти в выходной регистр, а затем вырабатываетуправляющий сигнал, который поступаетна блск / контроля для изменения состояния триггерог, 22, 26, 28 и навходной рсгистр 1 для его разблокировцния и ввода очередного симгола,Если текущий символ явлнетсн знаком дизъюнкции, то по сигналу с дешифратсра 2 блок 3 управления блокирует запись во вуодной регистр 1, переключает коммутатор 8 на записьметки (символического адреса формируемой программы) из блока 5 памятив выходной рсл:сгр 9, переключаегкоми,татор 8 на запись содержимогосне, ы а Ь .1 етс., в выходной регистрц .рс я;,.-.ает коммутатор 8 на запись :) из блока 3 памяти н выходнойрегистр " изменяет состояние триггеров 72 и 3, а за -ем разбл:кирсвывает35входнс, регистрЕс .и нс входном регистре появляется открывающая скобка, то сигнал сдешифратора 2 пос упает на блок 3управления, который чо этому сигналублокирует запись во входной регистрпереключает коммутатор 8 на записьсостветсгвующей открывающей скобкеконструкции выходного языка из блока5 памяти в выходной регистр 9, увеличин-.ет на единицу значение счетчика 6 меток и переключает коммутатор8 на запись значения счетчика 6 метокв выходной регистр 9, а затем производит разблокирование входнсго регистра 1 Одновременно по сигналу сдешнфратора 2 блок / контроля производит и,"верку порядка следования инакопления количества поступающихскобок,15Если во входном регистре появляется закрывающая скобка, то по сигналус дешифратора 2 блок / контроля снова осуществляет проверку порядка следования и накопление количествапоступающих скобок. При этом блок 3управления никаких управляющих сигналов не вырабатывает.Когда во входном регистре 1 появляется знак конца уравнения (:), тоблок 3 управления блокирует записьочередного символа во входной регистри осуществляют сброс счетчика Ь меток в нулевое состояние. Одновременно с дешифратора 2 подаетсясигнал на блок / контроля, где осуществляется проверка наличия и порядка следования этого символа, атакже анализ накопившейся суммь 1 открывающих и закрывающих скобок,Затем с блока 3 управления подаетсясигнал на блок / контроля, где изменяется состояние триггеров 22,26и 28. После этого Осуществляетсяразблокирование регистра 1 и на негомогут поступать для анализа составлядцие следующего уравнения дизъюнктивной формы входной грамматики.Преобразование символов входнойграмматики в программу контроля происходит до тех пор, пока в регистре1 не окажется символ конца диэъюнктивной формы ф). При этом блок 3угравления переключает коммутатор 8на запись из блока 5 памяти в выходной регистр 9 той конструкции выходного языка, которая определяетвыход из программы контроля и вырабатывает сигнал "Останов", Генераторпрекращает работу,Блок 3 управления работает следующим образом. Запуск генератора осуществляется при наличии разрешающего потенциала на единичном выходе триггера 15 (положение "Пуск" ). При его наличии сигналы с генератора 14 тактовых импульсов поступают на узел 12 памяти и одновременно на элемент 16 задержки, а пройдя элемент 16 задержки и элемент И 1/, поступают на программируемую логическую матрицу И 1 О. Элемент 16 задержки предназначен для, начальной установки узла,12 памяти перед пуском устройства.Программируемые логические матрицы И 10 и ИЛИ 11 организованы известным способом, Выходы матрицы И 10 соединены с входами матрицы ИЛИ 11 таким образом, что поступающие от дешифратора 2 и счетчика 6 меток сигналы У, (1=112), пройдя матрицу И 101=Ф3 1,если с переменной Р 1первого уравнения связывается знак отрицания контролируемых выражений;О, в противном случае,где 1, если с переменной Рпервого уравнения связывается операнд контролируемых выражений;О, в противном случае,преобразуются в некоторую совокупность логических произведений, а затем, пройдя матрицу ИЛИ 11, преобразуются в логические суммы от этих логических произведений. Результат суммирования снимается с одноименных выходов в виде управляющих сигналов У; (1 = 1,23) блока 3 управления,Сигнал Останов устройства" вырабатывается элементом ИЛИ 13 при поступлении с дешифратора 2 на входы матрицы И 10 сигнала, определяющего конец дизъюнктивной скобочной формы входной грамматики.. Программируемые логические матрицы И 10, ИЛИ 1 и узел 12 памяти обеспечивают реализацию любой схемы перевода входного языка в выходной язык беэ переделки связей между блоками. При переходе с одного выходного языка на другой язык корректировке подлежат лишь используемые в блоке 5 памяти базовые конструкции выходного языка. При изменении входного языка никаких корректировок не требуется ввиду специальной (само- настраиваемой) формы представления входной грамматики.Работу генератора и его основных блоков можно дополнительно проиллюстрировать на следующем примере,Пусть необходимо сгенерировать программу на языке Ассемблер для синтаксического контроля логических выражений с одной унарной и с одной бинарной операциями: отрицанием и дизъюнкцией. Грамматика такого рода логических выражений представима в ,виде следующей системы уравнений в алгоритмических алгебрах10 15 1, если с переменной Р 1 второго уравнения связывается знак дизъюнкции контролируемых выражений; О, в противном случае,1, если с переменной РЭ второго уравнения связывается знак конца выражения; О, в противном случае.Если считать, что в ячейки блока 5 памяти занесены базовые конструкции языка Ассемблера (табл. 1), то пошаговое преобразование исходной системы уравнений в программу будет осуществляться в соответствии с табл. 2. 20 30 Содержательный смысл приведенныхв табл.2 управляющих сигналов блока3 управления следующий:У - останов устройства;25 У - сброс в нулевое состояниесчетчика 6 меток;У - увеличение на единицу значения счетчика 6 меток;У - сброс в нулевое состояниеЭреверсивного счетчика 18блока контроля;У(У ) - разблокирование (эаблокирование) входного регистра;У - переключение коммутатора 8на запись текущего символа 35из входного регистра 1 ьвыходной регистр 9;У - переключение коммутатора 8на запись содержимого счетчика 6 меток в выходнойрегистр 9;У (У ) - установка в нулевое (единичное) состояние триггера 22блока контроля;45 У (У 11 )- установка в нулевое (единичное состояние триггера28 блока контроля;У(У 1 )- установка в нулевое (единичпое) состояние триггера26 блока контроля;У 1 - переключение коммутатора 8на запись данных иэ блока5 памяти в выходной регистр;Если исходная запись входнойграмматики не содержит ошибок, то в любой момент времени на выходе элементо И .1 ЧЛУ согласно табл. 4 долж. нь:ггь :лько нули Наличие сигнала на выоде элемента .1 ЛИ 32 рассматри О ва .тс; ка;, .тиг., а во входной грамма.- тике, ., . Ро;-. нал,.чиясл.дсва.н.я символов в исходном пред- ".тавлгниграмматики осущест;ляется комбинационной схемой (элементы И,1 йП 1 и ннверторы) совместно с группой РБ-т иггеров. состояние которых изме" няется под непосредственным воздействнсм в 1 ходных сигналов блока 3, Изменение состояния триггеров 22, 26 28 4 О осуществляется непосредственно леред раэблк.ровкой входного регистра 1 в соответствия с табл. 5.Если гекущий символ являет я от;р.,ы;.коскобкой, то сн нас дг шифра-,ора 2 поступает на суммирующий вхоц реверсивного счетчика 18, а в случае, если это закрывающая скобка на виитающий. 2550В процессе генерации программ чепрерывнэ контролируется текущая сумма от. рывающих и закрывающих скобок.Нулевая сумма соответствует "балансу скобок". Последний должен соблюдаться по окончании каждого уравнения исход ного представления грамматики, т.е.при поступлении во входной регистр 1 знака (;) или знака Ф). Преобразование 1-го уравнения исходной системы к программе на языкеАссемблер завершается эа 23 шага.Преобразование 2-го уравнения идентич 5но первому. Сгенерированная устройством программа для всей исходной системы уравнений приводится в табл. 3.Блок / контроля работает следующим образом. Текуший символ исходногопредставления входной грамматики последовательно поступает на входнойрегистр 1 устройства а затем на дешифратор 2. Последний формирует выходной сигнал, соответствующий текущемусимволу грамматики,Если текущий символ является одной, из букв алфавита входной грамматики,то с ответствующий ему сигнал с дешифратора 2 подается на блок / контроля и, пройдя в нем элементь 1 И иИШ. (табл.4), подается на элементИЛИ 32. В случае нарушения баланса скобокили появления зчака (;) или знака Ф)внутри уравнения на выходе реверсивного счетчика 18 Формируется код,в разрядах которого содержится хотябы одна единица. В этом случае навыходе элемента ИЛИ 19 формируетсясигнал, который, пройдя элемент И 20,появляется на выходе блока контроляв виде сигнала ошибкиВ случае отсутствия знака (;) вконце некоторого неконечного уравнения или отсутствия знака (ф) в концепоследнего уравнения при соблюдениибаланса скобок, на выходе элементаИЛИ 21 формируется сигнал, который,пройдя элемент ИЛИ 32, появляетсяна выходе блока контроля в виде сигнала ошибки,Отсутствие знака (;) в конце анализируемого уравнения с одновременным нарушением баланса скобок (парная ошибка) должно обнаруживатьсяпри поступлении начального оператораР последующего уравнения, так как вэтом случае триггер 22 не перейдетв н 1 левое состояние (единичное состояние соответствовало конечномузнаку уравнения - закрывающей скобке),и выходной сигнал, после триггера22 г 1 ройдя элемент ИЛИ 25 и ИЛИ 32п,.явится на выходе блока контроля ввид. .игнала ошибки.Поскольку баланс скобок соблюдается не только для конечного знака (;),но и для начальных знаков (Р или =)анализируемого уравнения, то можетвырабатываться ложный сигнал ошибки.Для его предотвращения сигналы Х, Хи Х, формируемые дешифратором 2, подаются на вход блока ИЛИ 21,В табл,б приведены основные ситуа"ции распознавания ошибок во входнойграмматике, характеризующие полнотуконтроля,Формула изобретенияГенератор программ для управляемого синтаксического контроля, содержащее дешифратор операторов, блок управления, блок памяти, счетчик меток, причем выход дешифратора операторов соединен с первым входом блока управления, первый выход которого является выходом "Останов" устройства, второй выход блока управления соедине со счетным входом счетчика меток,16/ Таблица 1 Интерпретация конструкций выходного языка в генерируемойпрограмме Базовые конструкции выходного языка МеткаМеткаДвоеточие после меткиОператор перехода к подпрограммеОператор безусловного переходаОператор перехода по условиюОператор конца программыИмя подпрограммы семантическогоконтроля входного выраженияИмя подпрограммы определенияпринадлежности символа входномуязыкуПустой оператор РХР1 БК РС,ВВВСБЕ 11 Ц)1 РЧ ХОР Та блида 2 Шаг работыыустройства Содервимое вход Выходные сигналы Содервимоевыходногорегистра 9 явления ещнФра- Счетчиора 2 ха иет Блоха ного регистра 1 х,х,х,У 5 У 15 У 14 Т564 У 1У 65 1 В У 14 У5 1 б 14УбВ 1 о 1229 14 Уо х,ИОн Р управляющий выход которого соединенс .вторым входом блока управления,о т л и ч а ю щ и й с я тем, что,с целью расширения функциональныхвозможностей за счет обеспечения самонастраиваемостн на различные классыграмматик при одновременном повышениидостоверности контроля за счет выявления ошибок во входной грамматике,а также повышения быстродействия, вустройство введены входной регистр,дешифратор адреса, блок контроля,коммутатор и выходной регистр, причеминформационный вход входного регистра является информационным входомустройства, третий выход блока управления соединен с управляющим входомвходного регистра, выход которогоподключен к входу дешифратора и первому информационному входу коммутатора,2461 14выход дсшифратора операторов и четвертчй выход блока управления соединены с первым и вторым входами блокаконтроля соответственно, выход блока 511 ыконтроля является выходом Ошибкаустройства, пятый выход блока управления соединен с входом дешифратораадреса,а выход которого соединен с ад Рресным входом блока памяти, выходкоторого подключен к второму информационному входу коммутатора, третийинформационный вход которого соединен с информационным выходом счетчи" 15 ка меток, шестой выход блока управления соединен с управляющим входом коммутатора, выход которого соединен синформационным входом выходного регистра, выход которого является информационным выходом устройства.15 16/246/ Метки Операторы яэыка Ассемблер 1 БК РС, ВВСБ ИР 11 БК РС,ВК Р1 БК РС, ВВСБ ИР1 БК РС,РЮК1 БКВСБ1 БКВКТБКВСБ1 БКВКЮР. ЕМП 1 1 Р1 2Р РС, В,11 Р 3РС, ЧРРС, В.йРРс, ЕР Э П р и м е ч з н н е. Подпрограммы В -В устанавливают принадлежность4элементов логического выражения алфавиту исходной грамматики. Подпрограммы 01-Чвключены для воэможности проведения семантического контроля входных выражений. Укаэанные подпрограммы должны быть предварительно включены в библиотеку подпрограмм и введены в память ЭВМ. Та блица 4 Текущий символ входной Элементы И и ИЛИ, принимающие сигналы от дешифратора 2 Сигнал, формируемый дешифратором 2 грамматики 2729, 30 23, 25 24, 25,29,31 или М Х 1 ИЛИ Х н Х 9 Х,167246/ Таблица 5 Сигнал, Характер изменения состояформируе- ния триггеров Примечание мый дешифратором 2 8 о ъ с. С ики Х,тригге 8 не изсех три меняетс-О 1 1 Состояние триггера 26 не изменяется 1-е О Х 1 О 1 1 -1 остаяние вс иггеров не изменяетс 1 -фО-ф О Х Буква испольэграмматикой авита (+) могоаблица Текущий символ вкодного ре- гистра Распоэнаваемый видощнбки гналы элементо модны ока контроля 29 ИЛИ 3 Ч О О 1 О 9 О О О О Ф О О О 1 Замене Р на Заменана1 Замена Я наПропуск О О 1 О Замене / нэ РПерестановка о О 1 О 1 Замена у на Р Замена Р наО О 1 О О 1 О О 1 ропус ТекущийсимволвходнойграммаХ 93 И 24 ИЛИ 25 ИЛИ 22 И 30 О О О Состояни ров 26 и меняется Состояниегеров не Состояние триггеров 26 и 28 не иэменяется Состояние триггеров 22 и 28 не иэменяется Состояние триггеров 22 и 28 не именяется Состояние всех триггеров не иэ меняется