Regex - nettes kleines Tutorial

Ich werds mal genauer ansehen. Bist Du irgendwie mit der Seite 
verbandelt?

Mal ne Frage: kennt jemand ein theoretische Paper/Seite zu regular 
expressions? Ich habe mal aufgeschnappt das regex eigentlich finite 
state machines sind. Dazu wüsste ich gerne mehr. Auch ob es 
grundsätzliche Abschätzungen zur Komplexität (O Notation) gibt.

Dumdi D. schrieb:
> Ich werds mal genauer ansehen. Bist Du irgendwie mit der Seite
> verbandelt?
>
> Mal ne Frage: kennt jemand ein theoretische Paper/Seite zu regular
> expressions? Ich habe mal aufgeschnappt das regex eigentlich finite
> state machines sind. Dazu wüsste ich gerne mehr. Auch ob es
> grundsätzliche Abschätzungen zur Komplexität (O Notation) gibt.

Ja, FSMs können reguläre Ausdrücke "erkennen". Um sich damit weiter zu 
befassen Google doch mal nach formalen Sprachen und Chomsky-Hierarchie.

Dumdi D. schrieb:
> Ich werds mal genauer ansehen. Bist Du irgendwie mit der Seite
> verbandelt?

Nee, überhaupt nicht! Bin selbst erst gestern Abend darüber gestoplert, 
weil ich das für ein aktuelles Projekt brauche.

Bisher waren mir die Tutorials einfach zu umfangreich bzw. nur theorie. 
Hier hat man halt ein schönes Böxchen, mit dem man das gleich 
ausprobieren/experimentieren kann.

> Mal ne Frage: kennt jemand ein theoretische Paper/Seite zu regular
> expressions? Ich habe mal aufgeschnappt das regex eigentlich finite
> state machines sind. Dazu wüsste ich gerne mehr. Auch ob es
> grundsätzliche Abschätzungen zur Komplexität (O Notation) gibt.

Gibt's da nichts auf Wikipedia darüber ???

Dumdi D. schrieb:
> Mal ne Frage: kennt jemand ein theoretische Paper/Seite zu regular
> expressions? Ich habe mal aufgeschnappt das regex eigentlich finite
> state machines sind. Dazu wüsste ich gerne mehr.

Das Stichwort ist "Automatentheorie". Wird gerne mit "Formale Sprachen" 
(Chomsky Hierarchie) zusammengelegt, weil es gut zusammen passt.

Dazu gibts Bücher aus dem Bereich theoretischer Informatik, und mit 
etwas Glück brauchbare Vorlesungsskripte. Standardwerk dürfte das hier 
sein, auf dem Gebrauchtmarkt dürften sich ältere Fassungen aber 
wesentlich billiger finden lassen: 
https://www.amazon.de/Einführung-Automatentheorie-Formale-Sprachen-Komplexität/dp/3827370205

Martin S. schrieb:
> Vielleicht hilft es jemanden :)

Vielen Dank für den Tipp. :)

Nur zur Bestätigung: die vorgeschlagenen Bücher behandeln auch regex(von 
einem theoretischen Standpunkt aus), habe ich ao richtig verstanden?

Dumdi D. schrieb:
> Nur zur Bestätigung: die vorgeschlagenen Bücher behandeln auch regex(von
> einem theoretischen Standpunkt aus), habe ich ao richtig verstanden?

Allein in beiden Titeln steht schon was von Theorie. Denkst du die 
richten sich an Arduino-Nutzer? Das ist alles Stoff der in den Bereich 
"Theoretische Informatik" fällt.

Cyblord -. schrieb:
> Dumdi D. schrieb:
>> Nur zur Bestätigung: die vorgeschlagenen Bücher behandeln auch regex(von
>> einem theoretischen Standpunkt aus), habe ich ao richtig verstanden?
>
> Allein in beiden Titeln steht schon was von Theorie. Denkst du die
> richten sich an Arduino-Nutzer? Das ist alles Stoff der in den Bereich
> "Theoretische Informatik" fällt.

Haha. witzig. Nein, das es theoretisch ist glaube ich. Hätte nur sein 
können, das die Verbindung zu Regex nicht geschlagen wird und nur 
Automatentheorie behandelt.

Dumdi D. schrieb:
> Haha. witzig. Nein, das es theoretisch ist glaube ich. Hätte nur sein
> können, das die Verbindung zu Regex nicht geschlagen wird und nur
> Automatentheorie behandelt.

Es ist gut möglich dass Reguläre Ausdrücke wie sie praktisch z.B. in der 
Programmierung vorkommen nicht explizit behandelt werden. Dafür gibt es 
sicher eigene Bücher. Du fragtest aber auch explizit nach deren 
theoretischen Grundlagen und genau davon handeln diese Bücher. Reguläre 
Ausdrücke welche eine reguläre (sprich typ 3) Sprache beschreiben und 
durch eine FSM erkannt werden können. Genau das macht ja auch eine RegEx 
Library, um einen Match festzustellen. Es erzeugt eine FSM aus dem 
regulären Ausdruck und jagt die Eingabe da durch.

Cyblord -. schrieb:
> Es erzeugt eine FSM aus dem
> regulären Ausdruck

Genau dieser Schritt interessiert mich. Oder ist das irgendwie 
offensichtlich wie das funktioniert?

Dumdi D. schrieb:
> Oder ist das irgendwie offensichtlich wie das funktioniert?

Es gibt ja nun wahrlich genügend öffentliche Implementierungen für
reguläre Ausdrücke inzwischen, beginnend von den UNIX-Originalen bis
hin zu erweiterten regulären Ausdrücken, wie sie heute üblich sind –
ihrer Herkunft nach oft als "Perl compatible REs" (pcre) bezeichnet.

Jörg W. schrieb:
> Es gibt ja nun wahrlich genügend öffentliche Implementierungen für
> reguläre Ausdrücke inzwischen, beginnend von den UNIX-Originalen bis
> hin zu erweiterten regulären Ausdrücken, wie sie heute üblich sind –
> ihrer Herkunft nach oft als "Perl compatible REs" (pcre) bezeichnet.

Danke für den Hinweis, hätte ja sein können, das jemand mal 
aufgeschrieben hat wie man das im Prinzip macht und nicht das man sich 
das aus Code zusammensuchen muss.

Hier steht z.B. wie das geht:

RegEx - > NFA -> DFA -> FSM

https://www.gamedev.net/resources/_/technical/general-programming/finite-state-machines-and-regular-expressions-r3176

Cyblord -. schrieb:
> Hier steht z.B. wie das geht:
>
> RegEx - > NFA -> DFA -> FSM
>
> 
https://www.gamedev.net/resources/_/technical/general-programming/finite-state-machines-and-regular-expressions-r3176

Super. Danke. Ich habe dank eurer Stichworte auch noch das folgende 
gefunden (falls irgendjemand anderes dieselbe Frage hat)
https://swtch.com/~rsc/regexp/regexp1.html

Wer noch was weiterführendes sucht:

Hier ein toller Online-Editor: https://regex101.com/

Am Anfang etwas unübersichtlich, aber der Informationsgehalt ist enorm. 
Auch zum "debuggen" gut geeignet.

Und hier noch ein Tutorial: 
https://danielfett.de/de/tutorials/tutorial-regulare-ausdrucke/

Ist teilweise sehr prosaisch, und leider nicht interaktiv, aber dann 
doch interessant, weil auch die "positive lookahead / lookbehind" 
erklärt werden.