Патент ссср 333558

 

О"П-И- C- А Н И Е

ИЗОБРЕТЕН ИЯ

333558

Союз Советских

Социалистических

Республик зт АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависнхтос от piiт. свндетс IüñTÂ2 ¹â€”

М.Кл. С 06f 11/00

G 06f l5/48

Заявлено 06.!11.1970 (№ 1411398/18-24) с присоединением заявки ч

Приоритет—

Опубликовано 21.111.1972. Бюллетень ¹ 11 комитет по делам изобретений и откр!,!тий при Совете Министров

СССР

УДК 681.327(088.8) Дата опубликования описания 7Х!.1972

Автc;p изобретения

И. В, Вельбицкий

Институт кибернетики AH Украинской ССР ьявнтель э., 1

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

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

Недостатком известных устройств является их сложность и низкое быстродействие.

Предлагаемое устройство отличается тем, !б что оно содержит регистр типа синтерма и логическую схему выбора, подключенную к выходному регистру долговремеспюй памяти, вспомогательному регистру типа синтерма, который подключен к выходному регистру и ре- 20 гистру типа синтерма, подключенному к выходному регистру долговременной памяти.

Это упрощает устройство, уменьшает его габариты и увелгсвает быстродеиствие.

На фиг. изображена блок-схема предла- 25 гаемого устройства; на фиг. 2 приведены

WR-массивы грамматики алгоритмического языка, Устройство состоит из входного регистра 1, вспомогательного регистра 2, схемы сравне- 30

2 ння 3, выходного регистра 4, долговременной памяти 5, регистра адреса 6, стековой памяти 7, регистра 8 типа сннтерма и логической схемы 9 выбора синтерма соответствующего типа.

Грамматика языка записана в долговременной памяти устройства в виде двух массивов W u R. В массиве 1V записана таблица соответствия термов (ocHQBIIblx символов языка) синтермам. Под синтермом понимается символ, которым обозначается группа синтаксически эквивалентных символов (состоящая быть может нз одного символа) языка.

Например, в языке АЛГОЛ-60 спнтерм V обозначает группу синтаксически эквивалентных символов: V-.==

Однако в практических языках, как Ilpaвило, одпому терму соответствует несколько сиптермов (несколько типов синтермов) в зависимости от того, в какой синтаксической конструкции используется данный терм. Например, в языке АЛГОЛ-60 символам +, Х после ограничителя соп1птеп! соответствует один синтерм — пусть S, тем же сихгволом в арифметическом выражении соответствует два разных синтерма +, Х.

В долговременной памяти каждому слову массива W соответствует терм. В слове записаны все соответствующие ему синтермы.

Каждое слово условно разбито на т частей

УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО КОНТРОЛЯ

ЛРОГРАММ

333558

L по ()одф) разрядов, где т: — = — макси(10Я2 | ) мальное число сннтермов, соответствующее одному терму языка; L — число разрядов в слове долговременнои памяти; 1; — общее число различных синтермов для заданного языка. Длина массива W равна и, где n — число термов в языке. Таким образом, в долговременной памяти массив В занимает гп (log>/г) и разрядов.

В массиве записаны правила грамматики языка. Весь R-массив условно разбит на некоторые подмассивы, в каждом из которых расположено несколько (некоторое число элементов массива). Каждому элементу Я-массива соответствует правило грамматики языка.

Каждый элемент массива занимает одно слово долговременной памяти и состоит нз восьми частей:

R(-- код синтерма языка (занимает (1одф) разрядов);

R2 —,признак записи в стековую память (занимает 1 разряд);

РЗ вЂ” признак чтения из стековой памяти (занимает 1 разряд);

R4 — признак окончания некоторого подмассива (занимает 1 разряд);

R5 — признак того, что синтерм Rl этого элемента подмассива может быть последним в программе, записанной на данном алгоритмическом языке (занимает 1 разряд);

1х6 — адрес начала, соответствующего данному элементу подмассива грамматики (занимает в общем случае ()og N) разрядов, где N — длина всего Я-массива);

R7 — адрес соответствующего данному элементу, элемента массива Я, у которого в R2 стоит признак записи в стековую память. R7 — пусто, если в РЗ нет признака чтения нз стековой памяти (в общем случае R7 также занимает (log>N) р аз р ядов );

R8 — код типа синтерма (номер по порядку синтерма в элементе W-массива), соответствующий всем расположенным ниже элементам подмассива Я-грамматики; занимает (1од|п) разрядов.

Таким образом, в общем .случае элемент

R-массива грамматики языка занимает ((log,k)+ 4+2(log N)+(log>m)) разрядов.

