Regex parsen

Hallo,

habe mal eine schwierigere Frage. Mich würde mal generell interessieren,
wie reguläre Ausdrücke überhaupt in einer Zeichenkette auf Vorkommen
überprüft werden können?

Wenn ich beispielsweise etwas der Form /[a-f]*t/ habe, wie wird denn
intern bei einer Zeichenkette überprüft, ob es hier ein Matching gibt
oder nicht? Wie geht Perl bzw. jedes andere Tool hier vor? Wird hier
linear durch die Zeichenkette gewandert und jedes Mal überprüft, ob der
Ausdruck überhaupt noch vorkommen kann?

Re: Regex parsen

Mike Wesling wrote:

> Hallo,
>
> habe mal eine schwierigere Frage. Mich würde mal generell interessieren,
> wie reguläre Ausdrücke überhaupt in einer Zeichenkette auf Vorkommen
> überprüft werden können?
>
> Wenn ich beispielsweise etwas der Form /[a-f]*t/ habe, wie wird denn
> intern bei einer Zeichenkette überprüft, ob es hier ein Matching gibt
> oder nicht? Wie geht Perl bzw. jedes andere Tool hier vor? Wird hier
> linear durch die Zeichenkette gewandert und jedes Mal überprüft, ob der
> Ausdruck überhaupt noch vorkommen kann?

Perl macht das vielleicht anders (Perl-Regexe gehen ja auch über normale
reguläre Ausdrücke hinaus...), aber normalerweise nimmt man dafür einen
Endlichen Automaten, der nur den regulären Ausdruck als Eingabe akzeptiert.

Ferdinand

--
Against such abominations, we organize our defenses on the
principle that one strong and able mind can shield the many.
-- Spartan Battle Manual

Re: Regex parsen

Mike Wesling schrieb:
> Hallo,
>
> habe mal eine schwierigere Frage. Mich würde mal generell interessieren,
> wie reguläre Ausdrücke überhaupt in einer Zeichenkette auf Vorkommen
> überprüft werden können?
>
> Wenn ich beispielsweise etwas der Form /[a-f]*t/ habe, wie wird denn
> intern bei einer Zeichenkette überprüft, ob es hier ein Matching gibt
> oder nicht? Wie geht Perl bzw. jedes andere Tool hier vor? Wird hier
> linear durch die Zeichenkette gewandert und jedes Mal überprüft, ob der
> Ausdruck überhaupt noch vorkommen kann?

Mit dem Modul re ( siehe perldoc re ) kannst du der Regexengine zuschauen.

Zum Beispiel so:
perl -mre=debug -e "$_ = 'Just another Hacker'; $\ = qq'\n'; s{\s(H.+$)}
{ Perl \1} and print"

Grüße,

Andreas Pürzer

--
Have Fun,
and if you can't have fun,
have someone else's fun.
The Beautiful South

Re: Regex parsen

* Andreas Pürzer [2006-07-07]:

Hallo Andreas,

schönes Beispiel, nur ein Kommentar am Rande.

> Zum Beispiel so:
> perl -mre=debug -e "$_ = 'Just another Hacker'; $\ = qq'\n'; s{\s(H.+$)}{ Perl \1} and print"

Statt den output record separator zu setzen würde ich in so einem Fall
eher zum -l switch greifen:

perl -lmre=debug -e "$_ = 'Just another Hacker'; s{\s(H.+$)}{ Perl \1} and print"

Bei den meisten Shells bietet es sich außerdem an single (statt double)
ticks zu verwenden, sonst werden da Dinge wie »$_« schon vor dem
Perl-Aufruf interpoliert.

Gruß
Christian

--
Wer gegen ein Minimum Aluminium immun ist,
besitzt Aluminiummimimumimmunität
http://www.lackas.net/ Perl Delphi Linux MP3 Searchengines Domainchecker

Re: Regex parsen

Christian Lackas schrieb:

> * Andreas Pürzer [2006-07-07]:
>
> Hallo Andreas,
>
> schönes Beispiel, nur ein Kommentar am Rande.
>
>
>>Zum Beispiel so:
>>perl -mre=debug -e "$_ = 'Just another Hacker'; $\ = qq'\n'; s{\s(H.+$)}{ Perl \1} and print"
>
>
> Statt den output record separator zu setzen würde ich in so einem Fall
> eher zum -l switch greifen:
>
> perl -lmre=debug -e "$_ = 'Just another Hacker'; s{\s(H.+$)}{ Perl \1} and print"
>

Danke für den Hinweis, sehr viel schöner als $\ per Hand zu setzen.
Den -l switch hatte ich aus irgendeinem Grund nur mit $/ in Verbindung
gebracht und deswegen ( zu Unrecht wie sich jetzt herausstellt ) ignoriert.

> Bei den meisten Shells bietet es sich außerdem an single (statt double)
> ticks zu verwenden, sonst werden da Dinge wie »$_« schon vor dem
> Perl-Aufruf interpoliert.
>

Ja, wenn man mit ner richtigen Shell arbeitet ist ' sinniger, aber meine
cmd.exe hier mag sie nicht:

D:\Temp>perl -e 'print "yeah"'
Can't find string terminator "'" anywhere before EOF at -e line 1.

D:\Temp>perl -e ' print qq~yeah\n~'
Can't find string terminator "'" anywhere before EOF at -e line 1.

Nur deswegen auch das qq'' Konstrukt in meinem Beispiel um folgenden
Späßen zu entgehen:

D:\Temp>perl -e "print qq'yeah'; print "yeah" "
yeah

Das " vor dem zweiten yeah ist für cmd.exe schon der string terminator!
Genauso hier: (gar kein yeah mehr)

D:\Temp>perl -e "print "yeah" "

Lustigerweise fällt mir gerade auf daß es wie erwartet funktioniert,
wenn man die beiden yeah's erst verkettet:

D:\Temp>perl -e "print qq'yeah' , "yeah" "
yeahyeah
D:\Temp>perl -e "print qq'yeah' . "yeah" "
yeahyeah
D:\Temp>perl -e "print "yeah" . "yeah" "
yeahyeah

Aber halt leider auch nicht immer:

D:\Temp>perl -e "print "yeah" , "yeah" "
No comma allowed after filehandle at -e line 1.

Zum Abschluß dieses kleinen Quoting-Exkurses möchte ich noch
perlwin32.pod und perlfaq3.pod zitieren:

perlwin32
Using perl from the command line
If you are accustomed to using perl from various command-line shells
found in UNIX environments, you will be less than pleased with what
Windows offers by way of a command shell.

perlfaq3
Why don't Perl one-liners work on my DOS/Mac/VMS system?
The problem is usually that the command interpreters on those systems
have rather different ideas about quoting than the Unix shells under
which the one-liners were created. On some systems, you may have to
change single-quotes to double ones, which you must *NOT* do on Unix
or Plan9 systems. You might also have to change a single % to a %%.
....
Using qq(), q(), and qx(), instead of "double quotes", 'single quotes',
and `backticks`, may make one-liners easier to write.

There is no general solution to all of this. It is a mess.

> Gruß
> Christian
>

Gruß,

Andi

--
Have Fun,
and if you can't have fun,
have someone else's fun.
The Beautiful South

Re: Regex parsen

Ferdinand Ihringer schrieb:

>> habe mal eine schwierigere Frage. Mich würde mal generell interessieren,
>> wie reguläre Ausdrücke überhaupt in einer Zeichenkette auf Vorkommen
>> überprüft werden können?
>>
>> Wenn ich beispielsweise etwas der Form /[a-f]*t/ habe, wie wird denn
>> intern bei einer Zeichenkette überprüft, ob es hier ein Matching gibt
>> oder nicht? Wie geht Perl bzw. jedes andere Tool hier vor? Wird hier
>> linear durch die Zeichenkette gewandert und jedes Mal überprüft, ob der
>> Ausdruck überhaupt noch vorkommen kann?
>
> Perl macht das vielleicht anders (Perl-Regexe gehen ja auch über normale
> reguläre Ausdrücke hinaus...), aber normalerweise nimmt man dafür einen
> Endlichen Automaten, der nur den regulären Ausdruck als Eingabe akzeptiert.

Das ist mir etwas zu allgemein. Bedeutet das, dass der reguläre Ausdruck
in Zustände eines Automaten umgesetzt wird und dann nacheinander jedes
einzelne Zeichen aus dem zu parsenden Text in den automaten gestopft
wird? Irgendwie verstehe ich nicht ganz, wie man sowas effizient
programmieren kann...

Re: Regex parsen

Mike Wesling wrote:

> Hallo,
>
> habe mal eine schwierigere Frage. Mich würde mal generell interessieren,
> wie reguläre Ausdrücke überhaupt in einer Zeichenkette auf Vorkommen
> überprüft werden können?
>
> Wenn ich beispielsweise etwas der Form /[a-f]*t/ habe, wie wird denn
> intern bei einer Zeichenkette überprüft, ob es hier ein Matching gibt
> oder nicht? Wie geht Perl bzw. jedes andere Tool hier vor? Wird hier
> linear durch die Zeichenkette gewandert und jedes Mal überprüft, ob der
> Ausdruck überhaupt noch vorkommen kann?

