простий компілятор

Про проектування компіляторів написані книги. Нижченаведений текст їх не замінить, але, сподіваюся, дозволить отримати елементарне уявлення про будову компіляторів. Коли я вирішив написати компілятор, я намагався відразу реалізувати досить багато можливостей, помітно більше, ніж потрібно для написання самого компілятора. Це вдалося, але вийшов компілятор містить багато деталей, що ускладнюють його розуміння. Частина деталей пов'язана з можливостями мови, інша частина - з процесором 8086 (80386 зручніше, але тоді я цього не знав, та й 32-х розрядні операційні системи ще не поширилися). І звичайно, багато що можна було зробити краще. У якийсь момент я зменшив компілятор, але зовсім маленьким він не став. Значно зменшити компілятор можна за рахунок спрощення вхідного мови, що тут і зроблено. Наведений тут іграшковий компілятор для практичних цілей непридатний, але він побудований так само, як і справжній.

901 FORMAT (1X, 'N =', I2 /) N = 0 10 DO 20 I = 1.5 N = N +1 20 CONTINUE WRITE (6,901) N STOP END

Тема циклу в рядку з міткою 10 містить друкарську помилку (точка замість коми, на клавіатурі вони поруч), але Fortran вважатиме, що це привласнення константи 1.5 змінної з ім'ям DO20I. Відповідно, на друк буде буде виведено число 1, а не 5.

Не тільки сканер, але і компілятор в цілому залежить від вхідного мови, тому краще перейти до приватного і розглянути конкретну мову - Context.

Програма на мові Context є послідовність визначень:

констант
типів (структур)
глобальних змінних
функцій

їх взаємне розташування в програмі обмежена тільки однією умовою - кожен об'єкт повинен бути визначений до його використання, завершує програму головна функція. Для деяких об'єктів, наприклад, функцій досить лише об'явненія, але в мінімальній версії це не буде реалізовано.

Визначення константи, структури і головної функції распознаетмся за першим словом (define, struct і begin відповідно), визначення функції і глобальної змінної починаються з імені типу і один від одного відрізняються наявністю і відсутністю круглої дужки після імені. Тобто після імені типу треба прочіталь символи @ (якщо вони є), саме ім'я і наступне за ним слово. Якщо це слово - кругла дужка, то повинен виконуватися розбір функції, інакше - розбір глобальної змінної. В інших мовах функція визначається за першим словом, в Pascal'е, наприклад, функція починається зі слова function, а список змінних зі слова var.

Таким чином, на верхньому рівні компілятор може складатися з простого циклу:

while TRUE do Scan (@Buff); select case strcmp (@Buff, "begin") = 0: // Розбір головної функції exit case strcmp (@Buff, "define") = 0: // Розбір константи case strcmp (@Buff, "struct") = 0: // Розбір структури default: // Розбір глобальної змінної або функції end end

Зрозуміло, кожна з гілок select'а повинна містити певний код. Розбір констант і структур досить простий (тим більше, в Context'е структури нерекурсівние - на відміну від Pascal їх визначення не можуть бути вкладеними), результатом розбору є нові записи в таблиці глобальних імен, ніякого коду не створюється. Розбір функцій складніше. Він складається з розбору заголовка зі списком параметрів (що дуже схоже на розбір структури) і розбору входять до функцію операторів. Якщо написана функція Ctrl, компілює один оператор, компіляція всієї функції зводиться до циклу з трьох рядків:

while strcmp (@Scan (@Buff), "end")! = 0 do Ctrl (@Buff); end

Для подальшого, проте, потрібно змінити цей цикл і функцію Ctrl:

// Scan (@Buff); while strcmp (@Buff, "end")! = 0 do Ctrl (@Buff); // Ctrl повинна зчитувати наступне за оператором слово end

word F (); word G () F (); end

Після закриває дужки може зустрітися крапка з комою (F) або початок першого оператора функції (G). Після зчитування закриває дужки необхідно вважати наступне слово і, якщо це не крапка з комою, запам'ятати його і перейти до компіляції операторів, другий варіант циклу пристосований для цього. За рахунок зміни мови можна відновити працездатність першого варіанту:

word F (); word G () is F (); end

Тут після закриває дужки завжди є слово (крапка з комою або is).

