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

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

121

4.8. ОПТИМИЗАЦИЯ УПРАВЛЯЮЩИХ ГРАФ-СХЕМ

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

имеющейся в оптимизированной управляющей таблице. Действительно,

сравнивая характеристики эквивалентных состояний между собой можно

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

Выполнив склейку таких вершин, при которой склеятся также и

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

числом вершин и дуг.

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

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

процессора, а также при генерации тестов.

Заметим, что несмотря на то, что любая RBNF-грамматика отображается в

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

оптимизации, может оказаться отображаемой в форму RBNF-грамматики

адекватно в том смысле, что не существует такой RBNF-грамматики, которая

отображалась бы в эту граф-схему. Другими словами, это отображение не

является биекцией.

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

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

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

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

например, на базе системы Рефал.

Редуцированная грамматика адекватная минимизированной граф-схеме

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

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

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

какой бы то ни было оптимизации.

122

Глава 5

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ

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

5.1. ПРИЧИНЫ, ЦЕЛИ И МЕТОДЫ ПРЕОБРАЗОВАНИЙ

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

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

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

построить адекватный сплайновый процессор. Как уже упоминалось, эти

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

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

1. Разложение любого состояния прямого просмотра должно быть конечно.

Как определено в гл.3, разложение состояния прямого просмотра

представляется в виде конечного множества деревьев (леса). Ограничение 1

означает, что все ветви этих деревьев должны иметь конечную длину. По

существу это равносильно недопустимости левосторонней рекурсии в правилах

грамматики.

2. Разложение каждого состояния прямого просмотра должно быть

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

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

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

тому же контексту

, должны иметь одну и ту же длину. Выполнение этого

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

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

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

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

магазин при приеме каждого входного символа.

3. Разложение каждого состояния прямого просмотра должно быть

сбалансировано по конечным листьям.

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

вида "end-A", где A — нетерминалы (не обязательно одинаковые), относящиеся

к одному и тому же контексту, должны иметь одинаковую длину. Выполнение

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

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

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

4. Разложение каждого состояния прямого просмотра должно быть

семантически сбалансировано.

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

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

123

Это значит, что все ветви разложения, о которых шла речь в двух предыду-

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

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

просмотра.

Ограничения 1−4 определяют внутренние свойства разложения каждого со-

стояния прямого просмотра. Последнее требование является внешним по от-

ношению к состояниям.

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

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

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

Ограничение 5 надо воспринимать "рекурсивно". Нарушение этого ограни-

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

нимать ли текущий входной символ в текущем состоянии (считать текущий

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

зировать в возвратном состоянии (т.е. отнести его к внешней конструкции).

Таким образом, необходимость или желательность эквивалентных преобра-

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

цию, может возникнуть по двум основным причинам:

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

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

зуемого в технологическом комплексе SYNTAX; необходимо построить экви-

валентную грамматику требуемого класса;

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

достижения большей степени регулярности грамматики; практически это уп-

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

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

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

(начальный) нетерминал и единственное RBNF-правило для него, и тогда

со-

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

конечным.

Часто, преследование второй из этих двух целей приводит одновременно и

к достижению первой.

Методы эквивалентных преобразований. Из определения трансляцион-

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

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

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

возможности: 1) преобразовывать управляющую грамматику, заботясь о сохра-

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

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

При условии, конечно, что начальный нетерминал не встречается в правой части этого

RBNF-правила грамматики.

124

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

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

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

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

чески эквивалентными

; очевидно, что любое синтаксически эквивалентное пре-

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

На практике используются обе возможности. Поскольку, как уже отмеча-

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

на эффективности процессора, но и на самой возможности его построения, то

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

ляющих исключить все несамовставленные нетерминалы. Напомним, что не-

терминал A ∈N называется самовставленным, если существует вывод вида:

A αAβ, где α и β∈W

, W=N∪T ∪ℜ∪Σ.

Другими словами, нетерминал A — самовставленный, если он выводится

сам из себя в одновременно непустых левом (α) и правом (β) контекстах. Если

нетерминал не является самовставленным, то он несамовставленный. В по-

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

т. е. таким, что одновременно существуют выводы вида:

A αA (праворекурсивность) и A Aβ (леворекурсивность).

И в самом деле, в противном случае из двух этих выводов можно было бы

построить вывод вида A αAβ.

Из теории формальных грамматик известно

, что язык, порождаемый КС-

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

некоторым конечным автоматом

. По следствию из теоремы Клини в этом

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

представляющее тот же самый язык. Оно может быть получено посредством

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

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

нять и к управляющим КС-грамматикам без самовставлений с целью получить

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

фицирующее то же самое синтаксическое управление. И тогда по этому регу-

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

же самую трансляцию. Во всяком случае, исключение из грамматики несамо-

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

Далее описывается алгоритм решения этой задачи.

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

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

преобразований приводится в гл.6.

См., например, [2].

Однако из этого не следует, что грамматика с самовставленными нетерминалами не

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

125

Алгоритм 5.1. Исключение несамовставленных нетерминалов из

управляющей КС-грамматики.

Вход: G

=(N,T,ℜ,Σ,P,S)—приведенная управляющая BNF-грамматика.

Выход: G

'= (N',T', ℜ', Σ',P',S')—управляющая RBNF-грамматика, не содер-

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

ски эквивалентная грамматике G

Метод:

1. Разобьем алфавит нетерминалов N данной грамматики G

на два непере-

секающихся подмножества N

и N

, включив в N

все несамовставленные не-

терминалы, а в N

— все остальные (самовставленные): N=N

∪N

2. Упорядочим каким-либо образом нетерминалы из N

. Пусть, например,

