Мартыненко Б.К. Синтаксически управляемая обработка данных. Изд. 2-е, дополн

Подождите немного. Документ загружается.

Рис.2.4. Операционная среда после завершения действий в состоянии 5.

В состоянии 6: происходит безусловное подавление текущего состояния —

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

верхнему символу магазина (2) определяется возвратное состояние 8. В мага-

зине процессора остается один магазинный символ (1). Состояние операцион-

ной среды не изменяется.

В состоянии 8: безусловно выполняется действие Close F in F. Так как n ≠0,

то произведение n

Fac, равное 1, передается в предыдущее окружение F в его

поле Fac, а экземпляр F1 уничтожается. Указатель CurEnv переводится на объ-

ект F. Состояние операционной среды в этот момент представлено на рис.2.5.

Следующее состояние управления — 10.

Рис.2.5. Операционная среда

после завершения действий в состоянии 8.

В состоянии 10: текущее состояние подавляется. По таблице возвратных

состояний для текущего (подавляемого) состояния (10) и верхнего символа ма-

газина (1) определяется возвратное состояние 7. Магазин процессора опусто-

шается. Состояние операционной среды не изменяется.

В состоянии 7: безусловно выполняется действие Close_F_in_S. Произведе-

ние n

Fac, равное 2, передается в поле Fac предыдущего окружения S, а экзем-

пляр объекта F уничтожается. Указатель CurEnv переводится на объект S. Со-

стояние операционной среды в этот момент изображено на рис.2.6. Следующее

состояние управления — 9.

Рис.2.6. Операционная среда

после завершения действий в состоянии 7.

В состоянии 9: безусловно выполняется операция Finish. Печатается резуль-

тат: ″2!=2″ и уничтожается последний экземпляр объекта, воплощающего ло-

кальное окружение конструкции S — CurEnv = Nil. Процессор переходит в со-

стояние 11.

В состоянии 11: обработка завершается, так как это состояние конечное.

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

Аккермана. Без особых комментариев приведем еще один пример

рекурсивного алгоритма — алгоритма вычисления функции Аккермана. По

сравнению с предыдущим примером это описание более ООП-последователь-

ное. Все используемые в нем объекты являются наследниками одного и того же

абстрактного типа объекта TProto.

Определение функции Аккермана:

Ackermann(m ,n )=if m =0&n >=0 then n +1

elif n =0&m >0

then Ackermann(m –1,1)

elif m >0&n >0

then Ackermann(m –1,Ackermann(m ,n –1))

fi.

Ackermann -- Трансляционная грамматика

вычисления функции Аккермана

Nonterminals: MAIN, A.

Terminals: 'Start', 'Finish', 'Alarm', 'SetResult',

'Open_A_in_MAIN', 'Close_A_in_MAIN',

'Open1_A_in_A', 'Open2_A_in_A', 'Open3_A_in_A',

'Close_A_in_A'.

Forward pass resolvers: Valid, Condition1, Condition2, Condition3.

MAIN: 'Start', { Создает первичное окружение

— экземпляр объекта Main. У объекта

Main есть поля данных m, n, Res, mIsValid, nIsValid, причем m и n

инициализируются терминал-действием 'Start'. Флажки, mIsValid и

nIsValid устанавливаются предикатом Valid и используются терминал-

методом 'Alarm', а Res вычисляется подконструкцией A конструкции

MAIN.}

