УСТРОЙСТВО СИНТАКСИЧЕСКОГО КОНТРОЛЯ ПРОГРАМB^iBJii-IOTei-CA Советский патент 1972 года по МПК G06F11/28 

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

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

В .предлагаемом устройстве для упрощения и уменьшения габаритов устройства стековая память соединеиа с регистром адреса и выходным .регистром долговременной памяти.

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

Устройство состоит из входного регистра /, вспомогательного регистра 2, схемы сравнения 3, выходного регистра 4, долговременной памяти 5, регистра адреса 6 и стековой иамяти 7.

В качестве основного символа для описания грамматики языка используется синтерм. Соответствие между термами и синтермами задано специальной таблицей W, занимающей ft log2J разрядов, где п - число термов, k - число синтермов в языке. Грамматика языка

записана в долговременной памят в виде двух массивов: R и W.

JR-массив условно разбит на некоторые подмассивы, в каждом из которых расположено несколько (некоторое число) элементов массива, каледый из которых занимает одно слово долговременной памяти и состоит из семи кодов:

1 эквивалентно R1 (занимает loga/ разрядов);

R2 эквивалентно R2; R3 эквивалентно R3; эквивалентно R4;

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

RQ эквивалентно R6 (занимает в общем случае Iog2b разрядов, где L - длина всего массива R;

R7. Если в R3 данного элемента есть признак чтения из стековой памяти, то R7 - адрес соответствующего данному элементу элемента -массива, у которого в 2 стоит признак записи в стековую память; в противном случае R7 либо пусто, либо является адресом «возврата, т. е. адресом, записываемым в стек и являющимся адресом продолжения соответствующего данному элементу подмассива, содержащего признак R5 в своем последнем элементе (в общем случае занимает разрядов элемента / -массива). В общем случае элемент /- -массива занимает (Iog2 +4+2 log2b) разрядов, а вся R-трамматика - {tt log2ft +L( + 2 log2b) 6мг долговременной памяти.

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

Для приведенного выше примера языка Rграмматика (см. фиг. 1) занимает 16-4 + +24 (4+4-1-2-6 544 бит долговременной памяти.

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

В исходном состоянии стековая память свободна, регистр адреса отмечает адрес начального подмассива / -грамматики, у которого в 1 записаны коды синтермов, которые могут быть первыми в программе данного алгоритмического языка.

Первый символ проверяемой программы записывается на входной регистр. Затем из таблицы W долговременной памяти по адресу на регистре адреса 6 считывается соответствующий этому символу синтерм и записывается на вспомогательный регистр, после чего из R-массива долговременной намяти но адресу на регистре адреса 6 считывается первый элемент начального подмассива и записывается на выходной регистр. Затем нроизводится сравнение кода Ri на выходном регистре с кодом на вспомогательном регистре. Сравнение производится с помощью схемы 3. Если указанные коды не сравнялись, то к коду адреса на регистре адреса прибавляется единица н считывается следующий элемент начального подмасснва. Указанные действия продолжаются до элемента, у которого в R4: стоит признак либо до элемента, у которого код 1 на регистре выходном совпал с кодом на вспомогательном регистре.

В первом случае вырабатывается сигнал синтаксической ошибки (СОШ), так как ни один из элементов в Rl начального подмассива не сравнился с первым синтермом проверяемой программы. Напомним, что в RI начального подмассива записаны коды синтермов, которые могут быть первыми в программе данного алгоритмического языка. Если первый синтерм проверяемой программы, полученный с помощью таблицы W из первого символа программы, не сравнился ни с одним из синтермов в данного подмассива, следовательно, он ошибочно написан первым, т. е. синтаксически неверно.

Во втором случае, когда код RI на выходном регистре 4 совпал с кодом на вспомогательном регистре, анализируется содержимое R7 на выходном регистре 4. Если R7 пусто, производится передача кода R& с выходного регистра долговременной памяти на регистр

адреса, т. е. на этот регистр записывается адрес начального элемента подмассива, у которого в RI записаны коды синтермов, которые в проверяемой программе могут идти следом за синтермом на вспомогательном регистре. Если R7 не пусто, производится запись кода 7 в стековую память и тем самым подготавливается адрес возврата, т. е. адрес продолжения -массива после некоторой подграмматики. Затем производится передача кода RQ с выходного регистра, долговременной памяти на регистр адреса.

После этого на входной регистр вызывается следующий символ проверяемой программы,

по которому из долговременной намяти на вспомогательный регистр считывается код соответствующего синтерма, затем на выходной регистр по адресу на регистре адреса считываются элементы / -массива, коды RI которых

сравниваются с кодом на вспомогательном регистре. Если просмотрен весь подмассив, т. е. проанализирован элемент, содержащий признак в R4, и не получено сравнение кода RI с содержимым вспомогательного регистра,

анализируется R5 текущего элемента -массива.

При отсутствии нризнака 5 устройством вырабатывается сигнал синтаксической ошибки, при наличии лризнака производится чтение из стековой памяти и передача на регистр адреса считанного адреса нродолжения текущего подмассива. По новому адресу на регистре адреса на выходной регистр считывается

элемент / -массива, коды RI которых сравниваются с кодом на вспомогательном регистре и т. д., аналогично описанному.

Указанные действия соответствуют элементам массива долговременной памяти, у которых отсутствуют признаки 2, R3.

В случае, если элемент на выходном регистре, у которого 1 совпал с кодом на вспомогательном регистре, имеет в R2 признак записи в стековую память, то замене кода на регистре адреса на код RQ предшествует запись текущего значения кода на этом регистре и признака R5 в стековую память. В остальном действия не отличаются от вышеописанных. В случае, если элемента на выходном регистре, у которого код 1 совпал с кодом на вспомогательном регистре, имеет в R3 признак, то записи кода 6 на регистр адреса предшествует сравнение кода на вершине стековой памяти с кодом 7 и 3 на выходном

регистре. Если эти коды совпали, то содержимое верхней ячейки стека удаляется и производятся описанные выше действия по переписи кода RQ на регистр адреса и т. д. Если же эти коды не совпали, то к содержимому стековой

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

жении приведенного выше алгоритмического языка могут быть i, b, р, п, t.

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

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

Фиг. 2