Управляющие конструкции

ВВЕДЕНИЕ

В четырех первых главах этой серии мы сконцентрировали свое внимание на синтаксическом анализе математических выражений и операций присваивания. В этой главе мы остановимся на новой и захватывающей теме: синтаксическом анализе и трансляции управляющих конструкций таких как, например, операторы IF.

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

ПЛАН

Далее мы снова начнем с пустого Cradle и, как мы делали уже дважды до этого, будем строить программу последовательно. Мы также сохраним концепцию односимвольных токенов, которая так хорошо служила нам до настоящего времени. Это означает, что «код» будет выглядеть немного забавным с "i" вместо IF, "w" вместо WHILE и т.д. Но это поможет нам узнать основные понятия не беспокоясь о лексическом анализе. Не бойтесь... в конечном счете мы увидим что-то похожее на «настоящий» код.

Я также не хочу, чтобы мы увязли в работе с какими либо операторами кроме ветвлений, такими как операции присваивания, с которыми мы уже работали. Мы уже показали, что можем обрабатывать их, так что нет никакого смысла таскать этот лишний багаж в течение предстоящих занятий. Вместо этого я буду использовать анонимный оператор «other» для замены неуправляющих операторов. Мы должны генерировать для них некоторый обьектный код (мы возвращаемся к компиляции а не интерпретации), так что за неимением чего-либо другого я буду просто повторять входной символ.

Итак, тогда, начав с еще одной копии Cradle, давайте определим процедуру:

{–}
{ Recognize and Translate an «Other» }
procedure Other;
begin
EmitLn(GetName);
end;
{–}

Теперь включим ее вызов в основную программу таким образом:

{–}
{ Main Program }
begin
Init;
Other;
end.
{–}

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

Первое, что нам нужно – это возможность работать с более чем одним оператором, так как однострочные ветвления довольно ограничены. Мы делали это на последнем занятии по интерпретации, но сейчас давайте будем немного более формальными. Рассмотрите следующую БНФ:

<program> ::= <block> END

<block> ::= [ <statement> ]*

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

Что является признаком окончания блока? Это просто любая конструкция, не являющаяся оператором «other». Сейчас это только утверждение END.

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

{–}
{ Parse and Translate a Program }
procedure DoProgram;
begin
Block;
if Look <> 'e' then Expected('End');
EmitLn('END')
end;
{–}

Обратите внимание, что я выдаю ассемблеру команду «END», что своего рода расставляет знаки препинания в выходном коде и заставляет чувствовать, что мы анализируем здесь законченную программу.

Код для Block:

{–}
{ Recognize and Translate a Statement Block }
procedure Block;
begin
while not(Look in ['e']) do begin
Other;
end;
end;
{–}

(Из формы процедуры вы видите, что мы собираемся постепенно ее расширять!)

ОК, вставьте эти подпрограммы в вашу программу. Замените вызов Block в основной программе на вызов DoProgram. Теперь испытайте ее и посмотрите как она работает. Хорошо, все еще не так много, но мы становимся все ближе.

НЕМНОГО ОСНОВ

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

IF <condition> THEN <statement>

(где <statement>, конечно, может быть составным.)

Синтаксис C аналогичен этому:

IF ( <condition> ) <statement>

Вместо этого я буду использовать нечто более похожее на Ada:

IF <condition> <block> ENDIF

Другими словами, конструкция IF имеет специфический символ завершения. Это позволит избежать висячих else Паскаля и Си и также предотвращает необходимость использовать скобки {} или begin-end. Синтаксис, который я вам здесь показываю, фактически является синтаксисом языка KISS, который я буду детализировать в следующих главах. Другие конструкции также будут немного отличаться. Это не должно быть для вас большой проблемой. Как только вы увидите, как это делается, вы поймете, что в действительности не имеет большого значения, какой конкретный синтаксис используется. Как только синтаксис определен, включить его в код достаточно просто.

Теперь, все конструкции, с которыми мы будем иметь дело, включают передачу управления, что на уровне ассемблера означает условные и/или безусловные переходы. К примеру простой оператор IF:

