Устройство для реализации подстановок Советский патент 1993 года по МПК G06F15/31 G06F15/16 

ел

с

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

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

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

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

Блок 2 выборки левых частей формул подстановок содержит узел памяти 9, реверсивный счетчик адреса 10, коммутатор 11, первый и второй регистры 12, 13, причем вход чтения, первый вход режима, вход инкремента адреса, вход декремента адреса, второй, третий и четвертый входы режима блока подключены соответственно ко входу разрешения чтения узла памяти, входу разрешения приема информации в счетчик адреса, входу инкремента счетчика адреса, входу декремента счетчика адреса, управляющему входу коммутатора, входу разрешесо

О

ел

XI 00

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

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

Блок 4 памяти слова содержит первый 26 и второй 30 узлы памяти, а первый 25, второй 27, третий 28 и четвертый 29 регистры адреса, счетчик адреса 33, первый 24 и второй 31 коммутаторы и элемент И 32, причем в блоке памяти слова с первого по шестой входы режима, первый вход записи,

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

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

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

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

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

Блок 5 подсчета длины вхождений со0 держит счетчик 34 и элемент ИЛИ 35, причем входы инкремента, декремента и установки в исходное состояние блока подключены соответственно ко входам инкремента, декремента и установки в ноль счетчика,

5 информационные выходы которого подключены ко входам элемента ИЛИ, выход которого подключен к выходу блока.

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

На фиг.1 изображена структурная схема устройства; на фиг.2 - структурные схемы блока выборки правых частей формул под- становок и блока подсчета длины вхождений; на фиг.З - структурная схема блока выборки левых частей формул подстановок; на фиг.4 - структурная схема блока анализа ситуации; на фиг.5 - структурная схема бло- ка памяти слов; на фиг.6 - граф-схема алгоритма работы блока микропрограммного управления.

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

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

Работа формулы подстановки заключается в выполнении двух операций:

- распознавания вхождения левой час- ти формулы в обрабатываемое слово;

- подстановки правой части формулы в обрабатываемое слово вместо найденного предыдущей операцией фрагмента.

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

Конечный список формул подстановок является системой тогда, когда на нем заданы условия включения формул списка в работу. Для алгорифма Маркова условия включения формул в работу определены следующим образом:

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

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

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

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

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

Рассмотрим пример нормального алгорифма:

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

вх.вых. метки

метка формулаМ1 М2

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

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

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

a pb ty f d - aba, будет реализована следующим образом:

М0М1МоМ1М1М0

a pbij}r)d ,

причем маска значащих символов a, b, d будет М0 00...О, а маска для алфавитных переменных- Mi 11...1.

Битовые ансамбли применяются в случаях необходимости осуществления замены фрагментов обрабатываемого слова, содержащего заданный набор битов внутри кодов символов.-Выделение значащих битов каждого символа слова-вхождения производится с помощью маскирования этих битов нулевыми масками, а биты, не имеющие в данной ситуации значения, при этом маскируются единицами. Например, необходимо выделить фрагмент, в котором значимыми являются первый и четвертый биты кода первого символа и пятый бит кода третьего символа. Маски символов левой части формулы подстановки будут представлены в следующем виде.

символы

биты1-й 2-й 3-й

1011

2111

3111

4011

5110

6111

7111

8111

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

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

/ab/, a/b/c,

где символ / не входит в рабочие алфавиты задаваемых алгорифмов и обозначает

границы слов-итераций.

Узел памяти 9 блока 2 выборки левых частей формул подстановок предназначен для хранения левых частей формул подстановок. В каждой его ячейке хранится очередной символ вхождения (п бит), его маска (п бит) и признак (1 бит), который равен 1 в случае, когда данный символ является последним в слове-вхождении. Кроме того, перед первым символом каждого словавхождения в ячейке с адресом Ao Ai -1 хранится адрес-метка (т бит, m 2п-1) начала слова-вхождения той формулы, на которую осуществляется переход в случае несрабатывания текущей и признак (1 бит), который

равен 1 только тогда, когда текущая формула является последней формулой алгорифма; после последнего символа каждого слова-вхождения в ячейке с адресом Ар Ак +1 находится адрес (k, бит, k 2п-1)

первого символа правой части данной формулы, которая хранится в узле памяти блока 2 выборки правых частей формул подстановок, а в следующей ячейке, адрес которой As Ap +1, хранится адрес метка (т бит) начала левой части формулы подстановки, на которую осуществляется переход при срабатывании данной формулы, причем разряд признаков данной ячейки равен 1 только тогда, когда текущая формула - заключительная.

В узле памяти 7 блока 1 выборки правых частей формул подстановок хранятся символы слов- подстановок всех формул алгорифма. Каждое слово-подстановка

завершается специальным символом - признаком конца слова (ПКС), имеющим единицы во всех разрядах своего кода.

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

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

Это - пустой символ а, используемый для записи формул вида:

- Т;

S-,

(кодируется нулями по всей длине кода), и. символ, применяемый для выделения границ слов-итераций (кодируется аналогично ПКС).

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

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

Процесс поиска в обрабатываемом слове вхождения, заданного включенной в работу формулой подстановки, заключается в поочередном сопоставлении символов слова-вхождения и обрабатываемого слова. Вначале в работу всегда включается первая в списке формула, начальная буква слова- вхождения которой всегда хранится в ячейке с адресом 0...01, Поэтому сначала в счетчике адреса 10 блока 2 выборки левых частей формул подстановок устанавливается адрес 0...01 первого символа искомого вхождения, а из ячейки второго узла памяти 30 блока 4 памяти слова с адресом 00...О, выставленном в регистре адреса 29 того же блока, через коммутатор 24 в регистр адреса 29 считывается адрес первого значащего символа обрабатываемого слова. Символы, расположенные по выставленным адресам в соответствующих узлах памяти и подлежащие сравнению, считываются в регистры символов 16 и 20 блока 3 анализа ситуации, причем в регистр 16 принимается символ слова-вхождения, а в регистр 20 - символ обрабатываемого слова. Кроме того, из поля п+1 - 2п указанной в счетчике адреса 10 ячейки узла памяти 9 блока 2 выборки левых частей формул подстановок в регистр маски 17 блока 3 анализа ситуации считывается битовая маска символа вхождения, а содержимое (2п+ 1)-го разряда той же ячейки считывается в триггер 14 блока 3 анализа ситуации. Если записанный в регистр 20 блока 3 анализа ситуации символ не является признаком конца обрабатываемого слова, (т.е. выходной сигнал схемы И 19 данного блока ), то проверяется выходной сигнал узла сравнения 18 того же блока, в котором производится анализ на совпадение кодов символов, записанных в регистрах символов 16 и 20 с учетом маски,

