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

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

Заметим, что управляющая таблица обратного просмотра состоит только из

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

возвратных состояний не используется. Это связано с тем, что в случае ε-

движения возвратное состояние снимается непосредственно с вершины мага-

зина. Особенностью обратного просмотра является и то, что в магазин помеща-

ется не более одного магазинного символа одновременно. Впрочем, все это

подробно рассматривается в разд.3.3.

Операционная среда. Понятие операционной среды, включающей интер-

претацию контекстных (т.е. резольверных и семантических резольверных)

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

зуемое в сплайновых процессорах, описанных в разд.1.3, можно естественным

образом обобщить для двухпросмотрового механизма трансляции. Для этого

достаточно принять во внимание, что ℜ = ℜ

∪ ℜ

, ℜ

∩ ℜ

= ∅, ∆ = ∆

∪ ∆

∆

∩ ∆

= ∅

и что контекстные символы из ℜ

∆

интерпретируются на пря-

мом просмотре, а резольверы и семантики из ℜ

и ∆

— на обратном.

Это

обобщение можно применять для трансляций, специфицируемых трансляци-

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

посредством челночных сплайновых процессоров.

3.3. ФУНКЦИОНИРОВАНИЕ

ЧЕЛНОЧНОГО СПЛАЙНОВОГО ПРОЦЕССОРА

Работу челночного сплайнового процессора опишем в терминах его конфи-

гураций.

Прямой просмотр. Как уже упоминалось, обработку начинает процессор

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

стояние операционной среды. Свою работу он начинает с начальной конфигу-

рации (q

,x,ε, e

), где q

∈Q

— начальное состояние его управления; x ∈Σ

—

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

— начальное

состояние операционной среды.

Пусть (q

,ax,α, e

) — текущая конфигурация прямого просмотра, в которой

∈Q

— текущее состояние его управления; ax∈Σ

— необработанная часть

входной цепочки, где a ∈Σ

— текущий входной символ, x∈Σ

— остаток

входной цепочки; α∈Γ

— текущая магазинная цепочка, причем считается,

что на вершине магазина находится крайний левый символ цепочки α;

—

текущее состояние операционной среды. Очередное движение определяется

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

если в этом описании положить Q = Q

, Σ = Σ

, Γ = Γ

, ∆ = ∆

, ℜ = ℜ

, δ = δ

(соответственно δ

= δ

, δ

= δ

, δ

= δ

), q

= q

, F = F

Прямой просмотр заканчивает свою работу тогда, когда он достигает одно-

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

В трансляционных грамматиках для обозначения семантических символов вместо

символа ∆ используется символ Σ, причем предполагается, что Σ = Σ

∪ Σ

и Σ

∩ Σ

= ∅.

Вся последовательность движений прямого просмотра может быть пред-

ставлена следующим образом:

, x, ε, e

) (p

, ε, ε, e

здесь p

∈F

. Достигнутое состояние операционной среды e

является началь-

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

состояний управления прямого просмотра регистрируется на его выходе.

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

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

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

ет вид (q

, p

... q

,ε, e

Пусть (q

, q

k–1

… q

,α, e

) — текущая конфигурация обратного про-

смотра. Очередное движение обратного просмотра определяется его управ-

ляющей таблицей в зависимости от ситуации.

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

, q

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

"символ" q

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

только одной резольверной цепочки из множества δ

, q

) дает true. В слу-

чае, если ни одна из них не дает true, входной символ может быть принят в од-

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

или признан как ошибочный в текущем контек-

сте

. Если несколько резольверных цепочек дает true, то ситуация контекстно

неоднозначна

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

численном ниже порядке.

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

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

, q

) : ι

). Движение определяется

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

, q

, r). Пусть δ

, q

, r)=(q

,γ,σ), где q

∈Q

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

∪ {ε}) — магазинная цепочка

, σ ∈ ∆

— се-

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

ним символом магазина

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

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

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

ки σ, что дает новое ее состояние: e

