Документація pyCompiler¶
Вступ¶
Опис роботи¶
Компілятор pyCompiler - системна програма, яка призначена для транслювання коду на мові високого рівня Myl на мову асемблера, компіляції за допомогою NASM та лінкування у виконавчий файл.
Компілятор включає в себе такі компоненти як:
- Лексичний аналізатор,
- Синтаксичний аналізатор,
- Транслятор (Формальна граматика мови описана далі. myl далі - “мова”),
- Оптимізатор коду на асемблері,
- Генератор коду мови асемблера;
Всі компоненти повністю покриті тестами. Для тестування використана програма nosetests.
Використані інструменти¶
Компілятор повністю написаний на мові програмування Python 2.7, призначений для запуску на OS GNU/Linux.
Зовнішні інструменти, необхідні для роботи:
- Власне компілятор, який може бути скачаний з репозиторію https://github.com/antigluk/pyCompiler (або архівом ZIP: https://github.com/antigluk/pyCompiler/archive/master.zip)
- Системна програма лінкування ld
- Компілятор мови асемблеру NASM
- Інтерпретатор мови Python 2
Етапи отримання виконавчого файлу¶
Вихідний код, поданий як вхідні дані проходить кілька етапів обробки:
- Лексичний аналіз, при якому код розбирається на окремі лексеми
- Синтаксичний, при якому зі списку лексем формується дерево виконання
- Аналіз отриманого дерева, отримання списків оголошених функцій, змінних, строкових літералів
- Транслювання дерева виконання у код на псевдо-асемблері для ОС GNU/Linux
- Оптимізація коду на псевдо-асемблері
- Генерація коду на асемблері в синтаксисі NASM
- Компіляція коду за допомогою системної програми NASM у об’єкний файл
- Лінкування об’єкного файлу зі бібліотекою libc в виконавчий файл
Тобто, на виході можна отримати бінарний файл, готовий до виконання.
Якщо запустити програму з параметром “-v”, то можна побачити команди виклику зовнішніх системних програм nasm та ld:
pyCompiler 0.1
-------------------
Lexical analysis: Done
Syntax analysis: Done
Find variables and strings: Done
Generate Pseudo-Asm code: Done
Optimization: Done
Generate NASM code: Done
Compiling:
nasm -f elf -o examples/build/e7.o -O2 -l examples/build/e7.lst examples/build/e7.asm
Done
Linking:
ld -s -lc -dynamic-linker /lib/ld-linux.so.2 -o examples/e7.bin examples/build/e7.o
Done
А саме, виклик NASM:
nasm -f elf -o examples/build/e7.o -O2 -l examples/build/e7.lst examples/build/e7.asm
Бачимо, що генерується об’єкний файл формату ELF, а також увімкнена оптимізація O2
Виклик ld - є програмою лінкування:
ld -s -lc -dynamic-linker /lib/ld-linux.so.2 -o examples/e7.bin examples/build/e7.o
Ключ “-lc” додає до програми бібліотеку libc - стандартну бібліотеку з корисними функціями, такими як printf, scanf, fflush та іншими.
Вихідний файл має розширення .bin, а саме examples/e7.bin - після лінковки є виконавчим файлом з правами на виконання (+x).
Опис мови програмування¶
Вступ до мови¶
Мова програмування, яка використовується в компіляторі, розроблена спеціально для нього і містить обмежену кількість конструкцій, які транслюються в асемблерні коди.
Присвоєння¶
Для того, щоб присвоїти значення змінній достатньо написати ім’я цієї змінної на початку рядка, знак дорівнює “=” та значення:
x = 5;
Також можна присвоювати значення будь-якого математичного виразу:
x = (a+b)*10;
Допустимі операції:
- Додавання, віднімання “+”, “-“
- Множення, цілочислене ділення “*”, “/”
- Остача від ділення: “%”
Оператор розгалуження¶
Конструкція розгалуження має вигляд:
if <вираз>:
<блок операторів 1>
else:
<блок операторів 2>
endif;
Якщо результат виразу є істиною, то буде виконаний блок операторів 1, інакше - блок операторів 2.
У виразі можуть бути використані математичні операції, а також такі оператори як “>”, “<”, “>=”, “<=”, “=”.
Оголошення змінних¶
В мові немає особливих конструкцій для оголошення змінних. Всі змінні, які були використані у програмі в будь-якому місці вважаються оголошеними.
Тип усіх змінних є цілочисленим подвійним словом.
Всі змінні, використані у функціях є локальними. Для роботи з зовнішніми змінними можна використовувати лише параметри функції. Змінні передаються за значенням.
Оголошення функцій¶
Для оголошення функції використовується ключове слово “function”. Синтаксис оголошення є таким:
function <name>(<аргументи, розділені комою>)
<блок операторів>
return <змінна>;
endfunc;
Інтерактивна консоль¶
Друк на екран¶
Для друку на екран використовується оператор “print”. Оператор існує в двох формах:
- друк змінної
print var;
- друк строкового літералу
print “Hello, world”;
В рядках може бути символи “\n”, які автоматично замінюються на символи переводу рядка.
Зчитування з клавіатури¶
Для читання з клавіатури використовується оператор “read”.
Наприклад, читання числа з клавіатури:
read var;
Оператори циклу¶
В мові існує оператор циклу while, який реалізує цикл з передумовою. Синтаксис оператору:
while <умова повтору>:
<блок операторів>
endwhile;
За умови істиності умови повтору, програма буде повторювати блок операторів.
За допомогою цієї конструкції легко реалізувати повторення блоку задану кількість разів:
N = 1;
while N<=4:
print N;
print "\n";
N = N+1;
endwhile;
В даному випадку цикл буде виконуватись 4 рази, друкуючи кожну ітерацію лічильник. Вивод буде таким:
1
2
3
4
Висновки¶
Розроблена мова програмування є повною за Тюрингом, тобто за допомогою неї можна обчислити будь-яку математичну функцію.
Формальна граматика мови¶
Граматика описана у розширеній БНФ:
Програма :: = {СтрокаПрограмми}
СтрокаПрограмми :: = (Операція ";") | (КеруючаКонстр ":") | ОголошенняФункції
Операція :: = Присвоєння | Друк | Введення | (КінецьГалуження)
| (КінецьWhile) | (ПоверненняЗначення | КінецьФункції)
КеруючаКонстр :: = (Галуження | ГалуженняІнакше) | (ЦиклWhile)
Число :: = ["+" | "-"] НатЧісло
НатЧисло :: = Цифра {Цифра}
Цифра :: = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Ідентифікатор :: = Буква {Буква | Цифра}
Змінна :: = Ідентифікатор
ВизовФункції :: = Ідентифікатор "(" {[Вираз [","]]} ")"
Присвоєння :: = Ідентифікатор "=" Вираз
Вираз :: = (Змінна | Число) | ВизовФункціі | Вираз МатОперація Вираз |
"+" | "-" Вираз | "(" Вираз ")"
МатОперація :: = "+" | "-" | "*" | "/" | "%"
Друк :: = "print" (Рядок | Змінна)
Введення :: = "read" Змінна
Рядок :: = "" {.} ""
Галуження :: = "if" Вираз
ГалуженняІнакше :: = "else"
КінецьГалуження :: = "endif"
ЦиклWhile :: = "while" Вираз
КінецьWhile :: = "endwhile"
ОголошенняФункції :: = "function" Ідентифікатор "(" [{Параметр [","]}] ")"
Параметр :: = Змінна
ПоверненняЗначення :: = "return" Змінна
КінецьФункції :: = "endfunc"
Компоненти¶
Лексичний аналізатор¶
Модуль, що відповідає за розбір вихідного коду на лексеми.
- Поділ робиться на основі типу лексем, які бувають:
- ALPHA - букви
- NUM - цифри
- SYMB - символи =:> <+ - * / () {}%,
- CMDEND - символ ;
- QUOTE - лапки ” і ‘
- COMMENT - коментарі. # - Однорядковий коментар
Все послідовності символів типу SYMB є сукупностями окремих посимвольно лексем крім деяких винятків, таких як поєднання символів ‘> =’ і ‘<=’.
Всі однорядкові коментарі ігноруються і не входять в результуючий список лексем.
Для кожної рядкової лексеми запам’ятовується рядок, на якій вона була знайдена для подальшої обробки помилок.
-
pyCompiler.utils.lexer.lex(source)¶ Функція, що відповідає за лексичний аналіз
Parameters: source – вихідний код програми Return type: список лексем
Приклад¶
Дан вихідний код:
i = (15-2) -5;
print "i =";
print i;
print "\ n";
Його лексичний розбір буде таким: [‘i’, ‘=’, ‘(‘, ‘15 ‘,’ - ‘, ‘2’, ‘)’, ‘-‘, ‘5 ‘,’; ‘,’ print ‘,’ “i =” ‘,’; ‘,’ print ‘,’ i ‘,’; ‘,’ print ‘,’ “n” ‘,’; ‘]
Синтаксичний аналізатор¶
Модуль приймає як вихідні дані результат лексичного аналізу, список лексем. Мета подальшої обробки - побудова синтаксичного дерева.
Аналіз робиться за допомогою двох машин, які будують дерево:
- Основна машина для обробки керуючих конструкцій і операторів мови
- Машина, що відповідає за обробку виразів
Перемикання між машинами відбувається автоматично, спираючись на машину станів.
Стани EXPR* є станами, в яких включається друга машина. При зустрічі лексеми, що не належить до виразу машина повертає керування основній.
Використання машин не тільки дозволяє спростити синтаксичний аналіз, знаючи які лексеми очікуються і який тип виразу розбирається в даний момент набагато раніше, ніж це було б використовуючи шаблони (маски), це також допомагає виявляти синтаксичні помилки дуже рано.
-
pyCompiler.utils.syntax.synt(lex)¶ Функція, що відповідає за лексичний аналіз
Parameters: lex – список лексем Return type: дерево розбору
Основна машина¶
Машина працює строго по станам, діаграма яких зображена вище. Використовується так само стекова система, що дозволяє відкласти обробку деяких лексем до остаточного визначення типу виразу і збору всіх даних для додавання вузла в дерево.
Також проводить аналіз синтаксичних помилок, перериваючи роботу і вказуючи на рядок з помилкою при виявленні.
-
pyCompiler.utils.syntax.m_default()¶ Генератор дерева розбору, основна машина
Машина виразів¶
Стекова машина, що працює за принципом перетворення інфіксного вираження в постфіксной (польська нотація), при цьому на виході не постфіксной запис у рядок, а дерево виразу з математичними операціями та операндами у вузлах.
-
pyCompiler.utils.syntax.m_expressions()¶ Машина виразів
Приклад¶
Вираз
(15-2) -5
перетвориться в таке дерево
- '-',
------ '-',
---------- '15 ',
---------- '2 '
------ '5 '
Вираз
j +2> = 10
У таке дерево
- '> =',
------ '+',
---------- 'J',
---------- '2 '
------ '10 '
Комунікація між машинами¶
Використовується глобальний стек, який доступний обом машинам, так що розібрані вирази передаються з другої машини в першу через нього, так як остаточні вузли в дерево додає саме перша машина. Вирази ж є лише частинами більш великих конструкцій, таких як присвоювання, розгалуження і умови виходу в циклах.
Транслятор¶
Транслятор перетворює дерево синтаксичного розбору на набір мікрооперацій абстракної мови асемблера, але у внутрішньому представленні (список кортежів мови Python). Вона може бути однозначно перетворена у текст програми асемблера, але цей крок робиться для того, щоб можна було зробити оптимізацію.
В даній реалізації транслятор перетворює дерево в код, який специфічний для операційної системи GNU/Linux.
- Системні визови до ядра Linux (номери функції ядра)
- Переривання визову функції ядра int 0x80
- Використання функцій бібліотеки libc
Але модульна архітектура компілятора дозволяє легко реалізувати транслятор для інших систем при необхідності та без впливу на інші модулі програми.
Транслювання відбувається в 2 етапи:
- Збір інформації
- Генерація псевдо-асемблерного коду
Збір інформації¶
Для перетворення коду транслятор в першу чергу робить обхід по дереву та збирає дані про майбутній код, такі як:
- Змінні
- Строкові літерали
- Оголошені функції
- Виклики функцій виводу та вводу
Особливістю є, що транслятор шукає тільки унікальні строки, то ж якщо в коді зустрічаються наприклад виводи на екран тієї самої строки кілька разів, строка буде включена у дані програми тільки один раз.
Якщо в коді не зустрічаються визови вводу/виводу чи інші функції з бібліотеки libc, то бібліотека не буде прилінкована.
-
class
pyCompiler.utils.gen.TreeStats¶
-
pyCompiler.utils.gen.find_vars(t)¶ Функція збору інформації
Parameters: t – дерево розбору Return type: структура TreeStats з інформацією про код
Генерація псевдо-асемблерного коду¶
Кожен оператор мови високого рівня (myl) транслюється в послідовність команд асемблеру.
-
pyCompiler.utils.gen.gen_code(t, stat)¶ Функція, що відповідає за генерацію псевдо-асемблерного коду
Parameters: - t – дерево розбору
- stat – дані про код
Return type: список операторів псевдо-асемблеру
Оголошення функції¶
function mul(x,y)
R = x*y;
return R;
endfunc;
Транслюється в:
jmp Func0End
label Func_mul
mov eax, esp+4
mov vmul_x, eax
mov eax, esp+8
mov vmul_y, eax
; Тіло функції
mov dword eax, [vmul_x]
mov dword ebx, [vmul_y]
imul ebx
; Кінець тіла
ret
label Func0End
Оператор return¶
Повернення результату з функцыї:
return x;
Всередині функції транслюється в:
mov eax, vFUNC_x
ret
Оператор print¶
Для строк:
print "123"
Транслюється в:
push str0
call printf
add esp, 4
push [stdout]
call fflush
add esp, 4
де str0 це:
str0: db "123"
str0len: equ $-str0
Або для змінних:
print x;
транслюється в:
mov eax, [vx]
push eax
push numbs
call printf
add esp, 8
push [stdout]
call fflush
add esp, 4
де numbs це:
numbs: db "%d", 0
Оператор read¶
Читання числа з клавіатури з записом результату в змінну x:
read x;
транслюється в:
push vx
push numbs_in_format
call scanf
add esp, 8
call getchar
де numbs_in_format це:
numbs_in_format: db "%d",0
Інші оператори¶
Транслювання інших операторів дивитись в доданку з вихідним кодом (https://github.com/antigluk/pyCompiler), файл utils/gen.py, функція gen_text_section
Оптимізатор коду на асемблері¶
-
pyCompiler.utils.optimizer.optimize(pseudo)¶ -
Функція, відповідальна за оптимізацію Parameters: pseudo – список операторів псевдо-асемблерного коду Return type: оптимізований список операторів псевдо-асемблерного коду
Оптимізація проводиться в кілька ітерацій, за замовчуванням код подходить оптимізатори два рази.
Оптимізатори - функції, які оптимізують кожна свою конструкцію.
Оптимізатор роботи зі стеком¶
-
pyCompiler.utils.optimizer.optimize_push_pop(pseudo)¶
Видаляє конструкції виду:
push eax
pop eax
Такі конструкції з’являються після генерації коду.
Оптимізатор подвійного копіювання¶
-
pyCompiler.utils.optimizer.optimize_mov(pseudo)¶
Оптимізує конструкції вигляду:
mov eax, 5
mov ebx, eax
у:
mov ebx, 5
Такі конструкції з’являються після генерації коду.
Генератор коду мови асемблера¶
Генерує код в синтаксисі nasm на основі псевдо-асемблерні коду.
Перетворює обмежену кількість команд псевдо-асемблера у реальний код. Кожна команда має однозначний еквівалент в компіляторі асемблеру NASM.
-
pyCompiler.utils.gen_asm.gen_real_asm(pseudo, src_file)¶ Функція, що відповідає за генерацію кода
Parameters: - pseudo – код на псевдо-асемблері
- src_file – назва файлу вихідного коду
Return type: код для NASM
-
pyCompiler.utils.gen_asm.nasm_gen(l)¶ Перетворення команди на код в синтаксисі NASM
Parameters: l – команда псевдо-асемблера Return type: команда в синтаксисі NASM
Приклад¶
Код на мові myl:
function mul(x,y)
R = x*y;
return R;
endfunc;
read j;
i = 5*mul(j,2);
print i;
print "\n";
Генерує такий код на асемблері
; Source file: e7.src
; Generated 2012-11-11 15:35:50
SECTION .data
_kernel_: equ 0x80
; Strings
numbs: db "%d", 0
numbs_in_format: db "%d",0
; Variables
vmul_x: dd 0
vmul_y: dd 0
vmul_R: dd 0
vj: dd 0
vi: dd 0
SECTION .text
global _start
extern printf
extern scanf
extern getchar
extern fflush
extern stdout
_start:
; setup stack frame
push dword ebp
mov dword ebp, esp
; Function mul
jmp Func1End
Func_mul:
mov dword eax, [esp+4]
mov dword [vmul_x], eax
mov dword eax, [esp+8]
mov dword [vmul_y], eax
mov dword eax, [vmul_x]
mov dword ebx, [vmul_y]
imul ebx
ret
Func1End:
push dword vj
push dword numbs_in_format
call scanf
add esp, 8
call getchar
push dword 2
push dword [vj]
call Func_mul
add esp, 8
push dword eax
mov dword eax, 5
pop dword ebx
imul ebx
mov dword [vi], eax
push dword [vi]
push dword numbs
call printf
add esp, 8
push dword [stdout]
call fflush
add esp, 4
; restore stack frame
mov dword esp, ebp
pop dword ebp
mov dword ebx, 0
mov dword eax, 1
int _kernel_
Інструкція з використання програми¶
Компіляція¶
Приклад використання програми¶
Наприклад, маємо вихідний код:
#file.src
function mul(x,y)
R = x*y;
return R;
endfunc;
read j;
i = 5*mul(j,2);
print i;
Компілюємо:
$ ./myl file.src
pyCompiler 1.0
-------------------
В директорії з вихідним кодом з’явився файл з такою-ж назвою, але з розширенням .bin з правами на виконання (+x).
Це і є виконавчий файл програми, в чому ми можемо переконатися, запустивши його:
$ ./file.bin
5
50
Параметри командного рядка¶
Виконавчий файл - ./myl
В загальному випадку для компіляції файлу file.src з вихідним кодом потрібно виконати таку команду:
$ ./myl /path/to/file.src
Після цього, якщо не задані інші параметри, в директорії з вихідним кодом з’явиться бінарний файл file.bin, який є виконавчим.
Для використання особливих опцій при компіляції ви можете вказати такі параметри:
- -O0 - вимкнення вбудованої оптимізації
- -l - зберігання результатів лексичного аналізу в файл .lex
- -s - зберігання результатів синтаксичного аналізу в файл .synt
- -A - зберігання файлу з програмою на асемблері
- -L - створення файлу лістингу
- -n - вимкнення оптимізації при генерації об’єкних файлів (не передається -O0 до nasm)
- -v - розширений вивід коментарів та етапів роботи при компіляції
- -a - вмикання всіх опцій -slAL одночасно
Вимкнення оптимізації¶
Не рекомендується, але може буди корисним при відлагоджуванні програми, щоб подивитись чистий код, який видає транслятор. Він буде містити багато безглуздих конструкцій, таких як:
push eax
push ebx
pop eax
pop ebx
або таких:
mov eax,eax
також можуть бути неоптимальні конструкції як:
mov eax, 1
push eax
які оптимізуються транслятором до:
push dword 1
та інші випадки.
Вмикання проміжних файлів¶
Якщо передати опцію -a, компілятор створить в директорії з вихідним кодом папку build, в якій будуть збережені всі проміжні файли:
- Лексичного аналізу .lex
- Синтаксичного аналізу .synt
- Пошуку змінних та строкових літералів .stat
- Файл згенерованого коду на мові асемблеру .asm
- Лістинг .lst
За допомогою цих файлів можна дізнатися про всі етапи обробки вихідної программи, а також подивитись дерево синтаксичного розбору у файлі .synt
Додатки¶
| [B1] | Пустоваров В.И. Ассемблер: программирование и анализ корректности машинных программ. – К: BHV, 2000, Стор. 230-265. |
| [B2] | Dandamudi, S.P.: Guide to Assembly Language Programming in Linux - Springer, 2005, Стор. 552. |
| [B3] | Tanenbaum, A.S. and Woodhull, A.S.: Operating systems: design and implementation - Pearson Prentice Hall, 2006, 1054 c. |
| [B4] | Mark Lutz: Learning Python, 2009, 1214 c. |
| [B5] | Marty Alchin: Pro Python, 2010, 368 c. |
| [B6] | Бек Л.: Введение в системное программирование: Пер. с англ.- М.: Мир, 1988. - 448 с. |
| [B7] | Інтернет-ресурс Intel x86 Instruction Reference - http://www.posix.nl/linuxassembly/nasmdochtml/nasmdoca.html |
| [B8] | Інтернет-ресурс Running NASM - http://www.nasm.us/doc/nasmdoc2.html |
Висновок¶
Було розроблено мову програмування високого рівня, повоної за Тюрингом, до неї розроблено компілятор з функцією оптимізації. Мова описана в формальній граматиці.
Під час написання роботи було написано лексичний, синтаксичний аналізатори, вивчені та реалізовані оптимізаційні алгоритми, робота кінцевого автомату станів, реалізований механізм обробки помилок. Вивчений синтаксис асемблеру NASM, тонкощі компіляції програм для операційної системи GNU/Linux.
Розроблена програма може бути використана як повноцінний компілятор, або бути частиної інтерпретатора з функцію Just-in-Time компіляції, які зараз достатньо поширені. Така можливість істотньо покращить показники швидкості запуску програм інтерпретованих мов програмування.
Код програми¶
./pyc
#!/usr/bin/python2
from __future__ import print_function
import sys
import string
import os
import argparse
import subprocess
from utils.lexer import lex
from utils.syntax import synt, print_tree
from utils.gen import find_vars, gen_code
from utils.gen_asm import gen_real_asm
from utils.optimizer import optimize
from utils import ParserError, verbose_output
VERSION = (1, 1)
def print_header():
print("pyCompiler %d.%d" % VERSION)
print('-------------------')
def build_file_path(fl_name, ext, build_dir=True):
fl = dirname = os.path.basename(fl_name)
if build_dir:
dirname = os.path.join(os.path.dirname(fl_name), 'build')
else:
dirname = os.path.dirname(fl_name)
parts = fl.split('.')
parts[-1] = ext
return os.path.join(dirname, string.join(parts, '.'))
@verbose_output
def do_lex(args):
lex_file = build_file_path(args.file, 'lex')
print("Lexical analysis: ", end="")
lex_l = lex(file(args.file).read())
if args.lex:
lexf = open(lex_file, 'w')
print(lex_l, file=lexf)
lexf.close()
print("Done")
return lex_l
@verbose_output
def do_synt(args, lex_l):
tree_file = build_file_path(args.file, 'synt')
print("Syntax analysis: ", end="")
tree = synt(lex_l)
if args.synt:
tree_f = open(tree_file, 'w')
print(tree, file=tree_f)
print_tree(tree, f=tree_f)
tree_f.close()
print("Done")
return tree
@verbose_output
def do_stats(args, tree):
stats_file = build_file_path(args.file, 'stat')
print("Find variables and strings: ", end="")
stat = find_vars(tree)
if args.synt:
stats_f = open(stats_file, 'w')
print("vars =", stat.vars, file=stats_f)
print("strs =", stat.strs, file=stats_f)
stats_f.close()
print("Done")
return stat
@verbose_output
def do_gen_pseudo_asm(args, tree, stat):
print("Generate Pseudo-Asm code: ", end="")
p = gen_code(tree, stat)
print("Done")
return p
@verbose_output
def do_gen_asm(args, p):
fl = os.path.basename(args.file)
asmfile_name = build_file_path(args.file, 'asm')
print("Generate NASM code: ", end="")
asmfile = open(asmfile_name, 'w')
lines = gen_real_asm(p, os.path.basename(fl))
for line in lines:
print(line, file=asmfile)
asmfile.close()
print("Done")
return p
@verbose_output
def do_optimization(args, p):
print("Optimization: ", end="")
res = optimize(p)
print("Done")
return res
@verbose_output
def do_compile(args):
lstfile_name = build_file_path(args.file, 'lst')
asmfile_name = build_file_path(args.file, 'asm')
ofile_name = build_file_path(args.file, 'o')
print("Compiling: ", end="")
params = ["nasm", "-f", "elf", "-o", ofile_name, '-O2' if not args.no_optimize else '',
'-l' if args.lst else '', lstfile_name if args.lst else '', asmfile_name]
try:
if args.verbose:
print('\n', ' '.join(params))
subprocess.check_output(params)
except subprocess.CalledProcessError:
print("NASM Error!", file=sys.stderr)
# print(res)
sys.exit(-1)
except OSError:
print("NASM not found", file=sys.stderr)
sys.exit(-1)
if not args.asm:
os.remove(asmfile_name)
print("Done")
@verbose_output
def do_link(args):
ofile_name = build_file_path(args.file, 'o')
binfile_name = build_file_path(args.file, 'bin', build_dir=False)
print("Linking: ", end="")
params = ["ld", '-s', "-lc", '-dynamic-linker', '/lib/ld-linux.so.2', '-o', binfile_name, ofile_name]
try:
print('\n', ' '.join(params))
res = subprocess.check_output(params)
except subprocess.CalledProcessError:
print("ld Error!", file=sys.stderr)
print(res)
sys.exit(-1)
except OSError:
print("ld not found", file=sys.stderr)
sys.exit(-1)
if not args.asm:
os.remove(ofile_name)
print("Done")
def main():
print_header()
parser = argparse.ArgumentParser()
parser.add_argument('file', metavar="FILE", type=str, help='source file name')
parser.add_argument('-l', '--lex', action="store_true", help="save lexical processing results to file")
parser.add_argument('-s', '--synt', action="store_true", help="save syntax tree to file")
parser.add_argument('-v', '--verbose', action="store_true", help="print information")
parser.add_argument('-A', '--asm', action="store_true", help="save asm file")
parser.add_argument('-L', '--lst', action="store_true", help="listing")
parser.add_argument('-O0', action="store_true", help="no internal optimization")
parser.add_argument('-n', '--no-optimize', action="store_true", help="no -O2 option for nasm")
parser.add_argument('-a', '--all-intermediate', action="store_true", help="Synonym for -slAL")
parser.add_argument('--target', type=str, choices=["linux", "c2m"], default="linux",
help="c2m target is Cyclone II based CPU")
args = parser.parse_args()
if args.all_intermediate:
args.lex = args.asm = args.synt = args.lst = True
build_files = args.lex or args.asm or args.synt or args.lst
build_dir_name = os.path.join(os.path.dirname(args.file), 'build')
if not os.path.exists(build_dir_name):
os.mkdir(build_dir_name)
try:
tree = do_synt(args, do_lex(args))
p = do_gen_pseudo_asm(args, tree, do_stats(args, tree))
if not args.O0:
p = do_optimization(args, p)
do_gen_asm(args, p)
do_compile(args)
do_link(args)
except IOError:
print("\n\nERROR: File not found", file=sys.stderr)
sys.exit(-1)
except ParserError, e:
print('\n\nERROR: %s' % e.message, file=sys.stderr)
if args.verbose:
import traceback
traceback.print_exc()
sys.exit(-2)
except NotImplementedError, e:
print("\n\nNot implemented: %s" % e.message, file=sys.stderr)
sys.exit(-3)
if not build_files:
try:
os.rmdir(build_dir_name)
except OSError:
pass
if __name__ == '__main__':
main()
./utils/__init__.py
class ParserError(Exception):
pass
import os
import sys
from const import *
def typeof(t):
if t is None:
return T_NO
if isinstance(t, FunctionCallInfo):
return T_CALL
if not isinstance(t, str):
return T_NO
if t.isalpha():
if t in RESERVED_WORDS:
return RESERVED_WORDS[t]
else:
return T_VAR
elif t.isdigit():
return T_NUMBER
elif t in SYMB_DICT:
return SYMB_DICT[t]
elif t[0] == '"' and t[-1] == '"':
return T_STRING
elif t.isalnum():
return T_VAR
else:
return T_NO
class FunctionCallInfo(str):
def __new__(cls, name, args):
s = super(FunctionCallInfo, cls).__new__(cls, name)
s.args = args
return s
def verbose_output(func):
"""
Suppresses output if --verbose was not set
"""
def _verbose_output(*pargs, **kwargs):
args = pargs[0]
old_stdout = sys.stdout
if not args.verbose:
null_output = open(os.devnull, 'w')
sys.stdout = null_output
try:
ret = func(*pargs, **kwargs)
if not args.verbose:
sys.stdout = old_stdout
except:
#fallback
if not args.verbose:
sys.stdout = old_stdout
raise
return ret
return _verbose_output
./utils/const.py
# Token types
T_NO, T_IF, T_PRINT, T_READ, T_VAR, T_NUMBER, T_STRING, T_OPEREND, T_CTRLEND, \
T_EQ, T_PLUS, T_MINUS, T_IMUL, T_IDIV, T_POPEN, T_PCLOSE, T_BEGIN, T_END, \
T_LT, T_GT, T_GE, T_LE, T_ELSE, T_ENDIF, T_WHILE, T_ENDWHILE, T_MOD,\
T_FUNCTION, T_SEPARATOR, T_RETURN, T_ENDFUNC, T_CALL = range(32)
# Tree blocks
A_NO, A_ASSIGN, A_IF, A_BLOCK, A_PRINT, A_ELSE, A_READ, A_WHILE, A_FUNCTION, \
A_RETURN, A_CALL = range(11)
# Asm command type
# C_EQU_F is $-label
C_NO, C_ADD, C_SUB, C_PUSH, C_POP, C_CALL, C_PRINT, C_COMMENT, C_READ, C_MOV, \
C_CMP, C_DB, C_DD, C_EQU, C_EQU_F, C_EXTRN, C_GLOBL, C_LABEL, C_INT, C_JMP, \
C_IMUL, C_IDIV, C_RET, C_NEG = range(24)
C_OPT_NO, C_OPT_ADDR, C_PRINT_STR, C_PRINT_VAR = range(4)
EXPRESSIONS_TOKENS = [T_VAR, T_NUMBER, T_STRING, T_EQ,
T_PLUS, T_MINUS, T_IMUL, T_IDIV, T_MOD,
T_LT, T_GT, T_GE, T_LE, T_POPEN, T_PCLOSE,
T_SEPARATOR, ]
NAMES = \
{
A_NO: "<no>",
A_ASSIGN: "=",
A_IF: "if",
A_BLOCK: "{block}",
A_PRINT: "print",
A_READ: "read",
A_WHILE: "while",
A_FUNCTION: "function",
A_RETURN: "return",
A_CALL: "call",
}
# line start states
START_LIST = [] # gen
RANGES_LIST = (T_BEGIN, T_END)
EXPRESSIONS_STATES = None # gen
START_NODE = -1
links = \
{ # gen
}
SYMB_DICT = \
{
"=": T_EQ,
"+": T_PLUS,
"-": T_MINUS,
"*": T_IMUL,
"/": T_IDIV,
"%": T_MOD,
";": T_OPEREND,
":": T_CTRLEND,
">": T_GT,
"<": T_LT,
">=": T_GE,
"<=": T_LE,
'(': T_POPEN,
')': T_PCLOSE,
'{': T_BEGIN,
'}': T_END,
',': T_SEPARATOR,
}
RESERVED_WORDS = \
{
'if': T_IF,
'print': T_PRINT,
'read': T_READ,
'else': T_ELSE,
'endif': T_ENDIF,
'while': T_WHILE,
'endwhile': T_ENDWHILE,
'function': T_FUNCTION,
'return': T_RETURN,
'endfunc': T_ENDFUNC,
}
from graph import read_syntax_graph
import sys
read_syntax_graph(sys.modules[__name__])
./utils/lexer.py
import string
from utils import ParserError
class Token(str):
def __new__(cls, val, line):
s = super(Token, cls).__new__(cls, val)
s.line = line
return s
def lex(text):
global line_num
NO, ALPHA, NUM, SYMB, CMDEND, QUOTE, QUOTE_end, COMMENT = range(8)
line_num = 1
def typeof(s, string=False):
global line_num
if s[0].isalpha():
return ALPHA
elif s[0].isdigit():
return NUM
elif s[0] in "=:><+-*/(){}%,":
return SYMB
elif s[0] in [';']:
return CMDEND
elif s[0] in ['"', '\'']:
return QUOTE
elif s[0] in ['#']:
return COMMENT
elif s.strip() == "":
return NO
else:
if not string:
raise ParserError(
"Unknown symbol %s on line %d" % (s, line_num))
def symb_check(t, s):
COMBINATIONS = ('>=', '<=', '**', )
return (string.strip(string.join(t, '')) + s) in COMBINATIONS
all_tokens = []
token = []
prev_type = current_type = NO
string_token = ""
inline_comment = False
for s in text:
if s == '\n':
if prev_type == QUOTE:
raise ParserError("Unclosed quotes on line %d" % line_num)
line_num += 1
if inline_comment:
if s == '\n':
inline_comment = False
continue
current_type = typeof(s, prev_type == QUOTE)
if prev_type == QUOTE:
if current_type != QUOTE:
string_token += s
else:
all_tokens.append(Token("\"%s\"" % string_token, line_num))
string_token = ""
prev_type = QUOTE_end
token = []
continue
if current_type == COMMENT:
inline_comment = True
continue
if ((prev_type == current_type) or (prev_type == ALPHA and current_type == NUM)) \
and (current_type != SYMB or symb_check(token, s)):
token.append(s)
else:
if prev_type != NO:
clear_token = string.strip(string.join(token, ''))
if len(clear_token) > 0:
all_tokens.append(Token(clear_token, line_num))
prev_type = current_type
token = [s]
clear_token = string.strip(string.join(token, ''))
if len(clear_token) > 0:
all_tokens.append(clear_token)
return all_tokens
./utils/syntax.py
#-*- coding: utf8 -*-
" Syntax analyser "
from __future__ import print_function
import sys
from utils import ParserError
from const import *
from . import typeof, FunctionCallInfo
MACHINE_DEFAULT, MACHINE_EXPR = range(2)
machine = []
DEBUG = False
def synt(lex):
" Builds syntax tree "
global global_lex, global_stack, gres
global_lex = []
global_stack = []
gres = []
def_machine = m_default()
def_machine.next()
# INIT
machine.append(def_machine)
global_lex = list(reversed(lex))
while len(global_lex) > 0:
token = global_lex.pop()
machine[-1].send(token)
def_machine.send('}')
return gres
global_stack = []
gres = []
global_lex = []
def m_expressions():
" Machine for expression analysis "
global global_lex
stack = []
res = []
weights = {
T_POPEN: 0,
T_CALL: 0,
T_PCLOSE: 1,
T_SEPARATOR: 2,
T_PLUS: 20,
T_MINUS: 20,
T_IMUL: 10,
T_IDIV: 10,
T_MOD: 10,
T_GT: 5,
T_LT: 5,
T_GE: 5,
T_LE: 5,
T_EQ: 5,
T_OPEREND: -9000,
T_CTRLEND: -9000,
}
current_line = -1
while True:
token = (yield)
if token == None:
continue
if hasattr(token, 'line'):
current_line = token.line
token_type = typeof(token)
if token_type not in [T_OPEREND, T_CTRLEND] + EXPRESSIONS_TOKENS:
raise ParserError('Syntax error on line %d' % current_line)
if token_type in [T_VAR, T_NUMBER]:
res.append(token)
# FIXME: replace by logging
if DEBUG:
print (stack, res)
continue
if token_type in [T_POPEN, ]: # parentheses or function call
if (len(res) > 0) and typeof(res[-1]) == T_VAR:
stack.append(FunctionCallInfo(res.pop(), len(res)))
else:
stack.append(token)
if DEBUG:
print (stack, res)
continue
while (len(stack) != 0) and \
(weights[token_type] <= weights[typeof(stack[-1])]):
operation = (stack[-1], res[-2:])
del res[-2:]
stack.pop()
res.append(operation)
if token_type in [T_PCLOSE, ]:
oper = stack.pop()
if typeof(oper) == T_CALL:
assert isinstance(oper, FunctionCallInfo)
# function
args_count = len(res) - oper.args
if DEBUG:
print (oper, args_count, res[-args_count:])
if args_count > 0:
args = res[-args_count:]
del res[-args_count:]
else:
args = []
res.append((A_CALL, oper, args))
if DEBUG:
print (stack, res)
continue
if len(stack) == 0 or (weights[token_type] > weights[typeof(stack[-1])]):
if token_type != T_SEPARATOR:
stack.append(token)
if DEBUG:
print (stack, res)
if token_type not in EXPRESSIONS_TOKENS:
stack.pop()
assert len(stack) == 0
machine.pop()
global_stack.append(res)
global_lex.append(token)
class FunctionDescription(object):
def __init__(self):
self.name = None
self.args = []
self.inner_vars = []
def __repr__(self):
return "%s%s" % (self.name, self.args)
class Machine(object):
def __init__(self):
self.func = None
self.token = None
def extract_block(self, stop):
group = []
while True:
if not len(gres) > 0:
raise ParserError("Syntax error: invalid block")
last = gres.pop()
if last != stop:
group.append(last)
else:
break
gres.append((A_BLOCK, group))
def do_function(self):
self.func = FunctionDescription()
def do_func_name(self):
self.func.name = self.token
def do_func_arg(self):
self.func.args.append(self.token)
def do_func_args_end(self):
gres.append(A_FUNCTION)
def do_beg(self):
gres.append(A_BLOCK)
def do_end(self):
group = []
self.extract_block(A_BLOCK)
if len(group) > 0:
gres.append((A_BLOCK, group))
def do_var(self):
gres.append(self.token)
def do_string(self):
gres.append(self.token)
def do_ifsend(self):
gres.append(A_IF)
def do_elsesend(self):
self.extract_block(A_IF) # THEN-block
gres.append(A_ELSE)
def do_endifsend(self):
self.extract_block(A_ELSE)
elseblock = gres.pop()
thenblock = gres.pop()
oper = (A_IF, [global_stack.pop(), thenblock, elseblock])
# print (op)
gres.append(oper)
def do_endfuncsend(self):
self.extract_block(A_FUNCTION)
block = gres.pop()
op = (A_FUNCTION, [self.func, block])
gres.append(op)
def do_assignsend(self):
oper = (A_ASSIGN, [gres.pop(), global_stack.pop()])
gres.append(oper)
def do_returnsend(self):
oper = (A_RETURN, gres.pop())
gres.append(oper)
def do_printsend(self):
oper = (A_PRINT, gres.pop())
gres.append(oper)
def do_readsend(self):
oper = (A_READ, gres.pop())
gres.append(oper)
def do_whilesend(self):
gres.append(A_WHILE)
def do_endwhilesend(self):
self.extract_block(A_WHILE)
block = gres.pop()
op = (A_WHILE, [global_stack.pop(), block])
gres.append(op)
def m_default():
ptype = START_NODE
waitfor = links[ptype][0]
def istypeeq(token_type, state_type):
if state_type == None:
return True
else:
return token_type in links[state_type][1]
stack = []
gres.append(A_BLOCK)
current_line = -1
# func = None
state_executor = Machine()
while True:
token = (yield)
if hasattr(token, 'line'):
current_line = token.line
if ptype in EXPRESSIONS_STATES: # processed in other machine, so waiting for ';' or ':'
waitfor = links[ptype][0]
ctype = typeof(token)
# check syntax errors
possibles = reduce(lambda a, b: a + b, [[] if links[x][1] == None else list(links[x][1])
for x in waitfor])
if possibles is None:
possibles = []
else:
possibles = list(possibles)
possibles += RANGES_LIST
if possibles is not None and ctype not in possibles:
raise ParserError('Syntax error on line %d' % current_line)
if ctype == T_NO and token != None:
# FIXME: dead code?
raise ParserError(
"Unknown token '%s' on line %d" % (token, current_line))
# Next state
possibles = []
if len(waitfor) == 1: # single transition
possibles.append(waitfor[0])
else:
for possible in waitfor:
if istypeeq(typeof(token), possible):
possibles.append(possible)
if len(possibles) > 1:
raise ParserError("Syntax error: Ambiguity")
if len(possibles) == 0:
raise ParserError("Syntax error")
ptype = possibles[0]
# Process state
if links[ptype][2] is not None:
action = getattr(state_executor, "do_%s" % links[ptype][2])
state_executor.token = token
action()
waitfor = links[ptype][0]
# check instant states
if links[waitfor[0]][3]:
ptype = links[ptype][0][0]
waitfor = links[ptype][0]
if len(waitfor) == 1 and waitfor[0] in EXPRESSIONS_STATES:
m = m_expressions()
m.next()
machine.append(m)
stack.append(ctype)
ptype = waitfor[0]
def print_tree(t, n=0, f=sys.stdout):
if isinstance(t, list):
for x in reversed(t):
print_tree(x, n, f=f)
elif isinstance(t, tuple):
if t[0] in NAMES:
print("--" * n, NAMES[t[0]], file=f)
else:
print("--" * n, t[0], file=f)
print_tree(t[1], n=n + 1, f=f)
else:
print("--" * n, t, file=f)
./utils/gen.py
from __future__ import print_function
from functools import partial
from utils.const import *
from utils import ParserError, typeof
class TreeStats(object):
def __init__(self, vars=None, strs=None, funcs=None):
if vars is None:
vars = []
if strs is None:
strs = []
if funcs is None:
funcs = {}
self.vars = vars
self.strs = strs
self.funcs = funcs
self.use_print = False
self.use_read = False
def find_vars(t, stat=None, func=None):
if func is not None:
prefix = func.name + "_"
else:
prefix = ""
if stat == None:
stat = TreeStats()
if isinstance(t, list):
for x in reversed(t):
find_vars(x, stat=stat, func=func)
elif isinstance(t, tuple):
if t[0] == A_PRINT:
stat.use_print = True
elif t[0] == A_READ:
stat.use_read = True
if t[0] == A_FUNCTION:
stat.funcs[t[1][0].name] = {'args': t[1][0].args,
'args_count': len(t[1][0].args),
'info': t[1][0]}
for v in t[1][0].args:
var = "%s_%s" % (t[1][0].name, v)
stat.vars.append(var)
t[1][0].inner_vars.append(var)
find_vars(t[1][1], stat=stat, func=t[1][0])
else:
find_vars(t[1], stat=stat, func=func)
else:
if isinstance(t, str) and typeof(t) == T_VAR:
if prefix + t not in stat.vars:
stat.vars.append(prefix + t)
if func is not None:
func.inner_vars.append(prefix + t)
if isinstance(t, str) and typeof(t) == T_STRING:
if t not in stat.strs:
stat.strs.append(t)
return stat
def make_asm_node_p(p, cmd, o, v, shift=0):
p.text.append((cmd, o, v, shift,))
class PseudoAsm(object):
def __init__(self, p=None):
if p is None:
self.text = []
self.data = []
self.labelNum = 0
self.ifNum = 0
self.loopNum = 0
self.funcNum = 0
else:
self.text = p.text[:]
self.data = p.data[:]
self.labelNum = p.labelNum
self.ifNum = p.ifNum
self.loopNum = p.loopNum
self.funcNum = p.funcNum
def gen_text_section(t, stat, p=None, prefix=""):
if p is None:
p = PseudoAsm()
make_asm_node = partial(
make_asm_node_p, p=p, shift=(0 if len(prefix) == 0 else 1))
aa_push = partial(make_asm_node, cmd=C_PUSH)
aa_pop = partial(make_asm_node, cmd=C_POP, o=None)
aa_mov = partial(make_asm_node, cmd=C_MOV)
aa_call = partial(make_asm_node, cmd=C_CALL, o=None)
aa_add = partial(make_asm_node, cmd=C_ADD)
aa_sub = partial(make_asm_node, cmd=C_SUB)
aa_imul = partial(make_asm_node, cmd=C_IMUL, o=None)
aa_idiv = partial(make_asm_node, cmd=C_IDIV, o=None)
aa_cmp = partial(make_asm_node, cmd=C_CMP, o=None)
aa_jmp = partial(make_asm_node, cmd=C_JMP)
aa_label = partial(make_asm_node, cmd=C_LABEL, o=None)
aa_neg = partial(make_asm_node, cmd=C_NEG, o=None)
aa_push_num = partial(aa_push, o=C_OPT_NO)
aa_push_addr = partial(aa_push, o=C_OPT_ADDR)
aa_ret = partial(make_asm_node, cmd=C_RET, o=None, v=None)
iterate = t
if isinstance(t, list):
iterate = reversed(t)
if isinstance(t, (str, tuple)):
iterate = [t]
for node in iterate:
p.text.append((C_COMMENT, None, None))
if isinstance(node, str):
tnode = typeof(node)
if tnode == T_NUMBER:
aa_push_num(v=node)
elif tnode == T_VAR:
aa_push_addr(v="v%s" % prefix + node)
else:
raise ParserError(
"Error generating ASM code on node %s" % node)
elif node[0] == A_BLOCK:
gen_text_section(node[1], stat, p=p, prefix=prefix)
elif node[0] == A_FUNCTION:
p.funcNum += 1
p.text.append((C_COMMENT, None, None))
p.text.append((C_COMMENT, None, "Function %s" % node[1][0].name))
aa_jmp(o=None, v="Func%dEnd" % p.funcNum, shift=1)
aa_label(v="Func_%s" % node[1][0].name, shift=1)
for i, arg in enumerate(node[1][0].args):
var = "v%s_%s" % (node[1][0].name, arg)
aa_mov(o=[C_OPT_NO, C_OPT_ADDR], v=["eax",
"esp+%d" % ((i + 1) * 4)], shift=1)
aa_mov(o=[C_OPT_ADDR, C_OPT_NO], v=[var, "eax"], shift=1)
gen_text_section(
node[1][1], stat, p=p, prefix=node[1][0].name + "_")
aa_label(v="Func%dEnd" % p.funcNum, shift=1)
elif node[0] == A_RETURN:
# print (node[1])
aa_mov(
o=[C_OPT_NO, C_OPT_ADDR], v=["eax", "v%s" % prefix + node[1]])
# aa_push_num(v="eax")
aa_ret()
elif node[0] == A_PRINT:
if typeof(node[1]) == T_STRING:
strnum = stat.strs.index(node[1])
aa_push_num(v="str%d" % strnum)
aa_call(v="printf")
aa_add(o=[C_OPT_NO, C_OPT_NO], v=["esp", "4"])
aa_push_addr(v="stdout")
aa_call(v="fflush")
aa_add(o=[C_OPT_NO, C_OPT_NO], v=["esp", "4"])
elif typeof(node[1]) == T_VAR:
aa_mov(o=[C_OPT_NO, C_OPT_ADDR], v=["eax",
"v%s" % prefix + node[1]])
aa_push_num(v="eax")
aa_push_num(v="numbs")
aa_call(v="printf")
aa_add(o=[C_OPT_NO, C_OPT_NO], v=["esp", "8"])
aa_push_addr(v="stdout")
aa_call(v="fflush")
aa_add(o=[C_OPT_NO, C_OPT_NO], v=["esp", "4"])
else:
raise ParserError("Error print argument: %s" % node)
elif node[0] == A_READ:
assert typeof(node[1]) == T_VAR
aa_push_num(v="v%s" % prefix + node[1])
aa_push_num(v="numbs_in_format")
aa_call(v="scanf")
aa_add(o=[C_OPT_NO, C_OPT_NO], v=["esp", "8"])
aa_call(v="getchar")
elif node[0] == A_ASSIGN:
var = node[1][0]
gen_text_section(node[1][1], stat, p=p, prefix=prefix)
aa_pop(v="eax")
aa_mov(o=[C_OPT_ADDR, C_OPT_NO], v=["v%s" % prefix + var, "eax"])
elif node[0] == A_IF:
p.ifNum += 1
gen_text_section(node[1][0], stat, p=p, prefix=prefix)
aa_pop(v="eax")
aa_cmp(o=[C_OPT_NO, C_OPT_NO], v=["eax", "0"])
aa_jmp(o="jnz", v="llIf%dElse" % p.ifNum)
# then
gen_text_section(node[1][1], stat, p=p, prefix=prefix)
aa_jmp(o=None, v="llIf%dEnd" % p.ifNum)
# else
aa_label(v="llIf%dElse" % p.ifNum)
gen_text_section(node[1][2], stat, p=p, prefix=prefix)
aa_label(v="llIf%dEnd" % p.ifNum)
elif node[0] == '+':
gen_text_section(node[1], stat, p=p, prefix=prefix)
aa_pop(v="eax")
aa_pop(v="ebx")
aa_add(o=[C_OPT_NO, C_OPT_NO], v=["eax", "ebx"])
aa_push_num(v="eax")
elif node[0] in ['>=', '<=', '>', '<', '=']:
gen_text_section(node[1], stat, p=p, prefix=prefix)
p.labelNum += 1
op = {'>=': 'jge',
'<=': 'jle',
'>': 'jg',
'<': 'jl',
'=': 'je',
}
aa_pop(v="eax")
aa_pop(v="ebx")
aa_cmp(v=["eax", "ebx"])
aa_jmp(o=op[node[0]], v="ll%d" % p.labelNum)
aa_push_num(v="1")
aa_jmp(o=None, v="ell%d" % p.labelNum)
aa_label(v="ll%d" % p.labelNum)
aa_push_num(v="0")
aa_label(v="ell%d" % p.labelNum)
elif node[0] == '-':
gen_text_section(node[1], stat, p=p, prefix=prefix)
if len(node[1]) == 2:
aa_pop(v="eax")
aa_pop(v="ebx")
aa_sub(o=[C_OPT_NO, C_OPT_NO], v=["eax", "ebx"])
aa_push_num(v="eax")
else:
aa_pop(v="eax")
aa_neg(v="eax")
aa_push_num(v="eax")
elif node[0] == '*':
gen_text_section(node[1], stat, p=p, prefix=prefix)
aa_pop(v="eax")
aa_pop(v="ebx")
aa_imul(v="ebx")
aa_push_num(v="eax")
elif node[0] == '/':
gen_text_section(node[1], stat, p=p, prefix=prefix)
aa_pop(v="eax")
aa_pop(v="ebx")
aa_idiv(v="ebx")
aa_push_num(v="eax")
elif node[0] == '%':
gen_text_section(node[1], stat, p=p, prefix=prefix)
aa_pop(v="eax")
aa_pop(v="ebx")
aa_idiv(v="ebx")
aa_push_num(v="edx")
elif node[0] == A_WHILE:
p.loopNum += 1
aa_label(v="llWhile%d" % p.loopNum)
gen_text_section(node[1][0], stat, p=p, prefix=prefix)
aa_pop(v="eax")
aa_cmp(o=[C_OPT_NO, C_OPT_NO], v=["eax", "0"])
aa_jmp(o="jnz", v="llWhile%dEnd" % p.loopNum)
gen_text_section(node[1][1], stat, p=p, prefix=prefix)
aa_jmp(o=None, v="llWhile%d" % p.loopNum)
aa_label(v="llWhile%dEnd" % p.loopNum)
elif node[0] == A_CALL:
if stat.funcs[node[1]]['args_count'] != len(node[2]):
raise ParserError("Call %s passing %d arguments. %d expected" %
(node[1], len(node[2]), stat.funcs[node[1]]['args_count']))
for iv in stat.funcs[node[1]]['info'].inner_vars:
aa_push_addr(v="v%s" % iv)
for arg in reversed(node[2]):
gen_text_section(arg, stat, p=p, prefix=prefix)
aa_call(v="Func_%s" % node[1])
aa_add(o=[C_OPT_NO, C_OPT_NO], v=["esp", str(4 * len(node[2]))])
for iv in reversed(stat.funcs[node[1]]['info'].inner_vars):
aa_pop(v="edx")
aa_mov(o=[C_OPT_ADDR, C_OPT_NO], v=["v%s" % iv, "edx"])
aa_push_num(v="eax")
elif node[0] in ['/', '%']:
raise NotImplementedError(
"%s operation is not implemented yet" % node[0])
else:
raise ParserError(
"Error generating ASM code on node %s" % repr(node))
def clear_string(s):
r = s
r = "\",10,\"".join(r.split("\\n"))
return r
def gen_code(t, stat):
p = PseudoAsm()
p.data.append((C_EQU, "_kernel_", "0x80"))
p.data.append((C_COMMENT, None, "Strings"))
for i, vs in enumerate(stat.strs):
s = clear_string(vs)
p.data.append((C_DB, "str%d" % i, "%s, 0" % s))
p.data.append((C_EQU_F, "lstr%d" % i, "str%d" % i))
p.data.append((C_DB, "numbs", "\"%d\", 0"))
p.data.append((C_DB, "numbs_in_format", "\"%d\",0"))
p.data.append((C_COMMENT, None, "Variables"))
for i, vs in enumerate(stat.vars):
p.data.append((C_DD, "v%s" % vs, "0"))
p.text.append((C_GLOBL, None, "_start"))
extern = []
if stat.use_print:
extern.append("printf")
if stat.use_read:
extern.append("scanf")
extern.append("getchar")
if stat.use_read or stat.use_print:
extern.append("fflush")
extern.append("stdout")
for e in extern:
p.text.append((C_EXTRN, None, e))
p.text.append((C_LABEL, None, "_start"))
p.text.append((C_COMMENT, None, "setup stack frame"))
p.text.append((C_PUSH, C_OPT_NO, "ebp"))
p.text.append((C_MOV, [C_OPT_NO, C_OPT_NO], ["ebp", "esp"]))
gen_text_section(t, stat, p=p)
# end
p.text.append((C_COMMENT, None, "restore stack frame"))
p.text.append((C_MOV, [C_OPT_NO, C_OPT_NO], ["esp", "ebp"]))
p.text.append((C_POP, None, "ebp"))
p.text.append((C_MOV, [C_OPT_NO, C_OPT_NO], ["ebx", "0"]))
p.text.append((C_MOV, [C_OPT_NO, C_OPT_NO], ["eax", "1"]))
p.text.append((C_INT, None, "_kernel_"))
return p
./utils/optimizer.py
from utils.const import *
from utils.gen import PseudoAsm
def optimize(pseudo, num=2):
text = pseudo
for x in xrange(num):
text = do_optimize(text)
return text
def do_optimize(pseudo):
pseudo = PseudoAsm(pseudo)
text = pseudo.text
text = optimize_push_pop(text)
text = optimize_mov(text)
text = optimize_mov_push(text)
text = optimize_mov_to_self(text)
text = optimize_clean_lines(text)
pseudo.text = text
return pseudo
def optimize_mov_to_self(text):
" reduce mov (mov eax,eax) "
result = []
for i, op in enumerate(text):
if op[0] == C_MOV:
if (op[2][0] == op[2][1]) and (op[1][0] == op[1][1]):
pass
else:
result.append(op)
else:
result.append(op)
return result
def optimize_push_pop(text):
" reduce push and pop sequences "
stack = []
result = []
ires = []
for i, op in enumerate(text):
if len(op) > 3:
offset = op[3]
else:
offset = 0
if op[0] == C_PUSH:
stack.append(op)
elif op[0] == C_POP:
if len(stack) > 0:
v = stack.pop()
can_reduce = True
for s in ires:
if s[0] == C_MOV:
can_reduce = can_reduce and (
s[2][0] != v[2]) and (s[2][1] != v[2])
if can_reduce:
ires.append(
(C_MOV, [C_OPT_NO, v[1]], (op[2], v[2]), offset))
else:
ires.insert(0, v)
ires.append(op)
else:
ires.append(op)
elif op[0] == C_COMMENT:
result.append(op)
else:
result += stack
stack = []
result += ires
ires = []
result.append(op)
result += stack
return result
def optimize_mov(text):
" reduce mov twice (mov eax, 5; mov ebx, eax)"
prev_mov = None
result = []
comments = []
for i, op in enumerate(text):
if len(op) > 3:
offset = op[3]
else:
offset = 0
if op[0] == C_MOV:
if prev_mov is not None:
v = prev_mov
if (v[2][0] == op[2][1]) and (v[1][0] == op[1][1]) and \
(not (op[1][0] == v[1][1] and op[1][0] == C_OPT_ADDR)):
result.append((C_MOV, [op[1][0], v[
1][1]], (op[2][0], v[2][1]), offset))
prev_mov = None
else:
result.append(prev_mov)
prev_mov = op
else:
prev_mov = op
elif op[0] == C_COMMENT:
comments.append(op)
else:
if prev_mov is not None:
result.append(prev_mov)
prev_mov = None
result += comments
comments = []
result.append(op)
if prev_mov is not None:
result += prev_mov
return result
def optimize_mov_push(text):
" reduce mov before push (mov eax, 5; push eax) "
prev_mov = None
result = []
comments = []
ires = []
for i, op in enumerate(text):
if len(op) > 3:
offset = op[3]
else:
offset = 0
if op[0] == C_MOV:
if prev_mov is not None:
ires.append(prev_mov)
prev_mov = op
elif op[0] == C_PUSH:
if prev_mov is not None:
v = prev_mov
if (v[2][0] == op[2]) and (v[1][0] == op[1]) and (v[1][0] != C_OPT_ADDR):
ires.append((C_PUSH, v[1][1], v[2][1], offset))
else:
ires.append(prev_mov)
ires.append(op)
else:
ires.append(op)
prev_mov = None
elif op[0] == C_COMMENT:
comments.append(op)
else:
if prev_mov is not None:
ires.append(prev_mov)
prev_mov = None
result += comments
comments = []
result += ires
ires = []
result.append(op)
if prev_mov is not None:
result += prev_mov
return result
def optimize_clean_lines(text):
result = []
n = 0
for i, op in enumerate(text):
if op[0] == C_COMMENT:
if op[2] == None or op[2] == "":
n += 1
if n < 2:
result.append(op)
else:
result.append(op)
else:
result.append(op)
n = 0
return result
./utils/gen_asm.py
from __future__ import print_function
from time import strftime, gmtime
from utils.const import *
from utils import ParserError
def gen_real_asm(pseudo, src_file):
res = []
res.append("; Source file: %s" % src_file)
res.append("; Generated %s" % strftime("%Y-%m-%d %H:%M:%S", gmtime()))
res.append("")
res.append("SECTION .data")
res.append("")
for command in pseudo.data:
res += nasm_gen(command)
res.append("")
res.append("SECTION .text")
res.append("")
for command in pseudo.text:
res += nasm_gen(command)
return res
def operand(x, t):
if t == C_OPT_NO:
return x
elif t == C_OPT_ADDR:
return "[%s]" % x
def nasm_gen(l):
cmd = None
if l[0] == C_PUSH:
cmd = ["push\tdword\t%s" % operand(l[2], l[1])]
elif l[0] == C_POP:
cmd = ["pop\t\tdword\t%s" % l[2]]
elif l[0] == C_CALL:
cmd = ["call\t%s" % l[2]]
elif l[0] == C_INT:
cmd = ["int\t%s" % l[2]]
elif l[0] == C_MOV:
cmd = ["mov\t\tdword\t%s, %s" % (operand(l[2][0], l[1][0]),
operand(l[2][1], l[1][1]))]
elif l[0] == C_ADD:
cmd = ["add\t\t%s, %s" % (operand(l[2][0], l[1][0]),
operand(l[2][1], l[1][1]))]
elif l[0] == C_IMUL:
cmd = ["imul\t%s" % l[2]]
elif l[0] == C_IDIV:
cmd = ["idiv\t%s" % l[2]]
elif l[0] == C_SUB:
cmd = ["sub\t\t%s, %s" % (operand(l[2][0], l[1][0]),
operand(l[2][1], l[1][1]))]
elif l[0] == C_CMP:
cmd = ["cmp\t%s,%s" % (l[2][0], l[2][1])]
elif l[0] == C_COMMENT:
if l[2] is None:
cmd = [""]
else:
cmd = ["; %s" % l[2]]
elif l[0] == C_EQU:
cmd = ["%s:\tequ\t%s" % (l[1], l[2])]
elif l[0] == C_EQU_F:
cmd = ["%s:\tequ\t\t$-%s" % (l[1], l[2])]
elif l[0] == C_DB:
cmd = ["%s:\tdb\t\t%s" % (l[1], l[2])]
elif l[0] == C_DD:
cmd = ["%s:\t\tdd\t%s" % (l[1], l[2])]
elif l[0] == C_GLOBL:
cmd = ["global\t%s" % l[2]]
elif l[0] == C_EXTRN:
cmd = ["extern\t%s" % l[2]]
elif l[0] == C_NEG:
cmd = ["neg\t%s" % l[2]]
elif l[0] == C_LABEL:
cmd = ["%s:" % l[2]]
elif l[0] == C_JMP:
if l[1] is None:
cmd = ["jmp\t%s" % l[2]]
else:
cmd = ["%s\t%s" % (l[1], l[2])]
elif l[0] == C_RET:
cmd = ["ret"]
else:
raise ParserError("Can't translate %d command" % l[0])
cmd = map(lambda x: "\t%s" % x, cmd)
if len(l) > 3:
return map(lambda x: "%s%s" % (l[3] * "\t", x), cmd)
else:
return cmd