Реферат: Проектирование трансляторов
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 >
│ └─┬─┬┘ │ \ / < └─────┘ \ /
│ │ │ │ ├─────────┐ │ да
Страницы: 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