=ι

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

. Те-

кущим входным символом становится следующий символ на входе. В терми-

нах конфигураций имеем:

, q

k–1

... q

,α, e

) (q

, q

k–1

... q

, γα, e

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

См. случай 2.2.3.

См. случай 2.

См. случай 1.2.

Одно-символьная или пустая.

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

записывается над верхним символом магазина.

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

, q

) :

(r ≠ r' & r ≠ ε & r' ≠ ε & ι

) & ι

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

стве δ

, q

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

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

текстную неоднозначность.

Случай 2 — входной символ не принимается в текущем состоянии. Здесь

либо δ

)=∅, либо ни одна резольверная цепочка из множества δ

( q

, q

)

не дает true. Дальнейший анализ ситуации покажет, возможно ли ε-движение

или текущий входной символ ошибочен.

Случай 2.1 — контекстная ошибка: δ

,ε)=∅. Здесь ε-движение невоз-

можно. Текущий входной символ не принимается. Обратный просмотр диагно-

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

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

, ε)≠∅.

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

, ε):(ι

)). Ни одно из

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

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

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

Случай 2.2.2 — контекстная неоднозначность ε-движения:

∃ r, r '∈δ

, ε): (r ≠ r' & r ≠ε & r' ≠ ε & ι

) & ι

)). Проще говоря, в мно-

жестве δ

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

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

истину. Обратный просмотр диагностирует контекстную неоднозначность вы-

бора ε-движения.

Случай 2.2.3 — однозначный выбор ε-движения:

∃ единственная r ∈δ

, ε): (ι

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

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

,ε,r).

Пусть δ

( q

,ε,r)=(Pop

,γ,σ), где γ∈(Γ

∪{ε}), σ∈∆

. В этом случае об-

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

, q

k–1

... q

,α, e

) (q

, q

k–1

... q

, γα, e

Здесь e

=ι

Пусть магазинная цепочка, образовавшаяся после записи γ над верхним

символом магазина, есть γα = Xβ. Тогда имеем

, q

k–1

... q

, γα, e

)=(q

, q

k–1

... q

, Xβ, e

Далее процессор совершает еще один шаг перехода, а именно:

, q

k–1

... q

, Xβ, e

)

, q

k–1

... q

,β, e

Для ε-движения вместо переходного состояния всегда дается специальное значение Pop:

следующее (возвратное) состояние следует брать с вершины магазина.

Здесь q

= X. Это последнее движение затрачивает верхний символ магазина,

но текущий входной символ все еще остается не принятым. Новое состояние q

называется возвратным, а исходное q

— подавляемым. Далее анализ новой

конфигурации начинается по той же схеме при том же текущем входном сим-

воле.

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

конфигурация, характеризуемая тем, что достигнуто одно из конечных состоя-

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

стояний прямого просмотра и магазин пуст. В противном случае считается, что

цепочка на входе челночного процессора ошибочна. Вся последовательность

движений обратного просмотра может быть представлена следующим образом:

, p

... q

, ε, e

)

, ε, ε, e

Здесь p

∈F

— конечное состояние обратного просмотра, прочитана вся по-

следовательность состояний прямого просмотра и магазин пуст.

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

цессора, считается состояние "интересной" части операционной среды, т. е.

]

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

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

во пар:

τ(P

)={(x, [e

]

)|( q

x , ε, e

)

ε , ε, e

), p

∈F

... q

, ε, e

) (p

ε , ε, e

), p

∈F

Замечание 1. Напомним, что результат интерпретации пустой резольверной

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

или обратного просмотра для любого входа, включая и ε-вход, дает множество

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

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

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

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

множества.

Замечание 2. Очевидно, что явнорегулярная челночная трансляция реалии-

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

— конечные.

3.4. ПОСТРОЕНИЕ

ЧЕЛНОЧНЫХ СПЛАЙНОВЫХ ПРОЦЕССОРОВ

