Regularni izrazi....

sed -e s/FOO/BAR/g ime_datoteke

Ni pa izpolnjen pogoj: kontrola med XML

Ampak sed ni regexp...

Stvar v bistvu delam v phphju, torej mora biti resitev za ereg_replace() oziroma preg_replace().

IMO sam preg_replace ne bo dost, če želiš samo besedilo znotraj <xml></xml>...

<?php
// tvoji podatki
$xml = <<<XML
<XML>
Tralalala FOO hopsasa FOO tralala
FOO tralala tralala hopsasa
FOO
</XML>
XML;

function fooBar($matches)
{
    return $matches[1] . str_replace('FOO', 'BAR', $matches[2]) . $matches[3];
}

// klic funkcije, ki izlušči besedilo med <xml></xml> in kliče funkcijo zgoraj, ki opravi dejanski replace...
// če hočš podrobnosti - http://si.php.net/preg_replace_callback
echo preg_replace_callback('/(<xml>)(.*?)(<\/xml>)/si', 'fooBar', $xml);
?>

Zgornja koda se da sicer izvest v eni vrstici z funkcijo preg_replace in modifierjem "e", ampak takšna koda je nepregledna + ni varna:

<?php
echo preg_replace('/(<xml>)(.*?)(<\/xml>)/sie', "'$1' . str_replace('FOO', 'BAR', '$2') . '$3'", $xml);
?>

...torej mora biti resitev za ereg_replace()...

Jst bi se družini ereg funkcij izogibal, ker jih bodo baje v PHP6 odstranl, tako da znajo potem nastati kakšni poroblemi pri nadgradnji... sicer bo to šele čez par let, ampak že zdej je fajn razmišljat v tej smeri, da ne bo potem spet jamranja (kot se je to dogajalo in se še pri prehodu iz PHP4 v PHP5), kako da nič ne dela...

@kekz: [ st.koda][ /st.koda] (brez presledka za [ )

Fascinantne tele regexp. Sploh jih ne obvladam prida, ampak me totalno fascinirajo. Nekaj časa sem razmišljal, da bi naredil tak battle. Prideta regexp A in regexp B in ena drugo obdelata. Tista, od katere več ostane, zmaga.

Naprimer.

Al pa cel niz regexpov, kamor se hodijo drugi regexpi optimizirat. Taka mehanična delavnica za regexpe, ki jo vodijo regexpi in pri svojem delu uporabljajo regexpe.

Možnosti je veliko, zaradi avtorekurzivnosti regexpov.

Thomas: Izrazna moč regularnih izrazov je jako premajhna da bi pokril vse potrebe po navadni tekstovni manipulaciji, kamo li da bi z regexi optimiziral druge regexe. IMHO tukaj rabiš kar navaden "lep" Turingov stroj.

Precej ziher sem,d a to lahko dokaj lepo v gawku narediš.

Ne sicer z enim regexpom, ampak z ene par vrsticami.
Verjetno tudi v SEDu.

Pa v m4 bi šlo, pravzaprav verjetno najlažje in najhitreje.

Aja, za php regexp rabiš- se opravičujem za zajeb...

> To ni res. Samo komplicirano rata, drugače pa ni omejitev.
Chomsky hierarchy. Regularni izrazi so na dnu, potem so kontekstno neodvisne, potem pa odvisne gramatike (mocnejse od regularnih izrazov). Na vrhu pa se neomejene gramatike, ki so enako mocne kakor turingovi stroji.

a^n b^n z obicajnimi regularnimi izrazi ni mogoce predstaviti. Ali pa naprimer xml s poljubnim gnezdenjem.

Thomas: Spiši mi regularen izraz, ki najde string, ki ima notri toliko a-jev, kot ima b-jev.

Torej, stvar naj najde:

ab
aabb
aaabbb
aaaabbbb

itd.

Zaporedoma menjaš ab z ničemer. Če ti ostane prazen string, je ok.

Ja samo potem sprejemas tudi abababab ... kar pa ni enako kakor a^n b^n problemu ... Cim pa gledas, ce je pozicija na sredini, pa izgubis regularnost problema in s tem koncnost avtomata (ker pozicija lahko gre cez vse meje (pri poljubno dolgih neskoncnih vhodnih besedah)).
Next try . Za tiste na FRIju ... Pri TOR2 imate v knjigi bolj uraden dokaz ...

> Ja samo potem sprejemas tudi abababab

Ja in? Osnovna definicija problema je bila:

> Spiši mi regularen izraz, ki najde string, ki ima notri toliko a-jev, kot ima b-jev.

Zgornji string tudi ustreza
Načeloma bi moral ustrezati celo: baaababb, katerega pa Thomasova rešitev dejansko ne bi našla.

Hm, kanoničen primer bi bil tudi nizi oblike:

abc
aabbcc
aaabbbccc
...

razmišljam v stilu: ker so reg izrazi podmnožica kontekstno-neodvisnih gramatik in za take nize ne obstaja kontekstno-neodvisna gramatika, ki bi jih lahko opisala (za a^n b^n pa recimo obstaja, samo regex še vedno ni dovolj močen)?

Sergio ima izgleda prav - omenjeni regex ki bi prepoznal a^n b^n, bi prepoznal tudi druge, ki niso te oblike (kot je omenil mspiller) in torej ne bi deloval pravilno. To je isti problem kot pri programu, ki išče praštevila tako, da preveri če je število liho - sicer dela, ampak samo, če mu ne daješ lihih ne-praštevil ;)


