Документы



Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 icon

Конспект лекций По предмету Системное программное обеспечение Ташкент 2008

НазваниеКонспект лекций По предмету Системное программное обеспечение Ташкент 2008
страница23/30
Дата29.05.2013
Размер5.65 Mb.
ТипКонспект лекций
скачать
1   ...   19   20   21   22   23   24   25   26   ...   30
1. /Sistemnoe_programnoe_obespecheniye.docКонспект лекций По предмету Системное программное обеспечение Ташкент 2008

9. Генерация кода. Методы генерации кода. Общие принципы генерации кода. Оптимизация линейных участков программы. Машинно-зависимые методы оптимизации.

Генерация кода. Методы генерации кода

Общие принципы генерации кода. Синтаксически управляемый перевод

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

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

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

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

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

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

Суть принципа СУ-перевода заключается в следующем: с каждой вершиной де­рева синтаксического разбора N связывается цепочка некоторого промежуточного кода C(N). Код для вершины N строится путем сцепления (конкатенации) в фик­сированном порядке последовательности кода C(N) и последовательностей кодов, связанных со всеми вершинами, являющимися прямыми потомками N. В свою очередь, для построения последовательностей кода прямых потомков вершины N потребуется найти последовательности кода для их потомков — потомков вто­рого уровня вершины N — и т. д. Процесс перевода идет, таким образом, снизу вверх в строго установленном порядке, определяемом структурой дерева.

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

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

Схему СУ-компиляции можно реализовать не для всякого входного языка про­граммирования. Если принцип СУ-перевода применим ко всем входным КС-языкам, то применить СУ-компиляцию оказывается не всегда возможным. Од­нако известно, что схемы перевода на основе СУ-компиляции можно построить для многих из широко распространенных классов КС-языков, в частности для LR- и LL-языков [6, 15].

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

  • помещение в выходной поток данных машинных кодов или команд ассембле­
    ра, представляющих собой результат работы (выход) компилятора;

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

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

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

Способы внутреннего представления программ

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

Все внутренние представления программы обычно содержат в себе две при] пиально различные вещи — операторы и операнды. Различия между фор?* внутреннего представления заключаются лишь в том, как операторы и one ды соединяются между собой. Также операторы и операнды должны отлича друг от друга, если они встречаются в любом порядке. За различение onepai и операторов, как уже было сказано выше, отвечает разработчик компиляч который руководствуется семантикой входного языка.

Известны следующие формы внутреннего представления программ1:

  • связочные списочные структуры, представляющие синтаксические дерев

  • многоадресный код с явно именуемым результатом (тетрады);

  • многоадресный код с неявно именуемым результатом (триады);

  • обратная (постфиксная) польская запись операций;

  • ассемблерный код или машинные команды.

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

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

Далее все перечисленные формы представления рассматриваются более подробно.

Синтаксические деревья

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

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

Синтаксические деревья могут быть преобразованы в другие формы внутренне­го представления программы, представляющие собой линейные списки, с учетом семантики входного языка. Алгоритмы такого рода преобразований рассмотрены далее. Эти преобразования выполняются на основе принципов СУ-компиляции.

Многоадресный код с явно именуемым результатом (тетрады)

Тетрады представляют собой запись операций в форме из четырех составляю­щих: операция, два операнда и результат операции. Например, тетрады могут выглядеть так: <операция>(<операнд1>,<операнд2>,<результат>).

Тетрады представляют собой линейную последовательность команд. При вычис­лении выражения, записанного в форме тетрад, они вычисляются одна за другой последовательно. Каждая тетрада в последовательности вычисляется так: опера­ция, заданная тетрадой, выполняется над операндами и результат ее выполнения помещается в переменную, заданную результатом тетрады. Если какой-то из операндов (или оба операнда) в тетраде отсутствует (например, если тетрада представляет собой унарную операцию), то он может быть опущен или заменен пустым операндом (в зависимости от принятой формы записи и ее реализации).

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

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

Тетрады требуют больше памяти для своего представления, чем триады, они та] же не отражают явно взаимосвязь операций между собой. Кроме того, есть ело? ности с преобразованием тетрад в машинный код, так как они плохо отображ ются в команды ассемблера и машинные коды, поскольку в наборах кома? большинства современных компьютеров редко встречаются операции с трек операндами.

Например, выражение A:=B*C+D-B*10, записанное в виде тетрад, будет иметь ви,

  1. * ( В, С, Т1 )

  2. + ( Tl.D, Т2 )

  3. * ( В. 10,ТЗ )

  4. - ( Т2.ТЗ.Т4 )

  5. := ( Т4,0, А )

Здесь все операции обозначены соответствующими знаками (при этом приевс

ние также является операцией). Идентификаторы Т1 Т4 обозначают време

ные переменные, используемые для хранения результатов вычисления тетрг Следует обратить внимание, что в последней тетраде (присвоение), которая тр бует только одного операнда, в качестве второго операнда выступает незначащ] операнд «0».

Многоадресный код с неявно именуемым результатом (триады)

Триады представляют собой запись операций в форме из трех составляющ! операция и два операнда. Например, триады могут иметь вид: <операция>(<операнд! <операнд2>). Особенностью триад является то, что один или оба операнда мог быть ссылками на другую триаду в том случае, если в качестве операнда данн триады выступает результат выполнения другой триады. Поэтому триады п записи последовательно нумеруют для удобства указания ссылок одних триад другие (в реализации компилятора в качестве ссылок можно использовать не i мера триад, а непосредственно ссылки в виде указателей — тогда при изменен нумерации и порядка следования триад менять ссылки не требуется).

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

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

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

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

Например, выражение A:=B*C+D-B*10, записанное в виде триад, будет иметь вид:

  1. * ( В, С )

  2. + П, D )

  3. * ( В, 10 )

  4. - Г2, Л3 )

  5. := ( А, А4 )

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

Обратная польская запись операций

Обратная (постфиксная) польская запись — очень удобная для вычисления вы­ражений форма записи операций и операндов. Эта форма предусматривает, что знаки операций записываются после операндов. Более подробно обратная польская запись рассмотрена далее.

Ассемблерный код и машинные команды

Машинные команды удобны тем, что при их использовании внутреннее пред­ставление программы полностью соответствует объектному коду и сложные пре­образования не требуются. Команды ассемблера представляют собой лишь форм} записи машинных команд (см. раздел «Трансляторы, компиляторы и интерпре таторы — общая схема работы», глава 13), а потому в качестве формы внутренне го представления программы практически ничем не отличаются от них. Однако использование команд ассемблера или машинных команд для внутрен него представления программы требует дополнительных структур для отображе ния взаимосвязи операций. Очевидно, что в этом случае внутреннее представле ние программы получается зависимым от архитектуры вычислительной системы на которую ориентирован результирующий код. Значит, при ориентации ком пилятора на другой результирующий код потребуется перестраивать как сам! внутреннее представление программы, так и методы его обработки (при исполь зовании триад или тетрад этого не требуется).

Тем не менее машинные команды — это язык, на котором должна быть записан результирующая программа. Поэтому компилятор так или иначе должен рабе тать с ними. Кроме того, только обрабатывая машинные команды (или их npe/i ставление в форме команд ассемблера), можно добиться наиболее эффективно результирующей программы (см. далее в разделе «Оптимизация кода. Основны методы оптимизации»). Отсюда следует, что любой компилятор работает с npez ставлением результирующей программы в форме машинных команд, однак их обработка происходит, как правило, на завершающих этапах фазы генераци кода.

Обратная польская запись операций

Обратная польская запись — это постфиксная запись операций. Она была пре; ложена польским математиком Я. Лукашевичем, откуда и происходит ее назв; ние [6, т. 2, 23, 82]1.

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

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

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

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

