Федеральное агентство по образованию РФ Государственное образовательное учреждение высшего профессионального образования Уральский государственный университет им. А.М.Горького
Математико-механический факультет
ASMPY – ассемблер pythoncompiled (*.pyc) файлов.
Курсовая работа студента гр. КН-202 КРАСНОРУЦКОГО А.В.
Рассматривается строение файлов скомпилированых модулей на языке программирования Python (“python compiled” файлов, или *.pyc файлов). Цель работы – создание языка низкого уровня для представления кода *.pyc файлов и
разработка программы-ассемблера для данного языка. Разрабатываются спецификация языка ассемблера виртуальной машины CPython, лексический и синтаксический анализаторы, методика тестирования модулей программы.
ВВЕДЕНИЕ Во многих из современных языков программирования высокого уровня (в том числе в языках Python, Perl, Java, C#, Managed С++) применяется компиляция исходных кодов программ в cтандартный промежуточный код (называемый байт-кодом) для виртуальной стековой машины.
Одним из наиболее динамично развивающихся сценарных языков в последние годы является язык Python. В целях обеспечения лучшей производительности при запуске программ скомпилированные байт-коды сохраняются на диске в виде так называемых “python compiled” файлов, или *.pyc файлов (имеющих расширение “pyc”). Значительный интерес вызывает задача изучения формата этих файлов и создания инструментов, позволяющих модифицировать эти файлы (например, с целью эффективной ручной оптимизации, изучения особенностей работы реализаций виртуальной машины python, обфускации байт-кода или обратного инжиниринга).
На основе имеющейся информации о грамматике *.pyc файлов и документации по опкодам ассемблера виртуальной машины языка Python была разработана спецификация языка ассемблера для генерации *.pyc файлов.
Была составлена формальная грамматика, описывающая данный язык, разработаны несколко вариантов лексического анализатора и синтаксический анализатор (предиктивный нерекурсивный парсер), создан транслятор, генерирующий *.pyc файлы. Подготовлен набор модульных тестов для всех основных компонентов программы. Все модули программы написаны на языке Python, что обеспечивает хорошую переносимость на различные оперционные системы и платформы.
В качестве дальнейшего развития программы может выступать реализация поддержки работы с новой версией языка Python (Python 3.0, или “Python 3000”), создание более высокоуровеневой версии языка ассемблера *.pyc файлов, разработка других инструментальных программ для работы с файлами формата «python compiled» . 1. ФОРМАТ *.PYC ФАЙЛОВ
Формат *.pyc файлов частично описан в исходном коде интерпретатора CPython. Имеется публично доступная грамматика этого языка на сайте [3].
Файлы формата *.pyc представляют собой бинарные (двоичные файлы), создаваемые интерпретатором при запуске сценариев на языке Python (текстовых файлов с расширением *.py) и сохраняемые им в той же самой директории, где находятся текстовые файлы python-скриптов. Также можно получать pyc-файлы при помощи маршаллинга (marshalling) объектов языка Python (см. документацию по модулям marshal и types из стандартной поставки интерпретатора).
В начале каждого *.pyc файла находятся два двойных слова (DWORD DWORD) (64 бит), образующие так называемый “magic” (сигнатуру). Прочитав эти восемь первых байт файла, интерпретатор идентифицирует его как скомпилированный модуль Python, а также определяет версию Python, для которой предназначен этот файл (формат *.pyc файлов изменяется от версии к версии; в настоящее время существуют 3 версии формата: версия 0 использовалась в Python до выхода версии 2.4, версия 1 – в Python 2.4, версия 2 – начиная с Python 2.5). Далее cледует так называмый “object” (объект), возможно, состоящий из других “объектов”. Объект может быть примитивным значенением (константы NULL, NONE, STOPITER, ELLIPSIS, FALSE, TRUE, UNKNOWN) или он может являться составным значенением, принадлежащем к одному из следующих типов: INT (целые числа), INT64, LONG (целые числа неограниченной величины для работы с «длинной арифметикой») , FLOAT (числа с плавающей запятой), BINARY_FLOAT, BINARY_COMPLEX (рациональные и комплексные числа, хранимые в бинарном формате), COMPLEX (комплексные числа), INTERNED, STRING, STRINGREF, UNICODE (стороковые типы), TUPLE (кортежи), LIST (списки), DICT (ассоциативные массивы), SET (множества), FROZENSET (неизменяемые множества) или CODE. Значения типа CODE состоят из нескольких секций (argcount, nlocals, stacksize, flags, code, consts, names , varnames, freevars, cellvars, filename, name, firstlineno, lnotab). В секций “code” хранятся непосредственно сами байт-коды виртуальной машины, в остальных секциях – информация о числе аргументов функций, имени файла, именах переменных, константах, локальных переменых, значениях флагов, требуемом размере стека, отладочная информация. В некоторых из секций может быть записано лишь единственное двойное слово (DWORD), а в других могут содержаться объекты, имеющие любые из перечисленных выше встроенных типов.
Коды операций ассемблера виртуальной машины СPython в большинстве своём являются однобайтовыми (они задают различные операции со стеком); некоторые коды требуют наличия двухбайтового операнда. Информацию по конкретным опкодам можно найти в документации к модулю “dis”, входящему в стандартную поставку интерпретатора.
2. РАЗРАБОТКА АССЕМБЛЕРА При разработке языка ассемблера для *.pyc файлов была составлена декомпозиция будущей программы, составлена спецификация, включающая в себя формальную контекстно-свободную грамматику этого языка. Также была разработана система модульных тестов (unit tests) для тестирования каждого из модулей.
При разработке грамматики предполагалось обеспечить возможность её разбора синтаксическим анализатором, работа которого основана на рекурсивном нисходящем анализе. Этой цели удалось достичь. Более того, созданная грамматика построена так, что её возможно разобрать при помощи предиктивного парсера, т.е. синтаксического анализатора, работающего методом рекурсивного нисходящего спуска без откатов.
Далее приводится спецификация языка ассемблера *.pyc файлов.
Ниже представлена формальная контекстно-свободная грамматика для языка, записанная при помощи нотации BNF (формы Бэкуса-Наура). Здесь используется разновидность BNF, где представления значений терминалов заключабтся в одинарные, а не в двойные кавычки. Стартовым символом является нетерминал . ::= INTERN_CONST
::= OPCODE | OPCODE | DB_DIRECTIVE ::= NUMBER | '' ::= NUMBER
::= NEWLINE | ',' | '' ::= '(' ')'
::= '[' ']'
::= '{' INDENT '}' |
::=
::= NEWLINE
| ',' NEWLINE
| DEDENT ::=
::= ',' | ' ::= ':' ::= 'set' '([' '])'
::= 'frozenset' '([' '])' 2.1.2 Спецификация для лексического анализа
Здесь и далее всюду, когда говорится о строке программы на AsmPy, понимается (если не оговорено обратное) логическая строка (строка, заканчивающаяся токеном NEWLINE). Если физическая строка завершается символом обратной косой черты (\) вне комментария или строкового литерала, то тогда сочетание данного символа и перевода строки интерпретируется как разделитель токенов, текущая строка иследующая строка составляют единую логическую строку. Внутри строкового литерала сочетание символа обратной косой черты (backslash) и перевода строки игнорируется; таким образом, можно продолжать длинные строковые литералы.
Внутри комментариев любые символы, кроме символа конца строки, игнорируются; backslash не продолжает комментарий на следующую физическую строку. Лексер выдаёт следующие токены (формальные определения записаны в виде perl-совместимых регулярных выражений илимодифицированного BNF-определения, принятого для описания грамматики языка Python (см. http://docs.python.org/2.6/doc/reference/introduction.html#notation), если явно не оговорено иное): INDENT - "+1 уровень отступа";
DEDENT - "-1 уровень отступа" (описание алгоритма выявления токенов INDENT и DEDENT можно найти в ПРИЛОЖЕНИИ 2); STR - строковая константа; поддерживаются escape-последовательности
"\a", "\f", "\n", "\r", "\t", "\v" и "\xNN", где NN -шестнадцатиричный код
символа; символы являются 8-битными;
регулярное выражение (запись, используемая в Python):
NEWLINE - перевод строки в стиле UNIX, DOS или Mac ( /(\015|\012)+/ ) c сохранением уровня отступа (но пустая строка или строка, в которую входят
только пробельные символы и/или комментарии, полностью игнорируется, если она не является частью строкового литерала; таким образом, не бывает двух токенов NEWLINE подряд);
регулярное выражение (запись, используемая в Python):
r'[\015\012]([ \t\f]+|;[^\015\012]*|[\015\012])*' ; WHITESPACE - последовательность пробельных символов (NEWLINE не считается пробельным символом) (эта последовательность должна соответствовать регулярному выражению /^[ \t\f]+\z/), парсеру не передаётся; NUMBER - число, ниже перечислены возможные его типы;
digit - '0'..'9' ;
word - '0'..'65535' ;
dword (STRINGREF) - '0'..'4294967295' ;
int - 32-битное целое со знаком;
int64 - 64-битное целое со знаком;
long - целое число (от "минус бесконечности" до "плюс бесконечности");
float - число с плавающей запятой (поддерживается и форма записи через
экспоненту; символ экспоненты – "e" (не "E"));
complex - комплексное число в форме "Re+Imj" или "Re+ImJ" (или же чисто
мнимое число в форме "ImJ"), где "Re" - вещественное число (в десятичной или восьмеричной записи), а Im - число с плавающей точкой или любая последовательность десятичных цифр (трактуется как число в десятичной системе счисления);
целые числа могут быть записаны в десятичной системе, в восьмеричной
(в начале ставится ноль) и в шестнадцатеричной системах (с ипользованием обычных цифр и символов "A", "B", "C", "D", "E", "F" (заглавных); если первая цифра не десятичная, то в начале ставится нуль; в конце всегда ставится 'h' или 'H'); числа с плавающей запятой могут быть только в десятичной записи;
знак ("-" или "+") входит в состав токена NUMBER;
общее регулярное выражение для токена NUMBER (запись, используемая в Python):
Ниже приведены значения по умолчанию для секций объекта СODE. argcount - 0;
nlocals - 0;
stacksize - 1;
flags - 64;
code - нет;
consts - нет;
names - 'TUPLE: ()';
varnames - 'TUPLE: ()';
freevars - 'TUPLE: ()';
cellvars - 'TUPLE: ()';
filename - 'STR: "1.py"';
name - 'STR: ""';
firslineno - 1;
lnotab - 'STR :""'. 3. АРХИТЕКТУРА ПРОГРАММЫ И ДЕТАЛИ РЕАЛИЗАЦИИ Общая структура включает в себя: реализации лексического анализатора, синтаксический анализатор, генератор предупреждений и сообщений об ошибках, хранилище информации об опкодах, транслятор AST (Abstract Syntax Tree; абстрактного синтаксического дерева) в байт-код, пользовательский CLI (Command Line Interface; интерфейс комндной строки) (разбор командной строки; вывод на консоль; операции файлового ввода-вывода). Command Line Parser
|
|
| +--> file.pym
V |
+-----> File I/O <-- file.pyc
| |
| |
| |
| V
| Lexer ---> ErrMsgGen --> STDERR
| | ^
| | |
| V |
| Parser-+
| |
| |
| V
| Translator
| |
| |
+----+ Все исходные тексты программы делятся на: * главный файл "asmpy.py" (процедура, реализующая разбор параметров командной строки, обработка ошибок ввода-вывода, вызовы процедур из остальных модулей),
* модуль AbstractLexer, включающий общую функциональность всех реализаций лексеров (зависит от "Opcodes.py"),
* модуль лексера "Lexer.py" (который зависит от модуля "ErrMsgGen.py"),
* альтернативный модуль для лексического анализа "RELexer.py" ( также
зависит от "ErrMsgGen.py"), * модуль для генерации предупреждений и сообщений об ошибках "ErrMsgGen.py" (также он предоставляет функции для отладочной печати), * модуль парсера "Parser.py" (зависит от "ErrMsgGen.py"), * модуль транслятора "Translator.py", * модуль-хранилище информации об опкодах "Opcodes.py". AsmPy
|
+--- asmpy.py
|
+--- AsmPyLib
|
+------- AbstractLexer.py
|
+--------- Lexer.py
|
+------- RELexer.py
|
+-------- Parser.py
|
+---- Translator.py
|
+----- ErrMsgGen.py
|
+------- Opcodes.py
3.1. Реализация лексического анализатора
Лескер получает на вход reader (т.е. любой подкласс класса file). Это может быть обычный file, буферизованный поток, IOString и др.
Public-методы класса Lexer: конструктор __init__, getAllTokens, readNextToken. Неизменяемый класс Token имеет атрибуты "lexeme" (лексема,
соответствующая данному токену), "kind" (тип токена), "pos" (позиция начала
токена во входном потоке: строка и столбец), "value" (значение лексемы).
Метод readNextToken пытается считать следующий токен из входного потока (т.е. из reader'а). Проверяется первый символ, по нему делается предположение о типе токена; если таких предположений может быть сделано несколько, то пытается читать дальше, следя за соответствием считываемого типу токена; если обнаружено несоответствие, делается другое предположение о типе токена; если не одно предположение не оказалось истинным, то читает до NEWLINE (вид данного токена устанавливается равным "ERR"). Также создана реализация «RELexer», использующая регулярные выражения, а не производящая достаточно медленные действия посимвольно.
Токены NEWLINE, INDENT и DEDENT распознаются отличным от других образом (распознавание INDENT и DEDENT происходит точно так же, как в языке Python), см. ПРИЛОЖЕНИЕ 2.
Не требуется, чтобы reader реализовывал метод seek. 3.2. Реализация синтаксического анализатора
Используется нерекурсивный нисходящий парсер без откатов. Отсутствие возможности того, что при разборе очередной продукции будет необходимо произвести откат, было достигуто за счёт левой факторизации исходного варианта формальной грамматики и устранения левой рекурсии.
Т.к. использован «предсказывеющий разбор» и отсутствует явная рекурсия, то разбор даже «сильно» вложенных констркций будет производиться достаточно быстро.
Обработка синтаксических ошибок
Если парсеру встретилась синтаксическая ошибка, рассматривать вершину, где это случилось, как последнего потомка её родителя. Дойти до конца секции или
(найти соответствующий DEDENT) и пытаться производить разбор дальше.
3.3. Реализация транслятора
Ниже приведено очень общее и схематичное описание трансляции.
Ccылки заменяются на объекты, на которые они указывают, до трансляции.
PycStream - поток, куда будет записывать pyc-код транслятор. 1. Открыть PycStream, записать magic в PycStream. 2. Обходя дерево (пройти вершину, потом её потомков слева направо),
транслировать висячие вершины и названия секций и типов в «python compiled» код и записывать в PycStream. 3. Обойдя всё дерево, закрыть PycStream.
3. 4. Тестирование Для тестирования правильности выполнения программы были написаны модульные тесты для каждого из её компонентов. Используется модуль unittest из стандартной поставки интерпретатора языка Python. Имеется также один модуль, предназначенный для тестирования программы целиком.
В каждой из этих тестовых программ тестируется один из классов библиотеки AsmPyLib; для каждого из этих классов есть 3 категории тестовых примеров:
«малые» примеры, проверяющие работу с небольшим количеством входных данных;
«большие простые» примеры, проверяющие работу с относительно большим количеством данных простой структуры;
«большие сложные» примеры, где широко представлены всевозможые крайние и предельные значения входных данных.
Большая часть примеров – выведенные заранее соответствия «входные данные -> правильный результат». Для некоторых модулей есть также тесты, где часть таких соответствий генерируется в процессе выполнения теста. Для лексического анализатора существенно помогает тестированию тот факт, что имеются две не связанные друг с другом реализации, которые должны проходить один и тот же набор тестов.
ЗАКЛЮЧЕНИЕ В настоящее время наблюдаются значительные изменения в структуре тех факторов, которые учитываются при выборе языка программирования для решения конкретных задач. Переносимость кода в бинарном виде часто стоит на одном из главных мест в списке требований. Программы на всё большем количестве языков программирования высокого уровня в наши дни не компилируются непосредственно в исполняемый машинный код, а транслируются в промежуточный код, исполняющийся на виртуальных машинах или преобразующийся в машинные инструкции во время испонения программы. Работа с низкоуровневым кодом для таких виртуальных машин будет приобретать всё большее практическое значение для задач оптимизации, отладки, обратного инжиниринга.
В архитектуре программе AsmPy заложены условия для хорошей расширяемости и переносимости, и это позволит развивать данный проект в дальнейшем.
СПИСОК ЛИТЕРАТУРЫ
Ахо, Альфред, В., Сети, Рави, Ульман, Джеффри, Д.
Компиляторы: принципы, технологии и инструменты. Пер. с англ. - М. Издательский дом “Вильямс”, 2003. - 768 с.
Aхо А., Ульман Дж.
Теория синтаксического анализа, перевода и компиляции. Пер. с англ. - М. Издательство “МИР”, 1978. - 616 с.
Параметры командной строки asmpy.py OPTIONS [source] [output] -hl consider as a program written in high-level version of
the python assembler. -q "quiet mode"; do not display warnings (the same as -W0) -Wn set warning level to n (where n is 0, 1, 2 or 3)
(0 is the most quiet one, 3 is the strictest level) -f "force"; overwrite existing ".pyc" file --lexer choose a lexer engine for processing source file(s) ("Lexer" or
"RELexer") -v verbose mode; display verbose warnings and error messages -V prints the AsmPy version number and exits
Руководство администратора Добавлено описание по заполнению файлов загрузки учреждений (п. 2 Подготовка Excel-файлов для импорта учреждений) и по заполнению...
Организация ученического самоуправления Факультетское образование: филологический факультет с изучением 2-х иностранных языков, физико-математический факультет с элементами...
