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

 

Изобретение относится к области вычислительной техники, предназначено для лексического анализа программ, написанных на языках высокого уровня. Устройство может быть использовано в специализированных процессорах, трансляторах и программно-аппаратных системах, осуществляющих перевод с языков программирования высокого уровня на машинный язык, а также в интерпретаторах языков высокого уровня. Цель изобретения состоит в расширении области применения за счет обеспечения возможности не только выделения лексем, но и сжатия значений лексем, выдаваемых лексическим анализатором. Устройство содержит блок преобразования 1 кода литер в код лексем, блок 2 регистров, блок 3 элементов ИЛИ, две группы элементов И 4, 5, дешифратор 12, блок управления 13, блок формирования 14 таблицы идентификаторов, преобразователь кодов 15, блок 16 регистров , блок двоично-десятичного преобразования 17, регистр 18, группу элементов И 19. сметчик 20, блок памяти 22 символьных строк и группу элементов И 24. 5 ил. 2 табл.

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

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

РЕСПУБЛИК (s»s G 06 F 15/38

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4822020/24 (22) 29.03.90 (46) 30,12,92. Бюл. N - 48 (71) Ленинградский электротехнический институт им. В.И.Ульянова (Ленина) (72) Г.B.Ðàçóìoâñêèé, А.И.Познянский($О) и

У.Be.Ïþò÷ëåð (D0) . (56) Авторское свидетельство СССР

М 1238103, кл. G 06 F 15/38, 1984, Авторское свидетельство СССР

М 1418757, кл, G 06 F 15/38, 1988. (54) УСТРОЙСТВО ДЛЯ ЛЕКСИЧЕСКОГО .АНАЛИЗА ПРОГРАММ (57) Изобретение относится к области вычислительной техники, предназначенодля лексйческого анализа программ, написаннйх на языках высокого уровня, Устройство может быть использовано в специализированных процессорах, трансляторах и программЯЦ„„1784999 А1 но-аппаратных системах, осуществляющих перевод с языков программирования высокого уровня на машинный язык, а также в интерпретаторах языков высокого уровня.

Цель изобретения состоит в расширении области применения за счет обеспечения возможности не только вйделения лексем, но и сжатия значений лексем, выдаваемых лексическим анализатором. Устройство содержит блок преобразования 1 кода литер в код лексем, блок 2 регистров, блок 3 элементов

ИЛИ, две группы элементов И 4, 5, дешифратор 12, блок управления 13, блок формирования 14 таблицы идентификаторов, преобразователь кодов 15, блок 16 регистров, блок двоично-десятичного преобразо- 3 вания 17, регистр 18, группу элементов И 19, сЧетчик 20, блок памяти 22 символьных строк и группу элемейтов И 24. 5 ил. 2 табл.

1784999

Изобретение относится к области вы- адреса, содержащихся в блоке формировачислительной техники, предназначено ния таблицы идентификаторов 14; а также в для аппаратной поддержки процессов обнулении блока 2 регистров и в записи трансляции и может быть использовано в начальното адреса таблицы символьных специализированных процессорах или 5 строк, поступающего на вход21устройства, программно-аппаратных средствах, кото- в счетчик 20. рые осуществляют перевод с языков про- Блок управления посылает на выход 10 граммирования высоко о уровня на устройства импульс, по которому на вход 7 машинный язык, а также в интерпретато- устройства должен быть подан первый симрах языков программирования высокого 10 вол программы. После подачи на вход7 симуровня. вола на вход 6 устройства подается импульс, Цель изобретения — расширение обла- подтверждающий наличие символа на вхости применейия за счет обеспечения воз- де 7. По соответствующему сигналу, вырабаможности не только выделения лексемы, но тываемому блоком уп равления 13, и сжатия значений лексем, выдаваемых лек- 15 содержимое блока 2 регистров сдвигается сическим анализатором. на один байт от младших разрядов к старНа фиг. 1 представлена функциональ- шим. Такая последовательность импульсов ная схема устройства для лексического ана- повторяется до тех пор, пока не будет заполлиза программ; на фиг. 2 — функциональная нен блок 2 регистров. Конец заполнения схема реализации блока формирования таб- 20 блока 2 регистров определяется по выработлицы идентификатора; на фиг. 3 —. пример ке на выходе дешифратора 12 символов косформированныхлексем; на фиг.4 — микро- да, отличного от нулевого, После программа работы устройства; на фиг, 5 — заполнения блока 2 регистров блок 13 начимикропрограмма работы блока формирова- нает распознавание лексем программы в ния таблицы идентификатора.. 25 зависимости от класса символов, поступаюПредлагаемое устройство для лексиче- щих на вход дешифратора 12, ского анализа программ (фиг. Ij содержит; Если управляющий код соответствует блок 1 преобразования кода литер в код - ключевым словам, однолитерному разделилексем, блок 2 регистров, блок 3 элементов телю, двулитерному, разделителю, симвоИЛИ, группы 4 и 5 элементов И, вход ответа 30 лам начала и конца комментария, символам

6, информационный вход 7, вход пуска 8, типа пробел или символам конец програминформационный выход 9, выход запроса мы, то работа устройства выполняется ана10, выход готовности 11, дешифратор 12, логично работе прототипа. блок управления 13, блок 14 формирования . Если символ в старших разрядах регитаблицы идентификаторов, преобразова- 35 стра 2 является буквой, то это означает тель кодов 15, блок 16 регистров, блок дво- начало идентификатора; Обработка иденично-десятичного преобразования 17, тификатора осуществляется при помощи регистр 18, третью группу элементов И 19, блока 14 формирования таблицы идентифисчетчик 20, блок памяти символьных строк катора. Рассмотрим вариант реализации и

22, четвертую группу элементов И 24, . 40 работы блока 14.

На фиг. 2 показан вариант реализации Блок формирования таблицы идентифиблока формирования таблицы идентифика- каторав служит для преобразования иденторов, в котором в.качестве хешфункции тификаторов в лексему фиксированной используется сложение по модулю два всех длины. Все идентификаторы записываются байтов идентификатора. Блок 14 содержит 45 втаблицуидентификаторов(символов), аадэлемент 26 сложения по модулю два, счет- рес идентификатора в этой таблице предчик адреса 27, память 28, регистрданных 29, ставляет собой значение лексемы. Способ схемусравнения 30, дешифратор31, группу организации таблиц хорошо известны. 8 элементов ИЛИ 32, 6 групп элементов И предлагаемом блоке таблица идентифика. 33 — 38, вход идентификатора 39, управляю- 50 торов основана на хешировании и методе щие входы 40-49, выход лексемы 50 и ос- цепочек для разрешения коллизий. ведомительные выходы 51, 52, регистр Обработка идентификатора в блоке 14 адреса 53. начинается после того, как в старшем байте устройство работает следующим обра- блока 2 регистров появилась буква и на ин55 формационном выходе блока 1 сформироНавход8устройстваподаетсяимпульс, вался тип лексемы "идентификатор", который запускает блок управления 13. который передается через группу 4 элемен,. Блок управления сначала выполняет на- тов И и блок 3 элементов ИЛИ на информачальную установку. Начальная установка за- ционный выход 9 устройства путем подачи ключается в обнулении памяти и счетчика из блока управления 13 соответствующего

1784999 сигнала. Одновременно на выход готовно- коды символов идентификаторов поступэют сти11 подается сигнал, свидетельствующий на вход комбинационной схемы 26, на выхоо наличии на выходе 9 устройства распоз- де которой вырабатывается значение хешнанного типа лексем. Из блока 2 регистров функции. устройства в блок 25 регистров блока 14 5 На управляющий вход 41 из блока уппередаются символы идентификатора, равления 13 подается сигнал и значение

Предварительно блок 25 регистров обнуля- хешфункции через группу 34 элементов И и ется подачей сигнала на вход 40 из блока группу 32 элементов ИЛИ передается на управления 13. Передача символа из стар- вход регистра адреса 53. Зат м по сигналу шего байта блока 2 регистров осуществля- 10 чтения, поданному на вход 42, осуществляется в младший байт блока 25 регистров с ется выборка на регистр 29 значение слова одновременным сдвигом на один байт от памяти 28. В дальнейшем работа блока замладших разрядов к старшим путем подачи висит от состояния выходов 51 и 52. Если сигнала из блока управления 13 на управля- код идентификатора, прочитанный из памяющий вход 49 блока 14. После этого выпол- 15 ти 28 не совпадает с кодом анализируемого няется сдвиг — на один байт от младших идентификатора, хранящимся вблоке25реразрядов к старшим содержимого блока 2 гистров, на выходе 51 схемы сравнения 30 регистров и цикл передачи символов иден-. появляется одиночный сигнал.- Если поле тификатора повторяется. Конец передачи ссылки в прочитанном слове равно нулю, то идентификатора определяется по появле- 20 на выходе 52 дешифратора 31 вырабатыванию в старшем байте блока 2 регистров ется единичный сигнал. Приединичныхсигсимвола, отличного от буквы и цифры. Про- налах на обоих выходах блок управления цесс преобразования идентификатора ба- осуществляет запись адреса в хейтаблицу и зируется на методе хеширования, который кодов символов анализируемого идентифипредполагает наличие двух таблиц: хештаб- 25 катора в таблицу идентификатора, Такая силицы и таблицы идентификаторов. Обе таб- туация возникает, когда выработанное лицы хранятся в памяти 28, которая значение хешфункции первый раз встречаобнуляется, как счетчик адреса 27, при ется при анализе программы, В этом случае включении устройства. Хештаблица содер- по сигналу на входе 44 содержимое счетчика жит адреса идентификаторов, Местоположе- 30 27 через группу 35 элементов И передается мие адреса идентификатора в хештаблице в поле ссылки регистра 29, затем по сигналу вычисляется с помощью хешфункции. В ли- записи, поданному на вход 45, осуществлятературе описано большое разнообразие ется запись адреса идентификатора в хешхешфункций. Среди них можно выделить таблицу. После этого по сигналу 46 класс функций, которые могут быть реализо- 35 содержимое счетчика 27 через группы 36 ваны с помощью логической схемы и не тре- элементов И и группу 32 элементов ИЛИ буют больших аппаратных затрат. Такой заносится на регистр 53. Одновременно по способопределенияхешфункцииназывает- этому же сигналу код идентификатора из ся методом свертывания. Например, эле- блока 23 регистров через группу элементов мент 26 может реализовать хешфункцию; 40 И 33 передается в поле идентификатора рекоторая вычисляется путем сложения по мо- гистра 29, а разряды поля ссылки этого редулю два кодов символов идентификатора, гистра сбрасываются в нуль, При помощи

Слова памяти 28 разбиты на два поля: поле сигнала на входе 45 производится запись идентификатора и поле ссылки. Первое по- содержимого регистра 29 в память 28, а по ле служит для хранения идентификатора, 45 сигналу47наединицуувеличиваетсязначевторое поле предназначено для связывания . ние счетчика адреса 27. После этого подаетв цепочку идентификатора, второе поле ся сигнал на вход 48, по которому через предназначено для связывания в цепочку . группу 38 элементов И адрес идентификатоидентификаторов, имеющих одинаковое ра передается на в@ход 50 и блок заканчизначение хешфункции, Конец цепочки опре- 50 вает свою работу. деляется уникальным значением поля ссыл- Если на выходе 51 схемы сравнения 30 ки. В рассматриваемом блоке таким появится единичный сигнал, а на выходе 52 уникальным значением является нуль во дешифратора 31 отсутствовал сигнал, то всех разрядах поля ссылки. Хештаблица блок управления 13 по сигналу 43 через представляет собой последовательность 55 группу 37 элементов И и группу 32 элеменслов, в полях ссылки которых содержатся тов ИЛИ значсние пбля ссылки регистра 29 адреса первых элементов цепочки иденти- передает на регистр 53, Затем по сигналу фикатора, имеющих одинаковое значение чтения 42 осуществляется выборка слова из хешфункции, а поля идентификаторов со- памяти 28 на регистр 29. Последующая радержат нули. С выходов блока 25 регистров бота блока 14 снова строится R зависимости

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

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

Если на выходе 51 схемы сравнения 30 отсутствует сигнал, что означает совпадения кодов прочитанного иэ таблицы идентификатора и анализируемого идентификатора, тоблокуправления выдает сигнал на вход 48 и адрес идентификатора через группу 38 элементов И передается на выход 50. После этого блок заканчивает свою работу, Выработанное в блоке 14 значение идентификатора передается через группу 5 элементов

И и группу 3 элементов ИЛИ на выход 9 устройства. Одновременно на выход го товности 11 подается сигнал, свидетельст вующий о наличии на выходе 9 устройства значения лексемы.

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

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

4 элементов И и блок 3 элементы ИЛИ на информационный выход 9 устройства, путем подачи из блока управления 13 соответствующего сигнала: Одновременно на выход готовности 11 подается импульс, свидетельствующий о наличии на выходе 9 устройства тип лексемы, Формирование лексемы начинается с обнуления блока 16 регистров, Затем на младший байт блока 16 регистров через преобразователь кодов 15 подаются двоичные представления цифр, составляющих лексему "целое", одновременно содержимое блока 16 регистров сдвигается на 1 байт со старшим разрядом.

Новые символы программы поступают в блок 2 регистров как и в предыдущем случае. При помощи преобразователя кодов 15 осуществляется преобразование представления цифр "целого" из символьного вида в двоичный. Таким образом, в блоке 16. регистров формируется двоично-десятичное представление лексемы "целое", При помощи блока двоично-десятичного преобразо-! вателя 17 содержимое блока 16 регистра преобразовывается к двоичному виду и записывается в регистр 18. Затем двоичное представление числа передается на регистр

10

18, через группу 19 элементов И и блок 3 элементов ИЛИ на выход 9 устройства в качестве значения лексемы "целое". Одновременно на выход готовности 11 подается импульс, свидетельствующий о наличии на выходе 9 устройства значения лексемы целое. После передачи значения лексемы

"целое" осуществляются действия, соответствующие классу символов, находящихся в старших разрядах блока 2 регистров, Если символ, находящийся в старших разрядах блока 2 регистра, является признаком символьной строки (например, кавычкой), то на информационном выходе блока I формируется тип лексемы символьная строка. Этот тип передается на информационный выход 9 устройства таким же образом, как и для остальных лексем. После . передачи типа осуществляется сдвиг содер20 жимого блока 2 регистра на один символ с . записью нового символа программы. Табли- ца символьных строк находится в блоке памяти 22. Счетчик 20 указывает на первую свободную ячейку памяти 22, адрес которой

25 задается на входе 21 устройства. Начиная с этого адреса будет размещена новая символьная строка; В качестве значения лексемы "символьная строка" выступает адрес ее первого символа, записанного в блоке 22..

30 Поэтому содержимое счетчика 20 через группу 24 элементов И и группу 33 элементов ИЛИ передается на выход 9 устройства.

Одновременно на выход 11 подается им-. пульс; свидетельствующий о наличии на вы35 ходе 9 значения лексемы "символьная строка". После этого начинается запись символьной строки в таблицу символьных строк. Символ и старшего байта регистра 2 помещается в ячейку памяти 22 с адресом, 40 находящимся в счетчике 20. После. этого со.держимое счетчика 20 увеличивается на единицу. Символы записываются в блок 22

BnJlQTb до появления символа ограничителя символьной строки "кавычки". После записи

45 ограничителя обработка лексемы "символьная строка" прекращается и дальнейшие действия осуществляются в соответствии с классом символов, расположенных в старших байтах блока 2 регистров. На последу50 ющих этапах трансляции доступ к символьным строкам может осуществляться путем подачи адреса символьной строки на вход 21 устройства и считывания символов со входа 23 устройства.

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

10 программирования (Ф-язык), который, как является входом пуска устройства, вход лоизвестно, является средством описания гических условий блока управления являет-. функций операционных устройств на уров- ся входом ответа устройства, первый выход не микропрограммы безотносительно к блокауправлениясоединенсвходом второй структуре, которая может быть использова- 5 группы элементов И, второй выход блока надля реализации этихфункций. Функцио- управления соединен с вторыми входами нальная микропрограмма, как известно; элементов И первой группы, третий выход содержит в себе два рода сведений, две блока управления являетСя выходом готовчасти: 1) описание слов и массивов, устанав- ности устройства, четвертый выход блока ливающее типы и форматы слов, с которыми 10 управления соединен с входом синхронизаоперирует микропрограмма; 2) содержа- ции первого блока регистров, пятый выход тельный граф микропрограммы, который блока управления является выходом запроопределяет алгоритм выполнения операций са устройства, о т л и ч а ю щ е е с я тем, что, всодержательной форме — в видеописаний с целью расширения области применения микроопераций и логических условий. 15 за счет обеспечения возможности не только

