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

 

Изобретение относится к вычислительной технике и может быть использовано для синтаксического контроля соответствия входной последовательности символов формальной грамматике языка. Цель изобретения - расширение функциональных возможностей устройства за счет контроля контекстно-независимых языков. Для достижения указанной цели в устройство дополнительно введены элементы И 4-6, элементы 8 и 9 задержки, счетчик 14, элементы ИЛИ 16 и 17, элемент ИЛИ-НЕ 18, сумматор 19, группа 20 элементов ИЛИ, группы 21 и 22 элементов И. стек 23 и дешифратор 25. Введение данных элементов и порождаемых ими связей позволяет реализовать указанные преимущества. 2 ил.

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

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

РЕСПУБЛИК

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

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

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А8ТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4714776/24 (22) 04,07,89 (46) 23,10,91. Бюл. N. 39 (72) В.А.Балабанов, П.В.Денисович, А.В.Тихобаев и А.Г,Шевчик (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 780011, кл, G 06 F 15/38, 1971.

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

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

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

Цель изобретения — расширение функциональных возможностей устройства за счет контроля контекстно-независимых языков.

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

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

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

15, первый 16 и второй 17 элементы ИЛИ, элемент ИЛИ-НЕ 18, сумматор 19, группу элементов 20, первую 21 и вторую 22 группы

„„Я3 „„1686462 А1 синтаксического контроля соответствия входной последовательности символов формальной грамматике языка, Цель изобретения — расширение функциональных воэможностей устройства за счет контроля контекстно-независимых языков. Для достижения указанной цели в устройство дополнительно введены элементы И 4-6, элементы 8 и 9 задержки, счетчик 14, элементы ИЛИ 16 и 17. элемент ИЛИ-НЕ 18, сумматор 19, группа 20 элементов ИЛИ. группы 21 и 22 элементов И, стек 23 и дешифратор 25, Введение данных элементов и порождаемых ими связей позволяет реализовать указанные преимущества. 2 ил, элементов И, стек 23, первый 24 и второй 25 дешифраторы, блок 26 памяти символов, блок 27 памяти номеров команд, блок 28 памяти количества символов. Стек (см. фиг.

2) содержит счетчик 29, элемент задержки

30, дешифратор 31, группу из N элементов

И 32, группу из N регистров памяти 33, груп- Со пу из N элементов И 34 и группу элементов 0

ИЛИ 35, Устройство позволяет осуществ- Дь, лять синтаксический контроль последова- 0с, тельности символов (предложений языка), ) по0ожденной некоторой формальной грамматикой, Формальной грамматикой языка будем называть четверку символов Ч,, Чм, P.

S >, где VT — алфавит терминальных символов; P — множество порождающих правил вывода; S — аксиома (54Чи). Под правилами вывода понимают преобразования а -+)3, где а и/3 — цепочки символов из VT

Vtu Чм — алфавит нетерминальных символов.

Предлагаемое устройство позволяет осуществлять синтаксический контроль языков, 1686462 порождаемых контекстно-независимыми грамматиками, т.е. грамматиками, порождающие правила которых имеют вид А Ð где А А; P — строка символов из алфавита ч а, уу

Синтаксис языковых конструкций описывается в виде набора понумерованных команд, каждая из которых содержит три поля. В первом поле содержится терминальный символ языка xc- Vr или специальный символ у Ми(Чэ — алфавит специальных символов, VsqV =ф) для обработки специальных команд, во втором поле — число N символов, которые могут следовать в предложениях языка вслед за символом данной команды, в третьем поле хранится номер

М», соответствующий номеру команды, Устройство отрабатывает четыре специальные команды: "Безусловный переход", "Запись в стек", "Возврат по адресу", "Выход". Контроль синтаксиса производится следующим образом, Первый поступающий символ сравнивается с символом х1, хранимым в первом поле команды. Если они совпадают, то осуществляется переход к команде с номером N», хранящимся в третьем поле первой команды, При этом устанавливается значение счетчика возможных ветвей, равное N< — содержимому второго поля первой команды, и вводится следующий символ, который сравнивается с содержимым первого поля N»-й команды, Если вновь поступивший символ не совпал с символом xtv»первым полем N»-й команды, то от счетчика возможных ветвей отнимается единица и происходит переход к команде, следующей заданной (c номером М»+1). При этом ввод нового символа не производится. Если число на счетчике возможных ветвей становится равным нулю, то вводимая последовательность символов с точки зрения формальной грамматики языка является ошибочной. Если в первом поле команды содержится символ у1 специальной команды, то новый символ входной последовательности не вводится. Если у1 — символ команды безусловного перехода, то в счетчик команд заносится значение N», хранящееся в третьем поле команды, в счетчик ветвей заносится значение N< из второго поля команды, осуществляется переход на команду с номером N,. Если y> — символ команды записи в стек, то в стек заносится номер команды, следующей эа данной, в счетчик команд заносится значение N» из третьего поля команды, в счетчик ветвей заносится значение N< из второго поля команды и осуществляется переход на команду с номером N». Если yi - символ команды

