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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК БО 1187173 А(51)4 С 06 Р 15 04 9/44 ОПИСАНИЕ ИЗОБРЕТЕНИЯ Е.хх а 3кв х:хъ ътлт. -Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Ленинградский институт авиационного приборостроения и Ленинградский научно-исследовательский вычислительный центр АН СССР(56) Авторское свидетельство СССР У 519715, кл. С 06 Р 15/04, 1974,Авторское свидетельство СССР У 1034043, кл. С 06 Р 15/04, 1982,(54)(57) 1. УСТРОЙСТВО ДЛЯ ЛЕКСИЧЕСКОГО АНАЛИЗА СИМВОЛЬНОГО ТЕКСТА, содержащее два регистра, шифратор, первый коммутатор, первый информационный вход которого и вход шифратора.соединены с выходами разрядов первого регистра, информационный вход которого является информационным входомустройства, выход шифратора соединенс вторым информационным входом коммутатора и с входом блока синхронизации,первый и второй выходы которого соединены соответственно с первым и вторымразрешающими входами первого коммутатора, третий выход соединен с синхронизирующим входом первого регистра,выходы разрядов второго регистра являются информационным выходом устройства, о т л и ч а ю щ е е с я тем,что, с целью повышения быстродействия,в него введены блоки сравнения, блокипамяти текстов подстановок, шифратортекста подстановки, второй и третийкоммутаторы, блок управления подстановкой, элемент ИЛИ-НЕ и элемент ИЛИ, выход которого соединен с первым входом блока управления подвтановкой, первый выход которого соединен с разрешающими входами блоковсравнения и с адресными входами блоков памяти текстов подстановок, выход каждого блока сравнения соединенс соответствующими входами элементаИЛИ-НЕ, шифратора текста подстановки,и с первым входом разрешения считывания соответствующего блока памятитекстов подстановок, второй вход раз"решения считывания которого соединенс третьим выходом блока синхронизации,выход элемента ИЛИ-НЕ соединен с вто- дрым входом блока управления подстановкой, третий вход которого соединенс третьим выходом .блока синхронизации,выхода оконнания вывода блоков памятитекстов подстановок подключены соответственно к входам элемента ИЛИ, информационные выходы соединены соответ-ственно с информационными входами вто- ырого коммутатора, разрешающий вход ООкоторого соединен с.выходом шифрато- ав 1ра текста подстановки, выход подклю- еаВчен к первому информационному входу 3третьего коммутатора информационные Мвходы блоков сравнения и второй информационный вход третьего коммутатора соединены с выходом первого коммутатора, синхронизирующие входыблоков сравнения соединены с вторымвыходом блока управления подстанов фкой третий и четвертый выходы которого соединены соответственно с раз,решающим входом третьго коммутатораи с синхронизирующим входом второгорегистра, пятый выход подключен квходу блокировки записи первого регистра и к,третьим разрешающим вхо1187173 Составитель А. ЖереновРедактор Н,Данкулич Техред Я.Кастелевич Корректор В,Бутяга Заказ 6552/55 Тираж 709 ВНИИПИ Государственного комитета по делам изобретений и открыт 113035, Москва, Ж, Раушская н1187173 дам считывания блоков памяти текстовподстановок, выход коммутатора подключен к информационному входу второго регистра, четвертый, пятый,шестой и седьмой выходы блока синхронизации подключены соответственнок четвертому, пятому, шестому и седьмому вхбдам блока управления подстановкой, который содержит два триггера, четыре элемента И, элемент ИИЛИ-НЕ, выход первого элемента Исоединен с единичными входами первого и второго триггеров и с первым выходом блока управления подстановкой,первый и второй входы которого соединены соответственно с первым нулевымвходом второго триггера и с первымвходом второго элемента И, третийвход подключен к первым входам третьего элемента И и элемента И-ИЛИ-НЕ,второй вход которого является четвертым входом блока управления подстановкой, пятый и шестой входы которого являются соответственно первым ивторым входами первого элемента И,седьмой вход является нулевым входомпервого триггера, единичный выход которого соединен с вторым входом третьего элемента И, выход которого является вторым выходом блока управления подстановкой, третий выход которого и первы й вход четвертого элемента И соединены с единичным выхо-дом второго триггера, нулевой выходкоторого соединен с третьим входомэлемента И-.ИЛИ-ПЕ, четвертый входкоторого и пятый выход блока управления подстановкой подключены к выходу четвертого элемента И, вторыевходы второго и четвертого элемен -тов И соединены с нулевым выходомпервого триггера, выход второго элеИзобретение .относится к вычислительной технике и может быть использовано для анализа символьных текстов в тацсляторах с языков программирования и микропрограммирования, в ситемах редактирования текста.Цель изобретения - повышение быстродействия за счет сокращения объмента И соединен с вторым нулевымвходом второго триггера, выходэлемента И-ИЛИ-НЕ является четвертымвыходом блока управления подстановкой. 2, Устройство по п.1, о т л и ч аю щ е е с я тем, что блок синхронизации содержит дешифратор, три триггера, четыре элемента И, элемент ИЛИ и генератор синхроимпульсов, выход которого соединен с синхронизирующим входом первого триггера, с первыми входами первого и второго элементов И и с третьим выходом блока, вход дешифратора является входом блока, первый выход дешифратора подключен к первому входу третьего элемента И,В второй выход подключен к единичному входу второго триггера и к седьмому выходу блока, третий и четвертый выходы дешифратора соединены соответственно с нулевым и единичным входами третьего триггера, пятый выход является пя 1 ым выходом блока, нулевой выход третьего триггера соединен с вторым входом третьего элемента И и с шестым выходом блока, выход третье." го элемента И подключен к второму входу первого элемента И, к нулевому входу второго триггера и к первому выходу блока, выходы первого и второго элементов И соединены соответственно с входами элемента.ИЛИ, выход которого является четвертым выходом блока, единичный выход второго триггера подключен к установочному входу первого триггера и к первому входу четвертого элемента И, второй вход которого соединен с нулевым выходом первого триггера, выход четвертого элемента И подключен к второму входу второго элемента И и к второму выходу блока. ема информации путем автогенерацииповторяющихся фрагментов символьноготекста.На фиг.1 приведена структурная 5 схема прилагаемого устройства," нафиг.2 - структурная схема блока синхронизации; на фиг,З - схема коммутатора; ца фиг.4 - структурная схемакоммутатора 11. На управляющий вход коммутатора 11 с выхода блока 6 поступает нулевой сигнал, так как триггер 28 находится в нулевом состоянии (это его исходное состояние) При нулевом значении сигнала на управляющем входе коммутатор 11 передает информацию на свой выход с второго информационного входа, двоичный код информационного символа записывается 1 О в регистр 2 при поступлении очередного импульса на его синхронизирующий вход.Формирование синхроимпульса записи в регистр 2 в этом режиме осуществляется следующим образом. Импульсы 15 с выхода генератора 23 синхроимпульсов (фиг.8, а) поступают через эле- мент И 20 (фиг,2) и элемент ИЛИ 22 на выход блока 4 синхронизации, так как на выходе первого элемента 20 И 16 в этом режиме присутствует единичный сигнал. Далее эти импульсы поступают на вход элемента И-ИЛИ-НЕ 33 в блоке 6 и в инвертированном виде поступают на выход блока 6 и 25 далее на синхронизирующий вход регистра 2, поскольку на входе элемента И-ИЛИ-НЕ 33 присутствует разрешающий единичный сигнал с нулевого выхода триггера 28 подстановки.Если очередной символ является разделителем, то единичный сигнал с второго выхода дешифратора 14 (фиг.2) устанавливает триггер 17 в единичное состояние. Триггер 18 в З 5 исходном состоянии находится в нулевом состоянии, поэтому с его нулевого выхода на вход элемента И 19 подается единичный сигнал. Так как и на другом входе элемента И 19 при сутствует единичный сигнал с триггера 17, то единичный сигнал формируется на выходе элемента И 19. Этот управлйощий сигнал выхода блока 4 синхронизациипоступает навход ком мутатора 5 и обеспечивает передачу с выхода шифратора 3, соответствующего внутреннему разделителю. Так же, как и в первом режиме, этот код поступает через коммутатор -11 на инфор мационный вход регистра 2. Управляющий сигнал с выхода элемента И 19 поступает также на второй вход элемента И 21, обеспечивая прохождение через него очередного импульса, который проходит через описанные для пер. вого режима цепи и поступает на синхронизирующий вход регистра 2. При этом производится запись кода внутреннего разделителя в регистр 2, Если за первым символом разделителя последуют 1 оже символы разделителей, то их запись в регистр 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 обеспечивает выдачу синхроимпульсов на второй выход блока б управления подстановкой через9 11871шестой элемент И 30 (фиг.8,д) дляосуществления проверки на совпадениесимволов входного ключевого слова ссимволами эталонных слов, хранимыхв узлах 34 памяти. При поступлениис выхода регистра 1 информационныхсимволов, составляющих входное ключе вое слово, они проходят через коммутатор 5, так как на выходе элементаИ 16 при считывании символов первой 1 Огруппы присутствует единичный разрешающий сигнал. Код очередного символа входного ключевого слова одновременно поступает на вход схемы 35сравнения каждого из блоков 7 провер.15ки ключевых слов. Все блоки 7 работают параллельно, так как на каждыйиз них поступают управляющие сигналыс блоков 6 управления подстановкой.Рассмотрим работу одного из блоков 07. После поступления сигнала начальной установки на вход узла 34 памяти его счетчик 44 адреса устанавливается в исходное нулевое состояние,при этом иэ регистров 43 считывается25первый символ эталонного ключевогослова, который поступает на вход схе"мы 35 сравнения (фиг.5). Если кодына входах схемы 35 совпадают, то наее выходе вырабатывается единичныйсигнал (фиг.8,е). В этом случае припоступлении первого синхроимпульсана вход триггера 37 он устанавливается н единичное состояние (Фиг.8,и).Егопрохождение. через элемент И 38 35обеспечивает разрешающий сигнал сединичного выхода первого триггераЗЬ, установленного в единичное состояние по сигналу с выхода элементаИ 29 блока 6 (Фиг. 8,ж). Если все 40символы входного ключевого слова совпали с символами эталонного слова, топо окончании проверки триггера 37останется в единичном состоянии. Еслихотя бы один из символов не совпал с 45эталонным, то триггер 37 по нулевомусигналу с выхода элемента И 38 будетсброшен в нулевое состояние, Единичныйсигнал с нулевого выхода триггера37 сбросит н нуль триггер 36. В результате этого элемент И 38 будетв дальнейшем заперт, и триггер 37 останется в нулевом состоянии, дажеесли следующие символы входного ключевого слова будут совпадать с символами эталонного слова,Поскольку в каждом из блоков 7 хранятся разные эталонные ключевые спо 73 10на, то разрешающий сигнал, указывающий на полное совпадение входного ключевого слова с эталонным, по окончании проверки будет присутствовать только на выходе одного из блоков 7, Конец входного ключеного слова наступает, когда очередной символ, считанный с выхода регистра 1, окажется разделителем. Единичный сигнал с второго выхода дешифратора 14 поступает на вход триггера 27 в блоке 6 и переводит его в нулевое состояние (фиг8,г). На этом заканчивается этап проверки ключевого слова, На этом этапе входные символы ключевого слова считывались из регистра 1, но их запись н регистр 2 не производилась, так как оба элемента И, входящие н состав элемента И-ИЛИ-НЕ 33, были заперты нулевыми сигналами с выхода элемента И 31 (фиг.8,л) и с нулевого выхода триггера 28На втором этапе в режиме подстановки единичный сигнал с выхода элемента И 31 обеспечивает прохождение сицхроимпульсон через элемент И-ИЛИ-НЕ 33 (фиг.8,м) на синхронизирующий вход регистра 2. Кроме того, этот управляющий сигнал обеспечивает разрешение считывания , текстов подстанонок из блоков 8 и одновременно блокирует запись в регистр 1 новых символов входной символьной строки. Разрешающий сигнал с выхода блока 6 поступает на вход элемента И 42 н каждом блоке 8. Другой разрешающий сигнал, вырабатываемый на выходе только одног о блока 7, поступает на вход элемента И 42 только н блоке 8. Б результате синхроимпульсы пройдут через элемент И 42 только в одном блоке 8 и обеспечат считывание выбранного .текста подстановки из его узла 39 памяти. Считываемый текст подстановки посимвольно поступает с информационного выхода соответствующего блока 8 на одноименный инФормационный вход коммутатора 10. Шифратор 9 формирует двоичный код номера блока 8, этот код поступает на управляющий вход коммутатора 10 и обеспечивает подключение к выходу коммутатора 10 его соответствующего информационного входа, В результате этого символы выбранного текста подстановки поочередно подаются на информационный вход регистра 2 для записи в него через коммутатор 11зблока управления подстановкой; нафиг.5 - структурная схема блока сравнения; на фиг.6 - структурная схемаблока памяти текста подстановки;на фиг.7 - схема узла памяти; нафиг.8 - временные диаграммы, поясняющие работу устройства..39 памяти, схему 40 сравнения, узел41 памяти константы, элемент И 4225группу 43 регистров, счетчик 44 адреса.Работу устройства. поясняют диаграммы, изображенные на фиг.8, где а -диаграмма на выходе генератора 23синхроимпульсов; б - диаграмма навыходе регистра 1; в - диаграмма навыходе элемента И 29 блока 6 управления подстановкой; г - диаграммана единичном выходе триггера 27;д - диаграмма на выходе элемента 35И 30; е - диаграмма на выходе схемы35 сравнения; ж - диаграмма на выходе триггера 36; и - диаграмма наединичном выходе триггера 37; кдиаграмма на единичном выходе триггера 28; л - диаграмма на выходеэлемента И 31; м - диаграмма навыходе элемента И-ИЛИ-НЕ 33; ндиаграмма на выходе схемы 40 сравнения п диаграмма на выходе регис 45тра 2,Регистр 1 предназначен для хранения двоичного кода очередного анализируемого символа из входной строкисимволов. На вход регистра 1 поступают символы исходного текста (программы, микропрограммы пользователя),например, из буферной памяти (не показана) .Регистр 2 предназначен для хранения очередного символа выходного сжатого текста, содержащего только дексемы (последовательности символовя 87173 4имеющие смысловое значение для конкретного языка микропрограммирования),отдаленные друг от друга символамиразделиелей, .причем выходной текстможет содержать вновь подставленныелексимы или их последовательностьвместо выделенных ключевых слов исходного текста.Шифратор 3 предназначен для выработки управляющего кода по коду очередного символа входного текста дляуправления грамматическим разборомвходного символьного текста с цельювыявления смысловых конструкцийязыка микропрограммирования,Блок 4 синхронизации предназначендля выработки управляющих сигнаповпо управляющему коду, поступающемус шифратора 3, разрешающих либо пропуск символа из регистра 1 в регистр2, либо запись кода символа внутреннего разделителя с выхода шифратора3 в регистр 2, либо игнорированиепоследовательности входных символових регистра 1, либо подстановку вместо группы входных сигналов из регистра 1, определяемых как ключевоеслово, заранее заданной последовательности символов, записываемых с вы .хода одного из блоков 8 регистр 2Коммутатор 5 предназначен для передачи на свой выход одного из двухдвоичных кодов, присутствующих на егоинформационных входах, в зависимостиот наличия разрешающего сигнала наодном из двух его управляющих входах,Блок 6 управления подстановкойпредназначен для формирования управляющих сигналов при выработке блоком4 синхронизации управляющего сигналаУвыделяющего начало ключевого слова9с целью сравнения его с эталоннымиключевыми словами и, в случае совпадения входного ключевого слова с одним из них - осуществления его замены на заранее определенный символьныйтекст.Каждый из блоков 7 предназначендля выработки. управляющего сигналав случае совпадения входного ключевого слова с соответствующим эталонным словом, хранящимся в данном блоке.Каждый блок 8 предназначен для выдачи соответствующего (заранее определенного и хранящегося в нем) текста подстановки в регистр 2 в случаесовпадения входного ключевого словас эталонным, хранящимся в одноименном блокеШифратор 9 предназначен для форми рования двоичног о кода номера того блока проверки ключевого слова, на выходе которого выработан единичный сигнал совпадения принятого ключевого слова с одним из эталонных. Такой сигнал может быть выработан всегда только на выходе одного из блоковПоэтому шифратор 9 фактически обеспечивает преобразование унитарного кода на его выходе в двоичный код на его выходе.Коммутатор 10 предназначен для передачи на свой выход символов текста подстановки с одного из,своих информационных входов в зависимости от двоичного кода на своем управляющем входе.Коммутатор 11 по своим Функциям аналогичен коммутатору 5 и предназначен для передачи на свой выход кода символа либо текста подстановки, либо сжатого входного текста, в зависимости от значеция сигнала на егоуправляющем входе,Основной задачей устройства лексического анализа является преобразование исходного символьного текста с целью выделения смысловых конструкций (лексем) из исходного символьного. текста, написанного ца соответствуюцем языке программирования (микропрограммировация), и передача для дальнейшего синтаксического анализа. Одновременно с этим в ходе решения этой задачи устройство обеспечивает "сжатое" представление информации, поскольку в исходном символь ном тексте программы (микропрограммы) всегда имеется избыточная информация в виде разделителей, используемых в неограниченном количестве, комментариев, необходимых для обеспечения читаемости микропрограмм человеком-программистом . Вся эчЪ избыточная информация не должна поступать ца выход устройства, так какона затруднит синтаксический анализ и значительно увеличит его время. Кроме того, при выделении из исходного символьного текста специальных конструкций, называемых ключевыми словами, устройство осу ществляет подстановку в исходный текст вместо цих нового символьного текста, представляющего собой более развернутые смысловые, конструкции, с целью повышения эффективности дальнейшего синтаксического анализа цсжатого символьного текста исходной программы (микропрограммы).По возрастающему фронту синхроимпульса, поступающему на синхровход регистра 1, при отсутствии единичного сигнала на входе блокировки записи двоичный код очередного символа входной строки записывается в регистр 1 (фиг. 8 б) и поступает с его выхода на вход шифратора 3, 11 о управляющему коду, сформированному шифратором 3, дешифратор 14 вырабатывает единичный управляющий сигнал ца своем соответствующем выходе в зависимости от того, к какой из пяти групп принадлежит очередной символ. Когда входной символ принадлежит к первой группе (информационный символ), единичный сигнал вырабатывается на первом выходе дешифратора 14. Е сли входной символ соответствует второй группе (разделители), единичный сигнал Формируется только на втором выходе дешифратора 14. Управляющий код, соответ- ствующий входному символу третьейИ ц группы (символ Начало комментария ), возбуждает третий выход дешифратора 14, код,соответствующий четвертой группе ( символ "Конец комментарияи)- четвертый выход дешифратора 14, Управляющий код, соответствующий входному символу пятой группы (символ Маркер ключевого слова"), обеспечивает формирование единичного сигнала на пятом выходе дешифратора 14. Рас-смотрим последовательно режим работы устройства при обработке символов каждой из пяти групп.Если символ является информационным (первая группа) и триггер 15 находится в нулевом состоянии (это означает, что поступающий на анализ текст не является комментарием), то с выхо, да регистра 1 этот информационный символ приходит через коммутаторы 5 и 11 и записывается в регистр 2. Это достигается тем, что ца выходе триггера 15 (начальное состояние триггера 15 нулевое) присутствует единичный сигнал. Единичный сигнал с выхода элемента И 16 поступает на вход коммутатора 5, который при этом пропускает код входного символа с выхода регистра 1 на информационный вход(фиг.8,п) . В режиме подстановки,этот коммутатор 11 передает на свойвыход символы с информапионного входа, так как на его управляющем входе присутствует единичный сигнал,вырабатываемый на выходе блока 6,т.е. на единичном выходе триггера .28 (фиг,8,и). Конец считывания подстановки выбранного текста определяется схемой 40 сравнения, В конце 10каждого текста подстановки находится код специального символа конца 173 12текста. Этот код хранится также вузле 41 памяти константы. При считывании кода символа конца текстаподстановки из узла 39 памяти схема40 сравнения на своем выходе вырабатывает сигнал совпадения (фиг.8,н),который с выхода блока 8 через элемент ИЛИ 13 поступает на вход блока6 и далее на вход триггера 28, Триггер 28 возвращается висходное нулевоесостояние,что означает окончание работы устройствав режиме подстановки.