Устройство синтаксического контроля

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК щ) g С 06 F 15/38, 11/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н авто Сном СвидяткЛьСтвм

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И О 1НРЫТИЯМ

ПРИ ГННТ СССР

1 (21) 4447011/24-24 (22) 23 ° 05.88 (46) 23.08.90. Бюл. У 31 (72) В.Ю.Анисимов, В.А.Балабанов, И.Х. Галимзянов, П.В.Денисович, А.В.Тихобаев и А.Г.Шевчук (53) 681.325(088.8) (56) Авторское свидетельство СССР

N - 780011, кл. G 06 F 15/38, 1978.

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

N 1056210, кл. С 06 F 15/38, 1982. (54) УСТРОЙСТВО СИНТАКСИЧЕСКОГО КОНТРОЛЯ (57) Изобретение относится к вычислительной технике и может быть использовано для синтаксического контроля соответствия входной последователь„„SU„„1587542 A 1

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

9, блок 10 памяти команд, схему 11 сравнения, блок 12 памяти терминальных символов, блок 13 памяти количества символов, блок 14 памяти номеров команд. Устройство позволяет осуцествлять синтаксический контроль последовательности символов (предложений языка), порожденный некоторой йоомальной грамматикой. 1 ип.

1587542

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

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

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

10 памяти команд, схему 11 сравнения, блок 12 памяти терминальных символов, блок 13 памяти количества символов, блок 14 памяти номеров команд.

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

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

Формальной грамматикой языка будем н азывать четверку (V, Ч, P, S ) где V — алфавит терминальных симт волов; V „, — алфавит нетерминальных символов; P — множество порождающих правил вывода, S — аксиома (S E Vg) °

Под правилами вывода понимают пре-, образования с р где c(и 8 — цепочки символов из V 0 V

Предлагаемое устройство позволяет осуществлять синтаксический контроль языков, поражающих ре гулярными грамматиками, т. е . грамматиками, правила которых имеют вид: А - аВ, где АЕ, Ч„, В рЧ„,(3ф, à еЧ

Синтаксис языковых конструкций описывается в виде набора понумерованных команд, каждая из которых содержит три поля. В первом поле содержится терминальный символ языка

Х 6 V, во втором поле — число N символов, которые могут следовать в предложениях языка вслед за символом данной команды, в третьем поле хранится номер N„ соответствующий номеру команды.

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

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

Если вновь поступивший символ не совпал с символом Х ь1„- первым полем

И -й команды, то от счетчика возможных ветвей отнимается единица и происходит переход к команде, следующей за данной (с номером N „+,). При этом

Zp ввод нового символа не производится.

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

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

Производится установка начального состояния устройства. При этом на счетчике 7 и на счетчике 5 устанавливается значение "Единица", триггер 8 устанавливается в единицу, в счетчике 6 записывается число, равное числу символов, которое подвер35 гается синтаксическому контролю. В блоке 12 памяти терминальных символов записываются N символов, т.е. значения первых полей команд, в блоке памяти количества символов записы40 ВGeтся содержимое Вторых полей ко манд И,а в блоке 14 памяти номеров команд данных — третьих полей команд Nê

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

Так как начальное значение счетчика 5 равно единице, то дешифратор

9 подает напряжение на 1-й выход.

Этот сигнал поступает на входы блоков 12-14 памяти,и на выходе этих блоков устанавливаются сигналы, соответствующие их содержимому.

Короткий тактовый импульс открывает первый элемент И 1, так как на втором входе этого элемента триггера

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

Считанный символ сравнивается в схеме 11 сравнения с символом на выходе блока 12 памяти терминальных символов. Если эти символы совпали, то на выходе совпадения схемы 1 сравнения устанавливается единица, иначе единица устанавливается на выходе несовпадения

Тактовый импульс, пройдя через элемент 4 задержки, открывает второй элемент И 2 и третий элемент И 3.

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

13 памяти количества символов, а в счетчик 5 переписывается значение, установленное на выходе блока 14 памяти номеров команд. Значение счетчика 5 поступает на информационный вход дешифратора 9, который подает напряжение на соответствующий выход.

При этом на выходах блоков 12- 14 памяти устанавливаются новые значения.

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

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

4 задержки откроет третий элемент

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

Если при этом значение счетчика

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

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

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

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

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