Синтаксический анализатор Советский патент 1988 года по МПК G06F17/27 

4;

GO

I;D ел

со

00

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

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

; На фиг. 1 представлена структурная

схема синтаксического анализатора; I на фиг, 2 - блок-схема микропрограм- I много управления анализатором. I Синтаксический анализатор содержит I входной регистр 1,, дешифратор 2 лек- I сических единиц, блок 3 микропрограммного управления, шифратор 4 кодов скобок, сумматор-вычитатель 5, зле- , мент НЕ-И 6.

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

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

1, если лексическая единица исходного выражения есть операнд; О в противном случае;

1, если лексическая единица - открывающая скобка; О в противном случае;

X,

f

1, если лексическая единица - операция; О в противном случае;

Т, если лексическая еди- : ница - закрывающая скобка; О в противном случае;

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

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

0

5

У, 3035

40 45

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

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

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

У„ У. Ус amin ък где V. - глубина вложенности скобок;

а„,;„ - ближайшее простое число,

превышающее значение глубины вложенности.

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

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

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

п

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

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

Устройство работает следующим образом.

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

Если текущий сигнал-операнд

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

Если лексическая единица - открыающая скобка (к5 О, X, О, X 1), то по виду скобки шифратор 4 кодов скобок формирует соответствующий код, оторый поступает на вход сумматора- вычитателя 5, а по типу скобки вырабатывает микрооперацию у, кото- рая разрешает сложение кода скобки с содержанием сумматора-вычитателя, и затем микрооперацию у .

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

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

1439593

циен у

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

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

0 ошибки и на выходе устройства появляется сигнал Ошибка.

Пример 1. Пусть на вход уст- ройствг поступает выражение (А+В)

G г С - Dfjf:.

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

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

Знак операции - +, БМПУ вырабатывает микрооперацию у . Следующй

0 символ Б - операнд. БМПУ разрешает прием очередного символа.

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

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

5

микрооперацию

10

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

Далее на вход устройства последовательно поступают сигналы: Ч, С, +, D, которые определяются шифратором 2 лексических единиц как операция, операнд, операция, операнд.

I Очередная лексическая единица #: ,

поступившая на вход устройству, оп; ределяется дешифратором 2 как Конец выражения. Сигнал с выхода дешифратора поступает на вход признаков

i лексических единиц БМПУ 3, а на вход

i признаков анализа БМПУ через элемент

I НЕ-И 6 поступает сигнал с сумматораi вычитателя, содержимое которого равно

; нулю, Следовательно, БМПУ вырабатыва : ет микрооперацию у Конец анализа,

сообщающую об успешном окончании син- 2о таксические ошибки.

ет микрооперацию . ко

таксического анализа.

Пример 2. Исходное выражение имеет вид (А+В 4t- С , в котором вместо круглой закрывающей скобки поставлена квадратная скобка.

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

А - это операнд. Дешифратор 2 запускает БМПУ, который формирует микрооперацию у и на вход устройства поступает очередная лексическая единица + операции. БМПУ разрешает запись следующего символа В в регистр 1. Дешифратор 2 определяет, что это операнд, а БМПУ выдает разрешение на прием очередного символа 3. Полученная лексическая единица определяется дешифратором 2 как квадратная закрывающая скобка. По виду скобки шифратор 4 вьфабатывает код 37 (таблица), который поступает на вход сумматора-вычитателя 5. БМПУ по типу (закрывающая) скобки формирует

сумматору-вычитателю операцию вычитания. содержимое сумматора ,но 14. БМПУ вырабаты микрооперацию у .

На вход устройств поступают лексически С, которые определ ром как операция и о

Очередным символо на входной регистр,, Эта лексическая един g дешифратором 2 как Возбуждается БМПУ, к рует содержимое сумм ля 5. Оно не равно н но, исходное выражен

25

30

35

40

45

50

55

ройства появляется с Формула изо

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

1439593

микрооперацию

. которая разрешает

таксические ошибки.

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

На вход устройства последовательно поступают лексические единицы V, С, которые определяются дешифратором как операция и операнд.

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

0

5

0

5

0

5

ройства появляется сигнал ошибки. Формула изобретения

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

ходУ шифратора кодов скобок, вход типа скобок дешифратора лексических которого соединен с выходом признаков единиц,

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

С начало j

1

I / I

С Конец 3

Фие.2