Устройство синтаксического контроля программ
Союз Советских
Социалистических
Республик
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Зависимое от авт. свидетельства ¹
Заявлено 27.Х1!.1967 (№ 1206093/18-24) с присоединением заявки М
Приор !тст
Опубликовано 03.11.1969. Б!Оллетеиь ¹ 7
Дата опубликования описаьи!я 1Л!П.1969
Кл, 421ттт, 11/02
МПК 6 061
УДК 681.326.77(088.8) Комитет по делам изобретений и открытий при Совете Министров
СССР
Авторы изобретения
И. В. Вельбицкий, Г. А. Михайлов и Е. Л. Ющенко
Институт кибернетики AH Украинской ССР заявитель
УСТРОИСТВО СИНТАКСИЧЕСКОГО КОНТРОЛЯ ПРОГРАММ
Предлагаемое устройство относится к ооласти использования в вычислительной технике алгоритмических языков и служит для проверки послсдовательностеи символов, построенных на определенной совокупности правил, называемых грамматикой языка.
Известно устройство, использующее пр1шцип синтаксических карт для схемной синтаксической проверки вводимых в машину программ, записанных на алгоритмическом языке. Оно содержит входной регистр, дешифратор основных синтаксических понят1ш, регистр поля анализа, логическую схему об11аружен1!я синтакси !ески неверной конст руl llilil в проверяемой программе, логическую схему перехода на новое поле анализа, лоп !еск !О схему формирования поля анализа, стековую память, блок счетчиков и блок внешней иидiiкации. Однако B этом устройстве схема 00наружения синтаксически неверной конструкции в проверяемой программе, схема перехода на новое поле анализа и схема формирования поля àliàлиза для практически используемых алгоритмических языков весьма громоздки и составляют 90 — 95% оборудования всего устройства, Поэтому при переходе на новый алгоритхшческий язык, имеющий другие синтаксические карты, замена логи1еских схем практически сводится к построеншо нового устройства. Затруднено также IIIIeccii iie ДС исправлений и дополнений в связи с исправлениями If дополнениями в исходном à II оритмическом языке.
Само устро,ствО для практического языка почти полностью занимает шкаф ВЧ. Однако при современной теидснции снаожения хlашин иескольк11ми алгоритмическими языками построение такого устройства может оказаться нецелесообразным.
В предложенном устройстве эти недостатк! устранены благодаря использованию схемы сравнения и долговременной памяти, выходной регистр которой связан с регистром адреса этой памяти и схемой сравнения, связанной со входным регистром проверяемой программы и стсковой памятью, которая связана с регистром адреса долговременной памяти.
I1a чертеже показано предлагаемое устройство.
3 стро!!ство состоит 113 входного регистра 1, схемы сравнения 2, выходного регистра 8, долговременной памяти 4 (ДЗУ), регистра адреса 5 и стэковой памяти 6.
В ДЗУ 4 записывается грамматика языка в виде одного массива. Весь массив условно разбит на некоторые подуровни, в каждом из которых располагается несколько (определенное чис.10) чле !еитов массива. Каждый эле3
Ъ)Сит )! ICCIII32 3сl и П» ЯСТ 03 IIO C;Jo 30 )3 < П
c o c T 01! 1 и 3 c c )i I I c. I c;I J, 10 IJ(: I.: ч Я с те й:
h0, CII i! БО. 12 5131>!КЯ (,321! ID!с)СТ (10";>»J j) 23Р51Д013, ГДС /1 — . 1 .ICЛО TC())IOB 5
Б 513hl КС );
Г) PII3H ЯК 3 Я И И СИ Б СТСhoB»!0 IIHЗIЯТ1> (запимяст (разряд); призиак чтения из стековой памяи! (занимает 1 разря !); I0 признак окончания некоторого иодуровия массива (заииъ!Яет 1 разряд); признак того, Iòî символ 3 Я1 этого элсмсита массива может быгь иослсдill!.» Б ирограммс, зяиисяппои !я даи- Т !
103 1 Я, 1! O P I IT) I i l ) C C I(0 >! 5I:3 hi 1(C (: i H I I I i 31 Hс 1 1 !) Я 3 Р5!Д ); ()ДPC(. 1 . Я Я, 1 cl (. 00 11!С!СТВУIÎIJIC! 0:)alf110»3 =, IP 3lCIlT ИО.! 5 POUII51 »ЯСС, В Я (Зспи! » ЯСТ Б обшс<>! СЛ»clclc ()О >1 J РЯБ- 20 рядов, где L — — длина Всего мacciiBH); адрес соответствующего (аииому элементу элемента массива, у которогo B
R2 стоит признак Записи в стскозу о
ПЯ »51 Ь; 2:э
П3 СТО, СС I (! Б 1>,«5 IICT I!PI!3!I ll(2 )ТСПИ51
ii3 стсковой п=!3!Ятц (ь обще)! случае
R>с ТЯК ЖС ЗЯНИМЯСТ (10 >) .>LJ рЯЗрядо!3
H.Ë CÌ HTcI МаССИБЯ) .
R)—
R-!в
Кб—
1(7—
Такilì образом, в общем случае элcмсflт ) KH3<1 I) IIOI >! ЯССИ<В Я Гря .>1><)ятп КИ ЯЗЫ) сl 3 Яиимает (((о ) »J I--j-t--lloo 1-)) разрядов.
Устройство работает следу!Ощим Образом.
В Начале с)ско 3251 память свободна, регистр адреса отмечает адрес начального по.!уровия . >)яссива, » KOTopoi 0 B Rl записаны i:o II>1 cll)!BO,10Ь> 1 .OTÎPB! C МОГJ, Т ОЫТЬ ПЕРВЫ.>1 и В П РО)ряммс IHJIIIolo алгоритмического языка.
Г(срьый cliìâîë проверяемой программы
32Ï iIСЬ1Bс!С ГСя )12 t3XO(110(! рС11!CTр 1. Г!OC)IС этого из (ЗУ считывается первый элемент
Н Яilcl Ii>lloi О ПО, !УPOBII)f М ЯССИI)сl П Я 1)Ы ХОД)!Ой реп)стр 1, и. с по IQII tip схс»ы ) Ilj)011313oд!Ггс)1 сраьие.ièñ кодл Я1 ия Bыхо !Н03! рci!ICTpc с ко том и а реп)ст рс 1.
Г(. I ll >> ка 3 H II I)ыс l(ОД!>! Iс сj) Hi3! I i i, i i! Сь, 0
1 0 Д У Я Д Р С С с! И с! ) I j) l i 0 c! B Л и 0 Т (и i! ! I l ! i H 1
CcIIIThlB ciCTC5I С, i(. I » IOIII Illl Э. )С)1(ц 1 li
ПО Ч) РОЗИ Я )<| с .ССИ Бсl. 3TII „I (и С i в) f)i !1 РОДО, 1жа- .>О
ЮТСЯ ДО ЭЛСМСитcl, У КОТОРОГО В i7(Стопт ВРизиак, либо Jo эг!С)!сг!тг), у которогÎ код 1(1 !IH
peI iicTpe 5 coBt!aл с I(oдо)! Ня рсг:101 рс l. В пер)30)! С.)>) Iac Вырс>бятывастся ci!I 1 сl. 1 c:!Iiтакси
СПМВСЛОБ, Кс1орЬIС МоlгсТ ОЬIТЬ ПСрвь!.itlt Б fjp
ПРОГPcl)DIe ДЯННОГÎ Я 1roPI)T)1 JI Если первый символ проверяемой программы ис сравнился llil с одним из симво ioB данноГо иод, рош)я, то значит он ошибо-lifo написан ИСРБЬ! М, 1 . С. II 2 il iICH Jl CII !ITñ! BC!i !CÑÊI! ПСBP j))IO. Во )ггором случае, ког..а код Rl ня реп)стрс 3 совпал с кодом иа pcliicтре 1, a регисгр Я псРсп! ic1>)Б Е3 R1 записаны коды символов, которые в Ilpo веряемой программе могут идти следом за символом ця регистре 1. Г(осле э )ого иа регистр 1 вызывается cëñду!опий символ проверяемой программы, спова сч)гтываются иа выходной регистр элсмеиты подуровня, отмечаемого адресом на реr11CT )C ), .! Якже ll pO I!380 IIITC5) CpclhilCHIIC Rl C ЯИ«!ЛÎI .ПО 011110 I!JÍÎI»». Зil! дсйс!БП5! Соответстьуют )лсмсптам мясcIfBH, 1,3 1, » ко)ophJ (О!(» I còi3»!0! призияк й:), 1с ) . В сл) )ас, соли элемент па регистре,З. У которого Rl совпал с кодом ия регистре 1, имccr ! с2 Прпэпа! . 32IJJIC i !3 C rehoB>, iO Па))ЯТЬ> зап,icii кола 1гб на регистр б предшествует ЗсlППСЬ )СIA JIICI О Зиа 101)1151 1 .ОДH Ha pCI ИСТрС б l3 С1 Ci 0i3 < IO па )Iя TЬ. В ОСTЯ. )Ы!031 ДСIICTВIIЯ HP. 0),iil!IHIOTC51 OT ОППСЯННЫХ. В случае, если элемент на регистре 3, у коTo()o;o Я! совпал с кодом иа регистре 1, и»ecr в !сЗ признак, то записи ко !а !(б на регистр б предшествует сравнеиие кода иа верш!шс стсковой памяти с кодом R7 па регистре ) . Если послсдиис коды совпали, то содepihlI:,Io0 вср)и)сй ячейки стека удаляется и произ))одятся описан Ы выше действия по переписи кода иа реп!стр б и т. д. Если этц коды ис совпали, то к содержимому регистра б приОяьлястся с illlllilia и действия производятся с Новым (слсдующ!i») элементом даи ioro под PОБПЯ )I ЯССI)ВЯ. В ho!i lie Ii pOBej)hil ПОСЛС,Ill liif С Di 130, 1 ПрОВС()Немой ирогря)!мы обязательно должеп сряв1l l1Ti>(и С ЯКИ)1 Э,!С»СIITO)1 СООТБСТСТВУ!ОЩЕГО подуpo!3!Jii » яссивя> у 1 0 Оро! 0 В Й э I!a Вхоти О 31 ); с и с 1 р с ) с i О и т и р и . 3 I H h В 11 p o T 1! B H o 3 I С !3!!H(Пр013Ср)>С)iя51 црОГр ;iolii!(я !Ной> !10 также соотвстствуег условию B I>l (i < i 0 0 1 i(I l С И Г И сl, 1 с I I l 1 H h C I I C C К О И 0 И И I О К И . ((j) С Д 3! С 1 И 3 О 0 j) C T C ll !I 51 Ус! policTBО си итсlксичсс)(ОГО контроля Il рограмм, от»и шюясес)) тем, что, с целью уllрощсиия устройства, умсиьшен!Гя с;о габарито)в и повышения иадежпости синтаксического «оитроля, оио содержит схему сравнения и долгов;)смс;!иую память, в! !ходио(! реп)стр которой связан с регистром адреса этой долгoB()p)!cl!IIUJI иамят и схемой срависиия, связанной с Б: одпым регистром >провер5!Смо!! проГраммы ii с!Ско()ой памятью, которая в свою очередь cB)ia,па с регистром адреса долговременной памяти. 236861 Составитель В. М. Шумский Тсхред Т. II. Курилко Iхоррсктор Г. И. Плешакова Редактор Л. А. Утехина Типография, пр. Сапунова, 2 3аказ 1173;16 Тираж 480 Подписное ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Центр, пр. Серова, д, 4