Dem regex-coach ( http://weitz.de/regex-coach ) kann man, wenn man will,
sehr schoen beim Abarbeiten der Regex zuschauen.
Kann ich - immer wieder, sorry - nur empfehlen...

Jogi

--
The particular mistake will not be repeated. There are plenty of
mistakes left that have not yet been used. A. Tanenbaum
JogiKue@kuenstner.de

Re: Regex parsen

* Andreas Pürzer [2006-07-08]:

Hallo Andreas,

> Lustigerweise fällt mir gerade auf daß es wie erwartet funktioniert,
> wenn man die beiden yeah's erst verkettet:
> D:\Temp>perl -e "print qq'yeah' , "yeah" "
> yeahyeah

das liegt daran, weil du dann hier mit bareword arbeitest. Obige Zeile
ist äquivalent zu

D:\Temp>perl -e "print qq'yeah', yeah"

Ohne 'strict' schluckt Perl ja auch sowas. Ein bareword direkt hinter
dem print wird dann aber (wie du ja gezeigt hast) auch schonmal als
Filehandle statt als Zeichenkette interpretiert...

Gruß
Christian

p..s

> There is no general solution to all of this. It is a mess.

Es soll auch für Windows richtige Shells geben :-)

--
Opposition ist die Kunst, so geschickt dagegen zu sein, daß man später
dafür sein kann.
(Charles-Maurice de Talleyrand-Perigord, frz. Staatsmann, 1754-1838)
http://www.lackas.net/ Perl Delphi Linux MP3 Searchengines Domainchecker

Re: Regex parsen

Mike Wesling wrote:

> Ferdinand Ihringer schrieb:
>
>>> habe mal eine schwierigere Frage. Mich würde mal generell interessieren,
>>> wie reguläre Ausdrücke überhaupt in einer Zeichenkette auf Vorkommen
>>> überprüft werden können?
>>>
>>> Wenn ich beispielsweise etwas der Form /[a-f]*t/ habe, wie wird denn
>>> intern bei einer Zeichenkette überprüft, ob es hier ein Matching gibt
>>> oder nicht? Wie geht Perl bzw. jedes andere Tool hier vor? Wird hier
>>> linear durch die Zeichenkette gewandert und jedes Mal überprüft, ob der
>>> Ausdruck überhaupt noch vorkommen kann?
>>
>> Perl macht das vielleicht anders (Perl-Regexe gehen ja auch über normale
>> reguläre Ausdrücke hinaus...), aber normalerweise nimmt man dafür einen
>> Endlichen Automaten, der nur den regulären Ausdruck als Eingabe
>> akzeptiert.
>
> Das ist mir etwas zu allgemein. Bedeutet das, dass der reguläre Ausdruck
> in Zustände eines Automaten umgesetzt wird und dann nacheinander jedes
> einzelne Zeichen aus dem zu parsenden Text in den automaten gestopft
> wird? Irgendwie verstehe ich nicht ganz, wie man sowas effizient
> programmieren kann...

Ja, so meine ich das. Auf die Schnelle fand ich
http://www.lrz-muenchen.de/services/schulung/unterlagen/regu l/regul-12.html#beisp3th

Ferdinand

--
The sooner our happiness together begins, the longer it will last.
-- Miramanee, "The Paradise Syndrome", stardate 4842.6

Re: Regex parsen

Christian Lackas schrieb:
> * Andreas Pürzer [2006-07-08]:
>
> Hallo Andreas,
>

Hallo Christian,

>
>>There is no general solution to all of this. It is a mess.
>
>
> Es soll auch für Windows richtige Shells geben :-)
>

Man beachte den Konjunktiv! ;->

Sowas wie das hier:
http://www.microsoft.com/germany/technet/scriptcenter/hubs/m sh.mspx
?

Ne, im Ernst, wenn man sich mal an die Eigenheiten gewöhnt hat ( sprich
alle " durch ' und vice versa ersetzen, und exzessiven Einsatz der
quote-like-operatoren ), dann ist auch mit cmd.exe einiges anzustellen.
Das einzige was mich wirklich immer wieder nervt, ist daß ein Enter die
Befahlszeile abschließt und ich nicht wie gewohnt in einer
augenfreundlichen Weise über mehrere Zeilen gehen kann...


Lieber Herr Knopper, vielen Dank für Ihre CD's/DVD's!!!

Jetzt wird's aber endgültig OT...

