Главная » Просмотр файлов » Теория синтаксического анализа, перевода и компиляции - Том 1

Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 15

Файл №943928 Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции) 15 страницаТеория синтаксического анализа, перевода и компиляции - Том 1 (943928) страница 152013-09-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Сразу не ясно, что должна существовать какая-то структура, помогающая осуществить перевод, но почти всегда той структурой, которую полезно придать входной программе, оказывается помеченное дерево. Не углубляясь в философию о том, почему это так, мы посвятим ббльшую часть книги алгоритмам эффективного построения подходящих деревьев для входных программ. 71 ГЛ.

1. Введвнис в компиляцию к ь языки пногнлмнгсговлния а+Ьвс 72 73 В качестве приме а т видные ст кт ы Р, р того, как для цепочек строятся древопрсдложения на с Ру УР Рассмотрим разбиение любого апглийског ннтаксические категории согласно грамматио ческим правилам. Например, предложение Т)че р)я )з 1п 1)че реп на ис. !.1. Н имеет грамматическую структуру, представ ленную в виде дерева такс р... Неконцевые вершины этого дерева ическнми категориями, а концевые р помечены синцевые вершины, т.

е. листья, <глгппгг Чг1ппа» <Сгхмлл ммгггмгво> <ьйагзнггпнг» <гпдгавмгмм» <аглгггр <гггппв> Г ~. р1о 1в <предлог> <глиогигугеппгсг ! )н <гпогдгпмггг» СВядИелгвгвг» ! ! )йв рен Рнс. 1,1, и ев .. Др овнднан структура английского предложении. в данном сл ° ' ерминальными, символами, которые помечены концевыми, или те м~ энном случае являются английскими словами. Подобным же об программи ования, же образом программу, написанную иа языке ненты в соответствн р, можно расчленить на синтаксическ е и компони с синтаксическими правилами, управляющими этим языком. Например, цепочка может иметь синтаксическ с~рук~уру з~да~ную дар~~вы на данного п е л роцесс нахождения синтаксической струк у р д ожения называют синтаксическим анали труктуры заразбором. Синтаксическая ст кт а и е айализом или ть взаимоотношения между различными частями предложения.

') И ) И .. е ких категорий <выражение>, <терьО ) Испольвов,. ие трех еинтвксичес ь вмег " одной категории <вь в и ь р вырвжение» вызвано желанием ур ~рифметичеекого вырвчнг гть синтаксической ст кт ы в ь должен иметь вго в виду, иначе ем сложными ивши послечу1оп е ример синтаксического внгливв ерифмети- Термином синтаксис языка будем называть отношение, связывающее с каждым предложением языка некоторую синтаксическую структуру. Тогда правильное предложение языка можно определить как цепочку символов, синтаксическая структура <гогоиеггг> Г <мевч» <мг ) ж <мюФвгмег» <ипмвгмгм» <Елимпгмгдг <гднмжмгггггЧЗ» Рнс.

1чп Дерево впнфмегического выраженнн. которой соответствует категории (предложение>. В следующей главе мы рассмотрим несколько методов строгого определения синтаксиса языка. Вторая часть перевода называется семантическим отображением; оно отображает структурированный вход в выход, который обычно является программой в машинном языке, Термином семангпика языка будем называть отображение, связывающее с синтаксической структурой каждой входной цепочки цепочку в некотороги языке (возможно, в том же самом), рассматриваемую как „смысл" первоначальной цепочки, Задание семантики языка — очень трудная проблема, пока еще далекая от полного решения, в особенности для естественных языков„например английского. Даже задание синтаксиса и семантики языка программирования — задача нетривиальная. Хотя универсально применимых методов нет, в теории языков есть два понятия, которые можно использовать для разработки части необходимого описания.

Первое из них-- понятие контекстно-свободной грамматики. В виде контекстно-свободной грамматики можно формализовать большую часть правил, предназначенных для описания синтаксической структуры. Более того, контекстно-свободная грамматика обеспечивает описание, достаточно точное для того, чтобы его можно было использовать как часть определения самого ГЛ.

!. ВВЕДЕНИЕ В КОМПИЛЯЦИЮ коыпилятора. Соответствующие понятия теории контекстно-свободных языков будут изложены в гл. 2. Второе понятие — схема синтаксически управляемого перевода, с помощью которой можно задавать отображения одного языка в другой. Схемы синтаксически управляемого перевода мы изучим довольно подробно в гл. 3 н 9, В этой книге предпринята попытка изложить аспекты теории языков и других формальных теорий, имеющие отношение к созданию языков программирования и компиляторов для них. Воздействие теории состоит в том, что а одних случаях она обеспечивает язык, в рамках которого можно говорить о проблемах, возникающих при построении компиляторов, а в других— единообразные и практически применимые решения некоторых из этих проблем. ».З.

ОВЗОР ПРОЦЕССА КОМПИЛЯЦИИ схему расы»»ре»»пя, по посредством которой а Алгол можно авеста новые тяпы за»»пых я поэме оп р ораторы. Более поздяяс результаты, касающаеся расшяВегб ейта языков, содержа»ся в работах Крястеясеяа я Шоу [1969) в ег рейта Ряемых я ы [1976). В качес»пе примера большого языка программяроаак», р есть средства расширения языка, можно прпвеста Алгол 68 [вав Вейягаардея, 19о69) 1.2. ОБЗОР ПРОЦЕССА КОМПИЛЯЦИИ Мы рассмотрим технические приемы и алгоритмы, применяемые при построении компиляторов и других средств обработки языков. Чтобы представить эти алгоритмы в надлежащей перспективе, мы набросаем в этом разделе общую картину процесса компиляции. Замечания по литературе Языки программирования высокого уровня появились в начале 1960-х годов.

В это время яычкслптельиые машпяы яуждалясь в арифметических операциях с плавающей точкой, так что первые языки программяроааяпя служили для представления этях операций. Первым кз глаяяых языков программяроаакяя был Фортрая, который поязплся а середине !960-х годов. Тогда же было создано несколько других алгебраяческях языков, по Фортрая кашел яаяболее ш»»рокое прях»енеяие. С тех пор появились сотая языков программяроааяяя высокого уровня. В кааге Саммета [1969) дается обзор мяогях языков, существовавших а середяае !960-годоя, Теория языков программирования к компиляторов значительно отставала от практккк.

Сильным стимулом для рззактяя теории формальных языков стало кспользозаяяе прп определеяяя скятакскса Алгола 60 [Наур, !968) того, что теперь пазыаают формой Бэкуса — Наура (БНФ) '). Соойщеяяе аб Алголе 60 вместе с рапякмя работамя Хомского [1969а, 1968) вызвала зуряое разэятяе теоряв формалькых языков з 1960-е годы. Ббльшзя часть яашей книги посзящеяа результатам теории языков, сзязаппым с построеяяем я пояямаяпем траяслятороа для языков программировая»»я.

Большяястзо ранних работ по теории языков касалось синтаксического аспекта определояяя языков. О»»ределеняе семантики языков — проблема гораздо более трудаая — прязлекло меньше ваямапяя я даже к моменту паласа. аяя данкой кяагя не было аполке решеяпым делом з). Хорошие антологии по вопросам формальяого задання семаптякк — [Стал, 1966) я [Экгелер, 1971).