имеющейся в регистре маски 17. Выходной сигнал узла сравнения 18 формируется по следующему закону: (Xi1 д Х21 VXi1 V Xi1 д Х21 V mi) / d(Xi2d X22VXi2 5 X22Vm20 ... 5(Xin 5X2nV5 in 5X2nVmn).

где Xi Xi1Xi2...Xin, X2 X21X22...X2n, ...mn - коды, записанные соответственнов регистры 16,20 и 17 блока 3 анализа ситуации. Если 1, то проверяется: является ли обнаруженное совпадение символов первым при поиске данного вхождения. Если совпадений до этого не было, то счетчик 34 блока 5 подсчета длины вхождений находится в нуле и снимаемый с выхода схемы ИЛИ 35 данного блока сигнал . В этом случае в регистр адреса 28 блока 4 памяти слова принимается адрес из регистра адреса 29 того же блока, являющийся адресом предполагаемого начала искомого вхождения, после чего, а также сразу после получения сигнала 1 при , инкре- ментируется содержимое счетчика 34 блока

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

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

считывания и сравнения очередной пары символов.

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

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

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

Если признак , то проверяется выход схемы ИЛИ-НЕ 22 блока 3 анализа си- туации. Если , то анализируемый символ обрабатываемого слова является пустым и устройство его игнорирует, и считывает очередной символ обрабатываемого слова для сравнения с тем же симво- лом слова-вхождения,

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

и инкрементируется счетчик адреса 10 блока 2 выборки левых частей формул подстановок, тем самым устанавливая адрес следующего после слова-итерации символа вхождения, а в регистр адреса 29 блока 4 памяти слова через коммутатор 24 из регистра адреса 27 того же блока принимается хранимый там адрес возврата обрабатываемого слова в случае несовпадения его просматриваемого фрагмента со словом- итерацией, после чего устройство переходит к анализу указанных символов. Если , то выполняется проверка выходного сигнала ОСч блока 5 подсчета длины вхождений. Если , то в предыстории поиска данного вхождения не было частичного совпадения слова-вхождения и текущего фрагмента обрабатываемого слова. В этом случае берется следующий символ обрабатываемого слова и сопоставляется с тем же (первым) символом слова-вхождения. Если , то перед несовпадением анализируемых символов было обнаружено частичное вхождение. В этом случае текущий символ обрабатываемого слова остается тем же, а просмотр слова-вхождения начинается сначала, для чего в счетчик адреса 10 блока 2 выборки левых частей формул подстановок через коммутатор 11 из регистра 12 того же блока считывается адрес его первого символа, кроме того, обнуляется счетчик 34 блока 5 подсчета длины вхождений. Далее устройство переходит к считыванию и анализу указанных символов.

Если при анализе очередной пары символов выходной сигнал блока 3 анализа ситуации , то искомое вхождение в обрабатываемом слове не обнаружено, следовательно, формула не срабатывает и устройством выполняется подготовка к включению в работу следующей формулы подстановки, Для этого в счетчик адреса 10 блока 2 выборки левых частей формул подстановок из регистра 12 того же блока через коммутатор 11 считывается адрес первого символа слова-вхождения несработавшей формулы. Затем содержимое счетчика адреса 10 декрементируется. По полученному в 10 адресу производится обращение к ячейке узла памяти 9 блока 2 выборки левых частей формул подстановок, в которой хранится адрес-метка, описанная выше. Содержимое поля 1-го данной ячейки считывается в регистр 12 того же блока, а значение ее (2п+1)-го бита признаков - в триггер 14 блока 3 анализа ситуации. После этого проверяется состояние триггера 14 блока 3 анализа ситуации (выходной сигнал Т1 блока). Если Т1 1 (в триггер записан признак последней формулы алгорифма), то устройство заканчивает свою работу (не сработала последняя в списке формула). Если , то в работу включается следующая формула. Для этого в счетчик адреса 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 не равно О (выходной сигнал блока 5 подсчета длины вхождений ), то в регистр адреса 29 блока 4 памяти слова через коммутатор 24 из узла памяти 30 того же блока считывается адрес очередного подлежащего замене символа обрабатываемого слова и затем повторяются операции записи на его место из регистра символов 20 блока анализа ситуации текущего и чтения из узла памяти 7 блока выборки правых частей формул подстановок следующего символов подстановки. Этот цикл повторяется до тех пор, пока либо не закончится слово-подстановка, либо не будут заменены все символы совпавшего фрагмента.

В случае, когда длина слова-подстанов-. ки больше длины обнаруженного вхождения, остающиеся после замены букв совпавшего фрагмента обрабатываемого слова символы дописываются на незанятый обрабатываемым словом участок узла памяти 26 блока 4 памяти слова. Это делается следующим образом. При появлении сигнала в текущую ячейку узла памяти 30 блока 4 памяти слова через коммутатор 31 из счетчика адреса 32 записывается адрес первой свободной ячейки узла памяти 26 того же блока. Затем этот адрес считывается из узла памяти 30 через коммутатор 24 в регистр адреса 29 и инкрементируется содержимое счетчиков адресов 8 блока 1 выборки правых частей формул подстановок и 32 блока 4 памяти слова. После этого очередной символ подстановки записывается на указанное в регистре адреса 29 место обрабатываемого слова.

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

(выходной сигнал ПП блока). Если , то устройство выходит на аварийный останов, Если , то в регистр символов 20 считывается очередной символ подстановки, проверяется сигнал ПКС, в узел памяти 30 из счетчика адреса 32 переписывается адрес следующей свободной ячейки узла памяти 26, который затем заносится в регистр адреса 29, инкрементируются счетчики адресов 8 и 32, в узел памяти 26 записывается оче- редной символ подстановки. Этот цикл повторяется до тех пор, пока в регистр символов 20 блока анализа ситуации не будет считан символ, являющийся признаком конца подстановки, или не возникнет ситу- ация переполнения узла памяти 26 блока 4 памяти слова.

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

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

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

Для описания граф-схемы алгоритма работы блока 6 микропрограммного управления использованы следующие идентификаторы.

УОО - команда установки исходных состояний блоков устройства;

ПУСК - команда запуска устройства,

ПКС - признак конца обрабатываемого слова или слова-подстановки,

- результат сравнения символов (выходной сигнал узла сравнения 18),

/ - признак специального символа для выделения слов-итераций, - признак пустого символа,

ПП - признак переполнения узла памяти 26 блока 4 памяти слова,

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

Т1 - признак состояния триггера 14 блока 3 анализа ситуации,

Т2 - признак состояния триггера 21 блока анализа ситуации,

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

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

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

+1САЗ - команда инкрементирования счетчика адреса 33 блока 4 памяти слова,

ПР РС1 - команда приема информации в регистр символов 16 блока 3 анализа ситуации,

ПР РС2 - команда приема информации в регистр символов 20 блока 3 анализа ситуации,

ПР1 - команда приема информации в регистр 12 блока 2 выборки левых частей формул подстановок ,

ПР2 - команда приема информации в регистр 13 блока 2 выборки левых частей формул подстановок,

ПРЗ - команда приема информации в регистр адреса 25 блока 4 памяти слова,

ПР4 - команда приема информации в регистр адреса 27 блока 4 памяти слова,

ПР5 - команда приема информации в регистр адреса 28 блока 4 памяти слова,

ПР6 - команда приема информации в регистр адреса 29 блока 4 памяти слова,

+1СЧ - команда инкрементирования счетчика 34 блока 5. подсчета длины вхождений,

-1СЧ - команда декрементирования счетчика 34 блока 5 подсчета длины вхождений,

У05 - команда установки в ноль счетчика 34 блока 5 подсчета длины вхождений,

У04 - команда установки в ноль регистра адреса 29 блока 4 памяти слова,

УОЗ - команда установки в ноль триггера 21 блока 3 анализа ситуации,

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

У2 - команда управления коммутатором

23 блока 3 анализа ситуации,

УЗ - команда управления коммутатором

24 блока 4 памяти слова,

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

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

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

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

ЧТ4 - команда чтения информации из узла памяти 26 блока 4 памяти слова

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

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

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

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

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

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

5 первому-четвертому входам режима, к первому входу чтения, пятому входу режима, к входу инкремента адреса выборки, к шестому входу режима, второму входу чтения, второму входу записи и входу установки в

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

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

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

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

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

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

ИЭ65ЛЧ +1™2ЛРСА2

V72:

L

7

BBAC

5/4 Г

+1M Y-7W

,У№

i Г

J

JJ

$C4

i

J

Фиг. 2

3L

;j

ПР2

J

/7/°/

со r- т in о со