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

 

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

12 1 A i

СОЮЗ СОВЕТСНИХ . СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (I9) (И) (51) 4

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (54) УСТРОЙСТВО ПЛЯ ЛЕКСИЧЕСКОГО

АНАЛИЗА ПРОГРАММ (57) Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей. за счет обеспечения преобразования цепочки терминальных слон программы в цепочку лексем стандартной длины, осуществления. логического контроля и обеспечения режима работы запрос-ответ, в процессе трансляции. (21) 3808768/24-24 .(22) 30.10,84 (46) 15.06.86. Вюл. )(22 (72) С. А. Соколов, М. А. Курносов, С. В. Савченко, P П. Гахов и А. H. Николаев

:(53) 681.3..801.3(088.8) (56) Авторское свидетельство СССР

1(690497, кл. G 06 P 15/38, 1976. .Авторское свидетельство СССР

Ф 1034043, кл. G 06 Р 15/04, 1982.

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

1238103 зовано в вычислительных системах с диалоговым режимом отладки и исполне.ния программ, а также в электронных вычислительных машинах (3BM).со структурно реализованным языком программирования.

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

На. фиг. 1 изображена функциональная схема предлагаемого устройства; на фиг. 2 — диаграмма работы при анализе первых К литер входного текста (поля метки); на фиг. 3 — диаграмма работы устройства .при анализе поля оператора; на фиг. 4 — диаграмма работы устройства при анализе поля операндов; на фиг. 5 — диаграмма работы. устройства при анализе коммента. риев в поле операндов.

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

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

его выходов. Лексема имеет фиксированный формат и состоит из следующих

30 полей: поля ошибки, поля типа и поля значения. В существующих ЭВМ литеры терминальной цепочки программы обычно представляются в памяти ЭВМ в коде ДКОИ и длина литеры и равна восьми разрядам (байт) . Кроме -того, обычно на практике для различных языков программирования выдерживается следующее соотношение: и с п а(1 5 — 2)п, 40 где rn — Разрядность лексемы; и — разрядность литеры.

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

7, группы 8 и 9 элементов И, группы

10 элементов ИЛИ, элементы И 11-17, элементы ИЛИ 18-22, элемент ИЛИ-НЕ

Изобретение относится к вычислительной технике и может быть испольУстройство содержит блок 1 преобразования кода литер в код лексем, регистр 2, дешифратор 3, счетчик 4 позиций, счетчик 5 литер, триггеры 6 и 7, группы 8 и 9 элементов И, группа 10 элементов ИЛИ, элементы И ll17, элементы ИЛИ 18-22, элемент ИЛИНЕ 23, элементы 24-27 задержки, одновибратор 28, вход 29 ответа, информационный вход 30 устройства, вход

31 выдачи, вход 32 пуска, информационный выход 33 устройства, выход

34 запроса, выход 35 готовности, выход 36 расхождения типа.

23, элементы 24-27 задержки, одновибратор 28, вход 29 ответа, информационный вход 30, вход 31 выдачи, вход

32 пуска, информационный вход 33, выход 34 запроса, выход 35 готовности,. выход 36 расхождения типа. 5 ил.

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

1О входного текста.

3 1238103 4

Большинство существующих систем . белов, KobfMPHтариев, специальных литрансляции языков программирования тер); осушествлять выдачу литер лекпредполагает структурирование прог- сем "идентификатор" и "константа" с раммы на записи стандартной длины. . целью формирования временных таблиц, Это связано с организацией в совре- 5 используемых на последуюших этапах менных ЭВМ системного ввода-вывода, трансляции; осуществлять лексический при котором записи стандартной длины контроль входных терминальных слов, (обычно 80 бай ) буферируются и вво- формируя в случае недопустимой кондятся (выводятся) более крупными еди- струкции сигнал ошибки, устанавливаницами — блоками (240,400,800 и т.д. 1о ющий.бит ошибки в соответствующем побайт), что повышает эффективность ле лексем в единичное состояние; осуиспользования оборудования. ществлять процесс анализа в режиме

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

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

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

В устройстве осуществляется под- 35 или последовательного действия. счет числа литер терминального слова и

Регистр 2 работает по принципу мага,после окончания его анализа и выдачи зина: очередная литера заносится лексемы соответствующего типа про" в вершину стека и при этом ранее изводится последовательная выдача лн- (прннятые литеры сдвигаются на одну тер исходного слова для занесения в позицию вниз под действиея управляюсоответствующую временную таблицу. соответствующую времени б щего сигнала на первом входе сдвига;. стройство логично сопрягать непри установке единичного сигнала на посредственно с памятью для считывадругом входе литеры в стеке сдвигания литер входного текста и записи литер соответствующих лексем во вре- 45 ются на одну позицию вверх. менные та лицы, а с другой стороны— предназначены для отслеживания позис устройством синтаксического акалиций обрабатываемой записи и иницииро» за для выдачи ему сформированных ливания соответствующих сигналов на тер. В этом случае процессор ЭВХ выходах дешифратора 3, которые обесосвобождается от анализа текстовой зО печивают выполнение микроопераций в информации (программы), что повышает у тройстве. эффективность использования системы

Счетчик 5 литер предназначен для

В целом устройство позволяет осу- отслеживания состояния регистра 2 ществлять преобразование входного 55 (числа литер в нем} и управления совтекста программы в цепочку лексем местно с триггером 7, элементами стандартной длины с одновременным И 13-15, элементом ИЛИ 22, элементом подавлением незначащих литер (про- KIN-. НЕ 23 и элементами 24 г 25 за1238103 держки, процессом последовательной выдачи литер из регистра 2 на вход 33

:устройства в соответствующих тактах его работы.

Триггер 6 предназначен для фиксирования очередного такта работы устройства и формирования сигнала "Запрос" на выходе 34 устройства, инициирующего подачу очередной литеры входного текста в конце соответствующего такта устройства.

Группы 8 и 9 элементов И предназначены для коммутации соответственно лексемы и соответствующих ей литер через группу 10 элементов ИЛИ на выход 33 устройства в соответствующих такта его работы. Остальные элементы

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

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

Терминальные слова и соответствующие им лексемы принято подразделять на следующие типы: идентификатор; оператор (зарезервированное слово);

45 константа (число); разделитель (служебный символ).

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

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

ДКОИ и поступают в начале соответствующих рабочих тактов на вход 30 устройства. Одновременно поступает идентифицирующий начало очередного такта сигнал "Ответ" на вход 29. устройства.

Формируемая блоком 1 лексема содержит три поля: поле ошибки (один разряд), поле типа (три разряда) и поле значения (m разрядов), так что общая длина лексемы m > n.

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

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

1 — К может содержать значащую литеру метки.или литеру типа Ц вЂ” пробел.

Позиции (К+1) — (К+0) могут содержать значащие литеры оператора входного языка или C литер Ц (0 К) . Позиции (К+К+1) — (L-3) могут содержать значащие литеры идентификаторов или констант и специальных разделителей ("+","-","1Р и тому подобное), которые используются при записи выражений языка, меток перехода, ключевых параметров оператора. Число литер в каждом из терминальных слов данного поля не должно превышать К-1, при этом Ь (5-10)К. После каждого терминального слова должен следовать специальный одно-. или. двухлитерный разделитель иэ числа допустимых в языке или литера Ц . Допустимое чис-.. ло терминальных слов в данном поле зависит от конкретного языка программирования, а порядок их следования

1238103

У ц )

В исходном состоянии регистр 2, счетчик 4 позиций, счетчнк 5 яитер и триггер 7 находятся в нулевом состоя нни, а на вход 32 пуска поступает единичный сигнал, который через элемент 18 ИЛИ устанавливает триггер 6 в единичное состояние. При этом на выходе 34 присутствует единичный сигнал "Запрос", свидетельствующий о гоопределяется синтаксисом языка и проверяется на этапе синтаксического анализа, поэтому здесь конкретные ограничения не накладываются с целью сохранения общности. Кроме того, с любого места позиции после (К+ +1) до (L 3) включительно может размещаться комментарий, которому должен предшествовать (и заканчивать) специальный разделитель (например + ).

Позиции с L-2 no L обычно предназначены для указания номера записи (перфокарты) и используются при сис темном вводе-выводе. Поэтому в,устройстве анализ литер этих позиций не опрецеляется. Согласно укаэанному счетчик 4 позиций имеет Ь состоян. й.

Исходным для него является нулевое состояние. С поступлением первой литеры на информационный вход 30 устройства состояние счетчика 4 увеличивается на единицу, так что первой литере соответствует единичное состояние счетчика 4, i-й литере со- 25 ответствует i-e состояние, à L-ой литере (последней в записи) соответствует нулевое состояние счетчика 4, которое в то же время является 1.-ым по счету. Поэтому с поступлением пер- 30 вой и последующей литер очередной записи счетчи 4 вновь последовательно проходит состояния с первого по

L-e (нулевое), т.е. счетчик 4 является .циклическим. Множество состояний устройства однозначно определяется уровнем записи (состоянием счетчика 4 озиций), которык совместно с литерами входного текста данного уровня определяет переходы из текущего состояния в очередное и выходные воздействия устройства..

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

Запрос" вызывает подачу от внешнего .устройства (не показано) единичного сигнала "Ответ" на вход 29 и литеру входной записи на информационный вход 30 устройства ° Единичный сигнал на входе 32 при этом снимается. Сигнат Ответ" устанавливает триггер 6 в нулевое состояние, обеспечивая сня-, тие сигнала "Запрос". При этом единичный сигнал с нулевого выхода триггера 6 переводит счетчик 4 в единичное состояние и одновременно обеспечивает занесение литеры в регистр 2 (при этом информация иэ первой ячейки заносится во вторую, из второй в третью и т.д., а поступившая литера заносится в освобожденную первую ячейку — вершину стека). Затем с .задержкой на элементе 27 данный сигнал переводит счетчик 5 s единичное состояние (в регистре 2 находится одна — первая значащая литера входной цепочки) и стробирует анализ текущего состояния счетчика 4 дешифратором 3, на первом выходе которого формируется единичный сигнал. Данный сигнал устанавливает триггер 6 в единичное состояние. Прием последующих литер входной цепочки осушествляется аналогично, поэтому далее подробно не рассматривается. Указанная последовательность действия отражена на диаграмме работы устройства (см. фиг. 2,1 такт). При этом предполагается, что единичный сигнал на входе 32 устройства имеет импульсный характер и поступает в начале работы устройства. В этом случае данный сигнал одновременно с установкой единичного состояния триггера

6 вызывает установку нулевого состояния счетчиков 4 и 5, регистра 2 и триггера 7 (цепи обнуления иа фиг. 1 опущены) .

Рассматривается работа устройства в соответствии с подмножествами его состояний.

Подмножество еостояний 1:1 tC 4J+

К. В каждом такте после приема очередной литеры в регистр 2 и установки соответствующего состояния в счетчике 4 вырабатывается единичный сигнал на -первом выходе дешифратора.

3, обеспечивающий через элемент

ИЛИ 18 установку триггера 6 в еди1238103

10 ничное состояние и формирование сигнала ".Запрос" на выходе 34 устройства, который инициирует подачу очередной литеры на информационный вход

30 устройства. Одновременно унитарный ,код 10000 с первого по пятый выходов дешифратора 3 осуществляет блокировку анализа литер блоком 1. Данный про- ° цесс продолжается до приема К-1 литеры цепочки.

Подмножество состояний 2:.(С 4)=К.

В данном случае: в регистре 2 находится К-1 литера поля метки и в верхнюю ячейку в данном такте заносится литера LI или некоторый специальный разделитель. При состоянии счетчика °

4 )C 4)=K вырабатывается единичный сигнал. на втором выходе дешифратотора 3, Унитарный код 01000 с выходов дешифратора 3 инициирует анализ К литер, поступающих с информационных выходов регистра 2 на одноименнце информационные. входы блока 1, причем возможны следующие ситуации.

