Цитата:
Сообщение от ProxyGreen
Ни как не называется, иногда, в некоторых случаях... Вода и общие фразы одни, в каких случаях какой механизм, где используется и как называется?
|
Зависит. В MySQL regex - ДКА. Во flash - перебор с возвратом (backtraking). В Java - тоже перебор с возвратом. Какие еще эвристики добавляют в код - можно посмотреть в коде соответствующих пользователей. Я вот посмотрел в код tamarin'а - там используется pcre. Краткий поиск по pcre дает следующее:
ссылка1. Здесь автор пришет "We originally planned to use PCRE for the regular expression search, until we realized that it used a backtracking algorithm, meaning it is easy to make searches take exponential time or arbitrary stack depth". И я с ним согласен - ваши эксперименты по быстродействию регулярных выражений подтверждают именно его точку зрения, а не использование нка. В
wiki пишут, например, что в PCRE есть жесткое ограничение на глубину рекурсии. Откуда в НКА может взяться рекурсия - совсем не понятно.
Да, если очень покопаться, там скорее всего можно будет накопать "автомат" (не нка или дка!). Но "автомат" можно при желании много где накопать - достаточно наличия чуть ли не любого состояния.
Цитата:
|
Ну извините пока продолжаю гуглить по вопросу:
|
Не надо гуглить! Нужно вырабатывать понимание вопроса. Вы так и не ответили на вопрос о том, что понимаете под нка/дка. Извините, но у меня складывается впечатление, что вместо попыток понять проблему вы только ищете ссылки, которые якобы доказывают вашу правоту.
Чтобы вы понимали разницу, давайте введем развеем путаницу, существующую во многих книгах и описаниях. Есть "классические" регулярные выражения из Computer Science. Это то, что у вас по первой ссылке ("Реализакция механизма обработки регулярных выражений на языке C++"). Фактически это литералы, closure (звездочка), конкатенация и выбор (|). Для них работает вся теория автоматов. Эти регулярные языки описывают регулярные (автоматные) грамматики. Назовем такие и только такие регулярные выражения cs-regex. В большинстве библиотек в регулярные выражения добавляют дополнительные возможности - группы захвата (capturing groups), обратные ссылки (back references), различные типы матчинга (greedy/reluctang/posessive - в AS их нет, но есть, например, в java). Назовем все такое семейство p-regex. Будем рассматривать пока только те, в которых есть backreference. Так вот, как я показывал, backreferences не могут распознаваться дка (и нка тоже). На практике для работы с p-regex в библиотеках используются не нка и дка автоматы (которые просто не могут работать), а перебор (backtracking). Большинство авторов рассматривают теоретическую часть, а затем говорят, что "практические библиотеки" тоже используют автоматы. Ведь и то, и другое - "регулярные выражения". Ну бывает, есть такая ошибка в рассуждениях.
Посмотрел по-диагонали. Хорошая статья. Претензий к автору нет. Его регулярные выражения являются cs-regex (обратите внимание на список используемых возможностей). Для них прекрасно работают автоматы, что автор и демонстрирует. Но не демонстрирует, как работают p-regex (и даже задачу такую не ставит!). И в заблуждение по поводу реализации других библиотек не вводит (о других библиотека автор просто не упоминает)!
Ну да. Автор не различает cs-regex и p-regex. Большая часть статьи - про p-regex. Настоящие p-regex разбираются перебором. И их автомат (state machine, где состояние - "позиция разбора") очень далек от нка.
Ага, видел. Автор отсылает в математическую литературу и при этом не упоминает о том, что в литературе речь идет о cs-regex, а он рассказывает про p-regex. Названия-то у них одинаковые.
Ага. Только вот автор не конретизирует, какие именно выражения транслируются в конечные автоматы
. А детали важны - cs-regex транслируются, а вот p-regex - нет.
Ага. Вы на
документацию посмотрите. Это же классический cs-regex! Там даже операции только классические - проверить строку на совпадение (без поиска подстроки). И результат - "matched/not matched". Никих backreferences.
Цитата:
|
Наверное хватит пока, потом ещё поглубже попробую порыть.
|
Если интересно - попробуйте найти, как реализуются backreferences на нка или дка. Я с удовольствием почитаю. Что-то мне кажется, там будет не совсем нка/дка (а, скорее, совсем не нка, хотя и автомат). Только вот сложно вам будет - большинство авторов это скользкий вопрос очень аккуратно обходят и не упоминают
.
Цитата:
|
Ну и ладно, я с этим и не спорил особенно. Только при чём тут это?
|
Да ладно. С этого то и началось наше обсуждение. Это ведь вы в теперь уже первом (после выделения) сообщении утверждали, что "дка всегда, независимо от написания выражения работает очень быстро, но уступает нка в возможностях." Они же преобразуются друг в друга, как они могут иметь разные возможности?
Добавлено через 5 минут
Цитата:
Сообщение от alatar
|
Так у нас спор скорее теоретический, а не практический. По ссылке посмотрел - в AS3 используется pcre. И вроде бы предоставляется только часть их возможностей.
Pcre - это backtracking. Автоматы - это, например
Re2.