Устройство для синтаксического контроля Советский патент 1988 года по МПК G06F17/27 

,, Ошибки л (Успешный анамз

Фиг.1

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных и нроизводства 11рог)амм для ЭВМ.

J,e,ib изобретениярасн1ирение функциональных возможнос1ей путем полного синтаксическою анализа выражений, жаших скобки раз.-1ич11ых видов.

На . 1 представлена фупци(.1наль- ная схема ycrpoiicTEUi синтаксического контроля; на (})И. 2 (})унк1ии)нальная схема б.:|ока памяти; па фиг. Л нрпмер ныпо/i непия деп1И(})ра гора iifin (паков; па 4 нг. 4 блок-схема )11| | аммпого yii)aB |ения ус тройством CHHTaKcn U CKoio Ki)m |)оля.

Устройство слптаксичссксп о )оля («jinr. 1) C(Jдepжи иходной нчисц I. .ic- П11|ф|1агор 2 лекс пчсски сдппнп, о.кж ii унрав;1епия, п иф|1атп) 4, дсП1и4и)а i op Г) при (- наков, б. юк () памя i п.

В cocTasj блока (i Ufuir. 2| памяти входит группа |1енерспнньг регшмров 7 сдви1а

Входн(И1 нмдк тр I используется для хранения очередной . к-ксическо) единицы исходного вьц ажеппя. /leiii)i(()paTO() 2 лекс)1чсских единиц разде. 1Яет лексичс ски. 1. на о||е|1анды, операции, скобки, конеп шлраже- пия.

Б.юк 3 хнравления управ, 1яет 1)аботой всех элементов устройства. Д:1()ригм его 1})ункционирования описан б, 1ок-с емой мпк- jionpoi paMMnoro уп|)авл1М1ИЯ (фи1. 4), i дг входные си1палы . Х., .X,,. Х: формирует деп1ифрато|) 2 .лексических единиц (сигналы X, -. .4 образуют первую грунпу вхо. юв деп1ифра гора, а Xi;выход, деи1иф)атора

2 .лексических едипип). а Х.,. Х д(чпи(|)ра- тор 5 И)из11аков. 11а блока уи равле11ия формируются сигна.лы микроопераций YI Y:ii. (л)держате.:1Ы1Ы11 смысл входных и выходных .л()в с.л муюший:

ес.ли .лексическая единица исход ного выражения есгь операнд, в н)отинном с.чучае; если .лексическая единица исходною выражения ест1 одна из «.М видо(5 открывак)Н1их скобок, в противном с.чучае; если лексическая единица исходного вы)ажения есть бинарная операция; в противно.м с.чучае;

Г1, если .лексическая единица исход

(иого выражения есть одпа из «М вид(;в закрывающих скобок;

О в )тивном случае;

если на один из входов вгорой г)упп1,1 входов де|пи()а го|)а о признаков поступи.л сигнал о де- П1иф|1ации зак|))1цей скобки i-1 o вида, а на первую rfiynny входов ден1И(|)рато)а о признаков код открывающей CKo6i)i i-io вида; в противном с.лучае;

X,, --Х

если .лексическая единица исходного выра;«ения есть знак конца выраж(М1ия «ф«; в противном случае; если лексическая единица исходного В1 1ражения есть унарная операция; в п)отив11ом с.лучае;

если на вход ден1ифратора 5 поступил .л о дeцJифpaции знака «ф, а на третий вход ден1иф- ратора 5 с |1 цадения код нус- гогс.) симвс;;а (нули в ()азрядах peiHcrpoB б.лока В намяти); в 11ролд1вном с.чучае.

0

5

0

5

0

5

0

5

У

V

V

мик)(1опе|1ация,1)азре1иаЮ1цая

c6jK)c в п.П; содержимою блока 6 памяти;

ввод микроогц рации, разреп1аю1цей ввод с.и дуюшей .лексической единицы из ВХОДН01-0 регистра 1; микр1)опе)ация,разрешающая

i-двиг на один разряд в.лево (в сто- и)пу м,лад|пих |)азрядов) содержимого 1птис1 ров б.лока 6 памяти; выдача си|-на.ча «Запись в б.чок 6 |амяти;

выдача 1Ч)об|цения «Ошибка пушен оне|)

fibbiana сообщения «С)пибка цро- nvinena операция ; 1и,|дача с ообнн ния«Уснепшый

ана.

В1,|дача с(н)б|цсния «Опгибка нет ба.чапг;: скобокл ;

)ыдача сообщения «()1пибка не- соогве1ствие скобок ; С.ЧВИ1 на один разряд вправо (в сторону старн1их разрядов) c Jдepжи- мого регистров б,лока 6 памяти. 111п(})1а rt)p 4 4 ор Ч У - т ь:од1 1 «М видов отк 1ываюп1их скобок при поступлении на один из входов iруииы входов пифра- то)а 4 сигнала о деншфрации .лешифрато- )ом 2 .лексических е.чиниц кода открывающей скобки i-ro вида, что обеснечивает значи ге.льное уменьшение разрядности кода скобок, выдаваемого П1ифратором 4 (т.е. разрядности блока ( памяти), но сравнению с )аз 1ядностьк) входного кода.

j.4()K в намяли 11)едназначен для хранения, записи и считьшаиия кодов открывающих скобок различного вида, ностуиаю- ших на И1 формационный вход блсжа. Блок tj намяти н)едставляет собой на.мять с безадресным принципом записи и чтения и может быть выполнен на «К реверсивных с.лвпгаюн1их рег исграх 7. Соответствие между .чичеством видов открывающих ( акрываюн1ИХ) скобок и «К - числом разрядов, необходимых д.ля кодирования скобки, а с.чедовательно, и числом реверсивных сдвигающих регистров 7, вычисляется по формуле

К |loK,Mf+ 1.

где выражение означает 1елук) часть от iog:)M.

Загшсь поступившего кода скобки прои.4- водится в старшие (N-e) разряды регистров 7. Выходы N-X разрядов регист К)в 7 блока 6 памяти образуют группу выходов, связанную с первой ipyniioft входов (|)- ратора 5 признаков.

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

Реверсивные регистры 7 сдвига б.юка 6 памяти поразрядно сдвигают коды открывающих скобок, причем сдвиг вправо на один разряд равносилеп затиранию пос. 1еднегч) записанного в -е разряды регистров 7 кода открывающей скобки.

Де1иифратор 5 предназначен для выработки сигнала Х5 1 в случае, ec;in на один из разрядов второгс) входа дешифратора 5 поступил сигнал о дешифрации закрывающей скобки i-r o вида, а также си| нала Х8 I в случае, если на nepBijift вход дешифратора 5 поступи; сигнал о дешифрации знака «41. а на третий вход код пустого смивола. Дешифратор 5 может быть реализован, например, на программируемых логических матрицах (П,ПЛ). На первой промежуточной шине в магрице реализуется ко1п,юнкция кода iiepBoio вида открывающей скобки (например, код «ID...О и сигнала первого вида закрыЕ аюшег) скобки, на второй конъкл кция К(.)да второ1Ч) вида открывающей скобки (например, кои «010...О) и сигнала второго вида .закрывающей скобки, на М-й промежуточной шине конъюнкция кода М-го вида открывающей скобки и сигнала ЛА-го вида закрывающей скобки, на (М+1)-й промежуточной шине , ко1гьюнкция кода nycToi o си.мвола (код «00...()«) и сигнала дегпифра- ции знака «Ф конца выражения.

В матрице «ИЛИ L/1M задействованы два разряда выхода, на первом из которых формируется сигнал Xs как дизъюнкция конъюнций, сформированных на 1, 2

М-й промежуточных шинах, а на второ.м - сигнал .Х.ц.

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

На первом шаге блок 3 управления вырабатывает микрооперацию сброса в нуль содержимого регистров 7 блока 6 памяти (микроопе)ация Yi).

На втором шаге блок 3 управления вырабатывает .микрооперацию YL разрешения ввода лексической единицы из входного регистра 1. Пексическая единица поступает на дегпифратор 2 :1ексических единиц и дешифрируется дешифратором. Если на вход дешифратора 2 лексических единиц поступил код операнда (шаг 3), то дешифратор 2

лексических единиц вырабатывает cHiiia.i (Х|: 1), который запускает блок 3 управления, и на четвертом шаге блок 3 уцрав- ,|1ения выдает микрооперацию ввода с.ледую- шей лексической единицы (YL). Следующая лексическая единица поступает на дешш)- ратор 2 лексических единиц (шаг 5). При :)том, если па вход дешифрато|1а. nociy- пает код бинарной операции (Х,( 1), то блок 3 управления переходит к второму niary работы. Если на депгифратор 2 лексических

0

0

5

единиц цостуцил не код бинарной 1)пе)ации (), то блок 3 уцрав,1ения переходит к анализу сигнала Х4 (mai (i). Если на де шиф)атор 2 лексических единиц поступил код одной из М видов закрьп ающих скобок, то дешифратор 2 лексических единиц вырабатывает сигнал ., который занускает б, 1ок 3 управ,пения на анализ входного сигнала (Xs) от дешифратора 5. -.ели дешифратор 5 вырабатывает сигнал Хг, 1, то

4ТОТ сигна, запускает блок 3 унрав.тения

на выдачу микрооперации (Ym) сдвига вира- во на один разряд содержимого регистров 7 блока 6 памяти (соответствие вида поступившей из входного выражения закры5 вакццей скобки виду пос.гедней хранящейся открываюп1ей скобки приводит к их «вычеркиванию). Затем блок 3 управления переходит к выно,1нению третьего Hiai a. ЕС.in )1атор 5 вырабатывает сигна,;: :, 0. ТО сигнал занускает б, 1ок 3

0 управления на выдачу микрооперации «Ошибка - несоответствие скобок (микрооперация Y.I) и устройство завершает работу. Цикл обработки нового выражения может быть повюреи.

