Процесс трансляции. Этапы, фазы и проходы.

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

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

 Трансляция программы производится в несколько этапов.

 1. Лексический анализ.

 2. Синтаксический анализ.

 3. Генерация кода.

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

 Итак, файл исходной программы подготовлен, после чего мы некоторым образом передаем его транслятору для обработки. Происходить это может двумя способами: посредством командной строки (возможно, с использованием утилиты make.exe) либо в интегрированной среде. По сути, для транслятора оба эти способа одинаковы, так как ядро транслятора для обработки этих файлов будет одно. Единственное отличие в том, что в первом случае программист явно формирует все необходимые ключи и параметры командной строки, а во втором случае он это делает неявно, путем настройки параметров интегрированной среды.

 

Трансляция и ее фазы

 

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

 

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

 

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

 

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

Вот список всех проходов транслятора и их исходных файлов. Также включено описание того, как запросить отладочные дампы при помощи опции " -d ".

 Синтаксический анализ. Этот проход читает весь текст определения функции и строит частичные синтаксические деревья. Это и генерация RTL не являются больше отдельными проходами (как раньше), но проще думать о них как об отдельных. Представление дерева не следует полностью синтаксису C, потому что оно предназначено поддерживать также другие языки. Специфический для языка анализ типа данных также выполнен в этом проходе, и к каждому узлу дерева, который представляет выражение, присоединен тип его данных. Переменные представляются как узлы-объявления. Вычисление констант и некоторые арифметические упрощения также выполняются во время этого прохода. Языконезависимые исходные файлы для синтаксического анализа - "stor-layout.c", "fold-const.c", и "tree.c". Есть также файлы заголовка "tree.h" и "tree.def", которые определяют формат представления дерева. Исходные файлы для анализа C - "c-parse.in", "c-decl.c", "c-typeck.c", "c-aux-info.c", "c-convert.c" и "c-lang.c", а также файлы заголовка "c-lex.h", и "c-tree.h". Исходные файлы для анализа C ++ - "cp-parse.y", "cp-class.c", "cp-cvt.c", "cp-decl.c", "cp-decl2.c", "cp-dem.c", "cp-except.c", "cp-expr.c", "cp-init.c", "cp-lex.c", "cp-method.c", "cp-ptree.c", "cp-search.c", "cp-tree.c", "cp-type2.c", и "cp-typeck.c", а также файлы заголовка "cp-tree.def", "cp-tree.h", и "cp-decl.h". Специальные исходные файлы для синтаксического анализа Objective C "objc-parse.y", "objc-actions.c", "objc-tree.def", и "objc-actions.h". Для этого используются также некоторые специфические файлы C. Файл "c-common.c" также используется для всех вышеуказанных языков.

 Генерация RTL. Это преобразование синтаксического дерева в код RTL. Фактически она выполняется пооператорно во время синтаксического анализа, но для большинства целей о ней можно думать как об отдельном проходе. Именно здесь находится большая часть кода, зависящего от машины, так для cтратегий часто бывает необходимо применять их только тогда, когда доступны определенные стандартные виды команд. Цель названных образцов команд - обеспечить эту информацию для прохода генерации RTL. В этом проходе выполнена оптимизация для "if"-условий, являющихся сравнениями, булевыми операциями или условными выражениями. "Хвостовая" рекурсия также распознается в это время. Принимаются решения о том, как лучше всего упорядочивать циклы и как выводить операторы "switch". Исходные файлы для генерации RTL включают "stmt.c", "calls.c", "expr.c", "explow.c", "expmed.c", "function.c", "optabs.c" и "emit-rtl.c". Также в этом проходе используется файл "insn-emit.c", сгенерированный из машинного описания программой "genemit". Файл заголовка "expr.h" используется для связи внутри этого прохода. Файлы заголовка "insn-flags.h" и "insn-codes.h", сгенерированные из машинного описания программами " genflags " и " gencodes ", сообщают этому проходу, какие стандартные имена доступны для использования и какие образцы соответствуют им. Кроме вывода информации об отладке, ни один из следующих проходов не обращается к представлению структуры дерева функции (а только к той его части, которая сохранена). Решение о том, может ли и должен ли код функции напрямую встраиваться в код функций, ее вызывающих, делается в конце генерации RTL. Функция должна удовлетворять некоторым критериям, которые сейчас касаются ее размера и типов и количества ее параметров. Обратите внимание, что эта функция может содержать циклы, рекурсивные обращения к себе (функции с "хвостовой" рекурсией могут быть встроенными!), операторы перехода, короче говоря, все конструкции, поддерживаемые GNU CC. Файл " integrate.c " содержит код для сохранения RTL функции для того, чтобы потом его вставлять, и вставки этого RTL, когда функция вызывается. Файл заголовка " integrate.h " также используется для этой цели. Опция " -dr " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .rtl " к имени входного файла.

 Оптимизация переходов. Этот проход упрощает переходы к следующей команде, переходы через переходы и переходы к переходам. Он удаляет неиспользуемые метки и недостижимый код, за исключением того, что недостижимый код, который содержит цикл, не распознается как недостижимый в этот проход. (Такие циклы удаляются позже при анализе базовых блоков). Он также преобразует некоторый код, первоначально написанный с переходами, в последовательности команд, которые непосредственно устанавливают значения по результатам сравнений, если машина имеет такие команды. Оптимизация переходов выполняется два или три раза. Первый раз происходит сразу после генерации RTL. Второй раз - после CSE, но только если CSE сообщает, что повторная оптимизация перехода необходима. Последний раз - перед заключительным проходом. На этом проходе перекрестные переходы и стирание пустых команд перемещения выполняются вместе с оптимизациями, описанными выше. Исходный файл этого прохода - " jump.c ". Опция " -dj " вызывает дамп отладки RTL кода после первого выполнения этого прохода. Имя файла дампа получается добавлением " .jump " к имени входного файла.

 Просмотр регистров. Этот проход находит, когда первый и когда последний раз использовался каждый регистр; это потребуется для удаления общих подвыражений. Источник находится в " regclass.c ".

 Слияние переходов. Этот проход распознает условные переходы, ветви которых ведут к идентичному или обратному тесту. Такие переходы могут быть "слиты" через второй условный тест. Исходный текст этого прохода находится в " jump.c ". Эта оптимизация выполняется, только если установлена опция "-fthread-jumps".

 Удаление общих подвыражения (CSE). Этот проход также вычисляет константные выражения. Исходный файл - " cse.c ". Если после вычисления константных выражений некоторые условные переходы становятся безусловным или неисполняемыми, то по окончании CSE снова выполняется оптимизация переходов. Опция " -ds " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .cse " к имени входного файла.

 Оптимизация циклов. Этот проход перемещает постоянные выражения за пределы циклов и выполняет упрощения тела цикла или раскрутку цикла. Исходные файлы - " loop.c " и "unroll.c", а также файл заголовка " loop.h ", используемый для связи между ними. Раскрутка цикла использует некоторые функции в " integrate.c " и заголовок " integrate.h ". Опция " -dL " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .loop " к имени входного файла.

 Если была установлена опция " -frerun-cse-after-loop ", второй проход общего удаления подвыражения выполняется после прохода оптимизации цикла. В этом случае слияние переходов также снова выполняется в это время. Опция " -dt " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .cse2 " к имени входного файла.

 "Глупое" распределение регистров выполняется в этом месте при трансляции без оптимизации. Этот проход производит небольшой потоковый анализ. Если используется "глупое" распределение регистров, следующим выполняется проход перезагрузки; все проходы между ними пропускаются. Исходный файл - " stupid.c ".

 Потоковый анализ данных (" flow.c "). Этот проход делит программу на базовые блоки (и по ходу работы удаляет недостижимые циклы); затем он вычисляет, какие псевдорегистры "живут" в каждой точке программы и делает первую команду, которая использует значение, указывающей на команду, которая вычислила значение. Этот проход также удаляет вычисления, результаты которых никогда не используются, и объединяет ссылки на память с командами сложения или вычитания для получения адресации с автоинкрементом и автодекрементом. Опция " -df " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .flow " к имени входного файла. Если используется "глупое" распределение регистров, этот файл дампа отражает полные результаты такого распределения.

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

 Планирование команд (" sched.c "). Этот проход ищет команды, чей вывод не будет доступен ко времени его использования в последующих командах. (Команды загрузки памяти и работы с плавающей точкой часто ведут себя так на RISC машинах). Он переупорядочивает команды внутри базового блока, чтобы попытаться разделить определение и использование элементов, которые иначе вызвали бы приостановку работы. Планирование команд выполняется дважды. Первый раз - сразу после комбинирования команд и второй - сразу после перезагрузки. Опция " -dS " вызывает дамп отладки RTL кода после первого выполнения этого прохода. Имя файла дампа получается добавлением " .sched " к имени входного файла.

 Выбор класса регистров. RTL код просматривается, чтобы выяснить, какой класс регистров является самым лучшим для каждого псевдорегистра. Исходный файл - " regclass.c ".

 Локальное распределение регистров (" local-alloc.c "). Этот проход распределяет аппаратные регистры псевдорегистрам, которые используются только внутри одного базового блока. Поскольку базовый блок линеен, он может использовать быстрые и мощные методы и получать очень хорошие результаты. Опция " -dl " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .lreg " к имени входного файла.

 Глобальное распределение регистров (" global.c "). Этот проход распределяет аппаратные регистры для оставшихся псевдорегистров (тех, чьи промежутки жизни не содержатся в одном базовом блоке).

 Перезагрузка. Этот проход перенумеровывает псевдорегистры номерами аппаратных регистров, в которые они были распределены. Псевдорегистры, не получившие аппаратных регистров заменяются на слоты стека. Затем он находит команды, которые являются недопустимыми, потому что значение не смогло закончиться в регистре или закончилось в регистре неправильного вида. Он исправляет эти команды, временно перезагружая эти значения в регистры. Генерируются дополнительные команды для копирования. Проход перезагрузки также может устранять указатель кадра и вставлять команды для сохранения и восстановления регистров, использующихся вызываемой функцией, до и после вызова. Исходные файлы - " reload.c " и " reload1.c ", а также заголовок " reload.h ", используемый для связи между ними. Опция " -dg " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .greg " к имени входного файла.

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

 Оптимизация переходов повторяется, включая на этот раз перекрестные переходы и удаление пустых команд перемещения. Опция " -dJ " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .jump2 " к имени входного файла.

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

 Преобразование из использования некоторых аппаратных регистров к использованию регистров стека может быть выполнено в этом месте. В настоящее время это поддерживается только для регистров сопроцессора Intel 80387 с плавающей точкой. Имя исходного файла - " reg-stack.c ". Опция " -dk " вызывает дамп отладки RTL кода после этого прохода. Имя файла дампа получается добавлением " .stack " к имени входного файла.

 Заключительный проход. Этот проход выводит код ассемблера для функции. Он является также ответственным за идентификацию ложных команд проверки и сравнения. Специфическая для машины оптимизация выполняется в это же время. Последовательности для входа и выхода из функции генерируются непосредственно как код ассемблера в этом проходе; они никогда не существуют как RTL. Исходные файлы - " final.c " и " insn-output.c "; последний генерируется автоматически из машинного описания утилитой " genoutput ". Файл заголовка " conditions.h " используется для связи между этими файлами.

 Вывод информации об отладке. Он выполняется после заключительного прохода, потому что он должен вывести смещения слотов стека для псевдорегистров, которые не получили аппаратных регистров. Исходные файлы - " dbxout.c " для формата таблицы символов DBX, " sdbout.c " для формата таблицы символов SDB, и " dwarfout.c " для формата таблицы символов DWARF.

 

Роль рекурсии в грамматике. Примеры. (лекция 7)

⇐ Предыдущая234567891011

Поделиться: