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

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

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

условий, задаваемых резольверами. При этом предполагается, что резольверы

вычисляются синхронно с семантическими преобразованиями с учетом порядка

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

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

ные с резольверными символами, предшествующими терми-налу a

в порядке

следования резольверных символов. Если все они выполняяются, то испол-

няются преобразования операционной среды, ассоциированные с семантиче-

скими символами, предшествующими терминалу a

(также в тек-стуальном

порядке). Затем аналогичным порядком выполняются резольверы и семантики,

предшествующие терминалу a

, и т.д. Процесс заканчивается, когда успешно

завершается вычисление конъюнкции предикатов, следующих за символом a

, и

исполнение соответствующих семантик.

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

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

циированные с их резольверными символами. "Смысл" входного предложения x

представляется семантической цепочкой σ

...σ

Если некоторому входному предложению соответствует несколько управ-

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

ложение называется семантически неоднозначным. В SYNTAX-технологии

семантическая неоднозначность не допускается

. Однако использование ре-

зольверов во многих случаях помогает избегать этой опасности.

Приведем два примера трансляционных грамматик, одна из которых трак-

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

люстрирует спецификацию интерпретатора арифметических выражений (каль-

кулятора), а второй — вычисление функции факториал. Эти примеры обсуж-

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

личных аспектов использования SYNTAX-технологии. Как и во всех других

примерах в этой книге, управляющие грамматики записываются на языке TSL

, а

операционная среда представлена на языке программирования Borland Pascal 7.0.

1.3. АНАЛИЗИРУЮЩАЯ ТРАНСЛЯЦИОННАЯ

ГРАММАТИКА КАЛЬКУЛЯТОРА

Синтаксически управляемый калькулятор (спецификация которого дается в

этом разделе) вычисляет арифметические выражения, операндами которых яв-

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

каль. Допустимы арифметические операции: сложение, вычитание, умножение,

деление, а также унарные плюс и минус. Унарные операции можно использо-

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

употребимы.

Построение спецификации калькулятора обсуждается в гл. 5.

Фактически семантическая неоднозначность контролируется при построении управляющих

таблиц процессоров.

Описание языка TSL дано в гл. 8.

CALC — трансляционная грамматика калькулятора

MICROLEXICS

Lexical classes: d, '.', 'e', '+', '–', '*', '/', '(', ')', EOF, Escaped Symbols.

d: '0'..'9'.

Escaped Symbols: #32, #13, #10.

EOF: ''.

SYNTAX

Nonterminals: PROGRAM (ПРОГРАММА), EXPRESSION (ВЫРАЖЕНИЕ).

Terminals: 'd', '.', 'e', '+', '–', '*', '/', '(', ')', 'EOF'.

Auxiliary notions:

NUMBER (ЧИСЛО),

INTEGER NUMBER (ЦЕЛОЕ),

FRACTIONAL PART (ДРОБНАЯ_ЧАСТЬ),

EXPONENT PART (ПОРЯДОК),

DIGIT (ЦИФРА),

MONADIC OPERATION (УНАРНАЯ_ОПЕРАЦИЯ),

DYADIC OPERATION (БИНАРНАЯ_ОПЕРАЦИЯ),

OPERAND (ОПЕРАНД).

Forward pass semantics :

Reset,

Complete,

Push Mon{adic} Op{eration},

Push Dyadic Op{eration},

Push Op{eran}d,

Push Open Par{enthisis},

Unload And Discard Open Par{enthisis},

Init Int{eger Number},

App{end} Dig{it},

Set Int{eger} Part,

App{end} Exp{onent} Part,

Set Fr{actional} Part,

App{end} Fr{actional} Part,

Set Exp{onent},

Set Dig{it},

Set Sign.

PROGRAM: Reset, EXPRESSION, Complete, 'EOF'.

EXPRESSION: ((MONADIC OPERATION)*, OPERAND) # DYADIC OPERATION.

OPERAND: NUMBER, Push Op{eran}d;

Push Open Par{enthisis},'(', EXPRESSION, Unload And Discard Open

Par{enthisis}, ')'.

NUMBER: INTEGER NUMBER, Set Int{eger} Part,

[ FRACTIONAL PART, App{end} Fr{actional} Part ],

[ EXPONENT PART, App{end} Exp{onent} Part ].

INTEGER NUMBER: Init Int{eger Number}, (Set Dig{it}, DIGIT, App{end} Dig{it})+.

