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

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

101

3. К каждой вершине уровня level, которая помечена нетерминалом, при-

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

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

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

вершины будем считать относящимися к уровню level+1 разложения состоя-

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

Шаг 3 повторяется до тех пор, пока не обнаружится, что на текущем уровне

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

жения состояния q заканчивается. Если же шаг 3 “зацикливается”, разложение

состояния q — бесконечно

External balance — проверка внешней балансировки. Процедура External

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

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

ит в том, что для каждой пары вершин, принадлежащих одной и той же ветви

этого дерева и представляющих некоторые состояния q

и q

, должно быть:

Accept(q

) ∩ Accept(q

)=∅,

где Accept(q)

def

{a | a ∈Σ

& ∃r : (r ∈ℜ

(q, a, r) — определено} —

множество входных символов, допустимых в состоянии q.

Forward pass semantics — семантика леса. Процедура Forward pass

semantics(f) определяет множество семантических цепочек прямого просмотра

для леса f, заданного ее параметром. Именно, для каждой ветви леса f опреде-

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

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

зультата процедуры.

Height

— высота леса. Процедура Height вычисляет высоту леса, заданного

ее параметром. Она равна длине самой длинной ветви по всем деревьям, вхо-

дящим в данный лес, и выражается числом дуг, составляющих эту ветвь.

Leaves — множество листьев. Процедура Leaves выдает множество

листьев, т. е. концевых вершин леса или множества ветвей, заданного ее

параметром.

Mark

— метки вершин. Процедура Mark выдает множество меток, поме-

чающих вершины, заданные ее параметром.

Mark

ℜ

— резольверные метки. Процедура выдает цепочку резольверов

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

просмотра.

Mask — нетерминалы меток конечных вершин.

Процедура Mask(q, r), где q — подавляемое состояние, r — цепочка ре-

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

входящих в состав меток конечных вершин — листьев тех ветвей разложения

Разумеется, фактическое “зацикливание” алгоритма не допускается. Признаком,

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

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

102

состояния q, которые помечены цепочкой r, если в метках этих ветвей игнори-

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

смотра, т. е.

Mask(q, r)

def

{A | A ∈N&

&∃v :(v ∈Leaves(Selectedbranches(Develope(q), r))&

&Mark(v)="end-A")}.

Push-down list — магазинная цепочка. Эта процедура выдает цепочку мага-

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

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

вершин одного уровня, вносится в словарь магазинных символов Γ

. Вот алго-

ритм ее реализации.

Вход: f — лес, некоторое множество ветвей разложения некоторого состоя-

ния. Все ветви f имеют одинаковую длину.

Выход: α — цепочка магазинных символов из Γ.

Метод: α := ε;

for i to Height(f)–1

do # Инициализация магазинной цепочки #

X :={v | v∈Vertex

(f)}; # X — магазинный символ, множество нетерми-

нальных вершин f уровня i. #

α := Xα; # Наращивание магазинной цепочки #

if X∉Γ

then # Пополнение алфавита магазинных символов #

Γ:=Γ∪{X}

Return tree — дерево возвратных состояний. Эта процедура строит дерево

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

параметра. Именно, строится корень дерева R =Repr(q), представляющий дан-

ное состояние q, и инициализируется дерево возвратных состояний: RT:=R.

Считается, что R принадлежит уровню 0.

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

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

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

ных цепочек и магазинных символов).

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

ставляют неподавляемые состояния или являются повторными образами по-

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

. Для

этого выполняются следующие действия:

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

контролируется. Поэтому данный алгоритм "зацикливается", если дерево возвратных

состояний оказывается бесконечным.

103

for i from 0 while ∃v :(v ∈Vertex

(RT)&

∃p :(v =Repr(p)& Suppressible(p)))

do for ∀v :(v ∈Vertex

(RT)&∃p :(v =Repr(p)&Suppressible(p)))

# Здесь Vertex

(RT) — множество вершин дерева возвратных состояний

RT уровня i. Равенство v =Repr(p) означает, что вершина v дерева воз-

вратных состояний RT представляет состояние p. #

do for ∀X :(X ∈Γ

)

do for ∀r :(r ∈ℜ

(p,X,r)=q)

do # Провести дугу из вершины v во вновь создаваемую вершину w,

которая представляет возвратное состояние q. Вершину w счи-

тать относящейся к уровню i + 1 #

w := Repr(q); Create edge(v, w)

Selected branches — множество ветвей, помеченных данной резольверной

цепочкой. Процедура Selected branches(f, r), где f — некоторый лес, а r — це-

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

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

верные символы обратного просмотра, равны r.

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

Suppressible(q), где q — некоторое состояние, выдает true, если состояние q —

подавляемое, и false — в противном случае.

Vertex

— множество вершин уровня i. Процедура Vertex

(f) выдает множе-

ство вершин уровня i в дереве или лесу f, заданном ее параметром.

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

Вход: G

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

— множество состояний прямого просмотра

Выход:

= (Q

,Σ

,Γ

,∆

,ℜ

,δ

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

сор обратного просмотра, где Q

— множество состояний, Σ

— входной

алфавит, Γ

— магазинный алфавит, ∆

— алфавит семантик, ℜ

— алфа-

вит резольров,

) — управляющая таблца,  состоящая из таблицы

резольверов

δ :Q

×(Σ

∪{ε})→2ℜ

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

×(Σ

∪ {ε})×ℜ

→(Q

∪{Pop})×(Γ

∪{ε})×∆

— начальное со-

стояние, F

⊆Q

— множество конечных состояний.

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

вершин управляющей граф-схемы.

104

Метод:

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

:=Q

; ∆

и ℜ

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

:= {v |v ∈Vertex(G

):Mark(v)="end-S"};

:= ∅; Q

:= {

}; Γ

:= ∅;

# Построение

for ∀q : (q∈Q

) # q — некоторое состояние

обратного просмотра #

for ∀t :(t∈Σ

) # t — некоторое состояние прямого просмотра #

do E := Edges(t, q); # E — множество дуг граф-схемы, начала которых нахо-

дятся в множестве t, а концы — в множестве q #

if E

≠∅

then # E — не пусто #

R:= Backward pass resolvers(E); # R — множество цепочек, состоящих из

резольверных символов обратного про-

смотра, входящих в состав контекстных

цепочек, помечающих дуги множества E #

δ (q, t):=R;

for ∀r : (r ∈R)

SE := Select edges(E, r); # SE — подмножество дуг E, метки которых, если

в них принимать во внимание только резоль-

верные символы обратного просмотра, равны r

p :=∅;

for

∀e∈SE do p := p ∪Start(e) od ;

# Определение семантики #

σ := Backward pass semantics(SE);

if Ambiguous(σ)

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

q, "по входу ", t, " и резольверу ", r)

fi;

if Nonterminals(p)

then # p — нетерминальные вершины: прохождение правой границы

терминального порождения некоторого понятия, помечающего одну

из вершин множества p. #

s :={v v ∈Vertex(G

)&Mark(v)="end-A"&A ∈Mark(p)};

if s ∉Q

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

:= Q

∪{s}

fi;

105

if p∉Γ

then # p — новый магазинный символ #

:= Γ

∪{p}; Q

:= Q

∪{p};

fi;

(q,t,r):=(s, p, σ)

else # p состоит из терминальных вершин или начальной вершины за-

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

(q,t,r):=(p, ε, σ)

od # r #

od # t #;

s := {v v ∈Vertex(G

)&Mark(v)="begin-A"&Succ(v) ∩ q ≠∅};

if s ≠∅

then # Достигнута левая граница терминального порождения некоторого по-

нятия, являющегося меткой одной из вершин, входящих в множество,

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

E := Edges (s, q); # E — множество дуг граф-схемы, начала которых

находятся в множестве s, а концы — в множестве q #

R := Backward pass resolvers (E); # R — множество цепочек, со-

стоящих из резольверных символов обратного просмотра,

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

ги множества E #

(q, ε) := R;

