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

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

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

---

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

Булево «AND»

С это небольшой философией, мы можем приступить к оператору «and», который пойдет в процедуру Term. К настоящему времени вы возможно сможете сделать это без меня, но в любом случае вот код:

В Scanner:

{–}

function IsMulop(c: char): boolean;

begin

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

end;

{–}

в Parser:

{–}

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» изменять весь терм, последний терм в круглых скобках интерпретировался бы как:

not(a and b)

что совсем не то же самое. Так что ясно, что о логическом «not» нужно думать как о связанном с показателем а не термом.

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

–x <=> 0-x

Фактически, в одной из моих более простых версий Expression я реагировал на ведущий addop просто предзагружая нуль, затем обрабатывая оператор как если бы это был двоичный оператор. Но «not» это не эквивалент исключающему или с нулем... которое просто возвратит исходное число. Вместо этого, это исключающее или с FFFFh или -1.

Короче говоря, кажущаяся близость между унарным «not» и унарным минусом разваливается при более близком исследованиии. «not» изменяет показатель а не терм и он не имеет отношения ни к унарному минусу, ни исключающему или. Следовательно, он заслуживает своего собственного символа для вызова. Какой символ лучше, чем очевидный, также используемый в Си символ "!"? Используя правила того как мы думаем должен вести себя «not», мы должны быть способны закодировать исключающее или (предполагая что это нам когда-нибудь понадобится) в очень естественной форме:

a & !b | !a & b

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

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

!

– (унарный)

*, /, &

+, -, |, ~

Рассматривая этот список, конечно не трудно увидеть, почему мы имели проблему при использовании '~' как символа «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;

{–}

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

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

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