Синтаксический анализатор

 

Изобретение относится к вычислительной технике и может быть использовано и автоматизированных системах обработки данных и произв одства программ для ЭВМ. Цель изобретения - расширение функциональных возможностей за счет обработки выражений, содержащих скобки различных типов, при одновременном повьппении быстродействия и сокращении аппаратурных затрат устройства. Для достижения указанной цели в устройство дополнительно введены шифратор 4 кодов скобок и элемент НЕ-И 6. Введение указанных элементов и порождаемых ими связей позволяет использовать различные виды скобок в анализируемьрс выражениях, определяющих полностью порядок выполнения операций, а также вести синтаксический анализ в темпе поступления лексических единиц. 2 ил, § 1 табл. (Л

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

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

РЕСПУБЛИН (19) (11) А1 (5)) 4 С Об Г 11 00

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

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

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

К ABTOPCH0MV СВИДЕТЕЛЬСТВУ, (21) 4236423/24-24 (22} 27,04.87 (46} 23.1 1.88. Бюл. ) 43 (72) В.К.Водопьянов, С.Н.Вавилов, В.Н.Волков, В.Н.Завьялов и С.П.Зайцев (53) 681,325(088.8) (56) Авторское свидетельство СССР

В 673818, кл. С 06 У 11/00, 1978. Авторское свидетельство СССР

Р 1334149, кл. С 06 Г f1/00, 1986. (54} СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР (57) Изобретение относится к вычисли тельной технике и может быть использовано и автоматизированных системах: обработки данных и производства программ для ЭВИ. Цель изобретения — расширение функциональных возможностей за счет обработки выражений, содержащих скобки различных типов, при одновременном повышении быстродействия и сокращении аппаратурных затрат устройства. Для достижения указанной цели в устройство дополнительно введены шифратор 4 кодов скобок и элемент НЕ-И 6. Введение указанных элементов и порождаемых ими связей позволяет использовать различные виды скобок в анализируемых выражениях, определяющих полностью порядок выполнения операций, а также вести синтаксический анализ в темпе поступления лексических единиц. 2 ил, 1 табл.

1439593 х

3 х

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

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

1, если лексическая единица — операция;

0 в противном случае;

1, если лексическая единица — закрывающая скобка;

0 в противном случае;

1, если лексическая единица — конец выражения;

0 в противном случае; а я+ Че х

На фиг. 1 представлена структурная схема синтаксического анализатора

У t5 на фиг. 2 — блок-схема микропрограм: много управления анализатором.

Синтаксический анализатор содержит ,входной регистр 1, дешифратор 2лея .

,сических единиц, блок 3 микропрограм20 много управления, шифратор 4 кодов скобок, сумматор-вычитатель 5, эле, мент НЕ-И 6.

Входной Регистр 1 дешифратор

,лексических единиц, шифратор 4 кодов

25 скобок и элемент НЕ-И 6 реализованы известным образом на серийно выпускаемой элементной базе.

Входной регистр 1 используется для хранения очередной лексической единицы исходного выражения, дешифратор 2 лексических единиц разделяет, лексические единицы на операнды, операции, скобки (по виду и типуоткрывающие или закрывающие) и конец 35 ! выражения.

Блок 3 микропрограммного управления (БМПУ) выполнен известным способом на программируемых логических матрицах, управляет работой всех эле-40 ментов устройства. Входные сигналы х, ... х (фиг. 2) формирует дешифратор лексических единиц, а х поступает через элемент НЕ-И с суммато ра-вычитателя. На выходе блока мик- 45 ропрограммного управления формируются сигналы микроопераций у, Смысл входных и выходных сигналов следующий:

50 если лексическая единица исходного выражения есть операнд;

0 в противном случае;

1, если лексическая единица — открывающая скобка;

0 в противном случае;

1, если содержание сумматора-вычитателя равно нудю;

0 в противном случае; у " разрешение записи очередной