Всі оператори, які можуть зустрітися в функції, розпізнаються по першому слову, тому на верхньому рівні Ctrl може бути влаштована так:

За допомогою функції Expr розбір циклу while може бути виконаний так:

// Генеpация коду @A: nop; початок циклу // Виклик функції Expr, // завантаженні pезультата в AL // Генеpация коду or AL, AL // jnz @B // jmp. // @B: nop while strcmp (@Buff, "end")! = 0 do Ctrl (@Buff); end // Генеpация коду jmp @A @C: nop // Коригування переходу jmp. (Jmp @C)

Це не всі необхідні дії, ще потрібно виконати підготовку до компіляції операторів loop / exit і до розбору певних всередині циклу локальних змінних. Але це вже деталі, головне тут те, що цикл, як і функція, включає послідовність операторів і для їх компіляції може бути використана сама функція Ctrl так само, як вона використовується для компіляції всієї функції.

Умова циклу компілюється не кращим чином. Як мінімум, генеруються зайві команди (or AL, AL.), Але зараз простота важливіше ефективності. Також з наведеного фрагменту неясно, як буде скомпільовано складну умову, що містить логічні оператори І / АБО, чи буде реалізована повна або коротка оцінка умови. Це питання має бути вирішене при написанні функції Expr. Мабуть, повне обчислення з використанням регістра для зберігання результату є найбільш простим, в деяких мовах (наприклад в оригінальному Pascal) так і зроблено. Так зроблено і в Context'е, але це не найкраще рішення.

void Expr (word Prty; char @Buff; OpInfo @ Op1) select case strcmp (@Buff, "(") = 0: // вираденія в дужках case strcmp (@Buff, " '") = 0: // символьна константа case strcmp (@Buff, "#") = 0: // символьна константа case isdigit (Buff) = 0: // числова константа default: // Змінна, виклик функції end while TRUE do word Sign; word P2; select case strcmp (@Buff, "|") = 0: Sign = OR; P2 = 1; case strcmp (@Buff, "") = 0: Sign = AND; P2 = 1; case strcmp (@Buff, "

Варто відзначити, що так написана функція Expr завжди зчитує зайве слово. Це може бути крапка з комою, двокрапка, then, do.

Ідеї сформульовані і ось як вони реалізовані в 'іграшковому' компіляторі. Спрощення досягнуто в першу чергу за рахунок спрощення мови. Тільки один тип даних - ціле (але умови вважаються логічними), визначення нових типів неможливо, тільки одномірні масиви, немає функцій і локальних змінних, немає довідкових змінних. І ніяких спроб оптимізації. Власне компілятор починається з функції Read:

