Метод раскрутки

Компилятор – это весьма большая и сложная программа; на написание и отладку компилятора на языке ассемблера можно истратить слишком много времени. Для того, чтобы как-то справиться с этой проблемой, был придуман метод раскрутки, суть которого заключается в следующем.

Пусть есть компилятор K_A: P→A, гдеP– некоторый язык более высокого уровня, чем язык ассемблера. Тогда напишемK_P: L→A, а затем применим компиляторK_Aк компиляторуK_P, т.е. получимK_A=K_A(K_P): L→A. Такая схема проиллюстрирована с помощью Т-диаграмм на слайде и называетсяраскруткой(bootstrapping²); компиляторK_P как бы "раскручивается" с помощью компилятораK_A.

Описанная схема может быть использована при написании компилятора некоторого языка на нем самом. Пусть у нас есть компилятор некоторого подмножества S языкаLв языкA, написанный на языкеA,K_A: S→A. Тогда мы можем написатьK_L: L→Aи получим новый компиляторK_A = K_A(K_L). Мы используем это подмножествоSдля того, чтобы написать компилятор языкаLв языкA,K_S: L→A. Если теперь мы применим компиляторK_Aк программеK_S, то получимK_A=K_A(K_S): L→A.

Впервые такая схема была применена в 1960 году при реализации языка Neliac. В 1971 году Вирт написал с использованием раскрутки транслятор языкаPascal, причем самый первый компилятор был оттранслирован вручную. Количество шагов раскрутки было больше 1, т.е. была построена последовательность языков и построена последовательность компиляторов:K_A: S₁→A, K_A¹=K_A(K_S1: S₂→A), ...

Раскрутку можно использовать и в следующей ситуации. Пусть у нас есть недостаточно эффективный компилятор K_­A: L→A. Можно написать более эффективный компиляторK_L: L→A, а затем применить раскрутку.