Ситуация 2а (см. фиг. 2а, такты К-2К). На выходах с второго по "

К-й регистра 2 установлены значащие . литеры метки. Тогда йа информацион.ном выходе блока 1 формируется соответствующая метке лексема длины m (разрядов) и формируется единичный сигнал "Готово" на выходе 35 устройства, который удерживается до момента снятия унитарного кода 01000 с разрешающих входов блока 1. Данный .сигнал инициирует поступление от внешнего устройства (например, 5лока управления оперативной памятью, на фиг. 1 не показан) последовательности единичных импульсов на вход 31 устройства в течение времени действия сигнала "Готово". Первый импульс через элемент И 11, открытый единичным сигналом с нулевого выхода триггера 7, разрешает выдачу лексемы через группу элементов И 8 и ИЛИ 10 на информационный выход 33 устройства. Данный импульс через элемент

И 24 и элемент И 15, открытый элемент ИЛИ 21 единичным сигналом с второго выхода дешифратора 3 и единичным сигналом с выхода признака блока 1 (данный сигнал находится в единичном состоянии при наличии комбинаций 01000 на разрешающих входах блока 1), устанавливает триггер 7 в единичное состояние.

Ситуация 2 о (см. фиг. 2о, К-й такт). На выходах регистра 2 установлены литеры Ц, т.е. в данной записи в поле метки метка отсутствует.

Формируется единичный сигнал на выходе блока 1, который через элемент

ИЛИ 18 устанавливает триггер 6 в едиПри.появлении сигнала на единичном выходе триггера 7 и, соответственно, на входе элемента И 13 на

5 выходе 31. уже присутствует нулевой сигнал, так что первый импульс чере данный элемент не проходит. Второй импульс через элемент 13 И разрешает выдачу литеры, находящейся в вершине

1р регистра 2 через группу элементов

И 9 и ИЛИ 10 на выход 33 устройства .

Одновременно данный импульс через элемент ИЛИ 20 уменьшает счетчик 5 на единицу. Через время задержки на элементе 25 данный импульс через элемент ИЛИ 22 инициирует сдвиг литер в регистре 2 на одну позицию вверх, устанавливается (К-1) -ая литера. Одновременно блокируется прохождение

20 данного импульса через элемент И 14, который закрыт нулевым сигналом .с выхода элемента ИЛИ-НЕ 23:(состояние . счетчика 4 отлично от нуля, т.е. не все литеры метки выданы из регист25 ра 2). С приходом К-ro импульса на вход 31 (фиг . 2а 2k-такт) на выход

33 устройства выдается последняя . литера метки (литеры выдаются в порядке, обратном порядку поступления в регистр 2, аналогично указанному).

