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

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

aibicedefe

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

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

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

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

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

IF

<condition> 

BEQ L1 

<block> 

BRA L2 

L1: <block> 

L2: ...

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

IF

<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, или нет. Все становится проще, если вы приверженец точки зрения что эта конструкция эквивалентна:

<ident> = <expr1>

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