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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано при структурной интерпретации языков программирования для проверки правильности последовательности символов - цепочки некоторого формального языка, заданного соответствующей грамматикой. Цель изобретения - расширение области применения за счет расширения множества контролируемых языков. Для достижения указанной цели в устройство дополнительно введены блок управления, второй блок стековой памяти, два регистра числа блоков стековой памяти, два счетчика стека блоков стековой памяти, два блока ассоциативной памяти правил грамматики, два регистра признаков блока ассоциативной памяти правил грамматики, два регистра числа блоков ассоциативной памяти правил грамматики, блок ассоциативной памяти аксиом, регистр признака блока ассоциативной памяти аксиом, регистр левого контекста, блок элементов И и четыре блока сравнения. 1 з.п. ф-лы, 6 ил.

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

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

РЕСПУБЛИК (511 4 С 06 Р 15/38

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

H А ВТОРСКОМ,К СВИДЕТЕЛЬСТВУ

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

flO ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4276517/24-24 (22) 06.07.87 (46) 23.04.89. Бюл. № 15 (71) Институт кибернетики им. В.М.Глушкова (72) Е.Л.Ющенко, Г.Е.Цейтлин, Ю.Л.Иваськив и В.С.Харам .(53) 681.325(088.8) (56) Авторское свидетельство СССР № 669356, кл. G 06 F ll/00, 1979.

Авторское свидетельство СССР № 236861, кл. G 06 F 11/02, 1969. (54) УСТРОЙСТВО ДЛЯ СИНТАКСИЧЕСКОГО

КОНТРОЛЯ (57) Изобретение относится к вычислительной технике и может быть использовано при структурной интерпретации языков программирования для проверки правильности последовательности символов — цепочки некоторого

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

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

„„SU„„1474679 А 1 формального языка, заданного соответствующей грамматикой. Цель изобретения — расширение области применения за счет расширения множества контролируемых языков. Для достижения указанной цели в устройство дополнительно введены блок управления, второй блок стековой памяти, два регистра числа блоков стековой памяти, два счетчика стека блоков стековой памяти, два блока ассоциативной памяти правил грамматики,два регистра признаков блоков ассоциативной памяти правил грамматики, два регистра числа блоков ассоциативной памяти правил грамматики, блок ассоциативной памяти аксиом, регистр признака блока ассоциативной памяти. аксиом, регистр левого контекста, блок элементов И и четыре блока сравнения. 1 з.п. ф-лы, 6 ил, соответствующего языка программиро- р вания.указанная операция свертки является двойственной операции развертки, используемой в известном устройстве, т,е. при реализации операции развертки символы программы контролируются посредством применения правил грамматики путем замены их левых частей правыми. Используемая рпе- а рация свертки состоит в том, что ее применение предусматривает замену правых частей правил грамматики их левыми частями, в результате чего в процессе контроля анализируемая программа, если она правильная, сварачивается в аксиому.! 474679

Правые части правил в соответствии с общепринятой для анализа свертки терминологией называют основами.При выполнении операции свертки осуществляется левосторонний просмотр це5 почки языка с формированием первой слева основы и последующей ее заменой левой частью соответствующего правила грамматики. Этот акт циклически повторяется. до свертывания всей цепочки в аксиому грамматики (если цепочка синтаксически правильная, т.е. если она принадлежит данному языку) либо до обнаружения, в цепочке признака синтаксической ошибки.

При выполнении левостороннего просмотра анализируемые символы удобно хранить в памяти специального типа— стековой. Эту память называют первым стековым ЗУ. Для формирования основы используется отдельная память и эта память также типа стека — второе стековое ЗУ, длина второго стекового ЗУ выбирается, равной длине основы. При выполнении левостороннего просмотра необходимо также иметь специальные типы регистраций конечной длины для хранения правого и левого относительно основы контекстов.

Для хранения правил грамматики удобно использовать ассоциативное

ЗУ, В случае, если несколько правил имеют одну и ту же основу, эти правила записываются также во второе

35 ассбциативное ЗУ, На фиг.1 представлена блок-схема алгоритма работы предлагаемого устройства для синтаксического контроля; на фиг.2 — структурная схема предлагаемого устройства, на фиг.3—

6. — функциональная схема блока управления.

Пример 1. Пусть дан язык

L„= а «Ь ч а «с, m=1,2,...), порождаемьй бесконтекстной грамматикой G1, задаваемой следующей совокупностью правил. Р,: 6 Ч, (Ор О) у

Р7 а рг(ОЭО) Р3 М1 ач1bó; 4 а " с 50

Рg . y + (а,с). В приведенных правилах в круглых скобках указаны допустимые левые и правые контексты, при которых возможна свертка по данным правилам.