55 возврата по адресу, то в счетчик команд заносится номер команды из верхушки стека и осуществляется переход на команду с этим номером. Если стек пустой, то это означает ошибку при программировании набора команд, Если y> — символ команды выход, то на выходе устройства появляется сигнал об успешном окончании синтаксического анализа.

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

При включении устройства производится установка начального состояния устройства, При этом на счетчике 13 и вычитающем счетчике 15 устанавливается значение единица, на счетчике 14 — ноль, триггер 10 устанавливается в единицу. В блоки памяти символов 26, номеров команд 27 и количества символов 28 записываются команды (формализованное описание синтаксиса языка). В блок памяти команд 11 заносится последовательность символов, которая контролируется, причем в первые разряды регистров блока памяти команд информация не заносится. Так как начальное значение счетчика 13 равно единице, то дешифратор

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

Этот сигнал поступает на управляющие входы блоков памяти символов, номеров команд и количества символов и на выходе этих блоков устанавливаются сигналы, соответствующие содержимому полей первой команды. Если в блоке памяти символов содержится терминальный символ, то на всех выходах второго дешифратора 25 устанавливаются нули, на выходе элемента ИЛИНŠ— единица, которая поступает на третьи входы первого 1 и третьего 3 элементов И.

Ноль с третьего выхода дешифратора 25 открывает группу элементов И 21 и закрывает группу элементов И 22, а также закрывает элемент И 6. Значение номера команды из блока памяти номеров команд через группу элементов И 21 и через группу элементов

ИЛИ 20 поступает на информационный вход счетчика 13.

После приведения устройства в исходное состояние на тактирующий вход устройства поступает короткий тактовый импульс, Интервал между импульсами выбирается большим, чем максимальное время срабатывания устройства при обработке очередного символа. Тактовый импульс открывает элемент И 1, так как на втором входе этого элемента триггером 10 установлена единица, а на третьем входе — единица от элемента ИЛИ-НЕ 18. Сигнал с выхода элемента И

1 увеличивает на единицу значение счетчика

14 и позволяет считывание следующего символа входной последовательности симво1686462 лов, записанных в блоке памяти команд 11.

Считанный символ сравнивается в блоке сравнения 12 с символом на выходе блока памяти символов 26. Если эти символы совпали, то на выходе совпадения блока срав- 5 нения устанавливается единица, иначе единица устанавливается на выходе несовпадения. Если символы совпали, то тактовый импульс, пройдя через элемент задержки 7, открывает элемент И 2. Им- 10 пульс с выхода элемента И 2 подается на вход установки триггера 10, через элемент

ИЛИ 16 — на вход разрешения установки вычитающего счетчика 15, через элемент

ИЛИ 17 — на вход разрешения установки 15 счетчика 13. При этом в вычитающий счетчик 15 переписывается сигнал с выхода блока памяти количества команд 28, а в счетчик

13 — с выхода блока памяти номеров команд

27. Значение счетчика 13 поступает на ин- 20 формационный вход дешифратора 24, с выхода которого сигнал поступает на соответствующие входы блоков памяти символов 26, номеров команд 27, количества символов 28. При этом на выходах блоков 25 памяти 26 — 28 устанавливаются новые значения. Если блок сравнения 12 выработал напряжение на выходе несовпадения, то сигнал с выхода элемента задержки 7 открывает элемент И 3, сигнал на выходе ко- 30 торого устанавливает триггер 10 в ноль, тем самым запрещая ввод следующего символа, увеличивает на единицу значение счетчика