IF <condition> A ENDIF B...

должен быть переведен в:

Если условие не выполнено то переход на L

L: B

...

Ясно, что нам понадобятся несколько процедур, которые помогут нам работать с этими переходами. Ниже я определил две из них. Процедура NewLabel генерирует уникальные метки. Это сделано с помощью простого способа называть каждую метку 'Lnn', где nn – это номер метки, начинающийся с нуля. Процедура PostLabel просто выводит метки в соответствующем месте.

Вот эти две подпрограммы:

{–}
{ Generate a Unique Label }
function NewLabel: string;
var S: string;
begin
Str(LCount, S);
NewLabel := 'L' + S;
Inc(LCount);
end;
{–}
{ Post a Label To Output }
procedure PostLabel(L: string);
begin
WriteLn(L, ':');
end;
{–}

Заметьте, что мы добавили новую глобальную переменную LCount, так что вы должны изменить раздел описания переменных в начале программы, следующим образом:

var Look : char; { Lookahead Character }
Lcount: integer; { Label Counter }

Также добавьте следующий дополнительный инициализирующий код в Init:

LCount := 0;

(Не забудьте сделать это, иначе ваши метки будут выглядеть действительно странными!).

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

IF: Сначала получить условие и выдать код для него. Затем создать уникальную метку и выдать переход если условие ложно.

ENDIF: Выдать метку.

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

<condition> { Condition;

L = NewLabel;

Emit(Branch False to L); }

<block>

ENDIF { PostLabel(L) }

Это пример синтаксически-управляемого перевода. Мы уже делали все это... мы просто никогда прежде не записывали это таким образом. Содержимое фигурных скобок представляет собой действия, которые будут выполняться. Хорошо в этом способе представления то, что он не только показывает что мы должны распознать, но также и действия, которые мы должны выполнить и в каком порядке. Как только мы получаем такой синтаксис, код возникает почти сам собой.

Почти единственное, что осталось сделать – конкретизировать то, что мы подразумеваем под «Переход если условие ложно».

Я полагаю, что должен быть код, выполняющийся для <condition>, который будет выполнять булеву алгебру и вычислять некоторый результат. Он также должен установить флажки условий, соответствующие этому результату. Теперь, обычным соглашением для булевых переменных является использование 0000 для представления значения «ложь» и какого-либо другого значения (кто-то использует FFFF, кто-то 0001) для представления «истины».

Процессор 68000 устанавливает флажки условий всякий раз, когда любые данные перемещаются или рассчитываются. Если данные равны 0000 (что соответствует условию ложь, запомните) будет установлен флажок ноль. Код для «перехода по нулю» – BEQ. Таким образом

BEQ <=> Переход если ложь

BNE <=> Переход если истина

По природе вещей большинство ветвлений, которые мы увидим, будут BEQ... мы будем обходить вокруг кода, который должен выполняться когда условие истинно.

ОПЕРАТОР IF

После этого небольшого пояснения метода мы наконец готовы начать программирование синтаксического анализатора для условного оператора. Фактически, мы уже почти сделали это! Как обычно я буду использовать наш односимвольный подход, с символом "i" вместо «IF» и "e" вместо «ENDIF» (также как и END... это двойственная природа не вызывает никакого беспорядка). Я также пока полностью пропущу символ для условия ветвления, который мы все еще должны определить.

Код для DoIf:

{–}
{ Recognize and Translate an IF Construct }
procedure Block; Forward;
procedure DoIf;
var L: string;
begin
Match('i');
L := NewLabel;
Condition;
EmitLn('BEQ ' + L);
Block;
Match('e');
PostLabel(L);
end;
{–}

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

{–}
{ Recognize and Translate a Statement Block }
procedure Block;
begin
while not(Look in ['e']) do begin
case Look of
'i': DoIf;
'o': Other;
end;
end;
end;
{–}

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

{–}
{ Parse and Translate a Boolean Condition }
{ This version is a dummy }
Procedure Condition;
begin
EmitLn('<condition>');
end;
{–}