Считают, что в начальном состоянии стеки 7, и 7,Х, а также регистры левого и правого контекстов пусты.

Анализируют в соответствии с приведенным алгоритмом цепочку а + Ь, т которая принадлежит данному языку при m = 2.

На первом этапе левостороннего просмотра символ о заносится в регистр правого контекста, а 3 тем B первый стек. На втором шаге содержимое стека I переписывается в стек

II. На третьем шаге выполняется поиск основы в ассоциативном ЗУ по содержимому второго стека. Поскольку в первом ассоциативном ЗУ требуемой основы, нет, а также в связи с тем, что первый стек пуст, символ О из второго стека возвращается в первый стек ° На четвертом, шаге второй символ а пересылается в регистр правого контекста, а затем в первый стек, в котором теперь уже хранятся два символа a . Ha пятом шаге осуществляется перезапись символа а из первсго стека во второй стек ° Опять осуществляется поиск основы по содержимому второго стека (шестой шаг). Требуемой основы нет. Однако теперь первый стек не пустой (в нем хранится символ c ), не пустой и второй стек (в нем также хранится символ a,), Кроме того, второй стек еще и неполон. Поэтому на седьмом шаге содержимое первого стека переписывается во второй стек, в котором теперь уже хранятся два символа а., !

Требуемую основу по-прежнему (восьмой шаг) найти не удается. Однако теперь первый стек оказывается пустым. Поэтому на девятом шаге содержимое второго стека возвращается в первый стек. На десятом шаге символ + вводится в регистр правого контекста и далее в первый стек,. На одиннадцатом шаге содержимое вершины первого стека (символ ) переписывается во второй стек (после этого шага в первом стеке по-прежнему хранится цепочка aa ). На двадцатом шаге по содержимому второго стека ищется основа, Требуемую основу наконец удается найти (правила P и

Р ). Поскольку правила с такой основной неоднозначны, на тринадцатом шаге в регистр правого контекста вводится следующий символ из анализируемой цепочки, а именно, символ Ь.

Для проверки контекстов, позволяющих снять неопределенность, на че1474679 тырнадцатом шаге символ а из первого стека переписывается в регистр левого контекста, На пятнадцатом шаге по основе символу а, находящемуся в регистре левого контекста, а также символу Ь, находящемуся в регистре правого контекста, осуществляется поиск основы во втором ассоциативном ЗУ, в котором отыскивается левая часть (а именно Ю,) правила Р, по которому и осуществляется свертка. На шестнадцатом шаге символ < „ записывается в первый стек, после чего в нем находится следующая цепочка символов: аа,. На семнадцатом шаге второй стек обнуляется . На во семнадцатом шаге символ Ъ переписывается в первый стек. На девятнадцатом шаге содержимое времени первого стека (символ Ь) переписывается во второй стек.

На последующих шагах (с двадцатого по двадцать восьмой) подходящую основу обнаружить не удается, а из первого стека во второй стек, в котором уже хранится символ Ъ, последовательно переписываются символы и а, после чего содержимое первого стека составляет символ а, а содержимое второго стека составляет цепочка а ч, Ъ. На двадцать девятом шаге по содержимому второго стека удается найти основу (правило Р ), по которому и осуществляется свертка. На тридцатом шаге символ у записывается в первый стек, после чего его содержимым оказывается цепочка ау. На тридцать первом шаге второй стек обнуляется. На тридцать втором шаге второй символ Ь переписывается в регистр правого контекста и далее в первый стек, содержимое которого теперь уже представляет цепочка à V Ь.

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

На сорок седьмом шаге содержимое первого стека переписывается во второй стек. На сорок восьмом шаге осуществляется поиск основы в первом ассоциативном ЗУ по содержимому второго стека. Основу найти удается (правило P,). По этому правилу и осуществляется свертка. На сорок девятом шаге аксиома Б записывается в первый стек. На пятидесятом шаге второй стек опустошается. Так как анализируемая цепочка символов исчерпана, очередной символ в регистр правого контекста не вводится, и этот регистр

1 оказывается пустым. На пятьдесят первом шаге осуществляется проверка содержимого первого стека. В первом стеке находится аксиома. Следовательно, анализируемая цепочка является синтаксически правильной.