FRACTIONAL PART: '.', INTEGER NUMBER, Set Fr{actional} Part.

EXPONENT PART: 'e', Set Sign, (['+']; '–'), INTEGER NUMBER, Set Exp{onent}.

DIGIT: 'd'.

MONADIC OPERATION: Push Mon{adic} Op{eration}, ('+' ; '–').

DYADIC OPERATION: Push Dyadic Op{eration}, ('+' ; '–' ; '

' ; '/').

ENVIRONMENT

const Size = 100 {Размер магазина операндов и операций};

type

TOperation = (MonadicPlus, MonadicMinus, Plus, Minus, Mult, Division, OpenPar );

TPrio = 0 .. 3;

TOperationStackItem = record

Operation : Toperation;

Priority : Tprio

end;

TOperandStack = array [1 .. Size] of real {Магазин операндов};

TOperationStack = array [1 .. Size] of TOperationStackItem { Магазин операций };

var OperandStack : TOperandStack;

OperationStack : TOperationStack;

OperandStackTop, OperationStackTop : 0 .. Size;

Number, FractionalPart : real;

IntegerNumber, DigitsNmb, Exponent, Digit, Sign : integer;

{Вспомогательные процедуры и функции}

function CurrentSymbol: char;

var s : string;

begin s:=LR; CurrentSymbol := s[1] {Литерное представление лексемы} end;

function Power (A, B: integer):real {Вычисляет A

, где A≠0, а B ≥0};

var c : real; i : integer;

begin c:=1; for i:=1 to B do c:=c

A; Power:=c end ;

procedure Unload(Prio:TPrio) {Разгрузка и выполнение операций из магазина

операций};

function Unloading:Boolean{Дает true, если разгрузка магазина операций

возможна};

begin {Unloading} with OperationStack[OperationStackTop] do

Unloading := (OperationStackTop >0)and (Operation <>OpenPar) and

(Prio<=Priority)

end {Unloading};

begin {Unload}

while Unloading do

with OperationStack[OperationStackTop] do

begin

case Operation of

MonadicPlus:{Skip};

MonadicMinus: OperandStack[OperandStackTop] :=

–OperandStack [OperandStackTop]

else

begin

case Operation of

Mult :OperandStack[OperandStackTop–1]:=

OperandStack[OperandStackTop–1]

OperandStack[OperandStackTop];

Division:OperandStack[OperandStackTop–1] :=

OperandStack[OperandStackTop–1] /

OperandStack[OperandStackTop];

Plus: OperandStack[OperandStackTop−1] :=

OperandStack[OperandStackTop−1]+

OperandStack[OperandStackTop];

Minus: OperandStack[OperandStackTop−1]:=

OperandStack[OperandStackTop−1]−

OperandStack[OperandStackTop]

end {case};

Dec(OperandStackTop)

end {else-ветви}

end {внешнего case};

Dec (OperationStackTop)

end {with}

end {Unload};

IMPLEMENTATION

{ Реализация сематик }

procedure Reset {Инициализирует вычисление входного выражения};

begin

NewLine;

OperationStackTop := 0 {Опустошает магазин операций};

OperandStackTop := 0 {Опустошает магазин операндов}

end;

procedure Complete {Завершает разгрузку магазина операций и вычисление входного

выражения};

begin

Unload(0) {Разгружает магазин операций, завершая вычисление выражения};

PrintReal(OperandStack[OperandStackTop]) {Печать результата};

Dec(OperandStackTop){Сброс результата с вершины магазина операндов}

end;

procedure UnloadAndDiscardOpenPar {Разгрузка магазина операций до скобки и ее

сброс};

begin Unload(0); Dec(OperationStackTop) end;

procedure PushDyadicOp {Обработка бинарной операции};

var Prio : TPrio; CS : char;

begin

CS := CurrentSymbol;

case CS of

'+', '−' : Prio := 1;

', '/' : Prio := 2

end;

Unload(Prio) {Разгружает и выполняет операции приоритета Prio и выше};

Inc(OperationStackTop);

with OperationStack[OperationStackTop] do

begin

case CS of

'+' : Operation := Plus;

'−' : Operation := Minus;

'*' : Operation := Mult;

'/' : Operation := Division;

end ; Priority := Prio

end

end ;

procedure PushMonOp {Помещает унарную операцию в магазин операций};

begin Inc(OperationStackTop);

with OperationStack[OperationStackTop] do

begin

case CurrentSymbol of

'+' : Operation := MonadicPlus;

'−' : Operation := MonadicMinus

end; Priority := 3

end

end;

procedure PushOpd {Помещает значения операндов в магазин операндов};

begin

Inc(OperandStackTop);

OperandStack[OperandStackTop] := Number

end;

procedure PushOpenPar {Помещает '(' в магазин операций};

begin Inc(OperationStackTop);

with OperationStack[OperationStackTop] do

begin Operation := OpenPar; Priority := 0 end

end;

procedure InitInt {Инициализация целого};

begin IntegerNumber := 0; DigitsNmb := 0 end ;

procedure SetDig {Преобразует литеру цифры в соответствующее целое};

begin Digit := LN −1 end ;

procedure AppDig {Включение очередной цифры в целое};

begin IntegerNumber := IntegerNumber

10 + Digit; Inc(DigitsNmb) end;

procedure SetIntPart {Инициализация целой части};

begin Number := IntegerNumber end ;

procedure SetFrPart {Установка дробной части};

var i : integer;

begin FractionalPart := IntegerNumber;

for i := 1 to DigitsNmb do FractionalPart := FractionalPart

0.1

end ;

procedure AppFrPart {Добавление дробной части к числу};

begin Number := Number + FractionalPart end ;

procedure SetSign {Установка знака порядка};

begin if CurrentSymbol = '−' then Sign := −1 else Sign := +1 end ;

procedure SetExp {Учет знака порядка};

begin Exponent := IntegerNumber

Sign end ;

procedure AppExpPart {Учет порядка};

begin

if Exponent >= 0 then Number := Number

Power(10, Exponent)

else Number := Number / Power(10, −Exponent)

end ;

1.4. ПОРОЖДАЮЩАЯ ТРАНСЛЯЦИОННАЯ ГРАММАТИКА,

ОПЕДЕЛЯЮЩАЯ ВЫЧИСЛЕНИЕ ФУНКЦИИ FACTORIAL

В этом разделе дается пример спецификации посредством трансляционной

грамматики одного вычислительного алгоритма — алгоритма вычисления

функции Factorial.

Управление процессом вычисления этой функции определяется двумя пра-

вилами грамматики. Правило для начального нетерминала S описывает внеш-

ний контур управления, а правило для вспомогательного понятия F — внут-

ренний. Исполнение конструкции S состоит из инициализации вычисления

(Start) и, в зависимости от результата тестирования параметра (Valid), выпол-

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

завершения вычислений (Finish) — когда предикат Valid выполняется, либо

выдачи аварийного сообщения (Alarm) — когда этот предикат не выполняется.

Терминал Start подразумевает создание экземпляра объекта типа TFactorial,

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

чение параметра n и полагающим для начала поле Fac равным 1. Резольвер Valid

тестирует параметр n, выдавая значение true, если он не отрицателен, и

значение false − в противном случае. Терминал Finish уничтожает экземпляр

объекта, предварительно выдавая полученный результат на экран. Терминал

Alarm также уничтожает объект, но при этом сообщает о недопустимости ис-

ходного значения параметра.

Конструкция F в свою очередь циклически выполняет шаг вычислений

(Step), пока текущее значение параметра n велико (предикат Large выполняет-

ся). Метод Step домножает текущее значение результата Fac на текущее значе-

ние параметра n и уменьшает его на единицу. Резольвер Large выдает значение

true, если текущее значение параметра больше единицы, и значение false — в

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

Предполагается, что порождающий процессор, построенный по трансляци-

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

Его управляющая таблица играет роль таблицы решений, которая в зависимо-

сти от сочетания различных условий относительно текущего значения пара-

метра n диктует последовательность действий, ассоциированных с терминалами

грамматики.

Factor — трансляционная грамматика функции n!

(итеративный вариант)

Nonterminals: S.

Terminals: 'Start', 'Finish', 'Alarm', 'Step'.

Auxiliary notions: F. {Выражение для F подставляется использующего вхождения F в

правило для S — открытой функции (макроподстановки)}

Forward pass resolvers: Valid, Large, Small.

{Правила, определяющие структуру управления алгоритма вычисления n!}

S : 'Start', (Valid, (F, 'Finish'); 'Alarm').

F : (Large, 'Step')*, Small.

ENVIRONMENT

type PFactorial = ^TFactorial;

TFactorial = object

n {Параметр}, Fac {Результат}:integer;

constructor Init;

destructor FinishDone;

destructor AlarmDone;

function Valid : Boolean;

function Large : Boolean;

function Small : Boolean;

procedure Step;

end;

var Factorial : PFactorial; {Экземпляр объекта — создается действием Start}

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

constructor TFactorial.Init;

begin ReadLn(n); Fac := 1 end;

destructor TFactorial.FinishDone;

begin WriteLn(n, '! = ', Fac) end;

destructor TFactorial.AlarmDone;

begin WriteLn(n, ' — недопустимое значение параметра!') end;

function TFactorial.Valid : Boolean;

begin Valid := n >= 0 end;

function TFactorial.Large : Boolean;

begin Large := n > 1 end;

function TFactorial.Small : Boolean;

begin Small := Not Large end;

procedure TFactorial.Step;

begin Fac := Fac

n; Dec(n) end;

IMPLEMENTATION

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

procedure Start; begin Factorial := New(PFactorial, Init) end;

procedure Alarm; begin Dispose(Factorial, AlarmDone) end;

procedure Step; begin Factorial^.Step end;

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

function Valid: Boolean; begin Valid := Factorial^.Valid end;

function Large: Boolean; begin Large := Factorial^.Large end;

function Small: Boolean; begin Small := Factorial^.Small end;

Замечание. Может показаться, что резольвер Small в правиле для конст-

рукции F не нужен. Если его убрать, то это приведет к появлению зависимости

между резольверными цепочками Valid и Valid&Large

. C другой стороны, не-

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

тельно выполняется. Поскольку символ F обозначает вспомогательное (т.е.

раскрываемое) понятие, то ясно, что в этом примере мы имеем дело с

явнорегулярной трансляцией, и процессор, ее реализующий, является конечным.

1.5. АНАЛИЗИРУЮЩИЙ ПРОЦЕССОР

Процессор, реализующий трансляцию, подобно трансляционной граммати-

ке, состоит из управляющего процессора, который строится по управляющей

грамматике, и операционной среды, компилируемой по ее описанию. В разд. 1.1

неформально был описан анализирующий процессор. Здесь мы определим этот

процессор и трансляцию, им реализуемую, в точных терминах.

Анализирующим процессором назовем формальную систему P =(P

, E), со-

стоящую из управляющего анализирующего процессора (P

) и операционной

среды (E).

Управляющим анализирующим процессором назовем формальную систему P

=(Q,Σ, Γ, ∆, ℜ, δ, q

, F), включающую конечное множество состояний (Q),

входной алфавит (Σ), алфавит магазинных символов (Γ), алфавит семанти-

ческих символов (∆), алфавит резольверных символов (ℜ); управляющую таб-

лицу δ = (δ

, δ

), которая состоит из трех подтаблиц:

• таблицы резольверов δ

: Q × (Σ ∪ {ε}) → 2

ℜ

∗

• таблицы управляющих элементов δ

: Q × (Σ ∪ {ε}) × ℜ

∗

→ (Q ∪ {Sup}) × Γ

∗

× ∆

∗

• таблицы возвратных состояний δ

: Q × Γ × ℜ

∗

→ Q;

∈Q — начальное состояние, F⊆Q — множество конечных состояний.

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

вспомогательного понятия F в правую часть правила для конструкции S.

Работу процессора, как принято в теории автоматов, опишем в терминах

конфигураций.

Под конфигурацией процессора будем подразумевать совокупность

(q, x, α, e), где q∈Q — текущее состояние внутреннего управления процессо-

ра, x∈Σ

∗

— непрочитанная часть входной цепочки, α∈Γ

∗

— содержимое мага-

зина, e∈E — текущее состояние операционной среды.

Начальная конфигурация — это такая, в которой q =q

(текущее состояние

управления равно начальному), x — вся входная цепочка, α = ε (магазин пуст),

e = e

(текущее состояние операционной среды равно начальному).

Конечная конфигурация — это такая, в которой q∈F (текущее состояние

управления — конечное), x = ε (прочитана вся входная цепочка), α = ε (магазин

пуст).

На множестве конфигураций введем отношение непосредственного следо-

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

, ax, Xα, e

) — текущая конфигурация. Здесь q

