Мартыненко Б.К. Синтаксически управляемая обработка данных. Изд. 2-е, дополн
Подождите немного. Документ загружается.
131
В правиле для A
3
справа используется A
2
: требуется произвести подстановку
выражения для A
2
в правило для A
3
. Получаем:
A
3
: ('+' ; '−' ; ) , A
14
.
Теперь нетерминал в правой части (A
14
) имеет номер, больший, чем нетер-
минал в левой части (A
3
).
Правило для A
4
не нуждается в преобразованиях.
Правило для A
5
требуется преобразовать: вместо A
3
и A
4
подставим полу-
ченные для них выражения. Это дает
A
5
: ('\' ; 'e') , ('+' ; '−' ; ) , A
14
.
Правило для A
6
уже имеет требуемый вид.
Преобразуем правило для
A
7
, подставляя вместо A
6
и A
5
соответствующие
выражения. Получаем:
A
7
: (A
14
; A
11
) , A
4
, A
3
.
Продолжая подстановки вместо A
3
и A
4
, получаем:
A
7
: (A
14
; A
11
) , ('\' ; 'e') , (('+' ; '−' ; ) , A
14
).
Правила для A
8
и A
9
не требуют преобразований, поскольку и так имеют
требуемый вид.
Правило для A
10
преобразуем посредством подстановки выражения для A
9
.
В результате получаем:
A
10
: A
14
; . Короче, A
10
: [A
14
].
Аналогично правило для A
11
преобразуется к виду
A
11
: [A
14
] , '.' , A
14
.
Правило для A
12
преобразовывать не требуется.
Правило для A
13
приводится к виду
A
13
: A
12
; A
13
, A
12
= A
12
+
или
A
13
: d
+
.
Здесь d обозначает любой символ цифры.
Соответственно правило для A
14
приобретает вид
A
14
: d
+
.
Наконец, правило для A
15
преобразуется следующим образом:
A
15
: d
+
; [A
14
] , '.' , A
14
; A
7
=
d
+
; [d
+
], '.', d
+
; (A
14
; A
11
), ('\' ; 'e'), (('+' ; '−' ; ), A
14
) =
d
+
; d
*
, '.', d
+
; (d
+
; [A
14
], '.', A
14
), ('\'; 'e'), (('+' ; '−'; ), d
+
) =
d
+
; d
*
, '.' , d
+
; (d
+
; [d
+
] , '.' , d
+
), ('\'; 'e'), (('+' ; '−'; ), d
+
) =
d
+
; d
*
, '.', d
+
; (d
+
; d
*
, '.', d
+
), ('\'; 'e'), (['+' ; '−'], d
+
) =
(d
+
; d
*
, '.', d
+
), [('\'; 'e'), (['+' ; '−'], d
+
)].
132
Таким образом, мы получили эквивалентную явнорегулярную грамматику с
одним единственным правилом:
number : (d
+
; d
*
, '.', d
+
), [('\'; 'e'), (['+' ; '−'], d
+
)].
Здесь d = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}. Как видим, "обратный ход" не
потребовался.
В заключение этого параграфа перечислим основные синтаксически
эквивалентные преобразования управляющих грамматик:
• вынесение общих членов альтернатив за скобки (направо или налево);
• подстановка вместо использующего вхождения нетерминала
выражения, его определяющего;
• подстановка вместо некоторого подвыражения нового нетерминала,
определяемого этим подвыражением (пополнение грамматики еще
одним нетерминалом и соответствующим правилом для него);
• замена крайней (лево- или правосторонней) рекурсии на итерацию;
• замена обычной итерации, где возможно, итерацией с разделителем;
• использование тождеств, перечисленных в разд.5.2, для упрощения вида
правил.
5.4. РЕДУКЦИЯ КС-ГРАММАТИК
В этом параграфе мы обсудим использование информации об
эквивалентностях состояний и входных символов, получаемой при
оптимизации процессора прямого просмотра, для минимизации граф-схемы и
отображения ее в редуцированную RBNF-грамматику, т. е. эквивалентную
RBNF-грамматику с минимально возможным числом нетерминалов и
терминалов. Проиллюстрируем применение этого алгоритма для приведения к
минимальной форме КС-грамматики из предыдущего параграфа,
порождающей регулярный язык чисел Алгола 68, и КС-грамматики простой
модели арифметических выражений. Покажем, что задачу исключения
несамовложенных нетерминалов из КС-грамматики можно решить, не
прибегая к специальному алгоритму 5.1, использующем метод Гаусса, а
полагаясь на механизм макроподстановок вспомогательных понятий при
построении граф-схемы. Выясним, почему для минимальной граф-схемы,
построенной по первой грамматики, не существует адекватная RBNF-
грамматика. Опишем метод исключения всех нетерминалов из второй
грамматики, несмотря на то, что все они, за исключением начального
нетерминала, самовставленные.
Алгоритм 5.2. Минимизация граф-схемы по классам эквивалентности
Всюду, где в описании этого алгоритма говорится об отображении
множества вершин граф-схемы в одну, надо понимать, что область этого
преобразование не выходит рамки одной компоненты
102
.
102
Другими словами, “склеиваются” друг с другом только вершины, принадлежащие одной
компоненте.
133
С учетом классов эквивалентных состояний и лексических классов входных
символов, получаемых при оптимизации процессора, алгоритм минимизации
граф-схемы состоит из следующих шагов:
1. Начиная с начального, рассматривается очередной класс эквивалентных
состояний C.
(a) Если C начальный класс, то он всегда состоит из одного
начального состояния характеризуемого одной начальной вершиной граф-
схемы. Эта вершина при преобразовании граф-схемы переходить сама в себя.
(б) Если C класс не подавляемых состояний, то вершины этого
множества состояний V всегда помечены терминалами из одного лексического
класса L.
Преобразование граф-схемы: все вершины V отображаются в одну
вершину v, помеченную лексическим классом L. Все дуги, инцидентные
вершинам V, соединяются с v в качестве входных и выходных дуг
соответственно.
(в) Если C класс подавляемых состояний, то вершины V этого
множества состояний могут быть помечены либо только терминалами,
необязательно из одного лексического класса, либо только нетерминалами, не
обязательно одинаковыми.
Преобразование граф-схемы: если вершины V терминальные, то
они разделяются на подмножества согласно лексическим классам,
помечающих их терминальных символов. Все вершины одного подмножества
преобразуются так же, как описано в п. (б). Если вершины V
нетерминальные, то они обрабатываются как в п. (г).
(г) Если C класс возвратных состояний, то вершины этого множе-
ства состояний всегда помечены нетерминалами, причем необязательно
различными.
Преобразование граф-схемы: все вершины V, помеченные
одинаковыми нетерминалами, отображаются в одну вершину
v, помеченную
соответствующим нетерминалом. Все дуги, инцидентные вершинам-про-
образам вершины v, соединяются с v в качестве входных и выходных дуг
соответственно.
2. Процесс закачивается, когда рассмотрены все классы состояний.
Заметим, что случаи (в) и (г) относятся только к магазинным процессорам.
Образы дуг наследуют метки дуг-прообразов.
Пример 5.1. Редукция грамматики чисел. Проиллюстрируем этот метод
на примере грамматики чисел языка Алгол 68 (см. правила на стр. 130):
A
15
: A
14
; A
11
; A
7
.
A
14
: A
13
.
A
13
: A
12
; A
13
, A
12
.
A
12
: '0' ; '1' ; '2' ; '3' ; '4' ;
'5' ; '6' ; '7' ; '8' ; '9'.
A
11
: A
10
, A
8
.
A
10
: A
9
; .
A
9
: A
14
.
A
8
: '.' , A
14
.
A
7
: A
6
, A
5
.
A
6
: A
14
; A
11
.
A
5
: A
4
, A
3
.
A
4
: '\' ; 'e'.
A
3
: A
2
, A
14
.
A
2
: A
1
; .
A
1
: '+' ; '−'.
134
Теперь порядок нетерминалов не важен, лишь бы нетерминал A
15
оставался
начальным. Если бы не леворекурсивное правило для A
13
, то все нетерминалы,
кроме A
15
, можно было перенести из списка нетерминалов в список
вспомогательных понятий и автоматически получить явнорегулярную
грамматику. Воспользовавшись функцией Reduce ТК SYNTAX для
исключения левой рекурсии из BNF-правил, мы получаем правило A
13
: A
12
,
A
12
*
103
. Теперь ничто не мешает использовать механизм макроподстановок для
получения явнорегулярной граф-схемы. Ее представление в виде диаграммы
Вирта показано на рис. 5.1.
Рис. 5.1. Граф-схема A68NUM в виде диаграммы Вирта.
В ней при вершинах указаны номера записей, представляющих их во
внутреннем представлении граф-схемы. Метки вершин, порождающих цифры,
заменены на псевдотерминал ‘d’ только для того, чтобы не загромождать
рисунок. Построенный по этой граф-схеме конечный процессор A68NUM имеет
12 состояний, характеристики которых приведены в табл. 5.1.
Таблица 5.1.
Сост.
Вершины
Сост.
Вершины
Сост.
Вершины
s1 {0} s5 {107} s9 {116}
s2 {5, 23, 58, 75} s6 {109} s10 {118}
s3 {36, 88} s7 {40, 92} s11 {44, 96}
s4 { 9, 27, 62, 79} s8 {125} s12 {129}
В результате минимизации процессора A68NUM получаются следующие
лексические классы:
Таблица 5.2.
Лек.
класс
Символы
Лек.
класс
Символы
Лек.
класс
Символы
Лек.
класс
Символы
L1:
d ={ 0−9 }
L2:
{ . } L3: { \ е) } L4:
{+ − }
и классы эквивалентных состояний (см. табл. 5.3):
103
Или эквивалентное правило A
13
: A
12
+
.
135
Таблица 5.3.
Класс
сост.
Состояния класса
эквивалентности
Класс
сост.
Состояния класса
эквивалентности
Класс
сост.
Состояния класса
эквивалентности
C1 {s1} C3 {s3} C6 {s8, s12}
C2 {s2, s4} C4 {s5, s6} C7 {s9, s10}
C3 {s3} C5 {s7, s11 }
На рис. 5.2 показан вид граф-схемы A68NUM после обработки классов
эквивалентных состояний C1−C7 с учетом лексических классов. Заметим, что в
этом примере задействованы лишь ситуации (а) и (б) алгоритма минимизации
граф-схемы.
Рис. 5.2. Вид минимизированной граф-схемы A68NUM.
Обратное отображение граф-схемы в RBNF-грамматику
Конвертация граф-схемы в грамматическую форму может быть
произведена по-компонентно, т. е. одна компонента граф-схемы отображается
в одно правило грамматики. Это делается рекурсивно по виду элементов и
структуре их соединений элементов согласно таблицам 1.5 и 1.6 из гл. 1.
Замечание 5. Несмотря на то, что любая RBNF-грамматика отображается в
граф-схему, не всякая граф-схема, в частности, полученная в результате
минимизации, может оказаться отображаемой в форму RBNF-грамматики
адекватно, т. е. не существует такой RBNF-грамматики, которая отображалась
бы в эту граф-схему. Так в рассматриваемом примере в результате
минимизации получилась “слишком минимальная” граф-схема: невозможно
построить эквивалентное регулярное выражение с таким же числом операндов,
каково число внутренних вершин в граф-схеме. Причина в том, что две
подсхемы, представляющие подформулы (‘d’
+
) и (‘.’, ‘d’
+
), соединены
одновременно последовательно (рис. 5.3 а) и параллельно (рис. 5.3 б).
Рис. 5.3. Последовательное и параллельное соединение двух подсхем.
Однако не возможно эти два экземпляра подформул соединить
одновременно регулярными операциями конкатенации “,” и объединения “;”
как операнды одной большой формулы. Действительно, если схема S состоит
из подсхем S
1
и S
2
, порождающих соответственно множества цепочек L
1
и L
2
, а
‘.’ , ‘d’
+
‘d’
+
(а)
(б)
136
f
1
и f
2
формулы, представляющие порождения этих подсхем, то множество L
цепочек, порождаемых схемой S, есть
L = (L
1
L
2
) ∪ (L
1
∪ L
2
) = L
1
L
2
∪ L
1
∪ L
2
= L
1
[L
2
] ∪ L
2
= [L
1
]L
2
∪ L
1
.
Соответствующее регулярное выражение f, представляющее множество L,
есть f = f
1
,
[f
2
] ; f
2
или f = [f
1
] , f
2
; f
1
.
Если схема S не порождает множество цепочек, в котором содержится пус-
тая цепочка, то регулярное выражение, представляющее такую схему, не адек-
ватно ей. В противном случае соответствующее регулярное выражение есть f =
[f
1
], [f
2
], и оно адекватно схеме S, т. е. отображается в ту самую схему, из кото-
рой оно было получено.
Именно такой случай имеет место в языке Паскаль. В нем числа описыва-
ются подобной редуцированной граф-схемой (см. рис. 5.4), но без параллель-
ной связи, о которой шла речь выше (см. подсхемы F и E). Поэтому эта граф-
схема адекватна регулярному выражению ‘d’
+
, [‘.’, ‘d’
+
], [‘e’, [‘+’ ; ‘−’], ‘d’
+
],
которое получается из нее обратным отображением.
Рис. 5.4. Редуцированная граф-схема чисел языка Паскаль.
Пример 5.2. Редукция грамматики выражений
Пусть дана исходная КС-грамматика EXPRESS:
NONTERMINALS: S, E, T, F.
TERMINALS : ‘+’, ‘*’, ‘(‘, ‘)’, ‘a’.
(1) S : E.
(2) E : E, '+', T ; T.
(3) T : T, '*', F; F.
(4) F : '(', E, ')' ; 'a'.
В ней все нетерминалы, кроме начального S, являются самовставленными,
и потому не исключаются методом, описанном в алгоритме 5.1. Однако исклю-
чение из данной грамматики нетерминалов T и F возможно, несмотря на то, что
они самовставленные.
Действительно, после исключения явных левосторонних рекурсий (посред-
ством функции Reduce ТК SYNTAX) из правил (2) и (3) мы получаем регуляри-
зованную RBNF-грамматику EXPRESS1:
NONTERMINALS: S, E, T, F.
(1) S: E.
(2) E: T , ( '+' , T)
*
.
(3) T: F , ( '*' , F)
*
.
(4) F: '(' , E , ')' ; '
a'.
137
Затем без труда обнаруживается, что S = ρ
1
(E), E = ρ
2
(T), T = ρ
3
(F), F =
ρ
4
(E), где ρ
i
(i = 1, 2, 3, 4) некоторые регулярные выражения, зависящие от
нетерминалов, указанных в скобках. Это значит, что E = ρ
2
(T) = ρ
2
(ρ
3
(F)) =
ρ
2
(ρ
3
(ρ
4
(E))) и для автоматического выполнения указанных подстановок
достаточно символы T и F перевести в список вспомогательных понятий, не
меняя множества правил. В результате получаем регуляризованную RBNF-
грамматику EXPRESS2:
NONTERMINALS: S, E.
AUXILIARY NOTIONS : T, F.
(1) S: E. (3) T: F , ( '*' , F)
*
.
(2) E: T , ( '+' , T)
*
. (4) F: '(' , E , ')' ; 'a'.
При построении граф-схемы по этой грамматике регулярные выражения,
определяющие вспомогательные понятия T и F, встраиваются в компоненту
для нетерминала E (см. рис. 5.5).
Рис.5.5. Граф-схема грамматики EXPRESS2.
Процессор, построенный по исходной граф-схеме EXPRESS2, имеет
характеристики состояний, указанные в табл. 5.4.
Таблица 5.4.
Сост. Вершины Сост. Вершины Сост. Вершины Сост. Вершины
s1 {0} s6 {30} s11 {40}
s16
{18}
s2 {7} s7* {34} s12* {44}
s17
{41}
s3* {11} s8 {17}
s13
{1} s18* {9}
s4 {26} s9* {21}
s14
{8} s19* {32}
s5 {14} s10 {37}
s15
{31} s20* {19}
Звездочками помечены подавляемые состояния.
Жирным шрифтом выделены возвратные состояния.
s21* {42}
3
11
7
8
9
14
17
18
19
21
37
44
40 41 42
34
26
303132
49
2
1
0
138
Оптимизация процессора EXPRESS2 дает классы эквивалентных входных
символов и состояний, приведенных в табл. 5.5 и 5.6.
Таблица 5.5.
Лек.
класс
Симв.
Лек.
класс
Симв.
Лек.
класс
Симв.
Лек.
класс
Симв.
L1: { + * } L2: { ( } L3: { ) } L4:
{ a }
Таблица 5.6.
Класс Состояния класса Множества вершин
C1 {s1} {{0}}
C2 {s2, s6, s8, s11} {{7-(},{30-(},{17-(},{40-(}}
C3
*
{s3, s7, s9, s12,
s18, s19, s20, s21}
{{11-a},{34-a},{21-a},{44-a},
{9-)},{32-)},{19-)},{42-)}}
C4 {s4, s5, s10} {{26-+},{14 -*},{37-*}}
C5
{s13} {{1-E}}
C6
{s14, s15, s16, s17 } {{8-E},{31-E},{18-E},{41-E}}
Применение алгоритма 5.2 с учетом информации, приведенной в табл.
5.4−5.6, дает минимизированную граф-схему, показанную на рис. 5.6.
Рис. 5.6. Минимизированную граф-схема EXPRESS2.
Поясним, что класс подавляемых состояний C3 породил два образа вершин,
отмеченных на рис. 5.6 обозначениями C3-1 и C3-2.
Реконструкция RBNF-грамматики по полученной редуцированной граф-
схеме EXPRESS2 дает только два правила для нетерминалов S и E:
NONTERMINALS: S, E.
(1) S : E.
(2) E : (‘(’, E, ‘)’; ‘a’) # (‘+ ; *’).
Это и есть адекватная минимальная RBNF-грамматика, эквивалентная ис-
ходной КС-грамматике EXPRESS. В ней роль терминалов играют синтаксиче-
ские классы входных символов. Правило (1) не изменилось. Оно используется
лишь для того, чтобы удовлетворить одному из условий SYNTAX-технологии:
начальный нетерминал грамматики не должен встречаться в правой части ни
одного из ее правил.
139
Глава 6
ПРАКТИЧЕСКИЕ АСПЕКТЫ
ПРИМЕНЕНИЯ SYNTAX-ТЕХНОЛОГИИ
6.1. ПОСТРОЕНИЕ
ТРАНСЛЯЦИОННОЙ ГРАММАТИКИ
TSL
104
-cпецификацию трансляции некоторого языка программирования
можно построить, исходя из обычной BNF-грамматики, которая является
традиционной формой представления синтаксиса языка при его публикации.
Как известно, каждое правило BNF-грамматики состоит из левой и правой
частей, разделяемых метасинтаксической связкой '::='. В левой части находится
определяемый нетерминал, а правая есть список альтернатив, разделяемых
метасинтаксической связкой '|'. Альтернатива — это цепочка членов, каждый
из которых есть терминал или нетерминал. Нетерминалы принято представлять
цепочками символов, заключенными в метасинтаксические скобки '<' и '>', а
все прочие символы, отличающиеся от метасинтаксических знаков, трактуются
как терминальные. Например, следующие правила BNF-грамматики
определяют целые без знака — традиционные элементы многих языков
программирования:
<целое без знака> ::= <цифра> | <целое без знака> <цифра>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
В этих правилах <целое без знака> и <цифра> — нетерминалы, а 0,
…,9 —
терминалы. Имеются две альтернативы в первом правиле и десять — во
втором. Вторая альтернатива первого правила состоит из двух
(конкатенируемых) членов <целое без знака> и <цифра>, каждый из которых
является нетерминалом. В TSL-нотации эти же правила имеют вид
целое без знака : цифра ; целое без знака , цифра.
цифра : '0' ; '1' ; '2' ; '3' ; '4' ; '5' ; '6' ; '7' ; '8' ; '9'.
Использование в ней явного обозначения для конкатенации (запятой)
позволяет опускать метасинтаксические скобки в обозначении нетерминалов.
То, что эти цепочки обозначают нетерминалы, определяется благодаря
дополнительному описанию:
Nonterminals : целое без знака, цифра.
включаемому в TSL-спецификацию.
104
Метаязык TSL описывается в гл.8.
140
Для определения операционной семантики некоторой конструкции языка
достаточно в правые части правил исходной грамматики внести семантические
и резольверные символы и задать их интерпретацию в некоторой
операционной среде на некотором инструментальном языке
программирования. Планирование семантических преобразований
производится в контексте отдельного правила грамматики, точнее, каждой его
альтернативы (т.е. члена объединения). Следует исходить из того, что входная
цепочка реализуемого языка является заданием преобразований операционной
среды, которые выполняются по ходу ее сканирования и анализа.
Предполагается, что механизм анализа, сканируя входную цепочку,
сопоставляет некоторую ее часть с рассматриваемой альтернативой, как с
образцом, определяющим ее структуру. При этом подразумевается, что те
преобразования, которые заданы подцепочками, соответствующими
вхождениям нетерминалов в образец, уже выполнены во время сканирования
этих подцепочек. В данной же альтернативе правила необходимо определить
продолжение этих преобразований операционной среды, исходя из текущего ее
состояния.
Представление о текущем состоянии операционной среды складывается при
рассмотрении данной альтернативы по ее составу и правилам трансляционной
грамматики, определяющим нетерминалы, входящие в данную альтернативу, с
учетом семантик, используемых в упомянутых правилах.
Продолжение преобразований, ассоциированных с некоторым вхождением
нетерминала в данную альтернативу, задается путем вставки семантического
символа или даже последовательности таких символов после данного
вхождения нетерминала (т.е. справа) — для прямого просмотра или перед ним
(т.е. слева) — для обратного.
В отличие от описанной трактовки нетерминалов, предполагается, что с
вхождением терминала в образец не связаны никакие предварительные
преобразования. Они как раз и должны начаться в данной альтернативе в связи
с данным вхождением терминального символа. Для указания требуемых
преобразований, связанных с данным вхождением терминала, следует вставить
семантический символ или последовательность таких символов
слева от него
— для прямого просмотра, или
справа от него — для обратного.
Что касается резольверных символов, то размещение резольверной цепочки
слева от терминального символа (для прямого просмотра) или справа от него
(для обратного) определяет некоторое контекстное условие
105
, при выполнении
которого только и допустим данный символ.
Каждый новый резольверный или семантический символ полезно вносить в
реестр спецификаций, ассоциированных с такими символами предикатов и
преобразований операционной среды. Ведение такого реестра в процессе
написания трансляционной грамматики помогает повторно использовать уже
определенные семантики и резольверы в других правилах. В дальнейшем эти
спецификации используются при написании кода, реализующего
соответствующие предикаты и преобразования операционной среды.
105
Это условие — истинность конъюнкции предикатов, ассоциированных с резольверными
символами соответственно прямого или обратного просмотров.