Креншоу Д. Пишем компилятор

Подождите немного. Документ загружается.

Лекции по построению компилятора на Pascal

или функция абсолютного значения (определенно сложный код!):

### x*(1+2*(x<0))

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

жизни. Я почти обязательно написал бы эти функции в более читаемой форме, используя IF,

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

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

о хорошей практике кодирования на программисте, написав язык так, чтобы он не смог

сделать что-нибудь не так? Это то, что сделал Никлаус Вирт во многих местах Паскаля и

Паскаль критиковался за это - как не такой "прощающий" как Си.

Интересная параллель представлена в примере дизайна Motorola 68000. Хотя Motorola

громко хвастается об ортогональности их набора инструкций, факт то, что он является

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

### MOVE X,D0 (где X это имя переменной)

но вы не можете записать ее таким же образом. Для записи вы должны загрузить в регистр

адреса адрес X. То же самое остается истиной и для PC-относительной адресации.

### MOVE X(PC),DO (допустимо)

### MOVE D0,X(PC) (недопустимо)

Когда вы начинаете спрашивать, как возникло такое не ортогональное поведение, вы

находите, что кто-то в Motorola имел некоторые теории о том, как должно писаться

программное обеспечение. В частности, в этом случае они решили, что

самомодифицирующийся код, который вы можете реализовать, используя PC-относительные

записи - Плохая Вещь. Следовательно, они разработали процессор, запрещающий это. К

сожалению, по ходу дела они также запретили все записи в форме, показанной выше, даже

полезные. Заметьте, что это было не что-то, сделанное по умолчанию. Должна была быть

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

уничтожения естественной ортогональности набора инструкций.

Один из уроков, которым я научился в жизни: Если у вас есть два выбора и вы не можете

решить которому их них последовать, иногда самое лучшее - не делать ничего. Зачем

добавлять дополнительные ограничители в процессор, чтобы осуществить чужие

представления о хорошей практике программирования? Оставьте эти инструкции и

позвольте программистам поспорить что такое хорошая практика программирования. Точно

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

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

использовать? Я предпочел бы оставить компилятор простым и позволить программным

экспертам спорить, должна ли такая практика использоваться или нет.

Все это служит как объяснение моего решения как избежать смешанной арифметики: я не

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

меньше правил, тем лучше. Если вы не согласны, и хотите выполнять проверку на такие

условия, мы сможем сделать это, когда у нас будет таблица идентификаторов.

### БУЛЕВО "AND"

С это небольшой философией, мы можем приступить к оператору "and", который пойдет в

процедуру Term. К настоящему времени вы возможно сможете сделать это без меня, но в

любом случае вот код:

В Scanner:

{--------------------------------------------------------------}

function IsMulop(c: char): boolean;

begin

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

end;

{--------------------------------------------------------------}

в Parser:

271

Лекции по построению компилятора на Pascal

{--------------------------------------------------------------}

procedure Term;

begin

#Factor;

#while IsMulop(Look) do

# case Look of

## '*': Multiply;

## '/': Divide;

## '&': _And;

# end;

end;

{--------------------------------------------------------------}

{ Parse and Translate a Boolean And Operation }

procedure _And;

begin

#Match('&');

#Push;

#Factor;

#PopAnd;

end;

{--------------------------------------------------------------}

и в CodeGen:

{--------------------------------------------------------------}

{ And Primary with TOS }

procedure PopAnd;

begin

#EmitLn('AND (SP)+,D0');

end;

{--------------------------------------------------------------}

Ваш синтаксический анализатор теперь должен быть способен обрабатывать почти любые

виды логических выражений а также (если вы хотите) и смешанные выражения.

Почему не "все виды логических выражений"? Потому что пока мы не имели дела с

логическим оператором "not" и с ним все становится сложнее. Логический оператор "not"

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

первой мыслью было позволить оператору исключающего или, '~', дублировать унарный

"not". Это не работало. При моей первой попытке процедура SignedTerm просто съедала мой

'~' потому что символ проходил проверку на addop но SignedTerm игнорировал все addop за

исключением "-". Было бы достаточно просто добавить другую строку в SignedTerm, но это

все равно не решит проблему, потому что, заметьте, Expression принимает терм со знаком

только для первого аргумента.

Математически, выражение типа:

### -a * -b

имеет небольшой или совсем никакого смысла и синтаксический анализатор должен

отметить его как ошибку. Но то же самое выражение, использующее логическое "not",] имеет

точный смысл:

### not a and not b

В случае с этими унарными операторами выбор заставить их работать таким же самым

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

алтаре простоты реализуемости. Хотя я полностью за сохранение реализации настолько

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

Исправления подобные этому, приведут к потере основной детали, которая заключается в

том, чтобы логическое "not" просто не является тем же самым что унарный минус.

Рассмотрим исключающее "or", которое обычно записывается так:

### a~b ::= (a and not b) or (not a and b)

Если мы разрешим "not" изменять весь терм, последний терм в круглых скобках

интерпретировался бы как:

272

Лекции по построению компилятора на Pascal

### not(a and b)

что совсем не то же самое. Так что ясно, что о логическом "not" нужно думать как о

связанном с показателем а не термом.

Идея перегрузки оператор '~' не имеет смысла и с математической точки зрения. Применение

унарного минуса эквивалентно вычитанию из нуля:

### -x <=> 0-x

Фактически, в одной из моих более простых версий Expression я реагировал на ведущий

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

оператор. Но "not" это не эквивалент исключающему или с нулем... которое просто возвратит

исходное число. Вместо этого, это исключающее или с FFFFh или -1.

Короче говоря, кажущаяся близость между унарным "not" и унарным минусом разваливается

при более близком исследовании. "not" изменяет показатель а не терм и он не имеет

отношения ни к унарному минусу, ни исключающему или. Следовательно, он заслуживает

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

используемый в Си символ "!"? Используя правила того как мы думаем должен вести себя

"not", мы должны быть способны закодировать исключающее или (предполагая что это нам

когда-нибудь понадобится) в очень естественной форме:

### a & !b | !a & b

Обратите внимание, что никаких круглых скобок не требуется - выбранные нам уровни

приоритета автоматически заботятся обо всем.

Если вы продолжаете учитывать уровни приоритета, это определение помещает '!' на

вершину кучи. Уровни становятся:

1. !

2. (унарный)

3. *, /, &

4. +, -, |, ~

Рассматривая этот список, конечно не трудно увидеть, почему мы имели проблему при

использовании '~' как символа "not"!

Так, как мы механизируем эти правила? Таким же самым способом, как мы сделали с

SignedTerm, но на уровне показателя. Мы определим процедуру NotFactor:

{--------------------------------------------------------------}

{ Parse and Translate a Factor with Optional "Not" }

procedure NotFactor;

begin

#if Look ='!' then begin

# Match('!');

# Factor;

# Notit;

# end

#else

# Factor;

end;

{--------------------------------------------------------------}

и вызовем ее из всех мест, где мы прежде вызывали Factor, т.е. из Term, Multiply, Divide и

_And. Обратите внимание на новую процедуру генерации кода:

{--------------------------------------------------------------}

{ Bitwise Not Primary }

procedure NotIt;

begin

#EmitLn('EOR #-1,D0');

end;

{--------------------------------------------------------------}

273

Лекции по построению компилятора на Pascal

Испытайте ее сейчас с несколькими простыми случаями. Фактически, попробуйте пример с

исключающим или:

### a&!b|!a&b

Вы должны получить код (без комментариев, конечно):

#### MOVE A(PC),DO##; load a

#### MOVE D0,-(SP)##; push it

#### MOVE B(PC),DO##; load b

#### EOR #-1,D0# ; not it

#### AND (SP)+,D0# ; and with a

#### MOVE D0,-(SP)# ; push result

#### MOVE A(PC),DO ; load a

#### EOR #-1,D0# ; not it

#### MOVE D0,-(SP)# ; push it

#### MOVE B(PC),DO# ; load b

#### AND (SP)+,D0# ; and with !a

#### OR (SP)+,D0# ; or with first term

Это точно то, что мы хотели получить. Так что, по крайней мере, и для арифметических и

для логических операторов наш новый приоритет и новый, более тонкий синтаксис,

поддерживают друг друга. Даже специфическое, но допустимое выражение с ведущим

addop:

### ~x

имеет смысл. SignedTerm игнорирует ведущий '~' как и должно быть, так как выражение

эквивалентно:

### 0~x,

что эквивалентно x.

Когда мы взглянем на созданные нами БНФ, мы обнаружим, что наша булева алгебра

добавляет теперь только одну дополнительную строку:

### <not_factor># ::= [!] <factor>

### <factor>###### ::= <variable> | <constant> | '(' <expression> ')'

### <signed_term># ::= [<addop>] <term>

### <term>######## ::= <not_factor> (<mulop> <not_factor>)*

### <expression>## ::= <signed_term> (<addop> <term>)*

### <assignment>## ::= <variable> '=' <expression>

Это большое улучшение предыдущих достижений. Будет ли сохраняться наша удача когда

мы примемся за операторы отношений? Мы выясним это скоро, но мы должны будем

дождаться следующей главы. У нас выдалась подходящая пауза и я хочу выдать эту главу в

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

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

совсем не дает вам ничего хорошего, сидя на моем жестком диске, и удерживая ее пока

операторы отношений не будут сделаны, я не давал ее в ваши руки все это время. Пришло

время выдать ее чтобы вы смогли получить из нее что-нибудь ценное. Кроме того, имеется

большое количество серьезных философских вопросов, связанных с операторами

отношений, и я предпочел бы сохранить их для отдельной главы, где я смог бы сделать это

корректно.

Развлекайтесь с новой более тонкой арифметикой и логическим анализом а я скоро увижу

вас с отношениями.

]

274