Определепяе языка ПЛ/1, разработан»»ае в Венской лабораторяя фирмы Р!БА! [Лукаш я Вальк, 19Ь9), служит при»»ерем полностью формального подхода к определе»»яю большого языка программ»»розапяя. Очень интересным результатом а области языков программяроваяня было создаяке расширяемых языков, синтаксис ясеманткку которых можно мекать внутри»»раграммы. Одна яз самых раяякх я папболее вззесткых схем рзсшяреяяя языка — макроопределе»»ие (см., яа»»рямер, [МиоНлрой.

1960), [Лкаевзорт, !966) и [Чятэм, 1966)). Галлер я Перляс [!967) предложили ») То же самое чаще»»оправ»»лько, как отметял Кнут [1964), называют кормалькой формой Бэкуса.— Прим. лерез. з) С тех»»ор покаялась обшяй»»ая литература, посзящеякая вопросам формэльяой семактккя. Однако ях рассмотре»»яе выходит за рамки давкой каягя.— Прил. перев. 74 1.2.1. Основные чисты момпмпяторв Во многих компиляторах для многих языков программирования есть общие процессы. Попытаемся выделить сущность некоторых из этих процессов.

При этом мы постараемся устранить нз них по возможности все, что связано с конкретной реализацией и зависит от машины и операционной системы. Хотя соображения, относящиеся к реализации, важны (плохая реализация может испортить хороший алгоритм), нам кажется, что понимание фундаментальной природы проблемы существенно само по себе и позволяет применить технику, созданную для решения этой проблемы, к другим проблемам, по существу сходным с нею.

Исходная программа, написанная на некотором языке программирования, есть не что иное, как цепочка знаков. Компилятор в конечном итоге превращает эту цепочку знаков в цепочку битов — объектный код. В этом процессе часто можно выделить подпроцессы со следующими названиями: ([) Лексическии анализ (2) Работа с таблицами.

(3) Синтаксический анализ, или разбор, (4) Генерация кода, или трансляция в промежуточный код (например, язык ассемблера). (5) Оптимизация кода. (6) Генерация объектного кода (например, ассемблирование). В конкретных компиляторах порядок этих процессов может несколько отличаться от указанного, а некоторые из них могут Объединяться в одну фазу. Кроме того, никакая входная цепочка не должна нарушать работу компилятора, т.е. ондолжен обладать способностью реагировать на любую из них. Для входных цепочек, не являющихся синтаксически правильными програм- 75 Гл. 1.

звздв нче В «омпиляпию л. онзоп пгоцесса компиляции мами, компилятор должен выдать соответствующие сообщения об ошибках. Мы кратко опишем первые пять фаз компиляции. В реальном компиляторе они не обязательно разделены. Однако методически часто оказывается удобным расчленить компилятор иа эти фазы, чтобы изолировать проблемы, присущие именно этим частям процесса компиляции. 4.2.2. Лекснческкй анализ Первая фаза †лексическ анализ. Входом компилятора, а следовательно, н лексического анализатора, служит цепочка символов некоторого алфавита.

В версии языка ПЛ!1, предназначенной для публикаций, алфавит терминальных символов содержит 60 знаков: А В С ... Х 8 © 4~ 0 1 2 ... 9 пробел =+ — 7 ( ),;: ' 8с ~ > С р 5а В программе некоторые комбинации символов часто рассматриваются как единые объекты. Среди типичных примеров можно указать следующие: 1) В таких языках, как ПЛ/1, цепочка, состоящая из одного или более пробелов, обычно рассматривается как один пробел.

2) В некоторых языках есть ключевые слова, такие, как ВЕО!Х, ЕХП, ПОТО„1)О, !ХТЕОЕК и т. д., каждое из которых считается одним символом. 3) Каждая цепочка, представляющая числовую константу, рассматривается как один элемент текста. 4) Идентификаторы, используемые как имена переменных, функций, процедур, меток и т.

Характеристики

Тип файла
DJVU-файл
Размер
4,65 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6553
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее