część wspólna regexp-ów Opcje

[zimi]

no dobra... co wrażliwszych chyba powinienem prosić o to żeby usiedli przed przeczytaniem treści problemu

tak więc chciałbym aby mając 2 regexp-y w jakiś sensowny sposób podać przykładowy ciąg znaków który pasuję jednocześnie do obu lub generuje wyrażenie regularne które jest wynikiem "przecięcia" tych dwóch wyrażeń regularnych

wszystkie wzorce będą postaci: @^wzorzec$@ czyli wyrażenie regularne będzie obejmowało dany ciąg znaków zawsze od początku do końca...

może przykład
załóżmy że mamy wyrażenia: @^a{3,5}$@ i @^a{4,6}$@ nasza funkcja lub coś powinna zwracać 'aaaa', 'aaaaa' lub @^a{4,5}$@

oczywiście to tylko prosty przykład chciałbym aby to działało dla bardziej skomplikowanych wyrażeń regularnych

czy ktoś zna już jakiś skrypt, program cokolwiek... działające w ten sposób, tudzież ma pomysł jak się za to zabrać

[Kicok]

No jasne że się da:

[PHP] pobierz, plaintext 
<?php
 
	$text[0] = 'a';
	$text[1] = 'aaa';
	$text[2] = 'aaaa';
	$text[3] = 'aaaaa';
	$text[4] = 'aaaaaa';
	$text[5] = 'aaaaaaaa';
 
	$reg1 = '^a{3,5}$';
	$reg2 = '^a{4,6}$';
 
 
	for( $i = 0; $i < 6; ++$i )
	{
		preg_match( '@(?(?=' . $reg1 . ')(?:' . $reg2 . ')|)@', $text[$i], $matches );
		echo '<pre>' . print_r( $matches, true ) . '</pre>';
	}
 
?>
[PHP] pobierz, plaintext 

Wyrażenie zawsze coś dopasuje (choćby i pusty ciąg), więc musisz sobie jeszcze sprawdzać, czy tablica $matches jest pusta.

[zimi]

aha czyli Twoim zdaniem brute-force jest sensownym rozwiązaniem... że też na to nie wpadłem... od dawna mam za dużo wolnego czasu...

[Kicok]

Widzę że nie rozumiesz tego kodu. Ba, nawet sobie trudu nie zadałeś, żeby sprawdzić jak działa. Jeden rzut okiem i "wiem najlepiej".


No to może inny przykład. Wszystko zostało zmienione oprócz wyrażenia regularnego w taki sposób, żeby nie przypominało już brute force-a:

[PHP] pobierz, plaintext 
<?php
 
	$reg1 = '^a{3,5}$';
	$reg2 = '^a{4,6}$';
 
 
	// Test pierwszy
	echo '1. "a" nie pasuje do żadnego wzorca.<br>Test wyrażenia: ';
	preg_match( '@(?(?=' . $reg1 . ')(?:' . $reg2 . ')|)@', 'a', $matches );
	if( empty( $matches[0] ) )
	{
		echo 'nie dopasowano';
	}
	else
	{
		echo 'dopasowano "' . $matches[0] . '"';
	}
	echo '<br><br>';
 
 
	// Test drugi
	echo '2. "sdgsdgsdgsdgsdf" nie pasuje do żadnego wzorca.<br>Test wyrażenia: ';
	preg_match( '@(?(?=' . $reg1 . ')(?:' . $reg2 . ')|)@', 'sdgsdgsdgsdgsdf', $matches );
	if( empty( $matches[0] ) )
	{
		echo 'nie dopasowano';
	}
	else
	{
		echo 'dopasowano "' . $matches[0] . '"';
	}
	echo '<br><br>';
 
 
	// Test trzeci
	echo '3. "aaa" pasuje do pierwszego wzorca, ale nie pasuje do drugiego.<br>Test wyrażenia: ';
	preg_match( '@(?(?=' . $reg1 . ')(?:' . $reg2 . ')|)@', 'aaa', $matches );
	if( empty( $matches[0] ) )
	{
		echo 'nie dopasowano';
	}
	else
	{
		echo 'dopasowano "' . $matches[0] . '"';
	}
	echo '<br><br>';
 
 
	// Test czwarty
	echo '4. "aaaaaa" pasuje do drugiego wzorca wzorca, ale nie pasuje do pierwszego.<br>Test wyrażenia: ';
	preg_match( '@(?(?=' . $reg1 . ')(?:' . $reg2 . ')|)@', 'aaaaaa', $matches );
	if( empty( $matches[0] ) )
	{
		echo 'nie dopasowano';
	}
	else
	{
		echo 'dopasowano "' . $matches[0] . '"';
	}
	echo '<br><br>';
 
 
	// Test piąty
	echo '5. "aaaa" pasuje do obu wzorców.<br>Test wyrażenia: ';
	preg_match( '@(?(?=' . $reg1 . ')(?:' . $reg2 . ')|)@', 'aaaa', $matches );
	if( empty( $matches[0] ) )
	{
		echo 'nie dopasowano';
	}
	else
	{
		echo 'dopasowano "' . $matches[0] . '"';
	}
	echo '<br><br>';
 
 
	// Test szósty
	echo '6. "aaaaa" pasuje do obu wzorców.<br>Test wyrażenia: ';
	preg_match( '@(?(?=' . $reg1 . ')(?:' . $reg2 . ')|)@', 'aaaaa', $matches );
	if( empty( $matches[0] ) )
	{
		echo 'nie dopasowano';
	}
	else
	{
		echo 'dopasowano "' . $matches[0] . '"';
	}
	echo '<br><br>';
 
 
	// Test siódmy
	echo '7. "aaaaaaaaaaaaaaaaaaaaa" nie pasuje do żadnego wzorca.<br>Test wyrażenia: ';
	preg_match( '@(?(?=' . $reg1 . ')(?:' . $reg2 . ')|)@', 'aaaaaaaaaaaaaaaaaaaaa', $matches );
	if( empty( $matches[0] ) )
	{
		echo 'nie dopasowano';
	}
	else
	{
		echo 'dopasowano "' . $matches[0] . '"';
	}
	echo '<br><br>';
 
 
?>
[PHP] pobierz, plaintext 

[EDIT]
PS.

wszystkie wzorce będą postaci: @^wzorzec$@ czyli wyrażenie regularne będzie obejmowało dany ciąg znaków zawsze od początku do końca...

Nie wiem dlaczego wcześniej tego nie zauważyłem. W takim razie wystarczy zwykłe:

[PHP] pobierz, plaintext 
<?php
 
	if( preg_match( 'WZORZEC1', $zmienna ) && preg_match( 'WZORZEC2', $zmienna ) )
	{
		echo 'pasuje do obu';
	}
 
?>
[PHP] pobierz, plaintext 

Ten post edytował Kicok 25.07.2008, 16:55:54

[zimi]

rozumiem Twoje kody i wiem jak działają, założenia mojego problemu spełniają tylko przy brute-force...
dziękuję za nakład kodów jednak są dla mnie raczej bezużyteczne
może inaczej: nie chce sprawdzić czy jakiś ciąg znaków spełnia oba wyrażenia regularne, chce wygenerować ciąg znaków który spełnia oba wyrażenia regularne na podstawie tych wyrażeń regularnych, ew. generuje wyrażenie regularne które jest ich przecięciem

może powiem co chce osiągnąć... załóżmy że mam zbiór wyrażeń regularnych i chciałbym aby jeśli jedno wyrażenie regularne dopasuję jakiś ciąg to drugie już go nie może dopasować, jednak te ciągi znaków nie są z góry określone, więc mając jakiś zbiór wyrażeń regularnych puszczę ten algorytm na nich aby się dowiedzieć że jakieś 2 wyrażenia mają część wspólną i żeby poprawić jedno z nich tak aby już na siebie nie zachodziły

czyli załóżmy mamy to wspomniane @^a{3,5}$@, @^a{4,6}$@ i nie chcemy sprawdzić czy z góry określone ciągi pasują do obu wyrażeń naraz, ale chcemy np. wygenerować wyrażenie regularne które jest zgodne z jednym i drugim wyrażeniem czyli nasze @^a{4,5}$@

nie wiem jak jeszcze mogę to wytłumaczyć...

