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

 

Изобретение относится к вычислительной технике и может быть исполь:и)вано в автоматизированных система.х обработки данны.х и п)оизводства нрограмм для ЭВЛ. lle. ib изобретения расн ирение функциональных возможностей нутем Hojmoro синтаксического анализа выражений, содержащих скобки различных видов. Для достижения yKa.uiHHoi i це,-1И в устройство, содержанк с входной )е1 истр 1, де1ниф|1атор 2 лексических единиц, блок 3 управления, Н1ифратор 4 и б,1ок 6 памяти, до1И)лните, 1ык) вве ден де1нифратор 5 признаков, ведение дешифратора 5 и обусловленных его наличием связей позволяет существенно рас1ни- |))пь множество ис.ходных языков. 4 ил. с (О (Л со со го ел о: со

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 (-) 06 1 11101), 15 38

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 3

К А BTOPGKOMY СВИ4ЕТЕЛЬСТБУ ф(э,.

) д /

) Ашикам" „Чспешиь! в

ОИОИ03"

Й 02. ) (21) 4145262/24-24 (22) 10.11.86 (46) 30.04.88. Бк>л. ¹ 16 (72) В. К. Водопьянов, В. H. Завьялов, С. П. Зайцев, В. Н. Цымбал и С. H. Вавилов (53) 681.325 (088.8)

