Короткий пример регулярного выражения преобразовывается в конечный автомат?

Я уверен, что у кого-то есть лучшие примеры, но Вы могли проверка это сообщение Phil Haack , который имеет пример регулярного выражения и конечного автомата, делающего то же самое (существует предыдущее сообщение еще с несколькими regex примерами там также, я думаю..)

Проверка "HenriFormatter" на той странице.

Сделайте свое собственное на лету!

http://osteele.com/tools/reanimator/???

Это - действительно приятно соединенный инструмент, который визуализирует регулярные выражения как FSMs. Это не имеет поддержки части синтаксиса, который Вы найдете в реальных механизмах регулярного выражения, но конечно достаточно понять точно, что продолжается.

Довольно удобный способ помочь посмотреть на это для использования малоизвестного ре Python. Флаг DEBUG на любом шаблоне:

>>> re.compile(r'<([A-Z][A-Z0-9]*)\b[^>]*>(.*?)</\1>', re.DEBUG)
literal 60
subpattern 1
  in
    range (65, 90)
  max_repeat 0 65535
    in
      range (65, 90)
      range (48, 57)
at at_boundary
max_repeat 0 65535
  not_literal 62
literal 62
subpattern 2
  min_repeat 0 65535
    any None
literal 60
literal 47
groupref 1
literal 62

числа после 'литерала' и 'диапазона' относятся к целочисленным значениям символов ASCII, которым они, как предполагается, соответствуют.

Вопрос, "Как я выбираю состояния и условия перехода?", или, "Как я реализую свой абстрактный автомат в Foo?"

, Как я выбираю состояния и условия перехода?

я обычно использую FSMs для довольно простых проблем и выбираю их интуитивно. В мой ответ на другой вопрос о регулярных выражениях , я просто посмотрел на проблему парсинга как на один из того, чтобы быть или Inside или outside пара тега и выписал переходы оттуда (с началом и конечным состоянием для содержания реализации в чистоте).

, Как я реализую свой абстрактный автомат в Foo?

, Если Ваш язык реализации поддерживает структуру как c switch оператор, то Вы включаете текущее состояние и обрабатываете вход для наблюдения, какое действие и/или переход также работают затем.

Без switch - как структуры, или если они являются несовершенными в некотором роде, Вы if ветвление стиля. Тьфу.

Записанный все в одном месте в c пример, который я связал, будет выглядеть примерно так:

token_t token;
state_t state=BEGIN_STATE;
do {
   switch ( state.getValue() ) {
   case BEGIN_STATE;
      state=OUT_STATE;
      break;
   case OUT_STATE:
      switch ( token.getValue() ) {
         case CODE_TOKEN:
            state = IN_STATE;
            output(token.string());
            break;
         case NEWLINE_TOKEN;
            output("<break>");
            output(token.string());
            break;
         ...
      }
      break;
   ...
   }
} while (state != END_STATE);

, который довольно грязен, таким образом, я обычно срываю эти state случаи к отдельным функциям.

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

Конечные автоматы является самым легким понять с помощью схем. Например:

сопроводительный текст http://img6.imageshack.us/img6/7571/mathfinitestatemachinedco3.gif

, который Все это говорит, - то, что, если Вы начинаете в некотором состоянии q0 (тот с Начальным символом рядом с ним) можно перейти к другим состояниям. Каждое состояние является кругом. Каждая стрелка представляет ввод или вывод (в зависимости от того, как Вы смотрите на нее). Другой способ думать о конечном автомате с точки зрения "допустимого" или "приемлемого" входа. Существуют определенные выходные строки, которые НЕ являются возможными определенными конечными автоматами; это позволило бы Вам "соответствовать" выражениям.

Теперь предполагают, что Вы запускаете в q0. Теперь при вводе 0, Вы пойдете для утверждения q1. Однако при вводе 1, Вы пойдете для утверждения q2. Вы видите это символами выше стрелок ввода/вывода.

Скажем, Вы запускаете в q0 и получаете этот вход

0, 1, 0, 1, 1, 1

Это означает прохождение через состояний (никакой вход для q0, Вы только запускаете там):

q0-> q1-> q0-> q1-> q0-> q2-> q3-> Трассировка q3

изображение с Вашим пальцем, если это не имеет смысла. Заметьте, что q3 возвращается к себе для обоих исходных данных 0 и 1.

Другой способ сказать все это, "Если Вы находитесь в состоянии q0, и Вы видите, что 0 переходит к q1, но если Вы видите, что 1 переходит к q2". При создании этих условий для каждого состояния, Вы почти сделаны, определив Ваш конечный автомат. Все, что необходимо сделать, имеют переменную состояния и затем способ накачать вход в, и это в основном, что там.

хорошо, итак, почему это важное относительно оператора Joel? Ну, создание "ОДНОГО РЕГУЛЯРНОГО ВЫРАЖЕНИЯ TRUE ДЛЯ УПРАВЛЕНИЯ ИХ ВСЕХ" может быть очень трудным и также трудным поддержать, изменяют или даже чтобы другие возвратились и поняли. Кроме того, в некоторых случаях это более эффективно.

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