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

procedure DoLoop;

var L1, L2: string;

begin

Match('p');

L1 := NewLabel;

L2 := NewLabel;

PostLabel(L1);

Block(L2);

Match('e');

EmitLn('BRA ' + L1);

PostLabel(L2);

end;

{–}

{ Parse and Translate a REPEAT Statement }

procedure DoRepeat;

var L1, L2: string;

begin

Match('r');

L1 := NewLabel;

L2 := NewLabel;

PostLabel(L1);

Block(L2);

Match('u');

Condition;

EmitLn('BEQ ' + L1);

PostLabel(L2);

end;

{–}

{ Parse and Translate a FOR Statement }

procedure DoFor;

var L1, L2: string;

Name: char;

begin

Match('f');

L1 := NewLabel;

L2 := NewLabel;

Name := GetName;

Match('=');

Expression;

EmitLn('SUBQ #1,D0');

EmitLn('LEA ' + Name + '(PC),A0');

EmitLn('MOVE D0,(A0)');

Expression;

EmitLn('MOVE D0,-(SP)');

PostLabel(L1);

EmitLn('LEA ' + Name + '(PC),A0');

EmitLn('MOVE (A0),D0');

EmitLn('ADDQ #1,D0');

EmitLn('MOVE D0,(A0)');

EmitLn('CMP (SP),D0');

EmitLn('BGT ' + L2);

Block(L2);

Match('e');

EmitLn('BRA ' + L1);

PostLabel(L2);

EmitLn('ADDQ #2,SP');

end;

{–}

{ Parse and Translate a DO Statement }

procedure Dodo;

var L1, L2: string;

begin

Match('d');

L1 := NewLabel;

L2 := NewLabel;

Expression;

EmitLn('SUBQ #1,D0');

PostLabel(L1);

EmitLn('MOVE D0,-(SP)');

Block(L2);

EmitLn('MOVE (SP)+,D0');

EmitLn('DBRA D0,' + L1);

EmitLn('SUBQ #2,SP');

PostLabel(L2);

EmitLn('ADDQ #2,SP');

end;

{–}

{ Recognize and Translate a BREAK }

procedure DoBreak(L: string);

begin

Match('b');

EmitLn('BRA ' + L);

end;

{–}

{ Recognize and Translate an «Other» }

procedure Other;

begin

EmitLn(GetName);

end;

{–}

{ Recognize and Translate a Statement Block }

procedure Block(L: string);

begin

while not(Look in ['e', 'l', 'u']) do begin

case Look of

'i': DoIf(L);

'w': DoWhile;

'p': DoLoop;

'r': DoRepeat;

'f': DoFor;

'd': DoDo;

'b': DoBreak(L);

else Other;

end;

end;

end;

{–}

{ Parse and Translate a Program }

procedure DoProgram;

begin

Block('');

if Look <> 'e' then Expected('End');

EmitLn('END')

end;

{–}

{ Initialize }

procedure Init;

begin

LCount := 0;

GetChar;

end;

{–}

{ Main Program }

begin

Init;

DoProgram;

end.

{–}

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

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

Одним из дел, которыми мы займемся на этом уроке, будет заполнение этого пробела посредством расширения Condition до настоящего анализатора/транслятора.

Мы собираемся подойти к этой главе немного по-другому, чем к любой другой. В других главах мы начинали немедленно с экспериментов, используя компилятор Pascal, выстраивая синтаксические анализаторы от самых элементарных начал до их конечных форм, не тратя слишком много времени на предварительное планирование. Это называется кодированием без спецификации и обычно к нему относятся неодобрительно. Раньше мы могли избегать планирования, потому что правила арифметики довольно хорошо установлены... мы знаем, что означает знак "+" без необходимости подробно это обсуждать. То же самое относится к ветвлениям и циклам. Но способы, которыми языки программирования реализуют логику, немного отличаются от языка к языку. Поэтому прежде, чем мы начнем серьезное кодирование, лучше мы сперва примем решение что же мы хотим. И способ сделать это находится на уровне синтаксических правил БНФ (грамматики).

Некоторое время назад мы реализовали синтаксические уравнения БНФ для арифметических выражений фактически даже не записав их все в одном месте. Пришло время сделать это. Вот они:

::= [ ]*

::= [ factor]*

::= | | ( )

(Запомните, преимущества этой грамматики в том, что она осуществляет такую иерархию приоритетов операторов, которую мы обычно ожидаем для алгебры.)

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

::= [ ]*

::= [ factor]*

::= []

::= | | ()

Это возлагает обработку унарного минуса на Factor, которому он в действительности и принадлежит.

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

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

::= [ ]*

::= [AND ]*

::= [NOT]

::= | | ()

Заметьте, что в этой грамматике оператор AND аналогичен "*", а OR (и исключающее OR) – "+". Оператор NOT аналогичен унарному минусу. Эта иерархия не является абсолютным стандартом... некоторые языки, особенно Ada, обрабатывают все логические операторы как имеющие одинаковый уровень приоритета... но это кажется естественным.