Смекни!
smekni.com

Проектирование трансляторов (стр. 5 из 31)

некоторых 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) = { S | существует строка z, такая, что (U -> Sz) }.

5. В множество R(U) самых правых символов нетерминального

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

U -> zS,

где z - некоторая строка (возможно, пустая).

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

R(U) = { S | существует строка z, такая, что (U -> zS) }.

Данные выше формальные определения отношений предшествова-

ния и множеств самых левых и самых правых символов хорошо отра-

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

хождения с помощью ЭВМ целесообразно использовать следующие ре-

курсивные определения (символ ] означает существование, символ /\

- "И", символ \/ - "ИЛИ", символ ф - правило):

1а. Si = Sj ::= ] ф (ф: U ::= xSiSjy).

2а. Si < Sj ::= ] ф ((ф: U ::= xSiUly) /&bsol; Sj С L(Ul)).

3а. Si > Sj ::= ] ф ((ф: U ::= xUkSjy) /&bsol; Si С R(Uk)) &bsol;/

(] ф ((ф: U ::= xUkUly) /&bsol; Si С R(Uk)) /&bsol;

Sj С L(Ul)).

4a. L(U)= S | ]z (U ::= Sz) &bsol;/ ]z, U1 (U ::= U1z /&bsol; S С L(U1)).

5a. R(U)= S | ]z (U ::= zS) &bsol;/ ]z, U1 (U ::= zU1 /&bsol; 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 ├──────────┐

└──┬──┘ │

│ │

нет / &bsol; │

┌─────< 3 > │

│ &bsol; / │

│ │да │

│ ┌──┴──┐ │

│ │ 4 │ │

│ └──┬──┘ │

└───────┤ │<

┌──┴──┐ / &bsol; > ┌─────┐

│ 5 │ <13 >────┤ВЫХОД│

└──┬──┘ &bsol; / └─────┘

┌────────────┤ │

│ / &bsol; нет ┌──┴──┐

│ < 6 >────┐ │ 12 │

│ &bsol; / │ └──┬──┘

│ да│ │ │да

┌──┴──┐ ┌──┴──┐ │нет / &bsol;

│ 9 │ │ 7 │ ├────<11 >

└──┬──┘ └──┬──┘ │ &bsol; /

│ ├──────┘ │

│ < / &bsol; > ┌──┴──┐

└──────────< 8 >────────┤ 10 │

&bsol; / └─────┘

Рис. 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 ├─────────────────────────┐

└──┬──┘ │

│ │

┌─────┐ / &bsol; │

│ 4 │────< 3 >─────────────────┐ │

└─────┘ &bsol; / │ │

│ │ │

┌──┴──┐ │ │

│ 5 │ │ │

└──┬──┘ │ │

├────────┐ │ │

/ &bsol; да / &bsol; │ │ │

┌──────────< 7 >────< 6 > │ │ │

│ &bsol; / &bsol; / │ │ │

│ │нет │нет │ │ │

│┌─────┐ │ / &bsol; ┌──┴──┐ │ │

└┤ 8 ├─────┴──────< 9 >───┤ 10 │ │ │

└─────┘ &bsol; / < └─────┘ │ │

│> │ │

┌──┴──┐ │ │

│ 11 │ │ │

└──┬──┘ │ │

├────────┐ │ │

┌─────┐ да / &bsol; да / &bsol; │ │ │

│ 14 ├───<13 >────<12 > │ │ │

└──┬──┘ &bsol; / &bsol; / │ │ │

└────────┴────────┤ │ │ │

/ &bsol; ┌──┴──┐ │ │

<15 >───┤ 16 │ │ │

&bsol; / < └─────┘ │ │

│ │ ┌──┴──┐

┌──┴──┐ │ │ 29 │

│ 17 │ │ └──┬──┘

└──┬──┘ ┌──┴──┐ │

├─────────────┐ │ 30 │ / &bsol; > ┌─────┐

┌──┴──┐ │ └──┬──┘ <28 >───┤ВЫХОД│

│ 18 │ │ │ &bsol; / └─────┘

└──┬──┘ │ │ ┌───┘

│ │ │ │>

нет / &bsol; ┌──┴──┐ │ / &bsol;

┌──────────────────< 19 > │ 26 │ └──<27 >

│ &bsol; / └──┬──┘ < &bsol; /

│ │ │< │

│┌─────┐да / &bsol; да / &bsol; / &bsol; │

││ 22 ├───<21 >────<20 > <25 >────────┘

│└──┬──┘ &bsol; / &bsol; / &bsol; / >

│ │ │нет │ │

│ │ │ / &bsol; < ┌─────┐ │

└───┴────────┴──────<23 >───┤ 24 │ │

&bsol; / └─────┘ │

│> │

└─────────────┘

Рис. 3. Блок-схема алгоритма построения матрицы предшествования

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

Обозначения к алгоритму 1:

1. i = 1 (номер символа в алфавите языка).

2. j = 1.

3. ] P: U ::= x Si Sj - проверка наличия отношения = и

нахождение элемента матрицы с этим

отношением.

4. М [i,j]= =.

5. k = 1 (k,l - номера синтаксических правил).

6. Si C L (Uk) - находят элементы матрицы.

7. ] P: U ::= x Si Ux y имеющие отношение <.

8. М [i,j] = <.

9. k < j.

10. k = k + 1.

11. k = 1.

12. Si C L(Uk) находят элементы матрицы.

13. ] P: U ::= x Uk Sj y соответствующие отношению >

14. М [i,j] = >.

15. k < j.

16. k = k + 1.

17. k = 1.

18. l = 1.

19. Si C L(Uk) находят

20. Si C L(Ul) элементы матрицы,

21. ] P: U ::= x Uk Ul y соответствующие отношению >

22. М [i,j] = >.

23. l > j.

24. l = l + 1.

25. k < j.

26. k = k + 1.

27. j < I (I - мощность словаря языка).

28. i < I.

29. i = i + 1.

30. j = j + 1.

Блок 3 проверяет условие 1а и находит элементы матрицы, рав-

ные =, блок 4 записывает значение элемента в матрицу.

Блоки 6 и 7 проверяют условие 2а и находят элементы матрицы,

равные <.

Блок 8 записывает значение элемента в матрицу.

Блоки 12, 13, 19, 20 и 21 проверяют условия 3а и находят

элементы, равные >, блоки 14 и 22 записывают значения этих эле-

ментов в матрицу.

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

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

отношения предшествования между любыми двумя символами Si и Sj, а

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

ду ними существуют. Такая матрица не может использоваться в алго-

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

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

цы в каждом отдельном случае.

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

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

программ на языке программирования, т. е. эквивалентным преобра-