Устройство для лексического анализа символьного текста Советский патент 1985 года по МПК G06F17/27 G06F9/45 

дам считьшания блоков памяти текстов подстановок, выход коммутатора подключен к информационному входу второго регистра, четвертый, пятый, . шестой и седьмой выходы блока синхрочизации подключены соответственно к четвертому, пятому, шестому и седь мому входам блока управления подстановкой, который содержит два триггера, четыре элемента И, элемент ИИЛИ-НЕ, выход первого элемента И соединен с единичными входами первого и второго триггеров и с первым вы ходом блока управления подстановкой, первый и второй входы которого соеди нены соответственно с первым нулевым входом второго триггера я с первым входом второго элемента И, третий вход подключен к первым входам третьего элемента И и элемента И-ВДИ-НЕ второй вход которого является четвертым входом блока управления подстановкой, пятый и шестой входы кото рого являтатся соответственно первым BTopr iM входш- и первого элемента И, седьмой вход является нулевым входом первого триггера, единичный выход ко торого соединен с вторым входом третьего элемента И, выход которого является вторым выходом блока управления подстановкой, третий выход которого и первый вход четвертого элемента И соединены с единичным выходом второго триггера, нулевой выход которого .нен с третьим входом элемента И-ИЛИ--НЕ, четвертый вход которого и пятый выход блока управления подстановкой подключены к выходу четвертого элемента И, вторые входы второго и чет вертого элементов И соединены с нулевым выходом первого триггера, выход второго эле13 мента И соединен с вторым нулевым входом второго триггера, выход элемента И-Ш1И-НЕ является четвертым выходом блока управления подстановкой. 2,- Устройство по п. 1, о т л и ч аю щ е е с я тем, что блок синхронизации содержит дешифратор, три триггера, четыре элемента И, элемент ИЛИ и генератор синхроимпульсов, выход соторого соединен с синхронизирующим входом первого триггера, с первыми входами первого и второго элементов И и с третьим выходом блока, вход дешифратора является входом блока, первый выход дешифратора подключен к первому входу третьего элемента И, второй выход подключен к единичному входу второго триггера и к седьмому выходу блока, третий и четвертьш выходы дешифратора соединены соответственно с нулевым и единичным входами третьего триггера, пятый выход является пятам выходом блока, нулевой выход третьего триггера соединен с вторым входом третьего элемента И и с шестым выходом блока, выход третьего элемента И под1слючен к второму входу первого элемента И, к нулевому входу второго триггера и к первому выходу блока, выходы первого и второго элементов И соединены соответственно с входами элемента ИЛИ, выход Kotoрого является четвертым выходом блока, единичный выход второго триггера подключен к установочному входу первого триггера и к первому входу четвертого элемента И,-второй вход которого соединен с нулевым выходом первого триггера, выход четвертого элемента И подключен к второму входу второго элемента И и к второму выходу блока.

1. УСТРОЙСТВО ДЛЯ ЛЕКСИЧЕСКОГО АНАЛИЗА СИМВОЛЬНОГО ТЕКСТА, содержащее два регистра, шифратор, первый коммутатор, первый информационный вход которого и вход шифратора соединены с выходами разрядов первого регистра, информационный вход которого является информационньм входом устройства, выход шифратора соединен с вторым информационным входом коммутатора и с входом блока синхронизации, первый и второй выходы которого соединены соответственно с первым и вторым разрешающими входами первого коммутатора, третий выход соединен с синхронизируюгдим входом первого регистра, выходы разрядов второго регистра являются информационным выходом устройства, о тличающе еся тем, что, с целью повышения быстродействия, в него введены блоки сравнения, блоки памяти текстов подстановок, шифратор текста подстановки, второй и третий . коммутаторы, блок управления подстановкой, элемент ИЛИ-НЕ и элемент ИЛИ, выход которого соединен с первым входом блока управления подстановкой, первый выход которого соединен с разрешаюнщми входам -: блоков сравнения и с адресными входами блоков памяти текстов подстановок, выход каждого блока сравнения соединен с соответствующими входами элемента ИЛИ-НЕ, шифратора текста подстановки, и с первым входом разрешения считывания соответствующего блока памяти текстов подстановок, второй вход разрешения считывания которого соединен с третьим выходом блока синхронизации, выход элемента ИЛИ-НЕ соединен с вторым входом блока управления подста(Л новкой, третий вход которого соединен с третьим выходом блока синхронизации, с: выходы окончания вывода блоков памяти текстов подстановок подключены соответственно к входам элемента ИЛИ, информационные выходы соединены соответственно с информационными входами второго коммутатора, разрешающий вход 00 которого соединен с.выходом шифрато-«4 ра текста подстановки, выход подклю чен к первому информационному входу ы третьего коммутатора, информационные входы блоков сравнения и второй информационный вход третьего коммутатора соединены с выходом первого коммутатора, синхронизирующие входы блоков сравнения соединены с вторым выходом блока управления подстанов- i кой третий и четвертый выходы которого соединены соответственно с разг решающим входом третьго коммутатора и с синхронизирующим входом второго регистра, пятый выход подключен к входу блокировки записи первого регистра и к.третьим разрешающим вхо

1

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

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

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

71

коммутатора 11. На управляющий вход коммутатора 11 с выхода блока 6 поступает нулевой сигнал, так как триггер 28 находится в нулевом состоянии (эт.о его исходное состояние).. При нулевом значении сигнала на управляющем входе коммутатор 11 передает информацию на свой выход с второго информационного входа, двоичньм код информационного символа записывается в регистр 2 при поступлении очередно импульса на его синхронизирующий вхо

Формирование синхроимпульса записи в регистр 2 в этом режиме осуществляется следующим образом. Импульсы с выхода генератора 23 синхроимпульсов (фиг.8, а) поступают через эле мент И 20 (фиг.2) и элемент ИЛИ 22 на выход блока 4 синхронизации, так как на выходе первого элемента И 16 в этом режиме присутствует единичный сигнал. Далее эти импульсы поступают на вход элемента И-ИПИ НЕ 33 в блоке бив инвертированном виде поступают на выход блока 6 и далее на синхронизирующий вход регистра 2, поскольку на входе элемента Й-ИЛИ-НЕ 33 присутствует разрешающий единичный сигнал с нулевого выхода триггера 28 подстановки.

Если очередной символ является разделителем, то единичный сигнал с второго выхода дешифратора 14 (фиг.2) устанавливает триггер 17 в единичное состояние. Триггер 18 в исходном состоянии находится в нулевом состоянии, поэтому с его нулевого выхода на вход элемента И 19 подается единичный сигнал. Так как и на другом входе элемента И 19 присутствует единичный сигнал с триггера 17, то единичный сигнал формируется на выходе элемента И 19. Этот управл)4ющий сигнал выхода блока 4 синхронизациипоступает на вход коммутатора 5 и обеспечивает передачу с выхода шифратора 3, соответствующего внутреннему разделителю. Так же, как и в первом режиме, этот код поступает через коммутатор -11 на информационный вход регистра 2. Управляющий сигнал с выхода элемента И 19 поступает также на второй вход элемента И 21, обеспечивая прохождение через него очередного импульса, кот6 рый проходит через описанные для первого режима цепи и поступает на синхронизирующий вход регистра 2. При

738

этом производится запись кода внутреннего разделителя в регистр 2. Если за первым символом разделителя последуют тоже символы разделителей, то их запись в регистр 2 будет заблокирована, так как при поступлении очередного импульса на вход триггера 18 он переходит в единичное состояние. При этом на выходе элемецта И 19 формируется нулевой сигнал, который блокирует передачу кода внутреннего разделителя через коммутатор 5 и запрещает подачу импульсов на синхронизирующий вход регистра 2. Оба триггера 17 и 18 сбрасываются в исходное состояние при поступлении информационного символа.

Если входной символ определяет начало комментария, то единичный сигнал формируется только на третьем выходе дешифратора 14, устанавливая триггер 15 в единичное состояние. Нулевой сигнал с нулевого выхода триггера 15 запирает элемент И 16, в результате чего блокируется работа коммутатора 5 и элемента И 16. Поэтому, если в дальнейшем на вход устройства, находящегося в режиме комментарий, поступают информационные .символы, они не будут передаваться для записи в регистр 2 и его состояние не изменится. Устройство выходит из этого режима комментарий при поступлении символа четвертой группы конец комментария. При этом триггер 15 комментария переводится в исходное нулевое состояние.

Если входной символ является маркером ключевого слова, то единичный сигнал вырабатывается только на пятом выходе дешифратора 14, и устройство переводится в режим подстановки. Код маркера в регистр 2 не записывается, так как его передача через коммутатор 5 блокируется нулевым сигналом с выхода элемента И 16, Б случае, если триггер 15 находится в нулевом состоянии, на выходе элемента И 29 при поступлении маркера формируется единичный сигнал (фиг.1,в), по которому триггеры 27 и 28 переводятся в единичное состояние (фи.8,г,к), узлы 34 и 39 памяти всех блоков 7 и 8. устанавливаются в начальное состояние . Единичный сигнал с единичного выхода триггера 27 обеспечивает выдачу синхроимпульсов на второй выход блока 6 управления подстановкой через