I лексической единицы во входной регистр 1; у — сложить код очередной от2 крывающей скобки с содержанием сумматора-вычитателя; у — вычесть код очередной закры3 вающей скобки из содержи-. мого сумматора-вычитателя; у — успешное завершение синтак4 сического анализа выражения "Конец анализа"; у — при синтаксическом анализе

5 исходного выражения встречена ошибка — "Ошибка", Шифратор 4 кодов скобок формирует для каждой пары соответствующего вида скобок определенный код. Выбор кода для пары скобок производится следу ющим образом .

Исходя из укаэанного значения глубины вложенности скобок, определяется код для первой пары скобок, который удовлетворяет условию где V>„- глубина вложенности скобок а ;„ — ближайшее простое число, превышающее значение глубины вложенности.

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

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

1439593

Круглые (, ) .

Квадратные

Фигурные (23

43 вход усT— (А+В)I» начальное

1 постуВид используемых скобок Код скобок

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

Если содержимое сумматора-вычитателя равно нул»о, та на ныхаде элемента НЕ-И устанавливается единичнь»й сигнал. 20

Устройство работает следующим образом, Перед началом работы производится начальная установка устройства: обнуление входного регистра 7 и сумма- 2Б тара-вычитателя 5. Лексическая единица исходного выражения поступает на входной регистр 1, а затем через дешифратор 2 лексических единиц, который разделяет входную информацию на операнды, операции, скобки (па виду и типу — открывающая или за.крывающая) и конец нйражения, запускает БМПУ 3 °

Если текущий сигнал-операнд (х = О, х, = 1), то БМПУ 3 вырабатывает микрооперацию у,, которая разрешает запись следующей лексической единицы во входной регистр 1.

Если лексическая единица — откры- 40 вающая скобка (х + = О, х, = О, х = 1), .то по виду скобки шифратор 4 кодов скобок формирует соответствующий код, .который поступает на вход сумматара вычитателя 5,а БМПУ по типу скобки вырабатывает микрооперацию у, кото,рая разрешает сложение кода скобки с содержанием сумматора-нычитателя, и затем микрооперацию у» .

Если лексическая единица — операция (z = О, хз = 1), то БМПУ вырабатывает микрооперацию у».

Если очередной символ — закрывающая скобка (х„ = ", х = О, х4 = 1), ° Э 4 5Б то по виду скобки шифратор 4 кодов скоб формирует соответствующий код, поступающий на вход сумматора-нычитателя 5, а БИПУ разрешает микрооперацией у вычитание кода скобки из соЯ держимаго сумматора-вычитятеля 5 и потом по микраоперации у, запись очередной лексической единицы во нходной регистр 1.

Если поступившая на вход регистра 1 лексическая единица — конец выражения (х =1) тогда БМПУ н соответствии с са5 держанием сумматора-вычитателя 5 вырабатывает либо микраоперацию у, либо микраоперацию у . Если содержимое сумма5 тора-нычитателя 5 равно нулю (х 1), то синтаксический анализ исходного выражения завершен успешно и на выходе

ll устройства появляется сигнал Конец анали а". Если содержимое сумматораны:штателя 5 отлична от нуля (х = О), та выражение содержит синтаксические ошибки и на выходе устройства появляется сгп лал "Ошибка".

Пример 1. Пусть на райстна поступает выражение

П у=трайстна установлено в состояние. На вход регистра пает ленси еска", единица которая затем идентифицируется дешифратаром 2 как круглая аткрына»ощая скобка. ITo виду, скобки шифратор 4 Формирует кад 23 (таблица), который поступает на вход сумматора-вычитателя 5, по типу скобки (аткрынаюшая) БМПУ 3 вырабатывает микраоперацию, разрешающую сложение. кода скобки с содержимым сумматора-вь»читателя. При установке устройства содержимое сумматора-вычитателя абнулено. После сложения значение сумматора-нычитателя равно 23.

БМПУ формируе-. микраоперацию у», разрешения записи ва входной регистр следующей лексической единицы — "А", Дешифратор 2 определяет, что поступивший символ является операндом и запускает БМПУ, который разрешает прием очередного символа выражения.

Знак операции — "+". БМПУ вырабатывает микрооперацию у„ . Следующй символ "В" — операнд. БМПУ разрешает прием очередного символа.

Следующая лексическая единица ")"это закрывающая круглая скобка. По виду скобки шифратор 4 формирует код

„,23 и подает его на вход сумматора-вычитателя 5. БИПУ по типу скобки (закрывающая) вырабатывает микрооперацию, разрешающую вычитание кода скобки из содержимого сумматора-вычитателя.

5 14

В результате операции в сумматоревычитателе содержится ноль.

Далее на вход устройства последовательно поступают сигналы:

"С", "+", "0", которые определяются шифратором 2 лексических единиц как операция, операнд, операция, операнд.

Очередная лексическая единица "ф ", поступившая на вход устройства, определяется дешифратором 2 как "Конец выражения". Сигнал с выхода дешифратора поступает на вход признаков лексических единиц БИПУ 3, а на вход, признаков анализа БИПУ.через элемент

НЕ-И б поступает сигнал с сумматоравычитателя, содержимое которого равно нулю, Ыедовательно, БИПУ вырабатывает микрооперацию уц "Конец анализа", сообщающую об успешном окончании синтаксического анализа, Пример 2. Исходное выражение имеет вид (А+В) 4- С @, в котором вместо круглой закрывающей скобки пос" тавлена квадратная скобка.

Лексическая единица "(" поступает через входной регистр 1 на дешифратор

2 лексических единиц, который определяет, что это круглая открывающая скобка. По виду скобки шифратор 4 кодов скобок формирует код 23, кото-" рый подается на вход сумматора-вычи. тателя 5. БИПУ 3 по типу скобки (открывающая) вырабатывает,микрооперацию у, разрешающую сложение кода скобки с содержимым сумматора-вычитателя 5„

Содержимое сумматора-вычитателя равно нулю (в соответствии с начальной установкой устройства) и после сложения будет равно 23. Далее БИПУ вырабатывает микрооперацию у,, разреша. ющую входному регистру 1 прием следующего символа.

"А" — это операнд. Дешифратор 2 запускает БМПУ, который формирует микрооперацию у и на вход устройства поступает очередная лексическая единица "+" операции. БИПУ разрешает запись следующего символа "В" в регистр 1. Дешифратор 2 определяет, что это операнд, а БМПУ выдает разрешение на прием очередного символа "1".

Полученная лексическая единица определяется дешифратором 2 как квадратная закрывающая скобка. По виду скобки шифратор 4 вырабатывает код

37,.(таблица), который поступает на вход сумматора-вычитателя 5. БИПУ по типу (закрывающая) скобки формирует

39593 6

5

50 микрооперацию у,.которая разрешает сумматору-вычитателю 5 произвести операцию вычитания, В результате содержимое сумматора-вычитателя равно 14. БИПУ вырабатывает следующую микрооперацию у, .

На вход устройства последовательно поступают лексические единицы "-а", С", которые определяются дешифратором как операция н операнд, Очередным символом, поступившим на входной регистр,.является "у", Эта лексическая единица определяется дешифратором 2 как "Конец выражения", Возбуждается БИПУ, который анализирует содержимое сумматора-вычитателя 5. Оно не равно нулю, следовательно, исходное выражение содержит синтаксические ошибки. БИПУ вырабатывает микрооперацию у и на выходе устройства появляется сигнал ошибки, Формула изобретения

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

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

Составитель И. Поливода

Редактор А. Ворович Техред М.Ходанич Корректор Н, Король

Заказ 6078/48 Тираж 704 Подписное

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

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

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