Устройство для реализации подстановок

 

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

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

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

РЕСПУБЛИК (я)5 G 06 F 15/31, 15/16

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4873212/24 (22) 10,10,90 (46) 30.03.93. Бюл. ru.. 12 (71) Курский политехнический институт (72) В.M.Äoâãàïü, О,Ф,Корольков, Е.И.Леонов, Ф,А.Старков, Д,Н.Тютюнов, С.С.Шевелев (56) Марков А,А., Нагорный Н.М, Теория алгорифмов. M.: Наука, 1984.

Авторское свидетельство СССР

М 1455345, кл, G 06 F 15/16, (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

ПОДСТАНОВОК (57) Изобретение относится к техническим средствам информатики и вычислительной

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

Блок 1 выборки правых частей формул подстэновок содержит узел памяти 7 и счетчик адреса 8, причем в блоке выборки правых частей формул подстановок вход чтения, вход инкремента адреса и вход режима подключены соответственно ко входу разрешения чтения узла памяти, входу инкремента счетчика адреса и входу разреше(„)5U„„1805478 А1 техники и может быть использовано для обработки символьной информации в соответствии с заданной системой формул подстэновок. Целью изобретения является повышение быстродействия за счет реализации масок для анализа фрагментов обрабатываемых слов, алфавитных переменных и итерационных фрагментов в формулах подстановок. Поставленная цель достигается тем, что устройство содержит блок памяти слов, блок микропрограммного управления, блок выборки правых частей формул подстановок, блок выборки левых частей формул подстановок, блок анализа подстановок и блок подсчета длины заменяемых фрагментов слова. 6 ил. ния приема информации в счетчик адреса, информационные входы группы блока подключены соответственно к информационным входам счетчика, выход которого подключен к адресному входу узла памяти, выход которого подключен соответственно к информационному выходу блока, Блок 2 выборки левых частей формул подстановок содержит узел памяти 9, реверсивный счетчик адреса 10, коммутатор 11, первый и второй регистры 12, 13, причем вход чтения, первый вход режима, вход инкремента адреса, вход декремента адреса, второй, третий и четвертый входы режима блока подключены соответственно ко входу разрешения чтения узла памяти. входу разрешения приема информации в счетчик адреса, входу инкремента счетчика адреса, входу декремента счетчика адреса, управляющему входу коммутатора, входу разреше1805478

50

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

Блок 3 анализа ситуации содержит первый 16 и второй 20 регистры символов, регистр маски 17, первый 14 и второй 21 триггеры, узел сравнения 18, коммутатор

23, первый 15 и второй 19 элементы И и элемент ИЛИ 22, причем в блоке анализа ситуации входы режима с первого по шестой подключены соответственно ко входу синхронизации первого триггера, ко входам разрешения приема информации в первый регистр символа и регистр маски, входу установки в ноль второго триггера, входу установки в единицу второго триггера, входу разрешения приема информации во второй регистр символа и к управляющему входу коммутатора, выход которого подключен к информационному входу второго регистра символа, выходы которого подключены к соответствующим информационным входам второй группы узла сравнения, входам второго элемента И, элемента ИЛИ и информационным выходам блока, разряды с 1-го по п-й, с (п+1)-го по 2п-й и (2п+1)-й второго информационного входа подключены соответственно к информационным входам первого регистра символов, регистра маски и первого триггера, выходы первого регистра подключены к соответствующим входам первого элемента И и информационным входам первой группы узла сравнения, управляющие входы которого подключены к соответствующим выходам регистра маски, первый и третий информационные входы блока подключены соответственно ко второму и первому информационным входам коммутатора, управляющие выходы с первого по шестой блока подключены соответственно к выходам первого триггера, узла сравнения, второго триггера, инверсному выходу элемента ИЛИ, выходам второго и первого элементов И.

Блок 4 памяти слова содержит первый

26 и второй 30 узлы памяти, а первый 25, второй 27, третий 28 и четвертый 29 регист5

40 ры адреса, счетчик адреса 33, первый 24 и второй 31 коммутаторы и элемент И 32, причем в блоке памяти слова с первого по шестой входы режима, первый вход записи, первый вход чтения, вход инкремента адреса, вход установки в начальное состояние, второй вход чтения и второй вход записи подключены соответственно ко входам разрешения приема информации во второй регистр адреса, разрешения приема информации в третий регистр адреса, управляющему входу первого коммутатора, входу разрешения приема информации в первый регистр адреса, управляющему входу второго коммутатора, входу разрешения приема информации в четвертый регистр адреса, входу разрешения записи во второй узел памяти, разрешения чтения второго узла памяти, входу инкремента счетчика, входу установки в ноль четвертого регистра адреса, входу разрешения чтения первого узла памяти и входу разрешения записи в первый узел памяти, информационный вход которого подключен к информационному входу блока, выходы второго и третьего регистров адреса подключены соответственно к первому и второму информационным входам первого коммутатора, выход которого подключен к информационному входу четвертого регистра адреса, выход которого подключен к информационным входам первого и второго регистров адреса, адресному входу второго узла памяти и адресному входу первого узла памяти, выход которого подключен к информационному выходу блока, выходы счетчика адреса подключены к соответствующим входам элемента И и к информационным входам первой группы второго коммутатора, выход которого подключен к информационному входу второго узла памяти, выход которого подключен к третьему информационному входу первого коммутатора и информационному входу первого регистра адреса, выходы которого подключены к информационным входам второй группы второго коммутатора, управляющий выход блока подключен к выходу элемента И, Блок 5 подсчета длины вхождений содержит счетчик 34 и элемент ИЛИ 35, причем входы инкремента, декремента и установки в исходное состояние блока подключены соответственно ко входам инкремента, декремента и установки в ноль счетчика, информационные выходы которого подключены ко входам элемента ИЛИ, выход которого подключен к выходу блока.

Сопоставительный анализ показывает, что заявляемое устройство отличается от прототипа наличием новых блоков, позволя1805478 отдельных фрагментов слов-вхождений в формулах подстановок возможно использо- 5

15

25 ющих обрабатывать цепочки символов, используя системы формул подстановок с метками переходов, причем для записи вание алфавитных переменных, слов-итераций и битовых ансамблей, На фиг.1 изображена структурная схема устройства; на фиг.2 — структурные схемы блока выборки правых частей формул подстановок и блока подсчета длины вхождений; на фиг.3 — структурная схема блока выборки левых частей формул подстановок; на фиг.4 — структурная схема блока анализа ситуации; на фиг.5 — структурная схема блока памяти слов; на фиг,б — граф-схема алгоритма работы блока микропрограммного управления.

Устройство для реализации подстановок содержит блок 1 выборки левых частей формул подстановок, блок 2 выборки правых частей формул подстановок, блок 3 анализа ситуации, блок 4 памяти слов, блок 5 подсчета длины вхождений и блок 6 микропрограммного управления, Обрабатываемые слова и формулы подстановок задаются в некотором фиксированном алфавите, в который не входят символы, используемые для разделения левой и правой частей формулы и указания ее типа.

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

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

Конечный список формул подстановок является системой тогда, когда на нем заданы условия включения формул спйска в работу, Для алгорифма Маркова условия включения формул в работу определены следующим образом: — если i-я формула (здесь и далее по тексту i — номер включенной в работу формулы) сработала и она простая, то следующей вкл:очается в работу первая в списке формула;

- если сработавшая формула — заключительная, то алгорифм прекращает свою работу;

55 — если i-я формула не сработала, то следующей включается в работу (i+1)-я формула; если при этом i = N (N — число формул подстановок в списке), то алгорифм прекращает свою работу.

Воспользуемся следующими расширениями теории нормальных алгорифмов.

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

1, аЬ-> ms

2, kf-> som

3. prg -> fl

4. nal > stp.

При срабатывании каждой из трех последних формул алгорифма осуществляется переход на первую формулу, которая заведомо не сработает, поскольку при подстановке som, fl или stp в любое обрабатываемое слово, не содержащее фрагмента ab, буквосочетание ab появиться не может, но после срабатывания третьей формулы может сработать вторая, т,к. в обрабатываемом слове после выполнения подстановки fl может быть получен фрагмент ... kfl„,. В то же время, после срабатывания четвертой формулы никогда не сработает вторая, но в обрабатываемом слове может возникнуть буквосочетание ...

stprg..., порождающее срабатывание третьей формулы подстановки. Исходя из приведенных рассуждений, расставим в нормальном алгорифме метки переходов, Полученная размеченная система формул подстановок будет иметь следующий вид: вх. вых. метки метка формула М1 М2 аЬ -> ms

kf-> som

prg -> f l

nal > stp

1805478

55

По аналогии в тех случаях, когда формулы не срабатывают, возможны "скачки" через несколько формул вперед (к концу списка), Таким образом, использование размеченных формул подстановок в алгорифмах

Маркова позволяет получать существенный выигрыш во времени за счет невключения в работу заведомо несработавших формул, тем самым сокращая значительную часть самого длительного процесса — просмотра обрабатываемого слова, Алфавитные переменные — "безразличные" символы, используемые при написании левых частей формул подстановок, на месте которых подразумевается нахождение любого символа из рабочего алфавита, Для выделения алфавитных переменных вводятся маски для каждого символа словавхождения, причем алфавитные переменные маскируются единицами по всей длине кода символа, а символы, задаваемые в явном виде — нулями. Например, формула подстановки, содержащая три алфавитных переменные; а pbgrgd — > аЬа, будет реализована следующим образом: мом1мом1м1мо

a pbgig d — > aba, причем маска значащих символов а, Ь, d будет М = 00„.0, а маска для алфавитных переменных — М1 = 11...1, Битовые ансамбли применяются в случаях необходимости осуществления замены фрагментов обрабатываемого слова, содержащего заданный набор битов внутри кодов символов. Выделение значащих битов каждого символа слова-вхождения производится с помощью маскирования этих битов нулевыми масками, а биты, не имеющие в данной ситуации значения, при этом маскируются единицами. Например, необходимо выделить фрагмент, в котором значимыми являются первый и четвертый биты кода первого символа и пятый бит кода третьего символа, Маски символов левой части формулы подстановки будут представлены в следующем виде. символы биты 1-й 2-й 3-й

1 О 1 1

2 1 1 1

3 1 1 1

4 О 1 1

5 1 1 О

6 1 1 1

7 1 1 1

8 1 1 1

Еще одна из часто встречающихся при символьной обработке задач — выделение

45 повторя ющихся и роизвол ь ное (заранее неизвестное, в т,ч. и равное О) число фрагментов обрабатываемого слова — словитераций. Слова-итерации при программировании данного устройства выделяются следующим образом:

/аЬ/, а/Ь/с, где символ "/" не входит в рабочие алфавиты задаваемых алгорифмов и обозначает границы слов-итераций.

Узел памяти 9 блока 2 выборки левых частей формул подстановок предназначен для хранения левых частей формул подстановок, B каждой его ячейке хранится очередной символ вхождения (п бит), его маска (n бит) и признак (1 бит), который равен 1 в случае, когда данный символ является последним в слове-вхождении. Кроме того, перед первым символом каждого слова— вхождения в ячейке с адресом Ао =А -1 хранится адрес — метка (m бит, m < 2"-1) начала слова — вхождения той формулы, на которую осуществляется переход в случае несрабатывания текущей и признак(1 бит), который равен 1 только тогда, когда текущая формула является последней формулой алгорифма; после последнего символа каждого слова-вхождения в ячейке с адресом

Ар =AR+1 находится адрес (k, бит, k 2"-1) первого символа правой части данной формулы, которая хранится в узле памяти блока

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

Аз =Ap+1, хранится адрес метка (m бит) начала левой части формулы подстановки, на которую осуществляется переход при срабатывании данной формулы, причем разряд признаков данной ячейки равен 1 только тогда, когда текущая формула — заключительная, В узле памяти 7 блока 1 выборки правых частей формул подстановок хранятся символы слов — подстановок всех формул алгорифма, Каждое слово-подстановка завершается специальным символом — признаком конца слова (П КС), имеющим единицы во всех разрядах своего кода.

B первом узле памяти 26 блока 4 памяти слова располагаются символы обрабатываемого слова, связанные между собой в список адресами (1 бит), которые хранятся во втором узле памяти 30 того же блока. Конец списка обрабатываемого слова обозначается тем же символом (ПКС), что и конец слова — подстановки, Имеются еще два специальных символа, не входящих в рабочие алфавиты обрабатываемых устройством алгорифмов, но используемых при его программировании, 1805478

10 (кодируется нулями по всей длине кода), и 5 символ, применяемый для выделения граЭто — пустой символ а, используемый для записи формул вида;

-> Т;

$-> ниц слов — итераций (кодируется аналогично

П КС), В списке обрабатываемого слова первым всегда стоит пустой символ а„который хранится в ячейке с адресом 00...0.

Перед началом работы устройства для реализации подстановок все его регистры, триггеры, счетчики, кроме счетчика адреса

32 блока 4 памяти слова, в котором выставлен адрес первой свободной ячейки первого узла памяти того же блока, находятся в нулевом состоя нии.

Процесс поиска в обрабатываемом слове вхождения, заданного включенной в работу формулой подстановки, заключается в поочередном сопоставлении символов слова — вхождения и обрабатываемого слова, Вначале в работу всегда включается первая в списке формула, начальная буква слова— вхождения которой всегда хранится в ячейке с адресом 0...01, Поэтому сначала в счетчике адреса 10 блока 2 выборки левых частей формул подстановок устанавливается адрес 0Ä.01 первого символа искомого вхождения, а из ячейки второго узла памяти

30 блока 4 памяти слова с адресом 00...0, выставленном в регистре адреса 29 того же блока, через коммутатор 24 в регистр адреса

29 считывается адрес первого значащего символа обрабатываемого слова. Символы, расположенные по выставленным адресам в соответствующих узлах памяти и подлежащие сравнению, считываются в регистры символов 16 и 20 блока 3 анализа ситуации, причем в регистр 16 принимается символ слова — вхождения, а в регистр 20 — символ обрабатываемого слова. Кроме того, из поля и+1 - 2n указанной в счетчике адреса 10 ячейки узла памяти 9 блока 2 выборки левых частей формул подстановок в регистр маски 17 блока 3 анализа ситуации считывается битовая маска символа вхождения, а содержимое (2п+ 1) — го разряда той же ячейки считывается в триггер 14 блока 3 анализа ситуации. Если записанный в регистр 20 блока 3 анализа ситуации символ не является признаком конца обрабатываемого слова, (т.е, выходной сигнал схемы

И 19 данного блока ПКС=О), то проверяется выходной сигнал узла сравнения 18 того же блока, в котором производится анализ на совпадение кодов символов, записанных в регистрах символов 16 и 20 с учетом маски, 10

55 имеющейся в регистре маски 17. Выходной сигнал узла сравнения 18 формируется по следующему закону:

"="=(X1 д Хг ЧХ1 ЧХ1 дХг /m)) ) д (X1 д ХггVX1г Д Хг Чгпг)д д (X)" д Хг" VX)" д Хг" Vm p), где Х1=Х1 X1 ...X1", Хг=Хг" Хг ...Хг", М=т1аг...m> — коды, записанные соответственно в регистры 16, 20 и 17 блока 3 анализа ситуации. Если "="=1, то проверяется: является ли обнаруженное совпадение символов первым при поиске данного вхождения.