15 кода регистра 18, каналы 36 и 37, соединяющие четырнадцатый и пятУстройство для синтаксического контроля (фиг, 21 содержит блок 1 управления, блок 2 стековой памяти, регистр 3 числа блока 2, счетчик 4 сте20 ка блока 2, блок 5 сравнения, блок 6 стековой памяти, регистр 7 числа блока 6, счетчик 8 стека блока 6, блок

9 сравнения, блок 10 ассоциативной памяти правил грамматики, регистр 11 признака блока 10, регистр 12 числа блока 10, регистр 13 правого контекста, регистр !4 левого контекста, блок 15 сравнения, блок 16 ассоциативной памяти правил грамматики, регистр 17 признака блока lб,регистр

18 числа блока 16, блок 19 ассоциативной памяти аксиом, регистр 20приз-: нак а блока 1 9, блок 21 элементов И, блок 22 сравнения, канал 23, соединяющий первый выход блока 1 с управ35 ляющим входом блока 15 сравнения, каналы 24 и 25, соединяющие второй и третий выходы блока 1 с управляющими входами приема и вьдачи кода регистра 20 соответственно, каналы 26 и

27, соединяющие четвертый и пятый выходы блока 1 с управляющими входами контроля ассоциации блоков 19 и

16, каналы 28 и 29, соединяющие шес4 тОЙ и седьмОй ВыхОДы блока 1 с управляющими входами приема и выдачи кода регистра 14, каналы 30 и 31, соединяющие восьмой и девятый .выходы блока 1 с управляющими входами приема и вьдачи кода регистра 17, каналы 32 и 33, соединяющие десятый и одиннадцатый выходы блока 1 с уп-, равляющими входами контроля ассоциации и считывания блока 16, каналы

34 и 35, соединяющие двенадцатый и тринадцатый выходы блока 1 с управляющими входами приема и вьдачи

1474679 надцатый выходы блока 1 с управляющими входами приема и выдачи кода регистра 13, каналы 38 и 39, соединяющие шестнадцатый и семнадцатый выходы блока 1 с управляющими входа-:

5 ми приема и выдачи кода регистра 3, каналы 40 — 42, соединяющие восемнадцатый, девятнадцатый и двадцатый выходы блока 1 с управляющими входами записи, считывания и начала операции блока 2, каналы 43 и 44, соединяющие двадцать первый и двадцать второи выходы блока 1. с управляющими входами счетчика 4 и блока 5 сравнения соответственно, каналы 45 и 46, соединяющие двадцать третий и двадцать четвертной выходы блока 1 с уп-, равляющими в одами приема и выдачи кода регистра 11, каналы 47 — 49, 20 соединяющие двадцать пятый, двадцать шестой и двадцать седьмой выходы блока 1 соответственно с управляющими входами контроля ассоциации, считывания, начала операции блока 10, 25 каналы 50 и 51, соединяющие двадцать восьмой и двадцать девятый выходы блока 1 соответственно с управляющими входами приема и выдачи кода регистра 12, канал 52, соединяющий 30 тридцатый выход блока 1 с управляю щим входом блока 21, каналы 53 и 54, соединяющие тридцать первыи и тридцать второй выходы блока 1 с управляющими входами приема и выдачи кода регистра 7, каналы 55 — 58, соединяющие тридцать третий, тридцать четвертый, тридцать пятый и тридцать шестой выходы блока 1 с управляющими входами записи, считывания, одновре- 40 менного считывания, начала операции блока 6 соответственно, каналы 59—

61, соединяющие тридцать седьмой, тридцать восьмой и тридцать девятый выходы блока 1 с управляющими входами счетчика 8, блока 8 сравнения и блока 22 сравнения 22, канал 62, соединяиицж сороковой выход блока 1 с первым выходом устройства, каналы

63 и 64, соединяющие гервый и второй выходы блока 15 сравнения с первым и вторым входом блока 1, канал 65, соединяющий управляющий выход отсутствия слов, удовлетворяющих ассоциативному признаку, блока 16 с третьим входом блока 1, каналы 66 и 67, соединяющие управляющие выходы отсутствия слов, наличия слон, удовлетворяющих ассоциативному признаку, блока 19 с четвертым и пятым входами блока 1, канал 68, соединяющи:й управляющий.выход конца операции блока

19 с шестым входом блока 1, каналы

69 и 70, соединяющие управляющие выходы конца операций блоков 2 и 10 с седьмым и восьмым входами блока 1, каналы 71 - 73, соединяющие управляюшие выходы отсутствия слов, наличия слов, удовлетворяющих ассоциативному признаку, наличия более одного слова, удовлетворяющих ассоциативному признаку, блока 10 с девятым, десятым и одиннадцатым входами блока

1, канал 74, соединяющий управляющий выход конца операции блока 6 с двенадцатым входом блока 1, каналы 75 и 76, соединяющие первый и в..орой выходы блока 9 сравнения с тринадцатым и четырнадцатым входами блока 1, каналы 77 и 78, соединяющие первый и второй выходы блока 22 сравнения соответственно с пятнадцатым и шестнадцатым входами блока 1, каналы 79 и 80, соединяющие первый и второй выходы блока 5 сравнения с семнадцатым и восемнадцатым входами блока

1, канал 81, соединяющий двадцатый вход блока 1 с управляющим входом устройства, каналы 82 — 85, "оединяющие вход значения "0" соответственно с BTopbMH входами блоков 15, 5 и 22 сравнения и информационным входом блока 21, канал 86, соединяющий вход значения (m — длина основы) с вторым входом блока 9 сравнечия, канал 87, соединяющий информацлонный выход регистра 20 с информацяонным входом блока 19, каналы 88 — 90, соединяющие первый, второй и третий информационные выходы регистра 13 с первым входом блока 15 сравнения, первым входом регистра 17, вторым входом регистра 3, каналы 91 и 92, соединяющие первый и второй информационные выходы регистра 3 с информационным входом регистра 20 и первым информационным входом регистра

14, канал 93, соединяющий первый информационный выход регистра ll с вторым информационным входом регистра

17, каналы 94 и 95, соединяющие третий и четвертый информационные выхо. —, ды регистра 3 соответственно с первым информационным входом регистра

7 и информационным входом блока 2, каналы 96 — 99, соединяющие первый, третий, четвертый и пятый информа74679

9 14 ционные входы регистра 3 соответственно с первым информационным выходом регистра 7, информационным выходом регистра 18, первым информационным выходом устройства 2, информационным выходом регистра 12, канал 100, соединяющий информационный выход регистра левого контекста с третьим информационным входом регистра 17, канал 101, соединяющий информационный выход регистра 17 с информационным входом блока 16, канал 102, соединяющий информационный выход блока lб с информационным входом регистра 18, канал 103, соединяющий второй информационный выход блока 2 с информационным входом счетчика 4, канал

104, соединяющий выход счетчика 4 с первым входом блока 5 сравнения, канал 105, соединяющий второй информационный выход регистра II с информационным входом блока 10, канал 106 соединяющий информационный выход блока 10 с информационным входом регистра 12, канал 107, соединяющий выход блока 21 с вторым информационным входом регистра 14, канал 108, соединяющий второй информационный выход регистра 7 с информационным входом блока 6, каналы 109 — 111, соединяю, щие первый, второй и третий информационные выходы блока 6 соответственно с третьим информационным входом регистра 7 информационным входом регистра 11, информационным входом счетчика 8, каналы 112 и 113 соединяющие выход счетчика 8 соответственно с первыми входами блоков 9 и

22 сравнения, канал 114, соединяющий управляющий выход наличия слов, удовлетворяющих ассоциативному признаку, блока 16 с девятнадцатым входом блока 1, канал 115, соединяющий информационный вход регистра 13 с информационным входом устройства, канал 116s соединяющий сорок первый выход блока

1 с вторым управляющим выходом устройства.Регистры 3, 7, 12 — 14 и 18 предназначены для хранения одного символа (девять двоичных разрядов).

Емкость блока 2 стековой памяти составляет 2в+! односимвольных слов.

Емкость блока 6 стековой памяти составляет три односимвольных слова.

Регистр ll предназначен для хранения трех символов, а регистр 17 — пяти символов.

I0

Емкость блока 10 ассоциативной памяти правил грамматики определяется суммарным количеством основ (в рассмотренном примере пять основ).

Информационную часть слов, хранимых в этом ассоциативном устройстве, составляет один символ (являющийся левой частью соответствующего правила

1О грамматики) и двоичный разряд — признак неоднозначности.

Емкость блока ассоциативной памяти аксиом определяется количеством аксиом среди правил грамматики. В рассматриваемом примере имеется одна аксиома, которая представляется одним словом, Блок управления (фиг.3) содержит элемент ИЛИ 117, элементы 118 и 1!9 задержки, элемент И 120, элементы

121 и 122 задержки, элемент ИЛИ 123, элемент И 124, элемент 125 задержки, элементы ИЛИ 126 и 127, триггер 128 режима, элемент И 129, элементы 130—

132 задержки, элемент И 133, элементы 134 — 136 задержки, элемент ИЛИ

137, элемент 138 задержки, элемент

И 139, элемент 140 задержки, элементы И 14) и 142, элементы 143 и 144 задержки, триггер 145 режима, элементы И 146 и 147, элемент ИЛИ 148, элемент И 149, элемент 150 задержк, элементы И 151 и 152, элемент ИЛИ

