ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ Рейн Т. С. Сущность трансляции. Компиляция и интерпретация

Для чего изучать предмет ? Практическое программирование. Понимание особенностей языков программирования, нюансов выполнения написанных на них программ, вытекающих из принятых традиционных способов организации трансляторов. Практическое программирование. Получение навыков разработки сложных алгоритмов и структур данных. Основным элементом программирования на этапе синтаксического анализа является рекурсия, а основной структурой данных - деревья. Практическое программирование. Умение использовать элементы трансляции при разработке прикладных программ, воспринимающих входные данные в « свободной » форме ; Общая " информационная " культура. Свойства и ограничения возможностей программ базируются на тех формальных системах, которые лежат в их основе. На разных этапах трансляции ( лексический, синтаксический и семантический анализ ) в нем рассматриваются различные формальные системы ( конечные автоматы, формальные грамматики, машины Тьюринга ). Трансляторы здесь являются хорошей иллюстрацией для сравнительного анализа их свойств и возможностей.

Где это применяется ? анализ сетевого трафика коммуникационным сервером. Для фильтрации сетевого трафика требовалось формулировать и периодически менять условия фильтрации сетевого трафика ( в зависимости от характеристик пакетов – адресов, содержимого, длины, значений служебных полей и т. п.). Условия фильтрации можно было задавать в виде выражений, операндами которых выступали характеристики пакетов. Далее выражения транслировались во внутреннюю форму ( древовидную структуру данных ), которая использовалась для тестирования трафика ; импорт данных биохимического анализа из текстовой формы в базу данных. Данные биохимических анализов были собраны в большом объеме и накоплены в текстовой форме в довольно свободном формате. Для приведения их к регулярному виду, необходимому для импорта в базу данных, потребовалось применить методы синтаксического анализа и описания форматов входных данных с помощью формальных грамматик ; исследование вирусного генома ( как известно, геном - это последовательность из 4 типов нуклеотидов, т. е. цепочка символов ) с использованием средств лексического анализа. компиляция выражения во внутреннюю форму с последующей интерпретацией для множества значений входного аргумента

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

Компиляция - преобразование объектов ( данных и операций над ними ) с входного языка в объекты на другом языке для всей программы в целом с последующим выполнением полученной программы в виде отдельного шага. Интерпретация - анализ отдельного объекта на входном языке с одновременным выполнением ( интерпретацией ). Основные определения

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

интерпретатор непосредственно выполняет действия, связанные с определением или преобразованием объектов программы, а компилятор - переводит их на другой ( не обязательно машинный ) язык. Основные определения

Компилятор

Интерпретатор

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

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

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

Для обеспечения совместимости и переносимости трансляторов на компьютеры с различной архитектурой или с различными операционными системами был разработан универсальный внутренний язык (P- код ). Для каждой такой архитектуры необходимо реализовать свой интерпретатор P- кода. При этом все разнообразие имеющихся компиляторов с языков высокого уровня на P- код может быть использовано без каких - либо изменений. язык программирования Java аналогично был разработан для обеспечения переносимости различных приложений в среде Internet. Основные определения. Примеры стандартизации

Фазы трансляции и выполнения программы

Если языки программирования имеет уже более или менее короткую историю развития, то сама технология подготовки программ, написанных на любом языке программирования, вообще сформировалась в начале 60 годов и с тех пор не претерпела существенных изменений.

Подготовка программы начинается с редактирования файла, содержащего текст этой программы, который имеет стандартное расширение для данного языка. Затем выполняется его трансляция, которая включает в себя несколько фаз : препроцессор, лексический анализ, синтаксический анализ, семантический анализ, генерация кода и его оптимизация. В результате трансляции получается объектный модуль - некий « полуфабрикат » готовой программы, который потом участвует в ее сборке. Подготовка программы

Сборка программы Файл объектного модуля имеет стандартное расширение obj. Компоновка ( сборка ) программы заключается в объединении одного или нескольких объектных модулей программы и объектных модулей, взятых из библиотечных файлов и содержащих стандартные функции и другие полезные вещи. В результате получается исполняемая программа в виде отдельного файла ( загрузочный модуль, программный файл ) со стандартным расширением -".exe", который затем загружается в память и выполняется.

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

Препроцессор. Примеры В языке Си директивы препроцессора оформлены отдельными строками программы, которые начинаются с символа "#". #define идентификатор строка _ текста #define SIZE 100 int A[SIZE]; for (i=0; i

Трансляция и ее фазы Трансляция начинается с лексического анализа программы. Лексика языка программирования - это правила « правописания слов » программы, таких как идентификаторы, константы, служебные слова, комментарии. Лексический анализ разбивает текст программы на указанные элементы. Особенность любой лексики - ее элементы представляют собой регулярные линейные последовательности символов. Например, Идентификатор - это произвольная последовательность букв, цифр и символа "_", начинающаяся с буквы или "_".

Синтаксис языка программирования Синтаксис языка программирования - это правила составления предложений языка из отдельных слов. Такими предложениями являются операции, операторы, определения функций и переменных. Особенностью синтаксиса является принцип вложенности ( рекурсивность ) правил построения предложений. Это значит, что элемент синтаксиса языка в своем определении прямо или косвенно в одной из его частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частным случаем которого является все тот же оператор цикла.

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

Генерация кода Генерация кода - это преобразование элементарных действий, полученных в результате лексического, синтаксического и семантического анализа программы, в некоторое внутреннее представление. Это могут быть коды команд, адреса и содержимое памяти данных, либо текст программы на языке Ассемблера, либо стандартизованный промежуточный код ( например, P- код ). В процессе генерации кода производится и его оптимизация.

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

Модульное программирование Модульное программирование используется в двух случаях : При написании модульной программы ; При использовании стандартных библиотечных функций.

Модульное программирование Библиотека объектных модулей - это файл ( библиотечный файл ), содержащий набор объектных модулей и собственный внутренний каталог. Объектные модули библиотеки извлекаются из нее целиком при наличии в них требуемых внешних функций и переменных и используются в процессе компоновки программы. Компоновка - это процесс сборки программы из объектных модулей, в котором производится их объединение в исполняемую программу и связывание вызовов внешних функций и их внутреннего представления ( кодов ), расположенных в различных объектных модулях. Источником объектного модуля может быть не только Си - программа, но и программа, написанная на любом другом языке программирования, например, на Ассемблере. Но в этом случае необходимы дополнительные соглашения по поводу « стыковки » вызовов функций и обращений к данным в различных языках.

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

Структура транслятора Трансляция представляет собой три последовательных фаз анализа программы, на каждой из которой из текста программы извлекается вся более « глубоко » скрытая информация о структуре и свойствах программы и ее объектах. Отдельные фазы трансляции могут быть связаны между собой различным образом, через данные в памяти или через файл, что не меняет сущности процесса : каждая фаза транслятора получает файл данных от предыдущей фазы, обрабатывает его, создает внутренние таблицы данных и по ним формирует выходной файл с данными для следующей фазы ; фазы трансляции вызывают одна другую в процессе обработки соответствующих языковых единиц. Поскольку синтаксический анализ является обычно центральным в такой структуре, вокруг него и группируются остальные фазы. из этой схемы выпадает только препроцессор, который обычно представляет собой независимую предварительную фазу трансляции.

Фазы трансляции. Лексический анализ На этом этапе исходный текст программы « нарезается » на лексемы – последовательности входных символов ( литер ), допускающие альтернативу ( выбор ), повторение и взаимное пересечение в процессе распознавания не более чем на заданную глубину. Элементами лексики являются идентификаторы, константы, строки, комментарии, одно - и многосимвольные знаки операций и т. п.. Механизм распознавания базируется на простых системах распознавания, имеющих всего одну единицу памяти ( текущее состояние ) и табличное описание правил поведения ( конечный автомат ). Результат классификации лексем ( классы лексем ) является входной информацией для синтаксического анализатора класс лексемы называется на входе синтаксического анализатора символом. Значения лексем поступают на вход семантического анализатора в виде первичного заполнения семантических таблиц.

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

Лексический и синтаксический анализ являются формализованными компонентами языка, как с точки зрения их описания ( конечные автоматы и формальные грамматики ), так и с точки зрения проектирования распознавателей для них ( для чего используются известные методы и алгоритмы ). Фазы трансляции

Заключительная фаза трансляции – семантический анализ, а также фаза синтеза – генерация кода ( оптимизация ) или интерпретация - привязаны к синтаксису ( и, соответственно, к синтаксическому анализатору ), поскольку интерпретируют « смысловое » содержание и правила преобразования ( или исполнения ) элементарных синтаксических единиц, выделенных синтаксическим анализатором. Фазы трансляции. Семантический анализ

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

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

Фазы трансляции Лексичекий анализ Синтаксический анализ Семантический анализ Генерация промежуточного кода Оптимизация кода Генерация кода Диспетчер таблиц символов Обработчик ошибок Исходная программа Целевая программа

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

Генерация кода генерация кода - последняя фаза трансляции. Результатом является либо ассемблерный модуль, либо объектный ( или загрузочный ) модуль. В процессе генерации кода могут выполняться некоторые локальные оптимизации, такие как распределение регистров, выбор длинных или коротких переходов, учет стоимости команд при выборе конкретной последовательности команд. Для генерации кода разработаны различные методы, такие как таблицы решений, сопоставление образцов, включающее динамическое программирование, различные синтаксические методы. те или иные фазы транслятора могут либо отсутствовать совсем, либо объединяться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева.

Связывание. Сравнительная характеристика языков программирования

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

