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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советскнк

Соцнааистическик

Республик о .669356 (61} Дополнительное к авт. сеид-sy(22) Заявлено 2901.76(2)) 2318032/18-24 с присоединением заявки Hо(23) Приоритет(5 )м К 2

G 06 F ll/00

Государственный комитет

СССР но делам изобретений и открытий

Опубликовано. 2506.79. Бюллетень Мо 2 3

Дата опубликования описания 250679 (53) УДХ 681.3 (088.8) (72) Авторы изобретения

Е.Л. Ющенко, Г.Е. Цейтлин и Л.И. Довгополая

Ордена Ленина Институт кибернетики Украинской ССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО КОНТРОЛЯ

ПРОГРАИИ

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

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

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

Наиболее близко к предлагаемому изобретению по технической сущности устройство для синтаксического контроля программ, содержащее первый регистр текущего символа, блок долговременной памяти, первый регистр адреса, первый блок оперативной памяти, блок сравнения, регистр синтерма, причем первый и второй выходы блока долговременной памяти соединены соответственно с входом регистра синтерма и с входом первого блока оперативной памяти, первый и второй выходы которого соединены соответственно с первым входом блока сравнения и с первым входом первого регистра адреса, выход регистра синтерма соединен вторым входом первого ре истра адреса, первый выход которого соединен с первым входом блока долговременной памяти (2).

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

Цель изобретения — повышение быстродействия.

Это достигается тем, что в устройство введены первый и второй счетчики, второй блок оперативной памяти, второй регистр текущего символа, втоой регистр адреса, первый и второй локи синхронизации, причем первый, второй и третий выходы первого блока синхронизации соединены соответственно входом первого регистра текущего символа, вторым входом блока сравнения и с первым входом второго блока синхронизации, первый и второй выходы которого соединены соответственно с входом второго регистра текущего символа и с первым входом второ-15 го блока оперативной памяти, выход второго регистра текущего символа соединен с первым входом второго счетчика, первый и второй выходы которого соединены соответственно с первым входом первого блока синхронизации и с вторым входом блока долговременной памяти, третий и четвертый выходы блока долговременной памяти соединены. соответственна с вторым входом второго блока оперативной памяти и с первым входом второго регистра

ro соединены соответственно с третьим входом блока долговременной памяти и с в торым входом второго блока синхронизации„ первый, второй и третий выходы второго блока оперативной памяти соединены соответствен На чертеже дана структурная схема устройства для синтаксического контроля йрограмм.

Она состоит их двух процессоров

Р н обладающих общим полем па" мяти Z, В состав процессора Р вхо1 дят первый регистр 1 текущего символа, регистр 2 синтерма, первый регистр 3 адреса, первый счетчик 4, первый блок 5 оперативной памяти (функционирующий в режиме магазина), первый блок 6 синхронизации, блок 7 рой блок 8 синхронизации, второй сЧетчик 9, второй блок 10 оперативной памяти (функционирующий в режи669356

3 ме магазина> и блок 11 долговременной памяти, сбдержащий массив G правил грамматики данного языка и таблицу W синтермов. Процессор. Р содержит второй регистр 12 текущего символа, второй регистр 13 адреса.

5 8 устройстве для синтаксического контроля программ первый, второй и третий выходы первого блока 6 синхронизации соединены соответственно с входом первого регистра 1 текущего

)0 символа, с вторым входом блока 7 сравнения и с первым входом второго блока 8 синхронизации, первый и второй выходы которого соединены соответственно с входом второго регистра 12 текущего символа и с первым входом второго блока 10 оперативной памяти, выход второго регистра 12 текущего символа соединен с первым входом второго счетчика 9, первый и второй выходы которого соединены соответственно с первым входом первого блока 6 синхронизации и с вторым входом блока 11 долговременной памяти, первый и второй выходй блока 11 долговременной памяти соединены соответственно с входом регистра 2 синтерма и с входом первого блока 5 оперативной памяти, перадреса, пеРвый и втоРой выхоДы котоРо- вый и втоРой выходы которого соединены соответственно с первым входом блока 7 сравнения и с первым входом первого регистра 3 адреса, выход регистра 2 синтерма соединен с вторым входом первого регистра 3 адреса, первый выход которого соединен с перно с третьим входом блока сравнения, вым входом блока долговременной памяс вторым входом второго счетчика и 35 ти, третий и четвертый выходы блос вторым входом второго регистра ад- ка 11 долговременной памяти соединереса, второй выход первого регистра ны соответственно с вторым входом адресФ :соединен с вторым входом пер- второго блока 10 оперативной памяти вого блока синхронизации, выход пер- и с первым входом второго регистра 13 ,вого регистра входного символа сое- 40 адреса, первый и второй выходы кодинен с входом первого счетчика, торого соединены соответственно с первый и второй выходы которого сое- тРетьим входом блока 11 долговремендинены с третьим входом первого бло- Не> памяти и с вторым входом второго ка синхронизации и с четвертым вхо- блока 8 синхронизации, первый, втодом блока долговременной памяти, 45 рой и третий выходы второго блока 10 четвертый вход первого блока синх- оперативной памяти соединены соответронизации и.третий вход второго бло- ственно с третьим входом блока 7 сравка синхронизации являются соответст- нения со втоРым входом второго счетвенно первым и вторым входом устрой- чика 9 и с вторым входом второго рества. гистра 13 адреса, второй выход первоФ го регистра 3 адреса соединен с вторым входом первого блока 6 синхронизации, выход: первого регистра 1, текущего символа соединен с входом первого счетчика 4, первый и второй вы55 ходы которого соединены с третьим входом первого блока 6 синхронизации и с четвертым входом блока 11 долговременной памяти, четвертый вход пер-" вого блока 6 синхронизации .и .третий