( Valid, {Проверяет параметры m и n на допустимость}

'Open_A_in_MAIN', {Создает экземпляр объекта A с передачей ему парамер-

тов m и n из Main.}

A , {Обращение к интерпретации подконструкции A.}

'Close_A_in_MAIN' ; { Передает результат из поля Res подконструкции A в

поле Res конструкции MAIN и уничтожает локаль-

ный контекст подконструкции A.}

'Alarm', {Сообщает о недопустимости параметров m и n.}

'Finish' {Ликвидирует первичное окружение — экземпляр объекта Main,

предварительно печатая вычисленное значение функции Аккерма-

на.}

{Когда интерпретируется правило для конструкции A, ее локальный

контекст (экземпляр объекта типа TA) уже создан надконструкцией MAIN

или A. У объекта A есть поля данных m, n и Res, причем m и n

инициализированы надконструкцией MAIN или A, а поле Res самой

данной конструкцией A.}

A : Condition1, {m =0&n >=0}

'SetResult' ; { Res := n +1 }

Condition2, {n =0&m >0}

'Open1_A_in_A', {Создание нового инициализированного экземпляра A}

A, {Ackermann (m –1, 1)}

'Close_A_in_A' ; {Передача значения поля Res подконструкции A в поле Res

конструкции A и уничтожение локального контекста под-

конструкции A }

Condition3, {m >0&n >0}

'Open2_A_in_A', {Создание нового инициализированного экземпляра A }

A, {Ackermann (m, n –1)}

'Close_A_in_A', {Передача результата подконструкции A (значения поля Res)

в поле Res конструкции A и уничтожение локального кон-

текста подконструкции A }

'Open3_A_in_A', {Создание нового инициализированного экземпляра A }

A, {Ackermann ( m –1, Ackermann(m , n –1))}

'Close_A_in_A'. {Передача результата подконструкции A (значения поля Res)

в поле Res конструкции A и уничтожение локального кон-

текста подконструкции A }

ENVIRONMENT

type

PProto = ^TProto; {Протообъект — абстрактный объект, от которого наследу-

ются все другие объекты , представляющие локальные ок-

ружения конструкций}

TProto = object

Prev { Указатель на надконструкцию},

Next { Указатель на подконструкцию }: Pointer;

end;

{Локальный контекст конструкции MAIN и методы работы с ним}

PMain = ^TMain;

TMain = object ( TProto )

{ Вход:} m, n,

{ Выход:} Res : integer;

{ Флажки:} mIsValid, nIsValid : Boolean;

{ Методы:}

constructor Init;

destructor Done;

destructor AlarmDone;

procedure OpenA_in_MAIN;

procedure Close_A_in_MAIN;

function Valid : Boolean;

end ;

{Локальный контекст конструкции A и методы работы с ним .}

PA = ^TA;

TA = object ( TProto )

{Параметры: } m, n,

{Результат: } Res : integer;

{Методы:}

constructor Init ( valm, valn : integer );

destructor Done_A_in_MAIN;

destructor Done_A_in_A;

procedure SetResult;

procerure Open1_A_in_A;

procerure Open2_A_in_A;

procerure Open3_A_in_A;

procerure Close_A_in_A;

function Condition1 : Boolean;

function Condition2 : Boolean;

function Condition3 : Boolean;

end ;

var CurEnv : Pointer; { Указатель на текущее окружение — цепочку локальных кон-

текстов вложенных экземпляров конструкций }

Main : PMain; {Указатель на первичное окружение}

{Реализация методов TMain }

constructor TMain.Init;

begin

Prev :=Nil; Next := Nil; CurEnv := Self;

Writeln ('Введите параметр m : '); Readln ( m );

Writeln ('Введите параметр n : '); Readln ( n )

end;

destructor TMain.Done; {Выдача результата MAIN на экран}

begin if Valid then Writeln ( 'Ackermann (', m , ',' , n , ') = ' , Res) end;

destructor TMain.AlarmDone;

begin

if Not mIsValid then Writeln ('Значение m =', m, ' – не допустимо');

if Not nIsValid then Writeln ('Значение n =', n, ' – не допустимо');

CurEnv := Nil

end;

procedure TMain.Open_A_in_MAIN;

begin Next := New (PA, Init (m , n )); CurEnv:= Next end;

procedure TMain.Close_A_in_MAIN;

begin Dispose ( PA ( Next ), Done_A_in_MAIN ) end;

function TMain.Valid : Boolean;

begin

mIsValid := m >= 0; nIsValid := n >= 0;

Valid := mIsValid and nIsValid

end;

{Реализация методов TA }

constructor TA.Init ( Valm, Valn : integer );

begin

m := Valm; n := Valn; Prev := CurEnv;

Next := Nil; CurEnv := Self

end;

destructor TA.Done_A_in_MAIN { Выход A в MAIN };

{Передает данные из конструкции A в надконструкцию MAIN.}

begin

PMain(Prev)^.Res := Res;

PProto( CurEnv)^.Next := Nil; CurEnv := Prev

end;

destructor TA.Done_A_in_A { Âûõîä èç A â A };

{Передает данные из конструкции A в надконструкцию A. }

begin

PA(Prev)^.Res := Res; PA ( CurEnv )^.Next:=Nil; CurEnv := Prev

end;

procedure TA.SetResult;

begin Res:=n+1 end;

procedure TA.Open1_A_in_A;

begin Next := New ( PA, Init ( m – 1, 1)) ; CurEnv:= Next end;

procedure TA.Open2_A_in_A;

begin Next := New ( PA, Init ( m , n–1)); CurEnv := Next end;

procedure TA.Open3_A_in_A;

begin Next := New ( PA, Init ( m – 1, Res)); CurEnv := Next end;

procedure TA.Close_A_in_A;

begin Dispose ( PA ( Next ), Done_A_in_A) end;

function TA.Condition1 : Boolean;

begin Condition1 := ( m = 0 ) and (n>=0) end;

function TA.Condition2 : Boolean;

begin Condition2 := ( n = 0 ) and (m>0) end;

function TA.Condition3 : Boolean;

begin Condition3 := ( m > 0 ) and (n>0) end;

IMPLEMENTATION

{Реализация резольверов}

function Condition1 : Boolean;

begin Condition1 := PA ( CurEnv )^.Condition1 end;

function Condition2 : Boolean;

begin Condition2 := PA ( CurEnv )^.Condition2 end;

function Condition3 : Boolean;

begin Condition3 := PA ( CurEnv )^.Condition3 end;

function Valid : Boolean;

begin Valid := PMain ( CurEnv )^.Valid end;

{Реализация терминал-действий}

procedure Start;

begin Main := New ( PMain, Init ) end;

procedure Finish;

begin Dispose ( Main, Done ) end;

procedure Alarm;

begin PMain ( CurEnv )^.AlarmDone end;

procedure Open_A_in_MAIN;

begin PMain ( CurEnv )^.Open_A_in_MAIN end;

procedure Close_A_in_MAIN;

begin PMain ( CurEnv )^.Close_A_in_MAIN end;

procedure Open1_A_in_A;

begin PA ( CurEnv )^.Open1_A_in_A end;

procedure Open2_A_in_A;

begin PA ( CurEnv )^.Open2_A_in_A end;

procedure Open3_A_in_A;

begin PA ( CurEnv )^.Open3_A_in_A end;

procedure Close_A_in_MAIN;

begin PA ( CurEnv )^.Close_A_in_A end;

Управляющая граф-схема Ackermann. Представление управляющей

грамматики Ackermann в форме управляющей граф-схемы состоит из двух

компонент — по одной на каждое правило грамматики (MAIN — заглавная, A

— вспомогательная рекурсивная):

0 begin MAIN

1 T ‘Start’

−<

3 FR Valid

4 T ‘Open_A_in_MAIN’

5 N A

6 T ‘Close_A_in_MAIN’

→

8 T ‘Alarm’

9 T ‘Finish’

10 end MAIN

11 begin A

−<

13 FR Condition1

14 T ‘SetResult’

Заметим, что компонента A трижды ссылается сама на себя, но недопустимая

левосторонняя рекурсия не имеет места.

Управляющая таблица Ackermann. Управляющая таблица соответствую-

щего порождающего процессора состоит из таблицы управляющих элементов

(табл.2.3) и таблицы возвратных состояний (табл.2.4), относящейся к подавляе-

мым состояниям 6, 13 и 17.

Таблица 2.3

Условие Действие

Магазин Состояние

1 2 3 4

Состояние 1 = {0}

Start 2

Состояние 2 = {1}

Default Alarm 3

Valid Open_A_in_Main 4

Состояние 3 = {8}

Finish 5

Состояние 4={4}

Condition1 SetResult 1 6

Condition2 Open1_A_in_A 1 7

Condition3 Open2_A_in_A 1 8

→

−<

17 FR Condition2

18 T ‘Open1_A_in_A’

19 N A

20 T ‘Close_A_in_A’

→

22 FR Condition3

23 T ‘Open2_A_in_A’

24 N A

25 T ‘Close_A_in_A’

26 T ‘Open3_A_in_A’

27 N A

28 T ‘Close_A_in_A’

29 end A

Продолжение табл. 2.3

1 2 3 4

Состояние 5={9} (конечное)

Stop

Состояние 6 = {14}

Sup

Состояние 7 = {18}

Condition1 SetResult 2 6

Condition2 Open1_A_in_A 2 7

Condition3 Open2_A_in_A 2 8

Состояние 8 = {23}

Condition1 SetResult 3 6

Condition2 Open1_A_in_A 3 7

Condition3 Open2_A_in_A 3 8

Состояние 9 = {5}

Close_A_in_Main 12

Состояние 10 = {19}

Close_A_in_A 13

Состояние 11 = {24} (конечное)

Close_A_in_A 14

Состояние 12 = {6} (êîíå÷íîå)

Default

Stop

Состояние 13 = {20}

Sup

Состояние 14 = {25}

Open3_A_in_A 15

Состояние 15 = {26}

Condition1 SetResult 4 6

Condition2 Open1_A_in_A 4 7

Condition3 Open2_A_in_A 4 8

Состояние 16 = {27}

Close_A_in_A 17

Состояние 17 = {28}

Sup

Таблица 2.4

Магазинный

символ

Возвратное

состояние

1 9

2 10

3 11

4 16

Замечание 1. В табл. 2.3 отсутствует графа Семантика, которая имелась бы

в том случае, если бы в грамматике использовались семантические символы.

Интерпретация заданных в ней семантик должна выполняться перед

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

Замечание 2. Таблица возвратных состояний в этом частном случае имеет

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

имелся бы вход Условие. Последний действительно использовался бы, если бы

таблица управляющих элементов (табл.2.3) для какого-либо из подавляемых

состояний (6, 13 или 17) выдавала значение Sup в графе Состояние в зависимо-

сти от условия. Однако это не так.

2.2. ОБЪЕКТНО-СИНТАКСИЧЕСКАЯ

АРХИТЕКТУРА ПРОГРАММ

Как показывают предложенные вниманию читателя примеры, программы,

написанные в стиле объектно-синтаксического программирования, имеют

своеобразную архитектуру. Тип ее может быть выражен следующей метафори-

ческой формулой:

Программа = Объекты + Грамматика.

Это означает, что программа есть коллекция объектов, организованных для

конкретного применения посредством некоторой трансляционной RBNF-

грамматики. Объекты поставляют данные и методы их обработки, а управляю-

щая грамматика определяет возможные последовательности вызовов этих ме-

тодов. Грамматика порождает некоторый класс вычислений как множество це-

почек терминал-действий и семантик, реализуемых посредством методов. Кон-

кретное вычисление выбирается из этого множества цепочек в зависимости от

текущего состояния операционного окружения (пространства данных).

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

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

ле, реализация такой программы представляется фиксированной процедурой,

работающей под управлением таблицы, которая воплощает в себе ту структуру

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

вами, эта процедура эмулирует некоторый абстрактный вычислитель, а управ-

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

процедуру с различными таблицами в качестве ее параметров, мы настраиваем

ее на определенный класс вычислений.

Синтаксический подход поддерживает новую своеобразную парадигму прог-

раммирования. В соответствие с ней, когда вы пишете правило грамматики, то

определяете некоторую программную конструкцию. При этом считается, что

любая конструкция продолжает вычислительный процесс, уже выполненный

составляющими ее подконструкциями, и данной конструкции требуется лишь

надлежащим образом использовать результаты ее подконструкций для выра-

ботки своего собственного результата. Поэтому при написании правила грам-

матики, описывающего некоторую конструкцию, достаточно определить, какие

действия над результатами ее подконструкций должна совершить данная кон-

струкция. Благодаря такой концептуальной модульности, воплощаемой в пра-

вилах грамматики, при которой проектирование процесса обработки данных

естественно структурируется иерархическим образом, разработка программы

значительно облегчается.

Синтаксический подход открывает возможность диагностировать ошибоч-

ные ситуации

, возникающие во время вычислений, в терминах той предмет-

ной области, к которой относится задача. Для этого достаточно в качестве

нетерминалов или вспомогательных понятий грамматики, а также резольвер-

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

2.3. ИНФОРМАЦИОННОЕ ВЗАИМОДЕЙСТВИЕ

МЕЖДУ КОНСТРУКЦИЯМИ

При использовании грамматик для описания управляющей структуры про-

грамм полезно пронаблюдать аналогию между нетерминалами грамматики и

замкнутыми подпрограммами, а также между вспомогательными понятиями и

открытыми подпрограммами в обычном программировании.

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

тики. Это правило (совместно с другими) порождает множество всевозможных

конкретных реализаций соответствующей программной конструкции. В общем

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

ваемых ее подконструкциями, которые в правиле, определяющем эту конст-

рукцию, представляются как нетерминалы или вспомогательные понятия пра-

вой части данного правила. При этом возможны, и зачастую желательны, ре-

курсивные определения.

Грамматика определяет только возможные потоки управления в программе.

Но операторы, входящие в этот поток и по большей части представленные (в

конечном итоге) вызовами методов объектов, воплощают какие-то действия

над данными, которые представляются, главным образом, полями объектов.

Таким образом, с каждым нетерминалом (программной конструкцией) ассо-

циируется некоторый тип объекта. Его поля представляют локальные данные

конструкции, а методы реализуют возможные манипуляции над этими даны-

ми.

Обнаруживаемые автоматически ошибки в этом случае все являются контекстными.