Джек Креншоу - Давайте создадим компилятор!

• Название: Давайте создадим компилятор!
• Автор: Джек Креншоу
• Жанр: Программирование

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

---

end;

{–}

{ Match One Character }

procedure Match(x: char);

begin

if Look = x then GetChar

else Expected('''' + x + '''');

end;

{–}

{ Get an Identifier }

function GetName: char;

begin

if not IsAlpha(Look) then Expected('Name');

GetName := UpCase(Look);

GetChar;

end;

{–}

{ Get a Number }

function GetNumber: char;

begin

if not IsDigit(Look) then Expected('Integer');

GetNumber := Look;

GetChar;

end;

end.

{–}

Следующий фрагмент кода основной программы обеспечивает хорошую проверку лексического анализатора. Для краткости я включил здесь только выполнимый код; остальное тоже самое. Не забудьте, тем не менее, добавить имя Scanner1 в раздел «uses»:

Write(GetName);

Match('=');

Write(GetNumber);

Match('+');

WriteLn(GetName);

Этот код распознает все предложения вида:

x=0+y

где x и y могут быть любыми односимвольными именами переменных и 0 любой цифрой. Код должен отбросить все другие предложения и выдать осмысленное сообщение об ошибке. Если это произошло, тогда вы в хорошей форме и мы можем продолжать.

Модуль SCANNER

Следующая, и намного более важная, версия лексического анализатора, та которая обрабатывает многосимвольные токены, которые должны иметь все настоящие языки. Только две функции, GetName и GetNumber отличаются в этих двух модулях, но только чтобы убедиться, что здесь нет никаких ошибок, я воспроизвел здесь весь модуль. Это модуль Scanner:

{–}

unit Scanner;

{–}

interface

uses Input, Errors;

function IsAlpha(c: char): boolean;

function IsDigit(c: char): boolean;

function IsAlNum(c: char): boolean;

function IsAddop(c: char): boolean;

function IsMulop(c: char): boolean;

procedure Match(x: char);

function GetName: string;

function GetNumber: longint;

{–}

implementation

{–}

{ Recognize an Alpha Character }

function IsAlpha(c: char): boolean;

begin

IsAlpha := UpCase(c) in ['A'..'Z'];

end;

{–}

{ Recognize a Numeric Character }

function IsDigit(c: char): boolean;

begin

IsDigit := c in ['0'..'9'];

end;

{–}

{ Recognize an Alphanumeric Character }

function IsAlnum(c: char): boolean;

begin

IsAlnum := IsAlpha(c) or IsDigit(c);

end;

{–}

{ Recognize an Addition Operator }

function IsAddop(c: char): boolean;

begin

IsAddop := c in ['+','-'];

end;

{–}

{ Recognize a Multiplication Operator }

function IsMulop(c: char): boolean;

begin

IsMulop := c in ['*','/'];

end;

{–}

{ Match One Character }

procedure Match(x: char);

begin

if Look = x then GetChar

else Expected('''' + x + '''');

end;

{–}

{ Get an Identifier }

function GetName: string;

var n: string;

begin

n := '';

if not IsAlpha(Look) then Expected('Name');

while IsAlnum(Look) do begin

n := n + Look;

GetChar;

end;

GetName := n;

end;

{–}

{ Get a Number }

function GetNumber: string;

var n: string;

begin

n := '';

if not IsDigit(Look) then Expected('Integer');

while IsDigit(Look) do begin

n := n + Look;

GetChar;

end;

GetNumber := n;

end;

end.

{–}

Таже самая тестовая программа проверит также и этот сканер. Просто измените раздел «uses» для использования Scanner вместо Scanner1. Теперь у вас должна быть возможность набирать многосимвольные имена и числа.

Решения, решения

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

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

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

Оба подхода имеют свои преимущества. Так как мы выбираем число, метод, который немедленно приходит на ум – возвращать его как целое число. Но имейте ввиду, что возможно число будет использоваться в операторе вывода который возвращает его во внешний мир. Кто-то, или мы или код, скрытый внутри оператора вывода, окажется перед необходимостью снова преобразовывать число обратно в строку. Turbo Pascal включает такие подпрограммы преобразования строк, но зачем использовать их если мы не должны? Зачем преобразовывать число из строковой в целочисленную форму только для того, чтобы конвертировать его обратно в генераторе кода, всего несколько операторов спустя?

Кроме того, как вы скоро увидите, нам будет необходимо временное место для хранения токена, который мы извлекли. Если мы обрабатываем числа в их строковой форме, мы можем сохранять значение и переменной и числа в той же самой строке. В противном случае мы должны создать вторую, целочисленную переменную.

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

В конце концов обратно к строковому подходу меня склонило энергичное тестирование KISS, плюс напоминание самому себе, что мы тщательно избегаем проблем эффективности кода. Одна из вещей, которые заставляют нашу нехитрую схему синтаксического анализа работать, без сложностей «настоящего» компилятора, это то, что мы прямо сказали что мы не затрагиваем эффективность кода. Это дает нам массу свободы выполнять работу простейшим путем а не эффективнейшим, и эту свободу мы должны стремиться не потерять, не смотря на призывы к эффективности звучащие в наших ушах. В дополнение к тому, что я большой сторонник философии KISS я также защитник «ленивого программирования», что в этом контексте означает не программировать что-либо пока вы не нуждаетесь в этом. Как говорит П. Дж. Плоджер «никогда не откладывайте на завтра то, что вы можете отложить насовсем». Годами писался код, предоставлявший возможности, которые не были никогда использованы. Я научился этому сам на горьком опыте. Так что вывод таков: мы не будем конвертировать в целое число потому, что это нам не нужно.

Для тех из вас, что все еще думает, что нам может быть нужна целочисленная версия (и действительно она может нам понадобиться), вот она:

{–}

{ Get a Number (integer version) }

function GetNumber: longint;

var n: longint;

begin

n := 0;

if not IsDigit(Look) then Expected('Integer');

while IsDigit(Look) do begin

n := 10 * n + (Ord(Look) – Ord('0'));

GetChar;

end;

GetNumber := n;

end;

{–}

Вы могли бы отложить ее, как я предполагаю, на черный день.

Синтаксический анализ

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

Помните самую первую главу этой серии? Мы считывали целочисленное значение, скажем n, и генерировали код для его загрузки в регистр D0 через move:

MOVE #n,D0

Немного погодя, мы повторили этот процесс для переменной,

MOVE X(PC),D0

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

{–}

unit Parser;

{–}

interface

uses Input, Scanner, Errors, CodeGen;

procedure Factor;

{–}

implementation

{–}

{ Parse and Translate a Factor }