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

Блок 14 проверяет, есть ли правило Rj...Ri. Если да, то ал-

горитм анализа и свертывания входного текста закончен (переход к

блоку 10); иначе в тексте есть ошибка, из-за которой он не может

быть свернут (переход к блоку 15).

Блок 15 выводит сообщение об ошибке и переходит к анализу

следующего оператора.

Таким образом, сложный анализ входного текста, написанного

на входном языке, реализуется простым алгоритмом.


Требование единственности отношений предшествования вызы-

вает необходимость перестройки грамматики языка. Устранение этой

неоднозначности иногда становится достаточно трудоемкой задачей.

Мак-Киман разработал алгоритм анализа входного текста, который не

предъявляет к грамматике языка требования однозначности отноше-

ний предшествования.

Для определения границ сворачиваемой строки он использует не

одну, а две матрицы: первую - для нахождения самого правого сим-

вола строки - назовем М1, и вторую - для нахождения самого лево-

го символа строки - М2. В М1 заносятся следующие отношения пред-

шествования: <= (< или =), > и >=< (последнее означает > и либо

=, либо <). B M2 заносятся отношения предшествования => (> или =),

< и <=> (последнее означает < и либо =, либо >).


При поиске самого правого символа безразлино, какое от ноше-

ние предшествование <, = или <= находиться между двумя анализи-

руемыми символами. Аналогично при поиске самого левого символа

безразлично, какое отношение предшествование >, = или => находит-

ся между двумя анализируемыми символами. Поэтому эти отношения в

соответствующих матрицах не различаются. В тех случаях, когда

между парой символов существуеют отношения >=<, при поиске гра-

ниц сворачиваемой строки необходима дополнительная информация.

Эта информация задается в виде логических функций трех аргументов.

При поиске самого правого символа сворачиваемой строки с

помощью матрицы М1 используется функция


| истина, если Si > Lk;

Р1(Si-1, Si, Lk) = <

| ложь в противном случае.


Функция Р1 истинна, если в контексте Si-1SiLk символ Si яв-

ляется самым правым символом сворачиваемой строки ...Si-1Si.

Здесь Si - символ, хранящийся в верхней ячейке стека, Si-1 -сим-

вол, хранящийся в следующейся ячейке стека и Lk - очередной сим-

вол анализируемого текста.

Таким образом, каждой паре символов, у которых в М1 записа-

но отношение >=<, ставится в соответствие несколько функций Р1,

позволяющих анализировать уже не пару, а тройку символов для оп-

ределение правил границы сворачиваемой строки. Но эта тройка уже

должна быть определена так, чтобы ответ был однозначный.

Аналогично при поиске самого левого символа сворачиваемой

строки с помощью матрицы М2 используется функция


| истина, если Sj-1 < Sj;

Р2(Sj-1, Sj, Sj+1) = <

| ложь в противном случае.


B контексте Sj-1SiSj+1 символ Sj является самым левым симво-

лом сворачиваемой строки SjSj+1... . Здесь Sj-1, Sj, Sj+1 - сим-

волы, хранящийся в j-1, j и j+1 ячейках стека.

Каждой паре символов, у которых в М2 записано отношение <=>,

ставится в соответствие несколько функций Р2, позволяющих, как и

функции Р1, анализировать не пару, а тройку символов. Но эта

тройка уже должна быть определена так, чтобы ответ был однознач-

ный.


Блок-схема алгоритма анализа входного текста с помощью мат-

риц предшествования и функций Р1 и Р2 приведена на рис. 2. Буквы

i и j обозначают номера ячеек магазина, k - номер очередного сим-

вола входного текта, Ri и Rj- символы, находящиеся в i-х и j-х

ячейках магазина, Lk - k-й символ входного текста. В начале ана-

лиза строки в верхнюю ячейку магазина записывается первый символ

программы, т.е. символ "@" (блок 1). Затем производится проверка

на конец программы (блок 3). Если Lk = @, то выполнение програм-

мы окончено и осуществляется переход к блоку 14. Если Lk не сов-

падает @, осуществляется переход к блоку 4.

Производится поиск самого правого символа самой левой свер-

тываемой строки. Для этого по М1 проверяется отношение предшес-

твования между символами Lk и Ri (блок 4). Если это отношение

равно <=, т.е. Ri не является самым правым символом сворачивае-

мой строки, то производится запись очередного символа в магазин

(блок 2).

Если между символами Ri и Lk существует отношение <=>, то

блоком 5 проверяется функция Р1 для двух верхних символов магази-

на и очередного символа входного текста. При значении функции Р1

- ложь (на рис. 2), это значение обозначено Л, т.е. если Ri не

является самым правым символом, осуществляется переход к блоку 2.

Если значение Р1 - истина (И), т.е. Ri - самый правый символ

строки, то осуществляется переход к блоку 6.

Блоком 6 начинается поиск самого левого символа свертывае-

мой строки; j присваивается значение i. По М2 определяется отно-

шение между символами Rj-1 и Rj (блок 7). Если отношение есть =>,

т.е. Rj не является самым левым символом свертываемой строки, то

j := j-1 (блок 8) и определяется отношение между следующей парой

символов. Если отношение есть <, т.е. Rj-1 является самым левым

символом, осуществляется переход к блоку 10. Блок 10 введен для

того, чтобы в блоке 11 свертывание всегда происходило от j-го до

i-го элемента.