Определения Временем связывания называется соответственно фаза подготовки программы к выполнению ( трансляция, компоновка, загрузка ), на которой производится это действие. Заметим, что различные характеристики одного и того же объекта ( например, переменной ) могут связываться с различными элементами архитектуры в разное время, то есть процесс связывания не является одномоментным. C вязывание - процесс установления соответствия между объектами и их свойствами в программе на формальном языке ( операции, операторы, данные ) и элементами архитектуры компьютера ( команды, адреса ).

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

Пример int a,b; … a+b … Рассмотрим простейший фрагмент программы, для которого перечислим более - менее полный перечень времен связывания его различных свойств с элементами архитектуры компьютера : int a,b; … a+b … 1. Тип переменных int - как способ определения целой переменной в машинном слове стандартной длины ( представление целого со знаком, дополнительный код ), связывается с аналогичной формой представления данных в компьютере при определении языка. Язык Си характерен тем, что базовые типы данных в нем полностью совпадают с соответствующими формами представления данных в компьютере. 2. Конкретная размерность переменной int определяется при реализации соответствующего компилятора. 3. Имя a может быть определено в конструкции вида #define a 0x11FF. В этом случае имя ( псевдо - переменная ) связывается со своим значением на первой фазе трансляции - в препроцессоре. 4. Если переменная определяется обычным способом в виде int a; то связывание переменной с соответствующим ей типом происходит во время трансляции ( на фазе семантического анализа ).

Пример int a,b; … a+b … 5. Если переменная определяется как внешняя ( глобальная, вне тела функции ), то смысл ее трансляции заключается в распределении под нее памяти в сегменте данных программы, который создается для текущего модуля ( файла ). Но при этом сама распределенной памяти к конкретной оперативной памяти осуществляется в несколько этапов : при трансляции переменная привязывается к некоторому относительному адресу в сегменте данных объектного модуля ( то есть ее размещение фиксируется только относительно начала модуля ) при компоновке ( связывании ) сегменты данных и команд различных объектных модулей объединяются в общий программный файл, представляющий собой образ памяти программы. В нем переменная получает уже относительный адрес от начала всей программы.

Пример int a,b; … a+b … при загрузке программы в некоторую область памяти ( например, в DOS или в режиме эмуляции DOS в WINDOWS) она может размещаться не с самого начала этой области. В этом случае осуществляется привязка адресов переменных, заданных в относительных адресах от начала программного модуля к адресам памяти с учетом перемещения программного модуля ( так называемый перемещающий загрузчик, которая имеет место для exe- файлов в DOS).

Пример int a,b; … a+b … 6. Если переменная определяется как автоматическая ( локальная внутри тела функции или блока ), то она размещается в стеке программы : во время трансляции определяется ее размерность и генерируются команды, которые резервируют под нее память в стеке в момент входа в тело функции ( блок ). То есть в процессе трансляции переменная связывается только с относительным адресом в стеке программы ; связывание локальным переменной с ее адресом в сегменте стека осуществляется при выполнении в момент входа в тело функции ( блок ). Благодаря такому способу связывания в рекурсивной функции существует столько « экземпляров » локальных переменных, сколько раз функция вызывает сама себя.

7. Тип операции + в конкретном выражении a+b определяется при трансляции в зависимости от типов операндов. В данном случае генерируется операция целого сложения. 8. С точки зрения времени связывания понятие инициализация внешних переменных можно определить как связывание переменных с их значениями в процессе трансляции программы (int a=10;) С этой точки зрения обычное присваивание можно рассматривать как связывание переменной с ее значением во время выполнения программы. Пример int a,b; … a+b …

Методы создания компиляторов

T- диаграммы T- диаграммы – удобный графический способ представления компиляторов

Объектная программа Последовательность абсолютных команд машинных команд Последовательность перемещаемых машинных команд Программа на языке ассемблера Программа на некотором другом языке

Трансляция в ассемблер

Методики создания компилятора Прямой Раскрутка Кросс - транслятор Виртуальная машина Компиляция " на лету "

Метод раскрутки Как избежать написания компилятора на ассемблере ? 1) K_A: PA 2) K_P: LA 3) Применим K_A к K_P K_A=K_A(K_P) LA Пример K_A: SA, S подмножество L K_L: LA K_A = K_A(K_L) Используем S чтобы K_S: LA K_A=K_A(K_S): LA

Кросс - транслятор Компилятор, который работает на одной платформе и создает код для другой платформы Более общий вопрос – создание переносимых компиляторов Пусть у нас есть два компьютера : компьютер M с языком ассемблера A и компьютер M_1 с языком ассемблера A_1. Пусть имеется компилятор K_A1: P A_1, а сам компьютер M по каким - то причинам не доступен либо пока еще не существует компилятор K_A: P A. Тогда компилятор K_A: L A. Можно использовать M_1 в качестве инструментальной машины и написать компилятор K_P: L A

Виртуальная машина

Компиляция « на лету »