Компоненты систем программирования (1119464), страница 2

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

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

Не подразумевается никакой необходимости в системепрограммирования, кодирование программ ведётсянепосредственно на машинном языке2. Программирование ведётся на языке, не совпадающемс машинным языком данной вычислительной системы,что требует наличия системы программирования, вкоторую должны быть включены компоненты,ответственные за преобразование исходной программык виду, в котором она может быть понята34вычислительной системойТипы трансляторов.Интерпретаторы и компиляторы• Преобразование исходных программ выполняетсясистемами программирования с помощьюкомпонентов, называемых трансляторами, то естьпрограммами, которые переводят исходнуюпрограмму, написанную на некотором исходном(входном) языке, в другую программу, эквивалентнуюпервой• Получающаяся программа тоже формулируется нанекотором языке, называемом объектным языком35Типы трансляторов.Интерпретаторы и компиляторы• Процесс перевода с исходного языка на объектныйязык охватывает сразу три программы и называетсятрансляцией:1.

При трансляции вычислительная система выполняет программутранслятора (транслирующая программа)2. Транслятор транслирует последовательность предложений входногоязыка, удовлетворяющую набору синтаксических и семантическихправил (транслируемая программа)3. Результатом работы транслятора является программа, построенная посинтаксическим правилам выходного языка с учётом семантикивыходного языка (результирующая программа)• Результирующая программа полностью эквивалентна36исходной программеАссемблеры• Для каждой вычислительной машины имеется языкпрограммирования, близкий к машинному языку,называемый автокодом или языком ассемблера• Программы, которые обрабатывают тексты на такихязыках, называются ассемблерами• Для языков ассемблера разработан стандарт“Standard for Microprocessor Assembly Language” IEEE694-1985, в котором указано, что они должныобрабатываться ассемблерами на основе принципа“один-в-один”37Компиляторы• Термин компилятор обычно используется вместотермина транслятор в тех случаях, когда исходнымязыком трансляции является язык программированиявысокого уровня (Паскаль или Си++), а объектнымязыком является автокод, язык ассемблера илимашинный язык некоторой вычислительной машины• Вычислительная система, для которой ведётсякомпиляция, называется целевой вычислительнойсистемой, в понятие о которой входят: аппаратура ЭВМ операционная система, работающая на этой аппаратуре набор динамических библиотек , которые необходимыдля выполнения объектной программы38Схема преобразования программкомпиляторамиИсходнаяпрограммаКомпиляторпрограмма № 1программа № 2Объектнаяпрограммапрограмма № 3Разрыв во времени и в пространствеВходные данныеВыполнениеРезультат39Схема получения результатапрограмм интерпретаторамиИсходнаяпрограммаИнтерпретаторпрограмма № 2Результатпрограмма № 1Входные данные40Интерпретаторы• Интерпретация выполняется программой,называемой интерпретатором• При интерпретации программы она размещается втой области памяти вычислительной машины, котораяпредназначена для исходных данных выполняемыхпрограмм, интерпретатору также необходимы те жеданные, что и при выполнении исходной программы• В отличие от компилятора и ассемблера,интерпретатор исходного языка не простообрабатывает текст исходной программы, авыполняет действия, которые этой программойпредписываются41Принципиальное отличиеинтерпретатора от компилятора• Интерпретатор не порождает объектнуюпрограмму, которая впоследствии должнавыполняться, а выполняет её сам• Итогом работы интерпретатора являетсярезультат, определяемый смыслом исходнойпрограммы, если исходная программаправильна синтаксически и семантически, либосообщение об ошибке, в противном случае42Смешанная стратегия трансляции• При работе интерпретаторов сначалапроизводится преобразование исходнойпрограммы в некоторое внутреннеепредставление, которое затем программноинтерпретируется• Именно поэтому интерпретаторы относятк трансляторам• Термин транслятор является самым общим иобозначает, как компиляторы и ассемблеры,так и интерпретаторы43Концептуальная схемакомпилятораИсходнаяпрограммаКомпилятор языкапрограммированияНачальные установкиТекстФазы анализаЛексический анализЛексемыАнализ илокализацияобнаруженныхошибокСинтаксический исемантический анализВнутреннее представлениеФаза оптимизацииВнутреннее представлениеСообщенияоб ошибкахРаспределение памятиВнутреннее представлениеРаспределение регистровОбъектнаяпрограммаТекст иликодТаблицыкомпилятора:Внутреннее представлениеГенерация команд и машиннозависимая оптимизацияФазы синтезаслужебныхидентификаторовконстантидентификаторов(имён)процедурблоковцикловмножестводругихтаблиц44Схема работы компилятора• Информационные таблицы Таблицы служебных идентификаторов Таблица констант Таблица имён Таблица процедур Таблица блоков Таблица циклов Множество других таблиц45Схема работы компилятора1.

Начальные установки2. Фазы анализа программ2.1. Лексический анализатор• Выделение и обработка лексем• Замена сложных конструкций• Диграфы (‘:=’, ‘**’, ‘->’, ‘&&’)и триграфы (‘??<’ ≡ ‘(’, ‘??>’ ≡ ‘)’, ‘??=’ ≡ ‘#’)• Замена знаков операций• (‘AND’, ‘not’, ‘mod’)• Макрорасширение• Исключение примечаний46Схема работы компилятора2. Фазы анализа программ2.2. Синтаксический и семантическийанализаторы• Проверка программ насинтаксическую и семантическуюправильность• Формирование внутреннегопредставления для каждой составнойчасти программы47Внутреннее представлениепрограмм• Внутреннее представление программы втрансляторе зависит от обработки, которойдолжна подвергнуться программа• В ассемблерах внутреннее представлениеблизко к окончательному виду программы• Внутреннее представления в компиляторах двусвязные или древовидные списки линейные последовательности операторов48Схема работы компилятора3.

Фазы оптимизации программСтратегии оптимизации• Повышение скорости работы• Уменьшение размеров программы“Машинно-зависимая” оптимизация“Машинно-независимая” оптимизацияНезависимость рассматривается в терминахнекоторого класса вычислительныхархитектур49Схема работы компилятора4. Фазы синтеза программ4.1. Распределение памяти и регистров4.2. Генерация команд и машиннозависимая оптимизация• В интерпретаторах фазы синтеза заменяютсяпрограммой, которая фактически выполняет(интерпретирует) внутреннее представлениеисходной программы50Однопроходный компилятор• Проход – процесс последовательного чтениякомпилятором данных из внешней памяти,их обработки и записи результата вовнешнюю память• Количество проходов в разных компиляторахможет исчисляться от одного до несколькихдесятков• Во время одного прохода может выполнятьсясразу несколько фаз компиляции, нонекоторые фазы компиляции могутвыполняться за несколько проходов51Однопроходный компиляторНачальные установкиИсходнаяпрограммаТекстОбращение залексемойСинтаксическийанализаторЛексемаЛексическийанализаторВозвратуправленияЗавершениеформированияпрограммыСинтаксическаяконструкцияСемантический анализатор,распределитель памяти,генератор командТекст или кодОбъектный модуль52IАнализирующаячастькомпилятораIIПромежуточноепредставлениеОптимизаторпрограммПромежуточноепредставлениеГенераторкодаОбъектнаяпрограммаИсходная программаОптимизация в компиляторахIIIИнформационныетаблицы53Выбор оптимизирующихпреобразований• Оптимизирующие преобразования должны бытьэквивалентными (сохраняющими семантику)• “Стоимость” преобразования должна бытьсопоставима с “затратами” на них• В результате преобразований характеристикипрограммы в среднем должны “улучшаться”• Основные виды оптимизации:• Машинно-независимая оптимизация выполняетсяна специально выделенной фазе компиляции (II)• Машинно-зависимая оптимизация проводитсяодновременно с генерацией объектной программы54или уже после неё (III)Выбор оптимизирующихпреобразований• Оптимизирующим преобразованиям подвергаетсявнутреннее представление программы:1.

Операции, необходимые для реализациивысокоуровневых операций становятся на языкахвнутреннего представления явно выраженными:оператор исходной программы s = s + a [i] * a [i]скрывает, что вычисление адресов для элементовa [i] содержит подвыражения sizeof (тип a [0]) * i2. Внутреннее представление относительнонезависимо от объектной машины, что делаетоптимизатор устойчивым к изменениям55Машинно-независимаяоптимизация линейных участковЛинейные участки –выполняемые по порядкупоследовательностиопераций, имеющие одинвход и один выход56Машинно-независимаяоптимизация линейных участков• вычисление выражений из констант на стадиикомпиляции• арифметические преобразования• устранение общих подвыражений (избыточныхвычислений)• удаление ненужных присваиваний и других операций• распространение копий значений• перестановка независимых смежных участковпрограмм• удаление недостижимых фрагментов программы• оптимизация вычисления логических выражений57Машинно-независимаяоптимизация линейных участков• вычисление выражений из констант на стадиикомпиляции (свёртка операций):• непосредственное использование константпрограммистом:A = sin (2 * 3.14 * B)• возникновение констант-операндов послемакрорасширений:#define Pi 3.1415926A = sin (2 * Pi * B)• компиляция сложных языковых конструкций:int a [10][10][10], b [10][10][10], c [10][10][10];a [3][4][i] = b [8][3][k] * c [3][2][j];a’ [((3 * 10) + 4) * 10 + i] := b’ [((8 * 10) + 3) * 10 + k] *c’ [((3 * 10) + 2) * 10 + j];Машинно-независимаяоптимизация линейных участков• арифметические преобразования• выражениеA=B*C+B*Dможет заменяться выражением A = B * (C + D)• замена операций на более “простые” и эффективные:x := y ** 2x := y * 2=>=>x := y * yx := y + yx := y * 2=>x := y << 1// это уже машинно-зависимое преобразование59Машинно-независимаяоптимизация линейных участков• устранение общих подвыражений (избыточныхвычислений):• операция линейного участка может оказатьсяизбыточной, если ранее на этом же линейномучастке уже выполнялась идентичная операция, иникакой операнд данной операции не былизменён в промежутке между двумя идентичнымиоперациями: int a [p][q][r], b [p][q][r], c [p][q][r];a [3][4][i] = b [8][3][k] * c [3][2][j];a’ [3 * q * r + 4 * r + i] :=b’ [8 * q * r + 3 * r + k] *60c’ [3 * q * r + 2 * r + j];Машинно-независимаяоптимизация линейных участков• удаление ненужных присваиваний и других операций• если между присваиваниями переменнойзначений (f = v1 и f = v2) не было ни одногооператора, в котором использовалось бы значениеv1, присваивание f = v1 является бесполезным иудаляется из программы без изменения её смысла• распространение копий значений• использование некоторых переменных заменяетсяиспользованием их копий (после присваиванияf = g вместо f используется переменная g, априсваивание удаляется из программы)61Машинно-независимаяоптимизация линейных участков• перестановка независимых смежных участковпрограмм• выражениеA = 2 * B * 3 *Cможно преобразовать в такое: A = (B * C) * (2 * 3)• непосредственное вычисление A = (B + C) + (D + E)требует сохранять промежуточный результатсложения B и C, после перестановки эта память ненужна: A = B + (C + (D + E)) или A = ((B + C) + D) + E• перестановка целочисленных операций ввыражении I/J*K может привести к вычислениювыражения 10*3/8 вместо вычисления 3/8*10 62Машинно-независимаяоптимизация линейных участков• удаление недостижимых фрагментов программы• оптимизация вычисления логических выражений• пример: операцию логического “ИЛИ” можно непроводить, если известно, что один из еёоперандов имеет значение “истина”• правильный заголовок цикла языка Сиwhile (! feof (F) && ((c = fgetc (F)) != ‘\0’)) { … }• ошибочный оператор языка Паскаль:if (tree <> nil) and (tree^.next <> nil) then begin … end63Машинно-независимаяоптимизация вызовов процедур• Прямая подстановка функций (inline) может привестик увеличению скорости работы программы• особенно важна для установочных процедур• Передача параметров через регистры процессораприводит к снижению времени работы программы• сильная зависимость от вычислительной машины• невозможность включать в общие библиотеки• трудности вычисления адресов параметров• В некоторых языках можно указывать, какиепеременные следует размещать на регистрах(например, с помощью ключевого слова register)64• Девиртуализация вызововМашинно-независимаяоптимизация цикловЦикл – любаяпоследовательностьучастков программы,которая может выполнятьсяповторно65Машинно-независимаяоптимизация циклов• вынесение инвариантных вычислений изтела цикла• замена операций с переменными цикла• слияние, расщепление и развёртываниециклов66Машинно-независимаяоптимизация циклов• вынесение инвариантных вычислений из тела цикла• цикл for (i = 0; i < limit – 2; i ++) A [i] = B * C * A [i];при условии, что B, C и limit не изменяются в телецикла, заменяется операциямиD = B * C; k = limit – 2;for (i = 0; i < k; i ++) A [i] = D * A [i];• векторная архитектура делает оптимизациюциклов машинно-зависимой: снижение временивыполнения программы можно получить, невынося вычисления из циклов, а внося их туда 67Машинно-независимаяоптимизация циклов• замена операций с переменными цикла• последовательность операторовS = 10; for (i = 0; i < N; i ++) A [i] = i * S;может быть заменена наS = 10; T = 0; for (i = 0; i < N; i ++) A [i] = T, T = T + S;• значение A [i] требует индуктивной переменной:изменение значения переменной цикла на 1приводит к изменению адреса элемента массивана sizeof (A[0]), значит, & A [i] ≡ A+sizeof (A [0]) * i68Машинно-независимаяоптимизация циклов• замена операций с переменными цикла• для цикла:S = 10; for (i = 0; i < N; i ++) R = R + F (S), S = S + 10;переменную цикла можно исключить:S = 10; M = S + N * 10;while (S < M) R = R + F (S), S = S + 10;• этим преобразованием за счёт введениядополнительной переменной M удаётся исключитьN операций сложения для переменной i69Машинно-независимаяоптимизация циклов• слияние цикловfor (i = 0; i < n; i ++) { S1; }for (i = 0; i < n; i ++) { S2; }for (i = 0; i < n; i ++) { S1; S2; }• расщепление цикловfor (i = 0; i < n; i ++) { if (x < y) { S1; } else { S2; } }if (x < y) for (i = 0; i < n; i ++) { S1; }elsefor (i = 0; i < n; i ++) { S2; }70Машинно-независимаяоптимизация циклов• развёртывание цикловfor (i = 0; i < n; i ++){ A [i] = B [i] * C [i]; }for (i = 0; i < n; i += 2) { A [i] = B [i] * C [i];A [i+1] = B [i+1] * C [i+1];}• для целочисленных переменных A и B циклfor (i = 1; i < 100; i ++) { … A = i * B; … }может быть преобразован к виду:for (i = 1; i < 100; i ++) { … A = A + B; … }71Машинно-зависимаяоптимизация1.

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

Список файлов лекций