Реферат: Проектирование трансляторов
ду ними существуют. Такая матрица не может использоваться в алго-
ритме анализа программы, так как не ясно, какое из отношений
предшествования между двумя символами брать для нахождения грани-
цы в каждом отдельном случае.
Но введением дополнительных нетерминальных символов и изме-
нением синтаксических правил, которые не меняют правил написания
программ на языке программирования, т. е. эквивалентным преобра-
зованием грамматик, можно добиться того, чтобы между каждой па-
рой символов существовало не более одного отношения предшествова-
ния.
Единого алгоритма, преобразующего любую КС-грамматику в
грамматику типа 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
АНАЛИЗ КОНТЕКСТНО-ЗАВИСИМЫХ ЯЗЫКОВ
С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ
Наиболее распространенные грамматики, описывающие языки
программирования, - это КС-грамматики (грамматики типа 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<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) С Ф /\ 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 ├───┬───────< 2 >────┤ 3 ├────< 4 >
│ └─┬─┬┘ │ \ / < └─────┘ \ /
│ │ │ │ ├─────────┐ │ да
│ │ │ │ │ │ │
│ │ │ │ пусто / \ = ┌──┴──┐ / \ ┌────┐
│ │ │ └───────< 5 >────┤ 6 │ < 13>─1──┤ 14 │
│ │ │ \ / └─────┘ \ / да └────┘
│ │ │ │< нет│
│ │ └──────────────┼───────────────────┘
│ │ / \
│ └──────────────< 7 >
│ нет \ /
│ │ да
│ ┌──┴──┐
│ │ 8 │
│ └──┬──┘
│ ┌──┴──┐
│ │ 9 │
│ └──┬──┘
│ ├────────┐
│ ┌────┐ / \ ┌─┴───┐
└─┤ 11 ├─────────────<10 >────┤ 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
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
