RegExp-Kurs 04: Konkatenation, Alternation, Unterausdruecke

[Meillo]

Kursuebersicht


Teil 04: Konkatenation, Alternation, Unterausdruecke


Nachdem ihr nun mit egrep und dem Escapen der dort geltenden Zeichen mit Sonderbedeutung vertraut seid, kommen wir nun zu den ersten Operatoren. Diese machen egrep maechtiger als fgrep.


Konkatenation

Der einfachste Operator in REs ist die Konkatenation. Auf Deutsch: die Aneinandereihung. Der Operator ist deshalb einfach, weil er implizit ist. Wenn wir zwei Ausdruecke hintereinander schreiben, dann bilden sie damit einen groesseren Ausdruck. Es gibt kein Operator(meta)zeichen, das wir verwenden muessten.

Beispielsweise ist ``Schwaben'' ein Ausdruck, den wir mit egrep in der Datei schwaebische-kunde.txt matchen koennen. Gleichermassen ist ``streiche'' ein solcher Ausdruck. Diese beiden koennen wir auch einfach hintereinanderstellen, um einen konkatenierten Ausdruck zu bilden: ``Schwabenstreiche''.

Das mag trivial klingen, trotzdem ist es ganz gut, sich das zu vergegenwaertigen. Im kleinsten Fall ist ein Ausdruck ein einziges Zeichen. So ist der Ausdruck ``Schwaben'' ja auch schon eine Konkatenation von acht einzelnen Ausdruecken mit je einem literalen Zeichen.

Eine Stringsuche ist auch nur eine Konkatenation literaler Zeichen. Derart waren all die Aufgaben der vorigen Einheit. Die Moeglichkeiten der Stringsuche enden dort; bei uns geht es jetzt erst richtig los!


Alternation

Der zweite (und erste wirklich interessante) Operator ist die Alternation, die zwei Ausdruecke in eine Oder-Beziehung setzt. Wenn ich also mit einem Ausdruck sowohl ``Schwabe'' als auch ``Held'' suchen will, dann kann ich die beiden Ausdruecke per Alternation verbinden.

Die Alternation wird durch den Operator Pipe (|) angegeben. Das Pipe-Zeichen ist also ein Sonderzeichen. Tritt es in der RE auf, dann wird es als Operator interpretiert. Will man es literal matchen, dann muss man es escapen. (Achtung: Je nach RE-Variante kann das auch umgekehrt sein.)

Der Regulaere Ausdruck fuer die erwaehnte Suche waere damit:

Code: Alles auswählen

Schwabe|Held

Dies ist auch mehrfach moeglich:

Code: Alles auswählen

Spiess|Saebel|Pfeil|Schwerdt

(Hier nochmal der Text vom vorigen Teil, um die Beispiele anzuwenden: 41651)


Unterausdruecke

Um nicht nur eine Ebene von Alternation zu haben, sondern diese verschachteln zu koennen, brauchen wir eine Moeglichkeit, einen komplexen Ausdruck als Einheit zu betrachten. Das geht indem wir ihn in runde Klammern einfassen.

Runde Klammern ( und ) sind also Sonderzeichen. Wenn sie in der RE auftreten, dann werden sie als Metazeichen interpretiert. Will man sie literal matchen, dann muss man sie escapen. (Achtung: Je nach RE-Variante kann das auch umgekehrt sein.)

Wir koennten die Ausdruecke zwar immer auch ausschreiben, aber es ist weniger Schreibarbeit wenn wir gleiche Teile aus der Klammer rausziehen koennen.

Nehmen wir beispielsweise alle Kombinationen von einem zu- und abnehmenden Mond bzw. Wind. Ausgeschrieben koennte man das folgendermassen zu einem Regulaeren Ausdruck zusammenbauen:

Code: Alles auswählen

zunehmender Mond|abnehmender Mond|zunehmender Wind|abnehmender Wind

Das ist eine ganze Menge Text, in der sich viel wiederholt. Mit Unterausdruecken geht es auch kompakter:

Code: Alles auswählen

(zu|ab)nehmender (Wind|Mond)

Hier gilt die Alternation jeweils nur auf die geklammerten Teile.

Man kann Alternationen auch Schachteln:

Code: Alles auswählen

Erd(apfel|birne)|Kartoffel