∈Q — текущее состояние

управления, a∈Σ ∪{ε} — текущий входной символ (первый символ непрочи-

танной части входной цепочки), x∈Σ

∗

— остаток входной цепочки, X ∈Γ —

текущий верхний символ магазина, α∈Γ

∗

— остаток магазинной цепочки,

∈E — текущее состояние операционной среды.

Прежде всего определим интерпретацию резольверных и семантических

цепочек. Пусть e — некоторое состояние операционной среды, ρ∈ℜ

∗

— неко-

торая резольверная цепочка, а σ∈∆

∗

— некоторая семантическая цепочка. По-

ложим по определению

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

истинный предикат, а пустая семантическая цепочка — как пустой оператор, т.е.

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

В текущей конфигурации в зависимости от того, что дает управляющая таб-

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

ситуаций

В частности, допустимо неопределенное значение e

Которые идентифицируются управляющим процессором в порядке их перечисления.

(e) =

ρ1

(e)&ι

ρ2

(e)...&

ρn

(e), если ρ = ρ

...ρ

, ρ

∈ℜ, (i = 1, 2, ..., n),

если

(e) =

(...ι

(ι

(e)) ...), если

...

∈

∆

, (j = 1, 2, ..., m), m > 0,

если

т.е. m =0.

Случай 1 — входной символ допустим: δ

