Цель работы: изучение основных принципов генерации компилятором объектного кода для линейного участка программы, ознакомление с методами оптимизации результирующего объектного кода с помощью свертки и исключения лишних операций.
Для выполнения лабораторной работы требуется написать программу, которая на основании дерева синтаксического разбора порождает объектный код и выполняет затем его оптимизацию. В качестве исходного дерева синтаксического разбора рекомендуется взять дерево, которое порождает программа, построенная по заданию предыдущей лабораторной работы.
Программу рекомендуется построить из трех основных частей: первая часть — порождение дерева синтаксического разбора (по результатам лабораторной работы №3), вторая часть — реализация алгоритма порождения объектного кода по дереву разбора, и третья часть — оптимизация порожденного объектного кода. Результатам работы должна быть построенная на основании заданного предложения грамматики программа на объектном языке. В качестве объектного языка предлагается взять язык ассемблера для процессоров типа Intel 80×86 в реальном режиме (возможен выбор другого объектного языка по согласованию с преподавателем). Все встречающиеся в исходной программе идентификаторы считать простыми скалярными переменными, не требующими выполнения преобразования типов. Ограничения на длину идентификаторов и констант соответствуют требованиям предыдущей лабораторной работы.
Как быстро выучить программирование / ТОП 5 способов как быстро изучить программирование новичку
Краткие теоретические сведения
Генерация объектного кода — это перевод компилятором внутреннего представления исходной программы в результирующую объектную программу на языке ассемблера или непосредственно на машинном языке (машинных кодах).
Генерация объектного кода выполняется после того, как выполнен синтаксический анализ программы и все необходимые действия по подготовке к генерации кода: распределено адресное пространство под функции и переменные, проверено соответствие имен и типов переменных, констант и функций в синтаксических конструкциях исходной программы и т.д.
Оптимизация программы — это обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эффективной результирующей объектной программы. Оптимизация выполняется на этапах подготовки к генерации и непосредственно при генерации объектного кода.
Лучшие оптимизирующие компиляторы могут получать объектные программы из сложных исходных программ, написанных на языках высокого уровня, почти не уступающие по качеству программам на языке ассемблера. Временные и трудовые затраты на создание такой программы существенно меньше, чем при ее реализации на ассемблере. У современных компиляторов существуют возможности выбора тех или иных критериев оптимизации, исходя из которых оценивается эффективность объектной программы. Так, с одной стороны, возможна оптимизация с минимизацией размера программы, с другой стороны — оптимизация с увеличением скорости ее выполнения. При этом не требуется изменять текст программы на исходном языке.
ЧТО ДЕЛАТЬ ЕСЛИ НЕ ПОНИМАЕШЬ ПРОГРАММИРОВАНИЕ | КАК ВЫУЧИТЬ ПРОГРАММИРОВАНИЕ
Все эти преимущества говорят в пользу применения оптимизации. Единственным, но существенным недостатком оптимизации является необходимость тщательной ее проработки при создании компилятора.
Используемые методы оптимизации ни при каких условиях не должны приводить к изменению “смысла” исходной программы (т.е. к таким ситуациям, когда результат выполнения программы изменяется после ее оптимизации). К сожалению, не все методы оптимизации, используемые создателями компиляторов, могут быть теоретически обоснованы и доказаны для всех возможных видов исходных программ. Поэтому большинство компиляторов предусматривает возможность отключать те или иные из возможных методов оптимизации. (Часто при оптимизации компиляторы выдают предупреждения разработчику программы, если тот или иной ее участок вызывает подозрения в отношении правильности его “смысла”). Применение оптимизации также нецелесообразно в процессе отладки исходной программы.
Различаются две основные категории оптимизирующих преобразований:
· преобразования исходной программы (в форме ее внутреннего представления в компиляторе), не зависящие от результирующего объектного языка;
· преобразования результирующей объектной программы.
Последний тип преобразований может зависеть не только от свойств объектного языка (что очевидно), но и от архитектуры вычислительной системы, на которой будет выполняться результирующая программа. (Так, например, при оптимизации может учитываться объем кэш-памяти и методы организации конвейерных операций центрального процессора). Этот тип преобразований здесь рассматриваться не будет. Именно эти преобразования могут повлиять на “смысл” исходной программы. В большинстве случаев они являются “ноу-хау” производителей компиляторов и строго ориентированы на определенные архитектуры вычислительных машин.
Методы преобразования программы зависят от типов синтаксических конструкций исходного языка. Теоретически разработаны методы оптимизации для многих типовых конструкций языков программирования. Далее будут рассмотрены только методы оптимизации линейных участков — они встречаются в любой программе и составляют существенную часть программного кода.
Линейный участок программы — это выполняемая по порядку последовательность операций имеющая один вход и один выход. Чаще всего линейный участок содержит последовательность арифметических операций и операторов присвоения значений переменным.
Прежде чем перейти к вопросам оптимизации линейных участков рассмотрим их внутренне представление в компиляторе.
Алгоритм генерации объектного кода по дереву вывода
Возможны различные формы внутреннего представления синтаксических конструкций исходной программы в компиляторе. На этапе синтаксического разбора часто используется форма, именуемая деревом вывода (методы его построения рассматривались в предыдущих лабораторных работах). Но формы представления, используемые на этапах синтаксического анализа, оказываются неудобными в работе при генерации и оптимизации объектного кода. Поэтому перед оптимизацией и непосредственно генерацией объектного кода внутреннее представление программы преобразуется в одну из соответствующих форм записи.
Примерами таких форм записи являются:
· обратная польская запись операций;
· собственно команды ассемблера.
Обратная польская запись — это постфиксная запись операций. Преимуществом ее является то, что все операции записываются непосредственно в порядке их выполнения. Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек.
Тетрады представляют собой запись операций в форме из четырех составляющих:
(,,). Тетрады используются редко, так как требуют больше памяти для своего представления, чем триады, не отражают взаимосвязи операций и, кроме того, плохо отображаются в команды ассемблера и машинные коды, так как в наборах команд большинства современных машин не встречаются операции с тремя операндами.
Триады представляют собой запись операций в форме из трех составляющих: (,), при этом один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно номеруют для удобства указания ссылок одних триад на другие. Например, выражение A := B*C + D — B*10, записанное в виде триад будет иметь вид:
Здесь операции обозначены соответствующим знаком (при этом присвоение также является операцией), а знак ^ означает ссылку операнда одной триады на результат другой.
Команды ассемблера удобны тем, что при их использовании внутреннее представление программы полностью соответствует объектному коду и сложные преобразования не требуются. Однако использование команд ассемблера требует дополнительных структур для отображения их взаимосвязи. Кроме того, внутреннее представление программы получается зависимым от результирующего кода, а это значит, что при ориентации компилятора на другой результирующий код потребуется перестраивать как само внутреннее представление программы, так и методы его обработки в алгоритмах оптимизации (при использовании триад или тетрад этого не требуется).
Для построения внутреннего представления объектного кода (в дальнейшем — просто кода) по дереву вывода может использоваться простейшая рекурсивная процедура. Эта процедура прежде всего должна определить тип узла дерева — он соответствует типу операции, символ которой находится в листе дерева для текущего узла.
Этот лист является средним листом узла дерева для бинарных операций и крайним левым листом — для унарных операций. После определения типа процедура строит код для узла дерева в соответствии с типом операции. Если все узлы следующего уровня для текущего узла есть листья дерева, то в код включаются операнды, соответствующие этим листьям, и получившийся код становится результатом выполнения процедуры. Иначе процедура должна рекурсивно вызвать сама себя для генерации кода нижележащих узлов дерева и результат выполнения включить в свой порожденный код.
Поэтому для построения внутреннего представления объектного кода по дереву вывода в первую очередь необходимо разработать формы представления объектного кода для четырех случаев, соответствующих видам текущего узла дерева вывода:
· оба нижележащих узла дерева — листья (терминальные символы грамматики);
· только левый нижележащий узел является листом дерева;
· только правый нижележащий узел является листом дерева:
· оба нижележащих узла не являются листьями дерева.
Рассмотрим построение двух видов внутреннего представления по дереву вывода:
· построение ассемблерного кода по дереву вывода;
· построение списка триад по дереву вывода.
Построение ассемблерного кода по дереву вывода
В качестве языка ассемблера возьмем язык ассемблера процессоров типа Intel 80×86. При этом будем считать, что операнды могут быть помещены в 16-разрядные регистры процессора и в коде результирующей объектной программы могут использоваться регистры AX (аккумулятор) и DX (регистр данных), а также стек для хранения промежуточных результатов.
Тогда четырем формам текущего узла дерева будут соответствовать следующие фрагменты кода на языке ассемблера (табл. 5):
Преобразование типовых узлов дерева вывода в код на языке ассемблера
Источник: fort-inform.ru
Модули
Встроенные в язык программирования функции доступны сразу. Чтобы их вызвать, не надо выполнять никаких дополнительных действий. Однако за время существования любого популярного языка на нем было написано столько функций и классов, которые оказались востребованными множеством программистов и в разных областях, что включить весь этот объем кода в сам язык если возможно, то нецелесообразно.
Чтобы разрешить проблему доступа к дополнительным возможностям языка, в программировании стало общепринятой практикой использовать так называемые модули, пакеты и библиотеки. Каждый модуль содержит коллекцию функций и классов, предназначенных для решения задач из определенной области. Так в модуле math языка Python содержатся математические функции, модуль random позволяет генерировать псевдослучайные числа, в модуле datetime содержатся классы для работы с датами и временем, модуль sys предоставляет доступ к системным переменным и т. д.
Количество модулей для языка Python огромно, что связано с популярностью языка. Часть модулей собрана в так называемую стандартную библиотеку. Стандартная она потому, что поставляется вместе с установочным пакетом. Однако существуют сторонние библиотеки. Они скачиваются и устанавливаются отдельно.
Для доступа к функционалу модуля, его надо импортировать в программу. После импорта интерпретатор «знает» о существовании дополнительных классов и функций и позволяет ими пользоваться.
В Питоне импорт осуществляется командой import . При этом существует несколько способов импорта. Рассмотрим работу с модулем на примере math . Итак,
>>> import math
Ничего не произошло. Однако в глобальной области видимости появилось имя math . Если до импорта вы упомянули бы имя math , то возникла бы ошибка NameError . Теперь же
>>> math
В программе завелся объект math , относящийся к классу module .
Чтобы увидеть перечень функций, входящих в этот модуль, воспользуемся встроенной в Python функцией dir() , передав ей в качестве аргумента имя модуля:
>>> dir(math) [‘__doc__’, ‘__loader__’, ‘__name__’, ‘__package__’, ‘__spec__’, ‘acos’, ‘acosh’, ‘asin’, ‘asinh’, ‘atan’, ‘atan2’, ‘atanh’, ‘ceil’, ‘comb’, ‘copysign’, ‘cos’, ‘cosh’, ‘degrees’, ‘dist’, ‘e’, ‘erf’, ‘erfc’, ‘exp’, ‘expm1’, ‘fabs’, ‘factorial’, ‘floor’, ‘fmod’, ‘frexp’, ‘fsum’, ‘gamma’, ‘gcd’, ‘hypot’, ‘inf’, ‘isclose’, ‘isfinite’, ‘isinf’, ‘isnan’, ‘isqrt’, ‘lcm’, ‘ldexp’, ‘lgamma’, ‘log’, ‘log10’, ‘log1p’, ‘log2’, ‘modf’, ‘nan’, ‘nextafter’, ‘perm’, ‘pi’, ‘pow’, ‘prod’, ‘radians’, ‘remainder’, ‘sin’, ‘sinh’, ‘sqrt’, ‘tan’, ‘tanh’, ‘tau’, ‘trunc’, ‘ulp’]
Проигнорируем имена с двойными подчеркиваниями. Все остальное – имена функций и констант (переменных, которые не меняют своих значений), включенных в модуль math. Чтобы вызвать функцию из модуля, надо впереди написать имя модуля, поставить точку, далее указать имя функции, после чего в скобках передать аргументы, если они требуются. Например, чтобы вызвать функцию pow из math, надо написать так:
>>> math.pow(2, 2) 4.0
Обратите внимание, эта другая функция pow() , не та, что встроена в сам язык. «Обычная» функция pow() возвращает целое, если аргументы целые числа:
>>> pow(2, 2) 4
Для обращения к константе скобки не нужны:
>>> math.pi 3.141592653589793
Если мы не знаем, что делает та или иная функция, то можем получить справочную информацию о ней с помощью встроенной в язык Python функции help() :
>>> help(math.gcd) Help on built-in function gcd in module math: gcd(*integers) Greatest Common Divisor. (END)
Для выхода из интерактивной справки надо нажать клавишу q . В данном случае сообщается, что функция вычисляет наибольший общий делитель. Описание модулей и их содержания также можно посмотреть в официальной документации на сайте python.org.
Второй способ импорта – это когда импортируется не сам модуль, а только необходимые функции из него.
>>> from math import gcd, sqrt, hypot
Перевести можно как «из модуля math импортировать функции gcd , sqrt и hypot «.
В таком случае при их вызове не надо перед именем функции указывать имя модуля:
>>> gcd(100, 150) 50 >>> sqrt(16) 4.0 >>> hypot(3, 4) 5.0
Чтобы импортировать сразу все функции из модуля:
>>> from math import *
Импорт через from не лишен недостатка. В программе уже может быть идентификатор с таким же именем, как имя одной из импортируемых функций или констант. Ошибки не будет, но одно из них окажется «затерто»:
>>> pi = 3.14 >>> from math import pi >>> pi 3.141592653589793
Здесь исчезает значение 3.14, присвоенное переменной pi . Это имя теперь указывает на число из модуля math . Если импорт сделать раньше, чем присвоение значения pi , то будет все наоборот:
>>> from math import pi >>> pi = 3.14 >>> pi 3.14
В этой связи более опасен именно импорт всех функций. Так как в этом случае очень легко не заметить подмены значений идентификаторов.
Однако можно изменить имя идентификатора из модуля на какое угодно:
>>> from math import pi as P >>> P 3.141592653589793 >>> pi 3.14
В данном случае константа pi из модуля импортируется под именем P . Другой смысл подобных импортов – сокращение имен, так как есть модули с длинными именами, а имена функций и классов в них еще длиннее. Если в программу импортируется всего пара сущностей, и они используются в ней часто, то имеет смысл переименовать их на более короткий вариант. Сравните:
>>> import calendar >>> calendar.weekheader(2) ‘Mo Tu We Th Fr Sa Su’
>>> from calendar import weekheader as week >>> week(3) ‘Mon Tue Wed Thu Fri Sat Sun’
Во всех остальных случаях лучше оставлять идентификаторы содержимого модуля в пространстве имен самого модуля и получать доступ к ним через имя модуля, то есть выполнять импорт командой import имя_модуля , а вызывать, например, функции через имя_модуля.имя_функции() .
Практическая работа. Создание собственного модуля
Программист на Python всегда может создать собственный модуль, чтобы использовать его в нескольких своих программах или даже предоставить в пользование всему миру. В качестве тренировки создадим модуль с функциями для вычисления площадей прямоугольника, треугольника и круга:
from math import pi, pow def rectangle(a, b): return round(a * b, 2) def triangle(a, h): return round(0.5 * a * h, 2) def circle(r): return round(pi * pow(r, 2), 2)
Здесь также иллюстрируется принцип, что один модуль может импортировать другие. В данном случае импортируются функции из модуля math .
Поместите данный код в отдельный файл square.py . Однако куда поместить сам файл?
Когда интерпретатор Питона встречает команду импорта, то просматривает на наличие файла-модуля определенные каталоги. Их перечень можно увидеть по содержимому sys.path :
>>> import sys >>> sys.path [», ‘/usr/lib/python310.zip’, ‘/usr/lib/python3.10’, ‘/usr/lib/python3.10/lib-dynload’, ‘/home/pl/.local/lib/python3.10/site-packages’, ‘/usr/local/lib/python3.10/dist-packages’, ‘/usr/lib/python3/dist-packages’]
Это список адресов в Linux. В Windows он будет несколько другим. Первый элемент – пустая строка, что обозначает текущий каталог, то есть то место, где сохранена сама программа, импортирующая модуль. Если вы сохраните файл-модуль и файл-программу в одном каталоге, то интерпретатор без труда найдет модуль.
Также модуль можно положить в любой другой из указанных в списке каталогов. Тогда он будет доступен для всех программ на Python, а также его можно будет импортировать в интерактивном режиме.
Можно добавить в sys.path свой каталог. Однако в этом случае либо код программы должен содержать команды изменения значения sys.path , либо надо править конфигурационный файл операционной системы. В большинстве случаев лучше так не делать.
Поместите файл square.py в тот же каталог, где будет исполняемая программа. Ее код должен включать инструкцию импорта модуля square (при импорте расширение файла не указывается) и вызов той функции и с теми параметрами, которые ввел пользователь. То есть у пользователя надо спросить, площадь какой фигуры он хочет вычислить. Далее запросить у него аргументы для соответствующей функции. Передать их в функцию из модуля square , а полученный оттуда результат вывести на экран.
Примечание. Исполнение модуля как самостоятельного скрипта, а также создание строк документации, которые отображает встроенная в Python функция help() , будут рассмотрены в курсе объектно-ориентированного программирования.
Примеры решения и дополнительные уроки в pdf-версии курса
X Скрыть Наверх
Python. Введение в программирование
Источник: younglinux.info
Как из кода получается программа
Просто заходите на PythonOnline.kz. Там Вы можете писать, запускать, проверять и даже скачивать Ваш код на компьютер. Используя встроенный компилятор.
Компилятор PythonOnline.kz был создан для того, чтобы Вы не заморачивались на установке и настройке редакторов кода, а могли сразу приступить к программированию.
В этой книге я могу называть этот компилятор разными словами: редактор, консоль, компилятор. Это все одно и тоже.
3. Как читать код в этой книге?
Читая код в этой книге, пожалуйста обратите внимание на несколько нюансов:
Точки в начале некоторых строк кода указывают на отступы. Эти точки только в книге, и нужны они только для корректного отображения отступов. Вам не нужно ставить ни точки, ни отступы в своем коде, так как наш компилятор будет ставить отступы автоматически.
Все, что стоит в коде за знаком # – это комментарии к коду, для Вашего удобства.
Если Вы сейчас что-то не поняли, не волуйтесь. Время от времени, я буду напоминать Вам об этих нюансах, по мере прохождения данной книги.
4. Что делать с тестами из книги?
Очень рекомендую проходить тест в конце каждой главы.
Отвечайте на вопросы в уме. В случае, если в тесте нужно работать с кодом, записывайте, запускайте и проверяйте его на PythonOnline.kz
Если что-то не получается с тестами, Вы всегда можете подсмотреть готовые ответы. Они есть в приложении, в конце книги.
Только не бегите за подсказками сразу! Лучше пройдите тему еще раз. А затем вернитесь к тесту, и перепройдите его.
Здесь нет строгих учителей. И перепроходить тесты можно сколько угодно, пока Вы не останитесь довольны своим результатом.
5. Почему именно Питон?
Python – один из самых простых в освоении, но в то же время один из самых популярных и широко используемых языков программирования во всем мире.
Я бы порекомендовал Python как первый язык программирования всем, кто хочет научиться программировать.
У Python чистый, минималистичный синтаксис. И это упрощает написание и чтение кода.
Например, для того, чтобы написать небольшую программу на Python, Вам может потребоваться всего несколько строчек кода.
А для того, чтобы написать такую же программу, скажем, на Java или C++, Вам придется писать куда больше кода.
Именно поэтому, на технических собеседованиях в Google или еще куда, Вам позволят решать задачи на Python. Даже если Вас рассматривают на позицию разработчика Java или C++ и тд.
Python – это высокоуровневый язык программирования. Это означает то, что он автоматизирует многие процессы, такие, как управление памятью.
А это, в свою очередь, поможет Вам сосредоточиться на основных задачах, пока Вы пишите код.
Python чрезвычайно популярен в реальном мире. Возьмите для примера IT-гигантов, таких, как: Google, Apple, Netflix. Все они используют Python в повседневных задачах, связанных с обработкой данных, работой нейронных сетей, и других важными для этих компаний процессов.
Python, действительно, универсален. Он отлично работает не только для математических задач, связанных с данными. Но и для веб-приложений, видеоигр, и, вообще, чего угодно. И это благодаря огромному выбору расширений и библиотек, доступных для Python. Об этом Вы узнаете более подробно в четырнадцатой главе.
Источник: readli.net