Если совпадений до этого не было, то счетчик 34 блока 5 подсчета длины вхождений находится в нуле и снимаемый с выхода схемы ИЛИ 35 данного блока сигнал ОСч=О.

В этом случае в регистр адреса 28 блока 4 памяти слова принимается адрес из регистра адреса 29 того же блока, являющийся адресом предполагаемого начала искомого вхождения, после чего, а также сразу после получения сигнала "="=1 при ОСч=1, инкрементируется содержимое счетчика 34 блока

5 подсчета длины вхождений и счетчика адреса 10 блока 2 выборки левых частей формул подстановок, тем самым подготавливая адрес для обращения к следующей ячейке узла памяти 9. Если совпавший символ был последним в слове — вхождении, то триггер

14 блока 3 анализа ситуации находится в единичном состоянии и сигнал, снимаемый

c его прямого выхода Т1=1. В этом случае дальнейшая работа устройства идет в режиме подстановки. Если T1=0, то в регистр адреса 29 блока 4 памяти слова через коммутатор 24 из узла памяти 30 считывается адрес следующего символа обрабатываемого слова, после чего повторяется процесс считывания и сравнения очередной пары символов.

При несовпадении сравниваемых символов (вых.сигнал узла сравнения 18 "="=О) необходимо проверить: не является ли какой-либо из них специальным. Если текущий символ слова — вхождения является специальным символом "/" (граница слова— итерации), то на выходе первой схемы И 15 блока 3 анализа ситуации будет сигнал