5Если же на паге 6 де|пифратор 2 лексических единиц вырабатывает спгна,т Х4 О, то этот сигнал занускает блок 3 уп- рав,ления на анали.з входного сигнала .X,, от дешифратора 2 лексических единиц. Г:сли Х(, О, т.е. поступившая на 4 лексическая единица не есть знак конца выражения «Ф, то этот сигнал запускает б, 1ок 3 упраиления на выдачу микроопе- )ации «Ошибкапропущена операция

(микрооперация Yi,) и устройство заве ицает

5 работу. Цик,т обработки новою выражения может быть noBTOpcfi.

Если сигна, Х,, 1, т.е. пост ,пек- сическая единица де1цп(} рируется ратором 2 лексических едини. как знак конца выражения «Ф, то этот еигна,: за ускает

0 блок 3 у1 р1вления на анализ входного сигнала Хк от дешифратора 5 Г:с,и ратор 5 вырабатывает сигна/ X,i 1, то блок 3 управления выдает микрооперацию «Успешный анализ (микроо ерация Y;) и устройство заверц ает работу. Цикл обработки нового выражения может быть повторен. В противном с,учае, при ус,:1овии, что входной сигнал Xh О, блок 3 управления В1 рабатывает мик)оо ерацик) «()ибка

нет баланса скобок (микрооперация YH) и устройство завершает работу. Цикл обработки нового выражения может быть повторен.

Вернемся к тагу 3, т.е. к анализу в.хол- ного сигна.ча X|. Пусть дешифратор 2 лексических единиц выработал сигнал ., т.е. входная лексическая единица не есть онеранд. Этот сигнал запускает блок 3 управления на анализ входного сигнала .Х от деп ифратора 2 лексических единиц. Нс;1и Х- 1, т.е. лексическая единица ислоднсло выражения есть одна и.ч М видов отк)ыва- ющих скобок, то атог сигнал запускает блок 3 управления на выдачу микроопераций сдвига на один разряд влево содержимого регистров 7 блока 6 памяти (микрооперация Y.j) и зашк ь кода открывающей скобки i-ro вида н с таршие разряды рег ист- ров 7 блока 6 памяти (микрооперация Y., 1. Затем блок 3 управления переходит к выпол нению второго тага, выдает разрешение на ввод с. 1едуюн1ей ;|ексической единицы ного выражения.

Ксли же входной сигиа; Х-2 О, т.е. входная лексическая единица не есть открывающая скобка, то этот си| на.-г запускает блок 3 унравления на анализ входного сигнала Х от дешифратора 2 лексических единиц. В случае, если Х7 I, т.е. дешифратор 2 лексических единиц определяет входную лексическую единицу как упарную операцию, то утот сигна: запускает блок 3 унравления, который переходит к выполнению второго HJara, т.е. ввода следующей лексической единицы (микрооперация Yj). Если же входной сигнал Х7 О, т.е. входная лексическая единица не есть унарная операция, то сиг нал запускает блок 3 управления на выдачу микрооперации «Ошибка - пропущен операнд (микрооперация YS) и устройство завершает . Цикл

0

5

0

5

0

5

обработки HOBOI4J выражения может быть повторен.

Формула 11:ю6ретения

Устр(.)йство д.ля синтаксического коитро- , содержащее входной регистр, дешифратор .чексических единиц, блок управления, шифратор и блок памяти, причем инфор- мационн1 1Й вход входного регистра явля егся инфо)мационным входом устройства, )Д входнси о регистра подключен к входу дешифратора лексических единиц, первый выход которого соедин; ;1 с первым в.ходо.м логических условий б. кжа унрав.тения, второй вьгход дец|иф)а Kjpa ,;1ексических единиц со(динен с входом шифратора, выход которого юдключен к информационному входу о;|ока памяти, трегий выход дешифратора лексических единиц соединен с вторым Bxo. io.vi .логических условий блока управлении, выход блока управления соеди- иеи с входом синхроиичации | ходног(; )е- гист1)а. второй выход блока унрав.ления под- к почсн к н)авляк)1цему входу блока памяти, третий и че1ве)Т1,1Й вьгчоды блока упран.н иия об|)азуют .1 признаков «Ошибка и « с кмпный анализ устройства соответственно, О1,1ичающееся те.м, что, с целью расширения функци()нальных но.зможиосгей за счет полного синтаксиче- i;Koro сШилиза вы)а/ке)ий, соде)жащих cK(jr)Kii ia.(ЛИЧНЫХ , в Hei o введен де- .|1иф|1агор п)изпаков, первый и второй ин- 1 ирмапи()}1ные вход|)1 которого соединены V т)етьим и Ч1 тве :тым выходами, дешифратора лексических единиц соответственно, .ретий ипформационный вход дешиф)атора признаков подключеп к выходу блока памяти, а иы.чол деп1И||)рато)а п)изнаков соединен с 1() входом лог ических ус.и)вий блока уп|)аиле11ия.

Код, открывающий скобки от Luutppamopa

Vt YZ У УЮ

От блока 5 управлени/

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

От deLuuippamopa 2 От блока памяти 6 лексических единиц

Н блоку управ/генил

Фиг. 3

С Ни чал О