Смекни!
smekni.com

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

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

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

ния.

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

грамматику типа 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) /&bsol; 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) С Ф &bsol;/ ] (Be ::= B1x) С Ф /&bsol;

/&bsol; U С L(В1) };

R(В) = { U/ ] (eB ::= xU) С Ф &bsol;/ ] (eB ::= xB1) С Ф /&bsol;

/&bsol; 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<i<=k), в которых начальный

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

жеству L(В).

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

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

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

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

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

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

грамматик:

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

i j i j

B < B <--> ] ф (ф: g ::= xB Ny) С Ф /&bsol; B С Л(N);

i j i j

B > B <--> ] ф (ф: g ::= xNB y) С Ф /&bsol; B С П(N) &bsol;/

i j j i

&bsol;/ ] ф (ф: g ::= xNN y) С Ф /&bsol; B С П(N) /&bsol; 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 │

└──┬──┘

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

│ │ │ нет

│ ┌────┐ пусто / &bsol; = ┌─────┐ / &bsol;

│ │ 15 ├───┬───────< 2 >────┤ 3 ├────< 4 >

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

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

│ │ │ │ │ │ │

│ │ │ │ пусто / &bsol; = ┌──┴──┐ / &bsol; ┌────┐

│ │ │ └───────< 5 >────┤ 6 │ < 13>─1──┤ 14 │

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

│ │ │ │< нет│

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

│ │ / &bsol;

│ └──────────────< 7 >

│ нет &bsol; /

│ │ да

│ ┌──┴──┐

│ │ 8 │

│ └──┬──┘

│ ┌──┴──┐

│ │ 9 │

│ └──┬──┘

│ ├────────┐

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

└─┤ 11 ├─────────────<10 >────┤ 12 │

└────┘ = &bsol; / =/= └─────┘

Рис.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, работающий