"/"=1. Если при этом триггер 21 из того же блока находится в нулевом состоянии, то обнаруженный символ "/" обозначает переднюю границу слова-итерации. В этом случае инкрементируется счетчик адреса

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

50

55 можности осуществления возврата к началу слова — итерации в случае его успешного сопоставления с просматриваемым фрагментом обрабатываемого слова, этот адрес запоминается в регистре 13 того же блока, одновременно, производится установка в единицу триггера 21 блока 3 анализа ситуации, а в регистр адреса 27 блока 4 памяти слова из регистра адреса 29 переписывается адрес текущего символа обрабатываемого слова, который необходим для продолжения поиска данного вхождения в случае несовпадения текущего фрагмента обрабатываемого слова со словом — итерацией, после чего производится переход к считыванию и анализу очередной пары символов. Если при обнаружении в слове — вхождении специального символа "/" триггер 21 блока 3 анализа ситуации находится в единичном состоянии, то это значит, что в обрабатываемом слове обнаружен фрагмент, совпадающий со словом — итерацией и необходимо проверить, не стоит ли еще рядом (справа от совпавшего) такое же буквосочетание, Для этого слово — вхождение возвращается к началу слова — итерации, адрес первого символа которого считывается в счетчик адреса 10 блока 2 выборки левых частей формул подстановок через коммутатор 11 из регистра 13 того же блока, а в регистр 27 блока 4 памяти слова заносится новый адрес возврата на случай неудачного сопоставления следующего фрагмента обрабатываемого слова со словом — итерацией, который берется из регистра 29 того же блока, после чего устройство переходит к считыванию и анализу очередной пары символов.

