Давайте создадим компилятор!

В следующей главе мы применим ту же самую методику для создания законченного транслятора подмножества языка KISS, который я буду называть TINY. Но одна из моих целей в этой серии состоит в том, чтобы вы не только могли увидеть как работает компилятор для TINY или KISS, но чтобы вы также могли разрабатывать и создавать компиляторы своих собственных языков. Примеры Си и Паскаля помогут вам в этом. Одна вещь, которую я хотел чтобы вы увидели, состоит в том, что естественная структура компилятора очень сильно зависит от транслируемого языка, поэтому простота и легкость конструирования компилятора очень сильно зависит от того, позволите ли вы языку определять структуру программы.

Немного сложнее получить полный компилятор C или Pascal, да мы и не будем. Но мы можем расчистить верхние уровни так, чтобы вы увидели как это делается.

Давайте начнем.

ВЕРХНИЙ УРОВЕНЬ

Одна из самых больших ошибок людей при нисходящем проектировании заключается в неправильном выборе истинной вершины. Они думают, что знают какой должна быть общая структура проекта и поэтому они продолжают и записывают ее.

Всякий раз, когда я начинаю новый проект, я всегда хочу сделать это в самом начале. На языке разработки программ (program design language – PDL) этот верхний уровень походит на что-нибудь вроде:

begin

solve the problem

end

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

В нашем случае, общая функция компилятора заключается в компиляции законченной программы. С этого начинается любое определение языка, записанное в БНФ. На что походит верхний уровень БНФ? Хорошо, это немного зависит от транслируемого языка. Давайте взглянем на Pascal.

СТРУКТУРА ПАСКАЛЯ

Большинство книг по Pascal включают БНФ определение языка. Вот несколько первых строк одного из них:

::= '.'

::= PROGRAM

::=

Мы можем написать подпрограммы распознавания для работы с каждым из этих элементов подобно тому, как мы делали это прежде. Для каждого из них мы будем использовать знакомые нам односимвольные токены, затем понемногу расширяя их. Давайте начнем с первого распознавателя: непосредственно программы.

Для ее трансляции мы начнем с новой копии Cradle. Так как мы возвращаемся к односимвольным именам мы будем просто использовать "p" для обозначения «program».

К новой копии Cradle добавьте следующий код и вставьте обращение к нему из основной программы:

{–}

{ Parse and Translate A Program }

procedure Prog;

var Name: char;

begin

Match('p'); { Handles program header part }

Name := GetName;

Prolog(Name);

Match('.');

Epilog(Name);

end;

{–}

Процедуры Prolog и Epilog выполняют все, что необходимо для связи программы с операционной системой так чтобы она могла выполняться как программа. Само собой разумеется, эта часть будет очень ОС-зависима. Помните, что я выдаю код для 68000, работающий под ОС, которую я использую – SK*DOS. Я понимаю, что большинство из вас использует PC и вы предпочли бы увидеть что-нибудь другое, но я слишком далеко зашел, чтобы что-то сейчас менять!

В любом случае, SK*DOS особенно простая для общения операционная система. Вот код для Prolog и Epilog:

{–}

{ Write the Prolog }

procedure Prolog;

begin

EmitLn('WARMST EQU $A01E');

end;

{–}

{ Write the Epilog }

procedure Epilog(Name: char);

begin

EmitLn('DC WARMST');

EmitLn('END ' + Name);

end;

{–}

Как обычно добавьте этот код и испытайте «компилятор». В настоящее время существует только одна допустимая входная последовательность:

px. (где х – это любая одиночная буква, имя программы).

Хорошо, как обычно наша первая попытка не очень впечатляет, но я уверен к настоящему времени вы знаете, что дальше станет интересней. Есть одна важная вещь, которую следует отметить: на выходе получается работающая, законченная и выполнимая программа (по крайней мере после того, как она будет ассемблирована).

Это очень важно. Приятная особенность нисходящего метода состоит в том, что на любом этапе вы можете компилировать подмножество завершенного языка и получить программу, которая будет работать на конечной машине. Отсюда, затем, нам необходимо только добавлять возможности, расширяя конструкции языка. Это очень похоже на то, что мы уже делали, за исключением того, что мы подходили к этому с другого конца.

РАСШИРЕНИЕ

Чтобы расширить компилятор мы должны просто работать с возможностями языка последовательно. Я хочу начать с пустой процедуры, которая ничего не делает, затем добавлять детали в пошаговом режиме. Давайте начнем с обработки блока в соответствии с его PDL выше. Мы можем сделать это в два этапа. Сначала добавьте пустую процедуру: