Снова выражения

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

Разрешены только числовые показатели

Числовые показатели ограничены одиночной цифрой.

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

Большинство выражений, который мы встречаем на практике, включают переменные, например:

b * b + 4 * a * c

Ни один компилятор нельзя считать достаточно хорошим, если он не работает с ними. К счастью, это тоже очень просто сделать.

Не забудьте, что в нашем синтаксическом анализаторе в настоящее время существуют два вида показателей: целочисленные константы и выражения в скобках. В нотации БНФ:

<factor> ::= <number> | (<expression>)

"|" заменяет «или», означая, что любая из этих форм является допустимой. Запомните, также, что у нас нет проблемы в определении каждой их них… предсказывающим символом в одном случае является левая скобка "(" и цифра – в другом.

Возможно, не вызовет слишком большого удивления то, что переменная – это просто еще один вид показателя. Так что расширим БНФ следующим образом:

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

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

Небольшое осложнение при генерации кода возникает из того факта, что большинство операционных систем для 68000, включая SK*DOS которую я использую, требуют чтобы код был написан в «переместимой» форме, что в основном означает что все должно быть PC-относительно. Формат для загрузки на этом языке будет следующим:

MOVE X(PC),D0

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

{–}

{ 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

EmitLn('MOVE ' + GetName + '(PC),D0')

else

EmitLn('MOVE #' + GetNum + ',D0');

end;

{–}

Я уже отмечал, как легко добавлять расширения в синтаксический анализатор благодаря способу его структурирования. Вы можете видеть, что это все еще остается действительным и сейчас. На этот раз это стоило нам всего двух дополнительных строк кода. Заметьте так же, как структура if-then-else точно соответствует синтаксическому уравнению БНФ.

ОК, откомпилируйте и протестируйте эту новую версию синтаксического анализатора. Это не слишком сильно повредило, не так ли?

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

До этого момента мы создавали то, что называется «предсказывающим синтаксическим анализатором». Это означает, что в любой точке мы можем, смотря на текущий предсказывающий символ, точно знать, что будет дальше. Но не в том случае когда мы добавляем функции. В каждом языке имеются некоторые правила присваивания имен, по которым составляется допустимый идентификатор. Наши правила пока просты, так как идентификатором является одна из букв "a"…"z". Проблема состоит в том, что имена переменных и имена функций подчиняются одним и тем же правилам. Поэтому как мы можем сказать кто из них кто? Один из способов требует, чтобы каждое из них было объявлено перед тем, как оно используется. Этот метод использует Pascal. Другой способ состоит в том, чтобы функция сопровождалась списком параметров (возможно пустым). Это правило, используемое в C.

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

X().

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

Сейчас существуют две варианта для ветки «If IsAlpha» при проверке в процедуре Factor. Давайте обработаем их в отдельной процедуре. Изменим процедуру Factor следующим образом:

{–}

{ 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 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;

{–}

Откомпилируйте и протестируйте эту версию. Обрабатывает ли она все правильные выражения и корректно отмечает неправильные?

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

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

Имеется еще одна важная проблема, которую стоит отметить: обработка ошибок. Обратите внимание, что хотя синтаксический анализатор правильно отбрасывает (почти) каждое некорректное выражение, которое мы ему подбросим, со значимым сообщением об ошибке, в действительности мы не слишком много поработали для того, чтобы это происходило. Фактически во всей программе (от Ident до Expression) есть только два вызова подпрограммы обработки ошибок Expected. Но даже они не являются необходимыми… если вы посмотрите снова на процедуры Term и Expression, то увидите, что эти утверждения не выполнятся никогда. Я поместил их сюда ранее для небольшой подстраховки, но сейчас они более не нужны. Почему бы не удалить их сейчас?

Но как мы получали такую хорошую обработку ошибок фактически бесплатно? Просто я тщательно старался избежать чтения символа непосредственно используя GetChar. Взамен я возложил на GetName, GetNum и Match выполнение всей обработки ошибок для меня. Проницательные читатели заметят, что некоторые вызовы Match (к примеру в Add и Subtract) также не нужны… мы уже знаем чем является символ к этому времени… но их присутствие сохраняет некоторую симметрию, и было бы хорошим правилом всегда использовать Match вместо GetChar.

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

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

Но это также очень легко исправить, даже если это только временно. Все, что мы должны сделать – постановить, что выражение должно заканчиваться концом строки, то есть, возвратом каретки.

Чтобы понять о чем я говорю, испробуйте входную строку:

1+2 <space> 3+4

Видите, как пробел был обработан как признак завершения? Чтобы заставить компилятор правильно отмечать это, добавьте строку

if Look <> CR then Expected('Newline');

в основную программу, сразу после вызова Expression. Это отлавливает все левое во входном потоке. Не забудьте определить CR в разделе const:

CR = ^M;

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

Итак, к этому моменту мы имеем синтаксический анализатор, работающий очень хорошо. Я хотел бы подчеркнуть, что мы получили это, используя всего 88 строк выполнимого кода, не считая того, что было в Cradle. Откомпилированный объектный файл занял 4752 байта. Неплохо, учитывая то, что мы не слишком старались сохранять размеры как исходного так и объектного кода. Мы просто придерживались принципа KISS.

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

<Ident> = <Expression>

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

{–}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: char;

begin

Name := GetName;

Match('=');

Expression;

EmitLn('LEA ' + Name + '(PC),A0');

EmitLn('MOVE D0,(A0)')

end;

{–}

Обратите внимание снова, что код полностью соответствует БНФ. И заметьте затем, что проверка ошибок была безболезненна и обработана GetName и Match.

Необходимость двух строк ассемблера возникает из-за особенности 68000, который требует такого вида конструкции для PC-относительного кода.

Теперь измените вызов Expression в основной программе на Assigment. Это все, что нужно.

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

Конечно, это не единственный вид. Есть также немного таких элементов, как управляющие структуры (ветвления и циклы), процедуры, объявления и т.д. Но не унывайте. Арифметические выражения, с которыми мы имели дело, относятся к самым вызывающим элементам языка. По сравнению с тем, что мы уже сделали, управляющие структуры будут выглядеть простыми. Я расскажу о них в пятой главе. И все другие операторы поместятся в одной строчке, пока мы не забываем принцип KISS.

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

Большинство компиляторов выделяют обработку входного потока в отдельный модуль, называемый лексическим анализатором (сканером). Идея состоит в том, что сканер работает со всей последовательностью символов во входном потоке и возвращает отдельные единицы (лексемы) потока. Возможно придет время, когда мы также захотим сделать что-то вроде этого, но сейчас в этом нет необходимости. Мы можем обрабатывать многосимвольные токены, которые нам нужны, с помощью небольших локальных изменений в GetName и GetNum.

Обычно признаком идентификатора является то, что первый символ должен быть буквой, но остальная часть может быть алфавитно-цифровой (буквы и цифры). Для работы с ними нам нужна другая функция:

{–}

{ Recognize an Alphanumeric }

function IsAlNum(c: char): boolean;

begin

IsAlNum := IsAlpha(c) or IsDigit(c);

end;

{–}

Добавьте эту функцию в анализатор. Я поместил ее сразу после IsDigit. Вы можете также включить ее как постоянного члена в Cradle.

Теперь нам необходимо изменить функцию GetName так, чтобы она возвращала строку вместо символа:

{–}

{ Get an Identifier }

function GetName: string;

var Token: string;

begin

Token := '';

if not IsAlpha(Look) then Expected('Name');

while IsAlNum(Look) do begin

Token := Token + UpCase(Look);

GetChar;

end;

GetName := Token;

end;

{–}

Аналогично измените GetNum следующим образом:

{–}

{ Get a Number }

function GetNum: string;

var Value: string;

begin

Value := '';

if not IsDigit(Look) then Expected('Integer');

while IsDigit(Look) do begin

Value := Value + Look;

GetChar;

end;

GetNum := Value;

end;

{–}

Достаточно удивительно, что это фактически все необходимые изменения! Локальная переменная Name в процедурах Ident и Assignment были первоначально объявлены как «char» и теперь должны быть объявлены как string[8]. (Ясно, что мы могли бы сделать длину строки больше, если бы захотели, но большинство ассемблеров в любом случае ограничивают длину.) Внесите эти изменения и затем откомпилируйте и протестируйте. Сейчас вы верите, что это просто?

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

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

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

Неудивительно, что мы начинаем с еще одной подпрограммы распознавания:

{–}

{ Recognize White Space }

function IsWhite(c: char): boolean;

begin

IsWhite := c in [' ', TAB];

end;

{–}

Нам также нужна процедура, «съедающая» символы пробела до тех пор, пока не найдет отличный от пробела символ:

{–}

{ Skip Over Leading White Space }

procedure SkipWhite;

begin

while IsWhite(Look) do

GetChar;

end;

{–}

Сейчас добавьте вызовы SkipWhite в Match, GetName и GetNum как показано ниже:

{–}

{ Match a Specific Input Character }

procedure Match(x: char);

begin

if Look <> x then Expected('''' + x + '''')

else begin

GetChar;

SkipWhite;

end;

end;

{–}

{ Get an Identifier }

function GetName: string;

var Token: string;

begin 

Token := ''; 

if not IsAlpha(Look) then Expected('Name'); 

while IsAlNum(Look) do begin 

Token := Token + UpCase(Look); 

GetChar; 

end; 

GetName := Token; 

SkipWhite;

end;

{–}

{ Get a Number }

function GetNum: string;

var Value: string;

begin 

Value := ''; 

if not IsDigit(Look) then Expected('Integer'); 

while IsDigit(Look) do begin 

Value := Value + Look; 

GetChar; 

end; 

GetNum := Value; 

SkipWhite;

end;

{–}

(Обратите внимание, как я немного реорганизовал Match без изменения функциональности.)

Наконец, мы должны пропустить начальные пробелы в том месте, где мы «запускаем помпу» в Init:

{–}

{ Initialize }

procedure Init;

begin

GetChar;

SkipWhite;

end;

{–}

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

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

{–}

program parse;

{–}

{ Constant Declarations }

const TAB = ^I;

CR = ^M;

{–}

{ Variable Declarations }

var Look: char; { Lookahead Character }

{–}

{ Read New Character From Input Stream }

procedure GetChar;

begin

Read(Look);

end;

{–}

{ Report an Error }

procedure Error(s: string);

begin

WriteLn;

WriteLn(^G, 'Error: ', s, '.');

end;

{–}

{ Report Error and Halt }

procedure Abort(s: string);

begin

Error(s);

Halt;

end;

{–}

{ Report What Was Expected }

procedure Expected(s: string);

begin

Abort(s + ' Expected');

end;

{–}

{ Recognize an Alpha Character }

function IsAlpha(c: char): boolean;

begin

IsAlpha := UpCase(c) in ['A'..'Z'];

end;

{–}

{ Recognize a Decimal Digit }

function IsDigit(c: char): boolean;

begin

IsDigit := c in ['0'..'9'];

end;

{–}

{ Recognize an Alphanumeric }

function IsAlNum(c: char): boolean;

begin

IsAlNum := IsAlpha(c) or IsDigit(c);

end;

{–}

{ Recognize an Addop }

function IsAddop(c: char): boolean;

begin

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

end;

{–}

{ Recognize White Space }

function IsWhite(c: char): boolean;

begin

IsWhite := c in [' ', TAB];

end;

{–}

{ Skip Over Leading White Space }

procedure SkipWhite;

begin

while IsWhite(Look) do

GetChar;

end;

{–}

{ Match a Specific Input Character }

procedure Match(x: char);

begin

if Look <> x then Expected('''' + x + '''')

else begin

GetChar;

SkipWhite;

end;

end;

{–}

{ Get an Identifier }

function GetName: string;

var Token: string;

begin

Token := '';

if not IsAlpha(Look) then Expected('Name');

while IsAlNum(Look) do begin

Token := Token + UpCase(Look);

GetChar;

end;

GetName := Token;

SkipWhite;

end;

{–}

{ Get a Number }

function GetNum: string;

var Value: string;

begin

Value := '';

if not IsDigit(Look) then Expected('Integer');

while IsDigit(Look) do begin

Value := Value + Look;

GetChar;

end;

GetNum := Value;

SkipWhite;

end;

{–}

{ Output a String with Tab }

procedure Emit(s: string);

begin

Write(TAB, s);

end;

{–}

{ Output a String with Tab and CRLF }

procedure EmitLn(s: string);

begin

Emit(s);

WriteLn;

end;

{–}

{ Parse and Translate a Identifier }

procedure Ident;

var Name: string[8];

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;

{–}

{ 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

Factor;

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

if IsAddop(Look) then

EmitLn('CLR D0')

else

Term;

while IsAddop(Look) do begin

EmitLn('MOVE D0,-(SP)');

case Look of

'+': Add;

'-': Subtract;

end;

end;

end;

{–}

{ Parse and Translate an Assignment Statement }

procedure Assignment;

var Name: string[8];

begin

Name := GetName;

Match('=');

Expression;

EmitLn('LEA ' + Name + '(PC),A0');

EmitLn('MOVE D0,(A0)')

end;

{–}

{ Initialize }

procedure Init;

begin

GetChar;

SkipWhite;

end;

{–}

{ Main Program }

begin

Init;

Assignment;

If Look <> CR then Expected('NewLine');

end.

{–}

Теперь синтаксический анализатор закончен. Он получил все возможности, которые мы можем разместить в однострочном «компиляторе». Сохраните его в безопасном месте. В следующий раз мы перейдем к новой теме, но мы все рано будем некоторое время говорить о выражениях. В следующей главе я планирую рассказать немного об интерпретаторах в противоположность компиляторам и показать вам как немного изменяется структура синтаксического анализатора в зависимости от изменения характера принимаемых действий. Информация, которую мы рассмотрим, хорошо послужит нам позднее, даже если вы не интересуетесь интерпретаторами. Увидимся в следующий раз.