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

{–}

{ 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 символов).

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

Подпрограмма анализа типа GetName действительно реализует конечный автомат. Состояние неявно в текущей позиции в коде. Очень полезным приемом для визуализации того, что происходит, является синтаксическая диаграмма или «railroad-track» диаграмма. Немного трудно нарисовать их в этой среде, поэтому я буду использовать их очень экономно, но фигура ниже должна дать вам идею:

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

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

Из-за сложностей представления «railroad-track» диаграмм в этой среде я буду продолжать придерживаться с этого времени синтаксических уравнений. Но я настоятельно рекомендую вам диаграммы для всего, что включает синтаксический анализ. После небольшой практики вы можете начать видеть, как написать синтаксический анализатор непосредственно из диаграммы. Параллельные пути кодируются в контролирующие действия (с помощью операторов IF или CASE), последовательные пути – в последовательные вызовы. Это почти как работа по схеме.

Мы даже не обсудили SkipWhite, которая была представлена раньше, но это также простой конечный автомат, как и GetNum. Так же как и их родительская процедура Scan. Маленькие автоматы образуют большие автоматы.

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

Продвигаясь прямо вперед, давайте модифицируем наш сканер для поддержки более чем одной строки. Как я упомянул последний раз, наиболее простой способ сделать это – просто обработать символы новой строки, возврат каретки и перевод строки, как незаполненное пространство. Фактически это способ, используемый подпрограммой iswhite из стандартной библиотеки C. Прежде мы не этого делали. Я хотел бы сделать это теперь, чтобы вы могли почувствовать результат.

Чтобы сделать это просто измените единственную выполнимую строку в IsWhite:

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

Мы должны дать основной программы новое условие останова, так как она никогда не увидит CR. Давайте просто используем: