Является ли использование конечного автомата хорошим дизайном для общего анализа текста? - PullRequest
Новая
       33

Является ли использование конечного автомата хорошим дизайном для общего анализа текста?

2 голосов
/ 06 мая 2010

Я читаю файл, который заполнен с шестнадцатеричными числами. Я должен определить конкретный образец, скажем "aaad" (без кавычек) из Это. Каждый раз, когда я вижу образец, я сгенерировать некоторые данные в другой файл.

Это было бы очень распространенным случаем при разработке программ - парсинг и поиск определенного шаблона .

Я спроектировал его как Конечный автомат и структурировал его в C, используя switch-case для изменения состояний. Это была первая реализация, которая произошла со мной.

  • КОНСТРУКЦИЯ: Возможно ли улучшить дизайн?
  • РЕАЛИЗАЦИЯ: Видите ли вы некоторые проблемы с использованием корпуса переключателя, как я уже упоминал?

Ответы [ 2 ]

1 голос
/ 06 мая 2010

Для смущающе простых случаев достаточно пары if или switch. Для анализа строки в системах POSIX: man regex (3) . Для полнофункционального анализа целых файлов (например, сложных конфигураций) используйте Lex / Flex и Yacc / Bison .

При написании на C ++ посмотрите Boost Regex для более простого случая и Boost Spirit для более сложного. Flex & Bison также работает с C ++.

1 голос
/ 06 мая 2010

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

Вероятно, нет причин менять то, что вы уже разработали / реализовали, но если вы заинтересованы в методах синтаксического анализа текста общего назначения, вам, вероятно, следует рассмотреть такие вещи, как регулярные выражения, Flex, Bison и ANTLR. *

...