Устройство для синтаксического контроля программ Советский патент 1979 года по МПК G06F11/00 

Изобретение касается структурной интерпретации алгоритмических языко в связи с конструированием систем математического обеспечения, ориентированных на многопроцессорные вычислительные комплексы. Оно предназначено для проверки правильности пос ледовательности символов (программы некоторого заданного совокупностью правил (грамматикой) языка программирования. Известные устройства для синтакси ческого контроля программ со структурной интерпретацией языков высокого уровня обладают той особенностью что синтактический контроль входных программ в них осуществляется путем левосторонней посимвольной обработки входного текста с использованием син таксических таЬлиц, стековой пгиияти польской записи в качестве промежуточного языка при трансляции {Ц. Недостатки таких устройств - однопро цессорный режим работы и отсутствие средств для параллельной обработки символов входной программы, что существенно отра жается на быстродействии устройств. Наиболее близко к предлагаемому изобретению по технической сущности устройство для синтаксического контроля программ, содержащее первый регистр текущего символа, блок долговременной памяти, первый регистр адреса, первый блок оперативной памяти, блок сравнения, регистр синтерма, причем первый и второй выходы блока долговременной памяти соединены соответственно с входом регистра синтерма и с входом первого блока оперативной памяти, первый и второй выходы которого соединены соответственно с первым входом блока сравнения и с первым входом первого регистра адреса, выход регистра сичтерма соединен С вторым входом первого регистра адреса, первый выход которого соединен с первым входом блока долговременной памяти 2. Однако в таком устройстве посимвольная обработка текста слева направо ввиду отсутствиясредств, допускающих параллельный контроль символов входной программы, ограничивает эффективность процесса синтаксического контроля и делает невозможным использование описанной схемы при конструировании систем математического обеспечения, ориентированных на многопроцессорные вычислительные комплексы. Цель изобретения - повышение быстродействия. Это достигается тем, что в устрой ство введены первый и второй счетчики, второй блок оперативной памяти, второй регистр текущего символа, вто рой регистр адреса, первый и второй локи синхронизации, причем первый, второй и третий выходы первого блока синхронизации соединены соответст венно входом первого регистра текущего символа, вторым входом блока сравне ния и с первым входом второго бпока синхронизации, первый и второй выходы которого соединены соответст. венно с входом второго регистра теку щего символа и с первым входом второ iro блока оперативной памяти, выход второго регистра текущего символа , соединен с первым входом второго сче чика, первый и второй выходы которого соединены соответственно с первы м входом первого блока синхронизации и с вторым входом блока долговременн памяти, третий и четвертый выходы блока долговременной памяти соединены соответственно с вторым входом второго блока оперативной памяти и с первым входом второго регистра адреса, первый и второй выходы котор го соединены соответственно с третьим входом блока долговременной памяти и с вторым входом второго блока синхронизации, первый, второй и третий выходы второго блока оперативной памяти соединены соответствен но с третьим входом блока сравнения с вторым входом второго счетчика и с вторым входом второго регистра адреса, второй выход первого регистра адресу соединен с вторым входом первого блока синхронизации, выход пер,вого регистра входного символа соединен с входом первого счетчика, первый и второй выходы которого сое динены с третьим входом первого блока синхронизации и с четвертым входом блока долговременной памяти, четвертый вход первого блока синхронизации и-третий вход второго бло ка синхронизации являются соответствённо первым и вторым входом устрой ства. На чертеже дана структурная схема устройства для синтаксического контроля программ. Она состоит их двух процессоров Р и Р обладающих общим полем памяти Z. В состав процессора Pj входят первый регистр 1 текущего сим вола, регистр 2 синтерма, первый ре гистр 3 адреса, первый счетчик 4, первый, блок 5 оперативной памяти (функционирующий в режиме магазина) первый блок б синхронизации,блок 7 сравнения.Общая память Z содержит вт рой блек 8 синхронизации, второй с €етчик 9, ВТОРОЙ блок 10 оперативной памяти {функционирующий в режиме магазина) и блок 11 долговременной; памяти, содержащий массив G правил грамматики данного языка и таблицу W синтермов. Процессор Pj содержит второй регистр 12 текущего символа, второй регистр 13 адреса, В устройстве для синтаксического контроля программ первый, второй и третий выходы первого блока 6 синхронизации соединены соответственно с входом первого регистра 1 текущего символа, с вторым входом блока 7 сравнения и с первым входом второго блока 8 синхронизации, первый и второй выходы которого соединены соответственно с входом второго регистра 12 текущего символа и с первым входом второго блока 10 оперативной памяти, выход второго регистра 12 текущего символа соединен с первым входом второго счетчика 9, первый и второй выходы которого соединены соответственно с первым входом первого блока 6 синхронизации и с вторым входом блока 11 долговременной памяти, первый и второй выходи блока 11 долговременной памяти соединены соответственно с Входом регистра 2 синтерма и с входом первого блока 5 оперативной памяти, первый и второй выходы которого соединены соответственно с первым входом блока 7 сравнения и с первым входом первого регистра 3 адреса, выход регистра 2 синтерма соединен с вторым входом первого регистра 3 адреса, первый выход которого соединен с первым входом блока долговременной памяти, третий и четвертый выходы блока 11 долговременной памяти соединены соответствен«о с вторым входом второго блока 10 оперативной памяти и с первым входом второго регистра 13 адреса, первый и второй выходаз которого соединены соответственно с третьим входом блока 11 долговременной и с вторым входом второго блока 8 синхронизации, первый, второй и третий выходы второго блока 10 оперативной памяти соединены соответственно с третьим входом блока 7 сравнения, со вторым входом второго счетчика 9 и с вторым входом второго ре- гистра 13 адреса, второй выход первого регистра 3 адреса соединен с вторым входом первого блока б. синхрониз.ации, выход Первого регистра 1 / текущего символа соединен с входом первого счетчика 4, первый и второй вы-, ходы которого соединены с третьим входом первого блока 6 синхронизации и с четвертым входом блока 11 долговременной памяти, четвертый вход пер- вого блока б синхронизации и .третий вход второго блока 8 синхронизации являются соответственно первым и вторым входом устройства. Грамматика языка записана в долговременную память в виде двух массивов: G - массив провил и W-таблица синтермов. Массив G разбит на некото

рое количество подмассивоз, каждый из которых объединяет в себе правила, относящиеся к одной и той же метапёременнойJ метапеременная используется в дальнейшем также в качестве меток начал соответствующих подмассивов правил. Каждому грамматическому правилу соответствует слово Z € G в блоке долговременной памяти, состоящее из трех частей Z , где S- начальный синтерм; О - либо пусто, либо последовательность метапеременных и синтермов, начинающаяся метапеременной; ф - метка подмассива, к которому относится данное правило.

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

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

Пусть в начале очередного цикла взаимодействия процессоров Pj и Р содержимое первого и второго блоков 5 и 10 оперативной памяти равно соответственно mj, m.j, а содержимое первого и второго счетчиков 4 и 9 равно соответственно Е и Zi, где Е (Ej) - количество символов входной программы уже обработанных процессором Р (Pj) в направлении слева направо (справа налево); содержимое второго блока 8 синхронизации равно нулю; содержимое первого регистра 3 адреса равно ф, где ф - метка начала подмассива G, которая в начале любого цикла должна совпадать с метапеременной, содержащейся в вершине второго блока 10 (Оперативной памяти; содержимое второго регистра 13 адрес равно г,-где г - адрес последнего слова в массиве G.

Начиная свой цикл работы, процессор Р, включает первый блок 6 синхронизации для проверки неравенства

, n-(Ci + Cj) К, ( где С,-(С;) - содержимое первого (второго) счетчика; п - длина входной программы} К - коэффициент синхронизации, зависящий от грамматики языка и скорости обработки символов входной программы процессора Р, и

Р .

Если имеется неравенство (1),то в

первый регистр 1 текущего символа засылается очередной слева символ aj входной прогргиимы, содержимое первого счетчика 4 увеличивается на единицу. Далее осуществляется поиск по таблице W синтерма sj , соответствующего символу а|., и засылка этого синтерма в регистр 2 синтерма. Затем при помощи первого регистра адреса осуществляется присмотр подмассивац до нахо)рдения слова Z s шф такого, что , если подобное слово

отсутствует, то выдается информация СОШ о наличии синтаксической ошибки. После нахождения слова Z из первого блока 5 оперативной памяти (из его вершины) стирается код id(i и в первый блок 5 оперативной памяти посимвольно справа налево засылается последовательность UJaTV . Наконец, в первый блок 5 оперативной памяти засылается код Т- метка подмассива правил-преемников, применимых на

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

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

налево) символ а:, входной программы. Содержимое второго счетчика 9 увеличивается на единицу. Осущестгляется поиск по таблице W соответствующего синтерма s|, который заносится во

5 второй блок 10 оперативной памяти. Затем, при помощи второго регистра 13 адреса организуется поиск по массиву Gслова .Z swSTaKpro,, что последовательность W SWсовпадает с содержимым верхних ячеек второго блока 10 оперативной памяти. Если слово Z не обнаружено, то во второй регистр 13 адреса засылается г и описанная процедура повторяется вновь. При наличии слова Z во втором блоке 10 оперативной памяти стирается последовательность w и засылается метапеременная S . Затем после засылки г во второй регистр 13 адреса процессор Pj снова обращается ко второму блоку 8

0

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

ней некоторой метапеременной. При этом содержимое второго счетчика 9 уменьшается на соответствующее количество единицы, после чего процессо

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

В случае, когда на первой фазе работал процессора Р неравенство (1) не выполняется, во второй блок синхронизации засылается единица и

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

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

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

65 IСОШ. В начальном состоянии предлагаемого устройства содержимое первого 4 и второго 9 счетчиков равно нулю, содержимое второго блока 8 синхронизации также равно, нулю, второй блок 10 оперативной памяти пуст, содержимое первого блока 5 оперативной памяти и первого регистра 3 адреса равно & , где & - метка начального подмассива в G, соответствующего аксиоме грамматики данного языка; содержимое второго регистра 13 адреса г. При этом процессор Pg, начинает функционировать с некоторой задержкой 0 , которая равна времени проверки истинности неравенства (1) и засылки во второй блок 8 синхронизации единищл. Далее, процессоры Р и Pj функционируют параллельно. Предлагаемое устройство Синта сЙ чёского контроля программ обеспечи™ вает эффективный синтаксический конт роль, ориентированный на многопроцес сорный режим работы, что достигается путем органи зации параллельных встречных процессов обработки символов входной программы и средств их синхронизации. Предлагаемое устройс во может быть использовано при схемной интерпретации систем математического обеспечеяия для мяогопрея вссорных вычислительных компл€ ксов, чт позволит повысить их эффективность при решении задач обработки данных, в частности, в диалоговых системах коллективно О пользования при пежске и .испраэлении синтаксических ошибок. Формула изобретения Устройство для синтаксического контроля программ, содержащее пвр:вый региртр текущего символа, блок долговременной памяти, первый регистр адроса, первый блок оперативной памяти, блок сравнения, регистр синтер причем первый и второй выходы бяока долговременной памяти соединены соответственно с входом регистра син терма и с входом первого блока опера тивной г амяти, первый и ёторой выходы которого соединены соответственно с первым входом блока.сравнения и с первым входом первого регистра адреса, выход регистра синтерма соединен с вторим входом первого регистра адр са, первый выход которого соединен с первым входом блока долговременной памяти, отличающееся тем что, с целью повышения быстродействие устройство содержит первый и второй счетчики, второй блрк оперативной памяти, второй, регистр текущего символа, второй регистр адреса, первый и второй блоки синхронизации, причем первый, второй и третий выходы первого блока синхронизации соединены соответственно с входом первого регистра текущего символа, с вторым входом блока сравнения и с первым входом второго блока синхронизации, первый и второй выходы которого соединены соответственно с входом второго регистра текущего символа и с первым входом второго блока оперативной памяти, выход второго регистра текушеfo бимаола соединен с первым входом второго счетчикау первый и второй выходы которого соединены соответственно с первым входом первого блока синхронизации и с вторым входом блока долговременной памяти, третий и четвертый выходы блока долговременной памяти соединены соответственно с вторым входом вт-ерого блока оперативной -памяти и с деррьзм входом второго регистра адреса/ первый и эторой выходьз .которого соеданены соответственно с третьим вхойом блока долговременной йамяти и .с вторым входом второго 0лока синхронизации, , второй и третий выходы второго блока оперативной памяти соединекг- т соответственно с третьим входом блока сравнения,с вторым входом второго счетчика и с вторым входом второго регистра адреса, второй выход первого регистра адреса соединен с вторым входом первого блока синхронизации, выход первого регистра входйого символа соединен с входом первого счетчика, первый и второй выходы которого соединены с третьим входом первого блока синхронизации и с четвертым входом блока долговременной памяти, четвертей вход первого блока синхронизаьщи и третий вход второго блока синхронизации являются соответственно первым н вторым входом устройства. . Источники информации, принятые во внимание при экспертизе 1.Глушков В.М. и Барабанив А.А. и др. Вычислительные машины с развитыми система интерпретации. Киев Наукова думка 1970. 2.AjBTOpcKoe свидательство СССР 333558, кл. G 06 F 11/00, 06.03.70.

С