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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советскнк Соцнааистическик Республик(6) Дополнительное к авт, сеид-ау(22) Заявлено 2901.76(21) 2318032/18-24с присоединением заявки Ио(23) Приоритет(5 е)м К 2 О 06 Г 11/00 Государственный комитет СССР но дедам изобретений и открытий(72) Авторы изобретения Е.Л. Ющенко, Г.Е. Цейтлин и Л.И. Довгополая Ордена Ленина Институт кибернетики Украинской ССР(54) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО КОНТРОЛЯ ПРОГРАИИИзобретение касается структурной интерпретации алгоритмических языков в связи с конструированием систем математического обеспечения, ориентированных на многопроцессорные вычислительные комплексы, Оно предназначено для проверки правильности последовательности символов (программы) некоторого заданного совокупностью правил (грамматикой) языка программирования.Известные устройства для синтаксического контроля программ со струк-. турной интерпретацией языков высокого уровня обладают той особенностью, 15 что синтактический контроль входных программ в них осуществляется путем левосторонней посимвольной обработки входного текста с использованием синтаксических таблиц, стековой памяти, 20 польской записи в качестве промежуточного языка при трансляции 1). Недостатки таких устройств - однопроцессорный режим:работы.и отсутствие. . средств для параллельной обработки символов входной программы, что существенно отражается на быстродействии устройств.Наиболее близко к предлагаемомуизобретению по технической сущности устройство для синтаксического контроля программ, содержащее первый регистр текущего символа, блок долговременной памяти, первый регистр адреса, первый блок оперативной памяти, блок сравнений, регистр синтерма, причем первый и второй выходы блока долговременной памяти соединены соответственно с входом регистра синтерма и с входом первого блока оперативной памяти, первый и второй выходы которого соединены соответственно с первым входом блока сравнения и с первым входом первого регистра адреса, выход регистра синтерма соединен вторым входом первого резистра адреса, первый выход которого соединен с первым входом блока долговременной памяти (2).Однако в таком устройстве посимвольная обработка текста слева направо ввиду отсутствия средств, допускающих параллельный контроль символов входной программы, ограничивает, эффективность процесса синтаксического .контроля и делает невозможным использование описанной схемы при конструировании систем математического обеспечения, ориентированных на многопроцессорные вычислительные комплексы.Цель изобретения - повышениебыстродействия,Это достигается тем, что в устройство введены первый и второй счетчики, второй блок оперативной памяти,второй регистр текущего символа, втоой регистр адреса, первый и второй локи синхронизации, причем первый, второй и третий выходы первого блока синхронизации соединены соответственно входом первого регистра текущего символа, вторым входом блокасравнения и с первым входом второго блока синхронизации, первый и второй выходы которого соединены соответственно с входом второго регистра текущего символа и с первым входом второ го блока оперативной памяти, выходвторого регистра текущего символа соединен с первым входом второго счетчика, первый и второй выходы которого соединены соответственно с первым входом первого блока синхронизациии с вторым входом блока долговременной памяти, третий и четвертый выходыблока долговременной памяти соединены. соответственно с вторым входомвторого блока оперативной памяти ис первым входом второго регистра го соединены соответственно с третьим входом блока долговременной памяти и с вторым входом второго блока синхронизации первый, второй итретий выходы второго блока оперативной памяти соединены еоответствен На чертеже дана структурная схема устройства для синтаксического контроля йрограмм.Она состоит их двух процессоров Р и Рн обладающих общим полем па" мяти Е, В состав процессора Р вхо 1 дят первый регистр 1 текущего символа, регистр 2 синтерма, первый регистр 3 адреса, первый счетчик 4, первый блок 5 оперативной памяти (функционирующий в режиме магазина), первый блок 6 синхронизации, блок 7 рой блок 8 синхронизации, второй СЧетчик 9, второй блок 10 оперативной памяти (Функционирующий в режи 6693563ме магазина) и блок 11 долговременнойпамяти, сбдержащий массив 6 правилграмматики данного языка и таблицу Юсинтермов. Процессор.Р содержит второй регистр 12 текущего символа, второй регистр 13 адреса,5 В устройстве для синтаксическогоконтроля программ первый, второй итретий выходы первого блока 6 синхронизации соединены соответственно свходом первого регистра 1 текущего10 символа, с вторым входом блока 7 сравнения и с первым входом второго блока 8 синхронизации, первый и второйвыходы которого соединены соответственно с входом второго регистра 12текущего символа и с первым входомвторого блока 10 оперативной памяти,выход второго регистра 12 текущегосимвола соединен с первым входом второго счетчика 9, первый и второй выходы которого соединены соответственнос первым входом первого блока 6 синхронизации и с вторым входом блока 11долговременной памяти, первый и второйвыходй блока 11 долговременной памяти соединены соответственно с Входомрегистра 2 синтерма и с входом первого блока 5 оперативной памяти, перадреса, первый и второй выходы которо- вый и втоРой выходы котоРого соединены соответственно с первым входомблока 7 сравнения и с первым входомпервого регистра 3 адреса, выход регистра 2 синтерма соединен с вторымвходом первого регистра 3 адреса,первый выход которого соединен с перно с третьим входом блока сравнения, вым входом блока долговременной памяс вторым входом второго счетчика и 35 ти, третий и четвертый выходы блос вторым входом второго регистра ад- ка 11 долговременной памяти соединереса, второй выход первого регистра ны соответственно с вторым входомадресФ :соединен с вторым входом пер- второго блока 10 оперативной памятивого блока синхронизации, выход пер- и с первым входом второго регистра 13,вого регистра входного символа сое адреса, первый и второй выходы кодинен с входом первого счетчика, торого соединены соответственно спервый и второй выходы которого сое- третьим входом блока 11 долговремендинены с третьим входом первого бло- ной памяти и с вторым входом второгока синхронизации и с четвертым вхо- блока 8 синхронизации, первый, втодом блока долговременной памяти, 45 рой и третий выходы второго блока 10четвертый вход первого блока синх- оперативной памяти соединены соответронизации и третий вход второго бло- ственно с третьим входом блока 7 сравка синхронизации являются соответст- нения,со вторым входом второго счетвенно первым и вторым входом устрой- чика 9 и с вторым входом второго рества гистра 13 адреса, второй выход первоФ го регистра 3 адреса соединен с вторым входом первого блока 6 синхронизации, выход: первого регистра 1, текущего символа соединен с входом первого счетчика 4, первый и второй вы 55 ходы которого соединены с третьимвходом первого блока 6 синхронизациии с четвертым входом блока 11 долго"временной памяти, четвертый вход пер-"вого блока 6 синхронизации .и .третий60 вход второго блока 8 синхронизации являются соответственно первым и вторымвходом устройства.сравнения, Общая память 2 содержит вто" Грамматика языка записана в долго. временную память в виде двух массивов: 6 - массив правил и И-таблицасинтермов, Иассив С разбит на некоторое количество подмассивов, каждый иэ которых объединяет в себе правила, относящиеся к одной и той же метапеременной; метапеременная используется в дальнейшем также в качестве меток начал соответствующих подмассивов правил. Каждому грамматическому правилу соответствует слово Е 6 С в блоке долговременной памяти, состоящее из трех частей Е = Зыф, где Я - начальный синтерм; И - либо пусто, либо последовательность метапеременных и ".интермов, начинающаяся метапеременной; )" - метка подмассива, к которому относится данное правило.Таблица И задает соответствия между термами-основными символами языка - и синтермами, используемыми для придания компактности записи его грамматики и повышения быстродействия процесса контроля. Устройство работает следующим образом.Пусть в начале очередного цикла взаимодействия процессоров Р 1 и Р содержимое первого и второго блоков 5 и 10 оперативной памяти равно соответственно ю, в , а содержимое первого и второго счетчиков 4 и 9 равно соответственно В и 2, где В, ( 2 ) - количество символов входной программы уже обработанных процессором Р (Р) в направлении слева направо (справа налево); содержимое второго блока 8 синхронизации равно нулю; содержимое первого регистра 3 адреса равноф, где Ф - метка начала подмассива 6, которая в начале любого цикла должна совпадать с метапеременной, содержащейся в вершине второго блока 10 бперативной памяти; содержимое второго регистра 13 адреса равно г,.где г - адрес последнего слова в массиве 6.Начиная свой цикл работы, процессор Р, включает первый блок 6 синхронизации для проверки неравенстваи-(С + С ) ) К (1) где С (С) - содержймое первого (второго) счетчика; и - длина входной программы 1 К - коэффициент синхронизации, зависящий от грамматики языка и скорости обработки символов входной программы процессора Р иЕсли имеется неравенство (1),то в первый регистр 1 текущего символа засылается очередной слева символ а входной программы, содержимое первого счетчика 4 увеличивается на едини" цу, Далее осуществляется поиск по таблице Х синтерма з;, соответствующего символу а., и засылка этого синтерма в регистр 2 синтерма. Затем при помощи первого регистра адреса .осуществляется просмотр подмассива до нахождения слова Е = я му та- когО, что э=в , если подобное слово отс) тствует, то выдается информация"СОШо наличии синтаксической ошибки. После нахождения слова Е из первого блока 5 оперативной памяти (иэего вершины) стирается код ф и впервый блок 5 оперативной памяти по символьно справа налево засылаетсяпоследовательность ИСЧ, Наконец,в первый блок 5 оперативной памятизасылается код Г- метка подмассиваправил-преемников, применимых на р следующем шаге контроля в направлении слева направо. Это завершаетданиый цикл работы процессора Р,Совместно с процессором Р процес сор Р 2 обрабатывает Входную програм-.му справа налево. Вначале очередногоцикла работы процессор Р, проверяетсодержимое второго блока 8 синхронизации. Если оно равно нулю, то во второй регистр 12 текущего символа поступает очередной (в направлении справаналево) символ а входной программы.Содержимое второго счетчика 9 увеличивается на единицу. Осущестгляетсяпоиск по таблице И соответствующегосинтерма з , который заносится во 25 второй блок 10 оперативной памяти.Затем, при помощи второго регистра 13адреса организуется поиск по массиву6 слова .Е=зябтакого что последовательность Х = ЯМ совпадает с содер" 30 жимым верхних ячеек второго блока 10оперативной памяти. Если слово Е необнаружено, то во второй регистр 13адреса засылается г и описанная процедура повторяется вновь, При .нали чик слова Е во втором блоке 10 оперативной памяти стирается последовательность Ж и засылается метапеременная 6 , Затем после засылки г вовторой регистр 13 адреса процессор Р 40 снова обращается ко второму блоку 8синхронизации и т.д. В случае, когдана некоторой фазе контроля содержимое второго блока 8 синхронизацииравно единицев верхних ячейках второго блока 10 оперативной памяти сти раются все синтермы до появления вней некоторой метапеременной. Приэтом содержимое второго счетчика 9уменьшается на соответствующее количество единицы, после чего процессор 50 заканчивает свою работу.В случае, когдЪ на первой фазеработЫ процессора Р неравенство(1) не выполняется, во второй блок 8синхронизации засылается единица и 55 проверяется равенствои-( С +С) = 0 (2)Процессор Р, продолжает обработкувходной программы слева направо,пока не выполнится равенство (2);60 Затем осуществляется сравнениефсодержимых первого и второго блоков 5и 10 оперативной памяти. Если ониравны то процесс синтаксическогоконтроля завершается успешно, в противном случае выдается информация 65СО(1В начальном состоянии предлагаемого устройства содержимое первого 4 и второго 9 счетчиков равно нулю, содержимое второго блока В синхронизации также равно нулю, второй блок 10 оперативной памяти пуст, содержимое первого блока 5 оперативной памяти и первого регистра 3 адреса равно а-, где б - метка начального подмассива в С, соответствующего аксиоме грамматики данного яэыка 1 содержимое второго регистра 13 адре- Ю са равно г, При этом процессор Р начинает Функционировать с некоторой задержкой 8 , которая равна времени проверки истинности неравенства (1) и засылки ва второй блок 8 синхрони эации единицы, Далее, процессоры Р, и Р 2 Функционируют параллельна.Предлагаемое устройство Синтасйческого контроля программ обеспечивает эФФективный синтаксический конт" 0 роль, ориентированный на многопроцессорный режим работы, что достигается путем органиЭации параллельных встречных процессов обработки симВалав входной программы и средств их синхронизации. Предлагаемое устройст- ф во может быть использовано при скемной интерпретации систем математического обеспечения для многопроцессорных вычислительных комплексов, что позволит повысить их эФФективнасть ЗО при решении задач обработки данных, в частности, в диалоговых системах коллективного пользования при поиске и .исправлении синтаксических ошибок.35 Формула изобретенияУстройства для синтаксического контроля программ, содержащее первый 40 регистр текущего символа, блок дол- . говременной памяти, первый регистр адреса, первый блок оперативной памяти, блок сравнения, регистр синтерма, причем пеРвый и втоРОЙ выходы блока долговременной памяти соединены соответственно с входом регистра синтерма и с входом первого блока оперативной Памяти, первый и второй выходы которого соединены соответственно с первым входом блока. сравнения и с первым входом первого регистраадреса, выход регистра синтерма соединен с вторым входом первого регистра адреса, первый выход которого соединен с первым входом блока долговременнойпамяти, а т л и ч а ю щ е е с я тем,что, с целью повышения быстродействияустройство содержит первый и второйсчетчики, второй блок оперативной памяти, второй, регистр текущего символа, второй регистр адреса, первый ивторой блоки синхронизации, причем.первый, второй и третий выходы первого блока синхронизации соединены соответственно с входом первого регистратекущего символа, с вторым входомблока сравнения и с первым входомвторого блока синхронизации, первыйи второй выходы которого соединенысоответственна с входом второго Регистра текущего символа и с первымвходом второго блока оперативной памяти, выход второго регистра текущего символа соединен с первым входомвтюрого счетчика, первый и второй выходы которого соединены соответственна с первым входом ерваго блока синхронизации и с вторым входом блокадолговременной памяти, третий и четвертый выходы блока долговременнойпамяти соединены соответственно свторим входом втцрого. блока оперативной памяти и с первым входам второгорегистра адреса., первый и второй выходи которого соединены соответственно с третьим входом блока долговременной памяти и с вторым входом второго блока синхранизацйи, первый,второй и третий выходы второго блокаоперативной памяти соединен. соответственно с третьим входом блока сравнения,с вторым входом второго счетчика и с вторым входом второго регистРа адреса, второй выход первого регистра адреса соединен с вторым входам первого блока синхронизации,выход первого регистра входного символа соединен с входом первого счетчика, первый и второй выходы которого соединены с третьим входом первого блока синхронизации и с четвертымвходом блока долговременной памяти,четвертый вход первого блока синхронизации и третий вход второго блока синхронизации являются соответственно первым и вторым входом устройства,Источники инФормации, принятые во внимание при экспертизе1. Глушков В.И. и Барабанбв А.А. и др. Вычисдительные машины с развитыми системами интерпретации. Киев; "Наукова думка", 1970.2. Авторское свидетельство СССР 9 33355 В, кл, С 06 Р 11/00, 0603.70.669356 Составитель Н. Сигалов енникова Техред М. Келемеш Корректор НРедак Эакв 36 Филиал ППП фПатентф, г. Ужгород, ул. Проектн 40 ПНИИПИ по де 113035Тираж 779 сударственного изобретений и осква, Ж, Ра Подписнокомитета СССРоткритийушская наб., д,