załóżmy mamy liczby od 1 do 100, są to jakieś elementy tak jak Twoje ciągi znaków które wykorzystałeś: 'a', 'aaa', 'aaaaa', etc.
zbiór A reprezentuje liczby podzielne przez 5: 5, 10, 15, etc
zbiór B reprezentuje liczby podzielne przez 3: 3, 6, 9, etc.

nasze zbiory A i B to odpowiednik wyrażeń regularnych

na podstawie tych zbiorów, a właściwie założeń jakie spełniają elementy tych zbiorów tworzymy założenia zbioru C który będzie przecięciem zbioru A i B, jako uproszczenie możemy generować jakiś element ze zbioru C jednak nadal na podstawie założeń zbiorów A i B

a co Ty robisz w swoim kodzie... trzymając się tego przykładu:
bierzesz jakieś elementy które należą do całego uniwersum i mówisz tak ten pasuję do zbioru A, ale nie do zbioru B, ten pasuję do B ale nie do A, ten nie pasuję do żadnego, a ten do obu

bierzesz: "1: nie pasuję, 2: nie pasuję, 3 pasuję do B, 5 pasuję do A, 15 pasuję do A i B"
a ja chce...: "skoro element ma być podzielny przez 3 i ma być podzielny przez 5 to musi podzielny przez 15" w ten sposób tworzę założenia zbioru C, a więc wyrażenie regularne, które rozumiem jako przecięcie wyrażeń A i B

PS. pewnie wiele razy się powtórzyłem... chciałem to przedstawić na kilka sposobów aby można było zrozumieć moją ideę...

[Kicok]

Wygląda na to, ze nie zrozumiałem twojego pierwszego postu. Ba - nie rozumiem też ostatniego

nie chce sprawdzić czy jakiś ciąg znaków spełnia oba wyrażenia regularne, chce wygenerować ciąg znaków który spełnia oba wyrażenia regularne na podstawie tych wyrażeń regularnych

Heh, nie zdajesz sobie sprawy z tego jakie to skomplikowane. Już nawet wygenerowanie najprostszego pasującego ciągu na podstawie wyrażenia regularnego ciężko byłoby napisać.

może powiem co chce osiągnąć... załóżmy że mam zbiór wyrażeń regularnych i chciałbym aby jeśli jedno wyrażenie regularne dopasuję jakiś ciąg to drugie już go nie może dopasować

To znaczy masz jakiś przykładowy tekst i traktujesz go sekwencyjnie tymi wyrażeniami? I chcesz, żeby tekst dopasowany do jakiegoś wyrażenia stawał się niewidoczny dla następnych wyrażeń? No to może wycinaj wszystkie dopasowania z tekstu bazowego zanim zajmie się nim kolejne wyrażenie? To akurat nie byłoby tak ciężko zrobić, ale nie wiem czy będzie pasowało do twojego zamysłu.

czyli załóżmy mamy to wspomniane @^a{3,5}$@, @^a{4,6}$@ i nie chcemy sprawdzić czy z góry określone ciągi pasują do obu wyrażeń naraz, ale chcemy np. wygenerować wyrażenie regularne które jest zgodne z jednym i drugim wyrażeniem czyli nasze @^a{4,5}$@

To już masz podane na tacy od samego początku, wystarczyło tylko wyłuskać z mojego kodu:

[PHP] pobierz, plaintext 
<?php
 
	function combine( $regexp1, $regexp2 )
	{
		return '@(?(?=' . $regexp1 . ')(?:' . $regexp2 . ')|(?!.*))@';
	}
 
	echo combine( '^a{3,5}$', '^a{4,6}$' );
 
?>
[PHP] pobierz, plaintext 

Wiem, że "^a{4,5}$" wygląda o wiele ładniej niż: "@(?(?=^a{3,5}$)(?:^a{4,6}$)|(?!.*))@", ale oba wyrażenia dopasują dokładnie to samo. Są sobie równoważne. Problem może wystąpić wtedy, gdy nie ma się dostępu do pełnego zestawu funkcji wyrażeń perlowych (takich jak dopasowanie warunkowe i przewidywanie). Kolejny problem to:

