regular expression: maar niet

[_DeWie_]

Ben aan het stoeien met regular expressions, maar kan er niet echt uitkomen.

Wil een emailadres controleren tot de @ :

/^[/w.\-]+$/

maar nu wil ik dat root en postmaster niet kunnen.
Iemand enig idee waar ik dit kan vinden of hoe dit moet

[dusty]

In ware gewoon een reguliere expressie die zegt:

code:

(Niet root) en (Niet postmaster) en ( geldig email adres formaat)

[Juup]

Waarschijnlijk zul je het moeten opdelen in 2 regexps:
(perl style)

code:

if ($email =~ m/^([a-zA-Z0-9]+)\@\w+\.\w+/)
{ my $firstpart = $1;
  if ($firstpart !~ m/^(root|postmaster)$/)
  { &doSomething();
  }
  else
  { print "Don't mail root or postmaster!\n";
  }
}
else
{ ...
}

[_DeWie_]

Ja dat is dus mijn probleem.
Het is inderdaad in Perl, hier gebruik ik een leuke module om formulieren te controleren.
Ik wil het dus eigenlijk in een regex

[Grum]

het kan met een regexp hoor

het enige probleem wat je zal hebben is dat je niet (simpel) kan zeggen 'dit of dit niet'

bv iets als

[^(root|postmaster)]

zal niet werken

maar daar is wel wat omheen te coden ...

ik stel voor .. een sexeger (reversed regexp ) icm met look-aheads

[_DeWie_]

Grum, heb hier een leuk perlboek, maar kan het niet echt vinden ....

Kun je nog een tipje van de sluier lichten ??

[tomato]

code:

/^(?!postmaster|root)[/w.\-]+$/

Bedoel je zoiets?

Ik snap overigens niet precies wat je met die [/w.\-]+ probeert te bereiken en al helemaal niet met die $ erachter (omdat je zegt dat je tot de @ wilt controleren)...

[tomato]

Overigens vind ik het wel iets netter staan om gewoon een regex voor je email te gebruiken en daarnaast te checken of het gedeelte voor de @ geen 'postmaster' of 'root' is.

code:

if (/^([^@]+)@.*$/) {
   if ($1 =~ /^(root|postmaster)$/) {

   }

}

Dat wordt een stuk onderhoudbaarder (natuurlijk stelt mijn regex hier niets voor ).

[_DeWie_]

Even voor de duidelijkheid, wat ik controleer is gewoon 1 veld, het steld alleen een emailadres voor tot de @.

En is misschien inderdaad netter om dat buiten de regex te controleren.
Kan het nooit zo goed hebben als iets niet lukt, en het is nu een principe kwestie.