Вставьте эту процедуру в вашу программу как раз перед DoIf. Теперь запустите программу. Испробуйте строку типа:

aibece

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

aibicedefe

Он начинает все более походить на настоящий, не так ли?

Теперь, когда у нас есть общая идея (и инструменты такие как нотация и процедуры NewLabel и PostLabel) проще пареной репы расширить синтаксический анализатор для поддержки и других конструкций. Первое (а также и одно из самых сложных) это добавление условия ELSE в IF. В БНФ это выглядит так:

IF <condition> <block> [ ELSE <block>] ENDIF

Сложность возникает просто потому, что здесь присутствует необязательное условие, которого нет в других конструкциях.

Соответствующий выходной код должен быть таким:

BEQ L1

<block>

BRA L2

L1: <block>

L2: ...

Это приводит нас к следующей синтаксически управляемой схеме перевода:

<condition> { L1 = NewLabel;

L2 = NewLabel;

Emit(BEQ L1) }

<block>

ELSE { Emit(BRA L2);

PostLabel(L1) }

<block>

ENDIF { PostLabel(L2) }

Сравнение этого со случаем IF без ELSE дает нам понимание того, как обрабатывать обе эти ситуации. Код ниже выполняет это. (Обратите внимание, что использую "l" вместо «ELSE» так как "e" имеет другое назначение):

{–}
{ Recognize and Translate an IF Construct }
procedure DoIf;
var L1, L2: string;
begin
Match('i');
Condition;
L1 := NewLabel;
L2 := L1;
EmitLn('BEQ ' + L1);
Block;
if Look = 'l' then begin
Match('l');
L2 := NewLabel;
EmitLn('BRA ' + L2);
PostLabel(L1);
Block;
end;
Match('e');
PostLabel(L2);
end;
{–}

Вы получили его. Законченый анализатор/транслятор в 19 строк кода.

Сейчас протестируйте его. Испробуйте что-нибудь типа:

aiblcede

Работает? Теперь, только для того, чтобы убедиться, что мы ничего не испортили и случай с IF без ELSE тоже будет обрабатываться, введите

aibece

Теперь испробуйте несколько вложенных IF. Испытайте что-нибудь на ваш выбор, включая несколько неправильных утверждений. Только запомните, что 'e' не является допустимым оператором «other».

ОПЕРАТОР WHILE

Следующий вид оператора должен быть простым, так как мы уже имеем опыт. Синтаксис, который я выбрал для оператора WHILE следующий:

WHILE <condition> <block> ENDWHILE

Знаю, знаю, мы действительно не нуждаемся в отдельных видах ограничителей для каждой конструкции... вы можете видеть, что фактически в нашей односимвольной версии 'e' используется для всех из них. Но я также помню множество сессий отладки в Паскале, пытаясь отследить своенравный END который по мнению компилятора я хотел поместить где-нибудь еще. По своему опыту знаю, что специфичные и уникальные ключевые слова, хотя они и добавляются к словарю языка, дают небольшую защиту от ошибок, которая стоит дополнительной работы создателей компиляторов.

Теперь рассмотрите, во что должен траслироваться WHILE:

L1: <condition>

BEQ L2

<block>

BRA L1

L2:

Как и прежде, сравнение этих двух представлений дает нам действия, необходимые на каждом этапе:

WHILE { L1 = NewLabel;

PostLabel(L1) }

<condition> { Emit(BEQ L2) }

<block>

ENDWHILE { Emit(BRA L1);

PostLabel(L2) }

Код выходит непосредственно из синтаксиса:

{–}
{ Parse and Translate a WHILE Statement }
procedure DoWhile;
var L1, L2: string;
begin
Match('w');
L1 := NewLabel;
L2 := NewLabel;
PostLabel(L1);
Condition;
EmitLn('BEQ ' + L2);
Block;
Match('e');
EmitLn('BRA ' + L1);
PostLabel(L2);
end;
{–}

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

{–}
{ Recognize and Translate a Statement Block }
procedure Block;
begin
while not(Look in ['e', 'l']) do begin
case Look of
'i': DoIf;
'w': DoWhile;
else Other;
end;
end;
end;
{–}