więc mając jakiś zbiór wyrażeń regularnych puszczę ten algorytm na nich aby się dowiedzieć że jakieś 2 wyrażenia mają część wspólną i żeby poprawić jedno z nich tak aby już na siebie nie zachodziły

Wychodzi na to, że ty jeszcze nie wiesz które wyrażenia będziesz musiał ze sobą łączyć. Dopiero algorytm musi znaleźć takie pary wyrażeń, które na siebie zachodzą, a to też pewnie będzie nieźle skomplikowane.

[zimi]

Heh, nie zdajesz sobie sprawy z tego jakie to skomplikowane. Już nawet wygenerowanie najprostszego pasującego ciągu na podstawie wyrażenia regularnego ciężko byłoby napisać.

Bo ja wiem czy tak ciężko to napisać, trywialne to nie jest... ale nie trudniejsze niż samo dopasowywanie wyrażeń regularnych do wzorca

zresztą, nie po to napisałem:

no dobra... co wrażliwszych chyba powinienem prosić o to żeby usiedli przed przeczytaniem treści problemu

żeby to miało być proste

To znaczy masz jakiś przykładowy tekst i traktujesz go sekwencyjnie tymi wyrażeniami?

Nie, nie, bardziej trzeba patrzeć na mój problem jako na zbiór if-else'ów
regexpy będą pisane "niezależnie" od siebie i będzie ich "kilka"... załóżmy 150...
chodzi o to że tworząc nowy wzorzec nie musisz pamiętać o poprzednich
a zachodzenie na siebie tych wyrażeń regularnych należałoby traktować jako błąd
w sumie rozwiązanie nie jest mi potrzebne koniecznie w PHP
zaczynam się zastanawiać czy przyda mi się na tyle żeby zrekompensować mi nakład pracy

Wiem, że "^a{4,5}$" wygląda o wiele ładniej niż: "@(?(?=^a{3,5}$)(?:^a{4,6}$)|(?!.*))@", ale oba wyrażenia dopasują dokładnie to samo.

Tak masz rację... nie pomyślałem o tym w ten sposób, kod zrozumiałem ale nie zrozumiałem przesłania jaki ten kod miał nieść, myślałem o nim w trochę inny sposób...

zależało mi raczej na tej wersji uproszczonej... bo gdy wzorce razem nie dopasują niczego to dla Twojej propozycji dostanę jakiś długi ciąg znaków który "nic nie mówi", a w wersji uproszczonej będzie jakiś sprzeczny prosty regexp, wyrażenia regularne będące przecięciami miałyby bowiem służyć do "debugowania" i mają być tworzone aby człowiek mógł je zanalizować i poprawić nachodzące wyrażenia...

zdaję się że teraz problem jest jasny

zgłębiłem trochę temat:
Na podstawie wyrażenia regularnego tworzone są: automaty skończone (FST), które dzielą się na deterministyczne (DFA) i niedeterministyczne (NFA), w przypadku wyrażeń Perl'a zdaje się że generowane są te drugie, jednak można je konwertować między sobą, wg angielskiej wiki DFA można ze sobą przecinać (skoro można konwertować DFA <-> NFA, to rozumiem że konwertować w prosty sposób)..., również na podstawie FST można odtworzyć wyrażenie regularne odpowiadające temu FST

Najkrócej rzecz ujmując na pewno w źródłach PHP są kody które by wystarczyły do rozwiązania problemu....

Znalazłem kod w Python'ie, który teoretycznie powinien robić takie rzeczy: http://www.ics.uci.edu/~eppstein/PADS/Automata.py , próbowałem go przetestować jednak nie działał zgodnie z moimi oczekiwaniami

ściągnąłem więc źródła Perl'a i znalazłem programy w C które mają odpowiadać za kompilację wyrażeń regularnych..., jednak jest to przegląd dzieła 5000 linii na plik (pliki są dwa albo więcej...) kodu poprawianego przez x programistów na przestrzeni ponad 10 lat, z zastrzeżeniem że kod został przepisany tak aby był bardziej wydajny kosztem jego czytelności...
więc przynajmniej chwilowo skapitulowałem...

jeżeli ktoś zna jakieś źródła, które mogłyby mi pomóc byłbym wdzięczny

Ten post edytował zimi 28.07.2008, 23:39:27