Но там, где оптимизация вычисления выражений не требуется или не имеет большого значения, обратная польская запись оказывается очень удобным мето­дом внутреннего представления программы.

Обратная польская запись была предложена первоначально для записи арифме­тических выражений. Однако этим ее применение не ограничивается. В компи­ляторе можно порождать код в форме обратной польской записи для вычисления практически любых выражений1. Для этого достаточно ввести знаки, предусмат­ривающие вычисление соответствующих операций. В том числе, возможно ввести операции условного и безусловного перехода, предполагающие изменение после­довательности хода вычислений и перемещение вперед или назад на некоторое количество шагов в зависимости от результата на верхушке стека [6, т. 2, 74, 82]. Такой подход позволяет очень широко применять форму обратной польской за­писи.

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

Вычисление выражений с помощью обратной польской записи

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

  1. Если встречается операнд, то он помещается в стек (попадает на верхушку
    стека).

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

3. Если встречается знак бинарной операции (операции, требующей двух one рандов), то два операнда выбираются с верхушки стека, операция выполняв! ся и результат помещается в стек (попадает на верхушку стека).

Вычисление выражения заканчивается, когда достигается конец записи выраже

ния. Результат вычисления при этом всегда находится на верхушке стека.

Очевидно, что данный алгоритм можно легко расширить и для более сложны

операций, требующих три и более операндов.

На рис. 14.4 рассмотрены примеры вычисления выражений в обратной польско

записи.



6




7




10




4




+




*




+

4

10

10

14

7

7

7

7

98

6

6

6

6

6

6

104

Вычисление выражения 6+7* (10+4) = 104
6 7 10 + 4










































10

4

7

7

17

17

68

6

6

6

6

6

6

74

Вычисление выражения 6+(7+10) * 4=74
6 7 + 10 4








































4

7

10

10

40

6

6

13

13

13

13

53
1   ...   19   20   21   22   23   24   25   26   ...   30



Похожие:

Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconКонспект лекций по дисциплине "Программное обеспечение интеллектуальных систем". Для магистров специальности 5А521902
Целью данного курса является приобретение знаний по разработки и реализации основных элементов систем искусственного интеллекта
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconКонспект лекций для высшего образования отрасли по направлению
Конспект лекций предназначен для бакалавров факультета ррт по направлению
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconКонспект лекций по предмету «распределенные системы и сети» Ташкент-2012 г Содержание 1
Охватывает своей сетью всю территорию Республики Узбекистан. Ак «Узбектелеком» согласно правительственному решению (Постановление...
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 icon«классификация неорганических веществ» Фергана-2011 год. Аннотация. Конспекты лекций по предмету «Классификация неорганических веществ»
Конспекты лекций по предмету «Классификация неорганических веществ» составили в соответствии с утвержденными учебными программами...
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconДокументы
1. /Программное обеспечение ИС (УМП 2007).doc
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconДокументы
1. /конспект.лекций.rtf
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconДокументы
1. /КОНСПЕКТ ЛЕКЦИЙ ПО ВЫСШЕЙ МАТЕМАТИКИ.doc
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconЛекция 3 Прикладное программное обеспечение
Ташкентский Университет Информационных Технологий Кафедра Информационных Технологий Информационные Технологии
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconТема задания
Антивирусные программы прочно заняли свое место на жестких дисках и входят в категорию программ, которые должен иметь каждый пользователь....
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconКомпоненты компьютера
В действительности компьютер это система многих узлов, работающих вместе. Физические части, которые можно увидеть и потрогать, в...
Конспект лекций По предмету Системное программное обеспечение Ташкент 2008 iconКурс лекций по фармакогнозии с основами биохимии лекарственных растений, Ташкент "Медицина" Узсср, 1987
Кумаринларга умумий тушунча, уларнинг ўсимликлар тўқимасидаги синтези – биосинтез ва ўсимликлар ҳаётидаги аҳамияти
Загрузка...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©uz.denemetr.com 2000-2015
При копировании материала укажите ссылку.
обратиться к администрации