Onderhoudbaarheid valt in dit geval ook wel meer, in het geval van een regex kan ik de controle middels een mooie module doen (http://search.cpan.org/doc/MARKSTOS/Data-FormValidator-1.5/lib/Data/FormValidator.pm), alle veldcontroles staan dan in een bestand.

[_DeWie_]

Op maandag 25 maart 2002 13:28 schreef tomato het volgende:

code:

/^(?!postmaster|root)[/w.\-]+$/

Bedoel je zoiets?

Ja dit schijnt te werken.
even om het te begrijpen :

? staat voor 0 of 1 keer
dan moet die ! dus voor niet staan ???????

[tomato]

_DeWie_: even om het te begrijpen :

? staat voor 0 of 1 keer
dan moet die ! dus voor niet staan ???????

Nee, de ? heeft hier een andere betekenis. Omdat een ? als quantifier (0 of 1 keer) na een '(' over het algemeen onzin is, kan het in die vorm een speciale betekenis hebben:

code:

(?!   pattern   )

Dit is een negative lookahead. Op dit punt mag 'pattern' niet matchen. Een negative lookahead 'eet' geen karakters (vandaar de naam lookahead), het volgende stukje van de regex start dus gewoon op hetzelfde punt als waar de negative lookahead startte.

Positive lookahead:

code:

(?=   pattern   )

Non-grouping parentheses:

code:

(?:   pattern   )

Zoals je ziet wordt de (? constructie vaker gebruik voor speciale functionaliteit.
Overigens komt de ? nog in drie andere vormen voor naast quantifier en onderdeel van deze 'speciale blokken':

Achter een quantifier (*?, +?, ??, {0,7}?) is het een greedyness modifier.

Binnen een character class ([a-zA-Z?] matcht lower- en uppercase letters en een vraagteken).

Met een \ ervoor (escaped vraagteken matcht gewoon letterlijk een vraagteken).

[_DeWie_]

Dankje, zie nu in mijn boek,
dat dit hoort bij Extended Regular Expression

Bedankt !!!

[drm]

tomato:
uberuitleg
[..]

tomato behulpzaam +1

[Soultaker]

Wilde nog even vermelden dat niet alle tot nu toe besproken methoden POSIX-compliant waren en hoogstwaarschijnlijk alleen in Perl-style re's werken. Voor zowel de leesbaarheid als de efficientie zou ik voor tomato's TWEEDE suggestie (met 't ifje) kiezen.

[tomato]

Soultaker: Wilde nog even vermelden dat niet alle tot nu toe besproken methoden POSIX-compliant waren en hoogstwaarschijnlijk alleen in Perl-style re's werken.

Nee, maar aan POSIX heeft hij ook niets, omdat de perl regex engine niet POSIX compliant is. Regexen zijn alles behalve portable, dus dat probleem houd je altijd wel...

En daar naast is perl-style natuurlijk niet zomaar een willekeurige. Perl regex compatibility wordt erg veel nagebootst, zie bijvoorbeeld de PCRE library en Microsoft's regex library.

Blijft natuurlijk een feit dat het echte perlish constructies zijn

[Soultaker]

Op maandag 25 maart 2002 15:45 schreef tomato het volgende:
Nee, maar aan POSIX heeft hij ook niets, omdat de perl regex engine niet POSIX compliant is. Regexen zijn alles behalve portable, dus dat probleem houd je altijd wel...

De meeste modern POSIX regexps doen 't wel onder Perl. Ik zou zelfs willen beweren alle, aangezien ik geen constructie zou kunnen verzinnen die niet werkt, maar dat is natuurlijk geen bewijs.

Het idee van POSIX is juist dat regexps wel portable worden. Ik geef er zelf daarom de voorkeur aan om alleen niet-POSIX-compliant constructies te gebruiken als het niet anders kan (als het zeer veel performancewinst oplevert bijvoorbeeld). De POSIX regexps zijn door hun eenvoud vaak erg helder en toch krachtig genoeg om de meeste problemen te kunnen oplossen. Daarmee wil ik niet ontkennen dat in zeldzame gevallen Perl regexps handige extra functionaliteit bieden en als portability niet van (groot) belang is, moet je ze zeker gebruiken.

[drm]

* drm shouts
Perl Regex de nieuwe standaard!

Ik hou persoonlijk helemaal niet van posix regexen, simpelweg om dat de pcre in PHP net ff wat meer te bieden heeft

[tomato]

Soultaker: De meeste modern POSIX regexps doen 't wel onder Perl. Ik zou zelfs willen beweren alle, aangezien ik geen constructie zou kunnen verzinnen die niet werkt, maar dat is natuurlijk geen bewijs.

Perl gebruikt een Traditional NFA regex engine in tegenstelling tot een POSIX NFA engine.
Eigenlijk maakt dit nog niet zo heel veel uit, het zegt eigenlijk alleen maar wat over de manier waarop een match uitgevoerd. Het gevonden resultaat zal in beide gevallen altijd hetzelfde zijn (maar kan anders zijn dan waar een DFA engine mee aan zou komen zetten).
Een Traditional NFA engine is sneller dan een POSIX NFA, omdat een POSIX NFA altijd alle mogelijkheden langsgaat. Een Traditional NFA engine stopt wanneer er een match gevonden is.

Qua functionaliteit zijn er ook POSIX standaarden voor regexen:

* Basic Regular Expressions (BRE's)
* Extended Regular Expressions (ERE's)

Ik ken eigenlijk voor geen van deze standaarden een tool die ze volledig naleeft. Om volledig POSIX compliant te zijn moet een tool een van deze twee standaarden naleven.

Perl is iig geen BRE. In een BRE moeten parentheses bijvoorbeeld escaped worden om als grouping te dienen (dus \(...\) ipv (...) ).
Perl komt redelijk in de buurt van een ERE. Overigens komen in de ERE standaard geen backreferences voor ($0, $1, $2, etc), dus wil je POSIX compliant zijn gebruik je deze ook niet (in een BRE zijn ze overigens weer wel opgenomen .

Verder hebben we de POSIX locale. Dit heeft te maken met taal conventies, interpretatie van karakters in een bepaalde encoding, etc.
Denk bijvoorbeeld aan de 'letter' é die veel programma's niet als letter zouden beschouwen (valt buiten de ASCII range). Maar in Latin-1 encoding zou het wel als 'letter' geinterpreteerd moeten worden.
Een ander voorbeeld is \w (volgens de POSIX locale mogen hier alle karakters onder vallen die gedefinieerd zijn als letter of cijfer in de huidige locale, dus niet alleen ASCII letters en cijfers).

Ook al biedt een tool niet vanuit zichzelf locale support, dit kan (deels) nog bereikt worden door te compileren met een POSIX compliant C library (maar dat is dan eigenlijk maar toevallig).

Perl werkt bijvoorbeeld wel volgens de POSIX locale mbt \w en case-insensitive matches, maar perl's . (dot) en character class ranges niet.

Het idee van POSIX is juist dat regexps wel portable worden.

Dat is waar en dat is ook een mooi streven. Maar wat dat betreft is POSIX (iig mbt regex standaarden) IMHO behoorlijk mislukt. Er zijn veel tools dit ideeen uit POSIX overgenomen hebben, maar er zijn er erg weinig volledig POSIX compliant.

[Soultaker]

Op maandag 25 maart 2002 16:42 schreef tomato het volgende:
Perl gebruikt een Traditional NFA regex engine in tegenstelling tot een POSIX NFA engine.
Eigenlijk maakt dit nog niet zo heel veel uit, het zegt eigenlijk alleen maar wat over de manier waarop een match uitgevoerd. Het gevonden resultaat zal in beide gevallen altijd hetzelfde zijn (maar kan anders zijn dan waar een DFA engine mee aan zou komen zetten).
Een Traditional NFA engine is sneller dan een POSIX NFA, omdat een POSIX NFA altijd alle mogelijkheden langsgaat. Een Traditional NFA engine stopt wanneer er een match gevonden is.

Voor zover ik begrepen had legt de POSIX specificatie over regular expressions niet vast op welke manier die regular expressions uitgevoerd zouden moeten worden. Ik begrijp je betoog over POSIX/Traditional NFA's dan ook niet helemaal. Wat zijn de verschillen en waarom zou een POSIX-compliant regexp niet met een 'Traditional NFA' geparsed kunnen worden?

Verder snap ik niet waarom een NFA niet dezelfde resultaten op zou leveren als een equivalente DFA. Elke NFA is immers om te vormen tot een DFA. Het leek me zelf ook logisch om uitsluitend met DFA's te werken, in verband met de veel efficientere executie ten koste van een klein beetje geheugenruimte. Volgens jou gebeurd dat echter niet; wat is de reden daarvoor?

Perl komt redelijk in de buurt van een ERE. Overigens komen in de ERE standaard geen backreferences voor ($0, $1, $2, etc), dus wil je POSIX compliant zijn gebruik je deze ook niet (in een BRE zijn ze overigens weer wel opgenomen .

In de modern/extended regexps zijn backreferences afgeschaft omdat ze ambigue zouden zijn (hoewel dat met wat extra specificaties natuurlijk wel te verhelpen is) maar vooral ook omdat ze eigenlijk niet efficient te implementeren zijn. Dat ze wel bij basic regexps horen komt omdat deze gebaseerd zijn op de traditionele werking van regexps, zoals die er was voordat de ISO standaard bestond. Deze vorm wordt niet voor niets ook wel 'obsolete regular expression' genoemd.

Mijn punt was trouwens dat moderne POSIX regexps (waarschijnlijk) goed door Perl verwerkt worden en niet dat alle in Perl mogelijke regexps POSIX-compliant zijn (wat niet zo is, aangezien Perl veel meer functionaliteit biedt).

Verder hebben we de POSIX locale.

Inderdaad en nog wel tientallen andere POSIX standaarden, maar daar hadden we 't nu niet over.

[tomato]

Soultaker: Voor zover ik begrepen had legt de POSIX specificatie over regular expressions niet vast op welke manier die regular expressions uitgevoerd zouden moeten worden. Ik begrijp je betoog over POSIX/Traditional NFA's dan ook niet helemaal. Wat zijn de verschillen en waarom zou een POSIX-compliant regexp niet met een 'Traditional NFA' geparsed kunnen worden?

Sorry, in mijn tekst zat een fout. Traditional NFA's en POSIX NFA's kunnen verschillende resultaten geven. Een DFA geeft hetzelfde resultaat als een POSIX NFA.

De POSIX standaard zegt dat wanneer er meerder mogelijke matches zijn de eerste (meest linker) genomen moet worden. Wanneer er meerdere matches mogelijk zijn op die positie moet de langste van die matches genomen worden.

Dit betekent dat wanneer er een match gevonden is, er doorgezocht moet worden tot alle mogelijke matches gevonden zijn. Uit deze mogelijkheden zoeken we dan de langste en die verkiezen we tot winnaar.

Een Traditional NFA daarentegen kent alleen de 'leftmost' regel. Hij zal dus de eerste match pakken. Quantifiers zijn wel greedy, dus in veel gevallen zul je geen verschil merken:

code:

'dit is een string, dit niet' =~ /dit (is)?/

De eerste 'dit' zal gevonden worden en omdat quantifiers (?) greedy zijn zal 'is' ook meegenomen worden in de match.

Leftmost gaat voor longest, dus in dit geval:

code:

'dit is een string, dit niet' =~ /dit (niet)?/

zal 'dit ' gematched worden (de eerste 'dit') en verder niets.


Wanneer zien we het verschil tussen een POSIX NFA en een Traditional NFA? Er is gemakkelijk een voorbeeldje te verzinnen:

code:

'ikloopniet' =~ /ik(loop)?(loopniet)?/

Een Traditional NFA matcht 'ikloop', het is de leftmost match en de quantifier is greedy. Een POSIX NFA is nog niet tevreden en zoekt verder. Uiteindelijk zal hij 'ikloopniet' matchen, hier zien we dus een belangrijk verschil!

Op deze manier kun je gemakkelijk testen of je met een POSIX of Traditional NFA te doen hebt.


Ik ken vrijwel geen tools met een POSIX NFA (lex, mawk en er schijnt een POSIX NFA implementatie van GNU Emacs te zijn).


Een DFA is weer een ander verhaal. Een DFA engine is erg snel, maar doordat hij fundamenteel anders werkt is hij in veel gevallen niet nuttig. Na een match kan er geen informatie over de match aanwezig zijn (waar er gematched is, inhoud van parentheses), hierdoor zijn ook backreferences niet mogelijk. Verder is bijvoorbeeld lookahead niet mogelijk, of een non-greedy quantifier.

Een DFA kan wel goed gebruikt worden om heel snel te zien of er een match is. Als er dan een match is, wordt de NFA ingezet om er verder dingen mee te doen. Van deze methode maken enkele tools gebruik.

Het leek me zelf ook logisch om uitsluitend met DFA's te werken, in verband met de veel efficientere executie ten koste van een klein beetje geheugenruimte. Volgens jou gebeurd dat echter niet; wat is de reden daarvoor?

Ah, dat moet nu duidelijk zijn

Mijn punt was trouwens dat moderne POSIX regexps (waarschijnlijk) goed door Perl verwerkt worden en niet dat alle in Perl mogelijke regexps POSIX-compliant zijn (wat niet zo is, aangezien Perl veel meer functionaliteit biedt).

Ze zullen het zeker doen, maar zoals je ziet kun je dus voor verrassingen komen te staan.

Inderdaad en nog wel tientallen andere POSIX standaarden, maar daar hadden we 't nu niet over.

Daar hadden we het juist wel over

POSIX locale lijkt me juist voor regexen een erg belangrijke standaard. Voldoet een DFA of POSIX NFA (DFA is per definitie POSIX) niet aan de POSIX locale, dan is ie niet POSIX compliant. Regexen is all about text, localisation lijkt me daar een niet al te triviaal punt.

[Soultaker]

Op maandag 25 maart 2002 18:44 schreef tomato het volgende:
Sorry, in mijn tekst zat een fout. Traditional NFA's en POSIX NFA's kunnen verschillende resultaten geven. Een DFA geeft hetzelfde resultaat als een POSIX NFA.

De POSIX standaard zegt dat wanneer er meerder mogelijke matches zijn de eerste (meest linker) genomen moet worden. Wanneer er meerdere matches mogelijk zijn op die positie moet de langste van die matches genomen worden.

Dat is inderdaad een verschil, wat zijn effect heeft op de NFA die gegenereert wordt, maar het ik begrijp nog steeds niet waarom een 'Traditional NFA' niet naar een DFA zou kunnen worden omgezet (met dus het bijbehorende gedrag), hoewel ik wel inzie dat het dan moelijker is om interne informatie (zoals welke tekst door welk stukje uit de regexp wordt gematched) te behouden. Meer in zijn algemeenheid begrijp ik niet wat nu het verschil is tussen een 'Traditional NFA' en een 'POSIX NFA'. Ik begrijp dat als er verschillende voorwaarden worden gegeven voor het matchen, er verschillende NFA's gegenereerd worden. In mijn belevingswereld is een NFA echter niets anders dan een transitiefunctie die gedefinieerd is op een aantal staten waarin de parser kan verkeren.

Tenslotte ben ik het niet met je eens dat regular expressions ook maar iets met 'tekst' of 'locale' te maken hebben. Een reguliere expressie matched een reeks symbolen. Of dat integers, ASCII karakters, Japanse tekens of nog wat anders zijn lijkt me voor de implementatie en werking van de parsing engine absoluut niet relevant.

Buiten dat, bedankt voor je inzichtvolle reactie. Veel van geleerd, dat gebeurd niet zo vaak hier!

[tomato]

Soultaker: Dat is inderdaad een verschil, wat zijn effect heeft op de NFA die gegenereert wordt, maar het ik begrijp nog steeds niet waarom een 'Traditional NFA' niet naar een DFA zou kunnen worden omgezet (met dus het bijbehorende gedrag), hoewel ik wel inzie dat het dan moelijker is om interne informatie (zoals welke tekst door welk stukje uit de regexp wordt gematched) te behouden.

Over de exacte werking van een DFA weet ik niet genoeg (ik heb het ooit gelezen en begrepen, maar ik kan het je hier niet in detail uitleggen). Misschien dat iemand met wat meer theoretische kennis van eindige en oneindige automaten hier beter kan uitleggen waarom een DFA dezelfde match vindt als een POSIX NFA?
Je hebt overigens gelijk dat in theorie een echte DFA altijd hetzelfde zou moeten doen als een echte NFA. Wiskundig gezien is de naam NFA voor de NFA regex engines zoals ze in de praktijk zijn ook niet meer helemaal correct (maar toch blijft men het gewoon zo noemen).

Meer in zijn algemeenheid begrijp ik niet wat nu het verschil is tussen een 'Traditional NFA' en een 'POSIX NFA'. Ik begrijp dat als er verschillende voorwaarden worden gegeven voor het matchen, er verschillende NFA's gegenereerd worden. In mijn belevingswereld is een NFA echter niets anders dan een transitiefunctie die gedefinieerd is op een aantal staten waarin de parser kan verkeren.

Ik weet wel hoe een NFA engine in de praktijk werkt. Hij werkt via de regex, loopt deze dus helemaal af en aan het eind kan er een match of geen match zijn.
Telkens wordt in de string een positie gevonden waar het pattern op past. Wanneer er op een bepaald moment meerdere keuzes gemaakt kunnen worden door de engine wordt deze locatie 'onthouden'. Blijkt nu later dat de regex niet matcht, dan wordt er terug gesprongen naar die locatie in de string en wordt er anders gekozen. Dat is backtracking (maar ik heb eigenlijk het idee dat je dit wel weet ).
Een POSIX NFA blijft backtracken, ook al is er al een match gevonden. Op ieder punt waar keuzes mogelijk zijn, wordt iedere mogelijkheid bekeken.

In de aard van een DFA is het niet relevant over backtracking te spreken. Ieder karakter van de string wordt precies 1 keer bekeken (vandaar ook de D van deterministisch, eindig). Een DFA werkt langs de string (terwijl de NFA langs het pattern werkte).

Tenslotte ben ik het niet met je eens dat regular expressions ook maar iets met 'tekst' of 'locale' te maken hebben. Een reguliere expressie matched een reeks symbolen. Of dat integers, ASCII karakters, Japanse tekens of nog wat anders zijn lijkt me voor de implementatie en werking van de parsing engine absoluut niet relevant.

Hier heb je op zich gelijk in. Maar in de praktijk heb je toch met tekst en locales te maken (ook al heeft de regex engine dat niet). Het is voor jou wel degelijk interessant te weten of een [a-z] character range ook de a-umlaut matcht of niet. In de POSIX standaarden zijn hiervoor regels opgenomen en verschillende tools gaan hier erg verschillend mee om.

Buiten dat, bedankt voor je inzichtvolle reactie. Veel van geleerd, dat gebeurd niet zo vaak hier!

Nouja, ik moet zeggen dat ik er ook even wat documentatie bij moest pakken


Als je overigens echt meer wilt weten over de theorie achter regexen schijn je The Dragon Book (hoofdstuk 3) te moeten hebben:

Compilers - Principles, Techniques, and Tools - Aho, Sethi, and Ullman, 1986

[Soultaker]

Op dinsdag 26 maart 2002 00:03 schreef tomato het volgende:
Over de exacte werking van een DFA weet ik niet genoeg (ik heb het ooit gelezen en begrepen, maar ik kan het je hier niet in detail uitleggen).
Misschien dat iemand met wat meer theoretische kennis van eindige en oneindige automaten hier beter kan uitleggen waarom een DFA dezelfde match vindt als een POSIX NFA?

Ik ben wel bekend met de theorie van de eindige automaten. Ik kan het je dan ook wel precies uitleggen, als je de wilt, maar misschien dat je het liever zelf opzoekt (komt anders zo belerend over en scheelt mij een hoop werk).

Ik had uit de context al begrepen dat jij het over de praktische implementatie van NFA/DFA's had, vandaar dat ik me afvroeg wat het verschil hierin was met de theoretische werking.

Over de werking van NFA/DFA's laat je trouwens wat steken vallen. Zowel een NFA als een DFA parsed elk invoersymbool slechts eenmaal. Het verschil tussen een NFA en een DFA is alleen, dat een NFA zich tegelijkertijd in meerdere toestanden kan bevinden. Bij het parsen van de regexp '(aap|auto)' zal, na het invoersymbool 'a', een NFA naar zowel het begin van 'aap' als het begin van 'auto' willen verwijzen. Non-determinisme betekend dan ook eigenlijk weinig meer dan 'geen keuzes kunnen maken'. Een DFA schrijft een dergelijke regexp in principe om naar 'a(ap|uto)', waardoor bij elk invoersymbool een enkele beslissing genomen kan worden en het algoritme dus deterministisch is (op eenduidige wijze keuzen kan maken).

Omdat een NFA zich normaliter dus in meerdere toestanden kan bevinden, moeten bij het parsen ook meerdere toestanden worden bijgewerkt, waarbij toestanden die niet meer mogelijk zijn (het parsen van 'u' na 'a' zorgt ervoor dat alleen de tweede toestand ('auto') nog mogelijk is en de eerste afvalt) weer verlaten worden. Dit heeft eigenlijk niets met backtracken te maken, aangezien er geen verschillende mogelijkheden afgetast worden. De NFA zal niet eerst proberen 'aap' te matchen en als dat niet lukt 'auto' (of andersom, omdat 'auto' langer is) maar bevind zich simpelweg in beide toestanden tot een van de twee afvalt. Als er in plaats van 'aap' een belachelijk lang alternatief stond, zou het algoritme nog steeds na een aantal iteratieslagen dat gelijk is aan de lengte van de invoer klaar zijn.

Een NFA is echter wel minder efficient, omdat het mogelijk is dat meer dan één toestand bijgewerkt moet worden. Een DFA heeft in elke toestand slechts één mogelijke weg en zal dus altijd in precies één toestand blijven (tot het parsen mislukt, wat in principe als transitie naar een fout-toestand kan worden gezien). Hierdoor zal een DFA minder stappen hoeven ondernemen. Een DFA heeft in de regel weliswaar meer toestanden dan een equivalente NFA, maar hij bezoekt bij het verwerken van invoer maximaal evenveel toestanden als de lengte van de invoer, omdat elk invoersymbool een transitie tot gevolg heeft.

Zoals ik al heb laten zien zijn NFA's te transformeren naar DFA's. Dit is ALTIJD mogelijk. In principe biedt een NFA dus niet meer of andere functionaliteit dan DFA's. Ik kan me echter voorstellen dat het lastig (maar niet onmogelijk) is om een NFA die extra informatie zoals welke delen gematched worden om te zetten naar een DFA.

Een POSIX NFA blijft backtracken, ook al is er al een match gevonden. Op ieder punt waar keuzes mogelijk zijn, wordt iedere mogelijkheid bekeken.

Dat is niet helemaal waar. Ik heb het nog niet voor mezelf kunnen bewijzen, maar ik heb het vermoeden dat de POSIX eis dat de match in totaal zo lang mogelijk moet zijn (en elk van de onderdelen van die match, bij twijfel, dus ook steeds zo groot mogelijk moeten zijn, te beginnen bij de eerste) wel te bewerkstelligen is door de resultaten in de juiste volgorde op te leveren. Dit is op basis van mijn ervaring met de implementatie van parser door middel van combinators en hogere orde functies. Dit werkt allemaal net wat anders dan NFA's/DFA's. Mijn stelling is tot zover dat als elk parseronderdeel de langste match eerst oplevert (of eerst bekijkt) de eerste match ook degeen is die aan de POSIX-eis voldoet. Sorry dat ik zo vaag ben, maar ik kan 'm zelf nu ook niet beter onderbouwen. Als je hem nu al onderuit weet te halen, kom maar op, dat scheelt me weer een hoop denkwerk.

Maar in de praktijk heb je toch met tekst en locales te maken (ook al heeft de regex engine dat niet). Het is voor jou wel degelijk interessant te weten of een [a-z] character range ook de a-umlaut matcht of niet. In de POSIX standaarden zijn hiervoor regels opgenomen en verschillende tools gaan hier erg verschillend mee om.

Klopt; ik geef je ook geen ongelijk. Ik vind de theoretische basis van reguliere expressies echter al dusdanig ingewikkeld dat ik me liever niet tegelijkrtijd met andere onderwerpen bezig houd.

Als je overigens echt meer wilt weten over de theorie achter regexen schijn je The Dragon Book (hoofdstuk 3) te moeten hebben:
Compilers - Principles, Techniques, and Tools - Aho, Sethi, and Ullman, 1986

Bedankt voor de tip. Ik heb zelf Languages and Machines van Sudkamp liggen, wat een vrij uitgebreide introductie geeft in NFA's, DFA's, reguliere expressies en context-vrije grammatica's. Ook wel een aanrader, hoewel er vooral veel naar de theoretische achtergrond en minder naar implementatiedetails wordt gekeken. Zelf vind ik dat trouwens wel prettig.

[tomato]

Soultaker: Ik ben wel bekend met de theorie van de eindige automaten. Ik kan het je dan ook wel precies uitleggen, als je de wilt, maar misschien dat je het liever zelf opzoekt (komt anders zo belerend over en scheelt mij een hoop werk).

Als ik het wil weten kan ik het opzoeken, laten we het daar bij houden

Ik had uit de context al begrepen dat jij het over de praktische implementatie van NFA/DFA's had, vandaar dat ik me afvroeg wat het verschil hierin was met de theoretische werking.

Ik zit in het eerste jaar Wiskunde aan de TU, daar krijg je dit nog niet . Ik wil eigenlijk volgend jaar Informatica gaan doen, ik vermoed dat ik dan de theorie erachter nog wel krijg.

Ik heb hier wel 'Mastering Regular Expressions' liggen van Jeffrey Friedl (O'Reilly), dit is ook erg op de praktijk gericht. Verder is het ook gewoon lang geleden dat ik het opengeslagen heb (op het gebruik als reference na) .

In MRE wordt nog kort het volgende gezegd over theorie en praktijk van NFA's, ik quote even als je het niet erg vindt:

The true mathematical and computational meaning of "NFA'' is different from what is commonly called an "NFA regex engine.'' In theory, NFA and DFA engines should match exactly the same text and have exactly the same features. In practice, the desire for richer, more expressive regular expressions has caused their semantics to diverge. We'll see several examples later in this chapter, but one right off the top is support for backreferences.

As a programmer, if you have a true (mathematically speaking) NFA regex engine, it is a relatively small task to add support for backreferences. A DFA's engine's design precludes the adding of this support, but an NFA's common implementation makes it trivial. In doing so, you create a more powerful tool, but you also make it decidedly nonregular (mathematically speaking). What does this mean? At most, that you should probably stop calling it an NFA, and start using the phrase "nonregular expressions,'' since that describes (mathematically speaking) the new situation. No one has actually done this, so the name "NFA'' has lingered, even though the implementation is no longer (mathematically speaking) an NFA.

Er wordt wel verder op de werking ingegaan, maar niet echt op de theorie erachter.

Over de werking van NFA/DFA's laat je trouwens wat steken vallen.

Dit was wat er op dit moment nog in mijn hoofd hing van het verhaal. Dankje voor de correcties

Zoals ik al heb laten zien zijn NFA's te transformeren naar DFA's. Dit is ALTIJD mogelijk. In principe biedt een NFA dus niet meer of andere functionaliteit dan DFA's. Ik kan me echter voorstellen dat het lastig (maar niet onmogelijk) is om een NFA die extra informatie zoals welke delen gematched worden om te zetten naar een DFA.

Onder andere op dit punt zit dus inderdaad het probleem.

Dat is niet helemaal waar. Ik heb het nog niet voor mezelf kunnen bewijzen, maar ik heb het vermoeden dat de POSIX eis dat de match in totaal zo lang mogelijk moet zijn (en elk van de onderdelen van die match, bij twijfel, dus ook steeds zo groot mogelijk moeten zijn, te beginnen bij de eerste) wel te bewerkstelligen is door de resultaten in de juiste volgorde op te leveren.
[..]
Mijn stelling is tot zover dat als elk parseronderdeel de langste match eerst oplevert (of eerst bekijkt) de eerste match ook degeen is die aan de POSIX-eis voldoet.

Ik weet niet zeker of ik je nu goed begrijp, maar kijk hier eens naar:

string:

code:

hoi ik ben peter-jan rens

regex:

code:

hoi (ik ben|ik ben peter-jan)( | peter-jan rens)

Volgens POSIX zou de gehele string gematcht moeten worden, dus: 'hoi ', 'ik ben', ' peter-jan rens'.
Als ik jouw stelling goed begrijp zou je eruithalen: 'hoi ', 'ik ben peter-jan', ' '.

Overall dus niet de langste match, maar bij de eerste alternation wel.


Overigens kun je bij dit voorbeeld nog leuk zien dat perl in totaal slechts 'hoi ik ben' matcht, alternation is dus niet greedy.

Ook wel een aanrader, hoewel er vooral veel naar de theoretische achtergrond en minder naar implementatiedetails wordt gekeken. Zelf vind ik dat trouwens wel prettig.

Ik vind het ook interessant, maar je kunt niet voor alles tijd hebben he

[Soultaker]

Op dinsdag 26 maart 2002 01:20 schreef tomato het volgende:
Ik zit in het eerste jaar Wiskunde aan de TU, daar krijg je dit nog niet . Ik wil eigenlijk volgend jaar Informatica gaan doen, ik vermoed dat ik dan de theorie erachter nog wel krijg.

Als je met verzamelingenleer bekend bent is het allemaal erg eenvoudig hoor. Als je je daar zelf een keer in wil verdiepen heb je daar waarschijnlijk niet meer dan een beetje vrije tijd en een geschikt boek nodig.

Ik weet niet zeker of ik je nu goed begrijp, maar kijk hier eens naar:

string:

code:

hoi ik ben peter-jan rens

regex:

code:

hoi (ik ben|ik ben peter-jan)( | peter-jan rens)

Volgens POSIX zou de gehele string gematcht moeten worden, dus: 'hoi ', 'ik ben', ' peter-jan rens'.
Als ik jouw stelling goed begrijp zou je eruithalen: 'hoi ', 'ik ben peter-jan', ' '.

Overall dus niet de langste match, maar bij de eerste alternation wel.

De POSIX standaard zegt hier het volgende over (hoewel dit uit een secundaire bron, 'man 7 re_format' komt):

In the event that an RE could match more than one substring of a given string, the RE matches the one starting earliest in the string. If the RE could match more than one substring starting at that point, it matches the longest.
Subexpressions also match the longest possible substrings, subject to the constraint that the whole match be as long as possible, with subexpressions starting earlier in the RE taking priority over ones starting later. Note that higher-level subexpressions thus take priority over their lower-level component subexpressions.

Hieruit leid ik af, dat in jou voorbeeld de hele string gematched wordt. De overkoepelende expressie moet immers zo groot mogelijk zijn. Als er verschillende indelingen met die lengte mogelijk zijn, moet eerst de meest linkse subexpressie zo groot mogelijk zijn (en als die weer op verschillende manieren kan worden ingedeeld, ..., etc.), vervolgens de op een na meest linkse, etcetera.

Overigens kun je bij dit voorbeeld nog leuk zien dat perl in totaal slechts 'hoi ik ben' matcht, alternation is dus niet greedy.

Dat is inderdaad een opmerkelijk verschil. Hiermee is dus ook gelijk bewezen dat POSIX regexps niet per definitie in Perl werken.

Ik vind het ook interessant, maar je kunt niet voor alles tijd hebben he

Klopt

[tomato]

Soultaker: Als je met verzamelingenleer bekend bent is het allemaal erg eenvoudig hoor. Als je je daar zelf een keer in wil verdiepen heb je daar waarschijnlijk niet meer dan een beetje vrije tijd en een geschikt boek nodig.

Vooral die vrije tijd is dan het probleem

De POSIX standaard zegt hier het volgende over (hoewel dit uit een secundaire bron, 'man 7 re_format' komt):
[..]
Hieruit leid ik af, dat in jou voorbeeld de hele string gematched wordt. De overkoepelende expressie moet immers zo groot mogelijk zijn. Als er verschillende indelingen met die lengte mogelijk zijn, moet eerst de meest linkse subexpressie zo groot mogelijk zijn (en als die weer op verschillende manieren kan worden ingedeeld, ..., etc.), vervolgens de op een na meest linkse, etcetera.

Lijkt mij een correcte uitleg.

Dat is inderdaad een opmerkelijk verschil. Hiermee is dus ook gelijk bewezen dat POSIX regexps niet per definitie in Perl werken.

Maar dat hadden we al eerder gezien

code:

'ikloopniet' =~ /ik(loop)?(loopniet)?/

[Verwijderd]

tomato: Omdat een ? als quantifier (0 of 1 keer) na een '(' over het algemeen onzin is, kan het in die vorm een speciale betekenis hebben.

De ? komt natuurlijk niet na een letterlijke ( maar het begin van een group construct...
Als je een optionele linkerhaak wilde hebben had je wel \(? geschreven.

Maar dat wist jij ook wel.

[Verwijderd]

Soultaker: Voor zowel de leesbaarheid als de efficientie zou ik voor tomato's TWEEDE suggestie (met 't ifje) kiezen.

Als het dan toch om efficientie gaat is dit wat handiger:

code:

if ( /^[^@]+@/ ) {
   if ( /^(?:root|postmaster)@/ ) {
     # don't let them get any mail >:)
   }
}

(Al dan niet met /i modifier in de tweede regex omdat bijvoorbeeld POSTMASTER vaak gewoon bij postmaster uitkomt...)

[Verwijderd]

Soultaker: Het idee van POSIX is juist dat regexps wel portable worden.

Het idee, maar de praktijk niet. Bevale de regex contructies gaat het bijvoorbeeld ook om character representatie en hoe een regex genoteerd wordt (al dan niet in een strikte string context, welke delimiters etc...).
En als je port (van een taal naar een andere taal) werkt dat toch niet via copy-paste... Regexen zijn dan een kleine moeite (of zouden dat moeten zijn: als je een regex niet begrijpt moet je hem niet gebruiken).

[Verwijderd]

tomato en Soultaker schreven complete boeken

tomato: Als je overigens echt meer wilt weten over de theorie achter regexen schijn je The Dragon Book (hoofdstuk 3) te moeten hebben: Compilers - Principles, Techniques, and Tools - Aho, Sethi, and Ullman, 1986

Moeilijk aan te komen naar het schijnt, maar wel een goed boek (als je tegen nogal droge tekst kan).

Soultaker: Ik heb zelf Languages and Machines van Sudkamp liggen. Ook wel een aanrader, hoewel er vooral veel naar de theoretische achtergrond en minder naar implementatiedetails wordt gekeken.

Ook een goed boek, met inderdaad een wat wiskundige insteek ("A statemachine is a quintuple...").

Als je wel meer van implementatie details wilt weten zijn bijvoorbeeld... ehmm... kan niet op de naam komen "Compiler Design" van Wilhem en Maurer (met dank aan Amazon voor het plaatje van de voorkant ivm slechte geheugen ) en "Modern Compiler Design" van Dick Grune wel aanraders.

tomato: Vooral die vrije tijd is dan het probleem

Wasda?

Meer ga ik niet zeggen in dit draadje, andere stijgt het regex-precentage in mijn posts boven de 25.

[Grum]

Arien: met /i modifier in de tweede regex omdat bijvoorbeeld POSTMASTER vaak gewoon bij postmaster uitkomt...)


Eventjes ter bevestiging: email adressen behoren (sommige mailers doen et niet ) case insensitive te zijn, dus de /i is wel degelijk nodig

[chem]

Op donderdag 28 maart 2002 09:18 schreef Arien voor het eerst in weken weer iets

ey, je leeft nog?

[Verwijderd]

Grum: Eventjes ter bevestiging: email adressen behoren (sommige mailers doen et niet ) case insensitive te zijn, dus de /i is wel degelijk nodig

Was er al eens tegen aangelopen met een email-tool die ik adressen ("zoals het hoort") case-insensitive liet behandelen...

chem: ey, je leeft nog?

Check. Posto, ergo sum.