Создание механизма регулярных выражений - онлайн-ресурсов?

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

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

Что меня интересует, так это то, как в программном обеспечении реализован механизм регулярных выражений. Поэтому мне было интересно, существует ли какой-либо учебник или онлайн-ресурс, объясняющий реализацию механизма регулярных выражений, перевод из регулярного выражения в FSM и т.д. Я не хочу, чтобы какие-либо сайты просто объясняли теорию, лежащую в ее основе.

Спасибо.

Ответ 1

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

Ответ 2

Я думаю, что статья Как работают регулярные выражения от Mark-Jason Dominus. Он ориентирован на не-программистов, но он написан очень алгоритмически, и поэтому его можно использовать для реализации такого движка, особенно если у вас есть опыт компиляции. Я сделал это сам.

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

Ответ 3

В первой главе "Красивый код" (Amazon, онлайн-проект) Брайан Керниган рассказывает о элегантном, очень маленьком регулярном выражении Роба Пайка. Это очень просто, но Керниган дает семь упражнений, чтобы расширить его, что может быть хорошим вступлением для вас.

Ответ 4

У меня есть две интересные ссылки для механизмов регулярных выражений,

Ответ 5

Если вам удобно с C, вам, вероятно, удастся найти исходный код для Perl-совместимые регулярные выражения.

Ответ 6

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

Зачем использовать постфиксную нотацию
Что представляет собой стек фрагментов NFA
Алгоритм postfix-to-NFA в псевдокоде
Структура данных NFA

Кроме того, я нашел статью профессора Pace, полезную при реализации метода re2post, упомянутого WSU и Cox.

Я бы рекомендовал сначала прочитать статью WSU, а затем статью Russ Cox для большей глубины.

Ответ 7

Пятая глава из Алгоритмы Роберта Седжуика - очень хорошее введение в эту тему. Он объясняет, что такое NFA, и как NFA можно создать из регулярного выражения. Примеры имеют визуальные эффекты и очень ясны. У него даже есть код для простого регулярного выражения. И есть несколько упражнений для реализации дополнительных функций регулярных выражений.

Ответ 8

другое простое и ясное воплощение (C, менее 500 строк) RecursiveRegexpRaptor

Ответ 9

Для немецких читателей третья глава "Pattern-Matching-Algorithmen für einfache Strings" из " Algorithmen auf Sequenzen" может быть интересной. Автор - профессор Свен Рахманн, Лерхштул XI, Fakultät für Informatik, TU Dortmund. Все алгоритмы имеют примеры Python.