156) Авторское с в идетел ьство (.(.(Р № 1130879, кл. С) 06 1) 15/38, 1982.

Авторское свидетельство СССР № 1334149, кл. С(06 1) ll/00, () 06 E 15!38

1986.

„„SU„„1392563 А1 (54) У(.ТРО11(.ТВО I„ 1Я (.ИНТАК(.И(41 СКОРО КОНТРОЛЯ (57) Изобретение относится к выч(3сг)ительной технике и мо кет быть использовано (3 автоматизированных систеMdx обработки данных и производства программ для 3ВМ.

1 l (.в ь и зоб р с т (. н и я р (3 I I I и р (. ) I I I (. () ) 3 к 3 (и ональных возможностей путем полного синтакcè(lñ(.êîï) анали 3» выражений, содержагцих скобки р()злицных (33)до(3..1ля достижения

3 h)3.3(l ki 33() lk ц(.. )и в X стро((сTk30, (. од(. р ж а III((t3x()аной регистр 1, де(нифратор 2 лекси вских единиц, блок 3 управления, н(ифраl()E) 4 и блок 6 памяти, доно.)нительно ввс д(н дешифрапгор 5 признаков. Введение .((н)ифратор;3 ) и об)с)(о(3 i(. II(ihlx (I() н;)ли(нем (вя 3 II II() 3(3() IH(. ò сx нцственно расшиы ко13. 4 ил.

f392563

«Уснен!Ный

40

1, 45

Մ=—

ИЗОГ)рет< ни< ОTно(иTся к Вычи(. ли1(.1ьной технике ki можеT быть использовано в авгомытизировынных систеM

1)е.1 ь и.300 р<. т(н и я рыс i« i!pet! >i 3 фун кЦИОНЫ.>ЬНЫХ ВО.>МОЖ!!ОС Г(И НХ Т(М НО.1 НОГО

СИ НТ<3 К H IL (h01 0 Ы ft d. I kid ii i>t>l Раж tlH й, < O.l(. f)жыщих скобки р<3 <ли kill>lx ви.(013

1lы ф !г Ирелст;>в,!сны фу нционыльН <3 Я С X < М Ы > <. 1 Р О И < T B Ы < k I > I Г » K < И 1 (С КО! О КО Н ГролH itлы<ыя сxемы 10

6.>0k<> и >х>Я и, II<3 IIIOл

H <. tiki H, 1(lilt! ф p <> l 0 p к О 13, Н ы (() и 4

6. О к - (Х (М и !<1 >t k () 0 II ()< >I f) il м 1 Н О ГО х II p if< l < >I H H С POИСТВО" 1 СИ f>1 f)0. IH

I <(>и! . ) со,((f)rk>kt f Вхо ill«ll,)(I it< I Р I, ((IIII!фр>> Г(>р, 1<. k< II «(KII X (,(killlt II, 6 IOK 3

) i>р;>влс >ièÿ, >i ифр; г<>р -1,,(< «(и I <)p, »;рki < иаков, 0.10k () >lit (>I >I I II.

Б с(>(г>в 6 t0h i б (фиг 2! И>мяги (>ХО (и(гру Ilfl;I рсBCp< l!BBûX f)(I J!сl рОВ 7 <,iBHI,I 20

j3 x0,LIt0kt P(. I kl<. 1 f) I Jl < Il<).1 ь 3>. < 1 (H,l, JH

fl(Н И Я он< PC(НОИ . I(h< kl l ilkl l(l>l li < XO (Н О ГО В l>l p i t <к (I I I I Я . l < I I I J t ф р ы 1 О р I < h C и ((h u X

С,(Иf>иl(Рit.<. (СГ(H<. 1,>CKCИ I<< hè< С iн>IHI(I>l kl;I

0Il<. p<3Н 1Ы, OIIL f)lit, < КОбки, h0>l< 1! Нi>IJ)

l).I0K ) < iIр<3B lCНItЯ Х Ilf)

В< < X 3. !ЕМ(>ITOВ X (ГРОИС Гв<3. >3.! И)Р И ГМ ЕI O

<()у нкциониро!«>ния Ollll< >н блок-сx< IOH х>икр 0 I I p 0 l р (3 (>1 м н О О, I I p < I B, I (1 I k t H (ф и 1 . 4 ) фо(ми(-"T 30 ,. (С!!!И фР ) . I< h< И Ч(Ch И Х < lit fikt 1((< kt Гна. I Ы .х< 1- Х». 1, Ог)Р;«У«)! 1>(PB),K) (Рх>lll3 вх< (О(3 лешифры гора, ы x < BB>x01 . !I>33(!) ()i>TO() >

2 .IL ксичсски. с;I!it>Jtli) . (> Х „Х» .1(Ilill(j)Pкон. 11IХО,I(. блок > . 3 уи

Р<3 !3. (с I> kt я фо f) «1 fl Px K) Г< Я cи I lid 1û ми I,Р<>ОИ<>- 3з

P I 3 „. (.О.ц Р кы(с.>ьны(1 смы<.I вхо.(ill>l И (31>l XO.(Н Ь(Х 0ll i И<3, 1013 С.l(.(K)fill! Jt: с с,iи лL к< иры жени)1 сс I ь О;1«р>>нл, i3 Hf)0> ktt3>i0X> СЛУ IBC;

cc. t è;I(к< kt ч(. (к <>Я <,(lt >i t! IL

Bit, 1ов OTKpi>l >3<1K) lltkt X 0h060K, В II POT È В НО >1 СЛ У 1 <3(; если лексическая е;(иницы lt(0,(ног0 Выра hения ес1ь бинарная

0 I I <. P Ы Ц И Я; в нротивн<>м случ(>е;

С С Г> И Гl <> К С И Ч Е С K Ы Я <. Л И 1! И ! Ы И С Х О, ( ного выражения есTÜ Иди<1 и:3 «>31»

ВИлов >d кры13аК> I>(И" (ко()оh; 50 в противном сс!хчые;

CC1И НЫ ОДИН ИЗ ВХОДОВ BI ОРОИ грх lllll>l Входов (ешифр;>10()il 5 нри <н;>ко(3 посTóïè.l сигflI(3OI((< кобки

>-И> ВИЛI;> !IC(>IJÓf<) i f)yllllУ вхо,(ов .Ве>пифрытор(3 i) нри 3ныhîв

K0д Открывык)щ< и ско<>ы 1-1: J>lt l

1, если лексическая единица исходного выражения есть знак конца

131>l РI И и «+ «, 0 B нрот ианом с. f <> чае;

1, <>ели лексическая единица исходного выр;>ж<ния есть унарная

Он< ра ци я;

0 B llpOTktl3>IO)1 с.>х чае;

1, если >ш tixOд лешифратора 5 110< гx I>kt;I си> ныл о дешифрации знаh<1 «+», Ы llНIИф рыторы 5 с< ьныления кол нусгOIO сими<, з (нули в разрядах

p(рн (. б ); (i l3 lI Р<> Г и Ilf>0 М < . I >> I B<. . >IHkP00lI< Р;!ЦИHI, P

<ч)ро< h Ifx.!. с<)держим(но 6.10кы 6 нымяги;

Вво Микр<инц рации, разре>ныкнцей

ВВ(i,Л С. >(,, (3 К) (I!(. И .1<. КС И ((. С KOЙ ЕЛИIlk!i!I>l из !>хо. (ИО! О реги< тры 1;

I ., м и крООИ<>()ы ци я, р<(зр< н(аюн<ая

С,l llkli i!i> О (It >I РЫЗРЯЛ В 1< ВО (В CTO()0fIy м l;i;(i>ikix разрядов) содержиМОГО p(I ис1pOB блокы 6 памяти;

BJ>l,1ычы сигнал<3 «.3ыни(ь» в блок ()

Н(1 МЯ ГИ, Выл >чы <>06i>icflHH «()и!ибкы про-! > 3 I! L<. tl 01>< () >i;> ОII(. P 31(ИВ»;

131 (.((l i >!

Выл(3 >;> «и>бнц ния «Ошибка НсТ

6 чы 006>itcfiHH «Ошибка 00гв(Iс>ви«скобок»; с (Bèi II J Олин разряд ьч>рано (в сторону <"ãор 4 формирует колы «Ч» ви(0B Открываю!ци.< сh060k при ностунлении ны О (ин из >>хо,(013 i руины входов шифрагOpit 4 сигнал 1 О J,(. >lilt+ f)d(L>t>t де>нифрытоf)0M 2, I(ксическ их (ди ниц коды открывающей < кобки i-го виды, что обеспечивает зны (изе It>!IO(ум ньн((JIHc разрядности коды скобок, 1>ы (ы!Знаемого н>ифратором 4 (т.е.

f)<3.3J)H, (ll0(ГИ 6 IOKряднО< Гьк) !<ходнО! 0 кола.

1)ло б Вымя(и нреднызначен для хранения, зыниси и считывания кодов открыва

>ощи:< скоб, к различного вида, BOCTyl>dK>li(Hx 1ld информационный вход блока. Ьлок () памяти предстывляе1 собой намять с без»ДJ)<(IIЫ М I>PИ Н! (И 1(0> колич(ством BH,×oB открывак)llLJIx (<ыкрыв t>0!I(ktx) скобок и «К» — чис.Iом f) р я, (ОВ, II<. ОГ) х О,(>3 м ы х д 1я коли рОВания скобки, 3 <ле (Овытельно, и числом ре13Ч2563 версивных сдвигакнцих регистров 7, вычисляется но формуле

К = — (1о(М) + 1, где выражс ние 1!Од»М! означает целук> часть от (од>М.

Запись поступившего кода скобки ((роизводится в старшие (N-е) разряды регистров 7. Выходы N-h разрядов р(гнстров 7 блока (> памяти образуют группу выходов, связаннук> с первой рунной Вхо.tîâ де(пифратора 5 признаков.

Разрядность л регистров 7 зависит о1 допустимой глубины вложенности скобок и может наращиваться.

Реверсивные регистры 7 сдвига блока 6 памяти поразрядно сдвигак>т коды открыB3IoftLHx скобок, причем сдвиг вправо на один разряд равносилсн затиранию нос<)едне! О записанного В N-е разряды регистров 7 кода открывающей скобки.

Дешифратор 5 нредназнач kt для выработки сигнала Х;,= 1 в случае, если Hd один из разрядов второго входы д())<ифратора 5 поступил сигнал о дешифрации закрыван1)цей скобки I-го вида, а Taha«( сиГнала Х<<= 1 В случа<, (ñ1è на ll(>рвыЙ вход дешифратора 5 поступил си! нал о;ц шифрации знака «ф». а ны третий в. О1 код пустого смивола. Дешифратор 5 может быть реализован, наприм(р, н3 нрогрыммируемых логических матрицах (П, IM ) . 113

l1 (p Bo H l I p o x1 (ж х тО ч н О Й н и не В ы 3 I р и ц <. << (j реализуется конъюнкция коды II(рво! о ви ld открывающей скобки (например, коч «10 . О» и сигнала первого BH.и .>акрывыю<цей ско6ки, ны второй кон ьк>нкция ко!ы второго вида открывак>щей скобки (наприм(р, ко t

«010...0») и сигнала второго виды закрывающей скобки, на М-й ))ромежхто IH()H шине K<)H t>K)HKI(HH ко и М-го Виды открывак>щей скобки и сигнала М-го Вида закрывак>ц(ей скобки, ны (M+1) -й промежуточной шине, h<>tl ьK>flhltltH кодii пустого си м ВО 13 (кОд <<00...0«) и (. èÃíàë3 д(ц! ифрыции знака «ф:» конца выражения.

B матриц(«И,, 1 И» 11. I Ì заде Йствоныны два разряды Выходы, ны нервом из которых формируется сигнал Х-, hàк;(изГИК>нкция коньк>нций, сформированных на 1, 2,..., М-й промежуточных шинах, а на втором— сигна,l Х;.

Устройство работает следующим образом. (1a первом (наге блок 3 управления Вырабатывает микроонерацию сброса в нуль содержимого регистров 7 блока 6 памяти (м и кроо пера ци я ) ) .

l1a втором )наге блок 3 управления вырабатывает микроонерацию 1 > разрешения ввода лексической единицы из входного регистра I. Лексическая единица поступыег на дешифратор 2 лексических единиц и дешифрируется денIHôðàтором. Если на вход дешифрытора 2 лексических единиц поступил код оперын,и (шаг 3), то дешифратор 2 л(. Ксич(.ских (Линии t>t>lj)tt6IITI>laa(. 1 СНГН;!.! (hI — 1 ), кОторыЙ .(alf>><. кы<.т 6.)ОК > >> ftj>itffления, и на четвертом Ill!it е блок 3 у правления выдает микроонерыцик1 BBo ta следую)цей лексической единицы (E ). C.ë(.ióh)tft Iÿ л(ксическая единица постунаеT ны ден<ифрытор 2 лексических единиц (шыг 5). 11ри эгол), если на вход дец)ифрыторы. (И)ступы T код бинарной операции (Х = 1), T()

6лок 3 управления нерехо.i!IT к f>foj)oxly ftf;tf h работы. Если на дешифратор 2 Г)ексиче<. их единиц ностуиил не код бинарной Операции (Х = О), то блок 3 управ.)ения II(. реходит

ын(>лизу сиГltil 13 Х((ц!ВГ ()) . I с!и ны д(. (пифратор 2 лексических единиц ностунил код

15 одной из М видов закрывло(цих скобок, То ден)ифратор 2 лексических единиц выры6ilThlf3a(T <:И! Ны 1 Х< —— 1, K()T<)j>hf)1:(3!th(к,><. Т

6,Н>к 3 управления ны анализ вхо jH()I() сигныла (Х;,) от де)нифрытора 5. I.ñëè дешифратор 5 вырабатывает сигны.l Х;,= 1, То этот сигнал запускает 6<)ол 3 лпрывления ны Выдачу микроонерации (1<„) сдвига BtlpaB() на один разряд содержимого реги Tров 7 блока 6 ))амяти (соответ TBHc BHäa поступившей из входного выражения зыкры25 Вык>щей скобки видл последней храня<цейся Открывак>н(ей скобки приводит к Нх

«выч(. ркивыник)>> ) . З<>т(м 6лок ) унрыв.l(>ния

Il<>р«ходит к выпо.1нению третьего шага.

Е(ли дешифратор 5 вырабатывает сигнал

Х;.— О, то этот (игн;!л >ыпускаеT блок 3

30 hllpatiления ны выдачу микроонсрации «Ошибк;! — неcooTB(тствие скобок» (л(икроонер;)ция ) )) и устройство завер<н;цт р(>6оту.

1)ик.l обработки ново! () выра к(ния может

Оь!.1 ь новт()p(í.

35 1 (ли же на шаге 6 дешифратор 2 лексичесKHx единиц выра6ытывыет сигнал \(——

t), то этот сигнал запускает блок 3 управления на анализ входное(> сигH;i!3 Х„ о);ц шифрыпгоры 2 лексичесKHx единиц.

Если Х,;= О, т.е. поступившая ны шаге 4 лексическая единица не есть знак кон(и выражения «ф», то этот oèãíaë занускыет

6лок 3 лпрынления н3 вь(ды )л микрооперыции «Оц)И6к(! Ilpollh lll(и(! Опер,) ция» (микроон pallltH ) <,) и устрой TBo зыверн)ыет

45 ры6отл 1-IHK обры6отки нового Bill)i>ж

Если сигH(i.l Մ— >, ).е. поступившая леhсическая единица д(ц(и<рриру«т< я,(ец)инца выражения «ф», то этот сигнал зыпу h I(. г

50 6лок 3 унр >вления ía i»lы1«.«fxl() сигнала Х, от дешифрыторы 5 1 с.)и дешифратор 5 выра6атывыет сигнал Х.= 1, T() блок

3 унрывс(ения выдает микроон(рыцик> «YcIIBIII HhlH а на. IH !» (I>I I! K()o() !toð«i llH H E -, ) lt h!. Tройство завершает j)i>6() Ih. 1 икг! о6ры6отки

)н>вого выражения мож T 6ыть повтореH

В противном случае, нри условии, что

ВХОднОЙ сиГИ3.1 h <>= О, 6лок 3 h нрыВ1(ния

Bt>Ij) 36,ITI>I I>a(м и кр<ннц р;! ци к> . () IIIII(>hit

139250>3 нет баланса скобок» (микрооперация Yft) и устройство завершает работу. Цикл oáработки нового выражения может быть новTOP«Н.

Вернемся к шагу 3, т.е. к анализу входного сигнала Х<. II), ñòü L(øHôð3Top 2 лексических единиц выработал сигнал Х1 — О, т.е. входная леK(ическая сдиница II(. ес)ь операнд. Этот сигнал запускает блок 3 управления на анализ входного сигнала Х 0Т дешифратора 2 лексических единиц. Если

X = 1, т.е.. I(êñичс Kdя (дини ца исхо Ltloi О выражения есть Одна из М ви10B открывающих скобок, то эт01 сигни.l .<анускаст блок

3 управления на ны L3чу м икроонера ци и

H3 oJLHIi Pd3J)H,! B.1(f30 (o LL Ржимого регистров 7 блока 6 памяти (микроОII(. ра ция >,I ) и з31(и(ь кО, (3 ()ТKt) ы ни к) н!011 скобки i-го вида в старшие разряды регистров 7 блока 6 намя1и (микр<н>перация > .,1.

Затем блок 3 ytiJ)3B.I(IIHH ttepexoдит к вып<>л нению второго шага, выдает разрешение на ввод следующей лексической единицы исх0.1ног(> выражения.

Если же входной сигнал Х = О, I.e входная лексическая единица не ссть отлрывак>щая скобка, то этот сигнал зинускис г блок 3 управлеHHH на анализ вход>шго сигнала Х; от дешифратора 2 лексических единиц. В случае, если Х;= !, T.å. дешифратор 2 лексичес ки х един и ц oil ределяе T входную лексическуK) единицу кик унирнуK) операцию, то этот сигнал запускает блок 3 управления, который переходит к вынолнению второго шага, т.е. ввода следуюнци лексической единицы (It

Если же входной сигнал Х-,.= — О, т.е. вх0.1ная лексическая единица не есть унарния операция, то этот сигнал запускает блок 3 управления на выдачу микроонерации <()IJIII6ка -- пропущен операнд» (микроопериция

Y;,) и устройство завершает работу. ((икл обработки нового выражения может быть

ttOB t OJ)(и.

Формула Изобретения

Уt <ройс>во для синтаксического контроля, (.О !сржищее входш>й регистр, дешифратор л(ксических единиц, 6. 10K управления, tttHg)p JTop и блок 113мяти, нричем информационный вход входногo регистра явля(О еlся IIIIд в одного ре<истры подключен к входу ,N. шифратора лексических единиц, первый вы.хо,! Kt) lорогÎ сое IHlt(t (перВым входом логич(ских условий <.It)Kd vJIJ)38.цния, ВТо15 рой Bt tход дсшифр« 10J 3 лексиче ких едиlIHlL со< ди)ц и с Bxo,toë 1нифратори, выход

К () T 0 () О I О I I О. К Л IO Ч (. Н K И J t ф О () М и I! И О Н Н О М У вхо.tg блока памяти, грс THH выход,!ешифраJ<>p;i .10KHHtlvoKHx единиц соединен с вторым нхо, Ом,l<)I H÷å< KHx ус 1()HHH блока ), ttp3â tåэ0 ния, 11(рвый выход блока управtl(ния соедиtiCH (НХОДОМ «IIIIXJ)<)tilt JHHHH ВХО.(НОГО РЕi ист(>и, вгорой Bt txo;L 6 «>ки it!I)3Bл(ния 1<одК l lO lt lt К (II J) 3 B,:I >It<) IILL 1(t), B)>0, L>, 6.10ки J I 31 (J(.1 il H H tl(I 1« J)T t>I H Bi>I XO I l>t 6.10Kd

t, ll () и н, 1< tl И я <)6 J)3 t t К)т Bl Ход!>I П р Из Ни КО В

«с ) н(ибки ° и «У((н llllll>IH и ни IHз» уt тройства с<и> гвс т< твенно, о! лича>ощ((еч тем, чт0, с Itoët to рdсшир(ния функциОHальнk>lx

10<ма+ н<>сг(й:<3 счет 10лного (интаксиче> к 0 I < ),! I I i! I t t 1 i I в t >I J) L! >+ <. н и Й, с o>l t J) ж 3 LIL H x

t ho6)I It J>ii l.1H÷ных ни,H)B, B нс I о BB(..L(H д(>I l H J) J t I O J) I I J) ii .> Н 11 К О Б, 110 р Н ь) И И B TO p (> H И Н<() О () М 3 Ц И О Н Н Ь<С B X OT I>J K O T OP 0 I O O(. >L H I I P t I I>l

Iрс1ьим Jt It тн(J тым выходами .L(ц>и<ррагори It кси I(t. KHx е.(инин соответ твенно, ретин информиционныи вход .(с шифратора признаков подключен к выходу блока памяти, ;1 н<,<: 0.1,1<. Ill!I<()J) J тори признаков лп линев ()р(>) ьим нxolOм логич«(ких условий блока

Х II J) il и It. t 1 H u

1392563

Матрица „Или "

)Чатрица „И"

Фиг. У

0m дешисрра тора 2

0m блока памяти b лексическик единиц

E блоку упраВления

1392563

Составитель И. Поливода

Редактор А Маковская Техред И. Верес Корректор В Бутяга

Заказ 1808/53 Тираж 704 Подписное

В11ИИГ1И Государственного комитета СССР по делам изобретений и открытий

I l 3035, Москва, Ж - 35, Раугнская наб., д. 4, 5

Производственно полиг рафическое предприятие, г. Ужгород, ул 11роектная, 4