={A

, A

, ..., A

3. Рассмотрим правило для нетерминала A

∈N

. В общем случае оно имеет

вид

::= A

 A

 ... A

 β

 ... β

(5.1)

или

::= α

 α

 ...  α

 β

 ... β

(5.2)

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

рых α

,β

∈(N ∪Σ∪ℜ)

(i =1,2,...,n; j =1,2,...,k) не содержат нетерминала A

Очевидно, что правила (5.1), (5.2) эквивалентны правилам вида соответст-

венно

: (β

; β

; ... ; β

), (α

; α

; ...

; α

)

(5.1

)

: (α

; α

; ...

; α

)

(β

; β

; ... ; β

). (5.2

)

4. (Прямой ход). Пусть правила для первых p нетерминалов из N

уже

приведены к виду

:ϕ

,ψ

или A

:ψ

,ϕ

. (5.3)

где

, ψ

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

содержащие нетерминалов

,…,A

(i =1,2, ..., p).

Преобразуем правило для

к виду (5.3). Для этого в правую часть пра-

вила для

вместо каждого вхождения A

(

j =1,2,...,p)

последовательно

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

части правила для A

p+1

будут исключены нетерминалы A

,...,A

, причем

если A

p+1

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

двух соответствующих контекстов

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

нетерминал самовставленным или нет.

Т.е. сначала выполняются подстановки при j =1, затем полученные выражения

преобразуются подстановками при j =2, и т.д.

В противном случае вопреки предположениям какие-то из A

(i =1,2,...,p) оказались бы

самовставленными.

126

p+1

: A

p+1

, ψ

p+1

; ϕ

p+1

. или A

p+1

: ψ

p+1

, A

p+1

; ϕ

p+1

. ,

где ϕ

p+1

— регулярные выражения, не содержащие нетерминалов

,...,A

p+1

; после этого заменим крайние рекурсии на итерации и

правило для A

p+1

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

p+1

:ϕ

p+1

, ψ

p+1

. или A

p+1

:ψ

p+1

, ϕ

p+1

5. Повторяя шаг 4 для p =1, 2, ..., m –1 получаем правила требуемого вида

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

Заметим, что полученное таким образом правило для A

в своей правой

части не содержит ни одного несамовставленного нетерминала.

6. (Обратный ход). Для каждого p =m –1,m –2,...,1, подставляя в правую

часть правила, определяющего A

выражения, полученные для A

, A

m –1

,...,

p+1

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

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

7. Положим

′

={S}∪N

, T

=T, ℜ

=ℜ, Σ

=Σ, S

=S.

8. Наконец, преобразуем правила для нетерминалов из N

′

, подставив в их

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

предыдущих шагах алгоритма. В результате будут получены искомые правила

, определяющие нетерминалы из N

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

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

Очевидно, если N

= ∅, то грамматика G

' — явнорегулярна: в ней имеется

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

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

символами.

Замечание 1. Предложенный алгоритм в некотором смысле аналогичен

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

котором сначала (на прямом ходу) система приводится к “треугольному” виду,

а затем (на обратном ходу) посредством последовательных подстановок

находятся значения неизвестных.

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

применение к ней предложенного алгоритма дает явнорегулярную

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

Замечание 3. Принимая во внимание, что "сверхзадачей" алгоритма

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

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

исключить из него шаг 6 путем специального упорядочивания нетерминалов

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

Замечание 4. Несмотря на то, что описанный здесь алгоритм аналогичен

алгоритму 2.1 из монографии [2], он применим к более общему классу систем

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

коэффициентами.

127

5.2. НЕКОТОРЫЕ ПОЛЕЗНЫЕ

РЕГУЛЯРНЫЕ ТОЖДЕСТВА

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

следующие регулярные тождества, в которых A, B и C — произвольные

регулярные выражения

A ;B =B ;A (5.4)

(A ;B );C =A ;(B ;C ) (5.5)

(A ,B ),C =A ,(B ,C ) (5.6)

(A ;B ),C =A ,C;B ,C (5.7)

C ,(A ;B )=C,A;C,B (5.8)

A ,ε=ε,A =A (5.9)

A ,A

A =A

(5.10)

(A ,B )

,A =A #B (5.11)

(A #B )#C =A #(B ;C ) (5.12)

A #(B #C )=A ,(ε;B #(A ;C ),A) (5.13)

)#B =A #(ε;B ) (5.14)

[A ]=A ;ε (5.15)

5.3. ИЛЛЮСТРАЦИЯ

АЛГОРИТМА ИСКЛЮЧЕНИЯ НЕТЕРМИНАЛОВ

Продемонстрируем описанный алгоритм на примере грамматики,

определяющей числа в языке программирования Алгол 68. Заодно это

послужит свидетельством возможности применения SYNTAX-технологии к

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

Из [1] имеем следующее определение чисел посредством грамматики А. ван

Вейнгаардена:

NUMERAL :: fixed point numeral; (1.1)

variable point numeral; (1.2)

floating point numeral. (1.3)

fixed point numeral : digit cypher sequence. (2)

digit cypher : DIGIT symbol. (3)

NOTION sequence : NOTION; NOTION, NOTION sequence. (4)

DIGIT:: digit zero; digit one; digit two; digit three; digit four;

digit five; digit six; digit seven; digit eight; digit nine. (5)

variable point numeral : integral part option, fractional part. (6)

integral part : fixed point numeral. (7)

fractional part : point symbol, fixed point numeral. (8)

floating point numeral : stagnant part, exponent part. (9)

stagnant part : fixed point numeral; (10.1)

variable point numeral. (10.2)

Напомним, что ";" обозначает объединение, "," — конкатенацию,

"#"

— итерацию с

разделителем, "

" — усеченную итерацию, "

" — итерацию.

128

exponent part : times ten to the power choice, power of ten. (11)

times ten to the power choice : times ten to the power symbol; (12.1)

letter e symbol. (12.2)

power of ten : plusminus option, fixed point numeral. (13)

plusminus : plus symbol; minus symbol. (14)

NOTION option : NOTION; EMPTY. (15)

EMPTY :: . (16)

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

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

В отличие от обычных КС-грамматик, правила грамматики А. ван

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

называемые

гиперправила, а другой — метаправила. Одно гиперправило

фактически является схемой многих правил обычной КС-грамматики. Оно

состоит из левой и правой частей, отделяемых друг от друга двоеточием ':'. В

левой части находится

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

метапонятий — цепочек больших синтаксических знаков (букв) и малых

синтаксических знаков (букв), а в правой — некоторое множество

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

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

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

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

определяющие их правила.

Метапонятия порождаются при помощи метаправил. Множество

метаправил образует обычную КС-грамматику, в которой метапонятия играют

роль нетерминалов, а малые синтаксические знаки — роль терминалов. Левая

часть метаправила отделяется от правой двумя двоеточиями '::'. Из каждого

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

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

Механизм получения правил грамматики из гиперправила прост:

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

нибудь его терминальное метапорождение. При этом все вхождения одного и

того же метапонятия должны быть заменены на одно и то же терминальное

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

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

составленные из малых синтаксических знаков. Если такая цепочка

заканчивается на 'symbol', то она представляет терминал (символ), в противном

случае — нетерминал (понятие). Для каждого терминала определяется один

или несколько способов конкретного представления. Например, для терминала

'plus symbol' дается конкретное представление '+'.

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

для вывода предложений языка обычным образом

100

Строго говоря, такую грамматику нельзя считать КС-грамматикой, так как в общем

случае она может содержать бесконечное множество нетерминалов и бесконечное множество

правил.

129

В рассматриваемом примере NUMERAL, DIGIT, NOTION, EMPTY —

метапонятия, а (1.1)–(1.3), (5) и (16) — метаправила. Гиперправила — (3), (4) и

(15), остальное — правила.

Гиперправило (3) равносильно правилу

digit cypher : digit zero symbol ; digit one symbol ;

digit two symbol ; digit three symbol ;

digit four symbol ; digit five symbol ;

digit six symbol ; digit seven symbol ;

digit eight symbol ; digit nine symbol.

которое получается путем подстановки в (3) всех возможных терминальных

метапорождений метапонятия DIGIT.

Чтобы получить правило для понятия digit cypher sequence, используемого в

правой части правила (2), достаточно в гиперправило (4) вместо всех

вхождений метапонятия NOTION, подставить digit cypher в качестве

терминального метапорождения NOTION. В результате получаем правило

digit cypher sequence : digit cypher ;

digit cypher sequence, digit cypher.

Чтобы получить правило для понятия integral part option, используемого в

правой части правила (6), достаточно в гиперправило (16) вместо метапонятия

NOTION подставить его терминальное метапорождение integral part. Это даст

правило

integral part option : integral part ; .

Таким образом, мы получаем следующую обычную КС-грамматику,

определяющую числа в Алголе 68

101

, в которой терминальные символы

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

number : fixed point numeral ; (1.1)

variable point numeral ; (1.2)

floating point numeral. (1.3)

fixed point numeral : digit cypher sequence. (2)

digit cypher sequence : digit cypher ;

digit cypher sequence , digit cypher. (3)

digit cypher : '0'; '1'; '2'; '3'; '4'; '5'; '6'; '7'; '8'; '9'. (4)

variable point numeral : integral part option , fractional part. (5)

integral part option : integral part ; . (6)

integral part : fixed point numeral. (7)

fractional part : '.' , fixed point numeral. (8)

floating point numeral : stagnant part, exponent part. (9)

stagnant part : fixed point numeral ; variable point numeral. (10)

exponent part : times ten to the power choice , power of ten. (11)

times ten to the power choice : '\' ; 'e'. (12)

101

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

образом. Однако их можно увидеть "на фоне" соседних символов. Cм., например, правила (6) и

(14) на следующей странице.

130

power of ten : plusminus option, fixed point numeral. (13)

plusminus option : plusminus ; . (14)

plusminus : '+' ; '−'. (15)

Заметим, что гиперправило (1.1)–(1.3) фактически играет роль заглавного

правила в этой грамматике чисел. Чтобы оно выглядело как правило КС-

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

number, а метасинтаксическую связку ‘::’ разделителем ‘:’.

Начнем исполнение демонстрируемого алгоритма с констатации того

факта, что все нетерминалы этой грамматики являются несамовставленными.

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

открывающего возможность обойтись без "обратного хода", т.е. без шага 6:

= plusminus

= plusminus option

= power of ten

= times ten to

the power choice

= exponent part

= stagnant part

= floating point numeral

= fractional part

= integral part

= integral part option

= variable point numeral

= digit cypher

= digit cypher sequence

= fixed point numeral

= number

Начальным нетерминалом является number, и он — последний в заданном

упорядочивании. В новых обозначениях правила приобретают более

компактный вид:

: A

; A

: A

; A

, A

: '0' ; '1' ; '2' ; '3' ; '4' ;

'5' ; '6' ; '7' ; '8' ; '9'.

: A

, A

: A

; .

: A

: '.' , A

: A

, A

: A

; A

: A

, A

: '\' ; 'e'.

: A

, A

: A

; .

: '+' ; '−'.

Сначала требуется путем подстановок и исключения левосторонней

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

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

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

Правило для A

уже имеет требуемый вид: в его правой части нет ни одного

нетерминала.

В правиле для A

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

с меньшим номером.

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

в правую часть

правила для A

. Получаем:

: '+' ; '−' ; .