, a) ≠∅. Текущий входной

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

ная цепочка из множества δ

,a) дает true. В противном случае он может быть

принят в одном из возвратных состояний

или признан как ошибочный (в

текущем контексте). Это выясняется в ходе дальнейшего анализа ситуации.

Случай 1.1 — входной символ принимается в текущем состоянии: ∃ един-

ственная резольверная цепочка ρ∈δ

, a):(ι

)). Дальнейшее движение оп-

ределяется управляющим элементом δ

, a, ρ). Пусть δ

, a, ρ)=(q

, γ, σ), где

∈Q — переходное состояние, γ∈Γ

∗

— магазинная цепочка, σ∈∆

∗

— се-

мантическая цепочка. Процессор записывает магазинную цепочку γ над верх-

ним символом магазина, выполняет преобразования текущего состояния опе-

рационной среды e

, ассоциированные с семантическими символами, состав-

ляющими семантическую цепочку σ, что дает новое ее состояние e

= ι

), и

переходит в состояние q

. В терминах конфигураций имеем (q

, ax, Xα, e

)

,x,γXα, e

). После этого новая конфигурация анализируется сначала.

Случай 1.2 — контекстная неоднозначность: ∃ ρ,ρ'∈δ

,a) : (ρ ≠ ρ' &

& ρ ≠ ε & ρ' ≠ ε & ι

) & ι