Eh, zabluzili smo... mah, samo paše, kdaj pa kdaj ;)

Pozabi na neskončne besede! To bi bil že čisto drug problem.

Cakaj cakaj. Zgoraj govoris, da ni omejitev. Das link na Myhill-Nerode teorem, potem pa pravis, da naj pozabim na neskocne besede. Pri koncnih besedah je tvoj chalenge brezvezen. Ker se da pri koncni dolzini besede ali pa regularnega izraza s koncnim avtomatom prebrati vse. Magari z vnaprej zgeneriranimi tabelami. Drugace pa imas problem ze pri npr "((((regex))))", kjer se mora ujemati poljubno stevilo oklepajev. Spet variacija problema a^n b^n ...

Glede optimizacije regular expressionov. Glede na to, da je rezultat deterministicni koncni avtomat itak nima smisla. Edino minimizacija stevila stanj, za to pa ze obstaja algoritem.

Lahko mi pa napises regularni izraz, ki predstavlja ostale regularne izraze. Tukaj imas regex v BNF.

> Pri koncnih besedah je tvoj chalenge brezvezen. Ker se da pri koncni dolzini besede ali pa regularnega izraza s koncnim avtomatom prebrati vse

In kaj sem drugega trdil?

Neskončne besede me NE zanimajo. Niti malo. Boš oprostil!

Fora je edino to, da je na racunalniku kakorkoli ze string vedno koncen.
Ce ne drugega nimas neskoncno pomnilnika (oz. ok lahko se delas da del stringa
napises na en zunanji storage in ga ko je poln med delovanjem menjas),
ampak tako verjetno ne bi sel komplicirati. Pa se vedno si omejen z denarjem ;)

Zato regularni izraz ab|aabb|aaabbb .. cisto dobro deluje.
Seveda pa se da dokazati (kaj je tisto ze - lema o napihovanju) da v
primeru dolocenih neskoncnih jezikov regularni izraz ni dovolj "mocen" za njihovo predstavitev.

In z regularnim izrazom dejansko ti samo _opises_ kako nek string izgleda, nic ne menjas stvari!
Dolocena orodja znajo potem tisto kar ti opises z regularnim izrazom zamenjati z necim drugim,
ampak to ni vec stvar regexpa. Tako orodje je pomoje potem lahko tako mocno kot Turingov stroj (ce se potrudis).

V tem a^n b^n primeru se izkaze da je veliko bolj kompaktno ce stvar predstavis
v obliki kontekstno neodvisne gramatike kot pa da kompliciras z nastevanjem moznosti.
S -> aSb | eps

Neskončne besede me NE zanimajo. Niti malo. Boš oprostil!

Jasno.

Včasih bi blo boljš, če bi kakšen kej naredil, kot da dokazuje, kako ni mogoče.

Spet drugic bi bilo boljse namesto iti z glavo skozi zid, vzeti za osnovo kaj drugega. Npr. boljse je ze KNG (kontekstno neodvisna gramatika). Vec besed pokrije, kakor pri regularnih izrazih. Samo da se igras na stack masini, namesto na koncnem avtomatu. Posledicno lahko opises tudi programske jezike (ki jih z regularnimi izrazi seveda ne mores) in se igras z njimi (optimiziras, konvertiras, interpretiras, tvoj Critticall, ...).

sverde,

> Očitno si boš mogu aluminjasto foljo dat na glavo [>:D] .
> Drugač pa, zakaj ti pa taka rešitev ni všeč [:)] ?

Saj taka resitev mi je vsec. Sem jo na koncu tudi ponucal.

Problem, ki ga jaz do sedaj nikoli nisem mogel z regexpom resiti je tocno tak, kot sem ga opisal.

Kako matchas poljubno stevilo nizov med dvema nizoma, ki ju pa tudi matchas v istem regexpu.