Generell kann man jeden vollstaendigen Regulaeren Ausdruck in runde Klammern fassen und dann als Unterausdruck in einem anderen Ausdruck verwenden.



Das bisher Gelernte nochmal kompakt beschrieben

Hier ein etwas angepasster und mit Anmerkungen versehenen Ausschnitt aus der Manpage regex(7), der unseren Wissensstand bis zum aktuellen Punkt zusammenfasst:

A Regular Expression is one or more branches, separated by '|'.
It matches anything that matches one of the branches.
[= Alternation]

A branch is one or more pieces, concatenated. It matches a match
for the first, followed by a match for the second, etc.
[= Konkatenation]

A piece is an atom [...].

An atom is a regular expression enclosed in "()" (matching a
match for the regular expression) [= Unterausdruck],
[...],
a '\' followed by one of the characters "^.[$()|*+?{\"
(matching that character taken as an ordinary character)
[= escapetes Metazeichen das dann literal interpratiert wird],
[...],
or a single character
with no other significance (matching that character)
[= Literal].

[...]

(Die Luecken in dieser Beschreibung koennen wir in den naechsten Einheiten nach und nach fuellen.)


Aufgaben:

1) Schreibe einen egrep-Ausdruck, der sowohl eine Alternation enthaelt als auch das Pipezeichen literal matcht und wende ihn auf einen dazu passenden Eingabetext an.

2) Finde ein inhaltlich sinnvolles Beispiel fuer eine zwei- oder dreifach verschachtelte Alternation.

3) Schreibe einen egrep-Ausdruck (nur mit Alternation und Unterausdruecken), um die Schreibweisen Maier, Meier, Mayer, Meier zu matchen.

4) Ergaenze (3) um die Schreibeweise Myer.

5) Finde alternative Ausdruecke fuer (3) und (4) (ohne andere RE-Operatoren zu verwenden, sondern nur indem du anders gruppierst).

6) Versuche diese Aufgaben auch mit fgrep umzusetzen. Was sind deine Erkenntnisse?

7) Braucht man runde Klammern um den gesamten Ausdruck wenn man eine Alternation (auf oberster Ebene) verwendet?

[Meillo]

Nebenbemerkung:

In der gleichen Manpage steht auch folgender Abschnitt, der zwar auf die regex-Lib
von Henry Spencer zutrifft aber leider nicht generell auf POSIX oder sonstige
RE-Varianten:

An atom is [...]

a '\' followed by one of the characters "^.[$()|*+?{\"
(matching that character taken as an ordinary character),

a '\' followed by any other character (matching that
character taken as an ordinary character, as if the '\'
had not been present)

Der erste Satz gilt generell fuer alle EREs. Der zweite leider nicht. Waere es
anders, dann haette ich anfangs die Dinge nicht so kompliziert machen muessen,
denn dann haette ich sagen koennen:

- Das Escapezeichen ist der Backslash.
- Metazeichen sind die Standardzeichen.
- Jedes escapete Zeichen steht literal fuer sich selbst.

Das waere klar und konsistent gewesen. Damit waeren die beiden Zeichenklassen
(Literale und Metazeichen) klar getrennt gewesen.

Der Bequemlichkeit halber kann man sich mit folgender Zusatzregel dann noch
Tipparbeit sparen:

- Metazeichen, die keine Sonderbedeutung haben, stehen automatisch
als Fallback auch literal fuer sich selbst. (`a' und `\a' sind also
beide ein literales `a'.)

Leider gilt das aber eben nur fuer Programme, die Henry Spencers regex-Lib
verwenden. Fuer andere RE-Implementierungen ist die Situation etwas
komplizierter, wenn man sie konzeptionell beschreiben will, da es
implementierungsabhaengig ist, was `\a' bedeutet. In der Bedienpraxis
macht das aber selten einen relevanten Unterschied.

[tegula]

1) Schreibe einen egrep-Ausdruck, der sowohl eine Alternation enthaelt als auch das Pipezeichen literal matcht und wende ihn auf einen dazu passenden Eingabetext an.

Code: Alles auswählen