Пусть задана трансляционная граф-схема G = (G

, E ), которая, как мы зна-

ем, состоит из управляющей граф-схемы (G

) и описания операционной среды

(E ). Пусть G

=(N, T, ℜ, Σ, Κ, S), где N — алфавит нетерминалов; T — алфавит

терминалов; ℜ = ℜ

∪ ℜ

(ℜ

∩ ℜ

= ∅) — алфавит резольверных символов,

состоящий из резольверов прямого (ℜ

) и обратного (ℜ

) просмот-

ров; Σ = Σ

∪Σ

(Σ

∩ Σ

= ∅) — алфавит семантических символов, состоящий

из семантик прямого (Σ

) и обратного (Σ

) просмотров; Κ — множество ком-

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

нетерминал; S — начальный нетерминал.

Опишем метод построения челночного сплайнового процессора P

= ( P

, E), где P

, P

— управляющие процессоры соответственно прямого и об-

ратного просмотров; E — операционная среда. Поскольку операционная среда

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

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

и обратного просмотров. Далее следует запись алгоритма построения управ-

ляющего процессора на алголоподобном

языке с комментариями, которые в

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

комментариев, заключаемых в специальные ограничители (#), ничем не выде-

ляются.

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

Вход: G

= (N, T, ℜ, ∆ , Κ, S) — управляющая граф-схема

Выход:

=(Q

, Σ

, Γ

, ∆

, ℜ

, δ

, F

) — управляющий процессор прямого

просмотра

Метод:

# Инициализация #

:=T; # T — алфавит терминалов управляющей граф-схемы G

∆

— такой же как в управляющей граф-схеме

;

:={v

| v

∈Vertex(G

):(Mark(v

)="begin-S")};

:={

}; Γ

:=∅; ℜ

:=∅; F

:=∅; # Эти четыре множества в дальнейшем

пополняются #

Continue:=true;

# Главный цикл построения управляющего процессора прямого

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

, и затем

цикла пополнения таблицы

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

флажок Continue не перейдет в состояние false. Это происходит тогда, когда в

результате очередного выполнения этапа пополнения таблицы

не появляет-

ся ни одного нового возвратного состояния. И тогда производится проверка

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

проверки — обнаружение ситуаций, в которых не ясно, отнести ли текущий

входной символ к текущей или к объемлющей конструкции языка. Если такая

проверка не обнаруживает ни одной неясной ситуации, то гарантирована де-

терминированность процессора прямого просмотра относительно альтернати-

вы: использовать верхний символ магазина или нет. #

Имеется в виду, что используется по возможности синтаксис языка Алгол 68.

Напомним, что ∆ = ∆

∪ ∆

, ∆

∩ ∆

= ∅.

while Continue

do Continue:=false; Continue2:=false;

# Пополнение таблиц

На этом этапе производится разложение состояний, имеющихся в

множестве Q

. По разложению состояния проверяются необходимые

условия детерминированности процессора и планируются все его

возможные движения в данном состоянии. Появляющиеся при этом новые

состояния включаются в множество Q

, а новые магазинные символы —

в множество Γ

Этап пополнения таблиц

заканчивается, когда рассмотрены все

состояния из Q

. #

for ∀q :(q ∈ Q

)

do D :=Develope(q); # Разложение состояния q — лес, состоящий из

деревьев, корнями которых являются вершины

множества q. #

if Height(D)=∞

then Alarm(("Разложение состояния ", q, " бесконечно!"))

else # Построение непустых движений в состоянии q. #

for ∀a :(a ∈Σ

&∃v :(v ∈Leaves(D)&Mark(v)=a))

do # Отбор ветвей разложения D, листья которых помечены входным

символом a. #

:=Subforest(D, a);

if D

≠∅

then R :=∅; # Сброс резольверных входов для символа a. #

for

∀

r:(r ∈ℜ

&∃b:(b ∈Branches(D

)&Mark

ℜ

(b)=r))

do # Отбор ветвей из D

, метки которых, если в них учитывать только

резольверные символы прямого просмотра, образуют r. #

a,r

=Selected branches(D

, r);

if Не все ветви D

a,r

имеют равную длину

then Alarm(("Нарушена балансировка разложения " "состояния ", q,

" по входному " "символу ", a, " и составному "

"резольверу ", r, "!" ))

else # Обеспечена детерминированность уровня конструкции, к

которой относится текущий входной символ #

σ:=Forward pass semantics (D

a,r

);

Те из них, которые оказываются конечными, пополняют также множество F

Разумеется, эта запись условна. Бесконечные разложения появляются тогда и только

тогда, когда исходная управляющая грамматика леворекурсивна.

if Ambiguous(σ)

then Alarm(("Семантическая неоднозначность "

"состояния ", q, " по входному "

"символу ", a, " и составному "

"резольверу ", r, "!"))

else R :=R ∪{r}; # Пополнение резольверных входов для a #

p :=Leaves(D

a,r

); # p — переходное состояние из q по

входному символу a при условии, что

выполняется составной предикат r, т.е. если

ι(r). #

:=Q

∪{p};

α := Push down list(D

a,r

); # α — магазинная цепочка. Если она

содержит символы, которых еще нет в

алфавите Γ

, то Push down list

устанавливает флажок Continue2 в

состояние true. #

(q, a, r):=(p, α, σ);

od; # Конец цикла определения резольверных входов для a #

(q, a):=R

fi # Конец определения движения для входного символа a #

od; #Конецциклапостроениянепустыхдвиженийвсостоянии q #

# Построение ε−движений в состоянии q. #

# D

— те ветви разложения D, листья которых помечены символами вида

"end-A", где A — некоторый нетерминал. #

if D

≠ ∅

then # Пустые движения существуют

(q —подавляемое состояние). #

R :=∅; # Сброс резольверных входов для символа ε. #

for ∀r :( r ∈ℜ

&∃b:(b∈Branches(D

)&Mark

ℜ

(b)=r))

do # Отбор ветвей D

, метки которых, если в них учитывать только

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

f, r

:= Selected branches(D

f, r

);

if Не все ветви D

f, r

имеют равную длину

then Alarm(("Нарушена балансировка "

"разложения состояния ", q,

" по конечным меткам и "

"составному резольверу ", r, "!" ))

else σ:=Forward pass semantics (D

f,r

);

Subforest( , "end- ");

∈

∪

if Ambiguous(σ)

then Alarm(("Семантическая неоднозначность "

"состояния ", q, "по конечным вершинам и "

"составному резольверу ", r, "!" ))

else

if Mask(q, r) = {S}

then # q — конечное состояние #

:=F

∪{q}

else # q — подавляемое состояние #

Continue2:=true

fi;

R :=R ∪{r}; # Пополнение резольверных входов для ε #

α:=Push down list(D

f,r

);

# α — магазинная цепочка. Если она содержит магазинные

символы, которых еще нет в алфавите Γ

, то

Push down list

устанавливает флажок Continue2 в состояние true. #

( q, ε, r) := (Sup, α, σ);

od; # Конец цикла определения резольверных входов для ε.#

(q, ε):=R

fi # Конец определения ε -движений в подавляемом

состоянии q. #

od ; # Конец этапа пополнения таблиц

# Пополнение таблицы

Этот этап выполняется только при условии, что флажок

Continue2 был

установлен в состояние true в цикле пополнения таблиц

. Это же

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

новое подавляемое состояние или новый магазинный символ.

Рассматриваются всевозможные тройки вида (q, X, r), где q — подавляе-

мое состояние, X∈Γ

, r ∈(ℜ

∪{ε}), для которых значение

(q, X, r) не оп-

ределено, тогда как значение

(q, ε, r) определено. Если q и X сопряжены

по составному резольверу r (предполагается, что ι(r)=true, когда r=ε), то

по ним определяется возвратное состояние s, которое пополняет множество

, и

(q, X, r):=s.

Предполагается, что начальный нетерминал S не встречается в правых частях правил

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

этого легко добиться.

Цикл пополнения таблицы возвратных состояний

заканчивается, когда

рассмотрены все упомянутые тройки.

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

сле его завершения снова повторяется этап пополнения таблиц

. #

while Continue2

do Continue2:=false;

for ∀q : (q ∈Q

&Suppressible(q))

for ∀X :(X∈Γ

)

for ∀r : (r ∈(ℜ

∪{ε}))

(q, X, r)=undefined & Conj(q, X, r)

then # q и X сопряжены по составному резольверу r. #

s :={v |v ∈X &Mark(v)∈Mask(q, r)};

if s ∉Q

then # s — новое состояние. #

:=Q

∪{s}; Continue:=true

od # r #

od # X #

od # q #

od # Конец цикла пополнения таблицы возвратных состояний. #

od; # Конец главного цикла. #

# На этом заканчивается построение управляющей таблицы прямого про-

смотра. Затем производится последняя проверка, а именно: проверка

внешней балансировки грамматики (граф-схемы).

Проверка внешней балансировки. #

Ok:=true;

for ∀q :(q ∈Q

&Suppressible(q)) while Ok

do # Проверяется условие внешней балансировки для каждого дерева воз-

вратных состояний, построенного для подавляемого состояния q. #

Ok:=External balance(Return tree(q));

if ¬Ok

then Alarm ("Нарушена внешняя балансировка "

"в состоянии ", q)

100

Если во время исполнения последнего цикла не обнаружено нарушение

внешней балансировки

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

смотра δ

является правильной. Иначе она не годится для использования и в

этом случае необходимо попытаться исключить обнаруженные дефекты путем

эквивалентных преобразований исходной грамматики.

Вспомогательные алгоритмы для построения прямого просмотра. Да-

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

ренном алгоритме построения прямого просмотра.

Alarm — сигнализация нарушения ограничений, накладываемых на грам-

матику. Процедура выдает сообщение о нарушении необходимых и достаточ-

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

Она же прекращает процесс его построения.

Ambiguous — семантическая неоднозначность. Процедура дает результат

true, если множество, заданное ее параметром, содержит более одной семанти-

ческой цепочки. В противном случае ее результат — false.

Branches — множество ветвей, составляющих данный лес. Процедура

Branches(f), где f — некоторый лес, выдает множество ветвей, его составляю-

щих.

Conj — сопряженность подавляемого состояния с магазинным символом.

Считается, что подавляемое состояние q ∈Q

сопряжено с магазинным сим-

волом X ∈Γ

при условии r, если в момент обращения процессора прямого про-

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

дает true, на его вершине может оказаться символ X.

Функция Conj(q, X, r), где q — подавляемое состояние, X — магазинный

символ, r — составной резольвер, определяется следующим образом:

Conj(q, X, r)

def

Mask(q, r )⊆Mark(X)

Create edge — образовать ребро. Процедура Create edge(u, v) образует ори-

ентированную дугу от вершины u к вершине v.

Develope — разложение состояния. Разложение состояния q ∈Q

, являюще-

гося параметром процедуры Develope, выполняется по следующим шагам:

1. Создаются копии вершин, входящих в множество q. Будем считать, что

они принадлежат нулевому уровню разложения данного состояния q. Далее эти

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

при помощи последующих шагов алгоритма.

2. К каждому корню пристраиваются копии дуг управляющей граф-схемы,

инцидентных его прообразу, вместе с их концевыми вершинами и контекстны-

ми

метками, помечающими эти дуги. Будем считать, что множество присое-

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

ния q. Далее, level:= 1.

Балансировка называется внешней, так как она не может быть проверена локально по

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

управляющей таблице прямого просмотра.

См. определение функций Mask и Mark далее в этом разделе.

Т.е. семантическими и резольверными.