Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:

Error. Page cannot be displayed. Please contact your service provider for more details. (18)


Использование конечных автоматов

Поиск:
Я не хочу давать формальных определений, цель этой заметки --- показать "на пальцах" использование конечных автоматов (КА) для решения различных задач разбора.

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

Заданная грамматика позволяет указать, какая строка символов принадлежит некоторому множеству, а какая --- нет. Можно привести пример с множеством корректных URL-адресов: грамматика, заданная соответствующим RFC, указывает на то, какие строки являются правильными URL-адресами, а какие --- нет.

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

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

Простейший детерминированый КА работает следующим образом: в нем находится внутренний регистр для хранения текущего состояния и таблица правил вида "символ-состояние ===> состояние" позволяющая по текущему символу на ленте и текущему состоянию перейти в другое состояние (со сдвигом по ленте). Цепочка символов допустима, если КА завершил свою работу в одном из "разрешенных" состояний и не допустима в обратном случае.

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

Прототип функции, разбирающей текст:

Код

    void parse(const char* string);


Будем считать, что результат работы будет доступен... только внутри функции ;) это не принципиально; мы просто подсчитаем количество слов и чисел в исходном тексте. Для того, что бы хранить текущее состояние, вводится соответствующая переменная (лучше всего использовать перечислимый тип --- нагляднее).

Код

    enum
    {
       skip,
       sign,
       digit,
       letter,
       finish
    } state = skip;


Рассматриваемый тип КА работает без возвратов (на это прошу обратить особое внимание --- для разбора строки потребуется только один проход):

Код

    for(const char* current = string; state != finish; current++)
    {
      // ...
    }


Вышеприведенный цикл как раз и организует этот проход. Теперь интереснее всего содержимое цикла. Оно состоит из оператора switch:

Код

    switch(state)
    {
    case skip   : // ...
    case sign   : // ...
    case letter : // ...
    case digit  : // ...
    case finish : // ...
    }


Т.е., используется для определения текущего состояния КА и перехода в новое. Последний case введен для общности --- при его отсутствии компилятор gcc с флагом -Wall выдаст предупреждение о том, что не все варианты перечислимой переменной были учтены в операторе выбора.

Состояние skip введено для того, что бы обеспечить пропуск всех сивмолов, не являющемеся буквами или цифрами. Логично, что именно с него начинает свою работу КА.
Код


    case skip :
      if(isalpha(*current)) { state = letter; break; }
      if(isdigit(*current)) { state = digit; break; }
      if(*current == '+' || *current == '-') { state = sign; break; }
      if(*current == 0) { state = finish; break; }
      break; 


В этом состоянии, при получении на вход буквы КА считает, что впереди --- слово, цифры или знака --- возможно число. Выражение типа *current == 0, а не !(*current) как написали бы некоторые умники, используется для повышения общности записи и для более удобного последующего чтения. Т.е., я не против записи if(*current), но отрицание там смотрится очень... незаметно, по-моему. Может быть, конечно же, я не прав --- это замечание касается "стиля", а подобные вопросы традиционно вызывают массовые споры ;)

Если на вход поступил знак, то:

Код

    case sign : 
      if(isdigit(*current)) { state = digit; break; }
      if(isalpha(*current)) { state = letter; break; }
      if(*current == 0) { state = finish; break; }
      state = skip;
      break;


После знака '+' или '-' в случае поступления на вход цифры все еще возможно, что обрабатывается число. Если попалась буква, то никакого числа не было, а началось слово. Во всех остальных случаях требуется вернуться к состоянию skip для того, что бы продолжить пропуск символов.

Код

    case digit :
      if(isdigit(*current)) break;
      if(isalpha(*current)) { state = letter; break; }
      count_of_numbers++;
      state == *current ? skip : finish;
      break;


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

Код

    case letter :
      if(isalpha(*current)) break;
      count_of_words++;
      state = *current ? skip : finish;
      break;


Собственно говоря, это все --- после выхода из цикла переменные count_of_numbers и count_of_words будут содержать в себе количество чисел и слов соответственно (перед входом в цикл их, конечно же, надо было обнулить).

Кто-то мог заметить, что в состоянии sign в данном случае нет необходимости. Это так, но оно введено для того, что бы было проще адаптировать этот пример не только к подсчету слов и чисел, а еще и к выделению слов и чисел со знаком.

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

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

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

Я видел очень много решений этой задачи, которые программисты делали "от сохи". Существуют специализированные алгоритмы поиска вхождений подстроки в строку (например, алгоритм Кнута-Мориса-Пратта), но то, что делают чаще всего, несколько сомнительно по своему качеству.

Обычно задача решается следующим образом: фиксируется некоторая позиция, начиная с нее сверяется совпадение с шаблоном, если совпадения не было --- берется следующая позиция за фиксированной и все повторяется снова.

Это совершенно неправильно! Все дело в том, что на каждой такой итерации теряется информация о том, что на предыдущем шаге символы строки уже сверялись с шаблоном (пусть, и в другом месте), а это можно было бы использовать. Для этого строится конечный автомат с состояниями, соотвествующими длине совпавшей подстроки и правилами, которые каждой паре "длина-символ" выставляют новую "длину" совпавшей подстроки. Например, для подстроки "ababc" можно говорить, что пары "2,a" и "4.a" соответствуют переходу в состояние 3.

Особенно заметен выигрыш построения таблицы переходов (это достаточно простая задача: по подстроке построить подобную таблицу) тогда, когда надо найти не первое, а последнее вхождение подстроки. Год назад я давал задачку на олимпиаде для первокурсников, в которой требовалось как раз найти в строке длиной до 1МБ последнее вхождение подстроки длиной до 255 символов. При этом был тест, в котором вся исходная строка и строка образец состояли из одних только букв "a". В этом случае, используя возвраты, потребовалось бы сделать 255*1024*1024 сравнения... и это ровно в 255 раз больше одного прохода.

Кстати, алгоритм Кнута-Мориса-Прата, в принципе, как раз и является вариацией на тему построения КА, только в нем указано каким именно образом строится таблица переходов.
Резюме

КА это очень полезный инструмент. Очень простой и надежный, к сожалению, о нем часто забывают...
Автор: Андрей Калинин
Сайт: http://www.kalinin.ru






Просмотров: 4318

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную