RegExp Kurs: Go

[paedubucher]

Kursübersicht

Reguläre Ausdrücke in Go

In diesem Kursteil geht es um Behandlung regulärer Ausdrücke (fortan: «Regexp») in der Programmiersprache Go.

Offizielle Dokumentation

Go verfügt über sein eigenes Dokumentationssystem (go doc). Folgende Einträge (als Befehl angegeben, verlinkt auf die HTML-Dokumentation) sind für das vorliegende Thema empfehlenswert:

• go doc regexp
• go doc regexp.Regexp
• go doc regexp/syntax

Für eine Übung wird die Ausgabe von go doc benötigt. Von daher ist es besser, sich gleich mit dem Befehl vertraut zu machen, statt sich nur auf HTML-Version zu verlassen.

Dateien zum Download

Da Go über keine REPL verfügt, sind die vorgestellten Programme etwas umfassender als etwa Python-Beispiele. Der Einfachheit halber können die ganzen Beispiele unter folgendem Link als Zip-Datei heruntergeladen werden:

• dfdegoregexp.zip

Die einzelnen Dateien sind auch per NoPaste verlinkt.

Syntax

Go verwendet grundsätzlich die gleiche regexp-Syntax wie Perl oder Python. Genau genommen handelt es sich um die Syntax von RE2, mit kleineren Ausnahmen. Es ist aber auch möglich, die einfacheren ERE in Go zu verwenden. Hierzu stellt die regexp-Bibliothek Funktionen mit dem POSIX-Suffix zur Verfügung (mehr dazu später).

Implementierung

Die regexp-Implementierung von Go basiert auf der Arbeit von Ken Thompson in den 1960er-Jahren. Sie basiert auf endlichen Automaten und soll in ca. 400 Zeilen C-Code umsetzbar sein.

Die Laufzeitkomplexität dieser Implementierung (Thompson NFA: Thompson Non-Deterministic Finite Automaton) wächst linear zur Eingabe. Andere Implementierungen haben eine wesentlich höhere Laufzeitkomplexität. Siehe dazu den Beitrag von Russ Cox: Regular Expression Matching Can Be Simple And Fast (Der Artikel ist von 2007: das Jahr, in dem die Entwicklung von Go lanciert worden ist; u.a. von Ken Thompson. Russ Cox gehört mittlerweile zum Kernteam von Go.)

Passt es? Einfaches Matching

Ein einfaches Matching kann mit der Funktion regexp.Match umgesetzt werden:

Code: Alles auswählen

func Match(pattern string, b []byte) (matched bool, err error)
    Match reports whether the byte slice b contains any match of the regular
    expression pattern. More complicated queries need to use Compile and the
    full Regexp interface.

Liegen die zu prüfenden Daten als String und nicht als Byte-Array vor, kann man regexp.MatchString verwenden:

Code: Alles auswählen

func MatchString(pattern string, s string) (matched bool, err error)
    MatchString reports whether the string s contains any match of the regular
    expression pattern. More complicated queries need to use Compile and the
    full Regexp interface.

Das folgende Beispiel replexp (eine Kombination aus «REPL» und «Regexp») veranschaulicht die Verwendung der Match-Funktion:

41732

Das Beispiel lässt sich folgendermassen starten:

Code: Alles auswählen

$ go run replexp/main.go '#[A-Fa-f0-9]{6}'

Als Kommandozeilenargument wird die Regexp #[A-Fa-f0-9]{6} verwendet, womit hexadezimale Farbangaben mit einleitendem Rautezeichen gematched werden können. Die Interaktion mit dem Programm sieht dann etwa folgendermassen aus:

Code: Alles auswählen

#FFFFFF
#FFFFFF
#ffffff
#ffffff
#232323
#232323
#abc
#foobar
#deadbeef
#deadbeef
#999

Eingabezeilen werden nach Betätigung von [Return] nur dann erneut ausgegeben, sofern sie der Regexp genügen (#FFFFFF, #ffffff, #232323 usw.), andernfalls (#abc, #foobar, #999) jedoch nicht.

Aufgabe 1

Probiere verschiedene Regexp als Kommandozeilenparameter aus. Gib anschliessend Zeilen ein, und überlege dir vor der Betätigung von [Return], ob die Zeile der Regexp genügt oder nicht.

Aufgabe 2

In der obigen Wiedergabe der REPL-Interaktion wird die Zeichenkette #deadbeef ausgegeben, obwohl diese länger als die geforderten sechs Zeichen ist. Warum ist das so, und wie lässt sich das korrigieren?

Aufgabe 3

Das Programm verwendet die regexp.Match-Funktion, welche das Suchmuster als String und den Text, in dem zu suchen ist, als Byte-Array erwartet. Die regexp.MatchString-Funktion arbeitet mit zwei String-Argumenten. Was muss alles umgestellt werden, damit MatchString verwendet werden kann? (Siehe input.ReadBytes im Code.) Wird der Code durch die Umstellung insgesamt kürzer und/oder besser lesbar, oder verschlechtert sich die Situation eher?

Kompilierung und Regexp-Typ

Regexp können kompiliert und wiederverwendet werden. Das regexp-Paket bietet vier Funktionen an, womit eine Regexp kompiliert und anschliessend als Regexp-Typ wiederverwendet werden können:

• func Compile(expr string) (*Regexp, error)
• func CompilePOSIX(expr string) (*Regexp, error)
• func MustCompile(str string) *Regexp
• func MustCompilePOSIX(str string) *Regexp

Die Funktionen mit dem Must-Präfix werfen eine Runtime Panic, wenn der angegebene Ausdruck nicht kompiliert werden kann. Das ist besonders bei hart codierten regulären Ausdrücken sinnvoll, sodass fehlerhafter Code möglichst früh und offensichtlich scheitert. Die beiden Funktionen ohne Must-Prefix geben stattdessen einen error zurück, wenn die Regexp nicht kompiliert werden kann. Darauf ist im Code entsprechend zu reagieren.

Standardmässig wird die RE2-Syntax (PCRE mit kleinen Unterschieden) verwendet. Die Funktionen mit dem POSIX-Suffix schränken die Syntax auf EREs ein.

Durch die optionalen Präfixe Must und POSIX ergeben sich die obigen vier Funktionen.

Hat man durch gelungene Kompilierung eine Regexp-Struktur erhalten, bietet diese eine Vielzahl von Methoden an. Hier sollen nur die Find-Methode und die Replace-Methode mit ihren verschiedenen Ausprägungen von Interesse sein. (Match und MatchString sind auf der Regexp-Struktur analog zu gebrauchen wie vom regexp-Modul.)

Die Methode Find gibt es in verschiedenen Ausprägungen. Die folgenden Suffixe können in der angegebenen Reihenfolge angefügt werden, um die jeweilige Semantik zu erhalten. (Hier wird auf eine Eindeutschung der Dokumentation verzichtet):

• All: matches successive non-overlapping matches of the entire expression
• String: the argument is a string; otherwise it is a slice of bytes
• Submatch: the return value is a slice identifying the successive submatches of the expression
• Index: matches and submatches are identified by byte index pairs within the input string

Die Methodennamen folgen (gemäss Dokumentation) der Regexp:

Code: Alles auswählen

Find(All)?(String)?(Submatch)?(Index)?

Somit sind folgende Methoden vorhanden (zwei Varianten, die auf einem io.RuneReader basieren, sind der Vollständigkeit halber unten noch aufgeführt):

Code: Alles auswählen

func (re *Regexp) Find(b []byte) []byte
func (re *Regexp) FindAll(b []byte, n int) [][]byte
func (re *Regexp) FindAllIndex(b []byte, n int) [][]int
func (re *Regexp) FindAllString(s string, n int) []string
func (re *Regexp) FindAllStringIndex(s string, n int) [][]int
func (re *Regexp) FindAllStringSubmatch(s string, n int) [][]string
func (re *Regexp) FindAllStringSubmatchIndex(s string, n int) [][]int
func (re *Regexp) FindAllSubmatch(b []byte, n int) [][][]byte
func (re *Regexp) FindAllSubmatchIndex(b []byte, n int) [][]int
func (re *Regexp) FindIndex(b []byte) (loc []int)
func (re *Regexp) FindString(s string) string
func (re *Regexp) FindStringIndex(s string) (loc []int)
func (re *Regexp) FindStringSubmatch(s string) []string
func (re *Regexp) FindStringSubmatchIndex(s string) []int
func (re *Regexp) FindSubmatch(b []byte) [][]byte
func (re *Regexp) FindSubmatchIndex(b []byte) []int

func (re *Regexp) FindReaderIndex(r io.RuneReader) (loc []int)
func (re *Regexp) FindReaderSubmatchIndex(r io.RuneReader) []int

Den kleineren Rest der Funktionen, die nicht dem genannten Muster entsprechen, kann man bequem mittels (e)grep finden:

Code: Alles auswählen

$ go doc regexp.Regexp \
    | grep -Ev 'Find(All)?(String)?(Submatch)?(Index)?' \
    | grep '^func'

Bei den Replace-Methoden gibt es wiederum Varianten zur Ersetzung des gefundenen Textes mit Literalen (Literal) bzw. einer Funktion (Func), sowie Ausprägungen für Byte-Arrays und Strings (String):

Code: Alles auswählen

func (re *Regexp) ReplaceAll(src, repl []byte) []byte
func (re *Regexp) ReplaceAllFunc(src []byte, repl func([]byte) []byte) []byte
func (re *Regexp) ReplaceAllLiteral(src, repl []byte) []byte
func (re *Regexp) ReplaceAllLiteralString(src, repl string) string
func (re *Regexp) ReplaceAllString(src, repl string) string
func (re *Regexp) ReplaceAllStringFunc(src string, repl func(string) string) string

Für die nächste Übung kommt das Programm godocfuncs/main.go zum Einsatz:

41733

Dieses lässt sich folgendermassen ausführen:

Code: Alles auswählen

$ go run godocfuncs/main.go [package]

Es erwartet als Argument den Namen eines Go-Pakets oder -Symbols, wie z.B. string, regexp oder regexp.Regexp. Die Ausgabe der jeweiligen Dokumentationsseite (go doc string, go doc regexp usw.) soll so gefiltert werden, dass nur die zum Paket gehörigen Funktionsdeklarationen ausgegeben werden sollen. Hierzu wird die Regexp functionDeclaration und die Funktion dr.FilterLines verwendet, welche in der Datei godocfuncs.go definiert sind:

41734

Aufgabe 4

Die Regexp functionDeclaration (als String) muss ergänzt werden, damit das Programm korrekt arbeitet. Hier ein Beispiel für eine korrekte Ausgabe:

Code: Alles auswählen

$ go run godocfuncs/main.go regexp
func Match(pattern string, b []byte) (matched bool, err error)
func MatchReader(pattern string, r io.RuneReader) (matched bool, err error)
func MatchString(pattern string, s string) (matched bool, err error)
func QuoteMeta(s string) string

Die Datei godocfuncs_test.go enthält einen Testfall, der folgendermassen ausgeführt werden kann:

41735

Code: Alles auswählen

$ go test -run TestFilterFuncLines

Sektionen von Manpages

Das Programm manperf/main.go erwartet als Argumente einen beliebigen Befehl mit Kommandozeilenargumenten (z.B. man 3 printf oder man go). Der angegebene Befehl wird ausgeführt, und die Ausgabe davon vom Programm abgefangen. Aus der Ausgabe, die hierzu in der Form einer Manpage vorliegen muss, werden nun die einzelnen Sektionstitel extrahiert:

41736

Hierzu werden drei Funktionen aus dem Paket dfdegoregexp verwendet (Importname mit dr verkürzt), welche allesamt in manperf.go definiert sind:

41737

• CommandOutput: Die Funktion führt das angegebene Programm mit Argumenten aus und liefert dessen Ausgabe als ein String-Slice zurück.
• ExtractSectionsBad: Die Funktion extrahiert die Sektionstitel aus der gegebenen Ausgabe und liefert sie als String-Slice zurück. Die Implementierung ist fehlerhaft und inperformant!
• ExtractSectionsBetter: Die Funktion ist noch zu implementieren und aus manperf/main.go aufzurufen.

Aufgabe 5

Öffne die Datei manperf_test.go und betrachte den String-Slice expectedSections. Rufe nun man man auf, und überprüfe, ob die in expectedSections aufgelisteten Sektionen mit der tatsächlichen Ausgabe von man man übereistimmen; auch in ihrer Reihenfolge. Nimm Korrekturen daran vor, falls nötig.

41738

Aufgabe 6

Implementiere die Funktion ExtractSectionsBetter, sodass der entsprechende Testfall TestExtractSectionsBetter durchläuft. Dieser kann folgendermassen ausgeführt werden:

Code: Alles auswählen

$ go test -run TestExtractSectionsBetter

Läuft der Test durch, kannst du das Programm manperf/main.go so umschreiben, dass die neue Funktion ExtractSectionsBetter anstelle von ExtractSectionsBad verwendet wird. Rufe nun das Programm mit einer beliebigen Manpage aus, und kontrolliere dessen Ausgabe, z.B.:

Code: Alles auswählen

$ go run manperf/main.go man 3 printf

Aufgabe 7

Übertrage die funktioniertende Regexp aus der Funktion ExtractSectionsBetter nach ExtractSectionsBad, sodass nun beide Testfälle durchlaufen:

Code: Alles auswählen

$ go test -run TestExtractSections.*

Verändere aber nicht die Struktur der Funktion ExtractSectionsBad und verzichte auf eine kompilierte Regexp.

Starte nun die Benchmarks für die beiden Funktionen (ohne Tests):

Code: Alles auswählen

$ go test -bench . -run ^$

(Dem aufmerksamen Leser dürfte mittlerweile aufgefallen sein, dass das Go-Tool auch reguläre Ausdrücke zur Selektion von Benchmarks und Testfällen akzeptiert.)

Versuche die Implementierung von ExtractSectionsBetter schnell zu machen. (Tipp: verwende eine kompilierte regexp.Regexp, falls du noch nicht auf diese Idee gekommen bist.)

Ist die Variante der Compile-Funktion mit dem POSIX-Suffix schneller? Warum (nicht)?

Parsen von E-Mails; Gruppen

Im letzten Beispiel sollen Informationen aus E-Mail-Adressen ausgelesen werden. Die E-Mail-Adressen liegen in verschiedenen Formaten vor. Diese Formate sollen hier nicht definiert, sondern nur anhand vorgegebener Testfälle beschrieben werden. (Die zu implementierenden Regeln sind also induktiv zu erschliessen.)

Die Datei emailextract_test.go definiert die Testfälle:

41739

Eine E-Mail-Adresse kann folgende Elemente enthalten:

1. einen Vornamen (immer vorhanden)
2. einen Nachnamen (optional, nach dem Punkt)
3. ein Geburtsdatum (optional, vor dem @-Zeichen; eine zweistellige Zahl impliziert das 20. Jahrhundert)
4. einen Firmennamen (immer vorhanden, Domain ohne TLD; in Grossbuchstaben)

Die Implementierung liegt in der Datei emailextract.go vor:

41740

Die Funktion Extract nimmt einen String (die E-Mail-Adresse) entgegen, und gibt einen neuen String zurück. Das ganze passiert in mehreren Schritten:

1. Das Pattern p wird auf die E-Mail-Adresse angewendet, um Matches zu erzeugen (siehe go doc regexp.FindStringSubmatch).
2. Die Matches von p werden abgearbeitet. Mit p.SubexpNames (siehe go doc regexp.SubexpNames) erhält man eine Map, deren Key den Index und Value den Namen des Matches bezeichnet (i kann als Index für matches verwendet werden).
3. Es wird eine emailInfo-Struktur erstellt, auf der die extrahierten Informationen gesammelt werden können. Anhand des Gruppennamens können die ausgelesenen Informationen mithilfe von switch/case ins richtige Feld der emailInfo-Struktur abgelegt werden. (Siehe go doc strconv.Atoi für Konvertierungen von String zu Integer).
4. Zuletzt wird die String-Methode von emailInfo verwendet, um die extrahierten Informationen in der Form auszugeben, wie sie vom Testfall erwartet werden. (Die String-Methode ist bereits korrekt implementiert.)

Aufgabe 8

Rufe die Dokumentation zu Regexp-Syntax (go doc regexp/syntax) auf und finde heraus, wie man «named capturing groups» definiert.

Definiere nun die Regexp (Variable r oben an der Datei emailextract.go) und implementiere die Funktion Extract zu Ende, indem zu die TODO-Zeilen innerhalb der switch/case-Kontrollstruktur abarbeitest.

Führe den Testfall aus, um die Implementierung zu überprüfen:

Code: Alles auswählen

$ go test -run TestEmailExtract

[Meillo]

Noch ist ja nicht Mittwoch, darum will ich nicht zu viel von meinen Loesungsversuchen verraten.

Aktuell befasse ich mich mit folgender Aufgabe:

Aufgabe 2

In der obigen Wiedergabe der REPL-Interaktion wird die Zeichenkette #deadbeef ausgegeben, obwohl diese länger als die geforderten sechs Zeichen ist. Warum ist das so, und wie lässt sich das korrigieren?

Den RegExp-Aspekt dieses Problems habe ich natuerlich sehr schnell loesen koennen, der Go-Aspekt hat etwas mehr Zeit gebraucht. Inzwischen verstehe ich warum meine erste Trivialloesung (reines RE) nicht funktioniert hat und was ich in Go machen muss, damit es tut. Das war ein netter Lernprozess. Technisch ist das stimmig so wie es ist, ich hatte nur andere Erwartungen, da ich aus einer anderen Perspektive darauf geschaut hatte.

Dabei habe ich auch einen kleinen logischen Fehler im Code gefunden. Den hat paedubucher sicherlich bewusst eingebaut, um uns ein bisschen herauszufordern. Waere er nicht dagewesen, dann haette ich weniger gelernt.


Aufgabe 3 (Umstellung von []byte of string) habe ich inzwischen auch schon fertig. Die weiteren Aufgaben kommen dann nach und nach.


Wer von euch programmiert denn aktuell in Go auch mit ... oder versucht es zumindest?

[TRex]

Bin auch bis Aufgabe 3 gekommen.

[paedubucher]

Wie die Zeit vergeht: schon ein Monat her seit dem letzten Post!

Ich denke, ich sollte mal meine Lösungen veröffentlichen. Dieses Wochenende hätte ich gut Zeit. Oder ist jemand noch verkrampft am Abarbeiten der Übungen, und möchte nicht durch meine Lösungsvorschläge gestört werden?