StartState : begin
if (Ch = '+') or (Ch = '-') then
State := GotSign else
if (Ch = DecimalSeparator) then
State := GotInitDecPt else
if TDIsdigit(Ch) then
State := GotInitDigit else
Exit;
end;
GotSign : begin
if (Ch = DecimalSeparator) then
State := GotInitDecPt else
if TDIsDigit(Ch) then
State := GotInitDigit else Expend;
GotInitDigit : begin
if (Ch = DecimalSeparator) then
State := ScanDigits else
if not TDIsDigit(Ch) then
Exit;
end;
GotInitDecPt : begin
if TDIsDigit(Ch) then
State := ScanDigits else Expend;
ScanDigits : begin
if not TDIsDigit (Ch) then
Exit;
end;
end;
end;
{в этой точке число допустимо, если текущее состояние является конечным}
if (State = GotInitDigit) or (State = ScanDigits) then
Result := true;
end;
Исходный код подпрограммы IsValidNumber можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.
Если сравнить коды, приведенные в листингах 10.3 и 10.4, невозможно не заметить, что код NFA-автомата значительно сложнее. Он содержит целый набор вспомогательных подпрограмм, которые необходимо закодировать и поддерживать. Он также более чреват ошибками (необходимо побеспокоиться о поддержке стека, о возврате конечного автомата к предшествующему состоянию, о выборе следующего перехода и т.п.).
В общем случае, если требуется фиксированный, заранее определенный автомат, следует попытаться разработать и использовать детерминированный автомат. Следует попытаться свести реализацию недетерминированных автоматов к автоматическим алгоритмам. Реализация их вручную - чересчур трудоемкая задача.
Конечно, в рассмотренном примере NFA-автомат (и в примере его аналога DFA-автомата) мы всего лишь проверяем, является ли строка текстовым описанием целого числа или числа с плавающей точкой. Обычно желательно также вычислить интересующее число, а это усложняет код реализации переходов. Реализация этой функции при использовании DFA-автомата достаточно проста. Мы устанавливаем значение аккумуляторной (накопительной) переменной равным 0. При декодировании каждой цифры, расположенной перед десятичной точкой, мы умножаем значение аккумуляторной переменной на 10.0 и добавляем к нему значение новой цифры. Для цифр, следующих за десятичной точкой, мы поддерживаем значение счетчика текущего десятичного разряда и увеличиваем его на единицу при считывании каждой цифры. Для каждой такой цифры мы добавляем ее значение, умноженное на 0.1 в степени, соответствующей достигнутой десятичной позиции.
А как насчет NFA-автомата? Что ж, в этом случае решить задачу достаточно трудно. Вся сложность обусловлена необходимостью реализации алгоритма отхода. В любой момент времени внезапно может оказаться, что необходимо вернуться к предыдущему состоянию. В примере преобразования строки в число с плавающей точкой это не очень страшно: при заталкивании выбора в стек достаточно сохранить в нем и текущее значение аккумуляторной переменной (и значения всех необходимых дополнительных переменных). При выполнении отхода в качестве данных для восстановления состояния в момент неудачного выбора мы вытолкнем из стека и значение накопительной переменной.
Теперь снова обратимся к теме, в связи с которой рассматривались NFA-автоматы. Поговорим о регулярных выражениях. Прежде всего, вспомним, что они собой представляют. По существу, регулярные выражения (regular expression) - это мини-язык простого описания шаблона, предназначенного для поиска текста (или, если говорить более строго, совпадающего с ним текста). В самой простой форме регулярное выражение состоит из слова или набора символов, Однако, используя стандартные метасимволы (или символы операций регулярного выражения), можно выполнять поиск более сложных шаблонов. Стандартными метасимволами являются "." (соответствует любому символу, кроме символа новой строки), "?" (соответствует нулю или более повторений предыдущего подвыражения), "*" (соответствует нулю или более повторений предыдущего подвыражения), "+" (соответствует одному или более повторений предыдущего подвыражения) и "|" (символ операции ИЛИ, которая устанавливает соответствие с левым или с правым подвыражением). Можно определить также класс символа для установки соответствия с одним из наборов символов. Если первым символом класса символов является "^", это означает отрицание класса. Т.е. символы класса не должны совпадать с остальными символами набора.
Правила представления регулярных выражений, с которыми мы будем работать, показаны на рис. 10.5. Они записаны в стандартной форме BNF (Backu;
Naur Form - форма Бэкуса-Наура, БНФ). "::=" означает "определено как", а "|" означает "ИЛИ". Следовательно, первая строка означает следующее: <выражение> является либо <членом>, либо <членом>, за которым следует символ вертикальной черты, а за ним - еще одно <выражение>. Вторая строка означает: <член> - это либо <коэффициент>, либо <коэффициент> за которым следует <член>, и т.д. Это определение грамматических правил (они называются "грамматическими", поскольку определяют язык. Если обратиться к справочной системе Delphi, в ней можно найти грамматические правила языка Object Pascal. Они определены таким же образом.) может использоваться для генерирования подпрограммы вычисления регулярного выражения. Вскоре мы увидим, как это делается. А пока примите к сведению, что определение грамматических правил может использоваться для быстрой проверки того, что данное регулярное выражение является правильным.
Вероятно, лучше привести несколько примеров регулярных выражений. Это поможет понять их применение.
Рис.10.5.Грамматические правила составления регулярных выражений, представленные в форме БНФ
Это регулярное выражение соответствует имени идентификатора в языке Pascal. Первое заключенное в квадратные скобки подвыражение - класс символов, из определения которого следует, что первым символом строки, для которой будет устанавливаться соответствие, должна быть буква, прописная или строчная, или символ подчеркивания. Второе заключенное в квадратные скобки подвыражение - еще один класс символов, совпадающий с первым, за исключением того, что в него добавлены цифры. Этот шаблон может повторяться ноль или более раз (что определено символом * в конце регулярного выражения). Таким образом, этому регулярному выражению соответствует буква или символ подчеркивания, за которой следует ноль или более букв, символов подчеркивания или цифр.
(+|-)?[0-9]+(.[0-9]+)?
Это регулярное выражение соответствует представлению целого числа или числа с плавающей точкой в языке Pascal. Оно означает необязательный знак, одну или более цифр и необязательную дробную часть. Дробная часть состоит из десятичной точки, за которой следует одна или более цифр. Если дробная часть отсутствует, число является целым. Если она присутствует, число является числом с плавающей точкой.
{[^}]*}
Этот последний пример регулярного выражения соответствует комментарию в языке Pascal, который помещается в фигурные скобки. Выражение означает наличие открывающей фигурной скобки, за которой следует ноль или более символов, ни один из которых не является закрывающей скобкой, а затем следует закрывающая фигурная скобка.
Существует три этапа использования регулярного выражения. На первом регулярное выражение разбивается на составляющие его лексемы, на втором они преобразуются форму, пригодную для установки соответствия (компиляция регулярного выражения) и на заключительном этапе скомпилированная форма регулярного выражения используется для собственно установки соответствия со строками. Этот материал изложен в данной главе потому, что скомпилированная форма регулярного выражения реализуется в виде NFA-автомата.