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

                   │  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 ::=

Страницы: 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