В данном также счетчик 5 имеет нулевое состояние и на выходе элемента

ИЛИ-НЕ 23 формируется единичный сигнал, разрешающий прохождение импульса с входа 31 через элемент И 14.

Данный импульс устанавливает триггер

7 в исходное состояние и триггер 6 через элемент ИЛИ 18 в единичйое состояние, обеспечивая формирование сигнала "Запрос" на выходе 34 устрой40

:ства. Таким образом, в данном подмножестве состояний осуществляется выдача для записи в оперативную память сформированной лексемы метки и последующая выдача (такты К+1 — 2К)

45 соответствующих лексеме терминальных литер исходной метки для записи в соответствующую временную таблицу.

После выдачи последней литеры осуществляется запрос на подачу очеред50 ных литер .входной цепочки.

1238103

12 ничное состояние и соответственно формирует сигнал "Запрос" на выходе

34 устройства (содержимое поля метки с 1 по К позиции включительно игнорируется) .

Подмножество состояний 3:K+ (С 4) K+

+ о. В каждом такте после приема очередной литеры в регистр 2 вырабатывается единичный сигнал на третьем !О выходе дешифратора 3, который обеспечивает блокировку срабатывания блока 1 и через элемент ИЛИ 18 обеспечивает установку триггера .6 в единичное состояние..Единичный сигнал "Запрос" .15 инициирует подачу очередной литеры . поля оператора в устройство без анализа уже поступивших до йриема литер .данного поля (см. фиг. 3ai) такты (K+1= В ) -(KA -1=6-1), 20

Подмножество состояний 4: j С 4)=

=K+Z. После занесения последней литеры поля оператора в вершину регистра 2 вырабатывается единичный сигнал на четвертом выходе дешифратора 3, 25 инициирующий: анализ Z литер поля оператора блоком 1 (обычно 2 а К), причем возможны следующие ситуации.

Ситуация 4а (см. фиг. 3, тактР) .

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

"Готово" на выходе 35 устройства и нулевой сигнал на выходе признака блока l. Сигнал "Готово" инициирует поступление импульса на вход 31 устройства, который стробирует выдачу

-лексемы на выход 33 устройства (ана- 4О логично ситуации 2a), Прохождение данного импульса через. элемент И 15 блокировано нулевыми сигналами второго и пятого выходов дешифратора 3 через элемент ИЛИ 21-и нулевым сигна- 45 лом с соответствующего выхода блока

