Czy można wyrównać dopasowanie przecięcia dwóch wyrażeń regularnych?

Question

Biorąc pod uwagę kilka wyrażeń regularnych, czy możemy napisać wyrażenie regularne, które jest równe ich przecięciu?

Na przykład, biorąc pod uwagę dwa wyrażenia regularne c[a-z][a-z] i [a-z][aeiou]t ich przecięcia zawiera cat i cut i ewentualnie więcej. Jak możemy napisać wyrażenie regularne dla ich przecięcia?

Dzięki.

Answer 1

Po pierwsze, uzgodnijmy warunki. Moja składniowej założenie będzie, że

skrzyżowaniu kilku regexes jest regex, który pasuje ciągi że każdy z regexes składowych również dopasować.

Walne Wariant

Aby sprawdzić przecięcia dwóch wzorów, ogólna metoda (pseudo-kod):

if match(regex1) && match(regex2) { champagne for everyone! } 

Opcja Regex

W niektórych przypadkach możesz zrobić to samo z uprzedzeniami, ale w przypadku złożonego wyrażeń regularnych nie ma takiej korzyści, niezależnie od tego, Sprawia, że ​​twoje regex jest bardziej niezrozumiałe dla twoich wrogów. Dlaczego małe korzyści? Ponieważ silnik i tak będzie musiał wielokrotnie analizować cały ciąg znaków.

logiczna AND

Ogólny wzór dla i sprawdzając, czy ciąg dokładnie spełnia regex1 i regex2 byłoby:

^(?=regex1$)(?=regex2$) 

$ w każdym uprzedzona gwarantuje, że każdy łańcuch pasuje do wzorca i nic więcej.

Matching kiedy i

Oczywiście, jeśli nie chcą po prostu sprawdzić wartość logiczną AND ale również zrobić rzeczywiste dopasowanie, po lookaheads, można dodać dot-gwiazda konsumować ciągu:

^(?=regex1$)(?=regex2$).* 

Albo ... Po sprawdzeniu pierwszego warunku, po prostu pasuje do drugiego:

^(?=regex1$)regex2$ 

jest to technika używana na przykład w sprawdzaniu poprawności haseł. Aby uzyskać więcej informacji na ten temat, zobacz Mastering Lookahead and Lookbehind.

sekcja Bonus: Związek regexes

Zamiast pracować na skrzyżowaniu, powiedzmy jesteś zainteresowany w związku z następujących regexes, tj, Wyrażenie regularne, która odpowiada jednej z tych regexes:

1. połowach
2. CAT1
3. cat2
4. cat3
5. kategorii 5

Osiąga się to za pomocą operatora naprzemiennie |:

catch|cat1|cat2|cat3|cat5 

Ponadto taki regex często mogą być skompresowane, jak w:

cat(?:ch|[1-35]) 

Answer 2

logiczne i w regex jest reprezentowany przez

(?=...)(?=...) 

So,

(?=[a-z][aeiou]t)(?=c[a-z][a-z]) 

Answer 3

Przykłady z wczytaniami są łatwe w użyciu, ale technicznie nie są już zwykłymi językami. Jednak możliwe jest skrzyżowanie dwóch języków regularnych, a to uzupełnienie jest regularne.

Pierwsza uwaga, że ​​Wyrażenia regularne można konwertować do iz NFA; obaj są sposobami wyrażania zwykłych języków.

Po drugie, zgodnie z prawem DeMorgan, w

Zatem są to kroki, aby obliczyć przecięcie dwóch RegExs:

• Konwersja zarówno RegExs do NFAs.
• Obliczyć dopełnienie obu NFA.
• Oblicz połączenie dwóch uzupełnień.
• Obliczyć dopełnienie tego związku.
• Konwertuj wynikowy NFA na RegEx.

Niektóre źródła:

• Unia i regex NFA: http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_06.pdf
• NFA do RegEx: http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf
• dopełnieniem NFA: https://cs.stackexchange.com/questions/13282/complement-of-non-deterministic-finite-automata

Answer 4

i wykonywania mamy coś takiego w RegEx

(REGEX) (REGEX)

Biorąc przykład

'Cat'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/) 
["Cat", "C", "a", "t"] 
'Ca'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/) 
//null 
'Cat123'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/) 
//null 

gdzie

([A-Za-z]+) //Match All characters 

i

([aeiouAEIOU]+) //Match all vowels 

połączenia ich obu pasuje

([A-Za-Z] +) ([aeiouAEIOU] +) ([A-Za-Z] +)

np

'Hmmmmmm'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/) 
//null 
'Stckvrflw'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/) 
null 
'StackOverflow'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/) 
["StackOverflow", "StackOverfl", "o", "w"] 

Answer 5

W ujęciu matematycznym przecięcie dwóch języków regularnych jest regularne, więc musi istnieć wyrażenie regularne, które je akceptuje.

Budowanie tego za pośrednictwem odpowiednich NFA jest prawdopodobnie najłatwiejsze. Rozważ dwa NFA, które odpowiadają dwóm wyrażeń regularnych. Nowe stany Q to pary (Q1, Q2) z dwóch NFAs. Jeśli występuje przejście (P1, x, Q1) w pierwszym NFA i (P2, x, Q2) w drugim NFA, wtedy i tylko wtedy następuje przejście ((P1, P2), x, (Q1, Q2)) w nowej NFA. Nowy stan (Q1, Q2) jest początkowy/końcowy, zarówno Q1, jak i Q2 są początkowe/końcowe.

Jeśli używasz NFAs z & epsilon; -moves, to także dla każdego przejścia (P1, & epsilon;, Q1) będzie przejście ((P1, P2), & epsilon;, (Q1, P2)) dla wszystkich stwierdza P2. Podobnie dla & epsilon; -moves w drugim NFA.

Teraz przekonwertuj nowy NFA na wyrażenie regularne z dowolnym znanym algorytmem i to wszystko.

Jeśli chodzi o PCRE, nie są one, ściśle mówiąc, wyrażeniami regularnymi. Nie ma sposobu, aby to zrobić w ogólnym przypadku. Czasami możesz użyć wyprzedzających, takich jak ^(?=regex1$)(?=regex2$), ale jest to dobre tylko dla dopasowania całego ciągu i nie jest dobre dla wyszukiwania lub osadzania w innych wyrażeniach regularnych. Bez zakotwiczenia dwie głowice mogą kończyć się pasującymi ciągami o różnej długości. To nie jest skrzyżowanie.