Несколько регэксов одновременно
есть ли возможность определить, какой из шаблонов вызвал совпадение в выражении вида "re1|re2|...|reN"?
function vlad_preg_match($regexp) {
$arrPatterns = explode('|',$regexp);
for($i=0;isSet($arrPatterns[$i]);$i++) {
if(preg_match($arrPatterns[$i]$someinputstring return $i;
}
return false;?
> за один проход
ЭЭ, а если внутри reK будет символ | ?
import re
import string
from operator import truth
def vlad_preg_match (regexp, text):
patterns=string.split (regexp, '|')
for i in xrange (0,len (patterns):
if truth(re.match (patterns[i], text:
return i
return None
А если 2 шаблона приведут в одно и то же состояние? Afaik ты их не различишь. Имхо, если есть возможность различения - то реализация будет перебором.
Это проблема регекспа
ИМХО, если символ правильно заэскейпеный, то это уже проблема не регекспа, а того, кто процедуру писал.
import re
import string
from operator import truth
def vlad_preg_match (regexp, text):
patterns=string.split (regexp, '|')
return map (lambda x: truth (re.match (x, text patterns).index (True)
вот, извратный вариант. Если совпадений нет, кидает ексепшн
Суть регэксов в том, чтобы перебора избежать. И теоретически нет никаких проблем транслировать такую сумму языков в автомат с несколькими выходами. Если языки пересекаются - да, неочевидно как поступать (так же как и при делении на ноль). Но можно либо разрешить эту операцию только для непересекающихся языков, либо как в решении ДиззиДена возвращать множество подошедших шаблонов.
Лямбда уже не модно, все юзают list comprehension. И в данном случае тоже так будет лучше. А если по теме -
> за один проход
> за один проход
Как ты себе представляешь реализацию (regexp1 | regexp2)? Имхо на уровне автомата это будет реализовано так же как посчитать regexp1 и regexp2. Не думаю что проводится хоть какая-то оптимизация.
гвидина дурь. Лямбда - хорошая штука.
Вопрос к аффтару, я вообще хз, что он имел в виду.
Если он собирается их как-то экранировать - придётся чуть сложнее разрезать.
Если он собирается их как-то экранировать - придётся чуть сложнее разрезать.
ыыы...
В том то и дело, что проводится. Для простоты буду говорить о маленьких регулярных (в теоретико-языковом смысле слова) выражениях в маленьком алфавите. По регэксу вида r1|r2 строится недетерминированный конечный автомат, который состоит из двух автоматов, принимающих языки r1 и r2, перед которыми помещается недетерминированная развилка. Когда НКА построен, производится детерминизация. При этом строится эквивалентный детерминированный автомат, состояния которого отвечают множествам состояний исходного автомата. Когда такой автомат построен (т.е. регэкс скомпилирован можно его натравливать на произвольную строку, и он будет совершать фиксированный набор операций на символ этого слова (а именно - посмотреть куда ведёт переход из текущего состояния, помеченный очередным симовлом, и поменять текущее состояние).
В том то и дело, что проводится. Для простоты буду говорить о маленьких регулярных (в теоретико-языковом смысле слова) выражениях в маленьком алфавите. По регэксу вида r1|r2 строится недетерминированный конечный автомат, который состоит из двух автоматов, принимающих языки r1 и r2, перед которыми помещается недетерминированная развилка. Когда НКА построен, производится детерминизация. При этом строится эквивалентный детерминированный автомат, состояния которого отвечают множествам состояний исходного автомата. Когда такой автомат построен (т.е. регэкс скомпилирован можно его натравливать на произвольную строку, и он будет совершать фиксированный набор операций на символ этого слова (а именно - посмотреть куда ведёт переход из текущего состояния, помеченный очередным симовлом, и поменять текущее состояние).
Ну, можно ведь из регулярных выражений r1, r2, r3, …, rN построить регулярное выражение (?P<name1>r1)|(?P<name2>r2)|(?P<name3>r3)|…|(?P<nameN>rN поматчить строчку, а потом пробежаться по группам name1, name2, name3, …, nameN и найти непустую?
Нужно только, чтобы name1, name2, name3, …, nameN не совпадали с именами групп, используемых внутри r1, r2, r3, …, rN.
Или я не понял, чо надо сделать?
Нужно только, чтобы name1, name2, name3, …, nameN не совпадали с именами групп, используемых внутри r1, r2, r3, …, rN.
Или я не понял, чо надо сделать?
можно. Тока я когда делал такой регексп из 8000 альтернатив, делал компилированную версию в Java 6, а потом применял к куче строчек, на каждой строке тормозило, как будто комп ща родит
А че, по очереди быстрее будет?
Выйди в IM!
Выйди в IM!
Да можно так. Правда не знаю, будет ли выигрыш в скорости. Надо сравнивать. По всей видимости все зависитот от "однородности" регэкспов.
У меня была не куча регекспов, а куча подстрок, поэтому меня выручил Ахо-Корасик
Полагаю, нечто подобное делают генераторы лексических анализаторов, которые по описаниям нескольких токенов строят автомат, извлекающий эти токены из входного потока в произвольном порядке.Да, штуки типа flex именно это и должны делать. А про поддержку подобного поведения в библиотеках регулярных выражений, к сожалению, не в курсе.
Не знаю что такое Ахо-Корасик. Если он основан на объединении слов в дерево, чтобы общие начала этих строк отвечали фрагменту пути в этом дереве, и простановке в листьях указателей к какой вершине переходить в случае облома - то регэкс уже делает это нахаляву. Обидно, если этим нельзя воспользоваться.
Сделать нужно именно это. Только хотелось бы
1) чтобы время работы зависело только от длины анализируемой строки, как в случае обычных регэксов (а у тебя регэкс отработает (возможно) за приемлемое время, но потом придётся долго искать подходящую группу);
2) использовать для этого уже написанный, отлаженный, оптимизированный и понятный каждому механизм регэксов, а не изобретать деревья подстрок или ленивую детерминизацию.
1) чтобы время работы зависело только от длины анализируемой строки, как в случае обычных регэксов (а у тебя регэкс отработает (возможно) за приемлемое время, но потом придётся долго искать подходящую группу);
2) использовать для этого уже написанный, отлаженный, оптимизированный и понятный каждому механизм регэксов, а не изобретать деревья подстрок или ленивую детерминизацию.
Я слышал, что в перле "регулярные выражения" аццки мощные. Может быть, в них даже можно запихнуть инструкции... Тогда покатит выражение типа "(re1 $found=1) | ... | (reN $found=N)".
Правда, такая возможность представляет для меня лишь теоретический интерес, т.к. использовать я в любом случае буду питон.
Правда, такая возможность представляет для меня лишь теоретический интерес, т.к. использовать я в любом случае буду питон.
Оставить комментарий
Dmitriy82
Автоматы, в которые транслируются выражения, имеют большие возможности, чем одиночный регэкс. У них может быть более одного финального состояния, что позволит распознавать один из нескольких шаблонов, и сообщать какой подошёл (за один проход). Поддерживается ли такая возможность в распространённых библиотеках регулярных выражений? В особенности интересуют питоновские средства.Можно ещё так вопрос переформулировать: есть ли возможность определить, какой из шаблонов вызвал совпадение в выражении вида "re1|re2|...|reN"?
Полагаю, нечто подобное делают генераторы лексических анализаторов, которые по описаниям нескольких токенов строят автомат, извлекающий эти токены из входного потока в произвольном порядке.