ρ'

)). Проще говоря, в этом случае в множестве

, a) существует несколько разных непустых резольверных цепочек, интер-

претация которых дает истину. Процессор диагностирует контекстную неодно-

значность.

Случай 2 — входной символ не принимается в текущем состоянии:¬∃ρ∈

, a) : (ι



)). В этом случае либо δ

, a)=∅, либо ни одна резольверная

цепочка из множества δ

, a) не дает истины. Дальнейший анализ ситуации

покажет, возможно ли ε-движение или текущий входной символ ошибочен.

Случай 2.1 — ошибка: δ

, ε)=∅. В этом случае ε-движение невозможно.

Если значение δ

,a) ≠∅, то входной символ не принимается в текущем

контексте, и процессор диагностирует контекстную ошибку; если δ

,a)=∅,

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

рует бесконтекстную ошибку.

Случай 2.2 — имеется некоторый контекстный выбор ε-движений: δ

, ε)≠∅.

Случай 2.2.1— контекстная ошибка: ¬∃ρ∈δ

,ε) : (ι

)).

Ни одно из контекстных условий, допускающих ε-движение в текущем состоя-

нии операционной среды, не выполняется. Процессор диагностирует контекст-

ную ошибку.

Случай 2.2.2 — контекстная неоднозначность: ∃ρ,ρ'∈δ

, ε): (ρ ≠ ρ' &

& ρ ≠ ε & ρ' ≠ ε & ι

) & ι

)). Проще говоря, в множестве

,ε) существуют несколько разных непустых резольверных цепочек, интер-

претация которых дает true. Процессор диагностирует в этом случае контекст-

ную неоднозначность выбора ε-движения.

См. разд. 2.2.