I53, усилитель-формирователь 154, элементы 155 и 156 задержки, элемент

ИЛИ 157, элемент .158 задержки, усилитель-формирователь 159, триггер

160 режима, элемент И 161, элемент

162 задержки, элемент И 163, элемен40 ты 164 и 165 задержки, элементы И 166 и 167, усилитель-формирователь

168, элемент 169 задержки, элементы

И 170 — 172, элементы 173 и 174 задержки, элемент И 175, элемент ИЛИ

4> 176, элементы 177 — 179 задержки, триггер 180 режима, элемент 181 задержки, усилители-формирователи 182 и 183, элементы 184 и 185 задержки, элементы И 186 и 187, элементы 188

190 задержки, элемент ИЛИ 191, триггер 192 режима, усилитель-формирователь 193, элементы И 194 и 195, элементы ИЛИ 196 — 206, триггер 207 управления записью блока 2, триггер

208 управления записью блока 6, элементы ИЛИ 209 и 210, триггер 211 управления чтением блока 2, элемент

ИЛИ 212, триггер 213 управления чтением блока 6, канал 214, соединяющий

11 1474679

12 мента 132 задержки с единичным входом триггера 208, канал 245, соединяющий единичный выход триггера 208 с третьим входом элемента И 133, кана-.; лы 246 и 247, соединяющие выход элемента И 133 соответственно с входом элемента 134 задержки и нулевь м входом триггера 208, канал 248, соединяющий выход элемента 134 задержки с входом элемента 135 задержки, канал

