Как движки регулярных выражений учитывают нарушения? - PullRequest
Новая
       2

Как движки регулярных выражений учитывают нарушения?

3 голосов
/ 21 ноября 2011

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

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

(.*)\1   // this is not regular

1 Ответ

2 голосов
/ 21 ноября 2011

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

Из того, что я могу сделать из исходного кода Python re, она сохраняет группубуфер (так или иначе, так как он должен возвращать это как часть объекта сопоставления) и выполняет прямое сопоставление строк в алгоритме сопоставления, потребляя столько символов, сколько имеется в буфере сопоставления групп.

[Необязательный трюк: к сожалению, движки RE на практике представляют собой наборы хаков поверх NFA, которые разрушают их математические свойства.Многие разработчики игнорируют изящную алгебру регулярных языков и их мощное расширение регулярных отношений, которые могут быть эффективно захвачены FSTs .]

...