Множество слов, с которыми работает: выделения лексем, но и сжатия значений микропрограмма, описываются в виде лексем, выдаваемых лексическим анализатабл. 1. тором, в него введены блок формирования

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

Содержательный граф микропрограм- памяти символьных строк, четвертая группа мы, соответствующий алгоритму работы ус- элементов И, причем информационные вытройства, изображен на фиг. 3, 25 ходы блока формирования таблицы идентиЧасть микропрограммы, описывающей фикаторов соединеньг с первыми входами работу блока 14 формирования таблицы элементов И второй группы, информационидентификатора, предс; авлена множест- ный вход — с вторым выходом первого блока вом слов, с которыми работает эта часть регистров,группауправляющихвыходов-с микропрограммы (табл. 2), и графом микро- 30 второй группой входов логических условий программы (фиг. 4). блока управления, групйа управляющих

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

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

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

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

Таáлице1 г ° «О О O «Ю 4

« « Ю °

Пояснение йФ

Выход запроса 10 устройства

Слово отп

Вход ответа б устройства

Выход готовности 11 устройства

ГОТ. Выход дешифратора 12,. соответствующий признаку ключевого слова.

Выход дешифратора 12, соответствующий признаку буквы

Выход дешифратора 12, соответствующий признаку цифры

Выход дешифратора 12, соответствующий признаку двулитерного разделителя