$ ## "Reiter" oder "|Läufer"
$ egrep --line-number "Reiter|\|Läufer"  schwaebische-kunde.txt
9:Und mancher deutsche Reitersmann
12:Fast musst' der Reiter die Maehre tragen.
22:Fuenfzig tuerkische Reiter daher,
37:Er schwingt es auf des Reiters Kopf,
$ 

2) Finde ein inhaltlich sinnvolles Beispiel fuer eine zwei- oder dreifach verschachtelte Alternation.

Code: Alles auswählen

$ egrep --line-number "Reit(er|ar)" schwaebische-kunde.txt
9:Und mancher deutsche Reitersmann
12:Fast musst' der Reiter die Maehre tragen.
22:Fuenfzig tuerkische Reiter daher,
37:Er schwingt es auf des Reiters Kopf,
$ 

3) Schreibe einen egrep-Ausdruck (nur mit Alternation und Unterausdruecken), um die Schreibweisen Maier, Meier, Mayer, Meier zu matchen.

Code: Alles auswählen

$ cat a3.txt
Maier
Meier
Müller
Mayer
Meier
$ printf "\n"

$ egrep --line-number "M(a|e)(i|y)er" a3.txt
1:Maier
2:Meier
4:Mayer
5:Meier
$ 

4) Ergaenze (3) um die Schreibeweise Myer.

Code: Alles auswählen

$ cat a4.txt
Maier
Meier
Müller
Mayer
Meier
Myer
$ printf "\n"

$ egrep --line-number "M(a|e)(i|y)er|Myer" a4.txt
1:Maier
2:Meier
4:Mayer
5:Meier
6:Myer
$ 

5) Finde alternative Ausdruecke fuer (3) und (4) (ohne andere RE-Operatoren zu verwenden, sondern nur indem du anders gruppierst).

Code: Alles auswählen

$ egrep --line-number "Maier|Meier|Mayer|Meier" a3.txt
1:Maier
2:Meier
4:Mayer
5:Meier
$ printf "\n"

$ egrep --line-number "Maier|Meier|Mayer|Meier|Myer" a4.txt 
1:Maier
2:Meier
4:Mayer
5:Meier
6:Myer
$

6) Versuche diese Aufgaben auch mit fgrep umzusetzen. Was sind deine Erkenntnisse?

Versuch der Umsetzung:⁣ Siehe NoPaste-Upload (41671, Zeile 98 - 138)
Erkenntnisse: Eine wortgetreue Umsetzung der Aufgaben ist nicht möglich, da fgrep keine Operatoren (Konkenation, Alternation oder Unterausdrucke) unterstützt. Eine sinngemäße Lösung der Aufgaben (das heißt, die gleiche Eingabe soll mit fgrep zur selben Ausgabe führen wie zuvor mit egrep) ist hingegen möglich. Hierfür wird der Umstand genutzt, dass fgrep gleichzeitig nach mehreren Suchbegriffen suchen kann:

1. Musterdatei erzeugen, welche jedes potenziell mögliche "match" in einer separaten Zeile festhält.
2. Musterdatei anschließend mithilfe der Komandozeilenoption "-f" an fgrep übergeben

7) Braucht man runde Klammern um den gesamten Ausdruck wenn man eine Alternation (auf oberster Ebene) verwendet?

Nein, das Einklammern des Ausdrucks ist in diesem Fall nicht notwendig. Beispiel: Aufgabe 5 (41671, Zeile 80 - 93).

[Huo]

Aufgaben:

1) Schreibe einen egrep-Ausdruck, der sowohl eine Alternation enthaelt als auch das Pipezeichen literal matcht und wende ihn auf einen dazu passenden Eingabetext an.

Code: Alles auswählen

$ egrep 'C\|_\||Kaffeetasse' re4.txt
C|_| (ASCII-Art)
Kaffeetasse (Begriff)

2) Finde ein inhaltlich sinnvolles Beispiel fuer eine zwei- oder dreifach verschachtelte Alternation.

Code: Alles auswählen

egrep '(F|Ph)otophobie|Licht(scheu|empfindlichkeit)'

3) Schreibe einen egrep-Ausdruck (nur mit Alternation und Unterausdruecken), um die Schreibweisen Maier, Meier, Mayer, Meier zu matchen.

Code: Alles auswählen

egrep 'M(a|e)(i|y)er'

4) Ergaenze (3) um die Schreibeweise Myer.

Code: Alles auswählen