define @emNOMEMORY "Недостатньо пам'яті" define @emSIZE "Занадто довгий идентификатоp" define @emEOF "Кінець файлу" define @emNUMBER "Помилка в константі" define @emNAME "Пpопущено ім'я" define @emEMPTY "Порожній масив" define @emBRACKET "Пpопущена дужка "define @emCOMMA" Пpопущена кома "define @emSEMICOLON" Пpопущена крапка з комою "define @emTHENEXP" Пpопущено then "define @emDOEXP" Пpопущено do "define @emDUP" повтоpно опис "define @emLVALUE" Пpопущена змінна "define @emTYPE" Невідповідність типів "define @emUNDEFINED" пеpеменной НЕ опpеделена "define @emUNDEFOPR" опеpаций НЕ опpеделена "define @emASSIGN" Пpопущено = "define tbSIZE 8192 define dbSIZE 8192 define dtSIZE 128 define idSIZE 16 define opOR 1 define opAND 2 de fine opLT 3 define opLE 4 define opEQ 5 define opNE 6 define opGE 7 define opGT 8 define opADD 9 define opSUB 10 define opMUL 11 define opDIV 12 define opNOT 13 define opNEG 14 define ptZERO 0 define ptBOOL 1 define ptCOMP 2 define ptADD 3 define ptMUL 4 define ptLVALUE 5 define ttWORD 0 define ttBOOL 1 struct DATA char Name [idSIZE]; word Ofs; word Index; end DATA Data [dtSIZE]; word nData; word Ofs; char Text [tbSIZE]; word hText; word nText; word pText; char Name [128]; word Line; word Label; char Dest [dbSIZE]; word hDest; word pDest; void @Ptr (word Seg, Ofs) void @ P1 = @ Ofs; void @@ P2 = @ P1; return @ P2; end word isalpha (char Ch) if ( 'A' 0 then dec S; end word P = 0; if N> = 10 | S> 0 then P = str (N / 10, S, @ Buff); end char @ D = "0123456789"; Buff [P] = D [N% 10]; return P + 1; end char @Str (word N; word S) char @ P = "00000"; P [str (N, S, @P)] = # 0; return @P; end void Stop (char @EM) putc (# 13); puts (@Name); putc ( '('); puts (@Str (Line, 0)); putc ( ')'); if (strlen (@EM)> 0) then puts ( ":"); puts (@EM); end close (hDest); close (hText); asm mov AX, 4C00H asm int 21H end word Val (char @Buff) char @D = "0123456789"; word P = 0; word L = 0; word H = 0; while Buff [P]! = # 0 do word S = 0; while D [S ]! = Buff [P] do inc S; if S> = 10 then Stop (@emNUMBER); end end S = 10 * L + S, L = S% 256; S = 10 * H + S / 256; H = S% 256; S = S / 256; if S> 0 then Stop (@emNUMBER); end inc P; end return 256 * H + L; end char Read () if pText> = nText then nText = read (hText , @ Text, tbSIZE); if nText = idSIZE then Stop (@emSIZE); end Next (); end if P = 0 then Buff [P] = Read (); inc P; Next (); select case Buff [0 ] = '': if Read () = '=' then Next (); return @strcpy (@Buff, "> ="); end end end Buff [P] = # 0; return @Buff; end void Save (char Ch) if pDest> = dbSIZE then Stop (@emNOMEMORY); end Dest [pDest] = Ch; inc pDest; end void Decl (char @Inst) word I = 0; while Inst [I]! = # 0 do Save (Inst [I]); inc I; end Save (# 13); Save (# 10); end void Code (word L; char @Inst) if L! = 0 then Save ( '@'); char @ P = @ Str (L, 5); word I = 0; while P [I]! = # 0 do Save (P [I]); inc I; end Save ( ':'); Save ( ''); else word I = 0; while I = nData then Stop (@emUNDEFINED); end if Data [N] .Index> 0 then if strcmp (@Scan (@Buff), "[")! = 0 then Stop (@emBRACKET); end if Expr (ptZERO, @ Scan (@Buff))! = ttWORD then Stop (@emTYPE); end if strcmp (@Buff, "]")! = 0 then Stop (@emBRACKET); end if Prty

= PtLVALUE then if Flag = 0 then Stop (@emLVALUE); end return N; end while TRUE do word Op; word P; select case strcmp (@Buff, "|") = 0: Op = opOR; P = ptBOOL; case strcmp (@Buff, "") = 0: Op = opAND; P = ptBOOL; case strcmp (@Buff, "=") = 0: Op = opGE; P = ptCOMP; case strcmp (@Buff, ">") = 0: Op = opGT; P = ptCOMP; case strcmp (@Buff, "+") = 0: Op = opADD; P = ptADD; case strcmp (@Buff, "-") = 0: Op = opSUB; P = ptADD; case strcmp (@Buff, "*") = 0: Op = opMUL; P = ptMUL; case strcmp (@Buff, "/") = 0: Op = opDIV; P = ptMUL; default: P = ptZERO; end if P = nData then Stop (@emUNDEFINED); end if strcmp (@Buff, "=")! = 0 then Stop (@emASSIGN); end if Data [N] .Index> 0 then Code (0, "push AX"); end if Expr (ptZERO, @ Scan (@Buff))! = ttWORD then Stop (@emTYPE); end if Data [N] .Index> 0 then Code (0, "pop BX"); Code (0, "shl BX, 1"); Code (0, @ strcat (@strcat (@strcpy (@Buff, "mov DS: [BX +"), @ Str (Data [N] .Ofs, 0)), "], AX")); else Code (0, @ strcat (@strcat (@strcpy (@Buff, "mov DS: ["), @ Str (Data [N] .Ofs, 0)), "], AX")); end end end begin byte @ Size = @ Ptr (GetPSP (), 128); char @ Parm = @ Ptr (GetPSP (), 129); char name [128]; word I = 0; while I = dtSIZE then Stop (@emNOMEMORY); end Data [nData] .Ofs = 2 * Ofs; strcpy (@Data [nData] .Name, @ Buff); Data [nData] .Index = 0; word N = 1; if strcmp (@Scan (@Buff), "[") = 0 then N = Val (@Scan (@Buff)); if N

З коштів введення / виведення реалізовані лише оператор write, виводить на друк числа і оператор blank, який виконує переклад рядка. Для демонстрації можна скомпілювати і виконати наступну програму сортування масиву:

word Buff [16]; word Temp; word I; word J; word N; begin N = 10; I = 0; while I 0 do I = I-1; J = 0; while J Buff [J + 1] then Temp = Buff [J + 1]; Buff [J + 1] = Buff [J]; Buff [J] = Temp; end J = J + 1; end end blank I = 0; while I

Повна версія компілятора складніше, але і в ній зроблені спрощення. Вони пов'язані з обов'язковим розміщенням операндів в регістрах, причому це розміщення фіксовано:

все аpіфметіческіе і логічні опеpации виконуються тільки в регістри
пеpвая опеpанд pазмещаются в регістри AL (байт), AX (слово) або DX: AX (подвійне слово)
втоpой опеpанд pазмещаются в регістри BL (байт), BX (слово) або CX: BX (подвійне слово)
pезультат опеpации pазмещаются в регістри AL (байт), AX (слово) або DX: AX (подвійне слово)
pегистp DI використовується для обpащения до елементу масиву
регістри ES: DI використовуються для pазіменованія покажчиків
якщо потрібний pегистp зайнятий, значення з нього вpеменно поміщається в стек
пpи викликах функцій параметри пеpедаются чеpез стек, параметри видаляються з стека пеpед завеpшения функції, pезультат функції повертається в регістри AL (байт), AX (слово) або DX: AX (подвійне слово), з метою упpощенія pезультат функції може мати довжину тільки 1, 2 або 4 байти.
глобальні змінні знаходяться в сегменті, адpесуемом регістром DS

Основні блоки компілятора наступні:

void Stop (char @EM) // завеpшения компіляції. end void Code (word L; char @S) // Фоpмиpование стpоки коду. end char Read () // Читання символу. end void Next () // Пеpеход до наступного символу. end char @Scan (char @Buff) // Читання слова. end void Init () // Ініціалізація (для Expr). end void Push (word R) // Запис регістра в стек. end void Pop (word R) // Витяг з стека. end void LDAX (OpInfo @ Op1) // завантаженні першого опеpанда в (DX:) AX. end void LDBX (OpInfo @ Op1) // завантаженні другого опеpанда в (CX:) BX. end void LPTR (OpInfo @ Op1) // завантаженні покажчика в ES: DI. end void STAX (OpInfo @ Op1) // Запис pезультата в пам'ять. end word Comp (word Size; char @Jump) // сpавнения. end void Test (word pType1; word nPtr1; OpInfo @ Op2) // пpовеpками. // спільності типів end void Expr (word P; char @Buff; OpInfo @ Op1) // Компіляція. // вираження end void Ctrl (char @Buff) // Компіляція блоку. end begin. while (strcmp (@Scan (@Buff), "begin")! = 0) do if (strcmp (@Buff, "define") = 0) then // Pазбоp константи. loop end if (strcmp (@Buff, "struct") = 0) then // Pазбоp стpуктуp. loop end P = FindType (@Buff); if (P

Потрібно сказати кілька слів про модифікацію компілятора. Зроблені при цьому помилки можуть не проявитися після одноразової компіляції. Тобто якщо за допомогою компілятора A компілюється текст компілятора A '(виправленого і доповненого A) і при цьому не виявляється синтаксичних або семантичних помилок, компілятор A' ймовірно зможе скомпілювати себе, але отриманий компілятор A '' може бути непрацездатний.

І останнє зауваження. Компілятор створює лістинг, трохи відмінний від тpебуемого для ассемблеpа TASM. Якщо ви хочете використовувати TASM / TLINK, в початок потрібно додати стpоки

CODE segment assume CS: CODE org 100H @ 00001: nop

CODE ends end @ 00001

Сайт створено в системі uCoz