333558

О П-ИС А Н И Е 333558 Союз Советских Социалистических РеспубликИЗОБРЕТЕН ИЯ К АВТОРт КОМУ СВИДЕТЕЛЬСТВ лавцсцхтос от Вт. свидетельства Ъ 2.Кл, С 061 11/00 6 061 1 о/4 явлено 06.111.1970 ( 1411398/18-24) с присоединением заявки чеПриоритет -Комитет по делам изобретений и откр,тийпри Совете Министров СССР81,327(0 Опубликовано 21.111.19Дата опубликования опи оллетець ЛЪ 11 ания 7 Х.197 Авторизобретения.1 нститут кибернетики АН Украинской СС ьтВцтелэ НТАКСИЧЕСКОГО КОНТРОЛЛРОГРАММ УСТРОЙСТВО ДЛЯ го регистра 1,хемы сравнеИзобретение относится к вычислительнойтехнике для проверки последовательностейсимволов, построенных по определенной совокупности правил, называемых грамматикойязыка.Известны устройства для синтаксическогоконтроля программ, содержащие входной регистр проверяемой программы, вспомогательный регистр для запоминания текущего синтерма, схему сравнения, долговременную истековую память, выходной регистр и регистрадреса долговременной памяти.Недостатком известных устройств являетсяих сложность и низкое быстродействие.Предлагаемое устройство отличается тем,что оно содержит регистр типа синтерма и логическую схему выбора, подключенную к выходному регистру долговремесщой памяти,вспомогательному регистру типа сицтерма, который подключен к выходному регистру и регистру типа синтерма, подключенному к выходному регистру долговременной памяти.Это упрощает устройство, уменьшает егогабариты и увелгсвает быстродеиствие.На фиг.изображена блок-схема предлагаемого устройства; на фиг. 2 приведеныФЯ-массивы грамматики алгоритмическогоязыка,Устройство состоит из входновспомогательного регистра 2, с цця 3, выходцого регистра 4, долговремевойпамяти 5, регистра адреса 6, стековой памяти 7, регистра 8 типа сццтерма и логическойсхемы 9 выбора сццтерма соответствующего5 типа,Грамматика языка записана в долговременной памяти устройства в виде двух массивов К и /. В массиве т" записана таблицасоответствия термов (основных символов0 языка) синтермам, Под синтермом понимается символ, которым обозначается группа синтаксически эквивалентных символов (состоящая оыть может цз одного символа) языка,Например, в языке АЛГОЛсинтерм Ъ10 обозначает группу синтаксически эквивалентНЫХ СИМВОЛОВ: Ч-:==- Однако в практических языках, как правило, одному терму соответствует несколькосицтермов (несколько типов сцнтермов) в за 20 висимости от того, в какой синтаксическойконструкции используется данный терм. Например, в языке АЛГОЛсимволам +, Хпосле ограничителя сотптеп 1 соответствуетодин синтерм - пусть Я, тем же символом в25 арифметическом выражении соответствуетдва разных синтерма +, Х.В долговременной памяти каждому словумассива В соответствует терм, В слове записаны все соответствующие ему синтермы.30 Каждое слово условно разбито на т частейпо 1 од 1 г разрядов, где т:-. - = - макси оь 2 с 1мальное число сцнтермов, соответствующееодному терму языка; 1, - число разрядов вслове долговременнои памяти; 1 г - общеечисло различных сицтермов для заданногоязыка, Длина массива К равна п, где п - число термов в языке. Таким образом, в долговременной памяти массив Й 1 занимает тоо 2/г и разрядов,В массиве записаны правила грамматикиязыка. Весь Я-массив условно разбит на некоторые подмассивы, в каждом из которыхрасположено несколько (некоторое число элементов массива). Каждому элементу Я-массива соответствует правило грамматики языка.Каждый элемент массива занимает одно слово долговременной памяти и состоит цз восьми частей:К 1код синтерма языка (занимает одаразрядов);1 с 2 - ,признак записи в стековую память (занимает 1 разряд);ЯЗ - признак чтения из стековой памяти (занимает 1 разряд);Я 4 - признак окончания некоторого подмассива (занимает 1 разряд);1 с 5 - признак того, что синтерм Я этогоэлемента подмассива может быть последним в программе, записанной наданном алгоритмическом языке (занимает 1 разряд);1 сб - адрес начала, соответствующего данному элементу подмассива грамматики(занимает в общем случае одУ разрядов, где У - длина всего Я-массива);Й 7 - адрес соответствующего данному элементу, элемента массива Й, у которогов Я 2 стоит признак записи в стековуюпамять, 1 с 7 - пусто, если в АЗ нетпризнака чтения нз стековой памяти (вобщем случае Я 7 также занимает1 оц 2 У разрядов);й 8 - код типа синтерма (номер по порядкусинтерма в элементе К-массива), соответствующий всем расположенным ниже элементам подмассива Я-грамматики; занимает 1 одт разрядов.Таким образом, в общем случае элемент1 с-массива грамматики языка занимает(1 одгй+ 4+2 о,У+ о,т) разрядов.В долговременной памяти (ДП) устройстваэта грамматика, очевидно, занимает толафп + У(1 о 21 г+4+21 о 2 У + 1 офт)668 разрядов.Работа устройства состоит в следующем,В ис.содцом состоянии стековая памятьсвободна, на регистре 8 типа синтерма записан код первого типа синтерма в В-массиве,ца регистре адреса б - адрес начального подмассива Я-грамматики языка. В этом подмассиве в 1 с записаны коды синтермов, которыемогут быть первыми в программе данного алгоритмического языка. 4Первый символ проверяемой программызаписывается на входной регистр 1. Затем из массива й 2 долговременной памяти по адресу ца регистре 1 считываются ца выходной ре гистр 4 все соответствующие данному символусинтермы. По коду на регистре 8 сломощью логической схемы 9 выоирается один из синтермов (в данном случае первый) и записывается на вспомогательный регистр 2. Послеэтого из Я-массива долговременной памяти по адресу на регистре б считывается первый элемент начального подмассива и записывается на выходной регистр 4. Затем производится сравнение кода на выходном регистре с кодом текущего сицтерма на регистре 2 с помощью схемы 3. Если указанные коды це сравнились, то к коду адреса ца регистре б прибавляется единица и считывается следующий элемент начального подмассцва. Действия продолжаются до элемента грамматики, у которого код Я на регистре 4 совпал с кодом ца регистре 2, либо до элемента, у которого в Я 4 стоит признак конца подмассива, Я первом случае код об ца выходном регистре переписывается на регистр б, тем самым на регистр б записывается адрес следующего подмассива, у которого в Я записавы коды синтермов, которые могут следовать за проверенным символом.Во втором случае, если код Я на регнст- зО ре 4 не совпал с кодом на регистре 2, а в Я 4стоит признак конца подмассива, то вырабатывается сигнал СОШ (синтаксической ошибки), так как,ни один из элементов Р в начальном подмассиве .не сравнился с первым З 5 синтермом проверяемой программы, Напомним, что в Я начального подмассива записаны коды синтермов, которые могут быть первымн в программе данного алгоритмического языка.40 Если первый синтерм проверяемой программы, полученный с помощью таблицы У-регистра типа и логической схемы выбора синтерма, не сравнился ни с одним из синтермов в Я первого подмассива, то значит он 45 ошибочно написан первым то есть сицтаксически неверно.Если сигнал СОШ не выработался, то определяется тип сицтерма следующего символа проверяемого предложения языка. Для этого по адресу на регистре б из долговременной памяти 5 считывается ца выходной регистр 4 первый элемент текущего подмассива, у которого в Я 8 записан тип синтерма кодов Я 55для всего подмассива. Код Я 8 с регистра 4 переписывается ца регистр 8, Тем самым определен тип синтерма следующего символа проверяемого предложения языка. Затем этот символ вызывается и записывается ца регистр 1.По коду этого символа как по адресу считываются из ДП и записываются на выходной регистр 4 все соответствующие данному символу синтермы, По коду на регистре 8 с по мощью логической схемы 9 вырабатывается333558 5однц соответствующий этому символу синтерм и записывается на вспомогательный регистр 2,Затем ца выходной регистр 4 по адресу ца регистре 6 счцтывшотся элементы Я-массив 1, 11 коды которых сравниваются с кодом ца регистре 2 и т. д. аналогично выше описываемому.Ъ казанные действия соответствуют элементам У-массива ДО, у которы отсутствуют признаки Л 2, йЗ.В случае, если элемент Я-массива на регистре 2, у которого код Р 1 совпал с кодом на регистре 2, имеет в Я 2 признак записи в стековую память, то записи кода Л,б на регистр 6 предшествует запись текущего значения кода на регистре 6 в стековую память, В остальном действия це отличаются от вышеописанных.В случае, если регистр 4, у которого код 71 совпал с кодом ца регистре 2, имеет в ЯЗ признак, то записи кода ЯЬ на регистр 6 предшествует сравнение кода ца вершине стековой памяти с кодом Я 7 ца выходном регистре 4. Если эти коды совпали, то содержимое верхней ячейки стека удаляется, и произ,водятся описанные выше действия по переписи кода Яб на регистр 6 и далее определение типа синтерма следующего символа проверяемого предложения, Если эти коды не совпали, то к содержимому регистру б прибавляется единица и описанные выше действия производятся с новым, следующим элементом данного подмассива Д-грамматики.В конце проверки последний синтерм проверяемой программы обязательно должен сравниться с таким элементом соответствуюбщего подмассива Я-грамматики, у которого в Р 5 стоит признак, что данный синтерм Я 1 на регистре 4 и регистре 2 может быть последним в программе данного алгоритмического языка, 0 В противном случае проверяемая программасчитается цедопцсанцоц, что соответствует также условию выработки сигнала синтаксической ошибки.Таким образом, из приведенного опцсания 10 процедуры синтаксического контроля нетрудно убедиться, что первыми синтермами в предложениях данного алгоритмического языка могут быть синтермы а либо /, вторым после / - й, далее а, либо 5 и т. д а также что 1 б предложение апйаЫс синтаксически правильно, а предложение апйа 11 с синтаксически неверно - при проверке пятого символа этого предложения вырабатывается сигнал СОШ. 20 П р едм ет цз обретения Устройство для синтаксического контроляпрограмм, содержащее входной регистр проверяемой программы, вспомогательный ре 2 в гцстр для запомцнашя текущего сцнтерма,схему сравнения, долговременную ц стековую память, выходцоц регистр ц регистр адреса долговременной памяти, отличающееся тем, что, с целью упрощения, увеличения быстродействия и уменьшения габаритов устройства, оцо содержит регистр типа сицтерма и логическую схему выбора, подключенную к выходному регистру долговременной памяти, вспомогательному регистру типа синтерма, который подключен к выходному регистру и регистру типа синтерма, который подключен к выходному регистру долговременной памяти.333558 О 1 г 5 1 б 21 19 1 1 1 1 Составитель В, Богатырев Техред 3. Таранеико Корректор Т. Китаев Редактор Б. Нанкина440 Тираж 500 Подпнсно изобретений и открытий ири Совете Министров СССР ва, Ж, Раушская наб., д. 4/5 Изд. о делах МосЗаказ 1958ЦНИИПИ Комитет Загорская типографг 67 а д Р й д Ь с 1 2 5 1 5 б д У 1 О 11 12 15 Ф 15 1 б 17 1 о 19 го 21 гг 25 Л 25 гб г 7 Я ГУ Л) Л лг Л 54 Р с л а Ь Р Х х х Х а о 1 1 1 о О г 2 г о О О О о о