Как обрабатываются регулярные выражения?

Question

Как обрабатываются регулярные выражения?

Answer 1

Регулярное выражение описывает набор правил для конечного автомата . Обычно он перемещается по строке по одному символу за раз, принимая решения на основе того, что произошло с предыдущими символами и что описано в регулярном выражении.

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

Answer 2

Регулярные выражения можно смоделировать как Детерминированный конечный автомат . Вероятно, это было бы хорошим началом, если бы вы хотели «обработать» его.

Answer 3

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

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

1. Недетерминированный конечный автомат
2. Детерминированный конечный автомат

Эта статья MSDN объясняет несколько методов, реализованных в различных движках, а затем объясняет реализацию .NET и почему Microsoft выбрала то, что они выбрали для .NET.

Они еще более углублены в различные статьи, которые вы видите в списке здесь .

Answer 4

Этот вопрос очень широкий. Это не полный ответ, но Джефф Мозер написал в своем блоге отличную статью, в которой описан процесс регулярных выражений .NET: Как на самом деле работают регулярные выражения .NET

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

Answer 5

http://www.moserware.com/2009/03/how-net-regular-expressions-really-work.html

Answer 6

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