Gruß,
Andreas

--
Have Fun,
and if you can't have fun,
have someone else's fun.
The Beautiful South

Re: Regex parsen

Mike Wesling schrieb:

> Ferdinand Ihringer schrieb:
>
>>> habe mal eine schwierigere Frage. Mich würde mal generell interessieren,
>>> wie reguläre Ausdrücke überhaupt in einer Zeichenkette auf Vorkommen
>>> überprüft werden können?
>>>
>>> Wenn ich beispielsweise etwas der Form /[a-f]*t/ habe, wie wird denn
>>> intern bei einer Zeichenkette überprüft, ob es hier ein Matching gibt
>>> oder nicht? Wie geht Perl bzw. jedes andere Tool hier vor? Wird hier
>>> linear durch die Zeichenkette gewandert und jedes Mal überprüft, ob der
>>> Ausdruck überhaupt noch vorkommen kann?
>>
>>
>> Perl macht das vielleicht anders (Perl-Regexe gehen ja auch über normale
>> reguläre Ausdrücke hinaus...), aber normalerweise nimmt man dafür einen
>> Endlichen Automaten, der nur den regulären Ausdruck als Eingabe
>> akzeptiert.
>
>
> Das ist mir etwas zu allgemein. Bedeutet das, dass der reguläre Ausdruck
> in Zustände eines Automaten umgesetzt wird und dann nacheinander jedes
> einzelne Zeichen aus dem zu parsenden Text in den automaten gestopft
> wird? Irgendwie verstehe ich nicht ganz, wie man sowas effizient
> programmieren kann...

Wenn du's wirklich ganz genau wissen willst:
http://www.oreilly.de/catalog/regex2ger/

Gruß,
Andreas

--
Have Fun,
and if you can't have fun,
have someone else's fun.
The Beautiful South

Re: Regex parsen

On Sun, 09 Jul 2006 11:06:00 +0200, Mike Wesling wrote:
> Ferdinand Ihringer schrieb:
>>> habe mal eine schwierigere Frage. Mich würde mal generell interessieren,
>>> wie reguläre Ausdrücke überhaupt in einer Zeichenkette auf Vorkommen
>>> überprüft werden können?
>>>
>>> Wenn ich beispielsweise etwas der Form /[a-f]*t/ habe, wie wird denn
>>> intern bei einer Zeichenkette überprüft, ob es hier ein Matching gibt
>>> oder nicht? Wie geht Perl bzw. jedes andere Tool hier vor? Wird hier
>>> linear durch die Zeichenkette gewandert und jedes Mal überprüft, ob der
>>> Ausdruck überhaupt noch vorkommen kann?
>>
>> Perl macht das vielleicht anders (Perl-Regexe gehen ja auch über normale
>> reguläre Ausdrücke hinaus...), aber normalerweise nimmt man dafür einen
>> Endlichen Automaten, der nur den regulären Ausdruck als Eingabe akzeptiert.
>
> Das ist mir etwas zu allgemein. Bedeutet das, dass der reguläre Ausdruck
> in Zustände eines Automaten umgesetzt wird und dann nacheinander jedes
> einzelne Zeichen aus dem zu parsenden Text in den automaten gestopft
> wird? Irgendwie verstehe ich nicht ganz, wie man sowas effizient
> programmieren kann...

Das ist bei deterministischen endlichen Automaten eigentlich ziemlich
effizient: Pro Zeichen des zu durchsuchenden Strings braucht man nur
einen Table-Lookup, die Match-Zeit ist somit proportional zur Länge des
zu durchsuchenden Strings unabhängig vom Muster. Und jeder
non-deterministische endliche Automat lässt sich in einen äquivalenten
deterministischen umwandeln. Non-deterministische endliche Automaten
kann man natürlich auch direkt implementieren: Wann immer eine Eingabe
zu mehr als einem Folgezustand führt, probiert man diese der Reihe nach
durch, bis einer zum Erfolg führt. Im Prinzip arbeitet man einen
Suchbaum ab.

Perl-Regexes sind keine reinen regulären Ausdrücke: Man kann sie daher
nicht in endliche Automaten (weder deterministische noch
nondeterministische) übersetzen.
Man kann aber die gleiche Programmiertechnik wie bei
nondeterministischen verwenden.

hp

--
_ | Peter J. Holzer | > Wieso sollte man etwas erfinden was nicht
|_|_) | Sysadmin WSR | > ist?
| | | hjp@hjp.at | Was sonst wäre der Sinn des Erfindens?
__/ | http://www.hjp.at/ | -- P. Einstein u. V. Gringmuth in desd