Технология Клиент-Сервер 2002'2
	Home Поиск Издания Контакты k-press.ru

Продолжается подписка на наши издания! Вы не забыли подписаться?

Как проверить, является строка числом или e-mail'ом?

Николай Меркин

Предисловие. Формальные языки и конечные автоматы

Множества всех строк, записанных по некоторым правилам, называются формальными языками. Так, любой язык программирования, язык написания чисел и адресов e-mail – это формальные языки.

Грамматика языка. Формы записи.

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

Наиболее известная форма представления грамматики - это "форма Бэкуса-Наура" (БНФ): множество правил вида

<элемент> ::= цепочка из символов и/или <элементов>

что означает: в исходной цепочке можно заменить <элемент> (некоторый метасимвол, не входящий в алфавит языка) на другую цепочку.

Для сокращения записи используются регулярные выражения:

• A | B - произвольный выбор цепочки A или B.

• A* - повторить цепочку A 0 или более раз.

• [ A ] - вставить цепочку A 0 или 1 раз.

БНФ с элементами регулярных выражений называют Расширенной БНФ (РБНФ).

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

Конечный автомат (КА) – устройство, имеющее конечный набор состояний (им в данном случае соответствуют метасимволы), и конечный набор реакций на конечные же наборы входных и выходных сигналов (алфавиты).

состояние, входной сигнал -> новое состояние, выходной сигнал.

Программа, реализующая КА, очень проста. Номер (идентификатор) состояния хранится в регистре. При подаче входного сигнала находится правило с совпадающими текущим состоянием и входом. В соответствии с правилом, устанавливается новое состояние и выдается выходной сигнал.

Если есть разные правила с одинаковым условием, такой автомат называется недетерминированным (фактически, непредсказуемым). Если же у всех правил условия различаются – детерминированным (однозначным).

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

новое_состояние [ состояние, входной_сигнал ]
выходной_сигнал [ состояние, входной_сигнал ]

Автоматная грамматика. Порождающий автомат.

Грамматику языка, состоящую только из правил вида

<A> ::= символ <B>

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

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

A -> x B
A -> y C

мы можем из состояния А выдать как x, так и y.

Собственно, это и приводит к богатству языка (ДКА может порождать только либо бесконечную строку из одинаковых символов, либо 1-символьную, либо пустую).

Разбирающий автомат

Обработка исходной строки сводится к следующим задачам:

• Проверка на правильность (принадлежит ли строка языку).

• Трансляция (перевод в иное представление, например, из строки - в машинное число).

Естественно, что трансляция включает в себя проверку: если строка неправильна, то перевести ее не удастся.

Для задач разбора (parsing, синтаксический анализ), то есть проверки и трансляции, строится автомат, на вход которого посимвольно подается исходная строка, а на выходе – какие-либо диагностические сигналы (правильно/неправильно/продолжать).

Этот автомат должен быть детерминированным (однозначным); в противном случае его работа непредсказуема.

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

Фактически, такой автомат получается из порождающего:

порождающий: A, tact -> x, B
разбирающий: A, x -> B, diagnostics

Если получился недетерминированный автомат, то есть

A, x -> B
A, x -> C

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

A -> x, B заменяется на A -> x, N (вводим новое состояние)
A -> x, C заменяется на A -> x, N

Ко всем правилам, содержащим в условии B и С, добавляются новые:

B -> y, D добавляется N -> y, D

Автоматы для регулярных выражений

Ниже приведены способы написания правил для случаев, которые нас интересуют.

Здесь, R0 – исходное состояние перед порождением/разбором строки, а под z1 имеются в виду первые символы, которые могут идти в выражении, следующим за скобками.

Структура материала

Для каждого случая (целое число, вещественное число, адрес e-mail):

• определим грамматику в БНФ;

• напишем регулярное выражение;

• составим правила для разбирающего автомата;

• реализуем этот автомат различными способами;

• сравним производительность реализаций.

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

A, <digit> -> B

развертывается в

A, 0 -> B; ... A, 9 -> B

Итак, рассмотрим синтаксис искомых строк.

Целое число

Самый простой случай – десятичное число (или число в любой другой, наперёд заданной системе счисления):

БНФ

<Number> ::= [ <sign> ] <Digits>
<Digits> ::= <digit> [ <Digits> ]

Регулярное выражение

<Number> ::= <sign> <digit> <digit>*

Получаем достаточно очевидное решение (функции isSign, isDigit, isEnd могут быть реализованы любым способом, но наиболее простой способ – это сравнения).

Листинг 1. Функция checkInt

bool checkInt(const char* str)
{
    // [1] <sign>
    if(isSign(*str))    str++;
    // [2] <digit>
    if(!isDigit(*(str++)))  return false;
    // [3] <digit>*
    while(true)
    {
        char c = *(str++);
        if(isEnd(c))        return true;
        if(isDigit(c))  continue;
        return false;
    }
}

Число с плавающей точкой

БНФ

<Real_number> ::= <Mantissa> [ <E> <Exponent> ]
<Mantissa> :: = [<sign>] <Integer_part> [ <dot> [<Fractional_part>] ]
<Exponent> ::= [<sign>] <Unsigned_number>
<Integer_part> ::= <Unsigned_number>
<Fractional_part> ::= <Unsigned_number>
<Unsigned_number> ::= <digit> <digit>*
<sign> ::= + | -
<e> ::= E | e
<dot> ::= .

Регулярное выражение

[<sign>] <digit> <digit>* [<dot> <digit>* ] [ <e> [<sign>] <digit> <digit>* ]

Правила для автомата

Start = Mantissa1
Mantissa1 - начало мантиссы
	Mantissa1, <sign> -> Mantissa2
	Mantissa1, <digit> -> Mantissa3
Mantissa2 - начало целой части мантиссы
	Mantissa2, <digit> -> Mantissa3
	Mantissa2, <end> -> Success
Mantissa3 - наличие хотя бы одной цифры
	Mantissa3, <digit> -> Mantissa3
	Mantissa3, <dot> -> Mantissa4
	Mantissa3, <e> -> Exponent1
	Mantissa3, <end> -> Success
Mantissa4 - дробная часть
	Mantissa4, <digit> -> Mantissa4
	Mantissa4, <e> -> Indicator1
	Mantissa4, <end> -> Success
Exponent1 - начало порядка
	Exponent1, <sign> -> Exponent2
	Exponent1, <digit> -> Exponent3
Exponent2 - начало числа в порядке
	Exponent2, <digit> -> Exponent3
	Exponent2, <end> -> Success
Exponent3 - продолжение числа в порядке
	Exponent3, <digit> -> Exponent3
	Exponent3, <end> -> Success
(Во всех остальных случаях -> Error)

Реализация автомата на switch

Возможны два способа построения:

• Для каждого состояния автомата анализировать тип очередного символа.

• Для каждого типа очередного символа изменять состояние автомата.

Первый способ экономнее, так как для каждого состояния валидными являются не все типы символов.

Листинг 2. Функция checkFloat_S

inline bool isExp(char c) { return c == 'E' || c == 'e'; }
inline bool isDot(char c) { return c == '.'; }

bool checkFloat_S(const char* str)
{
    enum State { m1, m2, m3, m4, e1, e2, e3 } state = m1;
    while(true)
    {
        char c = *(str++);
        switch(state)
        {
        case m1:
            if(isSign(c))   state = m2;
            else if(isDigit(c)) state = m3;
            else return false;
            break;
        case m2:
            if(isDigit(c))  state = m3;
            else return false;
            break;
        case m3:
            if(isDigit(c))  state = m3;
            else if(isDot(c))   state = m4;
            else if(isExp(c))   state = e1;
            else if(isEnd(c))   return true;
            else return false;
            break;
        case m4:
            if(isDigit(c))  state = m4;
            else if(isExp(c))   state = e1;
            else if(isEnd(c))   return true;
            else return false;
            break;
        case e1:
            if(isSign(c))   state = e2;
            else if(isDigit(c)) state = e3;
            else return false;
            break;
        case e2:
            if(isDigit(c))  state = e3;
            else return false;
            break;
        case e3:
            if(isDigit(c))  state = m3;
            else if(isEnd(c))   return true;
            else return false;
            break;
        default:
            assert(false);
        }
    }
}

С другой стороны, если число типов символов меньше, чем число состояний, то можно пойти по второму пути.

Реализация с анализом типов символов

Листинг 3. Функция checkFloat_C

bool checkFloat_C(const char* str)
{
    enum State { m1, m2, m3, m4, e1, e2, e3, states_count, ok, er };
    enum CharType { cEnd, cDigit, cSign, cDot, cExp };
    typedef State Transfers[states_count];

    static const Transfers tEnd     = { er, er, ok, ok, er, er, ok };
    static const Transfers tDigit   = { m3, m3, m3, m4, e3, e3, e3 };
    static const Transfers tSign    = { m2, er, er, er, e2, er, er };
    static const Transfers tDot     = { er, er, m4, er, er, er, er };
    static const Transfers tExp     = { er, er, e1, e1, er, er, er };

    State state = m1;
    while(true)
    {
        char c = *(str++);

        if      (isEnd  (c))    state = tEnd  [state];
        else if (isDigit(c))    state = tDigit[state];
        else if (isSign (c))    state = tSign [state];
        else if (isDot  (c))    state = tDot  [state];
        else if (isExp  (c))    state = tExp  [state];

        if(state > states_count)
            return state == ok;
    }

Реализация на таблице

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

• Проверка диапазона символа.

• Получение нового состояния из матрицы.

• Проверка состояния на "конец работы".

Листинг 4. Функция checkFloat_T

bool checkFloat_T(const char* str)
{
    const char char_min = '+';
    const char char_max = 'e';
    // +,-./012456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde

    enum State { er = -2, ok = -1, m1, m2, m3, m4, e1, e2, e3, states_count };

// макросы для заполнения таблицы переходов (см.ниже)
#define t_5(state) state,state,state,state,state
#define t_10(state) t_5(state), t_5(state)
#define er_5 t_5(er)
#define er_10 er_5, er_5

#define t_sign(state) state, er, state  // until '.'
#define t_dot(state) state, er // until '0'
#define t_digits(state) t_10(state), er_10, er // until 'E'
#define t_exp(state) state, er_10, er_10, er_10, er, state

#define t_all(end, sign, dot, digits, exp)  \
    { end, t_sign(sign), t_dot(dot), t_digits(digits), t_exp(exp) }

    static const State transfer[states_count][char_max - char_min + 2] =
    {
        /*m1*/  t_all(er, m2, er, m3, er),
        /*m2*/  t_all(er, er, er, m3, er),
        /*m3*/  t_all(ok, er, m4, m3, e1),
        /*m4*/  t_all(ok, er, er, m4, e1),
        /*e1*/  t_all(er, e2, er, e3, er),
        /*e2*/  t_all(er, er, er, e3, er),
        /*e3*/  t_all(ok, er, er, e3, er),
    };

#undef t_5
#undef t_10
#undef er_5
#undef er_10
#undef t_sign
#undef t_dot
#undef t_digits
#undef t_exp
#undef t_all

    State state = m1;
    while(true)
    {
        char c = *(str++);
        if(isEnd(c))
            return transfer[state][0] == ok;

        if(c < char_min || c > char_max)
            return false;

        state = transfer[state][c - char_min + 1];
        if(state == er)
            return false;
    }
}

E-mail

БНФ

<Email> ::= <Name> @ <Domain>
<Name> ::= <Words>
<Domain> ::= <Words>
<Words> ::= <Word> [  . <Words> ]
<Word> ::= <letter> <letter>*
<letter> - любые символы в диапазоне #33 (-) до #126 (~), кроме ()<>@,;:\/.[] (согласно RFC 822)

Регулярное выражение

<letter> <letter>* ( <dot> <letter> <letter>* )* <at> <letter> <letter>* (
<dot> <letter> <letter>* )*

Правила для автомата

Start = Name1
Name1 – начало слова в имени (должен быть буквенно-цифровой символ)
	Name1, <letter> -> Name2
Name2 – продолжение слова
	Name2, <letter> -> Name2
	Name2, <dot> -> Name1 (после точки должно быть новое слово)
	Name2, <at> -> Domain1
Domain1 – начало имени в домене
	Domain1, <letter> -> Domain2
Domain2 – продолжение домена
	Domain2, <letter> -> Domain2
	Domain2, <dot> -> Domain1
	Domain2, <end> -> Success
(Во всех остальных случаях -> Error)

Реализация автомата на switch

Листинг 5. Функция checkEmail_S

inline bool isLetter(char c) 
{
    return c >= 33 && c <= 126 && !strchr("()<>@,;:\.[]");
}
    
inline bool isAt(char c) { return c == '@'; }

bool checkEmail_S(const char* str)
{
    enum State { n1, n2, d1, d2 };
    State state = n1;
    while(true)
    {
        char c = *(str++);
        switch(state)
        {
        case n1:
            if(isLetter(c))     state = n2;
            else                return false;
            break;
        case n2:
            if(isLetter(c))     state = n2;
            else if(isDot(c))   state = n1;
            else if(isAt(c))    state = d1;
            else                return false;
            break;
        case d1:
            if(isLetter(c))     state = d2;
            else                return false;
            break;
        case d2:
            if(isLetter(c))     state = d2;
            else if(isDot(c))   state = d1;
            else if(isEnd(c))   return true;
            else                return false;
            break;
        }
    }
}

Реализация с анализом типов символов

Листинг 6. Функция checkEmail_C

bool checkEmail_C(const char* str)
{
    enum State { n1, n2, d1, d2, states_count, ok, er };
    typedef State Transfers[states_count];

    enum CharType { cEnd, cLetter, cDot, cAt };
    Transfers tEnd    = { er, er, er, ok };
    Transfers tLetter = { n2, n2, d2, d2 };
    Transfers tDot    = { er, n1, er, d1 };
    Transfers tAt     = { er, d1, er, er };

    State state = n1;
    while(true)
    {
        char c = *(str++);

        if      (isEnd   (c))   state = tEnd   [state];
        else if (isLetter(c))   state = tLetter[state];
        else if (isDot   (c))   state = tDot   [state];
        else if (isAt    (c))   state = tAt    [state];

        if(state > states_count)
            return state == ok;
    }
}

Реализация на таблице

Листинг 7. Функция checkEmail_T

bool checkEmail_T(const char* str)
{
    const char char_min = '-';  // #33
    const char char_max = '~';  // #126
// в этот диапазон входят:
    //  -
    //  .
    //  /
    //  012456789
    //  :;<=>?
    //  @
    //  ABCDEFGHIJKLMNOPQRSTUVWXYZ
    //  [\]^
    //  _
    //  `
    //  abcdefghijklmnopqrstuvwxyz
    //  { | }
    //  ~

    enum State { er = -2, ok = -1, n1, n2, d1, d2, states_count };

// макросы для заполнения таблицы переходов (см.ниже)
#define t_4(st)     st,st,st,st
#define t_6(st)     st,st,st,st,st,st
#define t_10(st)    t_6(st), t_4(st)
#define t_26(st)    t_10(st), t_10(st), t_6(st)

#define er_3        er,er,er
#define er_4        t_4(er)
#define er_6        t_6(er)

#define t_dot(st)       st, er
#define t_digits(st)    t_10(st), er_6
#define t_at(st)        st
#define t_alpha(st)     t_26(st), er_4, st, er, t_26(st), er_3, st

#define t_all(end, dot, at, letter) \
    { end, letter, t_dot(dot), t_digits(letter), t_at(at), t_alpha(letter) }

    // под индексом [0] идет реакция на конец строки
    // анализ символов начинается с [1]: index = c - char_min + 1

    static const State transfer[states_count][char_max-char_min+2] =
    {
        t_all(er,er,er,n2),
        t_all(er,n1,d1,n2),
        t_all(er,er,er,d2),
        t_all(ok,d1,er,d2),
    };

#undef t_4
#undef t_6
#undef t_10
#undef t_26
#undef er_3
#undef er_4
#undef er_6
#undef t_dot
#undef t_digits
#undef t_at
#undef t_alpha
#undef t_all

    State state = n1;
    while(true)
    {
        char c = *(str++);
        if(isEnd(c))
            return transfer[state][0] == ok;
        if(c < char_min || c > char_max)
            return false;
        state = transfer[state][c - char_min + 1];
        if(state == er)
            return false;
    }
}

Сравнение скорости работы

Для сравнения была написана "бенчмарка", которая вычисляла каждую из функций 100 000 раз, измеряя длительность работы в тиках (1 тик = 55 мс). Испытания проводились на Pentium-II-400, под управлением Windows 2000. Компилятор – MSVC-6 (без оптимизации). Погрешность измерений составляет приблизительно 10 тиков (0.5 с), что связано, по-видимому, с загрузкой компьютера фоновыми процессами. Измерения проводились как для правильных, так и неправильных строк (тем самым, проверяется скорость принятия решения).

Превосходство табличного метода - налицо.

Число с плавающей точкой

Заодно проверим скорость системных функций...

E-mail

Copyright © 1994-2016 ООО "К-Пресс"