Устройство синтаксического контроля Советский патент 1990 года по МПК G06F17/27 

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

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

На чертеже представлейа структурная схема устройства.

Устройство для синтаксического контроля содержит элементы И 1-3, элемент 4 задержки, счетчик 5, пер- вьй 6 и второй 7 вычитающие счетчики, триггер 8, дешифратор 9, блок 10 памяти команд, схему 11 сравнения, блок 12 памяти терминальных символов, блок 13 памяти количества символов, блок 14 памяти номеров команд.

. Устройство работает следующим образом.

Устройство позволяет осуществлять синтаксический контроль последовательности символов (предложений языка) , порожденный некоторой формальной грамматикой.

Формальной грамматикой языка будем называть четверку V, V, P,S где V - алфавит терминальных символов; V - алфавит нетерминальных символов; Р - множество порождающих правил вывода; S - аксиома (S е V). Под правилами вьшода понимают преобразования (Ь, где о( и д - цепочки символов из V и V .

т N

Предлагаемое устройство позволяет осуществлять синтаксический контроль ЯЗЫКОВ, поражающих регулярными грамматиками, т.е. грамматиками, правипа которых имеют вид: А - аВ, где А V, В е V U, а е V .

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

Контроль синтаксиса производится следующим образом.

Первый поступающий символ сравнивается с символом Х, хранимым в пер- вом поле первой команды. Если они J совпадают, то происходит переход к команде с номером N, хранящимся в третьем поле первой команды. При этом устанавливается значение счетчика возможных ветвей, равное содер- 0 жимому второго поля первой команды, и вводится следующий символ, который сравнивается с содержимым первого поля команды.

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

Устройство синтаксического контроля работает следующим образом.

Производится установка начального состояния устройства. При этом 0 иа счетчике 7 и на счетчике 5 устанавливается значение Единица, триггер 8 устанавливается в единицу, в счетчике 6 записывается число, равное числу символов, которое подвер- гается синтаксическому контролю. В блоке 12 памяти терминальных символов записьшаются N символов, т.е. значения первых полей команд, в блоке памяти количества символов записы- д вается содержимое вторых полей команд N,a в блоке 14 памяти номеров команд данных - третьих полей команд N.,.

К

В блок 10 памяти команд заносит- 5 ся последовательность символов, которая контролируется, причем в первые разряды регистров группы информации не заносится.

Так как начальное значение счет- 0 чика 5 равно единице, то дешифратор 9 подает напряжение на 1-й выход. Этот сигнал поступает на входы блоков 12-14 памяти.и на выходе этих блоков устанавливаются сигналы, со- ответствутацие их содержимому.

Короткий тактовый импульс открывает первый элемент И 1, так как на втором входе этого элемента триггера 8 установлена единица. Первый эпемент И 1 уменьшает на единицу значение первого счетчика 6 и позволяет считывание следующего символа, записанного в блок 10 памяти команд. Считанный .символ сравнивается в схеме 11 сравнения с символом на выходе блока 12 памяти терминальных символов. Если эти символы совпали, то на выходе совпадения схемы 1 сравнения устанавливается единица, иначе единица устанавл1шается на выходе несовпаденияW

Тактовый импульс, пройдя через элемент 4 задержки, открывает второй элемент И 2 и третий элемент И 3. Если символы совпали, то импульс с выхода второго элемента И 2 подается на единичный вход триггера 8 и на входы разрешения установки счетчиков 5 и 7. При этом в счетчик 7 переписывается сигнал с выхода блока 13 памяти количества символов, а в счетчик 5 переписывается значение, установленное на выходе блока 14 памяти номеров команд. Значение счетчика 5 поступает на информационный вход дешифратора 9, который подает напряжение на соответствующий выход. При этом на выходах блоков 12-14 памяти устанавливаются новые значения.

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

Если схема 11 сравнения выработала напряжение на выходе несовпадения, то сигнал с выхода элемента 4 задержки откроет третий элемент И 3, сигнал на выходе которого установит триггер 8 в ноль, тем самым запретив ввод следующего символа, увеличит на единицу значение счетчика 5 и уменьшит на единицу значение счетчика 7.

Если при этом значение счетчика 7 оказалось равньм нулю, то на выходе признака ошибки устройства появляется сигнал об ошибке. Формула изобретения

Устройство синтаксического контроля, содержащее блок памяти ко0

5

0

5

0

5

0

5

0

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

Изобретение относится к вычислительной технике и может быть использовано для синтаксического контроля соответствия входной последовательности символов формальной грамматике языка. Цель изобретения - расширение области применения за счет расширения класса языков, поддающихся синтаксическому контролю. Устройство содержит элементы И 1 - 3, элементы задержки 4, счетчик 5, вычитающие счетчики 6, 7, триггер 8, дешифратор 9, блок 10 памяти команд, схему 11 сравнения, блок 12 памяти терминальных символов, блок 13 памяти количества символов, блок 14 памяти номеров команд. Устройство позволяет осуществлять синтаксический контроль последовательности символов (предложений языка), порожденный некоторой формальной грамматикой. 1 ил.