Никаких других изменений не требуется.

Хорошо, протестируйте новую программу. Заметьте, что на этот раз код <condition> находится внутри верхней метки, как раз там, где нам надо. Попробуйте несколько вложенных циклов. Испробуйте циклы внутри IF и IF внутри циклов. Если вы немного напутаете то, что вы должны набирать, не смущайтесь: вы пишите ошибки и в других языках, не правда ли? Код будет выглядеть более осмысленным, когда мы получим полные ключевые слова.

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

ОПЕРАТОР LOOP

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

Эта конструкция даже проще, так как она совсем не имеет проверки условия... это бесконечный цикл. Имеет ли смысл такой цикл? Немного сам по себе, но позднее мы собираемся добавить команду BREAK, которая даст нам способ выхода из цикла. Она делает язык значительно более богатым, чем Паскаль, который не имеет команды выхода из цикла и также позволяет избежать забавных конструкций типа WHILE(1) или WHILE TRUE в C и Паскале.

Синтаксис прост:

LOOP <block> ENDLOOP

Синтаксически управляемый перевод:

LOOP { L = NewLabel;

PostLabel(L) }

<block>

ENDLOOP { Emit(BRA L }

Соответствующий код показан ниже. Так как мы уже использовали "l" для ELSE на этот раз я использовал последнюю букву "p" как «ключевое слово».

{–}
{ Parse and Translate a LOOP Statement }
procedure DoLoop;
var L: string;
begin
Match('p');
L := NewLabel;
PostLabel(L);
Block;
Match('e');
EmitLn('BRA ' + L);
end;
{–}

После того, как вы вставите эту подпрограмму, не забудьте добавить строчку в Block для ее вызова.

REPEAT-UNTIL

Имеется одна конструкция, которую я взял напрямую из Паскаля. Синтаксис:

REPEAT <block> UNTIL <condition>

и синтаксически-управляемый перевод:

REPEAT { L = NewLabel;

PostLabel(L) }

<block>

UNTIL

<condition> { Emit(BEQ L) }

Как обычно, код вытекает отсюда довольно легко:
{–}
{ Parse and Translate a REPEAT Statement }
procedure DoRepeat;
var L: string;
begin
Match('r');
L := NewLabel;
PostLabel(L);
Block;
Match('u');
Condition;
EmitLn('BEQ ' + L);
end;
{–}

Как и прежде, мы должны добавить вызов DoRepeat в Block. Хотя на этот раз есть различия. Я решил использовать "r" вместо REPEAT (естественно), но я также решил использовать "u" вместо UNTIL. Это означает, что "u" должен быть добавлен к множеству символов в условии while. Это символы, которые сигнализируют о выходе из текущего блока... символы «follow», на жаргоне разработчиков компиляторов.

{–}
{ Recognize and Translate a Statement Block }
procedure Block;
begin
while not(Look in ['e', 'l', 'u']) do begin
case Look of
'i': DoIf;
'w': DoWhile;
'p': DoLoop;
'r': DoRepeat;
else Other;
end;
end;
end;
{–}

ЦИКЛ FOR

Цикл FOR очень удобен, но он тяжел для трансляции. Не столько потому, что сама конструкция трудна... в конце концов это всего лишь цикл... но просто потому, что она трудна для реализации на ассемблере. Как только код придуман, трансляция достаточно проста.

Фаны Си любят цикл FOR этого языка (фактически он проще для кодирования), но вместо него я выбрал синтаксис очень похожий на синтаксис из старого доброго Бейсика:

FOR <ident> = <expr1> TO <expr2> <block> ENDFOR

Сложность трансляции цикла «FOR» зависит от выбранного вами способа его реализации, от пути, которым вы решили определять правила обработки ограничений. Рассчитывается ли expr2 каждый раз при прохождении цикла, например, или оно обрабатывается как постоянное ограничение? Всегда ли вы проходите цикл хотя бы раз, как в Fortran, или нет. Все становится проще, если вы приверженец точки зрения что эта конструкция эквивалентна:

TEMP = <expr2>

WHILE <ident> <= TEMP

<block>

ENDWHILE

Заметьте, что с этим определением цикла <block> не будет выполнен вообще если <expr1> изначально больше чем <expr2>.

Код 68000, необходимый для этого, сложней чем все что мы делали до сих пор. Я сделал несколько попыток, помещая и счетчик и верхний предел в стек, в регистры и т.д. В конечном итоге я остановился на гибридном варианте размещения, при котором счетчик помещается в памяти (поэтому он может быть доступен внутри цикла) а верхний предел – в стеке. Оттранслированный код получился следующий:

<ident> ; получить имя счетчика цикла

<expr1> ; получить начальное значение

LEA <ident>(PC),A0 ; обратиться к счетчику цикла

SUBQ #1,D0 ; предварительно уменьшить его

MOVE D0,(A0) ; сохранить его

<expr1> ; получить верхний предел

MOVE D0,-(SP) ; сохранить его в стеке

L1: LEA <ident>(PC),A0 ; обратиться к счетчику цикла

MOVE (A0),D0 ; извлечь его в D0

ADDQ #1,D0 ; увеличить счетчик

MOVE D0,(A0) ; сохранить новое значение

CMP (SP),D0 ; проверить диапазон

BLE L2 ; пропустить если D0 > (SP)

<block>

BRA L1 ; цикл для следующего прохода

L2: ADDQ #2,SP ; очистить стек

Ничего себе! Это же куча кода... строка, содержащая <block> кажется совсем потерявшейся. Но это лучшее из того, что я смог придумать. Я полагаю, чтобы вам помочь, вы должны иметь в виду что в действительности это всего лишь шестнадцать слов, в конце концов. Если кто-нибудь сможет оптимизировать это лучше, пожалуйста дайте мне знать.

Однако, подпрограмма анализа довольно проста теперь, когда у нас есть код:

{–}
{ 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;
Match('e');
EmitLn('BRA ' + L1);
PostLabel(L2);
EmitLn('ADDQ #2,SP');
end;
{–}

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

{–}
{ Parse and Translate an Expression }
{ This version is a dummy }
Procedure Expression;
begin
EmitLn('<expr>');
end;
{–}

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

afi=bece

Хорошо, генерируется много кода, не так ли? Но, по крайней мере, это правильный код.

ОПЕРАТОР DO

Из-за всего этого мне захотелось иметь более простую версию цикла FOR. Причина появления всего этого кода выше состоит в необходимости иметь счетчик цикла, доступный как переменная внутри цикла. Если все, что нам нужно это считающий цикл, позволяющий нам выполнить что-то определенное число раз, но не нужен непосредственный доступ к счетчику, имеется более простое решение. Процессор 68000 имеет встроенную команду «уменьшить и переход если не ноль», которая является идеальной для подсчета. Для полноты давайте добавим и эту конструкцию. Это будет наш последний цикл.

Синтаксис и его перевод:

<expr> { Emit(SUBQ #1,D0);

L = NewLabel;

PostLabel(L);

Emit(MOVE D0,-(SP) }

<block>

ENDDO { Emit(MOVE (SP)+,D0;

Emit(DBRA D0,L) }

Это гораздо проще! Цикл будет выполняться <expr> раз. Вот код:

{–}
{ Parse and Translate a DO Statement }
procedure Dodo;
var L: string;
begin
Match('d');
L := NewLabel;
Expression;
EmitLn('SUBQ #1,D0');
PostLabel(L);
EmitLn('MOVE D0,-(SP)');
Block;
EmitLn('MOVE (SP)+,D0');
EmitLn('DBRA D0,' + L);
end;
{–}

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

ОПЕРАТОР BREAK

Ранее я обещал вам оператор BREAK для сопровождения цикла LOOP. Им я в некотором роде горд. На первый взгляд BREAK кажется действительно сложным. Моим первым подходом было просто использовать его как дополнительный ограничитель в Block и разделить все циклы на две части точно также как я сделал это для ELSE оператора IF. Но, оказывается, это не работает, потому что оператор BREAK редко находится на том же самом уровне, что и сам цикл. Наиболее вероятное место для BREAK – сразу после IF, что приводило бы к выходу из конструкции IF, а не из окружающего цикла. Неправильно. BREAK должен выходить из внутреннего LOOP даже если он вложен в несколько уровней IF.

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

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

Секрет состоит в том, чтобы заметить, что каждый оператор BREAK должен выполняться внутри блока... и ни в каком другом месте. Так что все, что мы должны сделать это передать в Block адрес выхода из самого внутреннего цикла. Затем он может передать этот адрес подпрограмме, транслирующей инструкцию Break. Так как оператор IF не изменяет уровень цикла, процедура DoIf не должна делать что-либо за исключением передачи метки в ее блок (оба из них). Так как циклы изменяют уровень, каждый цикл просто игнорирует любую метку выше его и передает свою собственную метку выхода дальше.

Все это проще показать вам чем описывать. Я продемонстрирую это с самым простым циклом, циклом LOOP:

{–}
{ Parse and Translate a LOOP Statement }
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;
{–}

Заметьте, что теперь DoLoop имеет две метки а не одну. Вторая дает команде BREAK адрес перехода Если в цикле нет BREAK, то мы зря потратили метку и немного загромоздили код, но не нанесли никакого вреда.

Заметьте также, что процедура Block теперь имеет параметр, который для циклов всегда будет адресом выхода. Новая версия Block:

{–}
{ 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;
{–}

Снова заметьте, что все что Block делает с меткой это передает ее в DoIf и DoBreak. Циклы не нуждаются в ней, потому что они в любом случае передают свою собственную метку.

Новая версия DoIf:

{–}
{ Recognize and Translate an IF Construct }
procedure Block(L: string); Forward;
procedure DoIf(L: string);
var L1, L2: string;
begin
Match('i');
Condition;
L1 := NewLabel;
L2 := L1;
EmitLn('BEQ ' + L1);
Block(L);
if Look = 'l' then begin
Match('l');
L2 := NewLabel;
EmitLn('BRA ' + L2);
PostLabel(L1);
Block(L);
end;
Match('e');
PostLabel(L2);
end;
{–}

Здесь единственное, что изменяется, это добавляется параметр у процедуры Block. Оператор IF не меняет уровень вложенности цикла, поэтому DoIf просто передает метку дальше. Независимо от того, сколько уровней вложенности IF мы имеем, будет использоваться та же самая метка.

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

{–}
{ Recognize and Translate a BREAK }
procedure DoBreak(L: string);
begin
Match('b');
if L <> '' then
EmitLn('BRA ' + L)
else Abort('No loop to break from');
end;
{–}
{ Parse and Translate a Program }
procedure DoProgram;
begin
Block('');
if Look <> 'e' then Expected('End');
EmitLn('END')
end;
{–}

Этот код позаботится почти обо всем. Испытайте его, посмотрите, сможете ли вы «сломать» («break») его (каламбур). Аккуратней однако. К настоящему времени мы использовали так много букв, что трудно придумать символ, который не представляет сейчас какое либо зарезервированное слово. Не забудьте, перед тем, как вы протестируете программу, вы должны будете исправить каждый случай появления Block в других циклах для включения нового параметра. Сделайте это точно так же, как я сделал это для LOOP.

Я сказал выше «почти». Есть одна небольшая проблема: если вы внимательно посмотрите на код, генерируемый для DO, вы увидите, что если вы прервете этот цикл, то значение счетчика все еще остается в стеке. Мы должны исправить это! Позор... это была одна из самых маленьких наших подпрограмм, но это не помогло. Вот новая версия, которая не имеет этой проблемы:

{–}
{ 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;
{–}

Две дополнительные инструкции SUBQ и ADDQ заботятся о сохранении стека в правильной форме.

ЗАКЛЮЧЕНИЕ

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

Я завершаю на этом урок. Чтобы можно было обернуть наш продукт красной ленточкой, в действительности мы должны иметь настоящие ключевые слова вместо этих игрушечных односимвольных. Вы уже видели, что расширить компилятор для поддержки многосимвольных слов не трудно, но в этом случае возникнут большие различия в представлении нашего входного кода. Я оставлю этот небольшой кусочек для следующей главы. В этой главе мы также рассмотрим логические выражения, так что мы сможем избавиться от фиктивной версии Condition, которую мы здесь использовали. Увидимся.

Для справочных целей привожу полный текст синтаксического анализатора для этого урока:

{–}
program Branch;
{–}
{ Constant Declarations }
const TAB = ^I;
CR = ^M;
{–}
{ Variable Declarations }
var Look : char; { Lookahead Character }
Lcount: integer; { Label Counter }
{–}
{ Read New Character From Input Stream }
procedure GetChar;
begin
Read(Look);
end;
{–}
{ Report an Error }
procedure Error(s: string);
begin
WriteLn;
WriteLn(^G, 'Error: ', s, '.');
end;
{–}
{ Report Error and Halt }
procedure Abort(s: string);
begin
Error(s);
Halt;
end;
{–}
{ Report What Was Expected }
procedure Expected(s: string);
begin
Abort(s + ' Expected');
end;
{–}
{ Match a Specific Input Character }
procedure Match(x: char);
begin
if Look = x then GetChar
else Expected('''' + x + '''');
end;
{–}
{ Recognize an Alpha Character }
function IsAlpha(c: char): boolean;
begin
IsAlpha := UpCase(c) in ['A'..'Z'];
end;
{–}
{ Recognize a Decimal Digit }
function IsDigit(c: char): boolean;
begin
IsDigit := c in ['0'..'9'];
end;
{–}
{ Recognize an Addop }
function IsAddop(c: char): boolean;
begin
IsAddop := c in ['+', '-'];
end;
{–}
{ Recognize White Space }
function IsWhite(c: char): boolean;
begin
IsWhite := c in [' ', TAB];
end;
{–}
{ Skip Over Leading White Space }
procedure SkipWhite;
begin
while IsWhite(Look) do
GetChar;
end;
{–}
{ Get an Identifier }
function GetName: char;
begin
if not IsAlpha(Look) then Expected('Name');
GetName := UpCase(Look);
GetChar;
end;
{–}
{ Get a Number }
function GetNum: char;
begin
if not IsDigit(Look) then Expected('Integer');
GetNum := Look;
GetChar;
end;
{–}
{ Generate a Unique Label }
function NewLabel: string;
var S: string;
begin
Str(LCount, S);
NewLabel := 'L' + S;
Inc(LCount);
end;
{–}
{ Post a Label To Output }
procedure PostLabel(L: string);
begin
WriteLn(L, ':');
end;
{–}
{ Output a String with Tab }
procedure Emit(s: string);
begin
Write(TAB, s);
end;
{–}
{ Output a String with Tab and CRLF }
procedure EmitLn(s: string);
begin
Emit(s);
WriteLn;
end;
{–}
{ Parse and Translate a Boolean Condition }
procedure Condition;
begin
EmitLn('<condition>');
end;
{–}
{ Parse and Translate a Math Expression }
procedure Expression;
begin
EmitLn('<expr>');
end;
{–}
{ Recognize and Translate an IF Construct }
procedure Block(L: string); Forward;
procedure DoIf(L: string);
var L1, L2: string;
begin
Match('i');
Condition;
L1 := NewLabel;
L2 := L1;
EmitLn('BEQ ' + L1);
Block(L);
if Look = 'l' then begin
Match('l');
L2 := NewLabel;
EmitLn('BRA ' + L2);
PostLabel(L1);
Block(L);
end;
Match('e');
PostLabel(L2);
end;
{–}
{ Parse and Translate a WHILE Statement }
procedure DoWhile;
var L1, L2: string;
begin
Match('w');
L1 := NewLabel;
L2 := NewLabel;
PostLabel(L1);
Condition;
EmitLn('BEQ ' + L2);
Block(L2);
Match('e');
EmitLn('BRA ' + L1);
PostLabel(L2);
end;
{–}
{ Parse and Translate a LOOP Statement }
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.
{–}

Оглавление