60 вход второго блока 8 синхронизации asляются соответственно первым и вторым входом устройства. сравнения. Общая память Е содержит вто" Грамматика языка записана в долговременную память в виде двух массивов: G — массив правил и И-таблица синтермов, Иассив G разбит на некота.

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

Б 6 6 в блоке долговременной памяти, состоящее из трех частей 2 = 8ыф, где S — начальный синтерм; а> - либо пусто, либо последовательность метапеременных и ".интермов, начинающаяся метапеременной; 4 — метка подмассива, к которому относится данное правило.

Таблица И задает соответствия между термами-основными символами языка — и синтермами, используемыми для придания компактности записи его грамматики и повышения быстродействия процесса контроля.

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

Пусть в начале очередного цикла взаимодействия процессоров Р1 и Рр содержимое первого и второго блоков

5 и 10 оперативной памяти равно соответственно m, щ, а содержимое первого и второго счетчиков 4 и 9 равно соответственно В< и Е, где

В, (Ю ) — количество символов входной программы уже обработанных процессором Р (Р ) в направлении слева направо (справа налево); содержимое второго блока 8 синхронизации равно нулю; содержимое первого регистра 3 адреса равноф, где ф — метка начала подмассива G, которая в начале любого цикла должна совпадать с метапеременной, содержащейся в вершине второго блока 10 оперативной памяти; содержимое второго регистра 13 адреса равно r, где r - адрес последнего слова в массиве G.

Начиная свой цикл работы, процессор Р, включает первый блок 6 синхронизации для проверки неравенства п (1С4+С1)) К (1) где С<. (C ) — содержймое первого (второго) счетчика; n — длина входной программы К - коэффициент синхронизации, зависящий от грамматики языка и скорости. обработки символов входной программы процессора Р и

Р .

Если имеется неравенство (1),то в первый регистр 1 текущего символа засыпается очередной слева символ а входной программы, содержимое первого счетчика 4 увеличивается на единицу, Далее осуществляется поиск по таблице N синтерма з;, соответствующего символу а ., и засылка этого синтерма в регистр 2 синтерма. Затем при помощи первого регистра адреса .осуществляется просмотр подмассиваф до нахождения слова Z = s мэу такогО, что s-s, если подобное слово отс) тствует, то выдается информация СОШ о наличии синтаксической ошибки. После нахождения слова Е из первого блока 5 оперативной памяти (иэ его вершины) стирается код ф и B первый блок 5 оперативной памяти по5 символьно спРава налево засылается последовательность 43

)0 следующем шаге контроля в направлении слева направо. Это завершает даниый цикл работы процессора P .

Совместно с процессором P процес-1 сор Р> обрабатывает Входную програм-му спРава налево. Вначале очередного цикла работы процессор Р, проверяет содержимое второго блока 8 синхронизации. Если оно равно нулю, то во второй регистр 12 текущего символа поступает очередной (в направлении справа налево) символ а входной программы.

Х .Содержимое второго счетчика 9 увеличивается на единицу. Осущестгляется поиск по таблице N соответствующего синтерма з., который заносится во

25 второй блок 10 оперативной памяти.

Затем, при помощи второго регистра 13 адреса организуется поиск по массиву

G ñëîâà .Е=зябтакого,, что последовательность W = SW совпадает с содер30 жимым верхних ячеек второго блока 10 оперативной памяти. Если слово 2 не обнаружено, то во второй регистр 13 адреса засылается r и описанная процедура повторяется вновь, При .нали35 чии слова 2 во втором блоке 10 оперативной памяти стирается последовательность Ж и засыпается метапеременная 6, Затем после засылки z во второй регистр 13 адреса процессор Р, 4 снова обра ается ко второму блоку 8 синхронизации и т.д. В случае, когда на некоторой фазе контроля содержимое второго блока 8 синхронизации равно единице,,в верхних ячейках второго блока 10 оперативной памяти сти45 раются все синтермы до появления в ней некоторой метапеременной. При этом содержимое второго счетчика 9 уменьшается на соответствующее количество единицы, после чего процессор

50 заканчивает свою работу.

В случае, когда на первой фазе

РаботЫ процессора Р неравенство (1) не выполняется, во второй блок 8 синхронизации засыпается единица и

55 проверяется равенство

n-(С + C ) = 0 (2)

Процессор Р, продолжает обработку входной программы слева направо, пока не выполнится равенство (2);

60 Затем осуществляется сравнение содержимых первого и второго блоков 5 и 10 оперативной памяти. Если они равны„ то процесс синтаксического контроля завершается успешно, в про тивном случае выдается информация СО(1 .

669356

B начальном состоянии предлагаемого устройства содержимое первого

4 и второго 9 счетчиков равно нулю, содержимое второго блока 8 синхронизации также равно нулю, второй блок

10 оперативной памяти пуст, содержимое первого блока 5 оперативной памяти и первого регистра 3 адреса равно о-, где 6 - метка начального подмассива в G соответствующего аксиоме грамматики данного языка; содержимое второго регистра 13 адре- l0 са равно r. При этом процессор Р> начинает Функционировать с некоторой задержкой 8, которая равна времени проверки истинности неравенства (1) и засылки во второй блок 8 синхрони- 15 эации единицы. Далее, процессоры Р, и Р2 Функционируют параллельно.

Предлагаемое устройство Синта сйческого контроля программ обеспечивает эФФективный синтаксический конт- 0 роль, ориентированный на многопроцессорный режим работы, что достигается путем органиЭации параллельных встречных процессов обработки симВОлов входной программы и средств их синхронизации. Предлагаемое устройст- во может быть использовано при скемной интерпретации систем математического обеспечения для многопроцессорных вычислительных комплексов, что позволдт повысить их эФФективность © при решении задач обработки данных, в частности, в диалоговых системах коллективного пользования при поиске и исправлении синтаксических ошибок.

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

Устфойство для синтаксического контроля программ, содержащее первый 40 регистр текущего символа, блок дол- . говременной памяти, первый регистр адреса, первый блок оперативной памяти, блок сравнения, регистр синтерма, причем первый H втоРой выходы бло- 45 ка долговременной памяти соединены соответственно с входом регистра синтерма и с входом первого блока оперативной памяти, первый и второй выходы которого соединены соответственно с первым входом блока. сравнения и с первым входом первого регистра адреса, выход регистра синтерма соединен с вторым входом первого регистра адреса, первый выход которого соединен с первым входом блока долговременной памяти, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройство содержит первый и второй счетчики, второй блок оперативной па)мяти, второй, регистр текущего символа, второй регистр адреса, первый и второй блоки синхронизации, причем. первый, второй и третий выходы первого блока синхронизации соединены соответственно с входом первого регистра текущего символа, с вторым входом блока сравнения и с первым входом второго блока синхронизации, первый и второй выходы которого соединены соответственно с входом второго Регистра текущего символа и с первым входом второго блока оперативной памяти, выход второго регистра текуще о символа соединен с первым входом втюрого счетчика, первый и второй выходы которого соединены соответственно с первым входом первого блока синхронизации и с вторым входом блока долговременной памяти, третий и четвертый выходы блока долговременной памяти соединены соответственно с вторым входом втцрого. блока оперативной памяти и с первым входом второго регистра адреса., первый и второй выходы которого соединены соответственно с третьим входом блока долговременной памяти и .с вторым входом второго блока синхронизацйи, первый, второй и третий выходы второго блока оперативной памяти соединен.- соответственно с третьим входом блока сравнения,с вторым входом второго счетчика и с вторым входом второго регистра адреса, второй выход первого регистра адреса соединен с вторым azoдом первого блока синхронизации, выход первого регистра входного символа соединен с входом первого счетчика, первый и второй выходы которого соединены с третьим входом первого блока синхронизации и с четвертым входом блока долговременной памяти, четвертый вход первого блока синхронизации и третий вход второго блока синхронизации являются соответственно первым и вторым входом устройства.

Источники инФормации, принятые во внимание при экспертизе

1. Глушков В.И. и Барабанбв A.A. и др. Вычислительные машины с развитыми системами интерпретации. Киев;

"Наукова думка", 1970.

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

9 333558 кл. G 06 Р 11/00, 06 ° 03.70.

669356

Составитель H Сигалов

Редактор Л. Гребенникова Гелред М. Хелемеш Корректор Н. Стец

Эакав 365S/40 Тираж 779 Подписное

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

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

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