1 . Следовательно, выдача литер .поля оператора из регистра 2 не осуществляется. Это объясняется тем, что в поле значения сформированной лексе- 5О мы .устанавливается номер (смещение). данного оператора в соответствующей постоянной таблице (таблицы операторов и разделителей языка формйруются при генерации транслятора, постоянно 55 находятся в оперативной памяти и в процессе лексического анализа форми-. руются), в которой терминально сформировано представление данного оператора. Одновременно с инициированием лексемы импульс через элемент И 12, открытый единичным сигналом с четвертого выхода дешифратора 3, через эле- . мент И 17 устанавливает триггер 6 в единичное состояние, обеспечивая формирование сигнала "Запрос" на выходе 24 устройства, и одновременно через элемент ИЛИ 19 устанавливает регистр 2 и счетчик 5 литер в нулевое состояние, подготавливая к приему и анализу очередных литер входной цепочки.

Ситуация 4Ь (см. фиг. ЗЯ, такт e ).

На информационных входах блока 1 установлены литеры Ц т.е. в данной записи оператор отсутствует. В этом случае формируется единичный сигнал на выходе блока 1, который через элемент ИЛИ 18 обеспечивает установку триггера 6 в единичное состояние и формирование сигнала "Запрос" (содержимое поля записи с K+1. по К+ позицию включительно игнорируется). !

Подмножество состояний 5: К + Г