egrep 'M((a|e)(i|y)|y)er'

5) Finde alternative Ausdruecke fuer (3) und (4) (ohne andere RE-Operatoren zu verwenden, sondern nur indem du anders gruppierst).

zu (3):

Code: Alles auswählen

egrep 'M(ai|ei|ay|ey)er'

zu (4):

Code: Alles auswählen

egrep 'M((a|e|)y|(a|e)i)er'

Bemerkenswert finde ich hier, dass im Unterausdruck "(a|e|)" eine leere Alternative funktioniert ("a" oder "e" oder "nichts").

6) Versuche diese Aufgaben auch mit fgrep umzusetzen. Was sind deine Erkenntnisse?

Geht mit Option "-e". Umsetzung von Aufgabe 3):

Code: Alles auswählen

fgrep -e Maier -e Meier -e Mayer -e Meyer

Es sind auf diese Weise mit fgrep zwar keine Verschachtelungen möglich, aber alle aus Konkatenationen und Alternationen zusammengesetzten Ausdrücke lassen sich durch "Ausmultiplizieren" auf eine unverschachtelte Normalform S1|S2| ... |Sn bringen, wobei S1 ... Sn literale Zeichenfolgen sind. Die Normalform ist i.A. länger als der verschachtelte Ausdruck, aber auch lesbarer.

7) Braucht man runde Klammern um den gesamten Ausdruck wenn man eine Alternation (auf oberster Ebene) verwendet?

Nein.

[Meillo]

Sehr gut, ihr beiden. Das gefaellt mir.


Hierauf eine Anmerkung:

zu (4):

Code: Alles auswählen

egrep 'M((a|e|)y|(a|e)i)er'

Bemerkenswert finde ich hier, dass im Unterausdruck "(a|e|)" eine leere Alternative funktioniert ("a" oder "e" oder "nichts").

Stimmt. Es ist wohl so, dass das je nach Regexp-Engine unterschiedlich ist. Hier der Ausschnitt aus Henry Spencers regex-Manpage:

A (modern) RE is one(!) or more nonempty(!) branches, separated by '|'.

Das Ausrufezeichen bedeutet an der Stelle, dass es hier Uneinigkeit unter den RE-Implementierungen gibt. Ein leerer Branch in einer Alternation kann also funktionieren, muss aber nicht ueberall. Ggf. funktioniert auch dieses Form schon `(a|e|)' aber diese nicht `(a||e)'. Das sind dann die Untiefen der Randfaelle.

Fuer uns ist das nicht weiter wichtig, da wir in der uebernaechsten Einheit eine Moeglichkeit kennenlernen wie wir diese Faelle einfacher abbilden koennen.

[TuxPeter]

ist ja schon wieder Mittwoch und ich habe die Aufgaben noch gar nicht alle in Angriff genommen - na, mal sehen wie weit ich komme ... Egal, es bleibt spannend!

[Huo]

A (modern) RE is one(!) or more nonempty(!) branches, separated by '|'.

Das Ausrufezeichen bedeutet an der Stelle, dass es hier Uneinigkeit unter den RE-Implementierungen gibt. Ein leerer Branch in einer Alternation kann also funktionieren, muss aber nicht ueberall. Ggf. funktioniert auch dieses Form schon `(a|e|)' aber diese nicht `(a||e)'. Das sind dann die Untiefen der Randfaelle.

Fuer uns ist das nicht weiter wichtig, da wir in der uebernaechsten Einheit eine Moeglichkeit kennenlernen wie wir diese Faelle einfacher abbilden koennen.

Trotzdem noch eine Nachfrage hierzu. In der Manpage regex(7) finde ich auch:

An atom is a regular expression enclosed in "()" (matching a match for the regular expression), an empty set of "()" (matching the null string)(!), [...]

Wenn ich das richtig verstehe, würde also die folgende Lösung für Aufgabe (4)

Code: Alles auswählen

egrep 'M(((a|e)|())y|(a|e)i)er'

mit Henry Spencers regex-Manpage konform gehen, wobei "()" als leeres Atom für den Nullstring steht?

Edit: Sehe gerade, dass obiger Ausdruck wohl auch mit weniger "Klammerung" ginge.

Code: Alles auswählen

egrep 'M((a|e|())y|(a|e)i)er'