В долговременной памяти (ДП) устройства эта грамматика, очевидно, занимает m ((одоп + N((log> e)+4+2(log>N) + ((ogham))

668 разрядов.

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

В исходном состоянии стековая память свободна, на регистре 8 типа синтерма записан код первого типа синтерма в W-массиве, на регистре адреса б — адрес начального подмассива Я-грамматики языка. В этом подмассиве в Rl записаны коды синтермов, которые могут быть первыми в программе данного алгоритмического языка.

Первый символ проверяемой программы записывается на входной регистр 1. Затем из массива W долговременной памяти по адресу на регистре 1 считываются на выходной регистр 4 все соответствующие данному символу синтермы. По коду на регистре 8 сломощью логической схемы 9 выоирается один из синтермов (в данном случае первый) и записывается на вспомогательный регистр 2. После этого из R-массива долговременной памяти по адресу на регистре б считывается первый элемент начального подмассива и записывается на выходной регистр 4. Затем производится сравнение кода на выходном регистре с кодом текущего синтерма на регистре 2 с помощью схемы 3. Если указанные коды не сравнились, то к коду адреса на регистре б прибавляется едини|ца и считывается следующий элемент начального подмасснва. Действия продолжаются до элемента грамматики, у которого код

Rl на регистре 4 совпал с кодом на регистре 2, либо до элемента, у которого в R4 стоит признак конца подмассива. R первом случае код Я6 на выходном регистре переписывается на регистр б, тем самым на регистр б записывается адрес следующего подмассива, у которого в Rl записаны коды синтермов, которые могут следовать за проверенным символом.

Во втором случае, если код Rl на регнстзо ре 4 не совпал с кодом на регистре 2, а в R4 стоит признак конца подмассива, то вырабатывается сигнал СОШ (синтаксической ошибки), так как,ни один из элементов Rl в начальном подмассиве .не сравнился с первым

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

40 Если первый синтерм проверяемой программы, полученный с помощью таблицы

W-регистра типа и логической схемы выбора синтерма, не сравнился IHH с одним из синтермов в Rl первого подмассива, то значит он

45 QIIIHoo tHO написан IlcpBbIM To есть сННТВКсН чески неверно.

Если сигнал СОШ не выработался, то определяется тип синтерма следующего символа проверяемого предложения языка. Для этого по адресу на репистре б из долговременной памяти 5 считывается на выходной регистр 4 первый элемент текущего подмассива, у которого в R8 записан тип синтерма кодов Rl

55 для всего подмассива. Код R8 с регистра 4 переписывается на регистр 8. Тем самым определен тип синтерма следующего символа проверяемого предложения языка. Затем этот символ вызывается и записывается на регистр 1.

По коду этого символа как по адресу считываются из ДП и записываются на выходной регистр 4 все соответствующие данному символу синтермы. По коду на регистре 8 с помощью логической схемы 9 вырабатывается

333558

5 один соответствующий этому символу синтерм и записывается на вспомогательный регистр 2.

Затем на выходной регистр 4 по адресу на регистре 6 счптывшотся элементы Я-массива, 1 1 коды которых сравниваются с кодом па регистре 2 и т. д. аналогично выше описываемому.

Ъ казанные действия соответствуют элементам R-массива ДО, у которы отсутствуют признаки R2, ЯЗ.

В случае, если элемент R-массива на регистре 2, у которого код Rl совпал с кодом на регистре 2, имеет в Р2 признак записи в стековую память, то записи кода Л, б на регистр

6 предшествует запись текущего значения «ода на регистре 6 в стековую память, В остальном действия не отличаются or вышеописанныхх.

В случае, если регистр 4, у которого код

1 совпал с кодом на регистре 2, имеет в ЯЗ признак, то записи кода Rh на регистр 6 предшествует сравнение кода на вершине стековой памяти с кодом Р7 на выходном регистре 4. Если эти коды совпали, то содержимое верхней ячейки стека удаляется, и произ,водятся описанные выше действия по переписи кода Яб на регистр 6 и далее определение типа синтерма следующего символа проверяемого предложения. Если эти коды не совпали, то к содержимому регистру б прибавляется единица и описанные выше действия производятся с новым, следующим элементом данного подмассива R-грамматики.

В конце проверки последний синтерм проверяемой программы обязательно должен сравниться с таким элементом соответствуюб щего подмассива Р-грамматики, у которого в

R5 стоит признак, что данный синтерм Rl на регистре 4 и регистре 2 может быть последним в программе данного алгоритмического языка.

В противном случае проверяемая программа считается педописаннои, что соответствует также условию выработки сигнала синтаксической ошибки.

Таким образом, из приведенного описания

10 процедуры синтаксического контроля нетрудно убедиться, что первыми синтермами в предложениях данного алгоритмического языка могут быть синтермы а либо /, вторым после / — d, далее а, либо S и т. д., а также что д предложение amhakc синтаксически правильно, а предложение amkahc синтаксически неверно — при проверке пятого символа этого предложения вырабатывается сигнал СОШ.

20 Предмет изобретения

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

333558

О 1 г

16

21

Фиг 2

Составитель В. Богатырев

Техред 3. Таранеико Корректор Т. Китаева

Редактор Б. Нанкина

Заказ 1958 Изд. № 440 Тираж 500 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий ири Совете Министров СССР

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

Загорская типография

m а д

Р

d

«1 с

2

5 ф

5 б

7 д

1О

11

12

1б

17

1д

19

2О

21

22

Л.

2б

27

2D

29

Л

32 ь|5

54л я

Р с

tt л а

Р

Х х х

Х а

Ь о

1

1 о

О

2

О

О

0 д

П