+ г (С 41 -2.

После приема (K+8+1)-ой литерь1 входной цепочки (см. фиг. 4, L --й" такт) формируется единичный сигнал на пятом выходе дешифратора 3, кото- рый инициирует анализ литер блоком 1.

При этом возможны следующие ситуации.

Ситуация 5п (eM. фиг. 4) . Если в результате .анализа поступившей в регистр 2 цепочки литер на выходе 36 не появляется единичный сигнал, импульс, сформированный по переднему фронту сигнала одновибратором 28 через элемент 26 задержки и через элемент И l6, открытый нулевым сигналом с выхода 35, устанавливает триггер 6 в единичное состояние. Формируется сигнал "Запрос" на выходе 34 устройства, инициирующий поДачу очередной литеры в устройство. Данная ситуация является характерной нри анализе поля операндов, в котором встречаются идентификаторы, константы и/или специальные одно-.и/или двулнтерные разделители. В этом слу чае анализ поступившей цепочки литер в каждом такте работы устройства не приводит к формированию единичного сигнала "Расхождение типа" ("РТ") на выхрде 36 устройства, так как поступившие литеры являются литерами

l4

1238103

13 одного типа. Если в регистре 2 находится допустимая лексическая конструкция (в такте Ь +К-1) и считанная в текущем такте (см, фиг. 4, такт

L +К) литера отлична по своему типу от ранее принятых. литер (например, в регистре 2 находится К-1 литера идентификатора и принята литера "+" или подобная; данный случай рассмот- Ю рен на диаграмме фиг. 4), та на выходе.36 устройства формируется еди- ничный сигнал, обеспечивая фиксацию внешним устройством требования повторной подачи последней литеры в . 15 следующем такте по сигналу "Запрос".

Одновременно сигнал "PT" обеспечивает уменьшение состояния счетчиков 4 и 5 на единицу и сдвиг литер в регистр

2 на одну позицию вверх (литера, вы- 2б звавшая расхождениее типа, выталкивается из вершины стека, и там остаются литеры допустимой лексической конструкции). После устранения .расхождения типа на выходе 36 устанавли- 25 вается нулевой сигнал и формируется сигнал "Готово" на выходе 35 устройства, который .инициирует подачу последовательности импульсов от внешнего устройства на вход 31 устройства для Зр считывания сформированной лексемы и соответствующих ей терминальных литер иэ регистра 2. Одновременно единичный сигнал "Готово" поступает на инверсный вход элемента И 16, блокируя прохождение импульса от одновибратора 28. Первый. импульс на входе

31 стробирует выдачу лексемы на выход.

33 устройства (аналогично ситуации

2g; .см. фиг. 4, такт L +K), Если 46

I тип сформированной лексемы "Идентификатор" или "Константа", то на выходе блока 1 присутствует единичный сигнал, который совместно с единичным сигналом с пятого выхода дешиф- 45 ратора 3 открывает элемент И l5. Импульс 2 через элемент 24 задержки устанавливает триггер 7 в единичное состояние. Второй и последующие им.пульсы с входа 31 через элемент И 13 50 инициируют выдачу литер, соответствукнцих сформированной лексеме, внешнему устройству для формирования соответствующих временных таблиц (аналогично ситуации 2й; см. фиг. 4, 55 такт L +К - L+2K-l). Наличие единич» ного сигнала на выходе блока 1 обеспечивает блокировку прохождения им1

I пульсов с входа 31 через элемент

И 17 и установку триггера 6 в единичное состояние. Если тип сформированной лексемы "Разделитель", то на выходе блока 1 установлен нулевой сигнал, который поддерживает. элемент

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

%

Ситуация 58 (см. фиг. 5). В какой-либо позиции после, (Х+ )-й может встретиться комментарий, который начинается служебным символом используется лишь для этой цели и им заканчивается. После приема символа в регистр 2 унитарный код 00001 с выходов дешифратора 3 инициирует его анализ .блоком 1. Импульс с выхода одновибратора 28 через элемент И 16 и далее через элемент ИЛИ 18 устанавливает триггер б в единичное состоя- ние, обеспечивая формирование сигнала "Запрос". на выходе 34 устройства. Процесс считывания литер продолжается аналогичным образом до тех пор, пока не считан закрывающий символ + . Считывание второй литеры + приводит к формированию единичного сигнала на выходе первого признака блока l. Данный сигнал через элемент

ИЛИ 19 обеспечивает установку регистра 2 и счетчика 5 в нулевое состояние (литеры комментария игнорируются). Единичный импульс с выхода одновнбратора 28 через элемент 16 И и через элемент ИЛИ 18 обесгечивает установку триггера. 6 в единичное состояние (формируется запрос на подачу очередной литеры).

Ситуация.5 3 (аналогична ситуациям 2 о и 43, см. фиг. 2о нли фиг. Зо) .

1238103

40

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

Формула изобретения устройство для лексического ана-, 50 лиза программ, содержащее регистр, информационный вход которого являет. ся информационным входом устройства, два триггера, четыре элемента И, первый элемент ИЛИ, дешифратор, две группы элементов И, первые входы которых соединены с первые выходом регистра, а выходы — подключены к ПерЕсли в какой-либо позиции после (К+г)-р. встречаются литеры Ц и при этом регистр 2 пуст, то анализ литеры Ц приводит к формированию еди5 ничного еигнала на втором выходе признака блока 1. Данный сигнал через элемент ИЛИ 18 устанавливает триггер 6 в единичное состояние, обеспечивая формирование запроса на 10 подачу очередных литер входной цепочки (пробелы игнорируются).

Подмножество состояний 6. Последовательно считываются литеры (Ь-2)-й; (L-1)-й и L-й позиции за- 15 писи. При этом L-й позиции записи

" соответствует нулевое состояние счетчика 4 позиций, т.е. после.достиже-. ния максимального (L-1)-го состояния счетчик 4 автоматически перехо- 20 дит в нулевое состояние. Данные состояния счетчика 4 позиций приводят к формированию единичного сигнала на

/ третьем выходе дешифратора 3, обеспечивающего установку запроса на подгчу очередной литеры записи и блокиров ку блока 1 (аналогично подмножеству состояний 1), т.е. литеры номера записи игнорируются при лексическом анализе. После анализа L-й литеры 30 данной записи поступает первая литера следующей, и работа устройства . происходит аналогично. При отсутствии готовых к анализу записей (программы) устройство может неопределен5 но долго находится в состоянии ожидания: на выходе 34 устройства присутствует единичный сигнал "Запрос" и схемы устройства находятся в исходном состоянии. вым входам группы элементов ИЛИ, вторые входы группы элементов ИЛИ соединены соответственно с выходами элементов И второй группы, выход первого элемента И соединен с первь * входом второго элемента И и с первыми входами элементов И второй группы, выход второго элемента И соединен с первым входом первого элемента ИЛИ,. выход третьего элемента И соединен с вторыми .входами элементов И первой

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

И и через второй элемент задержки— с первым входом пятого элемента И, выход которого соединен с единичным входом второго триггера, единичный выход которого соединен с вторым входом третьего элемента И,"нулевой выход соединен с вторым входом первого элемента И; выход третьего элемента И соединен с первым входом второго элемента .ИЛИ н через третий

17

18

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

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

15 ИЛИ, выход. второго признака соединен с четвертым входом пятого элемента

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

ИЛИ соединен с вторым сдвигающим вхо,дом регистра, выходы элементов ИЛИ

:группы являются информационным выходом устройства.

1238103 ю)

Ç5

1238103 авиа.4

Составитель А. Жеренов

Техред Н.Бонкапо

Корректор Л,Патай.

Редактор С. Лисина

Заказ 3294/51 . . Тираж 67) ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

1!3035, Иосква, Ж-35, Раушская наб., д. 4/5

Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4