[Meillo]

A (modern) RE is one(!) or more nonempty(!) branches, separated by '|'.

Das Ausrufezeichen bedeutet an der Stelle, dass es hier Uneinigkeit unter den RE-Implementierungen gibt. Ein leerer Branch in einer Alternation kann also funktionieren, muss aber nicht ueberall. Ggf. funktioniert auch dieses Form schon `(a|e|)' aber diese nicht `(a||e)'. Das sind dann die Untiefen der Randfaelle.

Fuer uns ist das nicht weiter wichtig, da wir in der uebernaechsten Einheit eine Moeglichkeit kennenlernen wie wir diese Faelle einfacher abbilden koennen.

Trotzdem noch eine Nachfrage hierzu. In der Manpage regex(7) finde ich auch:

An atom is a regular expression enclosed in "()" (matching a match for the regular expression), an empty set of "()" (matching the null string)(!), [...]

Wenn ich das richtig verstehe, würde also die folgende Lösung für Aufgabe (4)

Code: Alles auswählen

egrep 'M(((a|e)|())y|(a|e)i)er'

mit Henry Spencers regex-Manpage konform gehen, wobei "()" als leeres Atom für den Nullstring steht?

Ja, das ist korrekt. Aber hier hat es das gleiche `(!)' wie an der anderen Stelle. Beides ist also gleichermassen implementierungsabhaengig.

Fuer uns hier wichtiger ist der konzeptionelle Schritt: Dass man jede RE in runde Klammern einfassen und dann als Teilausdruck in einer groesseren RE nutzen kann.

In deinem Beispiel wird einfach die leere RE in Klammern eingefasst. Ob leere REs erlaubt sind, haengt halt von der Implementierung ab. Wie du sicherlich durch Testen rausgefunden hast, funktioniert es in egrep (und vermutlich in den meisten Implementierungen).

[heisenberg]

IdRegExpKurs2022

[inne]

... es bleibt spannend!

... wir in der uebernaechsten Einheit eine Moeglichkeit kennenlernen wie wir diese Faelle einfacher abbilden koennen.

Wenn doch schon Heute wäre, denn das ist/wäre bestimmt etwas das ich in eines meiner Skripte mitnehmen kann

[Meillo]

... wir in der uebernaechsten Einheit eine Moeglichkeit kennenlernen wie wir diese Faelle einfacher abbilden koennen.

Wenn doch schon Heute wäre, denn das ist/wäre bestimmt etwas das ich in eines meiner Skripte mitnehmen kann

Mit den derzeit im Kurs erklaerten Mitteln kannst du es auch schon umsetzen, ggf. etwas umstaendlicher. Aber das ist ganz gut so, weil du es dann einmal jetzt umstaendlich zusammen bauen kannst und dann in ein paar Tagen nochmal neu und eleganter. Und eine Woche spaeter nochmal besser, usw. -- Man muss sich nur mal diesen Uebungs- und Lernerfolg vorstellen!

[inne]

Man muss sich nur mal diesen Uebungs- und Lernerfolg vorstellen!

Den habe ich schon beim Vokabular lernen.

[Meillo]

Mal noch zu den Loesungen hier:


Die Aufgabe 1 war einfach und ist problemlos geloest worden.

Bei Aufgabe 2 hat Huo eine gute Zwei-Ebenen-Schachtelung gefunden. Auf drei Ebenen bin ich auch noch nicht gekommen, also etwas nicht rein konstruiertes, sondern halbwegs sinnvolles.

Aufgabe 3 habt ihr wieder sehr gut gemeistert. (Die taucht im Teil 05 wieder auf, dann mit Zeichenklassen.)

Ueber eure zwei verschiedenen Varianten bei Aufgabe 4 habe ich mich sehr gefreut:

Code: Alles auswählen

egrep "M(a|e)(i|y)er|Myer"

Code: Alles auswählen

egrep 'M((a|e)(i|y)|y)er'

Genau so soll das sein. Man kann nicht sagen, dass eine davon besser waere. Die eine ist kompakter, die andere leichter lesbar. Das werden wir noch oefters feststellen, je mehr Operatoren und demnach Moeglichkeiten wir bei REs kennenlernen: Man kann die Dinge unterschiedlich umsetzen. Alles hat irgendwelche Vorteile und es entspricht jeweils eben auch unserem Denken. (Vielleicht schauen wir uns spaeter auch mal noch das Thema Rechenperformance unterschiedlicher RE-Formulierungen an ... falls es jemanden gibt, der sich damit auskennt.)

Die Aufgabe 5 war simpel.

Bei der Aufgabe 6 habt ihr ganz recht, dass fgrep das nicht direkt kann ... weil fgrep eben (fast) nur Stringsuchen kann und wir nun in die Moeglichkeiten von REs kommen, die ueber Stringsuchen hinausgehen. Aber wie ihr richtig erkannt habt, kann man eine Alternation auf oberster Ebene mit fgrep ueber mehrere Suchwoerter simulieren.

Auch richtig war in Aufgabe 7, dass man Klammern ganz aussen nicht braucht.

[TuxPeter]

Hi,
wollte nur noch vermelden, dass ich noch dabei bin.
Ich habe die Dateinamen meiner Bilderverzeichnisse in eine Textdatei eingelesen und damit geübt, das funktioniert mit der Alternation teilweise erheblich zielgerichteter als nur mit Find. Wobei man natürlich auch mehrere Suchen nacheinander starten kann, um das Gleiche zu erreichen.

Was ich nicht hinbekommen habe ist, die RegEx direkt im Find-Befehl zu verwenden., habe aber auch nicht weiter nach Beispielen gesucht. Laut man sollte es gehen, sogar mit verschiedenen regex-typen.

[tobo]

-regex im find vergleicht den kompletten Pfad. Die Ausgabe bei einem

Code: Alles auswählen

$ find . -name '*.txt'
./f1.txt
./f2.txt

kann man da als Vergleich hernehmen, was zu finden ist.

Code: Alles auswählen

$ find . -regex '.*txt'
./f1.txt
./f2.txt
## oder
$ find . -regex '\./.*txt'
./f1.txt
./f2.txt
## aber
$ find . -regex 'f.*txt'
$

So auch in "man find" zu finden:

-regex pattern
File name matches regular expression pattern. This is a match on the whole path, not a search. For example, to match a file named `./fubar3', you can use the regular expression `.*bar.' or `.*b.*3', but not `f.*r3'.
]/quote]

