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

       

БУЛЕВА АЛГЕБРА


Следующий шаг, как мы изучили несколько раз до этого, это добавление булевой алгебры. В прошлом этот шаг по крайней мере удваивал количество кода, который мы должны были написать. Когда я прошел эти шаги в своем уме, я обнаружил, что отклоняюсь все больше и больше от того, что мы делали в предыдущих главах. Чтобы освежить вашу память, я отметил, что Паскаль обрабатывает булевы операторы в значительной степени идентично способу, которым он обрабатывает арифметические операторы.     Булево "and" имеет тот же самый уровень приоритета, что и умножение, а "or" то же что сложение. Си, с другой стороны, устанавливает их на различных уровнях приоритета, которые занимают 17 уровней.  В нашей более ранней работе я выбрал что-то среднее, с семью уровнями. В результате, мы закончили на чем-то называющемся булевыми выражениями, соответствующим в большинстве деталей арифметическим выражениям, но на другом уровне приоритета. Все это, как оказалось, возникло потому, что мне не хотелось помещать скобки вокруг булевых выражений в утверждениях типа:

    IF (c >= 'A') and (c <= 'Z') then ...

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

Чтобы оттолкнуться, давайте начнем заново, применяя более Паскаль подобный подход  и просто обрабатывая булевы операторы на том же самом уровне приоритетов что и арифметические. Мы увидим, куда это нас приведет. Если это окажется тупиком, мы всегда сможем возвратиться к предыдущему подходу.

С начала, мы добавим в Expression операторы "уровня сложения". Это легко сделать; во-первых, измените функцию IsAddop в модуле Scanner чтобы включить два дополнительных оператора: '|' для "или" и "~" для "исключающее или":

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

function IsAddop(c: char): boolean;


begin

 IsAddop := c in ['+','-', '|', '~'];

end;

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

Затем, мы должны включить анализ операторов в процедуру Expression:



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

procedure Expression;

begin

 SignedTerm;

 while IsAddop(Look) do

  case Look of

   '+': Add;

   '-': Subtract;

   '|': _Or;

   '~': _Xor;

  end;

end;

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

(Символы подчеркивания необходимы, конечно, потому что "or" and "xor" являются зарезервированными словами Turbo Pascal).

Затем процедуры _Or and _Xor:

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

{ Parse and Translate a Subtraction Operation }

procedure _Or;

begin

 Match('|');

 Push;

 Term;

 PopOr;

end;

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

{ Parse and Translate a Subtraction Operation }

procedure _Xor;

begin

 Match('~');

 Push;

 Term;

 PopXor;

end;

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

И, наконец, новые процедуры генерации кода:

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

{ Or TOS with Primary }

procedure PopOr;

begin

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

end;

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

{ Exclusive-Or TOS with Primary }

procedure PopXor;

begin

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

end;

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

Теперь давайте протестируем транслятор (вы возможно захотите изменить вызов в Main обратно на вызов Expression просто чтобы избежать необходимости набирать каждый раз "x=" для присваивания).

Пока все хорошо. Синтаксический анализатор четко обрабатывает выражения вида:

    x|y~z

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



    (a+b)*(c~d)

Мы говорили об этом немного в прошлом. Вообще, правила какие операции допустимы а какие нет не могут быть применены самим синтаксическим анализатором, потому что они не являются частью синтаксиса языка, а скорее его семантики. Компилятор, который не разрешает смешанные выражения такого вида должен распознать, что c и d являются булевыми переменными а не числовыми и передумать об их умножении на следующем шаге. Но такая "охрана" не может быть выполнена синтаксическим анализатором; она должна быть обработана где-то между синтаксическим анализатором и генератором кода. Мы пока не в таком положении, чтобы устанавливать такие правила, потом что у нас нет способа ни объявления типов, ни таблицы идентификаторов для сохранения в ней типов. Так что, для того что у нас на данный момент работает, синтаксический анализатор делает точно то, что он предназначен делать.

В любом случае, уверены ли мы, что не хотим разрешить операции над смешанными типами? Некоторое время назад мы приняли решение (или по крайней мере я принял) чтобы принимать значение 0000 как логическую "ложь" и -1 или FFFFh как логическую "истину". Хорошо в этом выборе то, что побитовые операции работают точно таким же способом, что и логические. Другими словами, когда мы выполняем операцию с одним битом логической переменной, мы делаем это над всеми из них. Это означает, что мы не должны делать различия между логическими и поразрядными операциями, как это сделано в C операторами & и &&, и | и ||. Уменьшение числа операторов наполовину конечно не выглядит совсем плохим.

С точки зрения данных в памяти, конечно, компьютер и компилятор не слишком интересуются, представляет ли число FFFFh логическую истину или число -1. Должны ли мы? Я думаю что нет. Я могу придумать множество примеров (хотя они могут быть рассмотрены как "мудреный" код) где возможность смешивать типы могла бы пригодиться. Пример, функция дельты Дирака, которая могла бы быть закодирована в одной простой строке:



    -(x=0)

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

    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:

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

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

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

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

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;

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

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

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

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

 


Содержание раздела