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

Question

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

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

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

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

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

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

622 5

python regex parsing

5 ответов:

Comments

Ничего не найдено.

Mark Byers · Accepted Answer · 2010-09-04 00:32:41

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

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

Регулярное Выражение Соответствия Может Быть Простым И Быстрым (но медленно в Java, Perl, PHP, Python, Ruby, ...)

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

Steve314 · Accepted Answer · 2016-08-04 23:00:09

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

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

то, что я буду (очень быстро) описать это подход принят в Современный Дизайн Компилятора.

представьте, что у вас есть следующее регулярное выражение...
a (b c)* d
буквы представляют собой буквенные символы, чтобы соответствовать. * - Это обычный матч с нулевым или большим количеством повторений. Основная идея заключается в выводе состояний на основе пунктирных правил. Нулевое состояние мы будем считать состоянием, в котором еще ничего не было сопоставлено, поэтому точка идет впереди...
0 : .a (b c)* d
единственным возможным совпадением является 'a', поэтому следующее состояние мы выводим это...
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, подход в современном дизайне компилятора заключается в переводе правила при нажатии оператора, чтобы упростить обработку точки. Состояние 1 будет преобразовано...
1 : a.b c (b c)* d
    a.d
что ваш следующий вариант - либо соответствовать первому повторению, либо пропустить повторение. Следующие состояния из этого эквивалентны состояниям 2 и 3. Преимуществом такого подхода является то, что вы можете отбросить все свои прошлые матчи (все до '.') как вы заботитесь только о будущих матчах. Это обычно дает меньшую модель состояния (но не обязательно минимальную).

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

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

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

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

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

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

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

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

кстати-посмотрите вокруг остальной части сайт Дик Грюнес - у него есть бесплатная PDF книга по методам разбора. Первое издание современного дизайна компилятора довольно хорошо IMO, но, как вы увидите, скоро появится второе издание.

dhaffey · Accepted Answer · 2010-09-04 00:39:56

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

Richard Fearn · Accepted Answer · 2010-09-04 00:24:48

есть интересная (если немного короткая) глава в Красивый Код Брайан Керниган, соответствующим образом называемый "регулярным выражением Matcher". В нем он обсуждает простой сопоставитель, который может соответствовать буквенным символам, и .^$* символы.

A_Var · Accepted Answer · 2010-09-23 10:03:45

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