[gelöst] [Programmierung] Parser-Frage

[heisenberg]

Das was mir fehlt sind nicht die Datenfelder, sondern die Datensätze. Aber kann gut sein, dass ich da cdr.log und asterisk.log durcheinanderwerfe.

Ich sehe denn aktuell einen Anruf, mit der Anrufernummer und der Zielrufnummer(Handy), wenn er z. B. darauf weitergeleitet wurde. Aber ich sehe nicht die Telefonnnummer, die der Anrufer gewählt hat(also die Komplettnummer mit Durchwahl bevor weitergeleitet wurde). Aber ich kann ja nochmal prüfen, ob die Info in einem verfügbaren Datenfeld vielleicht möglich ist.

Danke!

[Lord_Carlos]

Ist die erste Zeile einer CSV Datei nicht angegeben welche Felder vorhanden sind?
Koennte das nicht nuetzlich sein beim Parsen. Dann weist du immer genau wie viele Felder vorhanden sind.

[Meillo]

Ich habe mir die Daten nochmal genauer angeschaut:

Code: Alles auswählen

"","+4912349668222","+491234668249","from-provider-customer","""callername"" <+4912345668222>","SIP/provider-customer-00000006","SIP/provider-customer-context-00000007","Dial","SIP/01234567@provider-customer-context,1500,tT","2021-01-07 13:59:56","2021-01-07 14:00:14","2021-01-07 14:00:35",38,20,"ANSWERED","DOCUMENTATION","1610024396. 8",""

Die Regexp passt zwar nicht, aber das Format scheint doch eindeutig zu sein:

- Separator ist das Komma
- Felder sind entweder in Doublequotes eingeschlossen oder nicht
- Wenn Felder in Doublequotes eingeschlossen sind, dann sind die literalen Doublequotes im Feldinhalt verdoppelt

Das ist Standard-CSV und sollte von CSV-Libraries korrekt geparst werden koennen.

(Gestern Abend hatte ich das Escapen (= Verdoppeln) der Doublequotes uebersehen.)


Weil ich gerade Lust darauf hatte, habe ich den Ansatz mal kurz in C runtergeschrieben:
pastebin/?mode=view&s=41238
... nur zur Illustration. Da stecken sicherlich noch Fehler in Randfaellen drin. Meine Lust ist geschwunden, als obige Zeile aus dem Logfile korrekt geparst worden ist. Darum ist es mir letztlich nur gegangen.

Code: Alles auswählen

B-) ./csv-parse <in
Field 01: 
Field 02: +4912349668222
Field 03: +491234668249
Field 04: from-provider-customer
Field 05: "callername" <+4912345668222>
Field 06: SIP/provider-customer-00000006
Field 07: SIP/provider-customer-context-00000007
Field 08: Dial
Field 09: SIP/01234567@provider-customer-context,1500,tT
Field 10: 2021-01-07 13:59:56
Field 11: 2021-01-07 14:00:14
Field 12: 2021-01-07 14:00:35
Field 13: 38
Field 14: 20
Field 15: ANSWERED
Field 16: DOCUMENTATION
Field 17: 1610024396. 8
Field 18: 

[heisenberg]

(Gestern Abend hatte ich das Escapen (= Verdoppeln) der Doublequotes uebersehen.)

Du hast tatsächlich recht. Ich habe da offensichtlich nicht so genau hingeschaut und mir eine andere Erklärung zurechtgebogen. Aber das was Du sagst, ist absolut korrekt. Es ist tatsächlich eine Verdoppelung.

Und nur nochmal vollständigkeitshalber. Ich hatte den Regex für das Feld korrigiert. D. h. ein richtiger Regex war zwar nicht in Gänze aufgeführt, ist aber problemlos möglich.

[Meillo]

D. h. ein richtiger Regex war zwar nicht in Gänze aufgeführt, ist aber problemlos möglich.

Tut mir leid, hier nochmal pedantisch sein zu muessen: Ich denke, dass eine Regexp nicht moeglich ist, weil das Parsingproblem zu komplex ist, um es mit einer regulaeren Grammatik ausdruecken zu koennen. Der Escaping-Mechanismus erfordert State und eine regulaere Sprache hat keinen State. (Die theoretischen Informatiker hier koennen das sicher genauer ausfuehren.)


Beispiel:

Code: Alles auswählen

"foo","bar"",""baz","quux"

Das sind drei Felder, die man mittels Regexp nicht erkennen kann, weil man sie nicht von diesen Records mit jeweils vier Feldern unterscheiden kann:

Code: Alles auswählen

"foo","bar","baz","quux"
"foo","bar""","""baz","quux"

[heisenberg]

Tut mir leid, hier nochmal pedantisch sein zu muessen: Ich denke, dass eine Regexp nicht moeglich ist, weil das Parsingproblem zu komplex ist, um es mit einer regulaeren Grammatik ausdruecken zu koennen. Der Escaping-Mechanismus erfordert State und eine regulaere Sprache hat keinen State. (Die theoretischen Informatiker hier koennen das sicher genauer ausfuehren.)

Ich bin anderer Meinung. Ich denke der Escaping-Mechanismus ist vollkommen irrelevant für einen Regex-Ausdruck, der auf eine Zeile matchen kann oder nicht.

Erklärung

Das ist der Ausdruck für ein Feld:

Code: Alles auswählen

(("(.*)")|(.*))

Ich nenne das jetzt mal f.

Dann wäre der Zeilen Regex-Ausdruck(für eine Zeile mit dynamischer Feldanzahl):

Code: Alles auswählen

^f(,f)+$

Oder komplett ausgeführt:

Code: Alles auswählen

^(("(.*)")|(.*))(,(("(.*)")|(.*)))+$

Der Knackpunkt ist jetzt die Verankerung am Feldanfang und am Feldende. Natürlich können zwischendrin Kommata und Doppelanführungszeichen den Regex theoretisch stören. Der Punkt ist aber, dass sich die Zeichenkette von den Enden her korrekt aufbauen muss und daraus ergibt sich die Eindeutigkeit auch bei egal welchen Inhalten, sofern die bisher festgestellten Konventionen eingehalten werden.

Ich kann da jetzt keine theoretisch klar nachvollziehbare Erklärung für bieten. Es ist im Moment reine Intuition. Ich würde Dich bitten, dass jetzt mal so - unbewiesen und demnach faktisch falsch - stehen zu lassen. (Dass das z. B. bei XML ganz anders ist, das mag so sein.. Auch ist mein Verständnis, wie Regexes-Prozessing tatsächlich durchgeführt wird eher gering. D. h. dass könnte mir auch nochmal vor die Füsse fallen.)

Nächster möglicher Schritt wäre ein Programm, um mit Zufallsdaten diese Vermutung zu testen, dass es tatsächlich so ist. Falls ich damit Erfolg habe, würde ich mich nochmal melden.

[heisenberg]

Hier ist mal ein erster erfolgreicher Test mit einem Testdatenbeispiel von Dir.

Für die tatsächliche Erfassung der Feldinhalte kann ich nur mit fester Feldanzahl arbeiten, da ich auf die Captures bei Wiederholungen mit Perl(und von keiner anderen Sprache, die ich kenne und zumindest ansatzweise nutzen kann. Haskell wäre für so ein Problem vielleicht nochmal interessant) nicht zugreifen kann.

Code: Alles auswählen

#!/usr/bin/perl

$_='"foo","bar""","""baz","quux"';

print "data: $_\n\n";

$f='(("(.*)")|(.*))';

# Muster mit dynamischer Feldanzahl
$re="^$f(,$f)\$";

/$re/;
if($1) { print "regex matched!\n\n"; }

# Wiederholung mit Muster mit fester Feldanzahl, um an die Werte zu kommen
$re_expanded='^(("(?<a1>.*)")|(?<b1>.*)),(("(?<a2>.*)")|(?<b2>.*)),(("(?<a3>.*)")|(?<b3>.*)),(("(?<a4>.*)")|(?<b4>.*))$';

/$re_expanded/;

print("a1: ".$+{a1}."\n");
print("b1: ".$+{b1}."\n");

print("a2: ".$+{a2}."\n");
print("b2: ".$+{b2}."\n");

print("a3: ".$+{a3}."\n");
print("b3: ".$+{b3}."\n");

print("a4: ".$+{a4}."\n");
print("b4: ".$+{b4}."\n");

Ausgabe:

Code: Alles auswählen

data: "foo","bar""","""baz","quux"

regex matched!

a1: foo
b1: 
a2: bar""
b2: 
a3: ""baz
b3: 
a4: quux
b4: 

[Meillo]

Test mal folgende Inputzeile, die ebenfalls vier Felder hat:

Code: Alles auswählen

"foo","bar""","""baz"",""quux","blub"

Korrekte Ausgabe waere:

Feld 1: foo
Feld 2: bar"
Feld 3: "baz","quux
Feld 4: blub


Dein Testcode erzeugt:

Code: Alles auswählen

data: "foo","bar""","""baz"",""quux","blub"

regex matched!

a1: foo","bar""
b1: 
a2: ""baz"
b2: 
a3: "quux
b3: 
a4: blub
b4: 

Das vorhandene oder fehlende Escapen der Doublequotes innerhalb der Feldinhalte koennen wir vernachlaessigen, es geht mir nur um die korrekte Identifikation der Separatoren und damit um die korrekte Feldbildung.


Ich kann das schon so stehen lassen, wenn du es selber rausfinden willst. Ich tue mir nur schwer damit, falsche Aussagen stehen zu lassen. Ich muss nicht erklaeren. Ich kann auch einfach nur Gegenbeispiele liefern und Testdaten, die deine Aussagen widerlegen. Wie man das in der wisschenschaftlichen Herangehensweise halt so macht.

Von mir aus kann das auch gerne jemand anderes tun. Vielleicht sind meine Formulierungen gerade einfach nicht so gluecklich ...

Am liebsten waere es mir, wenn ein theoretischer Informatiker hier sachlich darlegen koennte, warum sich das Problem mittels Regexps nicht loesen laesst. Mein Wissen in Sprachentheorie ist dafuer zu begrenzt und ich kann eben auch nicht mit der Chomsky-Hierarchie argumentieren, weil ich sie nur ungefaehr kenne und die Sprachklassen nicht wirklich erklaeren kann.

Gerne lasse ich mich in meiner Meinung auch widerlegen!


Oder wuenschst du dir einfach mehr Zeit, um selber daran zu arbeiten? Und ich soll nicht so schnell posten?

[heisenberg]

Das läuft gerade schon so, wie ich das gut haben kann: Ich habe eine Idee und sie wird entweder widerlegt oder nicht. Und das Spielchen geht so lange weiter, bis einer keine Lust mehr hat, oder die Erkenntnis steht: Ja, das geht definitiv (nicht)!

Wenn ein theoretischer Informatiker da wäre, ist die Frage ob ich den überhaupt verstehen würde!

Ansonsten: Mein Beispielcode ist auf eine fixe Feldlänge von 4 Feldern festgelegt. Mit 5 Feldern funktioniert der nicht(Anpassung notwendig)! Anpassung auf variable Feldlänge ist möglich, da müsste ich mir den erweiterten Regex allerdings dynamisch zusammenbauen.

Nachtrag

Interessant auch ist die Art des falschen Ergebnisses: Das Ergebnis fasst Feld 1 und Feld 2 zusammen, da es ja nur 4 Felder geben darf und der Feldtrenner zwischen Feld 1 und Feld 2 wird logischerweise als Inhalt gewertet. Der Regex ist logisch nachvollziehbar passend. Folge: Wenn z. B. Feld 1 und Feld n (=letztes Feld) mit Anführungszeichen umschlossen sind, dann könnte die dynamische Erkennung daraus auch ein einziges valides Feld machen(ist ja von Doppelanführungszeichen umschlossen). Erst die Information wie viele Felder im Datensatz vorhanden sind, findet (vermutlich) aus der Lösungsmenge die korrekte Einzellösung heraus.

Nachtrag-2

Ich denke Du hast Recht. An Deinem Beispiel sehe ich, selbst, wenn ich es schon manuell als Mensch mir anschaue, kann ich keine eindeutige, richtige Lösung bestimmen. Anhand des Musters kann es mehrere zutreffende Lösungen geben, die alle derart sind, das einzelne Felder zusammengefasst werden (1+2,2+3,3+4,4+5) und dadurch die Feldzahl auf 4 reduziert wird. Es ist schlicht nicht bestimmbar was die eine richtige Lösung ist. Eine einzig richte Lösung im Kopf algorithmisch zu erreichen, ist aber der erste Schritt, ohne den es keinen 2. geben kann.

Und wahrscheinlich wird das nicht auch der einzige Fehlerfall bleiben. Wenn die Inhalte 1000 mögliche Felder sein könnten, dann gibt es halt wesentlich mehr Falschmöglichkeiten.

[heisenberg]

Zurück zum eigentlichen Problem:

Das war es was mir fehlte:

1. externer Anrufer ruft auf einer Festnetzrufnummer der Firma an
2. Nummer klingelt intern
3. Nummer wird intern nicht abgehoben
4. Nummer wird ggf. auf das Handy vermittelt.
5. Im Log fehlte die ursprünglich angenommene Festnetzrufnummer

Ich habe jetzt im Asterisk Wahlplan eines der Abrechungsfelder(CDR(userfield)) mit der der angerufenen Festnetzrufnummer belegt. Damit habe ich die Information.

[Meillo]

Edit: Ich hatte meinen Post schon zu schreiben angefangen, bevor du deinen letzten Post veroeffentlicht hast. Ich will mit der theoretischen Diskussion deinem konkreten Problem nicht im Weg stehen.

Nachtrag-2

Ich denke Du hast Recht. An Deinem Beispiel sehe ich, selbst, wenn ich es schon manuell als Mensch mir anschaue, kann ich keine eindeutige, richtige Lösung bestimmen. Anhand des Musters kann es mehrere zutreffende Lösungen geben, die alle derart sind, das einzelne Felder zusammengefasst werden (1+2,2+3,3+4,4+5) und dadurch die Feldzahl auf 4 reduziert wird. Es ist schlicht nicht bestimmbar was die eine richtige Lösung ist. Eine einzig richte Lösung im Kopf algorithmisch zu erreichen, ist aber der erste Schritt, ohne den es keinen 2. geben kann.

Hmm, ich sehe schon eine einzige korrekte Loesung, die man erreicht, wenn man den Weg nimmt, den ich ihn einem vorigen Post beschrieben und testweise in C implementiert habe. (Vgl. https://tools.ietf.org/html/rfc4180 )


Dieser CSV-String:

Code: Alles auswählen

"foo","bar""","""baz"",""quux","blub"

... ist strukturell identisch zu diesem Shell-String:

Code: Alles auswählen

"foo" "bar\"" "\"baz\" \"quux" "blub"

Es ist eindeutig, dass `baz' und `quux' das gleiche Feld sein muessen. Da gibt es keine Wahlfreiheit.

(Die Unentscheidbarkeit kommt nur dann ins Spiel, wenn man nicht weiss, welches CSV-Format es ist.)



Andererseits hast du doch recht, dass CSV grundsaetzlich mit einer Regexp geparst werden kann (solange man ignoriert, dass alle Zeilen gleich viele Felder haben muessen).

Siehe dazu:

https://stackoverflow.com/questions/245 ... ee-grammar
https://softwareengineering.stackexchan ... by-a-regex

Es ist etwas schwierig in den verschiedenen Antworten wirklich durchzublicken, aber escapte Quotes scheinen jedenfalls kein Problem zu sein (im Gegensatz zu meiner Vermutung).


Hier mit einer Regexp, die ich in einem der Threads gefunden habe:

Code: Alles auswählen

B-) echo '"foo","bar""","""baz","quux"' | egrep -o '[^,"]*|"(""|[^"])*"'           
"foo"
"bar"""
"""baz"
"quux"

B-) echo '"foo","bar""","""baz"",""quux","blub"' | egrep -o '[^,"]*|"(""|[^"])*"'
"foo"
"bar"""
"""baz"",""quux"
"blub"

Das ist korrekt geparst.

Man muss dann nur noch die Quotes und Escapes entfernen. (Z.B. mit sed 's,^"\(.*\)"$,\1,; s,"",",g' .)

[bluestar]

Zurück zum eigentlichen Problem:

Das war es was mir fehlte:

1. externer Anrufer ruft auf einer Festnetzrufnummer der Firma an
2. Nummer klingelt intern
3. Nummer wird intern nicht abgehoben
4. Nummer wird ggf. auf das Handy vermittelt.
5. Im Log fehlte die ursprünglich angenommene Festnetzrufnummer

Ich habe jetzt im Asterisk Wahlplan eines der Abrechungsfelder(CDR(userfield)) mit der der angerufenen Festnetzrufnummer belegt. Damit habe ich die Information.

Vielleicht magst du uns ja auch mal dein Dialplan verraten, dann könnten wir hier dem Problem auf den Grund gehen.

[heisenberg]

Der ist ziehmlich umfangreich... Und ich müsste den immer wieder anonymisieren. Da habe ich gerade keine Lust drauf.

Nachdem alles so funktioniert so wie es soll, ändere ich daran nichts mehr.

[Meillo]

Nachdem alles so funktioniert so wie es soll, ändere ich daran nichts mehr.

Verstehe ich das dann richtig, dass dein konkretes Problem damit schon geloest ist? (Und du damit den Thread auf erledigt setzen koenntest?) (Und dann auch die theoretische Parserdiskussion wieder aufleben koennte ... falls es dazu noch etwas zu erkunden/lernen/diskutieren/ausprobieren gibt?)

[heisenberg]

Ja.

[eggy]

Ok, ihr habe es ja so gewollt

Das läuft gerade schon so, wie ich das gut haben kann: Ich habe eine Idee und sie wird entweder widerlegt oder nicht. Und das Spielchen geht so lange weiter, bis einer keine Lust mehr hat, oder die Erkenntnis steht: Ja, das geht definitiv (nicht)!

Wenn ein theoretischer Informatiker da wäre, ist die Frage ob ich den überhaupt verstehen würde!

Ich versuchs mal so zu erklären dass man das auch ohne Studium verstehen kann. Sag Bescheid, falls was unverständlich ist. Und falls ich was durcheinandergeworfen hab, das Thema ist bei mir auch schon nen paar Tage her, wer es frischer gelernt hat, mag Fehler daher gerne korrigieren.

Der Begriff "Sprache" bezeichnet eine Menge von Elementen, die (in bestimmter Anordnung und Wiederholung als sogenannte "Wörter") strukturell zusammengefasst werden können. Die Sprache "a" z.B. könnte gebildet werden aus einer beliebigen Anzahl von "a", jedoch mindestens ein "a" und bis zur maximalen Länge von 5 "a", somit wären die Sprache "a" gebildet aus der Menge der folgende Wörter: "a", "aa", "aaa", "aaaa", "aaaaa". "ab" wäre hier aber kein Wort der Sprache.
Die Bildungsvorschriften können komplexer sein, so gibt es auch die Besonderheit namens ɛ (Epsilon, dem "leeren Wort", also ein Wort das kein "Zeichen" enthält. Ähnlich wie NULL, nicht 0, nicht nichts aber auch nichts... wollte hier nicht jemand mehr Philosophie im Forum? ) ... ​ Du hast nun also nen Berg "Sprachen", die will man aber auch irgendwie ordnen, nach bestimmten Eigenschaften. Da hat sich ein Herr namens Chomsky mal drangesetzt. Der sagte, es gibt ne Menge von Klassen und jede dieser Klassen hat ne weitere bestimmte besondere Eigenschaft, die die Klasse davor nicht hatte. Er nennt die Sachen Typ-3, Typ-2 usw., nicht von den Zahlen verwirren lassen, eigentlich kommt's nur darauf an, https://upload.wikimedia.org/wikipedia/ ... ie.svg.png dass bestimmte "Sprachen" strukturelle Eigenschaften haben, die andere so nicht haben.

Nun muss man ein paar Grundannahmen treffen. Dass die zutreffend sind, zeigt man im ersten bzw zweiten Semester, ich erspare Dir das hier, falls Du zweifelst oder Literaturempfehlungen haben willst, kann ich nen paar ISBN nachreichen, Schönings "Theoretische Informatik" sollte das ganze Thema ausreichend weit behandeln, wenn ich das noch richtig im Kopf hab.
Es gibt eine spezielle Struktur (die von regulären Sprachen), die hat die besondere Eigenschaft, dass man sie als eine sehr spezielle Art von Graph darstellen kann, einem DFA. Das ist auch wieder ein sehr lustiges Konstrukt der Theoretiker: Ein DFA ist wie ein kleines Monster, es frisst Zeichen und bewegt sich dabei. Wenn das Monster alles aufgefressen hat, und sich am Ende irgendwo befindet wo es ihm gefällt, sagt es "ja, das war ein gutes Wort, das gehört zur Sprache" (nennt sich dann "akzeptierender Endzustand"). Bekommt es was zu fressen, mit dem es nichts anfangen kann, sagt es "igitt, das will ich nicht, das gehört nicht auf meinen Speiseplan" (in theoreitschinformatisch: "das Wort ist nicht Teil der Sprache").
Man kann nen DFA auch mit nem U-Bahnplan vergleichen: Jedesmal wenn Du ein Zeichen gelesen hast, muss die Bahn eine Station weiterfahren, aber nur wenn das Zeichen eine Verbindung zur nächsten Station symbolisiert. Sind die Zeichen alle, steigst Du aus. Bist Du nun da, wo du sein wolltest, waren deine Zeichen ein Wort der Sprache, bist Du woanders, oder konnte der Zug nicht mit nem "a" vom Rathaus zum Markt fahren, war das, was Du der Bahn geboten hast, halt kein Wort der Sprache.
Jetzt gibt es noch ein zweites Konstrukt, den NFA, der ist praktisch das selbe in grün, nur dass man mehrere Stationen zu einer Schnellstrecke zusammenfassen kann. Und als nächstes muss man wissen, NFA und DFA sind zwar unterschiedliche Dinge, es gibt aber nen Beweis, der sagt, dass man durch regelkonformes Einfügen bzw Weglassen, den einen in den anderen verwandeln kann. Aus gutem Grund bevorzugt man in Computerprogrammen NFA, da man dann nicht so (unendlich) viel Speicherplatz braucht. Das A in DFA und NFA steht für finiter Automat. D wie deterministisch.

Nun gilt: gibt es einen DFA, dann gibt es dazu auch ne reguläre Sprache und diese reguläre Sprache ist durch die dazupassende reguläre Grammatik (den Bildungsregeln, wie "endlich viele a, mindestens 1 aber maximal 5") beschrieben (bzw "erzeugt").

Und nun kommt der für die eher praktisch veranlagten interessante Teil: immer dann, wenn das vorgesagte gilt, dann gibt es auch einen "Regulären Ausdruck" gibt, mit dem der Automat beschreiben werden kann (genauer, die Wege, die die U-Bahn nehmen darf, um alle Wörter der Sprache abzubilden).

Wichtig ist, dass der einfache finite Automat kein Gedächnis hat. Er weis nicht, was noch kommt, noch kann er sich daran erinnern, was und wieviel er bereits gefuttert hat, er hat auch keine Ahnung wie er dahin gekommen ist, wo er nun ist. Alles was er sagen kann ist: "gefällt mir hier", "gefällt mir hier nicht".

Soweit noch mitbekommen? War vielleicht etwas viel Unbekanntes auf einmal, aber die Grundlagen braucht man fürs Verständnis des Problems. Das war jetzt gut ein halbes Semester im Schnelldurchflug, ich entschuldige mich ausdrücklich für den verzettelten Blödsinn, das ist wirklich nur als unglaublich grober Überblick gemeint und erhebt keinerlei Anspruch auf Korrektheit. Die Wikipediaartikel zu den genannten Stichworten führen das genauer und teilweise auch sehr viel besser aus, manchmal steht man da aber ohne mathematisch/theoretisches/linguistisches Vorwissen aber im strömenden Regen.

Will man, dass der Automat mitzählen kann, bzw ein (kleines) Gedächnis hat, braucht es Kellerautomaten, Stackmaschines. Damit sind wir dann aber eine Klasse weiter.

Wenn Deine Sprache aber schon durch einen einfachen DFA abbildbar ist, dann (und zwar nur genau dann) darf man sie eine Reguläre Sprache nennen. Und dann gibt es auch (mindestens) einen regulären Ausdruck, mit dessen Hilfe man entscheiden kann, ob ein Wort zu dieser Sprache gehört oder nicht.

Und nun zu dem eigentlich Problem: Kann ich zeigen, dass man eindeutig sagen kann "ich bin vom Anfang zum Ende in endlich vielen Schritten durch meinen DFA gelaufen und dort geendet, wo es mir gefällt"? Oder gibt es die Möglichkeit, dass ich zwischendurch nicht mehr eindeutig sagen kann, gefällt es mir hier oder nicht - und wie geht's von hier weiter. In einigen Fällen ist es einfach zu erkennen, ob das Wort zur Sprache gehört, in anderen schwierig.

Und die Praxis macht's dann noch schwerer, weil einige Implementationen von "regulären" Ausdrücken, entgegen der formalen Anforderung, doch ein oft wenig mitzählen oder den Blick in Vergangenheit und Zukunft erlauben, was nach der reinen Lehre dort nichts zu suchen hätte. Die Stichworte dazu sind Backreferenz und Lookahead.

Wenn man zurück zu den Klassen geht, Typ-3 hatten wir anfangs, als nächstes kämen dann die kontextfreien Sprachen/Grammatiken und dann die kontextsensitiven. An der Stelle darf man sich dann mit dem Dangeling-Else-Problem rumschlagen, bevor wir ganz allgemein bei strukturierten Sprachen landen. Dann gehts über zu den natürlichen Sprachen. Und dann gehts zu der Frage nach der Semantik in der Sprache. Weitergehende Begriffe für die Suchmaschine wäre erstmal die Chomsky Hierarchie und dann, für die formalen Beweise wichtig, das gute alte Pumping Lemma, das Horden von Zweitsemestern an den Rand ihrer geistigen Gesundheit getrieben hat. Viel Spass auf der Reise