249, соединяющий выход элемента 135 задержки с входом элемента 136 задержки.

Блок управления (фиг.4) также содержит каналы 250 и 251, соединякяцие выход элемента ИЛИ 137 с входом элемента 138 задержки и с единичным входом триггера 145, каналы 252 и 253, 20 соединяющие выход элемента 138 задержки с третьим входом элемента И

l39 и с первым входом элемента И 146, каналы 254 и 255, соединяющие единичный выход триггера 145 с третьим входами элементов И 142 и 149, каналы

256 и 257, соединяющие единичный выход триггера 145 с вторыми входами элементов И 139 и 146, канал . 258, соединяющий выход элемента И 139 с входом элемента 140 задержки, каналы

259 и 260, соединяющие выход элемента 140 задержки с вторыми входами элементов И 141 и 147, канал 61, соединяющий выход элемента И 147 с первьп входом элемента ИЛИ 146, канал 262, соединяющий выход элемента

È 146 с вторым входом элемента ИЛИ

148, канал 263, соединяющий выход элеЗО

4О - мента ИЛИ 148 с первым входом элемента

ИЛИ 153, канал 264, соединяющий выход элемента ИЛИ 153 с единичным входом триггера 213, канал 265, соединяющий единичный выход триггера 2)3 < пер45 выход элемента И 152 с первым входом элемента ИЛИ 117, канал 215, соединяняций выход элемента И 167 с третьим входом элемента ИЛИ 117Ä 216, соединяющий выход элемента ИЛИ 117 с входом элемента 118 задержки, канал 217 соединяющ и выход элемента

118 задержки с входом элемента 119 задержки, каналы 218 и 219, соединяющие выход элемента 119 с входами вторым элемента И 120 и первым элемента И 186, канал 220, соединяющий выход элемента И 120 с входом элемента 121 задержки, канал 221, соединяющий выход элемента 121 задержки с входом элемента 122 задержки, канал 222, соединяющий выход элемента .

122 задержки с первым входом элемента ИЛИ 123, канал 223, соединяющии выход элемента ИЛИ 123 с единичным входом триггера 207, канал 224, соединяющий единичный выход триггера

207 с первым входом элемента И 124, каналы 225, соединяющий выход элемента И 124 с входом элемента 125 задержки. Каналы.226-229, соединяющие соответственно входы с первого по четвертый элемента HJ!H 126 с выходами элемента 125 задержки, элементов И 141, 170 и 186. Канал 230, соединяющий первый вход элемента

ИЛИ 127 с выходом элемента ИЛИ 117, канал 231, соединяющий выход элемента ИЛИ 126 с единичным входом триггера 211, каналы 232 и 233, соединяющие единичный и нулевой входы триггера 128 соответственно с выходами элементов ИЛИ 127 и задержки 136, каналы 234 — 236; соединяющие единичный выход триггера 128 с первыми входами элементов И 129 и 133,и с третьим входом элемента И 124, канал

237, соединяющий второй вход элемента ЙЛИ 127 с выходом элемента И 141, канал 238, соединяющий выход элемента

И 124 с первым входом элемента ИЛИ

209, канал 239, соединяющий единич-. ный выход триггера 211 с третьим входом элемента И 129, каналы 240 и 241 соединяющие выход элемента И 129 соответственно с входом элемента 130 задержки и первыи входом элемента

ИЛИ 210 канал 242 соединяющ и выход элемента !30 задержки с входом элемента 131 задержки, канал 243, соединяющий выход злеиента 131 за-.. держки.с входом элемента 132 задержки, канал 244, соединяющий выход эле вым входом элемента И 142, каналы

266 и 267, соединяющие выход элемента ИЛИ 142 соответственно с первым входом элемента ИЛИ 212 и входом элемента 143 задержки, канал 268, соединяняций выход элемента 143 задержки с входои элемента 144 задержки, канал 269, соединяющий выход элемента 144 задержки с входом элемента

