[RegEx] Alternatief voor Lookahead

[Maniakje]

Ik heb een reguliere expressie nodig die een zo groot mogelijke match maakt waarbij die match niet gevolgd mag worden door een bepaald karakter, zonder gebruik te maken van Lookahead.


Ik ben hierbij gebonden aan Delphi 2006 voor Win32 in combinatie met de gratis component TRegExpr.

Wat ik wil doen is een inkomende string converteren naar een uitgaande string waarin het aantal herhalingen per karakter is aangegeven. In de inkomende string kan het aantal herhalingen echter ook al zijn aangegeven. Enkele voorbeeldjes:

code:

AAA    ---> A(3)
A(3)   ---> A(3)
AAA(3) ---> A(5)
AA(2)A ---> A(4)

Het getal tussen haakjes slaat hierbij enkel op het voorgaande karakter.

Om dit te bewerkstelligen lijkt het mij handig om eerst de tekens te vinden die nog geen herhalingsaantal hebben. Daarvoor wil ik een reguliere expressie maken die bv uit AAA(3) de eerste twee A's matcht, of specifieker: die een zo lang mogelijke match van A's maakt die niet gevolgd wordt door een openingshaakje. Het idee daarachter is dat ik, zodra ik een match heb, die match kan vervangen door A(lengte van de match) waarna de volledige string staat in de vorm A(n)A(n)A(n). Daarna is het nog slechts een kwestie van omschrijven naar A(som van alle n's).

Na ongeveer 20 seconden zoekwerk hier op GoT was ik er al achter dat een Lookahead constructie precies doet wat ik wil: het matchen van iets dat niet gevolgd wordt door iets anders. Helaas heeft de TRegExpr component geen ondersteuning voor Lookaround constructies dus moet ik iets anders verzinnen.

Natuurlijk kan ik handmatig door de string heen lopen om dit te doen, maar is dit ook te doen door middel van een regex-replace zonder gebruik te maken van lookahead?


Note: ik heb het probleem enigszins versimpeld. In werkelijkheid gaat hier niet om invoer die iets ingewikkelder is dan enkel een opeenvolging van A's.

[pedorus]

[google=regular expressions two problems]?

Als je dit perse wil doen met regexp, dan is er geen lookahead constructie nodig, aangezien regexp standaard greedy is. Dan nog hou je bijna hetzelfde probleem over van het parsen, want regexp is geen calculator (normaal gesproken dan).

Als het om hele lange regels gaat, dan is het qua snelheid handig om voor de gehele lengte van de string alvast geheugen te claimen. Zie bijvoorbeeld dit voorbeeld.

Wat moet er trouwens gebeuren bij "BA(3)(3)B(2)B" als input?

[Maniakje]

Two problems. Daar zit zeker een kern van waarheid in.

BA(3)(3) is ongeldige invoer en zal niet voorkomen.

---

Stel, de invoer is AAAAxBBBxBBxA. Ik heb de (n) even vervangen door een x om de expressie verderop leesbaarder te maken.

De expressie A+|B+ geeft nu vier matches, te weten AAAA, BBB, BB en A. Wat ik echter hoop te bereiken is een expressie die de matches AAA, BB, B en A geeft.

Mijn eerste gedachte was om (A+|B+)[^x] te gebruiken: een zo lang mogelijke reeks A's of B's die niet gevolgd wordt door x. Dit geeft het dezelfde resultaat als de voorgaande expressie, omdat nu de [^x] nu wordt gematcht met telkens het laatste teken uit het invoerdeel. (A+ matcht AAA en [^x] matcht de vierde A).

Volgende poging: (A+[^xA])|(B+[^xB]). Resultaat: geen matches. Probleem is ook dat bij het matchen de [^xA] ook wordt geconsumeerd terwijl ik enkel geïnteresseerd in het deel dat ervoor staat. De match met [^xA] moet dus geen onderdeel zijn van het resultaat.

Zou je een voorbeeldje kunnen geven hoe ik dit aanpak zonder lookahead?

[pedorus]

Je zoekt naar groepjes van een karakter met eventueel een aantal erachter. Als zo'n groepjes gevolgd wordt door 1 of meer dezelfde groepjes, dan heb je een match. Je kan dat doen met backreferences.

Het probleem is dan dat je in die match de aantallen nog moet zien te vinden, en eigenlijk dubbel werk gaat doen. (Perl-regexp heeft daar trouwens wel oplossingen/hacks voor.)

Enkel op deze manier heb je eigenlijk ook al een parser gevonden:

code:

while (volgendeKarakter())
    huidigeKarakter:=leesKarakter();
    aantal:=leesAantalIndienBeschikbaar();
    while(volgendeKarakter()==huidigeKarakter)
        leesKarakter();
        aantal:=aantal+leesAantalIndienBeschikbaar();
    end while
    schrijfKarakter(huidigeKarakter);
    if (aantal>1) then schrijfAantal(aantal)
end while

Het is in Delphi handig om bij grote strings alvast de maximale lengte voor de resultaat-string te declareren (2x de huidige lengte in dit geval, bij "AABB").

[pkuppens]

Begrijp ik goed dat je van 'AAAA(1)' alleen 'AAA' wil hebben en van 'AAA(1)' wil je 'AA', ik weet niet helemaal of dat wel kan zonder lookahead.
Wat je misschien zou kunnen proberen is om een ungreedy
{A*?}A( te doen.

Wat je ook zou kunnen doen is om je string op te slaan, en hier in verschillende runs je reguliere expressies op loslaat, waarbij je zelf nog wat string manipulaties kunt doen, of wat logica kunt loslaten als je wel of niet (x) in je expressie tegenkomt.
Die logica ga je toch nodig hebben om dingen op te tellen, want dat doen reguliere expressies niet.

Succes.

-edit: vergeet ungreedy, probeer A*A of A*Ax
en manipuleer je output en remainder.

[ Voor 6% gewijzigd door pkuppens op 19-08-2008 14:18 ]

[ATS]

waarom parse je de string niet gewoon token voor token? Ik zie niet in waarom je hier een regexp voor zou gebruiken.

[_wm_]

je kan toch ook de A(3) vervangen door AAA, en daarna alle A's tellen? Dat lijkt me eenvoudiger...

Als je het op 'jouw' manier wil doen, kan je doen (A+)Ax|A+ wat er 'uitgewerkt' als volgt uit zou komen te zien: (A+)A\(.+?\)|(A+)

op-datum: even getest en het werkt...

[ Voor 9% gewijzigd door _wm_ op 20-08-2008 12:28 ]

[Verwijderd]

pedorus schreef op dinsdag 19 augustus 2008 @ 09:33:
Het is in Delphi handig om bij grote strings alvast de maximale lengte voor de resultaat-string te declareren (2x de huidige lengte in dit geval, bij "AABB").

Ik wil dit niet afbranden als onzin, maar bij Delphi voor Win32 zijn dit micro-optimalisaties die in het gros van de gevallen absoluut niet de moeite waard zijn.
Bij (Delphi voor) .NET is 't een heel ander verhaal, en zou ik bijna per definitie een StringBuilder gebruiken.

Voorbeeldje:
Een codegenerator die een database structuur omzet naar een class per tabel (resultaat: 65000+ regels code) kost me in Delphi/Win32, zonder de (onbekende) lengte van de Result string te definieren, zo'n 3 a 4 seconden.
In C# (.NET dus) kost dat onder dezelfde omstandigheden ongeveer 20 minuten, en met een StringBuilder werd dat weer 4 seconden.

Boxing/unboxing is duur in .NET...