Если признак "/"=О, то проверяется выход схемы ИЛИ вЂ” НЕ 22 блока 3 анализа ситуации, Если и =1, то анализируемый символ обрабатываемого слова является

"пустым" и устройство его игнорирует, и считывает очередной символ обрабатываемого слова для сравнения с тем же символом слова — вхождения, Если ни один из несовпавших символов не является специальным, то значит на просмотренном участке обрабатываемого слова нужного вхождения не обнаружено. B этом случае проверяется состояние триггера 21 (выходной сигнал Т2 блока 3 анализа ситуации), Если Т2=1, то несовпавший символ слова — вхождения принадлежит слову— итерации. В этом случае слово — вхождение пригоняется вперед(к концу слова) до конца слова — итерации, который обнаруживается появлением сигнала "/"=1 на выходе схемы И 15 блока 3 анализа ситуации, затем триггер 21 того же блока сбрасывается в 0

40 и инкрементируется счетчик адреса 10 блока 2 выборки левых частей формул подстановок, тем самым устанавливая адрес следующего после слова-итерации символа вхождения, а в регистр адреса 29 блока 4 памяти слова через коммутатор 24 из регистра адреса 27 того же блока принимается хранимый там адрес возврата обрабатываемого слова в случае несовпадения его просматриваемого фрагмента со словом— итерацией, после чего устройство переходит к анализу указанных символов . Если

Т2=0, то выполняется проверка выходного сигнала ОСч блока 5 подсчета длины вхождений. Если ОСч=0. то в предыстории поиска данного вхождения не было частичного совпадения слова — вхождения и текущего фрагмента обрабатываемого слова. B этом случае берется следующий символ обрабатываемого слова и сопоставляется с тем же (первым) символом слова — вхождения, Если

ОСч=1, то перед несовпадением анализируемых символов было обнаружено частичное вхождение. В этом случае текущий символ обрабатываемого слова остается тем же, а просмотр слова — вхождения начинается сначала, для чего в счетчик адреса 10 блока 2 выборки левых частей формул подстановок через коммутатор 11 из регистра 12 того же блока считывается адрес его первого символа, кроме того, обнуляется счетчик 34 блока

5 подсчета длины вхождений. Далее устройство переходит к считыванию и анализу указанных символов.

Если при анализе очередной пары символов выходной сигнал блока 3 анализа ситуации ПКС=1, то искомое вхождение в обрабатываемом слове не обнаружено, следовательно, формула не срабатывает и устройством выполняется подготовка к включению в работу следующей формулы подстановки. Для этого в счетчик адреса 10 блока 2 выборки левых частей формул подстановок из регистра 12 того же блока через коммутатор 11 считывается адрес первого символа слова — вхождения несработавшей формулы, Затем содержимое счетчика адреса 10 декрементируется, По полученному в

10 адресу производится обращение к ячейке узла памяти 9 блока 2 выборки левых частей формул подстановок, в которой хранится адрес-метка, описанная выше, Содержимое поля 1-m данной ячейки считывается в регистр 12 того же блока, а значение ее (2п+1) — го бита признаков — в триггер 14 блока 3 анализа ситуации. После этого проверяется состояние триггера 14 блока

