[PHP: preg_replace] nesting probleem oid *OUDE TOPIC*

[Tuinhark]

Hoi allen.

Ik had eerst een zootje regexps die na elkaar werden uitgevoerd: (jah, dit gaat wederom over de overbekende UBB tags )

code:

$tags = array("b", "u", "i", "tt");
for ($i = 0; $i < sizeof($tags); $i++)
{
  $t = $tags[$i];
  $open1 = quotemeta("[$t]"); $close1 = quotemeta("[/$t]");
  $open2 = "<$t>"; $close2 = "</$t>";
  $expression = "!$open1(.+)$close1!Uis";
  $replacement = "$open2\1$close2";
  $text = preg_replace($expression, $replacement, $text);
}

Werkt hartstikke leuk. Maar nu dacht ik ff slim te zijn door te optimaliseren (als daar überhaupt sprake van is):

code:

$text = preg_replace(
  "!\\[([bui(tt)])\](.+)\\[/\1\]!Uis",
  "<\1>\2</\1>",
  $text
);

Dit werkt op zich wel, behalve wanneer er tags genest worden (dus een i binnen een u bv). Dan worden de binnenste tags helemaal niet verwerkt.

Is er een truukje waarmee ik kan zeggen dattie opnieuw moet beginnen met zoeken vanaf het begin ofzo? Ik heb al wat gekeken bij de informatie die ze bij php.net beschikbaar hadden gesteld, maar daar vond ik ook geen oplossing. (Misschien zie ik iets over het hoofd. ) Wél werd er iets interessants genoemd over recursiviteit, maar dat verhaal snapte ik niet echt.

Any help would greatly be appreciated.

[tomato]

Ik denk dat het op zich wel snelheidswinst oplevert, maar ik zie zo geen oplossing voor je probleem. Je kunt er misschien net zo lang doorgaan tot alle tags eruit zijn, zo''n idee dus:

PHP:

<?
while (preg_match("/\\[([bui(tt)])\](.+)\\[\/\1\]/is", $text))

   $text = preg_replace(  "!\\[([bui(tt)])\](.+)\\[/\1\]!Uis",  "<\1>\2</\1>",  $text);
?>

Ziet er misschien uit als overkill, maar is wellicht toch nog sneller, vooral bij lange teksten met weinig genestte tags. Maar dat zul je dus zelf even moeten testen...
Overigens vind ik het opvallend dat je in je pattern ook een reference naar een match (\1) mag gebruiken, maar je zei dat het werkte. Stukje uit da manual:

Replacement may contain references of the form \n or (since PHP 4.0.4) $n, with the latter form being the preferred one.

Je kunt je eerste manier overigens nog wat makkelijker schrijven, omdat je preg_replace ook arrays kunt voeren.

[tomato]

Ik lees net dat stukje over recursive patterns in de manual waar je het over had. Daar zou inderdaad iets mee te doen moeten zijn. Ik heb nu alleen gee.n zin om te testen, maar ik denk dat het de moeite waard is er even wat mee te proberen.

[Tuinhark]

Ik ben dan meer geneigd om zo te doen:

PHP:

<?
$newText = !$text; //quick ''n dirty

while ($newText != $text)

{

  $newText = $text;

  $text = preg_replace(

    "!\\[([bui(?:tt)])\](.+)\\[/\1\]!Uis",

    "<\1>\2</\1>",

    $text

  );

}
?>

Maar het is em nog niet helemaal volgens mij.

Ach en het is niet zo belangrijk. ''k Was eerlijk gezegd geïnteresseerd in wat Arien en jij hierover te melden hadden.

(En ja, ik kom nog terug op je meeltje. )

PS: Zat een foutje in de regexp geloof ik.
\2 moest zijn \3 óf het (tt) gedeelte moest zijn (?:tt).
Maar zo had ik het volgens mij niet in de code waarmee ik had getest. Ach, ik zoek het uit...

[tomato]

Tuinhark: Ik ben dan meer geneigd om zo te doen:
[code]

Dat zal inderdaad nog iets efficienter zijn waarschijnlijk

(En ja, ik kom nog terug op je meeltje. )

Ondertussen heb je waarschijnlijk meerdere dingen ontvangen. Ik hoor (/we horen) er wel van

Ach, ik zoek het uit...

Doe dat

Als ik een keertje tijd/zin heb kijk ik misschien nog even naar een recursive pattern (dan hoor je het uiteraard).

[bartvb]

Had ik een tijdje geleden nog een discussie over met iemand:

No, it''s not possible to match the nested tags with a regular expression, that''s the whole heart of the problem. I''ll try and explain why:

Essentially, we want to match something like this, right:
#[tag](.*)[/tag]#

Now, there are two ways the quantifier in the middle there can match - either greedy or non-greedy. Look at the following example code block, where I;ll indicate the tags each method will match:
[tag] -- greedy start, non-greedy start
[tag]

[/tag] -- non-greedy end
[/tag] -- greedy end

So, in this case, the non-greedy match fails - it doesn''t do the right thing at all. But, the greedy match works fine. Repeated applications of that regexp will do the job.

So, consider our next example. I''ll do the same thing as before:
[tag] -- greedy start, non-greedy start

[/tag] -- non-greedy end
[tag]

[/tag] -- greedy end

In this case, the exact opposite is true. The greedy tag fails completely, and the non-greedy tag does the right thing. So, since these two cases could easily occur inside the same message, we can see that there''s no way to accomplish this with a regular expression.

Make sense?

And I guess there is no modifier for that?

Nope, ''cause it''s not a regular language. A regular expression can only match a regular language. The language we''re talking about here is effectively A^n B^n, where A is "[tag]" and B is "[/tag]", which is the textbook example of a non-regular language.

Regular expression routines are implemented with a machine called a Finite State Machine. As the name implies, they have a finite number of different state the machine can be in, and they have no other memory other than what their current state is. That''s it. All they can do it look at the next character of input, look at their current state, and decide what the next state should be. very simple.

The problem is that to match A^n B^n, you need a potentially infinite amount of memory, because if you come across a B, your next action depends on how many A''s you''ve seen before. Since n could effectively be infinite, that can''t be represented in a finite number of states.

The machine used for A^n B^n is called a Push-Down Automaton. It''s basically a Finite State Machine with the addition of an (infinite) push-down stack. So, as we find A''s, we push them onto the stack. When we find a B, we pull an A off the stack. If we find a B and there are no A''s on the stack, then it doesn''t match.

[tomato]

En daar hadden ze dit (?R) dus op gevonden:

Consider the problem of matching a string in parentheses,
allowing for unlimited nested parentheses. Without the use
of recursion, the best that can be done is to use a pattern
that matches up to some fixed depth of nesting. It is not
possible to handle an arbitrary nesting depth. Perl 5.6 has
provided an experimental facility that allows regular
expressions to recurse (amongst other things). The special
item (?R) is provided for the specific case of recursion.
This PCRE pattern solves the parentheses problem (assume
the PCRE_EXTENDED option is set so that white space is
ignored):

\( ( (?>[^()]+) | (?R) )* \)

First it matches an opening parenthesis. Then it matches any
number of substrings which can either be a sequence of non-
parentheses, or a recursive match of the pattern itself
(i.e. a correctly parenthesized substring). Finally there is
a closing parenthesis.

This particular example pattern contains nested unlimited
repeats, and so the use of a once-only subpattern for match-
ing strings of non-parentheses is important when applying
the pattern to strings that do not match. For example, when
it is applied to

(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa()

it yields "no match" quickly. However, if a once-only sub-
pattern is not used, the match runs for a very long time
indeed because there are so many different ways the + and *
repeats can carve up the subject, and all have to be tested
before failure can be reported.

The values set for any capturing subpatterns are those from
the outermost level of the recursion at which the subpattern
value is set. If the pattern above is matched against

(ab(cd)ef)

the value for the capturing parentheses is "ef", which is
the last value taken on at the top level. If additional
parentheses are added, giving

\( ( ( (?>[^()]+) | (?R) )* ) \)
^ ^
^ ^ then the string they capture
is "ab(cd)ef", the contents of the top level parentheses. If
there are more than 15 capturing parentheses in a pattern,
PCRE has to obtain extra memory to store data during a
recursion, which it does by using pcre_malloc, freeing it
via pcre_free afterwards. If no memory can be obtained, it
saves data for the first 15 capturing parentheses only, as
there is no way to give an out-of-memory error from within a
recursion.

Sorry als de quote een beetje gaar is...
Daarmee zou dat dus precies wel te doen zijn, ik heb het alleen nog niet geprobeerd.

[bartvb]

Pffff, ik was nog niet helemaal wakker
Ziet er interessant uit gaan we maar eens naar kijken.

BTW op het moment doen we BBcode in 2 passes. Eerst een keer om die genestte paren te zoeken (en te vervangen door iets unieks), het resultaat daarvan komt in de DB.

Bij het view van een post wordt de 2e pass erop losgelaten die die tags vervangt door HTML. Hierdoor hoef je geen ingewikkelde dingen te doen bij topic views.

[tomato]

Ik heb nog een beetje rondgezocht, maar ik kan eigenlijk maar heel weinig vinden over deze experimentele feature.

Met die manier van mij (while (preg_match(blaat))...) of Tuinhark (while ($tekst != $newtekst)...) moet je er trouwens wel aan denken dat je regex greedy is (U modifier dus weghalen) anders kan het alsnog misgaan (met simpele UBB tags zal het overigens niet uitmaken).

[CyberSnooP]

Misschien kom ik jullie discussie verstoren, maar bestaat er nou dus een regex die het volgende tekst:

[big]Groot![big]NOG GROTER[/big][/big]
normaal
[big] en weer gewoon groot[/big]

verwerkt naar de bijbehorende HTML?
Ik kan namelijk dus niet kiezen tussen greedy en Un-greedy. Bij beide gaat het fout.

[tomato]

Dat is inderdaad precies het probleem waar we het hier over hebben

Met 1 simpele regex zul je hier inderdaad geen juiste resultaten mee behalen. Een manier is trouwens ook nog om te splitten op [big] en open/close -tags bij te houden op een stekkie...
Wordt voor meerdere UBB codes (zoals Tuinhark nu gebruikt) weer iets lastiger omdat je wel kunt splitten op [([bui(tt)])\] oid, maar dan weet je niet meer waar ie op gesplit is (b, u, i, of tt) en weet je dus ook niet op welke close-tag je moet letten...

[p0m]

Tuinhark''s stukje code

PHP:

<?
$newText = !$text;

//quick ''n dirty

while ($newText != $text)

{

    $newText = $text;

    $text = preg_replace(

        "!\\[([bui(?:tt)])\](.+)\\[/\1\]!Uis",

        "<\1>\2</\1>",

        $text  );

}
?>

is bijna hetzelfde als wat ik meestal gebruik voor m''n regex recursie, alleen kan het vergelijken van de oude en nieuwe strings in php omzeild worden, omdat preg dit in principe al voor je doet.

Ik weet niet precies hoeveel snelheid de e modifier opneemt, maar waarschijnlijk is dat minder dan de string comparison/copying.

(kan ook als while tuurlijk, maar deze is leuker )

PHP:

<?
    for ($match = true ; $match ;

        $text = preg_replace(

            ''!\\[([bui]|tt)\](.+)\\[/\1\]!Uise'',

            ''($match = true) ? \''<\1>\2</\1>\'' : 0'',

            $text)

        ) $match = false;
?>

[tomato]

Niemand meer iets over te zeggen? Anders maar eens op PHPFreakz vragen, misschien hebben ze daar meer verstand van zaken...

[tomato]

Dat is qua snelheid denk ik langzamer, want je voert nu toch nog altijd 1 regex te veel uit (wanneer deze laatste niets uithaalt stop je, altijd 1 ''nutteloze'' dus). Eigenlijk doe je dus ongeveer hetzelfde als wat ik deed, maar ik denk dat een simpele preg_match toch nog iets sneller is (bijv: stopt al na 1 match, geen /e).
Tuinhark''s manier lijkt me dan toch nog de snelste, ook al moet er een string gecopied en vergeleken worden.

Maar nu het interessante gedeelte van deze thread: (?R)
Wie heeft dit al eens (al dan niet succesvol) gebruikt? Mij lukt het namelijk nog voor geen meter

Test scriptje dat ik gebruik (dit pattern werkt dus niet):

PHP:

<?
php







$origineel = "Begin [buitenste voor [binnenste] buitenste achter] einde!";







$pattern = "/\\[((([^\\[\]]*)|(?R))*)\]/Uis";







echo "<font face=\"Courier new\"><BR>".$origineel."<BR><BR>";







echo preg_replace("/([\(\)])/", "<font color=\"#FF0000\">\1</font>", $pattern)."<BR><BR>";







preg_match_all($pattern, $origineel, $x, PREG_SET_ORDER);







while (list($k, $v) = each($x)) {



    echo "<BR><B>Match:</B><BR>";



    while (list($l, $w) = each($v))



        echo $l.": ".$w."<BR>";



}







echo "</font>"
?>

Wie er een werkend pattern in propt krijgt een biertje!

[edit]
Oja, ik heb al vanalles geprobeerd, wat hier nu toevallig staat zal niet m''n best probeersel van vandaag geweest zijn. Overigens gaat het alleen om $pattern = ..., rest van scriptje kun je c/p-en om snel en makkelijk te testen

[tomato]

Hmmm, wordt geen bier meer vandaag volgens mij

Ik kom er nog steeds niet helemaal uit met het recursieve gedoe van die PCRE. Zelfs het voorbeeld uit de PCRE docs lijkt weinig nut te hebben:

PHP:

<?
$origineel = "Begin (eerste voor (binnenste) eerste na) tussengeblaat (tweede stukje) einde!!!!";



$pattern = "_\( ( ( (?>[^()]+) | (?R) )* ) \)_xU";



echo "<FONT FACE=\"Courier new\"><BR>".$origineel."<BR><BR>";



echo preg_replace("/([\(\)])/", "<FONT COLOR=\"#FF0000\">\1</FONT>", $pattern)."<BR><BR>";



preg_match_all($pattern, $origineel, $x, PREG_SET_ORDER);



while (list($k, $v) = each($x)) {

    echo "<BR><B>Match:</B><BR>";

    while (list($l, $w) = each($v))

        echo $l.": ".$w."<BR>";

}



echo "</FONT>";
?>

Ik heb hier dus als voorbeeld een string met inhoud:

aa(b(cc)b)aa(dd)aa

Daarbij zou ik dus 3 sets van matches willen hebben, namelijk:

cc
b(cc)b
dd

Maar het enige wat ik terugkrijg is:

b(cc)b
dd

(?R) lijkt dus wel iets te doen (anders krijg je deze matches niet zomaar voor elkaar), maar niet wat ik wil. Je kunt nu natuurlijk door er een /e achter te plakken en dan de match weer door dezelfde regex heen te halen de recursiviteit een handje helpen, maar dat lijkt me niet echt optimaal.

Overigens is het me nu wel duidelijk dat, ook al zou het werken, je dit niet voor de UBB tags kunt gebruiken, dit omdat je het irritante stukje [^()] nodig hebt en je dat moeilijk na kunt bouwen voor een complete tag ipv een haakje
Ja, het kan wel weer door hem greedy te maken, maar dan heb je een probleem als er na je nesting (dus geheel losstaand hiervan, verderop in je tekst) nog meer tags staan (in voorbeeldje (dd)).

Je bent er dus nog niet zomaar met 1 regex
Maar misschien loopt er nog ergens een regex koning rond die hier iets over kan zeggen? *wink* *wink*

[tomato]

Nou nog maar wat zeggen dan . De manier van ''regexen tot je erbij neervalt'' om genestte tags eruit te krijgen is denk ik de gemakkelijkste (en misschien zelfs snelste?) methode om hier goed mee om te gaan, dit idee dus:

code:

while (er_zijn_nog_ubb_tags) (
   regex_replace()
)

En dat kan dan op Tuinhark''s, Heolan''s, of mijn manier, bla bla bla. Dit zal allemaal wel werken, maar denk er wel aan dat je de genestte tags niet in de ''juiste volgorde'' afhandelt! Als je bijvoorbeeld dit hebt:

(aa(bb)aa)

zul je eerste aa(bb krijgen en daarna bb)aa. Op zich bij simpel gebruik van UBB tags niet zo erg, maar het kan een probleem worden (en ik vind het niet zo netjes). Het lijkt of je dit kunt oplossen door je regex greedy te maken, maar dan heb je weer het probleem als je verderop in je tekst nog tags hebt staan, bijv bij:

a(bb(cc)bb)a(dd)a

Om het echt op een mooie manier te doen, met al deze dingen rekening houdend is het denk ik nog het makkelijkst een kleine parser te maken (die eventueel gebruik maakt van een regex split) die zelf bijhoudt welke open- en closetags er geweest zijn.


bartvb: BTW op het moment doen we BBcode in 2 passes. Eerst een keer om die genestte paren te zoeken (en te vervangen door iets unieks), het resultaat daarvan komt in de DB.

Wat bedoel je eigenlijk precies met het zoeken van genestte paren en het vervangen daarvan door iets unieks? Houd je dan rekening met oneindige diepte van de nesting en wat moet ik me voorstellen bij ''iets unieks'' (informatie en formaat daarvan zal toch behouden blijven?)?

Genoeg voor vandaag

[Ramon]

ik ben vast heel dom hierin... .... maar kan je niet gewoon de tags splitsen? Dus bijvoorbeeld[_b] regexpen en daarna [/b_]?

dus in twee keer doen ipv in 1 keer...?

Dat word natuurlijk wat moeilijk bij [_url] enzo...

[tomato]

Zoals je zelf al zegt wordt dat erg moeilijk als je de ''inhoud'' van een tag nodig hebt. Daarnaast houd je ook geen rekening met ''bad'' ubb-code, bijvoorbeeld een [ i] zonder [ /i] (op jouw manier zou je dus ook ''bad'' HTML krijgen, hetgeen je pagina weer kan vern#@$ken). Daarom

[edit] Oja, UBB codes werken hier...

[Ramon]

dat kan je toch oplossen door aan het eind van elke posting een </font> te zetten??

[tomato]

Ja, misschien wel, maar het is iig niet mooi. En denk bijvoorbeeld aan een quote, die je in een aparte <DIV> wilt zetten. Wat als iemand dan wel [ quote] gebruikt maar niet [ /quote], dan ziet je pagina er niet meer uit...

[Tom]

[offtopic] ik zou daar dus echt het geduld niet voor hebben om te maken

[Ramon]

heb je gelijk in ja...
maar als je het in een keer doet... hoe moet je dan nesten? ff voorbeeldje:

als iemand bij mij dit intikt:

code:

[_url=http://www.url.com][_img]http://127.0.0.1/pictures/icoon.gif[/img_][/url_]

dan krijgt ie een gelinkt plaatje, als die persoon het andersom doet, werkt het niet. En dat komt alleen maar omdat ik eerst [_img] en daarna pas [_url] verwerk. weet je een oplossing hiervoor??

owja en [_quote] moet ik nog ''inbouwen''

[Tuinhark]

Ik moet zeggen dat ik aangenaam verrast ben over de discussie (meer: workshop van tomato ) die nog volgde. Dank voor de insights. Ik denk dat ik het voorlopig maar gewoon houd op:

PHP:

<?
$oldText = !$text; //quick ''n dirty

while ($oldText != $text)

{

  $oldText = $text;

  $text = preg_replace(

    "!\\[([bui(tt)])\](.+)\\[/\1\]!Uis",

    "<\1>\2</\1>",

    $text

  );

}
?>

Dit lijkt goed te werken. (Ja, zonder "?:" in "(tt)".)

[tomato]

Tuinhark: (Ja, zonder "?:" in "(tt)".)

(?:iets) betekent dat er ''iets'' moet staan, maar dat het niet meegenomen wordt in je match (de haken tellen ook niet als subpattern). Is dus niet wat je hier nodig hebt

Die laatste vraag van Tampie2000 snap ik trouwens niet zo goed...

[Tuinhark]

tomato: (?:iets) betekent dat er ''iets'' moet staan, maar dat het niet meegenomen wordt in je match (de haken tellen ook niet als subpattern). Is dus niet wat je hier nodig hebt

Nee idd, maar toen ik een eindje terug de opmerking maakte over ?:, dacht ik namelijk dat \2 dan \3 moest zijn. Vaudje..

Tampie wil trouwens zowiets proberen volgens mij: [_img][_url=blaat]url_naar_plaatje[/_url][/_img]
Dat gaat idd niet gaan.

[tomato]

Dat doet inderdaad niet gaan doen. Vind het trouwens niet zo''n logische constructie, wat zou je hier nou mee willen als poster? Ja, een plaatje dat een link is, maar dan vind ik het logischer om de link om het plaatje heen te zetten...

PS Emails al gelezen?

[Ramon]

Ja goed gezegd! Is idd niet logisch om het andersom te doen!

Mooi... hoef ik me daar ook niet meer druk om te maken!

[tomato]

Tom zit alleen maar uren achter elkaar naar PS te staren (daar heb ik het geduld vaak niet voor)

[CyberSnooP]

Op donderdag 19 april 2001 10:05 schreef Tuinhark het volgende:

PHP:

<?
$oldText = !$text; //quick ''n dirty



while ($oldText != $text)



{



  $oldText = $text;



  $text = preg_replace(



    "!\\[([bui(tt)])\](.+)\\[/\1\]!Uis",



    "<\1>\2</\1>",



    $text



  );



}
?>

Dit lijkt goed te werken.

Ik snap eigenlijk niet waarom dit werkt. Je regex is UNgreedy, dus stel ik het dit stukkie tekst:

[big]aaa[big]bbb[/big]ccc[/big]

Dan matcht ie als eerst op:
aaa[big]bbb
toch?

Dit loopt dus mis als je met quotes of andere vreemde tags gaat werken.

Wat ik eigenlijk ook niet snap, is dat niemand hier eerder een stukkie code en/of reg-ex voor heeft uitgevonden

[tomato]

CyberSnooP: Ik snap eigenlijk niet waarom dit werkt. Je regex is UNgreedy, dus stel ik het dit stukkie tekst:
[big]aaa[big]bbb[/big]ccc[/big]

Dan matcht ie als eerst op:
aaa[big]bbb
toch?

Jah, heb je gelijk in maar echt erg is dat bij simpel UBB gebruik niet. Merkte ik overigens ook al op:

Dit zal allemaal wel werken, maar denk er wel aan dat je de genestte tags niet in de ''juiste volgorde'' afhandelt! Als je bijvoorbeeld dit hebt:
(aa(bb)aa)

zul je eerste aa(bb krijgen en daarna bb)aa. Op zich bij simpel gebruik van UBB tags niet zo erg, maar het kan een probleem worden (en ik vind het niet zo netjes). Het lijkt of je dit kunt oplossen door je regex greedy te maken, maar dan heb je weer het probleem als je verderop in je tekst nog tags hebt staan, bijv bij:

a(bb(cc)bb)a(dd)a

Dit loopt dus mis als je met quotes of andere vreemde tags gaat werken.

Inderdaad, als je bijvoorbeeld elke quote binnen een aparte DIV wilt plaatsen lukt je dat niet op deze manier...

Wat ik eigenlijk ook niet snap, is dat niemand hier eerder een stukkie code en/of reg-ex voor heeft uitgevonden

Nou, is niet helemaal waar. Daarvoor was dus die (?R), maar die snap ik dus nog niet helemaal (kan natuurlijk goed aan mij liggen)
En stukjes code voor recursieve patterns zijn er wel degelijk geschreven, heel veel zelfs waarschijnlijk. En daarmee is het ook prima op te lossen, alleen vergt het wat extra programmeerwerk en zoals je weet is iedere goede programmeur lui

[Tuinhark]

Ja, ik snap dat

[_b]vet [_b]vetter?[_/b][/_b]

mis gaat, maar daar zit ik niet mee... Zullen we het hier eens proberen:

vet vetter

Kijk? Hier gaat het ook mis. Bovendien is het helemaal niet de bedoeling om dat ''2e'' ook daadwerkelijk ''vetter'' te maken. Zodoende ben ik tevreden over genoemd stukje code.

Tomato: PS Emails al gelezen?
Als je bedoelt die enen die je laatst al had gestuurd, ik ben het nog ff laten bezinken. (Druk... - én het geheime projectje )

[tomato]

Euh... die van jou zou hiervoor wel goed resultaat geven hoor:

[_b]vet [_b]vetter?[_/b][/_b]

Niet in 1x, maar hij blijft door regexen tot het niet meer nodig is...

Over die emails, ik weet niet precies meer wat ik gestuurd had, maar waarschijnlijk heb je ook een uitnodiging gehad voor een virtueel kantoor, kom daar eens kijken als je tijd hebt...

[p0m]

Na wat scriptjes te hebben getimed, blijkt de e pattern-modifier toch (aanzienlijk) langzamer te zijn dan string comparisons, dit komt waarschijnlijk ondermeer doordat de e pattern-modifier PHP code net als eval() uitvoert, en dus de PHP code niet wordt geoptimized door php/zend zoals de string comparison methode.

Maar om terug te komen op tomato''s probleem :

Na gisteren wat gepuzzeld te hebben kwam ik op het volgende :
Je kan het ''(aa(bb)aa)cc(dd)'' probleem goed parsen met deze regex :

PHP:

<?
do



{



    $old = $text;



    $text = preg_replace(



        "!(.*)\\[([bui]|tt)\](.*?)\\[/\2\](.*)!is",



        "\1<\2>\3</\2>\4",



        $text



    );



}



while ( $text != $old );
?>

waardoor (aa(bb)aa)cc(dd) zo wordt geparsed:
1. (aa(bb)aa)cc(dd)
2. (aa<bb>aa)cc<dd>
3. <aa<bb>aa>cc<dd>

Hij pakt dus alle (xx) zonder ( of ) in xx, parsed deze, enzo verder van binnen naar buiten.
Dit komt doordat de binnenste .* ungreedy is, terwijl de rest greedy is.

edit:

hmmmm beetje gaar gedaan , is tuurlijk hetzelfde zonder (.*) op ''t eind en begin.
dit krijg je nou als je te lang over iets na denkt

[Tuinhark]

tomato: Euh... die van jou zou hiervoor wel goed resultaat geven hoor:

[_b]vet [_b]vetter?[_/b][/_b]

Niet in 1x, maar hij blijft door regexen tot het niet meer nodig is...

Nee toch? Of vergis ik me nu? De regexp was niet greedy, dus krijg je toch net zo''n effect als hier..

Ik ben inmiddels een soort van oplossing aan het ontwikkelen voor een soortgelijk probleem dat ik in mijn secret project heb. Het behelst een recursieve aanroep aan de functie die de preg_match uitvoert, dmv de e-modifier. ''t Werkt alleen nog niet helemaal. Als ik er niet meer uit kom, zal ik maar laten zien wat ik tot dan toe heb. (''k Wil eerst ff proberen het zelf op te lossen. )

tomato: Over die emails, ik weet niet precies meer wat ik gestuurd had, maar waarschijnlijk heb je ook een uitnodiging gehad voor een virtueel kantoor, kom daar eens kijken als je tijd hebt...

Dat zal denk ik van het weekend worden.. het spijt me echt dat ik je zo lang laat wachten, maar heb nog ff geduld.. BTW, zover ik op dit moment weet, had je me 2 emails gestuurd met jullie discussie.. Kep verder nog niet aan email gedaan vandaag en gisteren enzow.



NB: De reden dat ik zo secret doe over dat nieuwe projectje is puur om interessant te doen. Werkt het? Gekkigheid; ik ben erg trots op het resultaat zover en kan niet wachten tot het 100% functional is.

[tomato]

Tuinhark: Nee toch? Of vergis ik me nu? De regexp was niet greedy, dus krijg je toch net zo''n effect als hier..

De regex op zich wel, maar je voert hem toch in een lus uit?

Het behelst een recursieve aanroep aan de functie die de preg_match uitvoert, dmv de e-modifier. ''t Werkt alleen nog niet helemaal. Als ik er niet meer uit kom, zal ik maar laten zien wat ik tot dan toe heb. (''k Wil eerst ff proberen het zelf op te lossen. )

[inkoppertje] Nou, dan zien we je vandaag of morgen wel verschijnen

Dat zal denk ik van het weekend worden.. het spijt me echt dat ik je zo lang laat wachten, maar heb nog ff geduld.. BTW, zover ik op dit moment weet, had je me 2 emails gestuurd met jullie discussie.. Kep verder nog niet aan email gedaan vandaag en gisteren enzow.

Geefnie, we zien het vanzelf wel komen...

[..] en kan niet wachten tot het 100% functional is.

Ik ook niet


Heolan: Na wat scriptjes te hebben getimed, blijkt de e pattern-modifier toch (aanzienlijk) langzamer te zijn dan string comparisons [..]

Ja, daar ben ik ook achter gekomen. Vrij uitgebreide patterns replacen mbv /e wordt inderdaad vrij langzaam. Zelfgeschreven parser (met eventueel ''kleine'' regexjes) is naar mijn ervaring dan vaak toch sneller (maar soms ook wat minder flexibel).

waardoor (aa(bb)aa)cc(dd) zo wordt geparsed:
1. (aa(bb)aa)cc(dd)
2. (aa<bb>aa)cc<dd>
3. <aa<bb>aa>cc<dd>
Hij pakt dus alle (xx) zonder ( of ) in xx, parsed deze, enzo verder van binnen naar buiten.
Dit komt doordat de binnenste .* ungreedy is, terwijl de rest greedy is.

Dat is mooi, foutje in mijn verhaal dus (ja, soms roep ik maar wat, meeste test ik niet, dat duurt veel te lang )...

[Tuinhark]

tomato: De regex op zich wel, maar je voert hem toch in een lus uit?

Ach ja, je hebt helemaal gelijk, ik keek ff niet verder dan m''n neus lang is. Heb het toevallig net getest en het gaat idd goed. Dan zou het nu puur aan de browser zijn om dit goed te renderen: <b> vet <b> vetter </b> en weer vet </b>

tomato: [inkoppertje] Nou, dan zien we je vandaag of morgen wel verschijnen

Kom, kom zeg.. beetje vertrouwen in mijn kunnen, he? Sterker nog, hijs nu af: http://yapbb.sourceforge.net/PSPCooker/
Weliswaar niet met de bedoelde oplossing (recursieve aanroep verhaal ), maar uiteindelijk wél werkende (op PHP4.0.2 en hoger).

tomato: Geefnie, we zien het vanzelf wel komen...

Goed, m''n dingetje is af, ik ga zo slapen; morgen (vanmiddag ) ga ik weer verder met het normale leven. Zal ik nog es zien wat er bij de email is gekomen.

[Verwijderd]

Op woensdag 18 april 2001 20:56 schreef tomato het volgende:
Niemand meer iets over te zeggen? Anders maar eens op PHPFreakz vragen, misschien hebben ze daar meer verstand van zaken...

Een grap

[tomato]

Op zaterdag 21 april 2001 10:24 schreef Zef het volgende:

[..]

Een grap

Ja en een hele flauwe

[tomato]

Tuinhark
Het downloaden van PSPCooker gaat bij mij niet goed, verkeerd mime type? Source bekijken gaat trouwens wel, dus dan kan ik het er toch wel afhalen.
Heel cool gedaan zeg! Ik kan inderdaad geen recursieve aanroep van een preg_replace vinden, maar goed.
Wat wel cool zou zijn is een kleine webinterface waarmee je je template files kan uploaden waarna er direct een PSPCook overheen gegooid wordt. Als je dan alleen op die manier upload zijn er geen checks meer nodig om te kijken of de template file nieuwer is dan de cooked file. Maar dit bouw je er natuurlijk zo omheen.
Zeer cool gedaan moet ik zeggen, op deze manier kunnen standaard templates toch snel gemaakt worden!

[Tuinhark]

Okee, download probleem is inmiddels opgelost. Kep er nu een tar.gz van gemaakt ipv enkel een gz. Deed een beetje raar omdat er standaard een gzip module bij sourceforge draait.

En tomato, als jij je geroepen voelt om op basis van PSPCooker een nieuwe database-driven engine te maken (met web-interface en alles), ga vooral je gang.

(We zijn inmiddels flink off topic gegaan, maar who cares. )

[CyberSnooP]

Op zaterdag 21 april 2001 21:40 schreef Tuinhark het volgende:
(We zijn inmiddels flink off topic gegaan, maar who cares. )

Off-topic gaan is niet erg, maar toch.. een goedwerkende oplossing lijkt me niet onaardig

[Tuinhark]

Nou, de oplossing voor mijn oorspronkelijke probleem is, wat mij betreft, gewoon het volgende:

PHP:

<?
$oldText = !$text; //quick ''n dirty

while ($oldText != $text)

{

  $oldText = $text;

  $text = preg_replace(

    "!\\[([bui(?:tt)])\](.+)\\[/\1\]!Uis",

    "<\1>\2</\1>",

    $text

  );

}
?>

Werkt goed. En lijkt me sneller dan mijn oude oplossing (zie HELEMAAL bovenaan); daar doettie namelijk 4 preg_replace''s (en als je de tag-set uitbreidt, nog meer) en nu (normaal, als je niet gaat nesten) maar 2. (Alhoewel ik ook wel snap dat deze nieuwe oplossing een ingewikkeldere expression krijgt.)

[crisp]

Ik schop even een heel oud topic omhoog, hopelijk levert me dit alsnog een biertje van tomato op

Ik zat gisteren en vandaag te pielen met geneste quotes, en kwam op dit topic dat melding maakte van de mogelijkheid tot recursie binnen een regexp. Met een kleine hack heb ik het werkend gekregen.

Het gaat dus om de [ quote]bla[ /quote] waarbinnen eventueel nog andere quotes kunnen zitten. Er zijn 2 manieren om hiermee om te gaan; je kan geneste quotes vervangen door [...], of je kan ze daadwerkelijk genest opnemen.

De code:

PHP:

$content = '[quote][quote]een voorbeeld met geneste quotes[/quote]en nog een quote[quote]deze dus[/quote][/quote]nog even een losse quote[quote]de laatste dan[/quote]en dat was het :-)';

$content = parse_quotes($content);

echo $content;

function parse_quotes($content) {

  // voor als je nog geen htmlentities gebruikt hebt
  $content = str_replace('¡', '&#161', $content);
  $content = str_replace('¿', '&#191', $content);

  // hack
  $content = str_replace('[quote]', '¡', $content);
  $content = str_replace('[/quote]', '¿', $content);

  $content = preg_replace('/¡((([^¡¿]*)|(?R))*)¿/Uise', 'quote(\'$1\')', $content);

  // ungematchede quote tags (nesting errors) weghalen
  $content = str_replace('¡', '', $content);
  $content = str_replace('¿', '', $content);

  return $content;

}

function quote($content) {

  // toggle genest (recursief) of geneste quotes vervangen door [...]
  $content = preg_replace('/¡((([^¡¿]*)|(?R))*)¿/Uise', 'quote(\'$1\')', $content);
//  $content = preg_replace('/¡((([^¡¿]*)|(?R))*)¿/Uis', '<br />[...]<br />', $content);

  return '<blockquote>quote:<hr width="100%" size="1" color="#808080" />'.$content.'<hr width="100%" size="1" color="#808080" /></blockquote>';

}

[tomato]

crisp schreef op 22 April 2003 @ 00:06:
Ik schop even een heel oud topic omhoog, hopelijk levert me dit alsnog een biertje van tomato op

Ik weet niet of je de houdbaarheidsdatum van dat biertej ook wilt weten

Ik zat gisteren en vandaag te pielen met geneste quotes, en kwam op dit topic dat melding maakte van de mogelijkheid tot recursie binnen een regexp. Met een kleine hack heb ik het werkend gekregen.

Goed gevonden, hoewel de ¡/¿ inderdaad wel een flinke hack is

[.oisyn]

waarvoor zijn de ¡ en ¿ dan nodig? .edit: oh om de quote tags tot 1 char te krijgen

En de recursie zit ook niet in de regex, maar gewoon in de evaluatie functie die in php geimplementeerd is.

Bovendien ben ik nog steeds van mening dat dit soort parsers niet met regex replaces geimplementeerd moeten worden

maar kun je niet gewoon greedy scannen voor de [/quote] tag?

[ Voor 20% gewijzigd door .oisyn op 23-04-2003 12:51 ]

[crisp]

.oisyn schreef op 23 April 2003 @ 12:49:
waarvoor zijn de ¡ en ¿ dan nodig? .edit: oh om de quote tags tot 1 char te krijgen

justem
het is een beetje lastig om te matchen op een string die geen [ quote] of [ /quote] bevat zonder ingewikkelde constructies (toch een gemis imho).

En de recursie zit ook niet in de regex, maar gewoon in de evaluatie functie die in php geimplementeerd is.

Er zit wel degelijk recursie in de regexp; ik match nu op alles wat tussen ¡ en ¿ staat maar zelf geen ¡ en ¿ bevat, TENZIJ het weer een match van de pattern zelf is.

Bovendien ben ik nog steeds van mening dat dit soort parsers niet met regex replaces geimplementeerd moeten worden

stack-based is beter, maar vaak ook trager en complexer.

maar kun je niet gewoon greedy scannen voor de [ /quote] tag?

ja, en als ik dan dit heb:

[ quote]
[ quote]bla[ /quote]
bla
[ quote]bla[ /quote]
[ /quote]
blabla
[ quote]bla[ /quote]

dan klopt het niet meer met een greedy regexp; vandaar de recursie in de regexp zelf

[.oisyn]

crisp schreef op 23 April 2003 @ 12:58:
Er zit wel degelijk recursie in de regexp; ik match nu op alles wat tussen ¡ en ¿ staat maar zelf geen ¡ en ¿ bevat, TENZIJ het weer een match van de pattern zelf is.

oh ja idd, die (?R)
kende ik niet

stack-based is beter, maar vaak ook trager en complexer.

trager complexer
Ten eerste is het bijna altijd sneller (mits goed geimplementeerd, en nee natuurlijk niet in PHP, aangezien je geen goede lexical analyser kan bouwen in PHP). Als je meerdere tags hebt moet je meerdere regex replaces doen over dezelfde string. Bovendien kun je niet echt rekening houden met speciale features zoals bijvoorbeeld een code-tag waarin geen andere tags gereplaced mogen worden. Of je moet echt hele ingewikkelde regexen opzetten (als het al kan).
Met een parser doorloop je de string in 1 keer, en tokenize je alles tot tags of tekst (dit is een vrij snel proces). De parser gaat deze tokens vervolgens matchen aan de hand van een bepaald patroon. Dit wordt bij een parser van bijvoorbeeld een programmeertaal behoorlijk complex, maar voor zoiets simpels als dit is het echt goed te doen. En ik vind de ingewikkelde regexen om met alles rekening te houden een stuk complexer dan een parser (ga jij maar na 6 maanden nog eens kijken wat die regex ook alweer allemaal deed als je er geen comments bij had gezet )

ja, en als ik dan dit heb:

klopt, helemaal gelijk in
had ik even geen rekening mee gehouden

[crisp]

Voor tags waarbinnen niets geparsed mag worden heb ik deze oplossing:

PHP:

// tussen [pre] en [/pre] niets replacen

// matches op [pre] [/pre] opslaan
preg_match_all('/\\[pre\](.+)\\[\/pre\]/Uis', $content, $prematches);

// nu alle andere regexpes over de content halen
$content = preg_replace('/\\[b\](.+)\\[\/b\]/Uis', '<b>$1</b>', $content);
$content = preg_replace('/\\[i\](.+)\\[\/i\]/Uis', '<i>$1</i>', $content);
$content = preg_replace('/\\[s\](.+)\\[\/s\]/Uis', '<s>$1</s>', $content);
$content = preg_replace('/\\[u\](.+)\\[\/u\]/Uis', '<u>$1</u>', $content);
// etcetera, hoe meer hoe beter ;)

// en zet nu alles wat oorspronkelijk tussen [pre] en [/pre] stond weer terug :)
if (count($prematches)) {

  $i=0;
  $content = preg_replace('/\\[pre\](.+)\\[\/pre\]/Uise', '\$prematches[1][\$i++]', $content);

}

heerlijk ranzig nietwaar?

[.oisyn]

En je hebt je nu zojuist tegengesproken op het gebied van zowel traagheid als complexiteit

[crisp]

.oisyn schreef op 23 April 2003 @ 16:31:
En je hebt je nu zojuist tegengesproken op het gebied van zowel traagheid als complexiteit

Maar de heerlijke ranzigheid maakt toch een hoop goed nietwaar?

Enfin: ik heb het maken van een stack-based parser nog op mijn to-do lijstje staan. Tot dan zal ik jullie lastig blijven vallen met hopelijk nog ranzigere regexps

zoals hier dus: Regexp probleem zoek naar = binnen <>

[ Voor 9% gewijzigd door crisp op 23-04-2003 16:50 ]

[.oisyn]

Ik was van plan om voor Orbb een klasse te maken waarmee je meerdere regexen met elkaar kunt combineren, waarbij je voor elke regex een bepaalde action opgeeft.

Vervolgens scan je een string, en dan wordt van begin tot eind gezocht naar matches, waarop vervolgens voor elke match de bijbehorende action wordt uitgevoerd. Dit is ook de manier waarop lexical analysers worden gemaakt. Wellicht een interessant iets om ook aan de php library toe te voegen.

Je moet je er dan zoiets bij voorstellen (even java code genomen voor highlighting)

Java:

class MyActions
{
    var str;
    constructor ()
    {
        str = "";
    }

    function actionDefault (var totalString, var matchedString, var pos)
    {
        str += matchedString;
    }

    function actionAap (var totalString, var matchedString, var pos)
    {
        str += "1";
    }

    function actionNoot (var totalString, var matchedString, var pos)
    {
        str += "2";
    }

    function actionMies (var totalString, var matchedString, var pos)
    {
        str += "3";
    }
}

var l = new Lexer ();
l.setDefault ("actionDefault");
l.addRule ("aap", "actionAap");
l.addRule ("noot", "actionNoot");
l.addRule ("mies", "actionMies");

var m = new MyActions ();
l.scan ("hallo hallo aap hier staat noot wat leuks mies", m);

System.wrinteln (m.str);

De output wordt dan: "hallo hallo 1 hier staat 2 wat leuks 3"

Op eenzelfde manier is ook gewoon een array van tokens te genereren die kan worden gebruikt voor je parser.

[vorlox]

Shit gepost bij verkeerde onderwerp:

*zucht*

[ Voor 89% gewijzigd door vorlox op 23-04-2003 18:57 ]

[vorlox]

Ik vind dit inderdaad wel een interresant onderwerp


Wat ik doe om eerst er vanuit te gaan dat er geen bad UBB code in zit zoals een niet afgesloten [i] ofzo is eerst een substr_count("$text","") en een substr_count("$text","");

als per tag de waarden niet gelijk zijn disable ik de omzetting naar HTML voor deze tags.

[crisp]

vorlox schreef op 23 april 2003 @ 18:58:
Ik vind dit inderdaad wel een interresant onderwerp


Wat ik doe om eerst er vanuit te gaan dat er geen bad UBB code in zit zoals een niet afgesloten [i] ofzo is eerst een substr_count("$text","") en een substr_count("$text","");

als per tag de waarden niet gelijk zijn disable ik de omzetting naar HTML voor deze tags.

in feite zoek je hiermee al een bijbehorend paar (voordeel boven str_replace op eerst [tag] en dan op [/tag]) waardoor je al geen verkeerde en/of onafgesloten html tags krijgt:

PHP:

$content = preg_replace('/\\[b\](.+)\\[\/b\]/Uis', '<b>$1</b>', $content);

als er dan toch een [ b] of [ /b] teveel in staat, wordt die gewoon niet geparsed.

[ Voor 7% gewijzigd door crisp op 23-04-2003 19:11 ]

[sjokki]

Ik heb een tijd geleden dit geschreven voor het geneste quotes probleem. Zonder omgekeerde vraagtekens:

PHP:

<?

// functie replace_recursive_quote()
// zoekt in een string naar [quote]...[/quote]
// tussen de tags kan ook weer [quote]...[/quote] staan
function replace_recursive_quote ($str)
{
  $search =
  '
    /
      \[quote]

      (?:
        (?:
          # alles behalve "["
          [^[]
          |
          # of "[" maar dan niet gevolgd door "quote"
          \\[(?!\/?quote)
        )+
        |
        # als er wel [quote] gevonden wordt moet er recursief gematcht worden
        (?R)
      )*

      \\[\/quote]
    /xi
  ';

  return preg_replace_callback($search, 'format_quote', $str);
}


// functie format_quote()
// verwerkt de matches en zorgt voor de opmaak
// wordt aangeroepen door replace_recursive_quote()
// roept zelf ook weer replace_recursive_quote() aan
function format_quote ($matches)
{
  $str = substr($matches[0], 7, -8);
  $ret_str  = '<div style="margin: 5px;"><b>Quote:</b>';
  $ret_str .= '<div style="border:1px solid black; margin-left:10px; background:yellow">';
  $ret_str .= replace_recursive_quote($str);
  $ret_str .= '</div></div>';

  return $ret_str;
}


// een voorbeeld
$str = 'bb [quote] bla bla [quote] blabla [/quote] bb [/quote] blabla';
echo replace_recursive_quote($str);
?>

[crisp]

sjokki schreef op 23 April 2003 @ 19:34:
Ik heb een tijd geleden dit geschreven voor het geneste quotes probleem. Zonder omgekeerde vraagtekens:

[...]

Geef mijn biertje maar aan sjokki!

uiteindelijk heb ik nu dit:

PHP:

$content = preg_replace('/\[quote]((([^[]|\\[(?!\/?quote))*|(?R))*)\\[\/quote]/Uise', 'quote(\'$1\')', $content);

function quote($content) {

  // toggle genest of geneste quotes vervangen door [...]
//  $content = preg_replace('/\[quote]((([^[]|\\[(?!\/?quote))*|(?R))*)\\[\/quote]/Uise', 'quote(\'$1\')', $content);
  $content = preg_replace('/\[quote]((([^[]|\\[(?!\/?quote))*|(?R))*)\\[\/quote]/Uis', '<br />[...]<br />', $content);

  return '<blockquote>quote:<hr width="100%" size="1" color="#808080" />'.$content.'<hr width="100%" size="1" color="#808080" /></blockquote>';

}