46023 (Проектирование трансляторов), страница 4

Осуществляем просмотр всех синтаксических правил, изменяя

индекс l и k (два индекса для того, чтобы различать нетерми-

нальные символы в левой (k) и правой (l) частях правила); индекс

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

алгоритма показана на рис. 2.

┌─────┐

│ 1 │

└──┬──┘

│

┌──┴──┐

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

└──┬──┘ │

│ │

нет / \ │

┌───── │

│ \ / │

│ │да │

│ ┌──┴──┐ │

│ │ 4 │ │

│ └──┬──┘ │

└───────┤ │<

┌──┴──┐ / \ > ┌─────┐

│ 5 │ ────┤ВЫХОД│

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

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

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

│ ────┐ │ 12 │

│ \ / │ └──┬──┘

│ да│ │ │да

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

│ 9 │ │ 7 │ ├────

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

│ ├──────┘ │

│ ┌──┴──┐

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

└─────┘ \ / │ │

│ │ │

┌──┴──┐ │ │

│ 5 │ │ │

└──┬──┘ │ │

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

/ \ да / \ │ │ │

┌────────────── │ │ │

│ \ / \ / │ │ │

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

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

└┤ 8 ├─────┴─────────┤ 10 │ │ │

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

│> │ │

┌──┴──┐ │ │

│ 11 │ │ │

└──┬──┘ │ │

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

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

│ 14 ├─────── │ │ │

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

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

/ \ ┌──┴──┐ │ │

───┤ 16 │ │ │

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

│ │ ┌──┴──┐

┌──┴──┐ │ │ 29 │

│ 17 │ │ └──┬──┘

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

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

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

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

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

│ │ │ │>

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

┌────────────────── │ 26 │ └──

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

│ │ │< │

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

││ 22 ├─────── ────────┘

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

│ │ │нет │ │

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

└───┴────────┴─────────┤ 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, т. е. су-

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

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

АНАЛИЗ КОНТЕКСТНО-ЗАВИСИМЫХ ЯЗЫКОВ

С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ

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

программирования, - это КС-грамматики (грамматики типа 2 в клас-

сификации Хомского). Однако описание языков программирования

грамматиками типа 1, т.е. контекстно-зависимыми (КЗ) грамматика-

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

сания языка, так и построение транслятора.

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

язык описан неукорачивающей грамматикой. Класс неукорачивающих

грамматик совпадает с классом КЗ-грамматик (грамматики типа 1 по

Хомскому).

Грамматика G является неукорачивающей, если для каждого

правила x ::= y С Ф выполняется условие │ x │<=│ y │, где │ x │

i i i i i

и │ y │ - число символов, входящих в строки x и y соответ-

i i i

ственно.

Множества самых левых Л(В) и самых правых П(В) символов сим-

вола В:

L(В) = { U/ ] (Be ::= Ux) С Ф \/ ] (Be ::= B1x) С Ф /\

/\ U С L(В1) };

R(В) = { U/ ] (eB ::= xU) С Ф \/ ] (eB ::= xB1) С Ф /\

/\ U С R(В1) };

где e, x - строки, возможно, пустые; В, В1, U С Vt U Vn.

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

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

при условии, что они использовались как начальные (конечные) сим-

волы в строках грамматических правил (x i ::= y i) С Ф.

Из определения L(В) непосредственно следует, что если a ->

b, т. е. a = f1 -> f2 -> ... -> fk = b (k>1) и a = Bx, то на-

чальные символы строк f i = Ux i (1

символ U участвовал в строках y правил вывода, принадлежат мно-

жеству L(В).

Аналогично из определения R(В) непосредственно следует, что

если a -> b, a = xB и, кроме того, a = f1 -> f2 -> ... -> fk =

= b (k>1), то конечные символы строк f i = x i U (1

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

множеству R(В).

Определим отношения предшествования для неукорачивающих

грамматик:

В = В ] ф (ф: g ::= xB B y) С Ф;

i j i j

B < B ] ф (ф: g ::= xB Ny) С Ф /\ B С Л(N);

i j i j

B > B ] ф (ф: g ::= xNB y) С Ф /\ B С П(N) \/

i j j i

\/ ] ф (ф: g ::= xNN y) С Ф /\ B С П(N) /\ B С Л(N );

1 i i 1

где x и y - строки, возможно, пустые, N, N , С V U V .

1 t n

Описание языка программирования неукорачивающими грамматика-

ми позволяет вводить символы языка типа IF, BEGIN, ELSE, FOR и

идентификаторы стандартных функций типа SIN, COS, EXP и т. п. в

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

чает анализ этих символов и ускоряет процесс трансляции.

Теперь рассмотрим алгоритм анализа входного текста, написан-

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

вования типа 1 по классификации Хомского. Блок-схема алгоритма

показана на рис. 4.

┌─────┐

│ 1 │

└──┬──┘

┌──────────────────────┼───────────────────┐

│ │ │ нет

│ ┌────┐ пусто / \ = ┌─────┐ / \

│ │ 15 ├───┬───────────┤ 3 ├────

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

│ │ │ │ ├─────────┐ │ да

│ │ │ │ │ │ │