Выход дешифратора 12, соответствующий признаку однолитерного разделителя

Вход записй регистра 18

Выход дешифратора 12, соответствующий символу конца программы

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

Выход дешифратора 12, соответствующий символу начала комментария

Выход дешифратора 12, соответствующий символу конца комментария

Вход синхронизации блока 2 регистров

Второй вход группы 4 элементов И

Второй вход группы 5 элементов И

Вход Синхронизации блока 25 регистров идентификатора блока 14

Второй вход группы 19 элементов И

Второй вход группы 23 элементов И

Вход синхроййзации блока 16 регистров

Управляющий вход блока 17 для преобразова ния двоично-десятичного коде в двоичной

Счетный вход счетчике 20

Вход обнуления блока 15 регистров бло ка 14 формирования таблицы идентифи-. каторов

Вход обнуления блока 16 регистров

Вход записи блока памяти 22

П1

ЗП1

KOH

СДБ

И1

И2

Сд РгИд

И3

И4

СдРГ

Пр

СчТС

УСТ!

УСТ2

Е Ф е вертай группы; вторые входы элементов И четвертой группы соединены с двенадцатым выходом блока управления, выходы элементов И четвертой группы — с четвертой группой входов блока элементов ИЛИ, вход 5 данных блока памяти символьных строк соединен с вторым выходом первого блока регистров, управляющий вход — с тринадцатым выходом блока управления, выход — с выходом символьных строк устройства, вход записи третьего регистра соединен с четырнадцатым выходом блока управления.

1784999

Таблица 2

Пояс нв ние

Слово

Второй вход группы 34 алвментон И

И5

Р3

Выход схемы сраннения30, соотнвтстнующией сонпадвниь данных

Выход двшифратора ЗХ, соотнетстнующий нуленояу значенив данных

И6

ЗП

Вход записи памяти 28

Вторые входы группы 36 и группы ЗЗ алементон И,сброо поля ссылки регистра 29

Счетный вход счетчика ад—

СТСА реса 27

Второй вход группы 38 элементов И

Второй вход группы 37 элвментон И

3РА

Вход записи регистра адреса 53

Второй вход группы 35 злвмвнтон И

1784999

1784999

/иск

leech и гнтирмкоещв 1 Каючг5ог май

Редактор В.Орлова

Заказ,4З66 Тираж Подписное

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

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

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

Инр.

Ему 7

Составитель А.Сошкин

Техред М.Моргентал Корректор Н.Милюкова