Реферат: Проектирование трансляторов
1. Для любой упорядоченной пары символов (Si, Sj) Si = Sj
тогда и только тогда, когда существует синтаксическое правило ти-
па U::=xSiSjy для некоторого символа U и некоторых строк x и y.
2. Для любой упорядоченной пары символов (Si,Sj) Si < Sj
тогда и только тогда, когда существует синтаксическое правило ти-
па U::= xSiUly для некоторых U, Ul, x, y и порождение Ul -> Sjz
для некоторой строки z.
3. Для любой упорядоченной пары символов (Si, Sj) Si > Sj
тогда и только тогда, когда:
a) существует синтаксическое правило типа U ::= xUkSjy для
некоторых U, Uk, x, y и порождение Uk -> zSi для некоторой стро-
ки z или
б) существует синтаксическое правило типа U ::= xUkUly для
некоторых U, Uk, Ul, x, y и порождения Uk -> zSi, Ul -> Sjw для
некоторых строк z и w.
Строки x,y,z,w могут быть пустыми.
4. В множество L(U) самых левых символов нетерминального
символа U входят все символы S такие, что существует порождение:
U -> Sz,
где z - некоторая строка (возможно, пустая).
Это определения может быть записано в виде:
Л(U) = .
5. В множество R(U) самых правых символов нетерминального
символа U входят все символы S такие, что существует порождение:
U -> zS,
где z - некоторая строка (возможно, пустая).
Это определения может быть записано в виде:
R(U) = существует строка z, такая, что (U -> zS) .
Данные выше формальные определения отношений предшествова-
ния и множеств самых левых и самых правых символов хорошо отра-
жают содержательную сторону определяемых понятий, но для их на-
хождения с помощью ЭВМ целесообразно использовать следующие ре-
курсивные определения (символ ] означает существование, символ /\
- "И", символ \/ - "ИЛИ", символ ф - правило):
1а. Si = Sj ::= ] ф (ф: U ::= xSiSjy).
2а. Si < Sj ::= ] ф ((ф: U ::= xSiUly) /\ Sj С L(Ul)).
3а. Si > Sj ::= ] ф ((ф: U ::= xUkSjy) /\ Si С R(Uk)) \/
(] ф ((ф: U ::= xUkUly) /\ Si С R(Uk)) /\
Sj С L(Ul)).
4a. L(U)= S | ]z (U ::= Sz) \/ ]z, U1 (U ::= U1z /\ S С L(U1)).
5a. R(U)= S | ]z (U ::= zS) \/ ]z, U1 (U ::= zU1 /\ S С R(U1)).
Всюду ф C P.
Определения 1а-5а дают эффективный алгоритм нахождения мно-
жеств L(U) и R(U) и отношений предшествования.
Рассмотрим алгоритм нахождение множества самых левых симво-
лов для символов, принадлежащих Vn.
Шаг 1: проверяем, является ли i-ый символ самым левым в
l-том синтаксическом правиле. Если да, то записываем Si в табли-
цу самых левых символов нетерминального символа Ul (при условии,
что он туда еще не записан);
Шаг 2: проверяем, не является ли символ Ul, для которого Si
- самый левый, самым левым символом Uk. Если да, то записываем
символы Ul и Si в таблицу самых левых символов нетерминального
символа Uk (при условии, что они туда еще не записаны).
Осуществляем просмотр всех синтаксических правил, изменяя
индекс l и k (два индекса для того, чтобы различать нетерми-
нальные символы в левой (k) и правой (l) частях правила); индекс
i указывает номер символа в синтаксическом правиле. Блок-схема
алгоритма показана на рис. 2.
┌─────┐
│ 1 │
└──┬──┘
│
┌──┴──┐
│ 2 ├──────────┐
└──┬──┘ │
│ │
нет / \ │
┌─────< 3 > │
│ \ / │
│ │да │
│ ┌──┴──┐ │
│ │ 4 │ │
│ └──┬──┘ │
└───────┤ │<
┌──┴──┐ / \ > ┌─────┐
│ 5 │ <13 >────┤ВЫХОД│
└──┬──┘ \ / └─────┘
┌────────────┤ │
│ / \ нет ┌──┴──┐
│ < 6 >────┐ │ 12 │
│ \ / │ └──┬──┘
│ да│ │ │да
┌──┴──┐ ┌──┴──┐ │нет / \
│ 9 │ │ 7 │ ├────<11 >
└──┬──┘ └──┬──┘ │ \ /
│ ├──────┘ │
│ < / \ > ┌──┴──┐
└──────────< 8 >────────┤ 10 │
\ / └─────┘
Рис. 2. Блок-схема алгоритма нахождения самых левых символов
Обозначения к алгоритму:
1. l = 1.
2. i = 1 - номер символа в синтаксическом правиле.
3. ] P: Ul ::= Si z - является ли i-ый символ самым левым
в синтаксическом правиле l.
4. Si записать в L(Ul): (L(Ul) = L (Ul) U Si).
5. k = 1.
6. ] P: Uk ::= Ul z - является ли Ul самым левым символом Uk
при условии, что Si C L(Ul).
7. L (Uk) = L (Uk) U Ul U Si - дополнить символами Ul и Si
мн-во L(Ul)
8. k < l (k, l - номера синтаксических правил),
проверка окончания цепочки.
9. k = k + 1.
10. i = i + 1.
11. Si = ; - завершилось ли синтаксическое правило.
12. l = l + 1.
13. l <= (L - общее число грамматических правил в грамматике).
Допущения к алгоритму:
- синтаксические правила отделены друг от друга ";"
- левая часть не отделяется от правой, и левая часть (т.е.
контекстно-свободная грамматика) всегда состоит из одного символа.
Аналогично можно построить множество самых правых символов.
Теперь перейдем к нахождению матрицы предшествования.
Блок-схема алгоритма построения матрицы предшествования, ис-
пользующая определения 1а-3а, представлена на рис. 3. Используют-
ся следующие условные обозначения:
i, j - индексы определяют номер символа в списке символов
языка.
M[i,j] - элемент матрицы предшествования;
l, k - номера синтаксических правил языка.
┌─────┐
│ 1 │
└──┬──┘
│
┌──┴──┐
│ 2 ├─────────────────────────┐
└──┬──┘ │
│ │
┌─────┐ / \ │
│ 4 │────< 3 >─────────────────┐ │
└─────┘ \ / │ │
│ │ │
┌──┴──┐ │ │
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
