Булевы выражения

6. Булевы выражения

ВВЕДЕНИЕ

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

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

Одним из дел, которыми мы займемся на этом уроке, будет заполнение этого пробела  посредством расширения Condition до настоящего анализатора/транслятора.

ПЛАН

Мы собираемся подойти к этой главе немного по-другому, чем к любой другой. В других главах мы начинали немедленно с экспериментов, используя компилятор Pascal, выстраивая синтаксические анализаторы от самых элементарных начал до их конечных форм, не тратя слишком много времени на предварительное планирование. Это называется кодированием без спецификации и обычно к нему относятся неодобрительно. Раньше мы могли избегать планирования, потому что правила арифметики довольно хорошо установлены... мы знаем, что означает знак "+" без необходимости подробно это обсуждать. То же самое относится к ветвлениям и циклам. Но способы, которыми языки программирования реализуют логику, немного отличаются от языка к языку. Поэтому прежде, чем мы начнем серьезное кодирование, лучше мы с начала примем решение что же мы хотим. И способ сделать это находится на уровне синтаксических правил БНФ (грамматики).

ГРАММАТИКА

Некоторое время назад мы реализовали синтаксические уравнения БНФ для арифметических выражений фактически даже не записав их все в одном месте. Пришло время сделать это. Вот они:

     <expression> ::= <unary op> <term> [<addop> <term>]*

     <term>       ::= <factor> [<mulop> factor]*

     <factor>     ::= <integer> | <variable> | ( <expression> )

(Запомните, преимущества этой грамматики в том, что она осуществляет такую иерархию приоритетов операторов, которую мы обычно ожидаем для алгебры.)

На самом деле, пока мы говорим об этом, я хотел бы прямо сейчас немного исправить эту грамматику. Способ, которым мы обрабатываем унарный минус, немного неудобный. Я нашел, что лучше записать грамматику таким образом:

     <expression>    ::= <term> [<addop> <term>]*

     <term>          ::= <signed factor> [<mulop> factor]*

     <signed factor> ::= [<addop>] <factor>

     <factor>        ::= <integer> | <variable> | (<expression>)

Это возлагает обработку унарного минуса на Factor, которому он в действительности и принадлежит.

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

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

     <b-expression>::= <b-term> [<orop> <b-term>]*

     <b-term>      ::= <not-factor> [AND <not-factor>]*

     <not-factor>  ::= [NOT] <b-factor>

     <b-factor>    ::= <b-literal> | <b-variable> | (<b-expression>)

Заметьте, что в этой грамматике оператор AND аналогичен "*", а OR (и исключающее OR) - "+". Оператор NOT аналогичен унарному минусу. Эта иерархия не является абсолютным стандартом... некоторые языки, особенно Ada, обрабатывают все логические операторы как имеющие одинаковый уровень приоритета... но это кажется естественным.

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

     a * -b

или еще хуже:

     a - -b

не разрешены. В булевой алгебре наоборот, выражение

     a AND NOT b

имеет точный смысл и показанный синтаксис учитывает это.

ОПЕРАТОРЫ ОТНОШЕНИЙ

Итак, предполагая что вы захотите принять грамматику, которую я показал здесь, мы теперь имеем синтаксические правила и для арифметики и для булевой алгебры. Сложность возникает когда мы должны объединить их. Почему мы должны сделать это? Ну, эта тема возникла из-за необходимости обрабатывать "предикаты" (условия), связанные с управляющими операторами, такими как IF. Предикат должен иметь логическое значение, то есть он должен быть оценен как TRUE или FALSE. Затем ветвление выполняется или не выполняется в зависимости от этого значения. Тогда то, что мы ожидаем увидеть происходящим в процедуре Condition, будет  вычисление  булевого выражения.

Но имеется кое-что еще. Настоящее булево выражение может действительно быть предикатом управляющего оператора... подобно:

     IF a AND NOT b THEN ....

Но более часто мы видим, что булева алгебра появляется в таком виде:

     IF (x >= 0) and (x <= 100) THEN...

Здесь два условия в скобках являются булевыми выражениями, но индивидуальные сравниваемые термы: x,  0 и 100 являются числовыми по своей природе. Операторы отношений >= и <= являются катализаторами, с помощью которых булевские и арифметические компоненты  объединяются вместе.

Теперь, в примере выше сравниваемые термы являются просто термами. Однако, в общем случае, каждая сторона может быть математическим выражением. Поэтому мы можем определить отношение как:

     <relation> ::= <expression> <relop> <expression>,

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

     =, <> (или !=), <, >, <=  и  >=

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

     <b-factor> ::=    <b-literal>

                     | <b-variable>

                     | (<b-expression>)

                     | <relation>

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

Уровень	Синтаксический элемент	Оператор
0	factor	literal, variable
1	signed factor	unary minus
2	term	*, /
3	expression	+, -
4	b-factor	literal, variable, relop
5	not-factor	NOT
6	b-term	AND
7	b-expression	OR, XOR

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

     IF ((((((A + B + C) < 0 ) AND....

Когда синтаксический анализатор анализирует этот код он знает, что после того, как он рассмотрит токен IF следующим должно быть булево выражение. Поэтому он может приступить к началу вычисления такого выражения. Но первое выражение в примере является арифметическим выражением A + B + C. Хуже того, в точке, в которой анализатор прочитал значительную часть  входной строки:

     IF ((((((A ,

он все еще не имеет способа узнать с каким видом выражения он имеет дело. Так не пойдет, потому что мы должны иметь две различных программы распознавания для этих двух случаев. Ситуация может быть обработана без изменения наших определений но только если мы захотим принять произвольное количество возвратов (backtracking) чтобы избавить наш путь от неверных предположений. Ни один из создателей компиляторов в здравом уме не согласился бы на это.

Происходит то, что красота и элегантность грамматики БНФ столкнулась лицом к лицу с реальностью технологии компиляции.

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

ИСПРАВЛЕНИЕ ГРАММАТИКИ

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

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

Когда Никлаус Вирт разработал Паскаль, его желанием было ограничить количество уровней приоритета (меньше подпрограмм синтаксического анализа, в конце концов). Так операторы OR и исключающее OR рассматриваются просто как Addop и обрабатываются на уровне математического выражения. Аналогично AND рассматривается подобно Mulop и обрабатывается с Term. Уровни приоритета:

Уровень	Синтаксический элемент	Оператор
0	factor	literal, variable
1	signed factor	unary minus, NOT
2	term	*, /, AND
3	expression	+, -, OR

Заметьте, что имеется только один набор синтаксических правил, применимый к обоим видам операторов. Тогда согласно этой грамматике выражения типа:

     x + (y AND NOT z) DIV 3

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

Авторы C взяли диаметрально противоположный метод: они обрабатывают операторы как разные и C имеет что-то гораздо более похожее на наши семь уровней приоритета. Фактически, в C имеется не менее 17 уровней! Дело в том, что C имеет также операторы '=', '+=' и их родственников '<<', '>>', '++', '--' и т.д. Как ни странно, хотя в C арифметические и булевы операторы обрабатываются раздельно, то переменные нет... в C нет никаких булевых или логических переменных, так что логическая проверка может быть сделана на любом целочисленном значении.

Мы сделаем нечто среднее. Я склонен обычно придерживаться Паскалевского подхода, так как он кажется самым простым с точки зрения реализации, но это приводит к некоторым странностям, которые я никогда очень сильно не любил, как например в выражении:

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

скобки обязательны. Я никогда не мог понять раньше почему, и ни мой компилятор, ни любой человек также не объясняли этого достаточно хорошо. Но сейчас мы все можем видеть, что оператор "and", имеющий приоритет как у оператора умножения, имеет более высокий приоритет, чем у операторов отношения, поэтому без скобок выражение эквивалентно:

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

что не имеет смысла.

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

     <b-expression> ::= <b-term> [<orop> <b-term>]*

     <b-term>       ::= <not-factor> [AND <not-factor>]*

     <not-factor>   ::= [NOT] <b-factor>

     <b-factor>     ::= <b-literal> | <b-variable> | <relation>

     <relation>     ::= | <expression> [<relop> <expression]

     <expression>   ::= <term> [<addop> <term>]*

     <term>         ::= <signed factor> [<mulop> factor]*

     <signed factor>::= [<addop>] <factor>

     <factor>       ::= <integer> | <variable> | (<b-expression>)

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

Есть одно тонкое, но определяющее различие, которое заставляет все это работать. Обратите внимание на квадратные скобки в определении отношения. Это означает, что relop и второе выражение являются необязательными.

Странным последствием этой грамматики (которое присутствует и в C) является то, что каждое выражения потенциально является булевым выражение. Синтаксический анализатор всегда будет искать булевское выражение, но "уладит" все до арифметического. Честно говоря, это будет замедлять синтаксический анализатор потому что он должен пройти через большее количество вызовов процедур. Это одна из причин, почему компиляторы Паскаля обычно быстрее выполняют компиляцию, чем компиляторы C. Если скорость для вас - больное место, придерживайтесь синтаксиса Паскаля.

СИНТАКСИЧЕСКИЙ АНАЛИЗАТОР

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

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

{ Recognize a Boolean Literal } 
function IsBoolean(c: char): Boolean; 
begin 
   IsBoolean := UpCase(c) in ['T', 'F']; 
end; 
 
{ Get a Boolean Literal } 
function GetBoolean: Boolean; 
var c: char; 
begin 
   if not IsBoolean(Look) then Expected('Boolean Literal'); 
   GetBoolean := UpCase(Look) = 'T'; 
   GetChar; 
end; 

 

Внесите эти подпрограммы в вашу программу. Вы можете протестировать их, добавив в основную программу оператор печати:

     WriteLn(GetBoolean);

Откомпилируйте программу и протестируйте ее. Как обычно пока не очень впечатляет но скоро будет.

Теперь, когда мы работали с числовыми данными, мы должны были организовать генерацию кода для загрузки значений в D0. Нам необходимо сделать то же самое и для булевых данных. Обычным способом кодирования булевых переменных является использование 0 для представления FALSE и какого-либо другого значения для TRUE. Многие языки, как например C, используют для его представления целое число 1. Но я предпочитаю FFFF (или -1) потому что побитовое NOT также возвратит логическое NOT. Итак, нам теперь нужно выдать правильный ассемблерный код для загрузки этих значений. Первая засечка на синтаксическом анализаторе булевых выражений (BoolExpression, конечно):

{ Parse and Translate a Boolean Expression } 
procedure BoolExpression; 
begin 
   if not IsBoolean(Look) then Expected('Boolean Literal'); 
   if GetBoolean then 
      EmitLn('MOVE #-1,D0') 
   else 
      EmitLn('CLR D0'); 
end;

 

Добавьте эту процедуру в ваш анализатор и вызовите ее из основной программы (заменив оператор печати, который вы только что там поместили). Как вы можете видеть, мы все еще не имеем значительной части синтаксического анализатора, но выходной код начинает выглядеть более реалистичным.

Затем, конечно, мы должны расширить определение булевого выражения. У нас уже есть правило в БНФ:

     <b-expression> ::= <b-term> [<orop> <b-term>]*

Я предпочитаю Паскалевскую версию "orop" - OR  и  XOR. Но так как мы сохраняем одно-символьные токены, я буду кодировать их знаками '|' и  '~'. Следующая версия BoolExpression - почти полная копия арифметической процедуры Expression:

{ Recognize and Translate a Boolean OR } 
procedure BoolOr; 
begin 
   Match('|'); 
   BoolTerm; 
   EmitLn('OR (SP)+,D0'); 
end; 
 
{ Recognize and Translate an Exclusive Or } 
procedure BoolXor; 
begin 
   Match('~'); 
   BoolTerm; 
   EmitLn('EOR (SP)+,D0'); 
end; 
{---------------------------------------------------------------} 
{ Parse and Translate a Boolean Expression } 
procedure BoolExpression; 
begin 
   BoolTerm; 
   while IsOrOp(Look) do begin 
      EmitLn('MOVE D0,-(SP)'); 
      case Look of 
       '|': BoolOr; 
       '~': BoolXor; 
      end; 
   end; 
end; 

Обратите внимание на новую процедуру IsOrOp, которая также является копией, на этот раз IsAddOp:

{ Recognize a Boolean Orop } 
function IsOrop(c: char): Boolean; 
begin 
   IsOrop := c in ['|', '~']; 
end; 

 

ОК, переименуйте старую версию BoolExpression в BoolTerm, затем наберите код, представленный выше. Откомпилируйте и протестируйте эту версию. К этому моменту выходной код начинает выглядеть довольно хорошим. Конечно, нет большого смысла от булевой алгебры над постоянными значениями, но скоро мы расширим булевы типы, с которыми мы работаем.

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

Переименуйте текущую процедуру BoolTerm в NotFactor, и введите следующую новую версию BoolTerm. Заметьте, что она намного более простая, чем числовая версия, так как здесь нет эквивалента деления.

{ Parse and Translate a Boolean Term } 
procedure BoolTerm; 
begin 
   NotFactor; 
   while Look = '&' do begin 
      EmitLn('MOVE D0,-(SP)'); 
      Match('&'); 
      NotFactor; 
      EmitLn('AND (SP)+,D0'); 
   end; 
end; 

 

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

{ Parse and Translate a Boolean Factor with NOT } 
procedure NotFactor; 
begin 
   if Look = '!' then begin 
      Match('!'); 
      BoolFactor; 
      EmitLn('EOR #-1,D0'); 
      end 
   else 
      BoolFactor; 
end;

 

 

 

И переименуйте предыдущую процедуру в BoolFactor. Теперь испытайте компилятор. К этому времени синтаксический анализатор должен обрабатывать любое булево выражение, которое вы позаботитесь ему подкинуть. Работает? Отлавливает ли он неправильно сформированные выражения?

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

{ Parse and Translate a Boolean Factor } 
procedure BoolFactor; 
begin 
   if IsBoolean(Look) then 
      if GetBoolean then 
         EmitLn('MOVE #-1,D0') 
      else 
         EmitLn('CLR D0') 
      else Relation; 
end;

 

 

 

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

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

{ Parse and Translate a Relation } 
procedure Relation; 
begin 
   WriteLn('<Relation>'); 
   GetChar; 
end;

ОК, наберите этот код и испытайте его. Все старые дела все еще должны работать... у вас должна быть возможность генерировать код для AND, OR и NOT. Кроме того, если вы наберете любой алфавитный символ, вы должны получить небольшой заменитель <Relation>, где должен быть булев показатель. Вы получили это? Отлично, тогда давайте перейдем к полной версии Relation.

Чтобы получить ее, тем не менее, сначала мы должны положить небольшое основание. Вспомните, что отношение имеет форму:

     <relation>     ::= | <expression> [<relop> <expression]

Так как у нас появился новый вид операторов, нам также понадобится новая логическая функция для ее распознавания. Эта функция показана ниже. Из-за ограничения в один символ, я придерживаюсь четырех операторов, которые могут быть закодированы такими символами ("не равно" закодировано как "#").

{ Recognize a Relop } 
function IsRelop(c: char): Boolean; 
begin 
   IsRelop := c in ['=', '#', '<', '>']; 
end;

 

Теперь вспомните, что мы используем нуль или -1 в регистре D0 для представления логического значения и также то, что операторы цикла ожидают, что будет установлен соответствующий флаг. При реализации всего этого для 68000 все становится немного сложным.

Так как операторы цикла выполняются только по флажкам, было бы хорошо (а также довольно эффективно) просто установить эти флажки и совсем ничего не загружать в D0. Это было бы прекрасно для циклов и ветвлений, но запомните, что отношения могут быть использованы везде, где могут быть использованы булевы показатели. Мы можем сохранять его результат в булевой переменной. Так как мы не можем знать пока как будет использоваться результат, мы должны учесть оба случая.

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

Решение заключается в инструкции Scc процессора 68000, которая устанавливает значение байта в 0000 или FFFF (забавно как это работает!) в зависимости от результата определенного условия. Если мы сделаем байтом результата регистр D0, мы получим необходимое логическое значение.

К сожалению, имеется одно заключительное осложнение: в отличие от почти всех других команд в наборе 68000, Scc не сбрасывает флажки условий в соответствии с сохраняемыми данными. Поэтому мы должны сделать последний шаг, проверить D0 и установить соответствующим образом флажки. Это должно быть похоже на оборот вокруг луны для  получения того, что мы хотим: мы сначала выполняем проверку, затем проверяем флажки, чтобы установить данные в D0, затем тестируем D0 чтобы установить флажки снова. Это окольный путь, но это самый простой способ получить правильные флажки и, в конце концов, это всего лишь пара инструкций.

Я мог бы упомянуть здесь, что эта область, по моему мнению, показывает самые большие различия между эффективностью вручную написанного на ассемблере и сгенерированного компилятором кода. Мы уже видели, что мы теряем эффективность при арифметических операциях, хотя позже я планирую показать вам как ее немного улучшить. Мы также видели, что управляющие конструкции сами по себе могут быть реализованы довольно  эффективно... обычно очень сложно улучшить код, сгенерированный для IF или WHILE. Но практически каждый компилятор, который я когда-либо видел, генерирует ужасный код, по сравнению с ассемблером, для вычисления булевых функций и особенно отношений. Причина как раз в том, о чем я упомянул выше. Когда я пишу код на ассемблере, я двигаюсь вперед и выполняю проверку наиболее удобным для меня способом, и затем подготавливаю ветвление так чтобы переход был выполнен на нужную ветку. Фактически, я "подстраиваю" каждое ветвление под ситуацию. Компилятор не может сделать этого (практически) и он также не может знать, что нам не нужно сохранять результат проверки как булевскую переменную. Поэтому он должен генерировать код по очень строгим правилам и часто заканчивает сохранением результата как булевой переменной, которая никогда не будет использована для чего-либо.

В любом случае мы теперь готовы рассмотреть код для Relation. Он показан ниже с сопровождающими процедурами:

{---------------------------------------------------------------} 
{ Recognize and Translate a Relational "Equals" } 
procedure Equals; 
begin 
   Match('='); 
   Expression; 
   EmitLn('CMP (SP)+,D0'); 
   EmitLn('SEQ D0'); 
end; 
{---------------------------------------------------------------} 
{ Recognize and Translate a Relational "Not Equals" } 
procedure NotEquals; 
begin 
   Match('#'); 
   Expression; 
   EmitLn('CMP (SP)+,D0'); 
   EmitLn('SNE D0'); 
end; 
{---------------------------------------------------------------} 
{ Recognize and Translate a Relational "Less Than" } 
procedure Less; 
begin 
   Match('<'); 
   Expression; 
   EmitLn('CMP (SP)+,D0'); 
   EmitLn('SGE D0'); 
end; 
{---------------------------------------------------------------} 
{ Recognize and Translate a Relational "Greater Than" } 
procedure Greater; 
begin 
   Match('>'); 
   Expression; 
   EmitLn('CMP (SP)+,D0'); 
   EmitLn('SLE D0'); 
end; 
{---------------------------------------------------------------} 
{ Parse and Translate a Relation } 
procedure Relation; 
begin 
   Expression; 
   if IsRelop(Look) then begin 
      EmitLn('MOVE D0,-(SP)'); 
      case Look of 
       '=': Equals; 
       '#': NotEquals; 
       '<': Less; 
       '>': Greater; 
      end; 
   EmitLn('TST D0'); 
   end; 
end; 
{---------------------------------------------------------------} 

 

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

{---------------------------------------------------------------} 
{ Parse and Translate an Identifier } 
procedure Ident; 
var Name: char; 
begin 
   Name:= GetName; 
   if Look = '(' then begin 
      Match('('); 
      Match(')'); 
      EmitLn('BSR ' + Name); 
      end 
   else 
      EmitLn('MOVE ' + Name + '(PC),D0'); 
end; 
{---------------------------------------------------------------} 
{ Parse and Translate a Math Factor } 
procedure Expression; Forward; 
procedure Factor; 
begin 
   if Look = '(' then begin 
      Match('('); 
      Expression; 
      Match(')'); 
      end 
   else if IsAlpha(Look) then 
      Ident 
   else 
      EmitLn('MOVE #' + GetNum + ',D0'); 
end; 
{---------------------------------------------------------------} 
{ Parse and Translate the First Math Factor } 
procedure SignedFactor; 
begin 
   if Look = '+' then 
      GetChar; 
   if Look = '-' then begin 
      GetChar; 
      if IsDigit(Look) then 
         EmitLn('MOVE #-' + GetNum + ',D0') 
      else begin 
         Factor; 
         EmitLn('NEG D0'); 
      end; 
   end 
   else Factor; 
end; 
 
{ Recognize and Translate a Multiply } 
procedure Multiply; 
begin 
   Match('*'); 
   Factor; 
   EmitLn('MULS (SP)+,D0'); 
end; 
{-------------------------------------------------------------} 
{ Recognize and Translate a Divide } 
procedure Divide; 
begin 
   Match('/'); 
   Factor; 
   EmitLn('MOVE (SP)+,D1'); 
   EmitLn('EXS.L D0'); 
   EmitLn('DIVS D1,D0'); 
end; 
{---------------------------------------------------------------} 
{ Parse and Translate a Math Term } 
procedure Term; 
begin 
   SignedFactor; 
   while Look in ['*', '/'] do begin 
      EmitLn('MOVE D0,-(SP)'); 
      case Look of 
       '*': Multiply; 
       '/': Divide; 
      end; 
   end; 
end; 
{---------------------------------------------------------------} 
{ Recognize and Translate an Add } 
procedure Add; 
begin 
   Match('+'); 
   Term; 
   EmitLn('ADD (SP)+,D0'); 
end; 
{---------------------------------------------------------------} 
{ Recognize and Translate a Subtract } 
procedure Subtract; 
begin 
   Match('-'); 
   Term; 
   EmitLn('SUB (SP)+,D0'); 
   EmitLn('NEG D0'); 
end; 
{---------------------------------------------------------------} 
{ Parse and Translate an Expression } 
procedure Expression; 
begin 
   Term; 
   while IsAddop(Look) do begin 
      EmitLn('MOVE D0,-(SP)'); 
      case Look of 
       '+': Add; 
       '-': Subtract; 
      end; 
   end; 
end; 
{---------------------------------------------------------------} 

 

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

ОБЪЕДИНЕНИЕ С УПРАВЛЯЮЩИМИ КОНСТРУКЦИЯМИ

Сейчас давайте возвратимся назад к файлу который мы создали ранее и который выполняет синтаксический анализ управляющих конструкций. Помните небольшие фиктивные процедуры Condition и Expression? Теперь вы знаете, что в них должно находиться!

Я предупреждаю вас, вы собираетесь сделать некоторые творческие изменения, поэтому потратьте ваше время и сделайте это правильно. Вы должны скопировать все процедуры из анализатора логики от Ident до BoolExpression в синтаксический анализатор управляющих конструкций. Вставьте их в текущей позиции Condition. Затем удалите эту процедуру, так же как и фиктивную Expression. Затем замените каждый вызов Condition на обращение к BoolExpression. Наконец скопируйте процедуры IsMulop, IsOrOp, IsRelop, IsBoolean, и GetBoolean на место. Этого достаточно.

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

Попробуйте:

     ia=bxlye

что означает "IF a=b X ELSE Y ENDIF".

Что вы думаете? Работает? Попробуйте что-нибудь еще.

ДОБАВЛЕНИЕ ПРИСВАИВАНИЙ

Раз у нас уже есть подпрограммы для выражений, мы могли бы также заменить "блоки" настоящими операциями присваивания. Мы уже делали это прежде, поэтому это не будет слишком трудно. Прежде, чем сделать этот шаг, однако,  мы должны исправить кое-что еще.

Скоро мы обнаружим, что наши однострочные "программы", которые мы здесь пишем, будут ограничивать наш стиль. В настоящее время у нас нет способа вылечить это, потому что наш компилятор не распознает символы конца строки, возврат каретки (CR) и перевод строки (LF). Поэтому перед продвижением дальше давайте заткнем эту дыру.

Существует пара способов для работы с CR/LF. Один (подход C/Unix) просто рассматривает их как дополнительные символы пробела и игнорирует их. Фактически это не такой плохой подход, но он приводит к странным результатам для нашего анализатора в его текущем состоянии. Если бы он считывал входной поток из исходного файла как любой уважающий себя настоящий компилятор, не было бы никаких проблем. Но мы считываем входной поток с клавиатуры и ожидаем, что должно что-то произойти, когда мы нажимаем клавишу Return. Этого не произойдет, если мы просто перескакиваем CR и LF (попробуйте это). Поэтому я собираюсь использовать здесь другой метод, который в конечном счете не обязательно является лучшим методом. Рассматривайте его как временную замену до тех пор, пока мы не двинемся дальше.

Вместо того, чтобы пропускать CR/LF, мы позволим синтаксическому анализатору двигаться вперед и отлавливать их, затем предоставлять их специальной процедуре, аналогичной SkipWhite, которая пропускает их только в определенных "допустимых" местах.

Вот эта процедура:

{ Skip a CRLF } 
procedure Fin; 
begin 
   if Look = CR then GetChar; 
   if Look = LF then GetChar; 
end; 

 

 

 

     Теперь добавьте два вызова Fin в процедуру Block следующим образом:

{ Recognize and Translate a Statement Block } 
procedure Block(L: string); 
begin 
   while not(Look in ['e', 'l', 'u']) do begin 
      Fin; 
      case Look of 
       'i': DoIf(L); 
       'w': DoWhile; 
       'p': DoLoop; 
       'r': DoRepeat; 
       'f': DoFor; 
       'd': DoDo; 
       'b': DoBreak(L); 
       else Other; 
      end; 
      Fin; 
 end; 
end;

 

 

 

Теперь вы обнаружите, что можете использовать многострочные "программы". Единственное ограничение в том, что вы не можете отделять токены IF или WHILE от их предикатов.

Теперь мы готовы включить операторы присваивания. Просто замените вызов Other в процедуре Block на вызов Assignment и добавьте следующую процедуру, скопированную из одной нашей более ранней программы. Обратите внимание, что сейчас Assignment вызывает BoolExpression, поэтому мы можем присваивать логические переменные.

{ Parse and Translate an Assignment Statement } 
procedure Assignment; 
var Name: char; 
begin 
   Name := GetName; 
   Match('='); 
   BoolExpression; 
   EmitLn('LEA ' + Name + '(PC),A0'); 
   EmitLn('MOVE D0,(A0)'); 
end; 

 

 

 

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

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

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