270 задержки, канал 271 соединяющий выход элемента 270 задержки с вторыи входом элемента ИЛИ 123, канал 272, соединяющий единичный выход триггера

207 с первым входом элемента И 149, каналы 273 и 274, соединяющие вы13

1474679 )4 ход элемента И 149 соответственно с входом элемента 150 задержки и с ezî рым входом элемента ИЛИ 209, каналы

275 и 276, соединяющие выход элемента 150 задержки с первыми входами элементов И 151 и 152, канал 277, соединяющий выход элемента И 151:ñ вторым входом элемента ИЛИ 153, канал 278, соединяющий выход элемента

И 152 с нулевым входом триггера 145, канал 279, соединяющий выход усилителя 159 с единичным входом триггера 160, канал 280, соединяющий выход усилителя 154 с входом элемента 155 задержки, канал 281, соединяющий выход элемента 155 задержки с входом элемента 156 задержки, канал 282, соединяющий выход элемента 156 задержки с первым входом элемента ИЛИ 157, канал 283, соединяющий выход элемента ИЛИ 157 с .нходом элемента 158 задержки, канал 284, соединяющий выход элемента 158 задержки с третьим входом элемента ИЛИ 123, каналы 285, соединяющий единичный выход триггера

160 с первым входом элемента И 161, канал 286, соединяющий выход триггера 207 с третьим входом элемента

И 161, канал 287, соединяющий единичный выход триггера 160 с первым входом элемента И 163, каналы 288 и

289, соединяющие выход элемента И

161 соответственно с входом элемента 162 задержки и с третьим входом элемента ИЛИ 209, канал 290, соединяющий третий вход элемента ИЛИ 153 с выходом элемента 162 задержки, канал 291, соединяющий единичный выход триггера 213 с третьим входом элемента И 163, канал 292, соединяющий выход элемента

И 163 с вторым входом элемента ИЛИ

212, канал 293, соединяющий выход элемента 164 задержки с входом элемента 165 задержки, каналы 294 и 295, соединяющие выход элемента 165 задержки с вторыми нходами элементов

И.lбб и 167, канал 296, соединяющий четвертый вход элемента ИЛИ 153 с выходом элемента И 166, канал 297, соединяющий выход элемента И !67 с нулевым входом триггера 160.

Кроме того, блок управления фиг.5 содержит каналы 298 и 299, соединяющие выход усилителя 168 соответственно с выходом элемента 169 задержки и единичным входом триггера 180, каналы 300-303, соединяющие единичный выход триггера 180 соответственно с вторыми входами элементов И 170-172 и 175, каналы 304 и.

305, соединяющие выход элемента 169 задержки с третьими входами элементов И 170 и 171, канал 306, соединяющий выход элемента И 171 с входом элемента 179 задержки, канал 307, соединяющий выход элемента 179 задержки с вторым входом элемента ИЛИ

176, канал 308, соединяющий единичный выход триггера 211 с третьим входом элемента И 172, каналы 309 и

310, соединяющие выход элемента И

172 соответственно с вторым входом элемента ИЛИ 2!О и входом элемента

173 задержки, какал 311, соединяющий выход элемента 173 задержки с входом

20 элемента 174 з держки, кан 312, соединяющий выход элемента 174 за-. держки с четвертым входом элемента

ИЛИ-123, каналы 313, соединяющий единичный выход триггера 207 с третьим входом элемента И 175, каналы 3!4 и

315, соединяющие выход элемента И

175 соответственно с четвертым вхо-. дом элемента ИЛИ 209 и первым входом элемента ИЛИ 176, канал 316, соединяющий выход элемента ИЛИ 176 с вхс— дом элемента 177 задержки, канал 31 соединяющий выход элемента 177 за-держки с входом элемента 178 задержки, каналы 318 и 319, соединяющие

35 выход элемента 178 задержки соотнетственно с входом элемента 181 задерж-. ки и нулевым входом триггера 180, канал 320, соединяющий ныход усилителя 183 с входом элемента 184 за40 держки, канал 321, соединяющий выход элемента 184 задержки с входом элемента 185 задержки, канал 322, соединяющий выход элемента 185 задержки с вторым входом элемента ИЛИ 157, канал 323, соединяющий выход элемента И 186 с единичным входом триггера

192, каналы 324 и 325, соединяющие

I второй и третий входы элемента И 187 соответственно с единичными выходами триггеров 211 и j92, каналы 326 и

327, соединяющие выход элемента И

187,соответственно с третьим выходом элемента ИЛИ 210 и входом элемента

1.88 задержки, каналы 328 и 329, соединяющие выход элемента 188 задержки соответственно с нулевым входом триггера 192 и входом элемента

