Написание парсера для регулярных выражений

Question

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

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

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

Вопрос в том, с чего начать? Я почти ничего не знаю о том, как регулярные выражения анализируются и интерпретируются отдельно от того, что он каким-то образом связан с автоматом конечного состояния. Любые предложения о том, как подойти к этой довольно сложной проблеме, будут высоко оценены.

EDIT:. я должен уточнить, что в то время как я собираюсь реализовать регулярное выражение парсер в Python, я не слишком хлопотал о том, что язык программирования примеры или статьи написаны в тех пор, пока это не в Brainfuck, я, вероятно, пойму, что это будет стоить того времени.

Answer 1

Написание реализации механизма регулярных выражений действительно является довольно сложной задачей.

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

Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)

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

Answer 2

В статье Beautiful Code есть интересная (если немного короткая) статья Брайана Кернигана, соответственно называемая «Регулярным выражением». В нем он обсуждает простой совпадение, которое может соответствовать буквальным символам и символам .^$*.

Answer 3

This paper принимает интересный подход. Реализация дана в Haskell, но это было reimplemented in Python хотя бы один раз.

Answer 4

Я уже отдал +1 марку Байерсу, но, насколько я помню, на бумаге не так много говорится о том, как работает регулярное выражение, объясняя, почему один алгоритм плох, а другой намного лучше. Может быть, что-то в ссылках?

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

Что я буду очень быстро описывать, это подход, принятый в Modern Compiler Design.

Представьте, что вы есть следующее регулярное выражение ...

a (b c)* d 

Буквы представляют буквенных символов, чтобы соответствовать. * - обычное совпадение с нулем или большим числом повторений. Основная идея - вывести состояния, основанные на пунктирных правилах. Государственный ноль мы возьмем в качестве государства, в котором ничего не было подкреплено еще, так что точка уходит на фронт ...

0 : .a (b c)* d 

Единственный возможный матч «а», так что следующее состояние, которое мы получаем это. ..

1 : a.(b c)* d 

Теперь мы имеем две возможности - соответствовать «B» (если есть по крайней мере один повтор «B C») или совпадать с «D» в противном случае. Примечание. В основном мы делаем поиск по орграфу здесь (сначала по глубине или по ширине, или по другому), но мы обнаруживаем орграф, когда мы его ищем. Предполагая, что стратегия в ширину, нам нужно будет поставить очередь на один из наших случаев для последующего рассмотрения, но я проигнорирую этот вопрос здесь. Во всяком случае, мы обнаружили два новых состояния ...

2 : a (b.c)* d 
3 : a (b c)* d. 

Состояние 3 - конечное состояние (может быть более одного). Для состояния 2 мы можем сопоставлять только «c», но после этого мы должны быть осторожны с точкой. Мы получаем «a. (B c) * d» - то же, что и состояние 1, поэтому нам не нужно новое состояние.

IIRC, подход в Modern Compiler Design заключается в том, чтобы перевести правило, когда вы нажмете на оператора, чтобы упростить обработку точки. Государство 1 будет преобразовано в ...

1 : a.b c (b c)* d 
    a.d 

То есть, ваш следующий вариант либо в соответствии с первым повторением или пропустить повторение. Следующие состояния из этого эквивалентны состояниям 2 и 3. Преимущество такого подхода состоит в том, что вы можете отбросить все свои прошлые матчи (все до «.»), Поскольку вы заботитесь только о будущих матчах. Обычно это дает меньшую модель состояния (но не обязательно минимальную).

EDIT Если вы отбрасываете уже согласованные детали, ваше описание состояния представляет собой представление набора строк, которое может произойти с этой точки.

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

Минимальное значение здесь означает процесс замыкания - могут быть меньшие эквивалентные автоматы, которые обычно называются минимальными.

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

Если ваши обычные грамматики становятся сложными, вы можете свести к минимуму. Основная идея здесь относительно проста. Вы группируете все свои состояния в один класс эквивалентности или «блок». Затем вы неоднократно проверяете, нужно ли разделять блоки (состояния на самом деле не эквивалентны) по отношению к определенному типу перехода. Если все состояния в определенном блоке могут принимать совпадение одного и того же символа и при этом достигать одного и того же следующего блока, они эквивалентны.

Алгоритм Hopcrofts - эффективный способ справиться с этой основной идеей.

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

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

BTW - посмотрите на остальную часть Dick Grunes site - у него есть бесплатная книга PDF по методам разбора. Первое издание Modern Compiler Design довольно неплохое ИМО, но, как вы увидите, появляется второе издание.

Answer 5

Я согласен с тем, что создание регулярного выражения улучшит понимание, но вы взглянули на ANTLR ??. Он автоматически генерирует парсеры для любого языка. Так что, может быть, вы можете попробовать свои силы, взяв одну из языковых грамматик, перечисленных в Grammar examples, и пройдите через AST и парсер, который он создает. Он генерирует действительно сложный код, но у вас будет хорошее понимание того, как работает парсер.