3 анализа ситуации (выходной сигнал Т1 блока), Если 71=1 (в триггер записан признак последней формулы алгорифма), то ус1805478

5

45

55 тройство заканчивает свою работу (не сработала последняя в списке формула). Если

Т1=0, то в работу включается следующая формула. Для этого в счетчик адреса 10 блока 2 выборки левых частей формул подстановок из регистра 12 того же блока через коммутатор 11 считывается адрес начала левой части указанной формулы и обнуляются регистр адреса 29 блока 4 памяти слова, счетчик 34 блока 5 подсчета длины вхождений и триггер 21 блока 3 анализа ситуации.

Далее производятся действия, аналогичные включению в работу первой формулы алгорифма: инкрементированием счетчика адреса 10 устанавливается адрес первого символа слова — вхождения (блок 1 выборки левых частей формул подстановок), а на регистр адреса 29 из узла памяти 30 (блок 4 памяти слова) считывается адрес первого символа обрабатываемого слова и устройство начинает поиск нового вхождения, В случае обнаружения в обрабатываемом слове фрагмента, задаваемого словом— вхождением (последний совпавший символ слова — вхождения имеет признак конца вхождения), устройство переходит в режим выполнения подстановки, В регистр адреса

25 блока 4 памяти слова из ячейки узла памяти 30, адрес которой указан в регистре адреса 29, считывается адрес символа, стоящего в цепочке обрабатываемого слова сразу после совпавшего фрагмента. К этому моменту в счетчике адреса 10 блока 2 выборки левых частей формул подстановок находится адрес ячейки узла памяти 9, в которой хранится адрес, по которому в узле памяти 7 блока 1 выборки правых частей формул подстановок расположен первый символ соответствующего слова — подстановки, Этот адрес считывается из поля (1-k) выходной информационной шины узла памяти 9 блока выборки левых частей формул подстановок в счетчик адреса 8 блока 1 выборки правых частей формул подстановок, затем, по указанному в 8 адресу, из узла памяти 7 того же блока, в регистр символов

20 блока анализа ситуации через коммутатор 23 считывается первый символ слова— подстановки. Одновременно, в регистр адреса 29 блока 4 памяти слова через коммутатор 24 из регистра адреса 28 принимается адрес первого символа совпавшего фрагмента обрабатываемого слова и инкрементируется содержимое счетчика адреса 10 блока 2 выборки левых частей формул подстановок, тем самым записывая в него адрес, по которому в узле памяти 9 того же блока хранится адрес — метка перехода к следующей формуле, включаемой в работу после завершения подстановки. После этого в узел памяти 26 блока 4 памяти слова по адресу, указанному в регистре адреса 29 того же блока, производится запись символа, имеющегося в регистре символов 20 блока 3 анализа ситуации, декрементируется содержимое счетчика 34 блока 5 подсчета длины вхождений и инкрементируется счетчик адреса 8 блока 1 выборки правых частей формул подстановок, Далее из узла памяти 7 того же блока в регистр символов

20 блока 3 анализа ситуации через коммутатор 23 считывается следующий символ подстановки.

Если считанный в регистр символов 20 блока 3 анализа ситуации символ не является признаком конца подстановки (выходной сигнал блока 3 анализа ситуации ПКС=О), то проверяется количество незамененных символов совпавшего фрагмента обрабатываемого слова, подсчитываемое в счетчике 34 блока 5 подсчета длины вхождений.

Если содержимое счетчика 34 не равно

0 (выходной сигнал блока 5 подсчета длины вхождений ОСч=1), то в регистр адреса 29 блока 4 памяти слова через коммутатор 24 из узла памяти 30 того же блока считывается адрес очередного подлежащего замене символа обрабатываемого слова и затем повторяются операции записи на его место из регистра символов 20 блока анализа ситуации текущего и чтения из узла памяти 7 блока выборки правых частей формул подстановок следующего символов подстановки. Этот цикл повторяется до тех пор, пока либо не закончится слово — подстановка, либо не будут заменены все символы совпавшего фрагмента, В случае, когда длина слова — подстановки больше длины обнаруженного вхождения, остающиеся после замены букв совпавшего фрагмента обрабатываемого слова символы дописываются на незанятый обрабатываемым словом участок узла памяти 26 блока 4 памяти слова. Это делается следующим образом. При появлении сигнала ОСч=0 в текущую ячейку узла памяти 30 блока 4 памяти слова через коммутатор 31 из счетчика адреса 32 записывается адрес первой свободной ячейки узла памяти 26 того же блока. Затем этот адрес считывается из узла памяти 30 через коммутатор 24 в регистр адреса 29 и инкрементируется содержимое счетчиков адресов 8 блока 1 выборки правых частей формул подстановок и 32 блока 4 памяти слова. После этого очередной символ подстановки записывается на указанное в регистре адреса 29 место обрабатываемого слова.

Далее проверяется ситуация переполнения узла памяти 26 блока 4 памяти слова

1805478

16 (выходной сигнал ПП блока). Если ПП=1, то устройство выходит на аварийный останов, Если ПП=О, то в регистр символов 20 считывается очередной символ подстановки, проверяется сигнал ПКС, в узел памяти 30 из счетчика адреса 32 переписывается адрес следующей свободной ячейки узла памяти

26, который затем заносится в регистр адреса 29, инкрементируются счетчики адресов

8 и 32, в узел памяти 26 записывается очередной символ подстановки. Этот цикл повторяется до тех пор, пока в регистр символов 20 блока анализа ситуации не будет считан символ, являющийся признаком конца подстановки, или не возникнет ситуация переполнения узла памяти 26 блока 4 памяти cnosa.

По окончании выполнения подстановки производится замыкание разорванного замененным фрагментом списка обрабатываемого слова, для чего в ячейку узла памяти

30 блока 4 памяти слова, адрес которой остался в регистре адреса 29, из регистра адреса 25 записывается адрес начала правой части разорванного списка.

После этого осуществляется считывание из узла памяти 9 блока 2 выборки левых частей формул подстановок в регистр 12 того же блока адреса — метки перехода к следующей формуле, а в триггер 14 блока 3 анализа ситуации соответствующего этой метке признака. Если в результате этого триггер 14 устанавливается в нулевое состояние (сигнал Т1=0), то далее производится включение в работу выбранной формулы подстановки, Если сигнал Т1=1, то сработавшая формула была заключительной и устройство заканчивает работу.

Для описания граф — схемы алгоритма работы блока 6 микропрограммного управления использованы следующие идентификаторы, УОΠ— команда установки исходных состояний блоков устройства;

ПУСК вЂ” команда запуска устройства, ПКС вЂ” признак конца обрабатываемого слова или слова — подстановки, "=" — результат сравнения символов (выходной сигнал узла сравнения 18), "/" — признак специального символа для выделения слов — итераций, — признак пустого символа, ПП вЂ” признак переполнения узла памяти 26 блока 4 памяти слова, ОСч — признак ненулевого состояния счетчика 34 блока 5 подсчета длины вхождений, Т1 — признак состояния триггера 14 блока 3 анализа ситуации, Т2 — признак состояния триггера 21 блока анализа ситуации, +1СА1 — команда инкрементирования счетчика адреса 10 блока 2 выборки левых

5 частей формул подстановок, -1СА1 — команда декрементирования счетчика адреса 10 блока 2 выборки левых частей формул подстановок, +1СА2 — команда инкрементирования

10 счетчика адреса 8 блока 1 выборки правых частей формул подстановок, +1CA3 — команда инкрементирования счетчика адреса 33 блока 4 памяти слова, ПР РС1 — команда приема информации

15 в регистр символов 16 блока 3 анализа ситуации, ПР РС2 — команда приема информации в регистр символов 20 блока 3 анализа ситуации, 20 ПР1 — команда приема информации в регистр 12 блока 2 выборки левых частей формул подстановок, ПР2 — команда приема информации в регистр 13 блока 2 выборки левых частей

25 формул подстановок, ПРЗ вЂ” команда приема информации в регистр адреса 25 блока 4 памяти слова, ПР4 — команда приема информации в регистр адреса 27 блока 4 памяти слова, 30 ПР5 — команда приема информации в регистр адреса 28 блока 4 памяти слова, ПР6 — команда приема информации в регистр адреса 29 блока 4 памяти слова, +1СЧ вЂ” команда инкрементирования

35 счетчика 34 блока 5. подсчета длины вхождений, -1СЧ вЂ” команда декрементирования счетчика 34 блока 5 подсчета длины вхождений, 40 УО5 — команда установки в ноль счетчика 34 блока 5 подсчета длины вхождений, УО4 — команда установки в ноль регистра адреса 29 блока 4 памяти слова, УОЗ вЂ” команда установки в ноль тригге45 ра 21 блока 3 анализа ситуации, У1 — команда управления коммутатором

11 блока 2 выборки левых частей формул подстановок, У2 — команда управления коммутатором

50 23 блока 3 анализа ситуации, УЗ вЂ” команда управления коммутатором

24 блока 4 памяти слова, У4 — команда управления коммутатором

31 блока 4 памяти слова, 55 ЧТ1 — команда чтения информации из узла памяти 9 блока 2 выборки левых частей формул подстановок, ЧТ2 — команда чтения информации из узла памяти 7 блока 1 выборки правых частей формул подстановок, 18

1805478

ЧТЗ вЂ” команда чтения информации из узла памяти 30 блока 4 памяти слова, ЧТ4 — команда чтения информации из узла памяти 26 блока 4 памяти слова

ЗПЗ вЂ” команда записи информации в узел памяти 30 блока 4 памяти слова

ЗП4 — команда записи информации в узел памяти 26 блока 4 памяти слова

Авар.ост. — признак аварийной остановки устройства.

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

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

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

1805478

55 памяти, к входу декремента и к счетному входу счетчика, информационные входы группы блока подключены соответственно к информационным входам счетчика, выход которого подключен к адресному входу узла памяти, выходы которого подключены соответственно к выходам блока, блок подсчета длины заменяемого фрагмента слова содержит счетчик и элемент ИЛИ, причем вход инкремента, вход декремента и вход установки в исходное состояние блока подключены соответственно к входу инкремента, к входу декремента и к входу установки в "0" счетчика; информационные выходы которого подключены к входам элемента ИЛИ, выход которого подключен к выходу блока, причем блок анализа подстановок содержит два регистра символа, регистр маски, два триггера, узел сравнения, коммутатор, два элемента И и элемент ИЛИ, причем в блоке анализа подстановок вход чтения, вход установки в исходное состояние, первый, второй и третий входы режима блока подключены соответственно к входу синхронизации первого триггера, к входам установки в "0" и в "1" второго триггера, к входу записи — чтения первого регистра символа, выходы которого подключены к информационным входам первой группы узла сравнения, к входам первого элемента И, к входам элемента ИЛИ и к выходам группы блока, вход признака приема символов блока подключен к входам записи-чтения второго регистра слова и регистра маски, выходы которого подключены соответственно к управляющим входам узла сравнения, информационные входы с первого по а-й (где а — разрядность символа) второй группы блока подключены соответственно к информационным входам второго регистра слова, выходы которого подключены к входам второго элемента И и к информационным входам второй группы узла сравнения, информационные входы с (а+1)-го по 2а-й второй группы блока подключены соответственно к информационным входам регистра маски,(2а+1)-й информационный вход второй группы блока подключен к информационному входу первого триггера, выход которого подключен к первому выходу блока, информационные входы второй и

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

1805478

Ф 1СФ

1ИР ppggg

+ 1И!

У7

П12

РбРПЧ УИР

1805478

ЧТ1 77

ПРИ бР tt

Т2

ПР3

ПРс

Ф 1САЗ

902. 5

9 ЯС ПР4

Н35АС ЧР ПРб

ИЭ V 3 д2 lЧ РС2ДР2 оЮЧ ЮС

1805478

Cupuc::/

vrt =/naos/:=/ уг:=э иэ:=/ л дгг:=/

И:=ФЮа /=/

-аю:=/ ю

vt/:=/.ж:=/

/р ж:=/i :=/

4/

nab /tv:-/

4/ аю =/ р 3I

zu и:=/-cv:=/

/Й:=/

/ Ю

ФЖ

Jl

У4 =Фюзи =/

ЛУ лт:=/,/4 у

ЛР

Л

/Ф аж:=/

Составитель Е. Леонов

Техред М,Моргентал

Корректор Jl. Пилипенко

Редактор

Заказ 943 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

4лу,г

/ аю:=/и:=vd иу: ne: /

AC

/Г Ф

/ /

vugg:=/ //ю- =/ е// naca:

rz:=/ vs: -/

naos::/кг:=v/

n//:=//а/:=/

z/

vl: / vtg:=/

n acz:=/ 4

У/--ЮФ и :=/

n e.=/. Х

7Т

e/ncc : / юд:=/