Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 37
Текст из файла (страница 37)
По теореме 6.16 С вЂ яз простого предшестпоиапия. С) 8.3.3. Обзор содержания главы Отношения включения для классов языков, установленные в гл. 8, можно изобразить и виде рис. 8.7. Все включения собственные. Приведем примеры языков из классов, показанных на рис, 8.7: е.з. тиория языков простого првдшяатэовдния (а) (О" 1")г!~)1) — Е!(!).язык и и то же время язык опера- тарного предшествования, (Ь) (Ое)к ) и ) 1) 0 (02" ) л ) 1) — язык операторного предшествовання, ао пе 1Л.-язык, (с) (аО"! "0 (т, и)1) 0 (ЬО 1 "О")т, п)1) 0(аО"2"0")т, п)1)— язык простого предшествовання, не являю!цийся ни языком операторного предшествования, ни ЕЕ-языком, Ркс а 7. Подклассы класса де;ермипироваиоьш яааков.
(ОГ !2, 1! — языки, ыорожлаемые обратимымн грамматиками !2,0 предшестаоваш н, простые ССП— яаыкн, порождаемые простымл ССП-граммшккамм. ПП вЂ” «эмки прошого пред. шествовваие, ОГСП вЂ” нэнни, порождаемые обратииыми грамматиками слабого предшествованнп, ОП вЂ” ялики операторного ере!!шестаолаиия.! (д) (аО" НО )и, и) 1) 0 (ЬОлРО')т, л) 1) — Щ1) язык иота же время язык простого предшестноеания, но не операторного предшестаопания, !е) (аО"1')и) 1) 0(ЬО"!ш)л) 1) — ЕЕ(1) язык, ио неязык простого предшествования, (Й (аО"1") и ) 1) 0 (аО"2е") л ) 1) 0 (ЬО"1'")л да!) †детерминированный язык, не яаляюыийся ни языком простого пред- шествования, ни ЕЕ-языком, !8) (О" 1" (л) 1) 0 (О'!а" (а~) 1) — КС-язык, но не детерминн.
роаанпый. Гл 3 твОРия летеРминиРОВАннОГО РАзвОРл Дпказательства этих утверждений предлагаем в качестве упражнений. УПРАЖНЕНИЯ 8.3.1. Покажите, что грамматика языка ).о приведенная в теореме 8 20, является (.(.(2)-грамзеатггко(е Найдите для уп 1Л.(1).грамматику. *832. Докажите, что изык 1.,--. (О"а1п(п) !) 0 (О"Ь2" (л%1) не является 1Л.-языком.,указаниег Предположвте, что (., имеет (Л.(Ь)-грамматику в нормальной форме Грейбах.
*8.3.3. Покажите, что нзык Ь, из упр, 8.3 2 являстси языком операторного иредшестповапия. 8.3.4. Докажите, что алгоритм 2.11 (исключение псиных правил) сохраняет свойства (а) Операторного предшествования, (б) (ш, а)-предшестиоваиия, (в) (щ, л)-ОПК. 8.3.3. Докажите лемму 8.14. '8.3.6. Почему алгоритвг 8.6 не всегда превра!пает производьиуго грамматику прелшествования в граыматику простого пред- шествования? 8.3.7. Превратите следующую грамматику Операнзрно~ а пред- шествования в эквивалегщную грамматику простого предшсствонаиия: 5 И Ь !Ьеп 5з еще 5( И Ь !Ьеп 5( а 5, ИЬ!ЬЕН5, е)ее5( а 6.3.8.
Проведите доказательство в случае 2 из леммы 8.16. 8.3.9. Дайте алгоритм устранения из языка, порождаемого некоторой грамматикой, левого канпевого маркера. Покажите, ч~о если Ваш алгоритм применнть к грамматике, построенной алгоритмом 8.7, то полученная грамматика останетси обратимой грамматикой слабого предшествования. 8.3.10.
Покажите, что язык простого предшествовании 1. =-(ООЯ) "0 (п~ )1, ш~) !) и (ЬО 1 "О" (л ~) 1, пг~)1) не ивляется языком операторного предшествования Укпаакпгг Покажите, что во всякой грамматике для С будутодиовремепно выполняться отногпсния операторного предигествованип ! сд ! и 1)1. *8.3.11. Покажите, что изык 1.
иа упр 8.3.10 является яаыком простого предшесгвоиания. г эз злмечАния по литеРАТРРЕ *8.3.12. Докажите, что языки, описанные в равд. 8.3.3, обладают всеми приписанными им там свойствами. 8.3.13. Приведите дополнительные примеры языков, ирннадлежагпих равным классам, указанным иа рис. 8.7. 8.3.14. Обобщите теорему 8.18 тан, чтобы можно было пока. зать, что Язык ! г из этой теоРсмы не ЯвлиетсЯ обРагнмылз Язы. ком (1, Д)-предитествоваиия ни дли какого й. 8.3.13. Покажите, что грамматика Оз из алгоритма 8.7 прзвопокрыиаст грамматкку 0 из этого алгоритма. 8.3.16. Верно ли, что грамматика бо построенная в алто.
ритме 8.6, правопокрывает грамматику б из этого алгоритма, если 0 . приведенная грамматикар **8.3.!7. Пусть С вЂ” язык простого предшествоваиия (а"Оп'Ь"(и, и ) О) ц (Оа"!а'с (г', и ) О) Покажите, что для !. не существует анализатора простого предгиес~вования, сообщающего об ошибке сразу после прочтения символа 1 из входной пеночки вяла а" 1а'Ь (см. упр. 7.3.6). Отдрышая проблема 8.3.!8. Каким образом класс обратимых языков (1, й)-предгпествования, Ь ) 1, связан с классами, показанными на рнс 8.77 Читатель должен обратить внимание на упр. 8,3.14, Замечания по литературе Строгое влдм ~ и м жесзвв языков простого предшссгвовзчня в мзсже. ство дезсрмжшровзнныд КС языкон, з также м. ожес вз языков опервшрн го иредшесгв взи я в ожесгжз явюеов врсстого прсдиксгзовзни» впервые докззянп Фнпгером !!9а9!.
з ~ галь пвгввадл в пеоцвссе компиляции 9 ПЕРЕВОД И ГЕНЕРАЦИЯ КОДА Разработчику компилятора обычна предоставляется неполное описание языка, для которого он должен построить компилятор. Вбльшую часть синтаксиса языка можно представить в виде КС-грамматнкгь В то жевремя точно описать объектный код, который необходимо сгенерировать для произвольной входной программы, значительно труднее. Широко применимые формальные методы определения семантикн языка программирования до сих пор остаются предметом исследований. В настоящей главе мы введем формальные соглашения, кото. рые можно использовать для точного описания переводов, выполняемых в компиляторе, и дадим примеры таких формализмов.
Затем разработаем методы машинного выполнения переводов, определяемых этими формачизмамн. Р.1. РОЛЬ ПЕРЕВОДА В ПРОЦЕССЕ КОМПИЛЯЦИИ Напомним, что в гл, ! компилятор определялся как транс- лятор, отображающий цепочки в цепочки. Входом компилятора служит цепочка символов, составляклцая исходную программу, Выход компилятора, называемый объектной программой, есть также цепочка символов.
Объектная программа может быть ((] последовательностью абсолютных машинных команд, (2) последовательностью перемещаел~ых машинных команд, (3) программой на языке ассемблера, (4) программой на нексггором другом языке. Обсудим вкратце характеристики каждой из приведенных форм объектной программы. (!) Метод отображения исходной программы в абсолкпиую программу на машинном языке, кьпоргю можно непосредственно выполнить, является одним ив способов, позволяющих добиться очень быстров компиляции Примером компилятора такого рода служит )ЧАТГОК. Такой тнп коыпиляции больше всего подходит 196 для небольших программ, не использующих независимо компилируемых подпрограмм.
(2) Перемещаемая машинная команда представляет собой команду, в которой участвуют адреса ячеек памяти относительна некоторого ппдвижного начала. Объектная программа в форме последовательности переме1паемых машинных команд обычно называетси перемещаемым объектным сегментом. Этот сегмент ыожст быть свяван с другими обьектными сегментамп, такими, как независимо компилируемые подпрограммы польвователя, программы ввода- вывода и библиотечные функции; при этом получаетсп единый перемещаемый объектный сегмент, часто называемый модулам загрузки, Программа, собирающая модуль загрузки иэ совок! п ности сегментов, называется дедакгиором ггяэгй.
Модуль загрузки затем размещается в памяти программой, назьшаемой загрузчикам, которая превращает перемещае. мыс адреса в абсолютные. После этого объектная программа готова к выполненшо. Хотя редактирование связей и загрузка требуют времени, большинство промышленных компиляторов вырабатывает пере. мещаемые сегменты, чтобы получить возможность гибко использовать больпше библиотечные подпрограммы и независимо компилируемые подпрограммы. (3) Подход, при котором выполняется перевод исходной программы в программ> на языке ассемблера, которая в свою очередь обрабатывается ассемблером, упрощает конструирование компилятора.
Однако общее время, требуемое для того, чтобы выработать программу на машинном языке, достагочво велико, так как обработка выхода такого компилятора ассемблером может занвмать столько же времеки, сколько и сама компиляция. (4) Некоторые компиляторы (например, Скидал) преобразуют исходную программу в другую програыму на специальном внутреннем языке. Эга внутренняя программа затем ныполняется путем моделирования последовательности команд внутренней программы Такие компиляторы обычно называются интерлргтата. рамп. Ыы можем, однако, расслгатривать как пример собственно компиляции только отображение исходной программы во внутренний язык.
В этой главе выходу компилятора не будет приписываться никакого фиксированного формата, хотя во многих примерах в качестве объектного кода берется язык ассемблера. В настоящем разделе мы рассмотрим в общих чертах процесс компиляции и основные методы преобразования исходной программы в объектный код. ит Гл. т ОеРевОд и ГенеРАция кодА ЭЛ. РОЛЬ ПЕРСВОДА В ПРОЦЕССЕ КОМПИЛЯЦИИ 1.1.1. Фазы иомпипяцми В гл. 1 мы видели, что компилятор можно расчленить на несколько промежуточных трансляторов, каждый из которых выполняе~ перевод некоторого представления исходной программы, пока, наконец, не будет получена объектная программа.
Каждый промежуточный транслятор можно считать преобразованием, определяющем одну фазу компиляции, а композиция всех фаз дает компиляцию э целом. Выбор того, чтб назвать фазой, достаточно произволен Удобно считать основными фазами компиляпин лексический апа. лиз, синтаксический апализ и гснерацию коЛа. Тем не менее во многих развитых компиляторах эти фазы часто разбиваются на несколько подфаз; могуг также быть и другие фазы (например, оптимизация кола). Входом компилятора служит цепочка символов. Лексический анализатор — это первая фаза компиляции.
Оп отображает свай вход в цепочку, состоящую из лексем и элементов таблицы имен. В ходе лексического анализа размеры первоначальной, исходной проГраммы несколько уменьшаются, так как идепти. фикаторы заменяются лексемами, а нснужцые пробелы и коимснтарии выбрасываются. После лексического анализа перерабатываемая информация остаегся по существу цепочкой, но некоторые части этой цепочки являются указателями на янформацию в таблице имен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
