Я уже дал +1 Марку Байерсу - но, насколько я помню, в статье мало что говорится о том, как работает сопоставление регулярных выражений, помимо объяснения, почему один алгоритм плох, а другой намного лучше.Может быть, что-то в ссылках?
Я сосредоточусь на хорошем подходе - создании конечных автоматов.Если вы ограничиваете себя детерминированными автоматами без минимизации, на самом деле это не так уж сложно.
То, что я (очень быстро) опишу, - это подход, принятый в Современный дизайн компилятора .
Представьте, что у вас есть следующее регулярное выражение ...
a (b c)* d
Буквы представляют буквенные символы для сопоставления.* - это обычное совпадение с нулем или более повторений.Основная идея заключается в получении состояний на основе пунктирных правил.Нулевое состояние мы возьмем в качестве состояния, в котором еще ничего не сопоставлено, поэтому точка идет впереди ...
0 : .a (b c)* d
Единственное возможное совпадение - это «a», поэтому следующее состояние, которое мы получимis ...
1 : a.(b c)* d
Теперь у нас есть две возможности - соответствовать 'b' (если есть хотя бы одно повторение 'b c') или совпадать с 'd' в противном случае.Обратите внимание - мы в основном выполняем здесь поиск орграфа (либо сначала по глубине, либо по ширине, либо как угодно), но мы обнаруживаем орграф по мере его поиска.Если исходить из стратегии в ширину, нам нужно будет поставить в очередь одно из наших дел для дальнейшего рассмотрения, но с этого момента я буду игнорировать эту проблему.В любом случае, мы обнаружили два новых состояния ...
2 : a (b.c)* d
3 : a (b c)* d.
Состояние 3 является конечным состоянием (их может быть несколько).Для состояния 2 мы можем только соответствовать 'c', но мы должны быть осторожны с позицией точки впоследствии.Мы получаем «a. (Bc) * d» - это то же самое, что и состояние 1, поэтому нам не нужно новое состояние.
IIRC, подход в Modern Compiler Design заключается в переводе правила, когдаВы нажимаете на оператора, чтобы упростить обработку точки.Состояние 1 будет преобразовано в ...
1 : a.b c (b c)* d
a.d
То есть, ваш следующий вариант - либо соответствовать первому повторению, либо пропустить повторение.Следующие состояния из этого эквивалентны состояниям 2 и 3. Преимущество этого подхода состоит в том, что вы можете отбросить все свои прошлые совпадения (все до «.»), Так как вы заботитесь только о будущих совпадениях.Обычно это дает меньшую модель состояния (но не обязательно минимальную).
EDIT Если вы отбрасываете уже сопоставленные детали, ваше описание состояния является представлением набора строк, которые могутпроисходят с этого момента.
С точки зрения абстрактной алгебры, это своего рода замыкание множества.Алгебра - это в основном множество с одним (или несколькими) операторами.Наш набор описаний состояний, а наши операторы - наши переходы (совпадения символов).Закрытый набор - это тот, где применение любого оператора к любому члену в наборе всегда приводит к другому члену, который находится в наборе.Закрытие множества - это минимально большее множество, которое закрыто.Таким образом, в основном, начиная с очевидного начального состояния, мы строим минимальный набор состояний, который является замкнутым относительно нашего набора операторов перехода - минимальный набор достижимых состояний.
Здесь минимальный относится к процессу закрытия -может быть меньший эквивалентный автомат, который обычно называют минимальным.
Имея в виду эту основную идею, не сложно сказать "если у меня есть два конечных автомата, представляющих два набора строк, какполучить третью, представляющую объединение "(или пересечение, или установить разность ...).Вместо пунктирных правил ваши представления состояний будут иметь текущее состояние (или набор текущих состояний) от каждого входного автомата и, возможно, дополнительные детали.
Если ваши обычные грамматики становятся сложными, вы можете минимизировать.Основная идея здесь относительно проста.Вы группируете все свои состояния в один класс эквивалентности или «блок».Затем вы неоднократно проверяете, нужно ли разбивать блоки (состояния на самом деле не эквивалентны) в отношении определенного типа перехода.Если все состояния в конкретном блоке могут принять совпадение одного и того же символа и при этом достичь одного и того же следующего блока, они эквивалентны.
Алгоритм Хопкрофта - эффективный способ справиться с этой основной идеей.
Особенно интересной особенностью минимизации является то, что каждый детерминированный конечный автомат имеет ровно одну минимальную форму.Кроме того, алгоритм Хопкрофта будет производить одно и то же представление этой минимальной формы, независимо от того, с какого представления начался более крупный случай.То есть это «каноническое» представление, которое можно использовать для получения хэша или для произвольных, но согласованных порядков.Это означает, что вы можете использовать минимальные автоматы в качестве ключей для контейнеров.
Выше, вероятно, немного небрежные определения WRT, поэтому убедитесь, что вы сами ищете какие-либо термины, прежде чем использовать их самостоятельно, но с небольшим количествомК счастью, это дает быстрое краткое введение в основные идеи.
Кстати - посмотрите на остальную часть сайта Дика Грунса - у него есть бесплатная книга в формате PDF по методам парсинга.Первое издание Modern Compiler Design довольно неплохое IMO, но, как вы увидите, есть второе издание.