91187

шестой элемент И 30 (фиг.8,д) для осуществления проверки на совпадение символов входного ключевого слова с символами эталонных слов, хранимых в узлах 34 памяти. При поступлении j с в 1хода регистра 1 информационныхсимволов, составляющих входное кгиочевое слово, они проходят через коммутатор 5, так как на выходе элемента И 16 при считывании символов первой ю группы п 1исутствует единичный разрешающий сигнал. Код очередного символа входного ключевого слова одновременно поступает на вход схемы 35 сравнения каждого из блоков 7 проверч5 ки ключевых слов. Все блоки 7 работают параллельно, так как на каждый из них поступают управляющие сигналы с блоков 6 управления подстановкой.

Рассмотрим работу одного из блоков 7. После поступления сигнала начальной установки на вход узла 34 памяти его счетчик 44 адреса устанавливается в исходное нулевое состояние, при этом из регистров 43 счл-1тывается первый символ эталонного ключевого слова, который поступает на вход мы 35 сравнения (фиг.5). Если коды на входах схемы 35 совпадают, то на ее выходе вырабатывается единичный 30 сигнал (фиг.8,е). В этом случае при поступлении первого синхроимпульса на вход триггера 37 он устанавливается в единичное состояние (фиг.8,и). Егопрохождение: через элемент И 38, 35 обеспечивает разрешшощий сигнал с единичного выхода первого триггера 36, установленного в единичное состояние по сигналу с выхода элемента И 29 блока 6 (фиг. 8,ж). Если -все 40 символы входного ключевого слова совпали с символами эталонного слова, то по окончании проверки триггера 37 останется в единичном состоянии. Если хотя бы один из символов не совпал с 45 эталонным, то триггер 37 по нулевому сигналу с выхода элемента И 38 будет сброшен в нулевое состояние. Единичный сигнал с нулевого выхода триггера 37 сбросит в нуль триггер 36. В ре- 50 зультате .этого элемент И 38 будет в дальнейшем заперт, и триггер 37 останется в нулевом состоянии, даже если следующие символы входного к,пючевого слова будут совпадать с сим- 55 волш-1и эталонного слова.

Поскольку в каждом из блоков 7 хранятся разные эталонные ключевые сло7310

на, то разрешающий сигнал, указывающий на полное совпадение входного ключевого слова с эталонным, по окончании проверки будет присутствовать только на выходе одного из блоков 7, Конец входного ключевого слова наступает, когда очередной символ, считанный с Выхода регистра 1, окажется разделителем. Единичный сигнал с второго выхода дешифратора 14 поступает на вход триггера 27 в блоке 6 и переводит его в нулевое состояние (фиг,8,г). На этом заканчивается этап проверки ключевого слова. На этом этапе входные символы ключевого слова считывались из регистра 1, но их запись в регистр 2 не производилась, так как оба элемента И, входящие в состав элемента И-ИЛИ-НЕ 33, были заперты нулевыми сигналами с выхода элемента И 31 (фиг.8,л) и с нулевого выхода триггера 28. На втором этапе в режиме подстановки единичный сигнал с выхода элемента И 31 обеспечивает прохождение синхроимпульсов через элемент И-ИПИ-НЕ 33 (фиг.8,м) на синхронизирующий вход регистра 2, Кроме того, этот управляющий сигнал обеспечивает разрешение считывания текстов подстановок из блоков 8 и одновременно блокирует запись в регистр 1 новых символов входной символьной строки., .