[TuxPeter]

Danke für die Beispiele.

Was mich aber sehr irritiert:

Code: Alles auswählen

 find -name '*kunde*'
./schwaebische-kunde.txt
 find . -regex '.*kunde.txt'
./schwaebische-kunde.txt
 find . -regex '.*kunde*'

Das letzte Beispiel funktioniert nicht, noch viel weniger die Alternation. (mit find direkt im Verzeichnis, in Textdateien mit egrep schon!)
Ist aber momentan unwichtig.

[tobo]

Was mich aber sehr irritiert:

Code: Alles auswählen

 find -name '*kunde*'
./schwaebische-kunde.txt
 find . -regex '.*kunde.txt'
./schwaebische-kunde.txt
 find . -regex '.*kunde*'

Was du suchst ist
./schwaebische-kunde.txt
und was du findest ist
./schwaebische-kunde
mit beliebig vielen e am Ende. Du musst den kompletten Dateinamen angeben, also hinten z.B. noch ".*" oder "\.txt" anhängen. Wenn du z.B. alles mit "Kunde" suchst, dann ".*Kunde.*"

[TuxPeter]

O, endlich hab' ich's. Habe die Wildcards stillschweigend als auch in RegEx gültig angenommen - stimmt natürlich ganz und gar nicht. Danke! Punkt als beliebiges Zeichen, * als Wiederholung. Oder so. Hatten wir ja auch noch nicht.

[Meillo]

O, endlich hab' ich's. Habe die Wildcards stillschweigend als auch in RegEx gültig angenommen - stimmt natürlich ganz und gar nicht. Danke!

Entweder oder. Beides zugleich kann nicht funktionieren, weil das gleiche Zeichen (z.B. der Stern) zwei unterschiedliche moegliche Bedeutungen haette und das Programm dann nicht wissen kann welche es nehmen soll.

Punkt als beliebiges Zeichen, * als Wiederholung. Oder so. Hatten wir ja auch noch nicht.

Richtig. Das kommt beides dieses Wochenende.