Проектирование трансляторов

│ │ └──┬──┘

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

├─────────────┐ │ 30 │ / > ┌─────┐

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

│ 18 │ │ │ / └─────┘

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

│ │ │ │>

нет / ┌──┴──┐ │ /

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

│ / └──┬──┘ < /

│ │ │< │

│┌─────┐да / да / / │

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

│└──┬──┘ / / / >

│ │ │нет │ │

│ │ │ / < ┌─────┐ │

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

/ └─────┘ │

│> │

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

Рис. 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, а

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

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

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

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

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

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

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

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

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

рой символов существовало не более одного отношения предшествова-

ния.

Единого алгоритма, преобразующего любую КС-грамматику в

грамматику типа 2 по классификации Хомского, отвечающую двум до-

полнительным ограничениям:

- однозначности отношений предшествования;

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

ми частями

НЕ СУЩЕСТВУЕТ.

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

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

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

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

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

КС-грамматику в грамматику типа 2 с учетом указанных ограничений:

1. Пусть между некоторыми двумя символами Si и Sj сущес-

твуют два отношения предшествования Si = Sj и Si < Sj.

Значит, существуют правила

Un ::= XnSiSjYn (n = 1,2,...,N); (1)

Um ::= ZmSiFkDm (m = 1,2,...,M; k = 1,2,...,K);

Fk -> SjQk; (2)

Введем новые нетерминальные символы Pn и синтаксические

правила Pn ::= SjYn (n = 1,2,...,N), заменяя все правила (1)

правилами Un ::= XnSiPn, при этом если исходная грамматика со-

держит правила вида Qn ::= SjYn, то заменяем их правилами Qn ::=

Pn.

1а. Если применение правила 1 не устраняет неоднозначности,

то вводятся нетерминальные символы Pn и Lm и синтаксические пра-

вила Pn ::= XnSi и Lm ::= ZmSi и все правила (1) заменяются на

Un ::= PnSjYn, а все правила (2) на правила Um ::= LmFkDm.

Если исходная грамматика содержит правила вида Qn ::= XnSi и

Tm ::= ZmSi, то заменяя их на правила Qn::=Pn и Tm::=Lm соответ-

ственно. Правила Pn и Lm надо выбирать так, чтобы Pn не совпада-

ло с Lm, т.е. чтобы ни для каких n и m Xn не совпадало с Zm.

Алгоритмы 1 и 1а устраняют отношения предшествования =. Это

видно из определений 1а-3а.

2. Пусть между некоторыми двумя символами Si и Sj сущес-

твуют два отношения предшествования Si = Sj и Si > Sj.

Значит, существуют правила

Un ::= XnSiSjYn (n = 1,2,...,N); (3)

Um ::= ZmFkSjDm или Um ::= ZmFkRlDm (4)

(m = 1,2,...,M; k = 1,2,...,K; l = 1,2,...,L);

Fk -> QkSi Rl -> SjTl.

Введем новые нетерминальные символы Pn и синтаксические пра-

вила Pn ::= XnSi (n = 1,2,...,N). Заменяем правила (3) правилами

Un ::= PnSjYn, устраняя тем самым отношения предшествования =.

Если исходная грамматика содержит правила вида Qn ::= XnSi, то

заменяем их правилами Qn ::= Pn.

3. Пусть между некоторыми двумя символами Si и Sj сущес-

твуют два отношения предшествования Si < Sj и Si > Sj, т. е. су-

ществуют правила

Un ::= XnSiFkYn (n = 1,2,...,N); (5)

Um ::= ZmRlSjDm или Um ::= ZmRlTpDm (6)

(m = 1,2,...,M; k = 1,2,...,K; l = 1,2,...,L;

p = 1,2,...,P);

Fk -> SjQk Rl -> HlSi, Tp -> SjWp.

Введем новые нетерминальные символы Pn и синтаксические пра-

вила Pn ::= XnSi (n = 1,2,...,N). Заменяем правила (5) правилами

Un ::= PnFkYn, сведя их к правилам (6) и устранив тем самым отно-

шения предшествования типа <. Если исходная грамматика содержит

правила вида Qn ::= XnSi, то заменяем их правилами Qn ::= Pn.

Справедлива теорема, согласно которой алгоритмы 1-3 измене-

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

писания и семантику программ на данном языке.

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

грамматику типа 2 только с одним дополнительным ограничением -

однозначность отношений предшествования (одинаковые правые части

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

алгоритм.

1. Составляются таблицы L(N) самых левых и R(N) - самых пра-

вых сиволов нетерминального символа N. Символ N C L(N) назовем

леворекурсивным, ссимвол N C R(N) - праворекурсивным.

2. Составляется матрица предшествования и определяются все

нарушения единственности отношений предшествования, и если их

нет, то производится остановка. Если они есть, то осуществляется

переход к 3.

3. К каждому праворекурсивному символу применяется процеду-

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

что каждый праворекурсивный символ N заменяется символом N1 и

вводится новое грамматическое правило N1::=N. Символ N не заме-

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

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

4. К каждому леворекурсивному символу применяется процедура

ограниченного левого расширения, которая заключается в том, что

каждый леворекурсивный символ N заменяется символом N2 и вводит-

ся новое грамматическое правило N2::=N. Символ N не заменяется

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

мым левым символом.

5. Если выполнен п. 3 или 4, то осуществляется переход к

п.1. Если нет, то осуществляется переход к п.6.

6. По матрице предшествования находятся пары символов X,Y и

P,Q такие, что X = Y и P = Q.

а. Если X C R(P) и выполняется одно из следующих условий: Q

и Y являются одними и теми же символами или Q C L(Y) или Y C L(Q)

или существует символ D такой, что D C (L(Q) / L(Y)), то к сим-

волу X применяется процедура ограниченного правого расширения.

б. Если Y C L(Q) а P и X являются одними и теми же символа-

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

расширения и осуществляется переход к п.1.

ЛЕКЦИЯ 5