for ∀r : (r∈R)

do SE:=Select edges(E, r); # SE — подмножество дуг E, метки которых, если

в них принимать во внимание только резольвер-

ные символы обратного просмотра, равны r #

# Определение семантики #

σ := Backward pass semantics(SE);

if Ambiguous (

σ)

then # Диагностика семантической неоднозначности #

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

" по

ε−входу и резольверу ", r)

fi;

(q, ε, r):=(Pop, ε, σ)

od # r #

od # q #;

:= {q∈Q

Edges({v

}, q) ≠∅, Mark(v

)="begin-S"}

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

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

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

106

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

просмотра, а вместе с тем и построение всего челночного процессора.

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

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

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

Backward pass resolvers — резольверы обратного просмотра. Процедура

Backward pass resolvers(E), где E — некоторое множество дуг управляющей

граф-схемы, дает множество цепочек резольверов обратного просмотра, зало-

женных

в метки этих дуг.

Backward pass semantics — семантики обратного просмотра. Процедура

Backward pass semantics(E), где E — некоторое множество дуг управляющей

граф-схемы, выдает множество семантических цепочек обратного просмотра,

заложенных

в метки дуг множества E.

Edges — дуги. Процедура Edges(p, q), где p и q — некоторые множества

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

ходятся в множестве p, а концы — в множестве q.

Nonterminals — нетерминалы. Процедура дает результат true, если множе-

ство, заданное ее параметром, состоит из нетерминальных вершин, и false — в

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

Select edges — выборка подмножества дуг. Процедура Select edges(E, r) из

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

которые заложена цепочка резольверных символов обратного просмотра r.

Start

— начало дуги. Процедура Start (e), где e — дуга, дает вершину, из

которой эта дуга выходит.

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

просмотра, но здесь не определенные, были описаны ранее.

3.5. СПЕЦИФИКАЦИЯ ЧЕЛНОЧНЫХ ТРАНСЛЯЦИЙ

ПРИ ПОМОЩИ

ТРАНСЛЯЦИОННЫХ RBNF-ГРАММАТИК

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

можно специфицировать и при помощи трансляционных RBNF-грамматик.

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

должны быть разделены по просмотрам. Термин просмотр в данном случае

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

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

ционные грамматики также будем называть челночными.

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

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

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

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

107

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

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

в разд. 1.2, указанием, что ℜ=ℜ

∪ℜ

ℜ

∩ℜ

=∅, Σ=Σ

∪Σ

, Σ

∩Σ

=∅,

и принять во внимание расширенное понимание операционной среды, данное в

разд.3.2. Тогда под трансляцией, специфицируемой челночной трансляционной

грамматикой G

, будем понимать множество

τ(G

)={(x,[e]

)|∃C

:(C

∈Ñ(G

), C

=κ

...κ

n –1

, где a

∈T (i =1, 2, ..., n;

≥0), κ

∈(ℜ∪Σ)

(m =0, 1, 2, ..., n) интерпретируются синхро-

низированно, x

= a

...a

— входная цепочка}.

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

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

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

ной цепочки κ

— семантические подцепочки прямого и обратного

просмотров контекстной цепочки κ

. Синхронизированная интерпретация

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

имеют место соответствующие равенства:

На прямом просмотре: На обратном просмотре:

) :

= ι

(

) :

(

= ι

(

n -

(

= ι

−

(

... ...

(

) :

= ι

(

) : e = ι

(

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

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

терминалу в управляющей цепочке (

). Эти предикаты вычисляются на на-

чальном состоянии операционной среды (e

). Если все они выполняются, то

производятся преобразования начального состояния операционной среды (e

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

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

). Ре-

зультатом этих преобразований является новое состояние операционной среды (

Затем на достигнутом состоянии операционной среды (

) вычисляются

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

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

). Если все

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

онной среды (

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

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

тельности (

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

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

), и т. д.

Мы используем обозначения, введенные при определении трансляции τ(G

108

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

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

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

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

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

щей цепочки (

). Если она выполняется, производятся преобразования опера-

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

просмотра, следующими за последним терминалом (

), в порядке, обратном

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

конъюнкции предикатов, ассоциированных с резольверными символами об-

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

), дает истину,

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

мантическими символами обратного просмотра, предшествую-щими первому

терминалу (

), в обратном порядке.

Полученное финальное состояние операционной среды (

e) в проекции на

объектное подпространство H, и есть результат челночной трансляции входной

цепочки. Если же хотя бы один предикат, вычисляемый в этом процессе, не

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

что входная цепочка содержит контекстную ошибку. Входная цепочка будет

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

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

каты которой синхронизированно выполняются.

109

Глава 4

ОПТИМИЗАЦИЯ ЧЕЛОЧНЫХ

ПРОЦЕССОРОВ

4.1. О МЕТОДЕ ОПТИМИЗАЦИИ

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

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

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

весьма объемными. Путем искусного кодирования можно добиться некоторой

экономии памяти, необходимой для их размещения. И хотя эту возможность не

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

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

нии отношений эквивалентности на множествах состояний, входных и мага-

зинных символов и использовании в управляющих таблицах классов эквива-

лентности в этих отношениях взамен элементов соответствующих множеств.

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

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

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

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

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

практика, уменьшается на десятки процентов, а то и в несколько раз. При этом

заметно сокращается количество обращений к таблице возвратных состояний,

и часто она оказывается совсем ненужной.

Опишем подробнее этот метод оптимизации челночных процессоров, ко-

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

конечным.

Отношения эквивалентности, о которых идет речь, определяются на осно-

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

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

4.2. ЭКВИВАЛЕНТНОСТЬ СОСТОЯНИЙ,

МАГАЗИННЫХ

И ВХОДНЫХ СИМВОЛОВ

Определение 4.2.1. Пусть q

, q

∈Q

— два состояния прямого просмотра.

Состояния

и q

считаются

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

следующих условий:

110

1) различны множества входных символов (включая ε

), допустимых в

этих состояниях, т. е. существует входной символ a ∈Σ

∪{ε}, такой, что из

двух значений

,a) и

,a) определено только одно; иначе

2) существует такой входной символ a

∈

∪{ε}, для которого множества

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

т. е.

,a) ≠

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

3) существуют такой входной символ a

∈

∪{ε}и такая резольверная

цепочка r ∈ℜ

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

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

,a,r)=(p

,α

,σ

) и

,a,r)= (p

,α

,σ

), то σ

≠σ

и/или α

≠α

(см.

далее определение 4.2.3); в противном случае

4) если оба состояния q

и q

— подавляемые, различны множества мага-

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

почке r, т. е. существуют магазинные символы X, Y ∈Γ

, такие, что из двух зна-

чений

,X,r) и

,Y,r) определено только одно; в противном случае эти

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

5) рассматриваемые состояния q

и q

различны как входные символы об-

ратного просмотра, если он используется; либо

6) различны соответствующие переходные состояния p

и p

в силу данного

определения

Определение 4.2.2. Состояния прямого просмотра q

, q

∈Q

эквивалентны,

если они не различимы согласно определению 4.2.1.

Эквивалентность состояний обратного просмотра определяется аналогично

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

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

на обратном просмотре не используется.

Определение 4.2.3. Магазинные цепочки α

... X

и α

... Y

∈Γ

, 1≤i ≤m, m ≥0, 1 ≤j≤n, n ≥0) — различны, если различна их длина, т. е.

m ≠n, в противном случае, если существует такое i (1≤i ≤m), что магазинные

символы

и Y

—

различны в силу следующего определения:

Определение 4.2.4. Два магазинных символа X,Y

∈

—

различны, если вы-

полняется хотя бы одно из следующих условий:

1) существует резольверная цепочка r ∈ℜ

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

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

зольверу r, в противном случае

Строго говоря, ε — не входной символ, а цепочка, в которой нет ни одного символа.

В этом определении первые пять признаков различимости — базовые, a шестой

определяет рекурсивное сведение к этим базовым признакам.