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

Ответ 1

Конечно, хотя вам понадобятся более сложные примеры, чтобы действительно понять, как работают RE. Рассмотрим следующий RE:

^[A-Za-z][A-Za-z0-9_]*$

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

state = FIRSTCHAR
for char in all_chars_in(string):
    if state == FIRSTCHAR:
            if char is not in the set "A-Z" or "a-z":
                error "Invalid first character"
            state = SUBSEQUENTCHARS
            next char
    if state == SUBSEQUENTCHARS:
            if char is not in the set "A-Z" or "a-z" or "0-9" or "_":
                error "Invalid subsequent character"
            state = SUBSEQUENTCHARS
            next char

Теперь, как я уже сказал, это очень простой пример. Он не показывает, как делать жадные/неподдельные совпадения, откат, соответствие внутри строки (а не всей строки) и другие более эзотерические функции состояний машин, которые легко обрабатываются синтаксисом RE.

Вот почему REs настолько сильны. Фактический конечный машинный код, необходимый для выполнения того, что может сделать однострочный RE, обычно очень длинный и сложный.

Лучшее, что вы могли бы сделать, это захватить копию некоторого кода lex/yacc (или эквивалентного) для конкретного простого языка и увидеть код, который он генерирует. Это не очень красиво (это не обязательно, так как он не должен быть прочитан людьми, они должны смотреть на код lex/yacc), но это может дать вам более полное представление о том, как они работают.

Ответ 2

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

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

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

Ответ 3

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

>>> 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

Цифры после "literal" и "range" относятся к целым значениям символов ascii, которые они должны соответствовать.

Ответ 4

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

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

Я обычно использую FSM для довольно простых задач и выбираю их интуитивно. В ответе на другой вопрос о регулярных выражениях, я просто рассмотрел проблему разбора как один из 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 для разделения функций.

Ответ 5

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

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

Ответ 6

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

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

alt text 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". Если вы сделаете эти условия для каждого состояния, вы почти закончили определение своего государственного аппарата. Все, что вам нужно сделать, это иметь переменную состояния, а затем способ ввода ввода, и это в основном то, что есть.

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

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