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

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

17 голосов
/ 08 февраля 2009

В подкасте Stack Overflow # 36 (http://blog.stackoverflow.com/2009/01/podcast-36/),) было высказано такое мнение: Как только вы поймете, как легко настроить конечный автомат, вы никогда не будете пытаться использовать регулярное выражение неуместно когда-либо снова.

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

Ответы [ 6 ]

23 голосов
/ 08 февраля 2009

Конечно, хотя вам понадобятся более сложные примеры, чтобы по-настоящему понять, как работают 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.

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

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

21 голосов
/ 08 февраля 2009

Довольно удобный способ помочь в этом - использовать малоизвестный флаг python re.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, которым они должны соответствовать.

19 голосов
/ 08 февраля 2009

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

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

A finite state machine

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

4 голосов
/ 08 февраля 2009

Является ли вопрос «Как выбрать состояния и условия перехода?» Или «Как реализовать мой абстрактный конечный автомат в Foo?»

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

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

2 голосов
/ 08 февраля 2009

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

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

1 голос
/ 08 февраля 2009

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

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

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

...