13 и уменьшает на единицу значение вычитающего счетчика 15, Если при этом значе- 35 ние вычитающего счетчика 15 оказывается равным нулю, то на выходе признака синтаксической ошибки появляется сигнал об ошибке. При этом на выходе номера ошибочного символа (выход счетчика 14) уста- 40 навливается номер ошибочного символа.

Если сигнал на выходе блока памяти символов 26, поступающий на вход блока сравнения 12 и на вход дешифратора 25, является символом специальной команды, то появля- 45 ется сигнал на соответствующем выходе дешифратора 25. Если сигнал появляется на четвертом выходе (специальная команда

"выход") дешифратора 25, то это признак успешного завершения синтаксического 50 контроля входной последовательности символов, В случае появления сигнала на любом из первых выходов дешифратора 25 элемент ИЛИ-НЕ 18 запирает элемент И 1, тем самым запрещая ввод следующего сим- 55 вола входной последовательности, а также элемент И 3. В случае появления сигнала на первом выходе дешифратора 25 (команда

"Безусловный переход") этот сигнал идет на второй вход элемента И 4. Тактовый импульс после элемента задержки 7 открывает элемент И 4. С выхода элемента И 4 сигнал через элемент ИЛИ 16 поступает на вход разрешения установки вычитающего счетчика 15, а через элемент ИЛИ 17 — на вход разрешения установки счетчика 13. При этом в счетчик 13 и вычитающий счетчик 15 записываются значения, установленные на выходе блоков памяти номеров команд 27 и количества символов 28. Если символ, поступающий на вход дешифратора 25, является символом специальной команды

"Запись в стек", то сигнал появляется на втором выходе дешифратора 25, Этот сигнал поступает на первый вход элемента И 5.

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

19, т,е. номер команды, следующей за текущей. Этот номер записывается в стек 23.

Сигнал с выхода элемента И 5 через элемент задержки 8 поступает на третий вход элемента ИЛИ 16, с выхода которого поступает на вход разрешения установки вычитающего счетчика 15, а через элемент ИЛИ 17 — на вход разрешения установки счетчика 13.

При этом в счетчик 13 и в вычитающий счетчик 15 записываются значения номеров команд и количества символов соответственно из блоков памяти номеров команд 27 и количества символов 28. Если символ, поступающий на вход дешифратора

25, является символом специальной команды "Возврат по адресу", то сигнал появляется на третьем выходе дешифратора 25. Этот сигнал закрывает первую группу элементов

И 21, открывает вторую группу элементов И

22 и поступает на первый вход элемента И

6. Значение номера команды из вершины стека через открытую группу элементов И 22 и через группу элементов ИЛИ 20 поступает на информационный вход счетчика 13, Тактовый импульс, поступающий на второй вход элемента И 6, открывает его и через элемент ИЛИ 17 поступает на вход разрешения установки счетчика 13, в который записывается значение номера команды из стека 23. Затем сигнал с выхода элемента

И 6 через элемент задержки 9 поступает на вход выталкивания стека 23, После обработки команды значение номера очередной команды с выхода счетчика 13 поступает на вход дешифратора 24. Дешифратор 24 подает сигнал на соответствующий выход. с которого поступает на управляющие входы блоков памяти символов, номеров команд и

1686462

55 количества cMMBofloB, Цикл повторяется до получения сигналов либо на четвертом выходе дешифратора 25 (нормальное завершение контроля), либо на выходе обнуления вычитающего счетчика 15 (синтаксическая ошибка во входной последовательности символов).

Стек (см. фиг. 2) работает следующим образом.

При поступлении на второй управляющий вход(вход разрешения записи) сигнала происходит добавление единицы к содержимому счетчика 29, срабатывание дешифратора 31 и открытие входным сигналом, задержанным в элементе задержки 30, соответствующего элемента группы элементов И 32, сигнал с выхода которого записывает сигнал на входе стека в соответствующий регистр 33 группы, а далее через открытую группу элементов И блока 34 и группу элементов ИЛИ 35 сигнал с входов стека проходит на его выход, Если стек пуст, т.е. счетчик 29 обнулен, то на управляющем выходе стека появляется сигнал, При поступлении сигнала на первый управляющий вход (вход выталкивания из стека) значение на счетчике 29 уменьшается на единицу, происходит как бы выбрасывание последнего записанного значения.

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

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

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

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

1686462

Фиг. 7

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

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