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

 

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных и производства программ для ЭВМ в условиях с жесткими требованиями к быстродействию и аппаратурным затратам. Цель изобретения - повышение быстродействия, сокращение аппаратурных затрат и расширение функциональных возможностей за счет обеспечения полного синтаксического анализа исходных вьфажений. Для достижения указанной цели в устройство введены шифратор 4 основ, буферный регистр 8, накапливающий сумматорвычитатель 9 и дешифратор 10 аксиомы. Реализация блока памяти на реверсивных сдвигающих регистрах, введение накапливающего сумматора-вычитателя и дешифратора аксиомы приводит к сокращению аппаратурных затрат и существенному повьш1ению быстродействия синтаксического анализатора. Применение шифратора основ, дешифратора приоритетов в сочетании с дешифратором аксиомы и другими блоками синтаксического анализатора обеспечивает полный синтаксический анализ вводимого текста. з.п. ф-лы, 3 ил. с б (Л с

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

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

РЕСПУБЛИК

А1. (19) (И) (51) 4 G 06 F 11/00

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

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

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

К д ВТОРСНОМУ СВИДЕТЕЛЬСТВУ (21) 4007832/24-24 (22) 15.01.86 (46) 30.08.87. Бюп. У 32 (72) С. Н. Вавилов, В. К. Водопьянов и В. Н. Цымбал (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 637818, кл. G 06 F ll/00, 1976.

Авторское свидетельство СССР

Ф 1130879, кл. G 06. F 15/38, 1982. (54) СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР (57) Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки данных и производства программ для ЭВМ в условиях с жесткими требованиями к быстродействию и аппа" ратурным затратам. Цель изобретения повышение быстродействия, сокращение аппаратурных затрат и расширение функциональных воэможностей за счет обеспечения полного синтаксического анализа исходных выражений. Для достижения указанной цели в устройство введены шифратор 4 основ, буферный регистр 8, накапливающий сумматорвычитатель 9 и дешифратор 10 аксиомы.

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

1 i 3341

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

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

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

На фиг. 1 изображена структурная схема синтаксического анализатора, на фиг. 2 — структурная схема блока памяти; на фиг. 3 — блок-схема микропрограммного управления анализатором, 25

Синтаксический анализатор (фиг. 1) содержит входной регистр 1, дешифратор 2.лексических единиц, блок 3 управления, выполненный, например, на программируемых логических матрицах, шифратор 4 основ, блок 5 памяти, де шифратор б кодов операции, дешифратор

7 приоритетов, буферный регистр 8, накапливающий сумматор-вычитатель 9 и дешифратор 10 аксиомы.

В состав блока 5 памяти входит группа реверсивных регистров 11 сдвига.

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

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

Блок 3 управления управляет работой всех элементов устройства. Пример „ его функционирования для операции

"+" и "х" описан блок-схемой микропрограммного управления (фиг, 3), где входные сигналы Х„- Х, Х> формирует

49 2 дешифратор 2 лексических единиц, Х дешифратор 7 приоритетов; Х,Х Х„ дешифратор кодов операции; К „, — дешифратор аксиомы. На выходе блока 3 управления формируются сигналы микроопераций Уз У .У 3 и У16 à акже сигналы У,, У, У, У, У, У г

У, являющиеся совокупностями микроопераций, Содержательный смысл входных и выходных сигналов следующий:

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

Х„

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

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

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

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

1, если лексическая единица исходного выражения есть закрывающая скобка;

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

1, если приоритет терминала, занесенного в К-е разряды блока 5 памяти, больше приоритета терминала, находящегося в (й-1) разрядах блока памяти;

О, в противном случае; 1, если терминал в (Й-1) разрядах блока 5 памяти, есть код знака плюс;

О, в противном случае; если терминал в (И-1) разрядах блока 5 памяти есть код знака умножить;

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

О, в противном случае", 1334149

1, если терминал в (N-I) разрядах блока 5 памяти, ес2 ь код открывающей скобки;

Х

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

1, если в сумматоре содержится код нетерминала

X 11 =

О, в противном случае.

10 запись кода нетерминала

"F" в буферный регистр 8; запись кода нетерминала ос35 новы РхГ в буферный регистр 8; вычитание кода нетерминала основы из содержимого накапливающего сумматора-вычитателя 9; сдвиг на 2 разряда вправо (в стс1рону старших разрядов) содержимого блока 5 памяти; запись кода нетерминала основы "F" в буферный регистр 8; запись кода нетерминала ос50 новы IIF4.FII в буферный регистр 8; сдвиг на 1 разряд .вправо содержимого блока 5 памяти; выдача сообщения Ошибка

tt и °

55 сдвиг на 1 разряд влево содержимого блока 5 памяти; запись кода терминала Знак и плюс" в буферный регистр 8; у1

V12

1 (V„ t V УЗ У4» У 1 2

4 9» 9 У13 4 1У14

»„1 » = 1»»»„I "» (»

У1ь s Yn t 9 = У1 У1д

12 УЬ 19 У®

1У9 У4» tg .(Y2 У» У

Ув» "и =У, где у — запись кода терминала иОт1 и .крывающая скобка в буфер- . ный регистр 8; 20 у - сложение кода терминала

2 (нетерминала) в накапливающем сумматоре-вычитателе 9, поступающего из буферного регистра 8; 25 у - запись кода терминала От3 крывающая скобка" в блок 5 памяти; у — чтение следующей лексичес4 кой единицы исходного выра- 30 жения иэ входного регистра I; у — запись кода терминала иЗнав

1<, tt умножить в буферный регистр 8; у — запись кода терминала "Знак

1» tt плюс в блок(5 памяти; у - запись кода терминала ".Знак

11 и умножить в блок 5 памяти; у — запись кода терминала "3a18 крывающая скобка" в блок .5 памяти; у — запись кода терминала иКо19 чец исходного выражения (знак иЪ и в блок 5 памяти.

Шифратор 4.основ формирует коды терминалов и нетерминалов.

Блок памяти 5 — это память с последовательным безадресным принципом записи и чтения. В состав блока памяти (фиг. 2) входит группа реверсивных сдвигающих регистров 11. Запись информации производится в старшие (К-e) разряды регистров.

Реверсивные регистры 11 сдвига блока 5 памяти поразрядно сдвигают коды терминалов и совместно с дешифратором 7 приоритетов осуществляют сравнение приоритетов терминалов, а также совместно с дешифратором 6 кодов операций производят выбор основы для свертки исходного выражения.

Буферный 8 регистр используется для хранения кодов терминалов и нетерминалов.

Накапливающий сумматор-вычитатель

»

9 выполняет либо .функцию сложения кодов терминалов и нетерминалов, либо функцию вычитания кодов нетерминала основ°

Дешифратор 10 аксиомы выделяет код нетерминала "F", определенный в качестве начального нетерминала (или аксиомы) и соответствующего успешному заьершению синтаксического анализа.

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

Лексические единицы исходного выражения последовательно поступают на входной реггстр 1, а затем на дешифратор 2 лексических единиц, который выделяет операнды, операции, скобки и конец выражения иФи.

При поступлении лексической единицы, например, открывающей скобки (Х 9 = О, Х, 1) дешифратор 2 лексических единиц запускает блок 3 управления, который вырабатывает совокупность микрооперации (Y„). Управляющие сигналы с блока 3 управления по5 13341 ступают на вход шифратора 4 основ и формируют код терминала открывающей скобки, а затем разрешают запись кода терминала в бусрерный регистр 8 (микрооперация у, ) и ложение его с содержимым накапливающего сумматоравычитателя 9 (микрооперация у ), а

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

Если следующая лексическая единица есть операнд (Х q = О, Х = О, Х = 1), то блок 3 управления выполняет совокупность микрооперации (Y

Y ): :на шифраторе 4 основ формируется код нетерминала "F", производится запись кода нетерминального символа

"F" в буферный регистр 8 (микрооперация у ), происходит сложение содержимого накапливающего сумматора-вычитателя 9 и кода, вь:полняется сдвиг на 1 разряд влево содержимого блока

5 памяти (микроаперация у ) и выра Ъ 13 батывается" разрешаюп ий сигнал на О чтение очередной лекс.ическай единицы из входного регистра 1. Если лекси" ческая единица не операция (Х3 = О, Х вЂ” О), то происходит формирование сигнала (Y ), сообщающего об ошибке. .3

После записи кода терминала в старшие разряды реверсивных регистров сдвига блока 5 памяти, содержимое N-x и (N-1)-х разрядов поступает на дешифратор 7 приоритета,.который формирует логический сигнал отношения приоритетов текущего терминального символа и предшествующего. Если код терминала, занесенный в М-е разряды реверсивных регистров сдвига блока 5 памяти, имеет приоритет меньший или равный приоритету кода терминала, занесенного в (И"1)"e разряды .(Х - О), то ко терминала с (Й-1)"х разрядов блока 5 памяти поступает на .1 „ вход дешифратора 6 ксдов операции, который формирует. сигнал, определяющий вид основы для свертки исходного выражения. Дешифратор 6 кодов опера, ции запускает блок 3 управления, который разрешает выполнение сигналов (Y, -Y>- ). Если в (И-1)"х разрядах реверсивных сдвигающих регистров находится, например, код терминала

49

Знак плюс {X G, Х вЂ” l ), та буферный регистр 8 записывается код нетерминала основы F+F" (микрооперация у ), затем из содержимого накапливающего сумматора — вычитателя

9 вычитается код нетерминала основы (микрооперация у ), а в буферный регистр 8 заносится код нетерминала (микрооперация у ), после мего производится сложение кода нечермина.па с содержимым накапливающего сумматора-вычита.леля 9 (микрооперация у ) и осуществляется сдвиг на 2 раз1 ряда вправо содержимого реверсивных сдвигающих регистров блока 5 памяти. (микрооперация у ), Сигнал с дешифратора 2 лексических единиц, соответствующий текущей лексической единице, например, знаку плюс (Х = О, Х = О, Х, = 1), инициирует блок 3 управления, управляющие сигналы которого разрешают сдвиг на 1 разряд влево садержимого реверсивных сдвигающих регистров блока 5 памяти и выполнение совокупностей микрооперации (У4 Уь).

Если код терминала, занесенный в

И-е разряды реверсивных сдвигающих регистров блока 5 памяти, имеет боль--. ший приоритет., чем код терминала, содержащийся в {Й-1)-х разрядах Х

6 — 1, то,цешифратор 7 приоритетов не разрешает прохождение на блок 3 управления сигнала с дешифратора 6 кодов операции. Содержимое блока 5 памяти (сдвигаемых) сдвигается на 1" разряд вправо., код терминала выталкивается из N-х разрядов в реверсивных регистрах сдвига (микрооперация у. ), 11 блок 5 памяти подготавливается к приему кода терминала (7 ): содержимое блока 5 памяти сдвигается влево на 1 разряд (микросперация у „ ). .Текущая лексическая единица сдешифратара 2 с помощью блока 3 управления формирует код терминала, который заносится .в буферный регистр 8 и блок 5 памяти, добавляется к содержимому накапливающую сумматора-вычитателя 9, а затем происходит переход к очередной лексической единице.

Если следующая лексическая единиI ца есть закрывающая скобка (Х > = О, Х = О, К = 1), то дешифратор 2 лексических единиц запускает блок 3 управления, управляющие сигналы которого разрешают формирование на шифраторе ч основ хода терминала Закрыft вающая скобка и запись кода терми7 13341 нала в блок 5 памяти (микрооперация у ), откуда код терминала поступает

1В также на вход дешифратора 7 приоритетов. „ дешифратор 7 приоритетов раз5 решает (Х = О) прохождение сигнала с дешифратора 6 кодов операции, который определяет выбор вида основы, Если в (N-1)-х разрядах реверсивных регистров сдвига находится, например, код терминала "Открывающая скобка" (Х1 = О, ХВ=О, Х, = 1), то дешифратор 6 кодов операции возбуждает блок 3 управления, выходные сигналы

15 ) которого Выполняют запись 15 нетерминала основы (F) в буферный регистр 8 (микрооперация у9), разрешает чтение очередной лексической единицы из выходного регистра 2 (микрооперация у ), вычитание из содержимого накапливающего сумматора-вычитателя 9 кода нетерминала основы (микрооперация у,), затем в буферный регистр 8 заносится код нетерминала (микрооперация у ), производится 25 сложение содержимого накапливающего сумматора-вычитателя 9 с кодом нетерминала (микрооперация у1) и осуществляется сдвиг на 2 разряда вправо содержимого реверсивных сдвигающих ЗО регистров блока 5 памяти (микрооперация у9). Если текущая лексическая единица есть закрывающая скобка Х .=

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

Y 1 ), а затем на шифраторе 4 основ происходит формирование кода термина- 40 ла Закрывающая скобкан и запись" (У9) кода терминала в блок 5 памяти (микрооперация Y ). Далее работа устройства повторяется °

Если очередная лексическая едини- 45 ца есть конец выражения 4" (Х = О, Х = О, Х5= О, Х9= 1), то дешифратор 2 лексических единиц запускает блок 3, выходные сигналы которого разрешают шифратору 4 основ формиро- 50 вания кода терминала Конец выражеII ниян и запись (Y, ) кода терминала

1О в старшие разряды реверсивнЬ1х регистров сдвига блока 5 (микрооперация у ). С,блока 5 памяти коды терми19 налов из N-го и (М-I)-го разрядов реверсивных регистров сдвига постуВ пают на дешифратор 7 приоритетг>в, с которого снимается сигнал (Х = 0 ), 49

8 разрешающий прием сигнала от. пешифратора 6 кодов операции, который анализирует код терминала, содержащийся в (М-1)-х разрядах реверсивных сдвигающих регистров, и формирует сигнал выбора вида основы. Если выбрана несуществующая основа (Х, = О Х8 = О

Х „ = О), то н блоке 3 управления формируется управляющий сигнал выдачи ошибки (Y ). Если, например, выбрана основа "FxF (Х, = 1), то блок 3 управления формирует выходные сигналы (Y,, V ), которые опреде; t5 ляют йоследовательность работы устройства. Далее дешифратор 2 лексичес ких единиц анализирует текущую лексическую единицу — конец выражения № (Х9 = О Х9 = 1) блок 3 управления, который передает на вход дешифратора 10 аксиомы содержимое сумматора — вычитателя 9 ° Если в накапливающем сумматоре-вычитателе

9 находится код нетерминала IIFII (Х„=

1), то дешифратор 10 аксиомы возбуждает в блоке 3 управления сигнал, по которому процесс синтаксического анализа завершается успешно. Если содержимое накапливающего сумматора-вычитателя 9 отлично от кода нетерминала F" (Х„ = О), то дешифратор 10 аксиомы воэбужает б 3 управления, управляющие сигналы которого формируют сигнал ошибки (У 1 ).

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

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

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

3 управления, формирующего совокупность микроопераций, которые блокируют входной регистр 1, запускается шифратор 4 основ на формирование кода терминала Открывающая скобка

tl tl затем производится запись кода терминала в буферный регистр 8, сложение кода терминала с содержимым накапливающего сумматора-вычитателя 9. В блоке 5 памяти происходит сдвиг на один разряд влево содержимого реверсивносдвигающих регистров, в старшие разряды которых записывается код терминала, после чего разрешается -чтение с входного регистра 1 следующей

9 13341 лексической единицы исходного выражения.

Лексическая единица "А" дешифриру ется дешифратором 2 как операнд (Х

1) и выдается сигнал на запуск бло ка 3 управления, который разрешает формирование на шифраторе 4 основ кода нетерминала "F", заносит его в буферный регистр 8, суммирует содержимое накапливающего сумматора-вычитателя 9 с кодом нетерминала, производит сдвиг на один разряд влево содержимого блока 5 памяти и снимает блокировку с входного регистра 1, с 5 которого поступает очередная лексическая единица "+".

Дешифратор 2 лексических единиц распознает ее как операцию (Х = 1) и возбуждает блок 3 управления, ко- 20 торый запускает шифратор 4 основ, формирующий код терминала Знак плюс,. записываемый в буферный регистр 8 и в Й-е разряды реверсивных сдвигающих регистров блока 5 памяти, проис- 25 ходит сложение кода терминала с содержимым накапливающего сумматоравычитателя 9 ° Код терминала ("+")

"Знак плюс" с Й"х раэрядоВ и код терминала "Открывающая скобка" с (Й-1)"х ЭО разрядов реверсивным регистров сдвига поступает на дешифратор 7 приоритета. Так как приоритет термииа.И И

I ла Знак плюс" больше приоритета терминала Открывающая скобка (Х = и и

1), то дешифратор 7 приоритетов блокирует запуск дешифратора 6 кодов операции блока 3 управления, который разрешает ввод и анализ следующей - .лексической единицы "(".

Лексическая единица, поступающая нд дешифратор 2, определяется как открывающая (точка) скобка. С помощью блока 3 управления шифратор 4 основ формирует код терминала открывающей скобки, который заносится В буферный регистр 8, складывается с содержимым накапливающего сумматора-вычитателя

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

В процессе дешифрирования дешифратор 2 лексических единиц определяет ,ее как операнд (Х = 1) и запускает блок 3 управления, выходные сигналы с которого разрешают шифратору 4 основ формирование кода нетерминала

49 1О

11 ll запись е г о в буферный регистр

8, сложе ние кода с содержимым н а к аплив ающе го сумматора- выч и т ат еля 9 и чтение очередной лексической единицы с входно го регистра

Поступившая н а дешифратор 2 л е кс ич е ск ая единица, " +", есть операция (Х = 1 ) . Блок 3 уп р а вления н а шифратор е 4 основ форми ру е т код терминала 1. 3 н ак плю с и з апи сыв а е е г о в старшие разряды блока 5 памяти, о т куда код терминала поступает также н а дешифратор 7 приоритета, на в т орой вход которого по с туггае т иэ (Й- 1 ) - х разрядов блока 5 памяти код терминала "Открывающая скобка", Дешифратор 7 (Х г = 1 ) блокирует прием сигнала с де шифр ато ра 6 кодов операции блоком

3 управления . В блоке 5 памяти производится сдвиг н а один ра э р я д Вправо содержимого р ев е р сив ных сдвиг RloIIIHx, регистров, а затем сдвиг содержимого блока 5 памяти влево н а 1 р аэ р яд .

1 Дешифрат ор 2 дешифрируе т текущую лексиче скую единицу " + " (Х 1 ) и з апускает шифратор 4 о сно и, с которого код терминала " (+ ) " " Знак плюс " од. новреме нно заносится в буферный р егис тр 8 и блок 5 памяти, а затем, складывается содержимым нак аплив ающего сумматора-вычит а теля 9 . После э т ого происходит считывание очередной ле ксич е ской единицы с входного регистра 1 .

Лексическая единица " С" — о п ер анд который формирует на шифраторе 4 код нет ермин ала " F " . Ко д не т ермин ала э аписыв ается в буфе рный регистр 8, и одновременно сдвигается содержимое блока 5 памяти влево на один ра э ряд, затем код н етерминала суммир уе т ся с содержимым н ак аплив ающе г о сумматораВычит ателя 9 .

Очередная лексическая единица " ) " ; по ступ а ет н а дешифратор 2 и апр еделяется как э акрыв ающа я скобка, блокирует ся Входной ре гис тр 1, . формируетН ся код терминала Закрывающая скобка, который записывается в блок 5 памяти и поступает, на дешифратор 7 приоритетов, который по приоритетам кодов текущего .(Закрывающая скобка ) и предыдущего (" Знак плюс") терминалов формирует сигнал (Х = 0), разрешающий выбор Вида ОсноВы свертки» Дешиф» ратор 6 кодов операции по коду предыдущего терминала определяет Вид основы (Х > = 1)» Код нетерминала осноll 1334 вы F+F заносится в буферный регистр

8 и вычитается из содержимого накапливающего сумматора-вычитателя 9, а содержимое блока 5 памяти сдвигается

5 на 2 разряда вправо. Код нетерминала ?" заносится в буферный регистр 8 и складывается с содержимым накапливающего сумматора-вычитателя 9. Дешифратор 2 определяет текущую лексическую единицу как закрывающую скобку, Блок 3 управления формирует сигнал, который производит сдвиг влево на один разряд содержимого- блока памяти и запись кода терминала Закрывающая )б скобка zz старшие разряды реверсивно сдвигающих регистров Дешифратор

7 приоритетов разрешает выбор основы

"(F) " (Х„о = 1), так как в (М"1) "х разрядах реверсивных регистрах сдвига 20 содержится код терминала Открывающая скобка". Код нетерминала основы записывается в буферный..регистр 8 и вычитается из содержимого накапливающего сумматора-вычитателя 9. Одновременно сдвигается содержимое блока 5 памяти на два разряда вправо и сни- мается блокировка с входного регистра 1, с которого на дешифратор 2 поступает лексическая единица ")". В 30 буферный регистр 8 заносится код нетерминала "F и складывается с содержимым накапливающего сумматора-вычитателя 9.

Текущая лексическая единица ")и определяется дешифратором 2 как закрывающая скобка (Х = 1), происходит блокирование входного регистра 1. Далее устройство работает по циклу, приведенному выше. 40

Текущая лексическая единица "Xtt определяется дешифратором 2 как orieрация (Х = 1). Сформированный шифратором 4 код терминала Знак умно- 4> жить" заносится в блок 5 памяти, запускается дешифратор 7 приоритетов, формирующий запрещающий сигнал (Х =

1). Код терминала заносится в блок

5 памяти, складывается с содержимым накапливающего сумматора-вычитателя

9 и осуществляется переход к следующей лексической единице.

Очередная лексическая единица

"D" - операнд. В накапливающем сумматоре-вычитателе 9 добавляется код нетерминала "Ftt, производится сдвиг влево на один разряд содержимого блока 5 памяти и выбирается следующая

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

ttÀ1! )

Дешифратор 2 выделяет лексическую единицу и запускает шифратор 4 основ, tt формирующий код терминала Конец выражения", ко орый заносится в блок 5 памяти и запускает дешифратор 7 приоритетов. Последний разрешает выбор основы вида "F+F" (Х, = 1). Сначала код нетерминала основы вычитается иэ содержимого накапливающего сумматоравычитателя 9, а затем к содержимому

tt t! до б авля е тся ко д н ет е рминала F, далее дешифратор 2 определяет текущую лексическую единицу как конец выражения (Х z = 1 ) . Блок 3 уп р авления ра з решает выдачу содержимого накапливающего сумматора в вычи тателя 9 н а цешифра тор 1 0 аксиомы . Т ак как в накапливающем сумматоре-вычит ат еле

Il tt

9 находится код нет е рминала F, то дешифратор 1 0 аксиомы запускает блок

3 управления, который успешно з ав ер шает синтаксический анализ исходного выражения .

Пример 2 . Пусть исходное выражение имеет вид ((А +, В ) х С .ф, которое содержит ошибку — нет з ак рыв ающей скобки .

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

2 и определяется к ак открывающая скобка . Запускается блок 3 уп равл ения, который блокирует входной р егистр 1, формирует н а шифраторе 4 о снов код терминала Открывающая скобка, который записывается в буферный регистр 8, сдвигает содержимое блока

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

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

Лексическая единица " (tt есть о т— крыв ающая скобка, и цикл работы у с тройс тв а повторяется .

tI It

Очередная лексическая единица А дешифрируется .как операнд. На шифраторе 4 формируется код нетерминала

Р, который поступает в буферный регистр 8, суммируется с содержимым накапливающего сумыа..ора."вычитателя

9, содержимое блока 5 памяти сдвигается на один разряд и происходит переход к следующей лексической едини13

1334149 це - +". "+" — операция., формируется код соответствующего терминала, который заносится в блок 5 памяти, откуда поступает на дешифратор 7 приоритетов,- блокирующий прием сигнала блоком 3 управления с дешифратора 6 кодов операции. Код терминала записывается в буферный регистр 8 и складывается с содержимым накапливающего сум- 10 матора-вычитателя 9, после чего выбирается очередная лексическая единица

"В»

Дешифратор 2 определяет ее как операнд. Содержимое накапливающего сум- 15 матора-вычитателя 9 увеличивается на значение кода нетерминала F, блок

5 памяти подготавливается к приему очередного кода терминала, Следующая лексическая единица } 20 дешифрируется как закрывающая скобка.

Шифратор 4 формирует код терминала

И tl

Закрывающая скобка, который записывается в блок 5 памяти и поступает на вход дешифратора 7, в который по при- 2 оритетам текущего кода терминала и предыдущего (Знак плюс" ) разрешает блоку 3 управления выбор основы F+

+F . Код нетерминала основы вычитаетtl ся из содержимого накапливающего сум- 30 матора-вычитателя 9, а в блоке 5 памяти содержимое сдвигается на два разряда вправо, содержимое сумматора складывается с кодом терминала "F".

Дешифратор 2 определяет, что текущая лексическая единица — закрывающая скобка. Код терминала Закрывающая скобка заносится в блок S памяти, 11 запускается дешифратор 7 приоритета, который разрешает выбор основы (F), 40

Блок 3 управления считывает очередную лексическую единицу "F,(Õ), одновременно из содержимого накапливающего сумматора-вычитателя 9 вычитается код нетерминала основы, сбрасывается содержимое 2 старших разрядов в блоке

5 памяти, к содержимому накапливающего сумматора-вычитателя 9 добавляется код нетерминала "F .

Текущая лексическая единица Х вЂ” 1t0 операция, Код терминала "Знак умноИ жить записывается в блок 5 памяти, складывается с содержимым накапливающего сумматора-вычитателя 9 и происходит переход к анализу следующей лексической единицы "С", 1E !!

С " операнд, код нетерминала

11 tt

F суммируется с содержимым накапливающего сумматора-вычитателя 9, а блок 5 памяти сдвигает содержимое на 1 разряд влево °

Очередная лексическая единица конец выражения ф . Код терминала записывается в блок 5 памяти, поступает на дешифратор 7 приоритетов, Возбуждается блок 3 управления и выбирается основа "FxF код нетерминала, который вычитается из содержимого накапливающего сумматора-вычитателя 9, сбрасывается 2 старших разряда блока 5 памяти, а содержимое накапливающего сумматора-вычитателя 9 увеличивается на код нетерминала "F".

Дешифратор 2 определяет, что текущая лексическая единица — конец выражения и содержимсе накапливающего сумматора-вычитателя 9 по сигналу с блока 3 микропрограммного управления поступает на дешифратор 10 аксиомы, который определяет что содержимое сумматора отлично ст кода нетерминала

"F" и возбуждает в блоке 3 микропрограммного управления сигнал ошибки.

Формула и з обре т е н и я

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

Фиг. 2

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

16 которого являются выходами признаков

"Ошибка и Конец анализан устройства соответственно.

2. Устройство по и. 1, о т л ич а ю щ е е с я тем,,что блок памяти содержит и. реверсивных сдвигающих регистров разрядности N, где и " число разрядов кода терминалов, Й максимальное число терминалов во входном выражении, причем группа выходов . (N-1) разрядов и группа выходов N разрядов реверсивных сдвигавших регистров .образуют первый и второй выходы блока соответственно, а входы управления сдвигами информации на один разряд влево, на один разряд вправо и на два разряда вправо реверсивных

I сдвигающих регистров соответственно объединены и образуют входы управления группы блока.

1334)49

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

Редактор Е. Конча Техред H.Попович Корректор М, Демчик

Заказ 3964/<6

Тираж 672 Подписное

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

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

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