189 задержки, канал 330, соединяющий выход элемента 189 задержки с нхо1474679

16 дом элемента 190 задержки, каналы

331 — 333, канал 334, соединяющий выход элемента И 194 с вторым входом элемента ИЛИ 191.

Блок управления (фиг.6) также содержит каналы 335-337, соединяющие первый, второй, третий входы элемента ИЛИ 196 соответственно с выходом элемента ИЛИ 137, выходом усилителя

168, выходом усилителя 193, каналы

338 и 339, соединяющие первый и второй входы элемента ИЛИ 197 соответственно с выходом элемента И 120 и выходом элемента 177 задержки, ка- 15 налы 340-346, соединяющие входы с первого по седьмой элемента ИЛИ 198 соответственно с выходами элементов

И 120, 129, элементов 143, 155 за-. держки, элемента И 172, элемента 184 20 задержки и элемента И 187, каналы "

347-353, соединяюшие входы с первого по седьмой элементы ИЛИ 199 соответственно с выходами элементов 121, 130,, 144 задержки, элемента ИЛИ 157, элемента 173 задержки, элемента ИЛИ

176 и элемента 188 задержки, каналы

354 и 355, соединяющие первый и второй входы элемента ИЛИ 200 соответственно с выходами элементов ИЛИ 123 30 и 126, каналы 356-358, соединяющие входы с первого по третий элемента

ИЛИ 201 соответственно с выходами элементов задержки 132 и 134 и элемента ИЛИ 153, каналы 359-364, соединяющие входы с первого по шестой элемента ИЛИ 202 соответственно с выходами элементов И 124,129,149,161, 172 и 187,каналы 365-367,соединяющие входы с йервого по третий элемента 4р

ИЛИ 203,соответственно с выходами элементов И 133; 42 и 163, каналы

368 и 369, соединяющие первый и второй входы элемента ИЛИ 204, соответственно с выходами элементов И 149 и элемента 164 задержки, каналы 370 и 371, соединяющие первый и второй входы. элемента ИЛИ 205 соответственно с выходами элемента 130 задержки и элемента И 142,-каналы 372 5р и 373, соединяющие первый и второй входы элемента ИЛИ 206,соответственно с выходами элементов 131, 143 задержки, канал 374, соединяющий выход элемента ИЛИ 209 с нулевым входом триггера 207, канал 375, соединяющий выход элемента ИЛИ 210 с нулевым входом триггера 211, канала 376, соединяющий выход элемента ИЛИ 212 с нулевым входом триггера 213, лемент задержки, каналы 377 и 378, соединяющие первый и второй входы элемента

ИЛИ 379 соответственно с выходом элемента ИЛИ 117 и выходом усилителя

168.

Устройство для синтаксического контроля начинает, работать с момента поступления управляющего сигнала по каналу 81 устройства. В качестве такого сигнала может быть использован, например, управляющий сигнал, формируемый в центральном устройстве управления ЦВМ, в которой применяется в качестве отдельного функционального блока предлагаемое устройство.управляющий сигнал, проходящий по входному каналу 81, запускает.в работу блок 1 управления. Под действием управляющего сигнала, поступающего из блока 1 по каналу 36, в регистр 13 вводится очередной символ из анализируемой цепочки символов. После приема символа в регистр 13 производится анализ запоминания регистра 13.

Анализ производится сравнением информационных и контрольных разрядов регистра 13 с значением "0". Сравнение происходит под действием управляющего сигнала, поступающего из блока 1 по каналу 23 на блок 15 сравнения. При несравнении значения регистра 13 с значением "0" с первого выхода блока 15 сравнения по каналу

63 в блок 1 поступает сигнал, под действием которого в блоке 1 вырабатываются управляющие сигналы, поступающие по каналам 37 и 38 соответственно на регистр 13 праь,ого контекста и регистр 3, Под действием этих сигналов происходит перепись содержимого регистра 13 в регистр 3.

После приема информации в регистр 3 организуется цикл записи инфс рмации, содержащейся в регистре 3, в блок 2 памяти.

Цикл записи происходит следующим образом. В начале цикла под действи-. ем управляющего сигнала, пос..упающего но каналу 39, происходи. выдача кода регистра 3 на информационный вход блока 2 памяти. Далее, под действием управляющих сигналов, поступающих по каналам 40 и 42, происходит запись информации в блок 2 стековой памяти. После окончания записи из последнего по каналу 69 поступает управляющий сигнал в блок 1 уп17

1474679

I8 равления. Под действием этого сигнала блок 1 управления выдает управляющий сигнал, поступающий по каналу 43 на управляющий вход счетчика

4 стека. В последний переписывается из блока 2 адрес последней занятой ячейки блока 2. На этом цикл записи заканчивается.

После записи информации в блок 2 выполняется перепись вершины блока

