Давайте создадим компилятор!

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

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

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

Эксперименты по сканированию

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

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

::= [ | ]*

]+

(Не забудьте, что "*" указывает на ноль или более повторений условия в квадратных скобках, а "+" на одно и более.)

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

{–}

{ Recognize an Alphanumeric Character }

function IsAlNum(c: char): boolean;

begin

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

end;

{–}

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

{–}

{ Get an Identifier }

function GetName: string;

var x: string[8];

begin

x := '';

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

while IsAlNum(Look) do begin

x := x + UpCase(Look);

GetChar;

end;

GetName := x;

end;

{–}

{ Get a Number }

function GetNum: string;

var x: string[16];

begin

x := '';

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

while IsDigit(Look) do begin

x := x + Look;

GetChar;

end;

GetNum := x;

end;

{–}

(Заметьте, что эта версия GetNum возвращает строку, а не целое число, как прежде).

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

WriteLn(GetName);

Эта программа выведет любое допустимое набранное имя (максимум восемь знаков, потому что мы так сказали GetName). Она отвергнет что-либо другое.

Аналогично проверьте другую подпрограмму.

Пробел

Раньше мы также работали с вложенными пробелами, используя две подпрограммы IsWhite и SkipWhite. Удостоверьтесь, что эти подпрограммы есть в вашей текущей версии Cradle и добавьте строку:

SkipWhite;

в конец GetName и GetNum.

Теперь давайте определим новую процедуру:

{–}

{ Lexical Scanner }

Function Scan: string;

begin

if IsAlpha(Look) then

Scan := GetName

else if IsDigit(Look) then

Scan := GetNum

else begin

Scan := Look;

GetChar;

end;

SkipWhite;

end;

{–}

Мы можем вызвать ее из новой основной программы:

{–}

{ Main Program }

begin

Init;

repeat

Token := Scan;

writeln(Token);

until Token = CR;

end.

{–}

(Вы должны добавить описание строки Token в начало программы. Сделайте ее любой удобной длины, скажем 16 символов).

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

Конечные автоматы