[RegEx] Eerst de geneste matches verwerken - Softwareontwikkeling

vrijdag 3 maart 2006 17:10

Acties:

Topicstarter

(Nogal een lange post. De concrete vraag staat aan het eind, maar ik leg liever de situatie grondig uit, want misschien zijn er oplossingen waar ik nog niet aan heb gedacht)

Ik ben met .NET bezig om een vrij complexe parser te schrijven voor een simpele markup taal die gebruikt wordt om e-mails te genereren op basis van een template. Om het eenvoudig te houden gebruik ik een soort HTML-achtige structuur, waarvan de elementen worden ingevoegd in gewone HTML. Een mogelijke template is:

code:

<HTML>
   <!RECORDLOOP DATA="select userID, name FROM security_users"!>
      <P>
          <!COLUMN INDEX="0"!> | <!COLUMN INDEX="1" MAXLENGTH="50"!>
      </P>
      <HR>
   <!/RECORDLOOP!>
</HTML>

Nu kan de parser het bovenstaande zonder problemen verwerken. Het voorbeeld is een beetje nuteloos, want het produceert alleen lijst met alle gebruikers (met ID en naam) in het systeem, maar het idee is duidelijk. Ik gebruik een aantal complexe regular expressions om de elementen te ontrekken aan de template, die te verwerken, en het resultaat weer terug te plaatsen in het origineel (via een matchevaluator). Nu werkt dat allemaal ook goed.

Mijn probleem zit hem in ge-neste matches. Wat ik wil kunnen is, om het even bij mijn systeem te houden, dat ik recordloop *binnen* recordloops kan plaatsen. Een ge-neste loop dus. Die loop zou ik dan eerst willen verwerken, waarna de grotere loop (laten we het maar 'de parent' noemen) verwerkt wordt. Het lastige is dat ik niet tot een regular expression kom die dat mogelijk maakt. De expressie die ik nu heb om de recordloops op te sporen (het eerste deel :

code:

1	<!RECORDLOOP.?!>(?<template>[\s\S]?)<!\/RECORDLOOP!>

Deze expressie werkt niet bij een ge-neste recordloop omdat hij het stuk tussen de recordloop elementen zo kort mogelijk probeert te houden (non-greedy). Stel:

code:

   <!RECORDLOOP DATA="select userID, name FROM security_users"!>
      <!RECORDLOOP DATA="select userID, name FROM security_users"!>
      <!/RECORDLOOP!>
   <!/RECORDLOOP!>

Het resultaat is met bovenstaande expressie is dan:

code:

1
2
3

   <!RECORDLOOP DATA="select userID, name FROM security_users"!>
      <!RECORDLOOP DATA="select userID, name FROM security_users"!>
      <!/RECORDLOOP!>

Als ik de expressie greedy maak, dus:

code:

1	<!RECORDLOOP.?!>(?<template>[\s\S])<!\/RECORDLOOP!>

Dan werkt het op zich goed. Het gaat dan alleen weer mis bij andere constructies:

code:

   <!RECORDLOOP DATA="select userID, name FROM security_users"!>
   <!/RECORDLOOP!>
   <!RECORDLOOP DATA="select userID, name FROM security_users"!>
   <!/RECORDLOOP!>

Met een greedy match krijg ik dan ook meteen alles terug, terwijl ik juist 1 loop per keer wil kunnen verwerken:

code:

   <!RECORDLOOP DATA="select userID, name FROM security_users"!>
   <!/RECORDLOOP!>
   <!RECORDLOOP DATA="select userID, name FROM security_users"!>
   <!/RECORDLOOP!>

Ik hoop dat het probleem een beetje duidelijk is, want het is nogal lastig uit te leggen

Maar ik hoop dat iemand weet hoe je dit met regular expressions aan kunt pakken. Wat ik concreet zoek is een expressie die de allerkleinste match (in lengte van karakters) eerst pakt. Niet de eerste match in de string (qua index). Als ik de kleinste eerst pak, en daarna omhoog ga, komt het goed.

[ Voor 18% gewijzigd door Christiaan op 03-03-2006 17:12 ]

vrijdag 3 maart 2006 17:28

Acties:

NMe

Quia Ego Sic Dico.

Met regexps zijn er twee oplossingen geloof ik. Eén mogelijke oplossing is lookahead/lookbehind assertion, maar daar weet ik niets tot weinig vanaf, dus daar doe ik geen uitspraken over. Een tweede optie is iets wat bijvoorbeeld phpBB doet bij geneste quotes: die voegen in de database aan elke quote-tag een uniek GUID toe, waardoor de interne tag zo wordt:
[quote:3403]blaat
[quote:4032]iets[/quote:4032]
blaat[/quote:3403]
Dit is uiteraard een stukje makkelijker te matchen. Of het al dan niet toepasbaar is bij jouw situatie weet ik niet, dat is aan jou om te bepalen.

Wat ik persoonlijk een betere oplossing zou vinden is het concept van regexps overboord gooien en kijken wat een stackbased parser voor je kan betekenen. Stackbased parsers zijn een stukje minder gevoelig voor fouten en kunnen complexere dingen zoals dit op een eenvoudigere manier mogelijk maken.

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.

vrijdag 3 maart 2006 17:37

Acties:

Christiaan

Topicstarter

Thnx voor de input. Ik had nog niet stilgestaan dat lookaheads en behinds hier ook goed te gebruiken zijn. Wat stackbased parsing betreft; ik heb het idee dat je bij alleen het dumpen van recordsets in HTML beter af bent met een simpelere recursieve parser. Zo zwaar hoeft het niet te worden namelijk. Er komen weinig logische bewerkingen in. Daar gebruik ik wel XML voor. In dit geval wilde ik iets waar ik snel mailtemplates of templates voor overzichten kan genereren, die ik ook vanuit een formpje op de site aan kan passen. Maar stackbased parsing is wel iets waar ik naar wil kijken als ik wat meer tijd heb.