2 в блок 6. Перепись состоит из следующих операций: чтение слова в блоке 2 в регистр 3, передача содержи" мого регистра 3 в регистр 7, запись слова, содержащегося в регистре 7, в блок б.

Цикл считывания слова в блоке 2 происходит следующим образом. Под действием управляющих сигналов, поступающих по каналам 41 и 42, происходит считывание в блоке 2. После окончания считывания из блока 2 по каналу 69 поступает управляющий сигнал в блок 1. Под действием этого сигнала блоком 1 выдаются управляющие сигналы, поступающие по каналам

38 и 43 соответственно на управляющие входы приема кода регистра 3 и счетчика 4. В регистр 3 переписывается прочитанная из блока 2 информация.

В счетчик 4 из блока 2 переписывается адрес последней запятой ячейки блока 2. На этом цикл считывания заканчивается. Под действием управляющих сигналов, поступающих из блока

1 по каналам 39 и 53 осуществляется перепись содержимого регистра 3 в регистр 7. Цикл записи слова, содержащегося в регистре 7, в блок 6 аналогичен циклу записи слова из регистра 3 в блок 2. Управление записью в этом случае происходит управляющими сигналами, приходящими из блока 1 по каналам 55 и 58. Адрес последней запятой ячейки блока 6 находится в счетчике 8.

После записи информации в блок 6 выполняется формирование ассоциативного признака в регистре 11. Формирование ассоциативного признака происходит следующим образом. Под действием управляющих сигналов, поступающих из блока 1 по каналам 57, 58 и

45, осуществляется перепись всех слов блока 6 в регистр 11. После формирования ассоциативного признака в регистре 11 в блоке 10 осуществляется контроль ассоциации. В устройство поступает по каналу 47 из блока 1 уптI равляющий сигнал контроля ассоциации.

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

Впервом случае, когда в блоке 10 отсутствует информация, удовлетворяющая ассоциативному признаку, в блок

1 из блока !О по каналу 71 поступает управляющий сигнал. Под действием этого сигнала в блоке вырабатывает,ся управляющий сигнал, поступающий по каналу 44 на управляющий вход схемы сравнения. Происходит сравнение адреса последней занятой ячейки блока

2 и значения "0". Если счетчик 4 стека не равен нулю, блок 2 заполнен, происходит анализ последней занятой

26 ячейки блока 6 путем сравнения счетчика 8 стека со значением m = З.Сравнение происходит под действием управляющего сигнала, поступающего из блока 1 по каналу 60. Если сравнения

3Q не происходит, блок 6 неполон — имс— ются свободные ячейки, по каналу 7 в блок поступает управляющий cvT нал, под действием которого организуется перепись вершины блока 2 в блок б. как это описано. Если счет35 чик 4 стека равен нулю (все ячейки блока 2 свободны) или счетчик 8 стека m = 3 (все ячейки блока 6 заполнены), в блок 1 поступают управляю40 щие сигналы по каналам 80 или 76. Под действием этих сигналов выполняется перепись содержимого блока 6 в блок

2. Перепись выполняется посимвольно по аналогии с переписью вершины бло45 ка 2 в блок 6. Однако в этом случае переписываются все заполненные ячейки блока 6. Анализ занятости блока

6 осуществляет блок 22 сравнения под действием управляющего сигнала, приходящего по каналу 62 из блока l. Передача информации из регистра 7 в регистр 3 происходит по каналу 96 под действием управляющих сигналов, поступающих из блока по каналам 54 и 38. После переписи содержимого блока 6 в блок 2,с второго выхода блока

22 сравнения в блок 1 по каналу 78 поступает сигнал,под действием которого в блоке 1 формируется управляю20

1474679

19 щий сигнал, поступающий по каналу 36 на регистр 13. Из анализируемой цепочки символов вводится очередной символ в регистр 13 и прбизводится дальнейший анализ заполнения этого регистра.

Во втором случае, когда в блоке

10 имеется информация, удовлетворяющая ассоциативному признаку, в блок 10

1 из блока 10 по каналу 72 поступает управляющий сигнал. Под действием этого сигнала в блоке 1 вырабатывают" ся управляющие сигналы, поступающие по каналам 48 и 49 на блок 10 ° В 15 последнем осуществляется считывание слова по ассоциативному признаку, хранящемуся в регистре 11. После окончания считывания в блоке 10 считанное слово переписывается в регистр >О

12 по каналу 106. Прием слова в рег гистр 12 происходит под действием сигнала, приходящего из блока 1 по каналу 50. Далее под действием управляющих сигналов, приходящих из блока 1 по каналам 51 и 53, осуществляется по каналу 99 перепись считанного слова из регистра 12 в регистр 3. В устройстве для синтаксического контроля осуществляется