RSS    

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

магазина (блок 2) и процесс продолжается до тех пор, пока не  бу-

дет выполнено условие Ri > Lk, т. е. не будет найден  самый  пра-

вый символ самой левой свертываемой части строки.

     Затем находится самый левый символ этой  свертываемой  части

строки. Для этого  проверяется  отношение  предшествования  между

каждой парой символов Rj-1 = Rj, записанных в магазине (блоки 5 и

6). Нарушение условия Ri = Rj означает,  что  свертываемая  часть

строки кончилась и последовательность символов Rj...Ri  есть  са-

мая левая свертываемая часть строки.

     У каждого нетерминального символа может быть несколько  са-

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

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

правила свертывания,  производится свертывание (блок 7) и управ-

ление передается на соответствующую семантическую  подпрограмму.

Семантическая подпрограмма генерирует программу на выходном язы-

ке, соответствующую данному синтаксическому правилу (блок 8).

     После того, как генерирование соответствующего куска  выход-

ной программы закончено, символы Rj...Ri "выталкиваются" из мага-

зина и в его верхнюю ячейку записывается символ u (блок 9).

     Процесс продолжается до тех пор, пока в верхней ячейке мага-

зина не будет обнаружен символ "@" (блок 3),  определяющий  конец

программы.

     Для анализа ошибок в алгоритм включены следующие блоки:

     Блок 11 проверяет, могут ли символы Rj и Lk стоять в  строке

рядом. Если в матрице предшествования (i,j)-ый элемент пуст (знак

_), то символы Si и Sj стоять рядом не могут и осуществляется пе-

реход к блоку 15. Иначе управление передается в блок 4.

     Блок 12 проверяет значение величины j: если j=1,  то  должно

производиться сравнение с символом "@", что по алгоритму  анализа

вообще быть не может. В этом случае переход к блоку 15. Если j не

равно 1, то переход к блоку 5.

     Блок 13 проверяет, есть ли правило с правой частью Rj...Ri в

грамматике языка. Если да,переход к блоку 7, иначе - к блоку 15.

     Блок 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, 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


Новости


Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

                   

Новости

© 2010.