Шинка пісочиння

Текст увійшов, машинний код вийшов, чотири етапи між ними

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

жива демонстрація · пов'язана симуляція● LIVE

Лексичний аналіз: символи у токени

Лексер (або сканер) читає необроблені символи та групує їх у токени – найменші значущі одиниці: числа, ідентифікатори, оператори, ключові слова, розділові знаки. Білі простори та коментарі зазвичай відкидаються тут. Внутрішньо лексер майже завжди є кінцевою машиною станів, еквівалентною великому регулярному виразу: він може розпізнати 42.5 як один ТОКЕН числа в одному проход без необхідності дивитися далі вперед, ніж на наступний символ, оскільки синтаксис чисел є регулярним.

input:   "12 + 3 * x"
tokens:  NUM(12)  PLUS  NUM(3)  STAR  IDENT(x)

Розбір: токени в дерево

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

12 + 3 * x розглядається як (+ 12 (* 3 x)) не як (* (+ 12 3) x) тому що * має вищий пріоритет, ніж +, тому аналізатор заходить у "3 * x" перед поверненням для завершення додавання Двозначні граматики — відомий приклад проблеми «висхідного else», де if (a) if (b) s1; else s2; може бути прикріплено до будь-якого з if — вирішуються за допомогою фіксованої конвенції (прикріплюється до найближчого невідповідного if), а не залишається на розсуд.

12 + 3 * x   parses as   (+ 12 (* 3 x))     not   (* (+ 12 3) x)

because * has higher binding power than +, so the parser
descends into "3 * x" before returning to finish the addition

Codegen: дерево до трьох адресних коду

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

AST: (+ 12 (* 3 x)) tрьох адресний код: t1 = 3 * x t2 = 12 + t1 Кожна трьох адресна інструкція майже безпосередньо відображається на невелику кількість реальних машинного коду (завантаження, множення, додавання, збереження), тому ця проміжна форма є стандартною точкою передачі між переднім кінцем компілятора (специфічним для мови) та заднім кінцем (специфічним для цільового пристрою): перенаправлення на нову CPU означає переписування лише невеликого кінцевого кроку з трьох адресного коду до інструкцій цієї CPU.

AST:  (+ 12 (* 3 x))

three-address code:
  t1 = 3 * x
  t2 = 12 + t1

Оптимізація: константне розгортання та далі

Між генерацією коду та остаточною емісією знаходяться проходи оптимізації, які покращують код без зміни його значення. Найпростіший і найуніверсальніший з них — константне розгортання: якщо операнди інструкції обидва відомі під час компіляції, оцінюйте їх один раз під час компіляції замість кожного запуску.

до: після константного розгортання: t1 = 3 * 4 t1 = 12 t2 = t1 + x t2 = 12 + x (подальші розгортання, якщо x також є сталою) Реальні компілятори ланцюжать десятки таких переходів — видалення мертвого коду, вилучення спільних підпрограм, спрощення коду, вкладення функцій, розподіл регістрів — кожен з них невелике переписування, яке зберігає значення, що виконується повторно до тих пір, поки нічого не змінюється. Інтерактивна демонстрація вище реалізує лише основні елементи — ліквідатор, рекурсивний розбірник, генерація коду на трьох адресах та один прохід константного розгортання, але будь-який повноцінний компілятор, від JavaScript двигуна JIT до GCC, будується з цих чотирьох етапів, просто з більшою кількістю їх ланцюжків.

before:                  after constant folding:
  t1 = 3 * 4               t1 = 12
  t2 = t1 + x               t2 = 12 + x   (further folds if x is also constant)

Frequently asked questions

Чому розділити розпізнавання лексем та синтаксичний аналіз на дві окремі стадії замість однієї?

Розпізнавання лексем — це простіша задача (регулярні мови, оброблювані кінцевою машиною), ніж синтаксичний аналіз (безвільні мови, які потребують стека або рекурсії для відстеження вкладеності). Розділення цих стадій дозволяє швидкому та простому розпізнавачу видаляти пробіли та коментарі та групувати символи в токени, щоб більш дорогий аналізатор завжди міг міркувати лише над коротким і чистим потоком токенів замість необроблених символів.

Що саме додає Абстрактне Синтаксичне Дерево, чого не має список токенів?

Структура та пріоритет. Список токенів — це плоский об'єкт, який не має жодного уявлення про те, який оператор застосовується до яких операндів першим. AST вкладе підвиражання так, щоб «3 * x» було дитиною вузла + в «12 + 3 * x», що безпосередньо кодує, що множення має бути виконане перед додаванням, не потребуючи окремої таблиці пріоритетів під час генерації коду.

Чи змінює постійне розгортання те, що програма обчислює?

Ні — це точно обмеження для кожного пропуску оптимізації. Постійне розгортання замінює вираз на значення, яке воно вже гарантовано виробляє під час виконання; якщо є сумніви (змінна, значення якої невідоме під час компіляції, або операція, яка може викликати виняток з різними значеннями), пропуск залишає код без змін.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Compiler Pipeline і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію Compiler Pipeline

Всередині компілятора: від вихідного тексту до машинного коду