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

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

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

     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 >─────────────────┐        │

         └─────┘     \ /                  │        │

                      │                   │        │

                   ┌──┴──┐                │        │

                   │  5  │                │        │

                   └──┬──┘                │        │

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

            / \  да  / \       │          │        │

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

│           \ /      \ /       │          │        │

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

│┌─────┐     │       / \    ┌──┴──┐       │        │

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

 └─────┘             \ /  < └─────┘       │        │

                      │>                  │        │

                   ┌──┴──┐                │        │

                   │ 11  │                │        │

                   └──┬──┘                │        │

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

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

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

 └──┬──┘    \ /      \ /       │          │        │

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

                     / \    ┌──┴──┐       │        │

                    <15 >───┤ 16  │       │        │

                     \ /  < └─────┘       │        │

                      │                   │     ┌──┴──┐

                   ┌──┴──┐                │     │ 29  │

                   │ 17  │                │     └──┬──┘

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

                      ├─────────────┐  │ 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.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16