Если между символами Rj-1 и Rj отношение >=<, то проверяет-

ся функция Р2 для трех символов, находящихся в j-1, j и j+1-й

ячейках магазина. Если значение Р2 - Л (Rj не является самым ле-

вым символом), осуществляется переход к блоку 8; если значение Р2

- И (Rj является самым левым символом), то осуществляется пере-

ход к блоку 11.

Блоки 11,12 и 13 производят свертывание, переход на генери-

рующую подпрограмму и запись вновь полученного нетерминального

символа U в верхнюю ячейку магазина. Они в точности соответ-

ствуют блокам 7, 8, 9 на рис. 1. На рис. 1. не показаны блоки

анализа синтаксических ошибок. Они аналогичны соответствующим

блокам на рис. 2.

Метод Мак-Кимана освобождает от ограничения однозначности

отношений предшествования, накладываемого методом Вирта, но он

требует, естественно, больших объeмов памяти для записи матриц и

функции. В трансляторе с одной из версий языка PL/1 для машин се-

рии IBM-360 М1 составила 90x45 элементов, М2-90x90. Каждый эле-

мент занимает 2 бита. Число функций Р1 и Р2 приближалось к 450.

ЛЕКЦИЯ 4


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

И ПРЕОБРАЗОВАНИЕ ГРАММАТИК


Рассмотрим алгоритм составления матрицы предшествования. Для

этого дадим формальные определения отношений предшествования и

множество самых левых и самых правых символов.


1. Для любой упорядоченной пары символов (Si, Sj) Si = Sj

тогда и только тогда, когда существует синтаксическое правило ти-

па U::=xSiSjy для некоторого символа U и некоторых строк x и y.


2. Для любой упорядоченной пары символов (Si,Sj) Si < Sj

тогда и только тогда, когда существует синтаксическое правило ти-

па U::= xSiUly для некоторых U, Ul, x, y и порождение Ul -> Sjz

для некоторой строки z.


3. Для любой упорядоченной пары символов (Si, Sj) Si > Sj

тогда и только тогда, когда:

a) существует синтаксическое правило типа U ::= xUkSjy для

некоторых U, Uk, x, y и порождение Uk -> zSi для некоторой стро-

ки z или

б) существует синтаксическое правило типа U ::= xUkUly для

некоторых U, Uk, Ul, x, y и порождения Uk -> zSi, Ul -> Sjw для

некоторых строк z и w.

Строки x,y,z,w могут быть пустыми.


4. В множество L(U) самых левых символов нетерминального

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


U -> Sz,


где z - некоторая строка (возможно, пустая).

Это определения может быть записано в виде:


Л(U) = { S | существует строка z, такая, что (U -> Sz) }.


5. В множество R(U) самых правых символов нетерминального

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


U -> zS,


где z - некоторая строка (возможно, пустая).


Это определения может быть записано в виде:


R(U) = { S | существует строка z, такая, что (U -> zS) }.


Данные выше формальные определения отношений предшествова-

ния и множеств самых левых и самых правых символов хорошо отра-

жают содержательную сторону определяемых понятий, но для их на-

хождения с помощью ЭВМ целесообразно использовать следующие ре-

курсивные определения (символ ] означает существование, символ /

- "И", символ / - "ИЛИ", символ ф - правило):


1а. Si = Sj ::= ] ф (ф: U ::= xSiSjy).

2а. Si < Sj ::= ] ф ((ф: U ::= xSiUly) / Sj С L(Ul)).

3а. Si > Sj ::= ] ф ((ф: U ::= xUkSjy) / Si С R(Uk)) /

(] ф ((ф: U ::= xUkUly) / Si С R(Uk)) /

Sj С L(Ul)).

4a. L(U)= S | ]z (U ::= Sz) / ]z, U1 (U ::= U1z / S С L(U1)).


5a. R(U)= S | ]z (U ::= zS) / ]z, U1 (U ::= zU1 / S С R(U1)).


Всюду ф C P.


Определения 1а-5а дают эффективный алгоритм нахождения мно-

жеств L(U) и R(U) и отношений предшествования.

Рассмотрим алгоритм нахождение множества самых левых симво-

лов для символов, принадлежащих Vn.

Шаг 1: проверяем, является ли i-ый символ самым левым в

l-том синтаксическом правиле. Если да, то записываем Si в табли-

цу самых левых символов нетерминального символа Ul (при условии,

что он туда еще не записан);

Шаг 2: проверяем, не является ли символ Ul, для которого Si

- самый левый, самым левым символом Uk. Если да, то записываем

символы Ul и Si в таблицу самых левых символов нетерминального

символа Uk (при условии, что они туда еще не записаны).

Осуществляем просмотр всех синтаксических правил, изменяя

индекс l и k (два индекса для того, чтобы различать нетерми-

нальные символы в левой (k) и правой (l) частях правила); индекс

i указывает номер символа в синтаксическом правиле. Блок-схема

алгоритма показана на рис. 2.


┌─────┐

│ 1 │

└──┬──┘

┌──┴──┐

│ 2 ├──────────┐

└──┬──┘ │

│ │

нет / │

┌─────< 3 > │

│ / │

│ │да │

│ ┌──┴──┐ │

│ │ 4 │ │

│ └──┬──┘ │

└───────┤ │<

┌──┴──┐ / > ┌─────┐

│ 5 │ <13>────┤ВЫХОД│

└──┬──┘ / └─────┘

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

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

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

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