Проектирование трансляторов
С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ
Наиболее распространенные грамматики, описывающие языки
программирования, - это КС-грамматики (грамматики типа 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 ├───┬───────< 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 = @.