Разрешаю1щй сигнал с выхода блока 6 поступает на вход элемента И 42 в калщом блоке 8. Другой разрешающий сигнал, вырабатываемый на выходе только одного блока 7, поступает на вход- элемента И 42 только в блоке 8. В результате синхроимпульсы пройдут через элемент И 42 только в одном блоке 8 и обеспечат считывание выбранного .текста подстановки из его узла 39 памяти. Считываемый текст подстановки посимвольно поступает с информационного выхода соответствующего блока 8 на одноименный информационный вход коммутатора 10. Шифратор 9 формирует двоичный код номера блока 8, этот код поступает на управляющий вход коммутатора 10 и обеспечивает подключение к выходу коммутатора 10 его соответствующего информационного входа. Б результате этого символы выбранного текста подстановки поочередно подаются на информационный вход регистра 2 для записи в него через коммутатор 11 блока управления подстановкой; на фиг.5 структурная схема блока срав нения; на фиг.6 - структурная схема блока памяти текста подстановки; на фиг.7 - схема узла памяти; на фиг.8 - временные диаграммы, поясняю щие работу устройства. .Устройство содержит регистры 1 и шифратор 3, блок 4 синхронизации, коммутатор 5, блок 6 управления подстановкой, блоки 7 сравнения, блоки 8 памяти текстов подстановок, шифратор 9 текста подстановки, коммутатор 10, коммутатор 11, элемент ИЛИ-НЕ 12 элемент ИЛИ 13, дешифратор 14, триггер 15, элемент И 16, триггеры 17 и 18, элементы И 19-21, элемент ИЛИ 22 генератор 23 синхроимпульсов, группы 24 и 25 элементов И, группу 26 элеме тов ИЛИ, триггеры 27 и 28, элементы И 29-32, -элемент И-ИЛИ-НЕ 33, узел 34памяти, схему 35 сравнения, триггеры 36 и 37, элемент И 38, узел .39 памяти, схему 40 сравнения, узел 41 памяти константы, элемент И 42, группу 43 регистров, счетчик 44 адре са. Работу устройства поясняют диагра мы, изображенные на фиг.8, где а диаграмма на выходе генератора 23 синхроимпульсов; б - диаграмма на выходе регистра 1 в - диаграмма на выходе элемента И 29 блока 6 управления подстановкой; г - диаграмма на единичном выходе триггера 27; д - диаграмма на выходе элемента И 30; е - диаграмма на выходе схемы 35сравнения; ж - диаграмма на выходе триггера 36; и - диаграмма на единичном выходе триггера 37; к диаграмма на единичном выходе триггера 28; л - диаграмма на выходе элемента И 31; м - диаграмма на выходе элемента И-ИЛИ-НЕ 33; н диаграмма на выходе схемы 40 сравнения; п - диаграмма на выходе регис тра 2. Регистр 1 предназначен для хранения ДВОИЧНОГО кода очередного анализируемого символа из входной строки символов. На вход регист за 1 поступают символы исходного текста (программы, микропрограммы пользователя) например, из буферной памяти (не показана). Регистр 2 предназначен для хранения очередного символа выходного сжа того текста, содержащего только дексемы (последовательности символов. 73 - . 4 имеющие смысловое значение для конкретного языка микропрограммирования), отдаленные друг от друга символами раздели елей., .причем выходной текст может содержать вновь подставленные лексимы или их последовательность вместо выделенных ключевых слов исходного текста. Шифратор 3 предназначен для выработки управляющего кода по коду очередного символа входного текста для управления грамматическим разбором входного символьного текста с целью выявления смысловых конструкций языка микропрограммирования. Блок4 синхронизации предназначен для выработки управляющих сигналов по управляющему коду, поступающему с шифратора 3, разрешающих либо пропуск символа из регистра 1 в ре гистр 2, либо запись кода символа внутреннего разделителя с выхода шифратора 3в регистр 2, либо игнорирование последовательности входных символов их регистра 1, либо подстановку вместо группы входных сигналов из регистра 1, определяемых как ключевое слово, заранее заданной последовательности символов, записываемых с вы хода одного из блоков 8 регистр 2. Коммутатор 5 предназначен для передачи на свой выход одного из двух двоичных кодов, присутствующих на его информационных входах, в зависимости от наличия разрешающего сигнала на одном из двух его управляющих входах. Блок 6 управления подстановкой предназначен для формирования управляющих сигналов при выработке блоком 4синхронизации управляющего сигнала, выделяющего начало ключевого слова, с целью сравнения его с эталонными ключевыми словами и, в случае совпадения входного ключевого слова с одним из них - осуществления его замены на заранее определенный символьный, текст. Каждь й из блоков 7 предназначен для выработки.управляющего сигнала в случае совпадения входного ключевого слова с соответствующим эталонным словом, хранящимся в данном блоке. . Каждый блок 8 предназначен для выдачи соответствующего (заранее определенного и хранящегося в нем) текста подстановки в регистр 2 в случае совпадения входного ключевого слова с эталонным, хранящимся в одноименно блоке 7. Шифратор 9 предназначен для форми рования двоичного кода номера того блока проверки ключевого слова, на выходе которого выработан единичный сигнал совпадения принятого ключевого слова с одним из эталонных. Такой сигнал может быть выработан всегда только на выходе одного из блоков 7. Поэтому шифратор 9 фактически обе печивает преобразование унитарного кода на его выходе в двоичный код на его выходе. Коммутатор 10 предназначен для пе редачи на свой выход символов текста подстановки с одного из,своих информационных входов в зависимости от двоичного кода на своем управля101((ем входе. Коммутатор 11 по своим функциям .аналогичен коммутатору 5 и предназначен для передачи на свой выход кода .символа jni6o текста подстановки, либо сжатого входного текста, в зависимости от значения сигнала на его управляющем входе. Основной задачей устройства лекси ческого анализа является преобразова ние исходного символьного текста с целью выделения смысловых конструкций (лексем) из исходного символьног текста, написанного на соответствуюшем языке программирования (микропро граммирования) , и передача для дальнейшего синтаксического анализа.- Одновременно с этим в ходе решения этой задачд устройство обеспечивает сжатое представление информации, поскольку в исходном символьном тексте программы (микропрограммы) всегдгг имеется избыточная ин формация в виде разделителей, используемых в неограниченном количес тве, комментариев, необходимых для обеспечения читаемости микропрограмм человеком-программистом. Вся Э1 избыточная информация не должна поступать на выход устройства, так какона затруднит синтаксический анализ и значительно увеличит его время. Кроме того, при выделении из исходного символьного текста спе- Щ1альных конструкций, называемых ключевыми словами, устройство осу111;ествляет подстановку в исходный текст вместо них нового символьного текста, представляющего собой более развернутые смысловые.конструкции, с-целью повышения э4 фективности дальнейшего синтаксического анализа сжатого символьного текста исходной программы (микропрограммы). По возрастающему фронту синхроимпульса, поступающему на синхровход регистра 1, при отсутствии единичного сигнала на входе блокировки записи двоичный код очередного сш вола входной строки записывается в регистр 1 (фиг. 8 б) и поступает с его выхода на вход шифратора 3. По управляющему коду, сформированному шифратором 3, дешифратор 14 вырабатывает единичный управляющий сигнал на своем соответствующем выходе в зависимости от того, к какой из пяти групп принадпешзт очередной символ. Когда входной символ принадлежит к первой группе (информационный символ), единичный сигнал вырабатывается на первом выходе дешифратора 14. Если входной символ соответствует второй группе (разделители) , единичный сигнал формируется только на втором выходе дешифратора 14. Управляющий код, соответствующий входному символу третьей группы (символ Начало комментария ), возбуждает третий выход дешифратора. . 14, код, соответствующий четвертой группе (. символ Конец комментария)четвертый выход дешифратора 14. Управляющий код. Соответствующий входному символу пятой группы (символ f.apкep ключевого слова) , обеспечивает формирование единичного сигнала на пятом выходе дешифратора 14. Рассмотрим последовательно режим работы устройства при обработке символов каждой из пяти групп. . Если символ является информационным (первая группа) и триггер 15 находится в нулевом состоянии (это означает, что поступающий на анализ текст не является комментарием), то с выхот. да регистра 1 этот информационный символ приходит через коммутаторы 5 и 11 и записывается в регистр 2. Это достигается тем, что на выходе триггера 15 (начальное состояние триггера 15 нулевое) присутствует единичный сигнал. Единичный сигнал с выхода элемента И 16 поступает на вход коммутатора 5, который при этом пропускает код входного символа с выхода регистра 1 на информационный вход

11

(фигл8,п). В режиме подстановки. этот коммутатор 11 передает на свой выход символы с информаинонного входа, так как на его управляющем входе присутствует единичный сигнал, вырабатываемый на выходе блока 6, т.е. на единичном выходе триггера 28 (фиг.8,и). Конец считывания подстановки выбранного текста определяется схемой 40 сравнения. В конце каждого текста подстановки находится код специального символа конца

17312

текста. Этот код хранится также в узле 41 памяти константы. При считывании кода символа конца текста подстановки из узла 39 памяти схема 40 сравнения на своем выходе вырабатывает сигнал совпадения (фиг.8,н), который с выхода блока 8.через элемент Ш1И 13 поступает на вход блока 6 и далее на вход триггера 28, Триггер 28 возвращается в исходное нулевое состояние,что означает окончание работы устройства в режиме подстановки.

Фиг.5

34(

У

: 1

ад

Фт

п п п п п