Генератор программ для управляемого синтаксического контроля Советский патент 1991 года по МПК G06F17/10 G06F9/455 

СЬ

VJ

ю

-N О XI

Изобретение относится к вычислительной технике и может быть использовано в быстродействующих операционных системах, в частности в системах с диалоговым режимом разработки, отпайки и выполнения программ, а также в ЭВМ с языком высокого уровня. Цель изобретения - расширение функциональных возможностей за счет обеспечения самонастраиваемости на различные планы грамматик при одновременном повышении достоверности контроля за счет выявления ошибок во входной грамматике, а также повышение быстродействия устройства. Для достижения указанной цели в устройство дополнительно введены входной регистр 1, дешифратор 4 адреса, блок 7 контроля, коммутатор 8 и выходной регистр 9. Использование аппарата алгоритмических алгебр для представления входной грамматики, оптимизация алгоритма работы блока 3 управления, а также введение блока 7 контроля входной грамматики обеспечивают эффективную генерацию программ контроля, делают устройство универсальным и самонастраиваемым. При этом исключение блока памяти грамматик позволяет повысить быстродействие и упростить устройство. 3 ил.

DcmanoS

Фиг

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

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

Генератор, получая на вход грамматику, записанную в специальной форме, выдает в результате своей работы программу синтаксического контроля на выходном языке. Генерируемая программа зависит, в основном, от особенностей входной грамматики, определяющей структурные свойства языка пользователя (арифметических, логи , Рн (Ч„ MB,4 q№P1zY...Vfl,i (q,KPKVfi,il{+, (qu+, P, V N))...);

2 p (,Vfc«(q,ЈPiV ..лфм q«PKvp 2K« (q.n-i ЛГ+г YN))...); к ,p,v|bKl(ittpiv«--vpKK(qKKpKV 5Kil(;i qM41 P.VN)...).

Р. - переменная (оператор регулярной схемы микропрограммы, ,, определяемой заданным уравнением; оператор , вклю(i;

чаемый в левую часть регулярной схемы, синтаксически определяют номер этой схемы); 1, если переменной PJ сопоставляется некоторый терминал входной грамматики;

0,в противном случае;

1,если переменной Р« сопоставляется макрокоманда в генерируемой программе;

О, в противном случае,

,К J-1.K+1,

N - постоянная, определяющая

пустой оператор„

Под терминалом входной грамматики понимается некоторая конструкция, например знаки операций +, -, х, имя, цифра, буква, ключевые слова типа if, GOTO; PROGRAM и т.д., используемая для описания синтаксиса в диа

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

но и семантикой входных выражений,,

Ii,

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

,,

40

45

50

.,

граммах Вирта, формах Бэкуса-Наура

И ДРо

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

На фиг„1 представлена структурная схема устройства; на фиг„2 - структурная схема блока управления; на фиг„3 - структурная схема блока контроля.

Устройство (фиг.1) содержит входной регистр 1, дешифратор 2 операторов, блок 3 управления, дешифратор 4 адреса, блок 5 памяти, счетчик 6 меток, блок / контроля, коммутатор 8 и выходной регистр 9„

51

В состав блока 3 управления (фиг„ входят программируемая логическая матрица И 10, программируемая логическая матрица ИЛИ 11, узел 12 памяти, элемент ИЛИ 13, генератор 14 тактовых импульсов, триггер 15, элемент 16 задержки, элемент И 1/

Блок контроля (фиГоЗ) содержит реверсивный счетчик 18, первый элемент ИЛИ 19, первый элемент И 20, второй элемент ИЛИ 21, первый триггер 22, второй 23 и третий 24 элементы И, третий элемент ИЛИ 25, второй тригге 26, четвертый элемент ИЛИ 2/, третий триггер 28, пятый элемент ИЛИ 29, четвертый 30 и пятый 31 элементы И, шесгой элемент ИЛИ 32

Входной регистр 1 предназначен для хранения текущего символа пода- ваемой на вход устройства дизъюнктивной формы представления входной грамматики и может быть выполнен, например, на микросхеме 155 ТН 2. Дешифратор 2 операторов предназначен для анализа текущего символа, хранящегося во входном регистре„

Блок 3 управления организует взаимодействие всех элементов устройства и может быть выполнен на многократно программируемых логических матрицахо

Блок 5 памяти предназначен -.ля хранения базовых конструкций входног языка (в частности языка Ассемблера) непосредственно используемых в процессе формирования генерируемой программы в выходном регистре Запись информации из блока памяти в выходной регистр осуществляется по командам блока 3 управления. При этом адрес опрашиваемой ячейки памяти формируется дешифратором 4 адреса.

Для схемной реализации блока 5 памяти может быть использовано ре- программируемое постоянно запоминающее устройство с длительным сроком хранения при включенном и выключенно источнике питания о

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

Блок / контроля предназначен для выявления ошибок путем проверки наличия и порядка следования символов з дизъюнктивной скобочной форме входной грамматики, поступающей на вход генератора

Коммутатор 8 обеспечивает поступление элементов генерируемой программы из входного регистра I, блока 5 памяти и счетчика 6 меток в выходной регистр 9

Генератор работает следующим образом

При включении генератора запускается блок 3 управления, управляющий сигнал которого подается на входы сброса в нуль счетчика b меток н одновременно на блок / контроля, где устанавливаются в нулевое состояние реверсивный счетчик 13 и триггеры 22 26 и 280 Этот же управляющий сигнал производит разблокировку входного регистра 1 для ввода текущего символа входной грамматики.

5

0

0

5

0

Текущий символ грамматики поступает во входной регистр 1, а затем на дешифратор 2 операторов„ Дешифратор 2 производит анализ текущего символа и вырабатывает соответствующий этому символу выходной сигнал, который поступает на блок / контроля, где проверяется наличие и порядок следования анализируемого символа, и одновременно на блок 3 управления.

Если текущий символ является оператором Р, то блок управления вырабатывает управляющие сигнал, которые различаются в зависимости от выходного сигнала счетчика 6 меток В том случае, когда счетчик 6 моток спрошен в нулевое состояние, то управляющий сигнал блока 3 управления переключает коммутатор 8 на запись текущего символа из входного регистра 1 в выходной регистр 9. В том случае, когда состояние счетчика отлично от нулевого, то управляющий сигнал блока 3 управления блокирует поступление во 5 входной регистр 1 очередного символа грамматики, переключает коммутатор 8 на запись соответствующей оператору Р конструкции выходного языка из блока 5 памяти в выходной регистр 9S a затем переключает коммутатор 8 на запись оператора Р из входного регистра 1 в выходной регистр 9„ После этого управляющий сигнал с блока 3 управления поступает на блок 7 контроля, где производится изменение состояния триггера 22, и на сходной регистр 1, для его разблокирования и ввода в него очередного символа грамматики

0

Если текущий символ является цифрой, то блок 3 управления переключает коммутатор 8 на запись этой цифры из входного регистра 1 в выходной регистр У и переходит к анализу сле- дуюырго текущего символа.

Если текущий символ является знаком , оператором N, признаком М или q, то блок 3 управления блокирует запись во входной регистр 1 очередного символа грамматики, переключает коммутатор 8 на запись соответствующей текущему символу конструкции выходного языка чз блока 5 памяти в выходной регистр, а затем вырабатывает управпяющии сигнал, которым поступает на блок / контропя для изменения состояния триггеров 22, 26, 28 и на входной регистр 1 дпя его разблокирования и вг.ода очередного симгола

Если текущий символ является знаком дипъ нкции, то по сигналу с дешифратора 2 блок 3 управления блокирует запрет- во входной регистр 1, переключает коммутатор 8 на запись метки (символического адреса формируемой про;гчммы) из блока 5 памяти в выходной регистр 9, переключает коммутатор 8 на запись содержимого сче.ча а Ь метих и выходной регистр 9, г-рс- л:.-.ает коммутатор 8 запись (; / из Олоча 3 памяти в выходной регистр , изменяет состояние триггеров 22 и 23, а рачбл жировывает

ВХОДНР-, р ТИСТр 1 с

Ecj.H но входном регистре появляется открывающая ст.обка, то сигнал с дешифратора 2 поступает на блок 3 управления, которьо-i по этому сигналу Олокирует запись FO входной регистр 1, переключает коммутатор 8 на запись соответствующей открывающей скобке конструкции выходного языка из блока 5 памяти в выходной регистр 9, увеличивает на единицу значение счетчика 6 меток и переключает коммутатор 8 на запись значения счетчика 6 меток в выходной регистр 9, а затем производит разблокирование входного регистра 1, Одновременно по сигналу с дешифратора 2 Олок / контроля производит г; оверку порядка следования и накопления количества поступающих скобок.

Если во входном регистре псяьляет- ся закрывающая скобка, то по сигналу с дешифратора 2 блок / контроля снова осуществляет проверку порядка

5

5

0

5

следования и накопление количества поступающих скобок. При этом блок 3 управления никаких управляющих сигналов не вырабатывает о

Когда во входном регистре 1 появляется знак конца уравнения (:), то блок 3 управления блокирует запись очередного символа во входной ре- i-истр 1 и осуществляют сброс счетчика 6 меток в нулевое состояние. Одновременно с дешифратора 2 подается сигнал на блок / контроля, где осуществляется проверка наличия и порядка следования этого символа, а также анализ накопившейся суммы открывающих и закрывающих скобок с Затем с блока 3 управления подается сигнал на блок / контроля, где изменяется состояние триггеров 22,26 и 28. После этого осуществляется разблокирование регистра 1 и на него могут поступать для анализа состав- I ляющие следующего уравнения дизъюнктивной формы входной грамматики„

Преобразование символов входной грамматики в программу контроля происходит до тех пор, пока в регистре 1 не окажется символ конца дизъюнктивной формы (,%) . При этом блок 3 управления переключает коммутатор 8 на запись ич блока 5 памяти в выходной регистр 9 той конструкции выходного языка, которая определяет выход из программы контроля и вырабатывает сигнал Останов. Генератор прекращает работу.

Блок 3 управления работает следующим образом. Запуск генератора осуществляется при наличии разрешающего потенциала на единичном выходе триггера 15 (положение Пуск). При его наличии сигналы с генератора 14 так- товых импульсов поступают на узел 12 памяти и одновременно на элемент 16 задержки, а пройдя элемент 16 задержки и элемент И 1/, поступают на программируемую логическую матрицу И 10. Элемент 16 задержки предназначен для начальной установки узла ,12 памяти перед пуском устройства

Программируемые логические матрицы И 10 и ИЛИ 11 организованы известным способом. Выходы матрицы И 10 соединены с входами матрицы ИЛИ 11 таким образом, что поступающие от дешифратора 2 и счетчика 6 меток сигналы , (,12), пройдя матрицу И 10, ,

преобразуются в некоторую совокупность логических произведений, а затем, пройдя матрицу ИЛИ 11, преобразуются в логические суммы от этих логических произведений„ Результат суммирования снимается с одноименных выходов в виде управляющих сигналов Y | (J ) бпока 3 управления.

Сигнал Останов устройства вырабатывается элементом ИЛИ 13 при поступлении с дешифратора 2 на входы матрицы И 10 сигнала, определяющего конец дизъюнктивной скобочной формы входной грамматикио

Программируемые логические матрицы И 10, ИЛИ 11 и узел 12 памяти обеспечивают реализацию любой схемы перевода входного языка в выходной язык без переделки связей между блоками. При переходе с одного выходного языка на другой язык корректировке подлежат лишь используемые в блоке 5 памяти базовые конструкции выходного языка. При изменении входного языка никаких корректировок не требуется ввиду специальной (самонастраиваемой) формы представления входной грамматики.

Работу генератора и его основных блоков можно дополнительно проиллюстрировать на следующем примере,

Пусть необходимо сгенерировать программу на языке Ассемблер для синтаксического контроля логических выражений с одной унарной и с одной бинарной операциями: отрицанием и дизъюнкцией Грамматика такого рода логических выражений представима в -виде следующей системы уравнений в алгоритмических алгебрах

/3, ());

/33(q3P,v/yq4i4VN));

#

де

P.

рг

1,если с переменной Р, первого уравнения связывается знак отрицания контролируемых выражений;

0,в противном случае,

1,если с переменной Р„ первого уравнения связывается операнд контролируемых выражений;

О, в противном случае,

w

1, если с переменной Р

b

IV

второго уравнения связывается знак дизъюнкции контролируемых выражений;

0,в противном случае,

1,если с переменной Р3 второго уравнения связывается чнак конца выражения; О, в противном случае о

Если считать, что в ячейки блока 5 памяти занесены базовые конструкции языка Ассемблера (табл.1), то пошаговое преобразование исходной системы уравнений в программу будет осуществляться в соответствии с табл. 2о

0

5

0

5

0

5

0

5

Содержательный смысл приведенных в табл02 управляющих сигналов блока 3 управления следующий: У„ Y, Y Y, W

ъ Y, останов устройства; сброс в нулевое состояние счетчика 6 меток; увеличение на единицу значения счетчика 6 меток; сброс в нулевое состояние реверсивного счетчика 18 блока контроля;

-разблокирование (эаблоки- рование) входного регистра; переключение коммутатора 8 на запись текущего символа из входного регистра 1 Б выходной регистр 9; переключение коммутатора 8 на запись содержимого счетчика 6 меток в выходной регистр 9;

-установка в нулевое (единичное) состояние триггера 22 блока контроля;

)- установка в нулевое (единичное состояние триггера 28 блока контроля;

)- установка в нулевое (единичное) состояние триггера 26 блока контроля;

-переключение коммутатора 8 на запись данных из блока

5 памяти в выходной регистр; ()-формирование дешифратором 4 адресов ячеек блока 5 памяти, хранящих соответственно ISR PC, В, BCS, NP, Q, BR, NOP, ENDuP1,1- .

w

Y,

Y1Ј(Y13

К

Преобразование 1-го уравнения исходной системы к программе на языке Ассемблер завершается за 23 шага. Преобразование 2-го уравнения идентично первому. Сгенерированная устройством программа для всей исходной системы уравнений приводится в табл 3.

Блок 7 контроля работает следующим образом. Текуший символ исходного представления входной грамматики последовательно поступает на входной регистр 1 устройства,, а затем на дешифратор 2. Последний формирует выходной сигнал, соответствующий текущему символу грамматики.,

Если текущий символ является одной 1 из букв алфавита входной грамматики, 1 то соответствующий ему сигнал с дешифратора 2 подается на блок / контроля и, пройдя в нем элементы И и ИЛК (табл.4), подается на элемент ИЛИ 32.

Если исходная запись входной грамматики не содержит ошибок, то в любой момент времени на выходе элементов И ч ЧШ; согласно таблс 4 долж- нь г.а ть i глькс Наличие сигнала ьа выходе элемента ИЛИ 32 рассматри- ва.т- кат- .ьтиг а г, о входной тнкг , Л t-1 ро.г калачик и порядк слгдсвамин огмволов в исходном пгед- гррмматики осуществляется комбинационной схемой (элементы И, ИЛИ и чнчерторы) совместно с группой RS-7 Иггсров. состояние которых изменяемся под непосредственным воздействием выходных сигналов блока 3. Изменение состояния триггеров 22,-26, 28 осуществляется непосредственно перед разбл К ровкой входного регистра 1 в соответствии с табл., 5.

Есги текущий символ является от- 1. 1(гюц V скобкой, то си -нал с дешифратора 2 поступает на суммирующий вход реверсивного счетчика 18, а в случае, если это закрывающая скобка - на вычитающий0

В процессе генерации программ непрерывна контролируется текущая сумма отгрызающих и закрывающих скобок. Нулевая сумма соответствует балансу скобок. Последний должен соблюдаться по окончании каждого уравнения исход- ного представления грамматики, , при поступлении во входной регистр 1 знака (;) или знака #) „

0

5

0

5

0

5

0

5

0

5

В случае нарушения баланса скобок или появления знака (;) или знака (ft) внутри уравнения на выходе реверсивного счетчика 18 формируется код, в разрядах которого содержится хотя бы одна единица о В этом случае на выходе элемента ИЛИ 19 формируется сигнал, который, пройдя элемент И 20, появляется на выходе блока контроля ч в виде сигнала ошибки,.

В случае отсутствия знака (;) в конце некоторого неконечного уравнения или отсутствия нака Сфг) в конце последнего уравнения при соблюдении баланса скобок, на выходе элемента ИЛИ 21 формируется сигнал, который, пройдя элемент ИЛИ 32, появляется на выходе блока контроля в виде сигнала ошибки,

Отсутствие знака (;) в конце анализируемого уравнения с одновременным нарушением баланса скобок (парная ошибка) должно обнаруживаться при поступлении начального оператора Р последующего уравнения, так как в этом случае триггер 22 не перейдет в нулевое состояние (единичное состояние соответствовало конечному знак} уравнения - ьакрывающей скобке), и выходной сигнал, после триггера 22 пройдя элемент ИЛИ 25 и ИЛИ 32, п- явится на выходе блока контроля в вид -.игнала ошибки „

Поскольку баланс скобок соблюдается не только для конечного знака (;), но и для начальных знаков (Р или ) анализируемого уравнения, то может вырабатываться ложный сигнал ошибки Для его предотвращения сигналы X, X и X, формируемые дешифратором 2, подаются на вход блока ИЛИ 21„

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

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

Генератор программ для управляемого синтаксического контроля, содержащее дешифратор операторов, блок управления, блок памяти, счетчик меток, причем выход дешифратора операторов соединен с первым входом блока управления, первый выход которого является выходом Останов устройства, второй выход блока управления соеди- не| со счетным входом счетчика меток,

13

10

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

входного регистра, выход которого гистра, выход которого являет подключен к входу дешифратора и перво- 20 мационным выходом устройства, му информационному входу коммутатора,

Таблица 1

15

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

Базовые конструкции выходного языка

PC,

UP,

Метка Метка

Двоеточие после метки Оператор перехода к подпрограмме Оператор безусловного перехода Оператор перехода по условию Оператор конца программы Имя подпрограммы семантического контроля входного выражения Имя подпрограммы определения принадлежности символа входному языку Пустой оператор

10

гистра, выход которого являет - 20 мационным выходом устройства,

15

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

Таблица 3 Операторы языка Ассемблер

Метки

Р, :

NP, :

Примечание. Подпрограммы устанавливают принадлежность элементов логического выражения алфавиту исходной грамматики. Подпрограммы включены для возможности проведения семантического контроля входных выражений с Указанные подпрограммы должны быть предварительно включены в библиотеку подпрограмм и введены в память ЭВМ

или N V

Р

Х10 или Х„

ХЈ

ISR PC, В,

BCS NP

ISKPC, Q

BRР,

ISRPC, B2

BCSNPZ

ISRPC, Qz

Таблица 4

27

29,30

23,25

24,25,29,31

О

Ц

1--О

1 0-vO

Состояние триггеров 26 и 28 не изменяется

Состояние всех триггеров не изменяется

О -1

0-1

14

Примечание. Знак /v/ определяет один из следующих символов:

скобку (открывающую и закрывающую), знак конца уравнения (;) или ($р) или L-ИМВОЛ Ґ - букву другого (не используемого грамматикой) алфавита

L

fyCKg

IW V--T- - -

I 1

ерш и

т

г г г

ю

167246/

20 Продолжение табл.6

У, в - 9ц

t k i i /

НЗ

ж.

12

ffi

7

Фиг. 2

Qm дешифратора 2.

%2 XjXjXjXfjXfXifXgXjQX

(О

1

I

1

т

I

§

I

Фиг.З