grep.asm – Schritt 3: Reguläre Ausdrücke erkennen

2019-06-14

Okay, was ist hier los, warum dauert das so lange? Hat viele Gründe, zwei davon sind besonders ausschlaggebend.

Der erste ist RSI. Der menschliche Körper mag es wohl nicht so sehr, 8 bis 16 Stunden pro Tag Tastatur und Maus zu bedienen, tagein, tagaus, für ein paar Jahrzehnte, viel davon unter Stress – und dann noch ein bisschen was oben drauf. Eines Tages waren da also Schmerzen in den Händen und die gingen nicht mehr weg. Vorboten habe ich zumindest keine wahrgenommen. Meh. Der Heilprozess ist noch im Gange und diesen Text schreibe ich mit einem albernen Workaround im Schneckentempo, aber es ist besser als nichts. Vielleicht irgendwann später mal mehr zu diesem Thema.

Das ist natürlich auch der Grund, weshalb dieses Posting kürzer und oberflächlicher ist, als mir lieb wäre.

Der andere Grund ist schlichtweg Motivation. Ich habe dieses Projekt (teilweise) angefangen, weil die Komplexität und die Menge an Abstraktion heutiger Software ermüdend sind. In Assembler zu programmieren, führt mich ein bisschen näher an „die Maschine“ heran. Man bekommt hier noch am ehesten mit, was eigentlich passiert. (Dabei ist mir durchaus bewusst, dass es Dinge wie Register Renaming gibt und alles ist ohnehin superskalar und out-of-order, also herrscht selbst auf ASM-Ebene Lug und Trug.) Eine Regex-Engine kann aber natürlich beliebig kompliziert werden. Will ich das wirklich in ASM implementieren? Wird das nicht ein riesiges Monstrum? Genau das, was ich vermeiden wollte?

Mir war das von Anfang an klar und ich hatte einfach gehofft, dass mir unterwegs etwas Cleveres einfallen würde.

Nope.

Dann hab’ ich endlich das hier gefunden:

https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html

Lustigerweise waren Brian Kernighan und Rob Pike auf der Suche nach einer einfachen Regex-Engine und alle existierenden waren zu groß. Also schrieb Rob Pike drei sehr kurze C-Funktionen. Damit kann man zwar nicht alle regulären Ausdrücke erkennen (natürlich), aber doch eine sehr nützliche Teilmenge:

c    matches any literal character c
.    matches any single character
^    matches the beginning of the input string
$    matches the end of the input string
*    matches zero or more occurrences of the previous character

All das in diesen drei kurzen Funktionen. Das ist einfach „wow“. Oder wie Brian Kernighan schreibt: „a superb example of beautiful code“.

Faul, wie ich bin, habe ich eine ASM-Version seiner Routinen in grep.asm eingebaut.

Und damit sind wir am Ziel angekommen. grep.asm ist, von etwaigen Bugfixes abgesehen, erst einmal fertig. Der Tag blogpost-step-3 zeigt auf die Version dieses Postings.

Comments?