Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 15
Текст из файла (страница 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) Идентификаторы, используемые как имена переменных, функций, процедур, меток и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
