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

к входу третьего элемента ИЛИ, второй вход которого подключен к выходу первого триггера и к выходу ошибки устройства, выход четвертого регистра соединен с первым информационным входом первого регистра первой группы, выход которого соединен с первьм входом третьего блока элементов И, выход третьего элемента ИЛИ соединен с входами сброса первого, второго регистров и регистров первой и третьей групп,выход 2го (г ) регистра третьей Ipynпы соединен с первыми входами (z-2)го блока элементов И второй группы, выход второго триггера соединен с вторьми входами блоков элементов И второй группы, выход-первого элемента ИЛИ соединен с первыми входами блоков элементов И третьей группы, выход у - го (У 1, п-1) регистра третьей группы подключен к вторьм входам у-го блока элементов И третьей группы, информационный вход у-го регистра третьей группы соединен с выходом у-го блока элементов ИЛИ группы, выход второго регистра третьей группы подключен к первым входам первого блока элементов ИЛИ группы, выход U)ro (0 1, n-l) блока элементов И второй группы подключен к первому входу (w+1)-ro блока элементов ИЛИ группы, выход U) -го блока элементов И третьей группы - к второму входу {и)+1)-го бло96899

ка элементов ИЛИ группы, выход - го (f 1, Ф) блока элементов И четвертой группы соединен с F-M (F 1,Ф) входом .f-rp блока элементов ИЛИ группы, выходы которого соединены с вторыми входами первого блока элемен тов ИЛИ группы, выход F-ro регистра второй группы соединен с первыми входами F-ro блока элементов И четвертой группы, F-йвыход дешифратора подключен к вторым входам F-ro блока элементов И четвертой группы, выход j-ro (j i, m) регистра первой группы соединен с информационным входом (j+1)-ro регистра первой группы, выходы формирователей импульсов группы соединены с входами четвертого .элемента ИЛИ, выход которого подключен к установочному входу четвертого триггера, вторые входы второго и третьего блоков элементов И соединены с выходом четвертого триггера, выходы второго блока элементов И подключены к информационным входам первой половины разрядов второго регистра, к информационным входам вторбй половины разрядов которого подключены выходы второго блока элементов И, вход начального символа грамматики устройства подключен к второму информационному входу первого регистра третьей группы, выходы (п-1)-го блока элементов И третьей группы под ключей к информационному входу н -го регистра третьей группы.

УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО АНАЛИЗА ПРОГРАММ, содержащее первый, второй триггеры, первый, второй блоки элементов И,первый,второй , регистры, постоянный запоминающий блок, формирователь импульсов, элемент И, первый элемент ИЛИ, причем выход первого блока элементов И соединен с первым информационным входом первого регистра, выход которого соединен с первьм входом второго блока элементов И, первый и второй выходы признаков и информационный выход постоянного запоминающего блока соединены с входами первого, второго триггеров и второго регистра, выход второго триггера соединен с вторым входом первого блока элементов И, отличающееся тем, что, с целью сокращения среднего времени синтаксического анализа программ, в него введены третий и четвертый регистры, третий блок элементов И,первая, вторая и третья группы регистр&в, группы блоков элементов ИЛИ, первая, вторая, третья и четвертая группы ОЛОКОБ элементов И, третий и четвертый триггеры, группа формирователей импульсов,генератор импульсов, второй третий, четвертый элементы ИЛИ,блок элементов ИЛИ,дешифратор исчетчик. причем информационный выход счетчика I подключен к входу дешифратора,выход j-ro (j 1,m) регистра первой группы соединен с первым входом j-ro блока элементов И первой группы, выход которого подключен к j - му выходу группы информационных выходов устройства, выход третьего регистра соединен с входами формирователей импульсов группы и с входом постоянного запоминающего блока, выход третьего признака, группа информационных выходов и выход номера правила которого подключены соответственно к входам третьего триггера, регистров i второй группы и четвертого регистра, (Л входы первого и последукмцих символов строки программ устройства соединены соответственно с вторьтм информационным входом первого регистра и . вторым входом первого блока элементов И, информационные выходысчетг чика подключены к входам первого :о элемента ИЛИ, первьй, второй, третий и четвертый входы второго элемента 05 00 ИЛИ соединены соответственно с выходами второго, третьего, первого (Г триггеров и элемента И, входы кото-, со рого соединены с инверсным информационным выходом счетчика, вычитающий и информационный входы которого соединены соответственно с выходами генератора импульсов и третьего регистра, выход второго элемента ИЛИ соединен с входом формирователя импульсов, выход которого подключен к установочному входу четвертого триггера, выход третьего триггера подключен к вторым входам блоков элементов И первой группы, к выходу Конец контроля устройства и

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

Цель изобретения - сокращение среднего времени синтаксического анапиза программ.

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

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

гистр 14, группу формирователей 15 импульсов, первую группу регистров 16, формирователь 17 импульсов, четвертый триггер 18, первую группу блоков 19

элементов И, генератор 20 импульсов, счетчик 21, дешифратор 22, первый элемент ИЛИ 23, четвертую группу блоков 24 элементов И, третий 25 и второй 26 блоки элементов И элемент И

27, второй элемент ИЛИ 28, блок 29 элементов ИЛИ, третий 30 и четвертый 31 элементы ИЛИ, выход 22 Конец контроля, входы 33 и 34 первого и по- следунщик символов , группу информационных выходов 35 , выход 36 ошибки , в-хоц 37 начального символа.

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

Заданы набор правил (1)S

S-VB (2)Л

(3)

а g S А (4)

и таблица разбора: входная строка авв,ав e,S $ ,е авв ав е BF. ав е вв ав е в ав е в ав е В исходном состоянии регистры 1,3,7,12 - 14 и 16,триггеры 9 - 11 и счетчик 21 обнулены. Управляющая программа заносит в первый регистр 3 (верхушка стека или магазина) код начального символа грамматики по входу 37, а в регистр 1 - код первого символа входной стро- ки (для примера а) по входу 33. Содержимое регистров 1 и 3 заносится, соответственно, в старшие и младшие разряды регистра 7 адреса постоянного запоминающего блока 8. При этом на выходе элемента ИЛИ 31 появляется сигнал, который устанавливает триггер 18 в единичное состояние, чем запрещается прохождение кодов адреса в регистр 7 через блоки элементов И 25 и 26. По данному адресу производится выборка, в результате чего на выходном регистре запоминающего устройства появляется следующая информация: признаки (ошибка триггер 9 в единичном состоянии, сдвиг - триггер 10, допуск, т.е. конец разбора - триггер 11 в единичном состоянии), количество символов правила (регистр 12), коды символов (регистры 13) и код номера правила (регистр 14).

При этом возможны следующиеварианты: в соответствующем месте таблицы разбора, хранящейся в постоянном запоминающем блоке 8 (задается содержимьи первого регистра 3 - номечание, J, е - граничные символы; ош - ошиб ка.

также разбор строки: магаз ASj{ BSAS $ SAS в AS j AS jj aSj S $ 25

личество символов F правила из регистра 12 записывается в вычитающий счетчик 21, содержимое которого дешифруется дешифратором 22, .в результате чего содержимое F-ro регистра 13 (код символа правила) через соответствующий F-й блок 24 элементов И и блок 29 элементов ИЛИ заносится в первый (верхний по схеме) регистр 3, при этом производится сдвиг стека, реализованного блоком регистров 3, вниз. Затем с генератора 20 импульсов на вычитающий вход счетчика 21 поступает импульс, в результате чего

содержимое счетчика 21 уменьшается на. единицу ST 21 : F-1 и содерясимое (F-l)-ro регистра 13 заносится в первый регистр 3. Описанный процесс продолжается до тех пор, пока коды

5 всех символов правила не записаны в обратном порядке в блок регистров 3. При этом содержимое счетчика 21 равно нулю, на выходе элемента И 27 поинвыходная строка jt Допуск мер строки и регистра 1 - номер столбца) содержится правая часть правила и его номер (вариант 1); ошибка ( II) j сдвиг (вариант Ш) и допуск конец разбора (вариант 1У). В варианте 1 триггеры 9-11 находятся в нулевом состоянии. Код номера правила из регистра 14 заносится в первый регистр 16 (при этом производится сдвиг стека, состоящего из регистров 16 по схеме вправо). Коявляется единичный сигнал, который через элемент ИЛИ 28, формирователь 17импульсов устанавливает триггер 18в нулевое состояние. На нулевом выходе триггера 18 появляется единичный сигнал, который разрешает прохождение содержимого регистра 1 и пер вого регистра 3 через блоки 26 и 25 элементов И, соответственно, в регистр 7. В результате чего производится очередное обращение к блоку 8. В варианте П из блока 8 считывается информация в триггеры 9-11,1)егистры 12-14,содержащая нули за исключением разряда, которому соответствует триггер 9: Т9 1 .Единичное состояние триг-гера 9 указывает на синтаксическую ошибку в анализируемой строке. По сигналу с единичного выхода триггера 9. производится следующая последовательность действий: на выходе 36 устройства появляется сигнал, указывающий на ошибку в анализируемой стро ке; триггер 18 через элемент ИЛИ 28 и формирователь 17 импульсов устанавливается в нулевое состояние и сигнал с выхода элемента ШШ 30 обнуляет регистры 1 и 7, блоки регистров 3 и 16

На этом работа устройства заканчивается.

В варианте Ш из блока 8 считывается нулевая информация за исключением разряда, которому соответствует триггер 10: .Т10 1. Единичное состояние триггера 10 указывает на то,

Таким образом в результате разбора синтаксически правильной строки на выходы 35 устройства вьщается последовательность кодов номеров правил, используемых при написании данной строки. что в данном элементе таблицы разбо ра, хранящейся в блоке 8, записан сдвиг. При этом разрешается запис очередного символа строки по входу 34 устройства через блок 2 элементов И в регистр 1, производится сдвиг блока регистров 3 вверх (по схеме), соответственно, через блоки 5 и 4, и триггер 18 через элемент ИЛИ 28 и формирователь 17 импульсов устанавливается в нуль. В варианте 1У из блока 8 считывается нулевая информация за исключением разряда, которому соответствует триггер 11: Т 11 1. При этом триггер 18 через элемент ИЛИ 28, формирователь 17 импульсов устанавливается в нулевое состояние на выходе 32 устройства появляется сигнал, свидетельствующий об успешном окончании разбора входной строки: через элемент ИЛИ 30 обнуляются регистры 1, 7 JH 3; на входах 35 устройства появляется множество кодов номеров правил разобранной строки, поступивших из регистров 16 через блоки 19 элементов И.На этом работа устройства заканчивается.