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

 

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

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

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

РЕСПУБЛИК

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

hO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3768726/24-24 (22) 11.07.84 (46) 07.12.85. Бюл. У 45 (72) В.В.Мазаник, И.П.Бакров, К.А.Марченко и В.M.Íåôôà (53) 681.3(088.8) (56) Авторское свидетельство СССР

Ф 1056210, кл. С 06 F 15/38, 1982.

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

У 1034045, кл.G 06 F 15/38, 198 1. (54)(57) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО АНАЛИЗА ПРОГРАММ, содержащее первый, второй триггеры, первый, вто goA блоки элементов И,первый, второй . регистры, постоянный запоминающий блок, формирователь импульсов, элемент И, первый элемент ИЛИ, причем выход первого блока элементов И соединен с первым информационным входом первого регистра, выход которого соединен с первым входом второго блока элементов И, первый и второй выходы признаков и информационный выход постоянного запоминающего блока соединены с входами первого, второго триггеров и второго регистра, выход второго триггера соединен с вторым входом первого блока элементов И, о т л и ч а ю щ е е с я тем, что; с целью сокращения среднего времени синтаксического анализа программ, в него введены третий и четвертый регистры, третий блок элементов И,первая, вторая и третья группы регистров., группы блоков элементов ИЛИ, первая, вторая, третья и четвертая группы блоков элементов И, третий и четверЪ тый триггеры, группа формирователей импульсов, генератор импульсов, второй третий, четвертый элементы ИЛИ,блок б элементов ИЛИ,декоратор и счетчик, ((9) SU (!((A причем информационный выход счетчика подключен к входу деши@ратора, выход

j —.го (j=1 m) регистрапервой группы соединен с первым входом j — го блока элементов И первой группы, выход которого подключен к j — яу выходу группы информационных выходов устройства, выход третьего регистра соединен с входами формирователей импульсов группы и с входом постоянного запоминающего блока, выход третьего признака, группа информационных выходов и выход номера правила которого подключены соответственно к входам третьего триггера, регистров второй группы и четвертого регистра, входы первого и последующих символов строки программ устройства соединены соответственно с вторым информационным входомпервого регистра ивторым входом первого блока элементов И, информационные выходы счет-. чика подключены .к входам первого элемента ИЛИ, первый, второй, третий и четвертый входы второго элемента

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

1196899

2 к первому входу третьего элемента

ИЙИ, второй вход которого подключен к выходу первого триггера и к выходу ошибки устройства, выход четвертого регистра соединен с первые информационным входом первого регистра первой группы, выход которого соединен с первым входом третьего блока элементов И, выход третьего элемента ИЛИ соединен с входами сброса первого, второго регистров и регистров первой и третьей групп, выход йго (х 3, n) регистра третьей группы соединен с первыми входами (х-2)ro блока элементов И второй группы, выход второго триггера соединен с вторыми входами блоков элементов И второй группы, выход первого элемента КПИ соединен с первыми входами блоков элементов И третьей группы, выход,у - го (У 1, и-1) регистра третьей группы подключен к вторым входам у-ro блока элементов И третьей группы, информационный вход у-го регистра третьей группы соединен с выходом у-го блока элементов

ИЛИ группы, выход второго регистра третьей группы подключен к первым входам первого блока элементов ИЛИ группы, выход l0-ro (N 1, п-1) блока элементов И второй группы подключен к первому входу (в+1)-го блока элементов ИЛИ группы, выход м -го блока элементов И третьей группы — к второму входу (М+1)-ro блоИзобретение относится к вычислительной технике, в частности к устройствам для синтаксического анализа.

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

Устройство содержит первый регистр

1, первый блок 2 элементов И, третью группу регистров 3, группу блоков 4 элементов ИЛИ, вторую 5 и третью 6 группы блоков элементов И, третий регистр 7, постоянный запоминающий блок

8, первый 9, второй 10 и третий 11 триггеры, второй регистр 12, вторую группу регистров 13, четвертый река элементов ИЛИ группы, выход f- го (f 1, Ф) блока элементов И четвертой группы соединен с F-м (F 1,Ф) входом Е-го блока элементов ИЛИ группы, выходы которого соединены с вторыми входами первого блока элемен .тов ИЛИ группы, выход Р-го регистра второй группы соединен с первыми

I входами F-го блока элементов И четвертой группы, F-й выход дешифратора подключен к вторьм входам F-ro блока элементов И четвертой группы, выход, )-го (j = 1, m) регистра первой группы соединен с информационным входом (j+1)-го регистра первой группы, выходы формирователей импульсов группы соединены с входами четвертого ,элемента ИЛИ, выход которого подключен к установочному входу четвертого триггера, вторые входы второго и третьего блоков элементов И соединены с выходом четвертого триггера, выходы второго блока элементов И подключены к информационным входам первой половины разрядов второго регистра, к информационным входам вторбй половины разрядов которого подключены выходы второго блока элементов И, вход начального символа грамматики устройства подключен к второму информационному входу первого регистра третьей группы, выходы (n-1)-ro блока элементов И третьей группы подключен к информационному входу и -го регистра третьей группы..гистр 14, группу формирователей 15 импульсов, первую группу регистров 16, формирователь 17 импульсов, четвертый триггер 18, первую группу блоков 19

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

1О Z7, второй элемент ИЛИ ZS, блок 29 элементов ИЛИ, третий 30 и четвертый

31 элементы ИЛИ, выход 22 "Конец контроля", входы 33 и 34 первого и последующих символов, группу информационных выходов 35, выход

36 ошибки, вход 37 начального символа.

1196899 а,AS,! а, 3 сдвиг

5 ош ош в, 2 в А, 4 ош ош ош ош допуск ош сдвиг ош

10 и таблица разбора: входная строка магазин выходная строка

aAS в» ав е AS)

HSAS y в ав е SAS $ в Ass ав е АЬф

aSg в s$ в в е 9

В исходном состоянии регистры

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 — но1

14

14

142

142

1423

1423

14232 ! 4232

Сдвиг

Сдвиг

Сдвиг

Сдвиг

Допуск вв ав е в ав е ав е мер строки и регистра 1 — номер столбца) содержится правая часть правила и его номер (вариант 1); ошибка (вариант II); сдвиг (вариант

Ш) и допуск конец разбора (вариант

В варианте 1 триггеры 9 — 11 находятся в нулевом состоянии. Код номера правила из регистра 14 заносится в первый регистр 16 (при этом

-производится сдвиг стека, состоящего

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

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

О

55 всех символов правила не записаны в обратном порядке в блок регистров 3.

При этом содержимое счетчика 21 равно нулю, на выходе элемента И 27 поз

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

Заданы набор правил

S -ю. aAS (1) S

S в (2) А

А - .а (3) а

А — в SA (4) 8 авв,ав е,S g,å авв ав е а в е л--Примечание.ф, е- граничные символы; ош — ошиб ка.

Задан также разбор строки:

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

5 1 1968 является единичный сигнал, который через элемент ИЛИ 28, формирователь

17 импульсов устанавливает триггер

18 в нулевое состояние. На нулевом выходе триггера 18 появляется еди5 ничный сигнал, который разрешает прохождение содержимого регистра 1 и первого регистра 3 через блоки 26 и 25 элементов И, соответственно, в регистр 7. В результате чего производится очередное обращение к блоку 8.

В варианте П из блока 8 считывается информация в триггеры 9-11,регистры

12-14,содержащая нули за исключением разряда, которому соответствует триггер

9: С Т9 ) = 1.Единичное состояние триг-гера 9 указывает на синтаксическую ошибку в анализируемой строке. По сигналу с единичного выхода триггера

9.производится следующая последовательность действий: на выходе 36 устройства появляется сигнал, указывающий на ошибку в анализируемой строке; триггер 18 через элемент ИЛИ 28 и формирователь 17 импульсов устанав- 25 ливается в нулевое состояние и сигнал с выхода элемента ИЛИ 30 обнуляет регистры 1 и 7, блоки регистров 3 и 16.

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

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

99 Ь что в данном элементе таблицы разбс ра, хранящейся в блоке 8, записан

"сдвиг". При этом разрешается запис1 очередного символа строки по входу

34 устройства через блок 2 элементов И в регистр i производится сдвиг блока регистров 3 вверх (по схеме), соответственно, через блоки 5 и 4, и триггер 18 через элемент

ИЛИ 28 и формирователь 17 импульсов устанавливается в нуль.

В варианте 1У из блока 8 считывается нулевая информация за исключением разряда, которому соответствует триггер 11: (T 11 ) = 1. При этом триггер 18 через элемент ИЛИ 28, формирователь 17 импульсов устанавливается в нулевое состояние; на выходе 32 устройства появляется сигнал, свидетельствующий об успешном окончании разбора входной строки: через элемент ИЛИ 30 обнуляются регистры

1, 7 и 3; на входах 35 устройства появляется множество кодов номеров правил разобранной строки, поступивших из регистров 16 через блоки 19 элементов И.Ha этом работа устройства заканчивается.

1196899

Составитель С.Бурухин

Техред Л.Мартяшова

Корректор Л.Пилипенко

Редактор Н.Бобкова

Заказ 7566/49

Филиал ППП "Патент", r.Ужгород, ул. Проектная, 4

Тирам 709 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.,4/5