│ │ │ │ пусто / \ = ┌──┴──┐ / \ ┌────┐

│ │ │ └───────────┤ 6 │ ─1──┤ 14 │

│ │ │ \ / └─────┘ \ / да └────┘

│ │ │ │< нет│

│ │ └──────────────┼───────────────────┘

│ │ / \

│ └──────────────

│ нет \ /

│ │ да

│ ┌──┴──┐

│ │ 8 │

│ └──┬──┘

│ ┌──┴──┐

│ │ 9 │

│ └──┬──┘

│ ├────────┐

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

└─┤ 11 ├─────────────────┤ 12 │

└────┘ = \ / =/= └─────┘

Рис.2

1. k,i=1 8. q := │Xn│

Мi=1 9. ГП

2. Ri ? Lk2 10. q=1

3. i=i+1 Ri=Lk3 11. i::=j

k=k+1 12. k=k-1

j=i Lk=n(q)

4. Ri=4 q=q-1

5. Rj=Ri 13. Y=R1...Ri

6. j=j-1 14. выход

7. Сущ. правило Y =Rj...Ri 15. обработка ошибки

При анализе входного текста используется стек R, работающий

по правилу FILO (first in, last out), чтение исходного текста

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

вверх.

Алгоритм в каждом текущем предложении Si выделяет самую ле-

вую строку, заключенную между отношениями > и <, и заменяет ее по

соответствующему правилу грамматики. Если грамматика предшество-

вания не имеет двух правил с одинаковыми строками y i, то данный

алгоритм для каждого предложения S L(G) всегда порождает одну и

ту же последовательность правил сворачивания. Для того, чтобы

строки сворачивания всегда были заключены между отношениями > и

<, в грамматиках анализируемых языков, как и в случае КС-грамма-

тик, вводятся ограничители начала и конца текста @.

В начале анализа строки в верхнюю ячейку стека R записыва-

ется первый символ программы, т. е. символ @. Индексам i (номер

символов стека R) и k (номер смвола входного текста) присваива-

ются начальные значения 1.

Блок 2. Проверяется отношение предшествования между верхним

символом стека Ri и очередным символом входного текста Lk . Если

между ними отношение вида _ (пусто), значит во входном тексте до-

пущена ошибка.

Блок 3 записывает в стек R очередной символ входного текста.

Блок 4 выделяет признак окончания текста Ri = @.

Блоки 5 и 6 определяют левую границу сворачиваемой строки.

Для этого проверяется отношение предшествования между каждой па-

рой символов R и R до выполнения условия R < R . В блоке

j-1 j j-1 j

5 не предусмотрен выход при выполнении условия R > R , так как

j-1 j

такое условие не может иметь место; вообще в процессе работы ал-

горитма в стеке R не может появиться пара символов с отношением

>, так как это исключает сам алгоритм.

Блок 7 производит поиск правила y=Rj,...,Ri по таблице грам-

матических правил и запоминает номер правила n, если оно найдено.

Блок 8 записывает в счетчик q число символов строки

Xn (q:=│Xn│).

Блок 9 производит переход на генерирующую подпрограмму.

Блок 10 проверяет длину строки Xn.

Блок 11 "выталкивает" символы Rj,..., Ri из стека R и запи-

сывает в него первый символ строки Xn, обозначенный на блок-схе-

ме Xn(1).

Блок 12 записывает все символы строки Xn, кроме первого, пе-

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

зовет переполнения массива L, так как по условию │Xn│ <= │Yn│.

Следовательно, число символов строки x не может быть больше чис-

ла символов строки y.

Блок 13 проверяет, выполняется ли правило R1,...,Ri. Если

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

входного текста закончен. Если такое правило не выполняется, зна-

чит данный текст из-за допущенной ошибки не может быть свернут.

Описания языков программирования КС- и даже неукорачивающи-

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

ных условий из синтаксиса в семантику. Например, в ФОРТРАНе при

анализе каждого идентификатора необходимо определить, является

ли его описание явным или неявным. Если описание явное, то опре-

деляется тип идентификатора.

Пример:

Имеется грамматика:

Vт = { А, B }, Vn = { S, D, H, B`, A` }

1: S -> A`SD

2: S -> A`B`A

3: AD -> HA

4: H -> D

5: B` -> B

6: BD -> BB`A

7: A` -> A

Эта грамматика порождает язык следующего вида:

(А**n)(B**n)(А**n) ; n - степень

L(S) =A`,A,H,D R(S)=A, D

L(B`)=B R(B`)=B

L(A`)=A,H,D R(A`)=A

L(H) =D R(H)=D, A

L(D) =" R(D)=A

L(B) =B R(B)=" (неопределено)

L(A) =H,D R(A)="

Матрица предшествования:

│

S │ = =

B`│ < < =

A`│ = = < < < <

H │ < < =

D │ > > > >

A │ > > > > > > >

B │ = > > > <

@ │ = < < < <

───┼────────────────────────

│ S B` A` H D A B @

Дерево вывода на основе матрицы и правил:

┌──────────────────────────┐

S+──┐ ┌─────────────А+ +D

│ │ │ \ /

│ S+─── +─────+B` H +────+3

│ │ │ │ │