Проектирование трансляторов

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

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


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

программирования, - это КС-грамматики (грамматики типа 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 = @.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: