Adventskalender 14. Dezember 2022 - lex

[Meillo]

Vermutlich wird von all denjenigen, die kein Informatik-Studium belegt haben, kaum jemand lex kennen. Und diejenigen mit Informatikstudium werden es fast nur mit dem Compilerbau verbinden. So jedenfalls ist es bei mir: Lex ist in der Wahrnehmung ein Programm, das man fuer die lexikalische Analyse verwendet, wenn man einen Compiler bauen will. Da die wenigsten beruflich oder in der Freizeit Compiler bauen, setzen auch wenige lex ein.

Mein Blick hat sich geweitet, als ich vor ein paar Jahren realisiert habe, dass lex mehr kann, als nur beim Compilerbau zu helfen und dass man es auch fuer allerlei kleine Programmieraufgaben nutzen kann. Vielleicht kann dieses Tuerchen auch euren Blick etwas weiten.


Was kann lex?

Lex liest einen Eingabetext, untergliedert ihn mittels regulaerer Ausdruecke in Stueckchen (Tokens) und kann dann etwas mit diesen Stueckchen machen.

Wann immer man also Aufgaben hat, die diesen Arbeitsschritt beinhalten, koennte lex nutztlich sein. Der grosse Vorteil an lex ist, dass es sehr flexibel arbeitet. Der Eingabetext kann also frei formatiert sein. Lex kann auch ueber Zeilenumbrueche hinweglesen und ueberlappende Suchmuster handhaben.

Lex ist fuer die Sprache C entwickelt worden. Alle Beispiele hier sind in C. Als konkrete, freie lex-Implementierung kommt flex zum Einsatz. Fuer andere Sprachen gibt es aehnliches, z.B. JFlex fuer Java und PLY fuer Python.


Erstes Beispiel: Zahlen extrahieren

Hier ein kleines lex-Aequivalent fuer:

Code: Alles auswählen

egrep -o '[0-9]+'

Das sieht dann so aus, dass wir eine Quellcodedatei `extractnum.l' anlegen, mit dem folgenden Inhalt:

Code: Alles auswählen

%%
[0-9]+  printf("%s\n", yytext);
.|\n    ;

Diese drei Zeilen sind der komplette Code des Programms, den wir schreiben muessen, der Rest wird von lex generiert.

Uebersetzt wird das Programm dann mit:

Code: Alles auswählen

lex extractnum.l
gcc lex.yy.c -ll -o extractnum

Mit dem ersten Befehl wird die Ausgabedatei `lex.yy.c' erzeugt. `-ll' sorgt dafuer, dass die lex-Lib gelinkt wird.

Anschliessend koennen wir das Programm starten und sehen, dass es die gleiche Ausgabe erzeugt, wie der egrep-Befehl:

Code: Alles auswählen

:-/ cat input1 
foo bar 123 baz
bli456bla7blub
zip1.98765zap

:-/ ./extractnum <input1                              
123
456
7
1
98765

:-/ egrep -o '[0-9]+' <input1                         
123
456
7
1
98765

Aufbau der lex-Datei

Die lex-Datei enthaelt drei Abschnitte, die durch `%%' getrennt sind, wobei der letzte Abschnitt und damit der zweite Trenner entfallen koennen.

Der erste Abschnitt enthaelt Definitionen fuer lex und C-Code, der unveraendert an den Beginn der generierten C-Datei kopiert wird, also z.B. Includes und Variablendeklarationen. Im vorigen Beispiel ist dieser Abschnitt leer.

Der zweite und wichtigste Abschnitt enthaelt Regeln fuer die einzelnen zu erkennenden Stueckchen des Eingabetextes (Tokens). Jede Regel besteht aus einem Muster (RegExp) und einer Action, also Code der ausgefuehrt werden soll, wenn das Muster in der Eingabe zutrifft.

Der dritte, optionale Abschnitt enthaelt wiederum C-Code, der ans Ende der generierten Datei kopiert wird. Typischerweise ist das z.B. eine main()-Funktion.

In unserem Beispiel enthaelt die Datei nur genau zwei Regeln:

- wenn eine Ziffernfolge im Input vorkommt, dann wird diese ausgegeben. (`yytext' enthaelt den gematchten String.)
- ein beliebiges Zeichen und Newlines werden ignoriert.

Passt ein Zeichen des Inputs auf keine Regel, so wird es einfach unveraendert ausgegeben. Das ist hier nicht der Fall, da das zweite Muster auf alle Zeichen passt. Jedoch werden laengere Treffer bevorzugt und bei gleicher Laenge die weiter oben stehende Regel.

Auf diese Weise koennen wir beispielsweise alle Newlines wegfuttern und den Rest ausgeben lassen:

Code: Alles auswählen

%%
\n      ;

Suchen-Ersetzen

Sinnvoller waere es, die Newlines mit Leerzeichen zu ersetzen, um den ganzen Text auf eine Zeile zu bekommen. Dies geht so:

Code: Alles auswählen

%%
\n      putchar(' ');

Daraus entstandene Programm tut das Gleiche wie `xargs' (ohne Argumente), wenn man beide mit dem gleichen Inputtext aufruft.

Ein Programm, das Platzhalter im Text ersetzt, ist ebenso einfach:

Code: Alles auswählen

%%
"foo"   printf("bar");

Jedes ``foo'' in der Eingabe wird durch ``bar'' in der Ausgabe ersetzt. Damit ist das ein Aequivalent zu:

Code: Alles auswählen

sed 's/foo/bar/g'

Mitzaehlen

Wir koennen in lex ganz einfach mitzaehlen, wie viel Mal ein String schon im Text vorgekommen ist:

Code: Alles auswählen

%{
        int n = 1;
%}
%%
"foo"   {
        printf("%s(%d)", yytext, n++);
}

Im ersten Abschnitt wird hier eine globale Variable angelegt. Text der in %{ und %} eingeschlossen ist, wird unveraendert in die C-Datei kopiert. Das gilt auch fuer jeden eingerueckten Text. Nur muessen #includes und #defines am Zeilenbeginn stehen und dafuer braucht es die Klammerbloecke.

Alternativ ginge auch diese Form, die nur eine lokale Variable anlegt, die dann aber im dritten Block nicht sichtbar waere:

Code: Alles auswählen

%%
        int n = 1;
"foo"   {
        printf("%s(%d)", yytext, n++);
}

Bei jedem Auftreten von ``foo'' wird der gematchte Text selbst (also ``foo'') plus die Anzahl des Vorkommens ausgegeben.

Ist das Suchmuster in Doublequotes angegeben, dann wird es als String gesucht. Andernfalls wird es als regulaerer Ausdruck interpretiert.


Zahlen summieren

Nun ein etwas umfangreicheres Beispiel, bei dem wir auch eine `main()'-Funktion schreiben:

Code: Alles auswählen

        int sum = 0;
%%
        int n;
[0-9]+  {
        n = atoi(yytext);
        printf("zahl gefunden: %d\n", n);
        sum += n;
}
.|\n    ;  /* ignore everything else */
%%
int
main(void)
{
        yylex();
        printf("SUMME: %d\n", sum);
        return 0;
}

Jede erkannte Zahl (egal wo im Text) wird ausgegeben und aufsummiert. Am Ende wird die Summe aller Zahlen ausgegeben.

Wenn wir keine eigene main()-Funktion schreiben, dann wird eine Default-main()-Funktion verwendet, die so aussieht:

Code: Alles auswählen

int
main(void)
{
	yylex();
	return 0;
}

(`yylex()' startet den Scanner.)

Man kann die main()-Funktion voellig frei gestalten, nur sollte halt irgendwo yylex() aufgerufen werden, da sonst lex nicht zum Einsatz kommt. ... kann man aber natuerlich auch machen:

Code: Alles auswählen

%%
%%
int
main(void)
{
        printf("hello, world\n");
        return 0;
}

Doppelte Worte finden

Ein Fehler, der mir beim Schreiben oefters passiert, sind sind doppelte Woerter. Wenn ich kurz abgelenkt bin, kann es vorkommen, dass ich ein Wort doppelt doppelt schreibe. Solche Fehler lassen sich mit lex finden, auch wenn sie vom Zeilenumbruch getrennt sind. Hierfuer nun ein etwas fortgeschritteneres Beispiel:

Code: Alles auswählen

%{
        char lastword[BUFSIZ] = "";
%}
WORD    [A-Za-z][A-Za-z-]*[A-Za-z]
RESET   [^ \t\n]
%%
{WORD}  {
        ECHO;
        if (strcmp(yytext, lastword)==0) {
                printf(" <-- DOPPELTES WORT\n");
        }
        strcpy(lastword, yytext);
}
{RESET} {
        ECHO;
        strcpy(lastword, "");
}

Im ersten Abschnitt gibt es sowohl C-Code, der kopiert wird, als auch zwei Muster-Aliase, die unten bei den Regeln wieder aufgegriffen werden. Das macht die Regeln lesbarer.

Die Regeln enthalten u.a. den praktischen Befehl `ECHO' -- ein Macro, das einfach nur den gematchten Text wieder ausgibt. Hier die Zeile aus dem Quellcode von Heirloom lex:

Code: Alles auswählen

fprintf(fout, "#define ECHO fprintf(yyout, \"%%s\",yytext)\n");

Das Programm gibt eine Hinweismeldung aus, sobald es zwei identische, nur durch Whitespace getrennte Worte erkennt. Hier koennte natuerlich noch weitere Logik eingebaut werden.

Ein Wort ist in diesem Beispiel definiert als mindestens zwei Buchstaben zwischen denen weitere Buchstaben und Bindestriche sein koennen. Beim Input ``foo-bar'' wird also ein Wort ``foo-bar'' erkannt. Beim Input ``-foo-bar-'' das gleiche Wort ``foo-bar'', da die Bindestriche am Wortende nicht zum Wort gezaehlt werden. Waehrend eine einfache Version dieses Programmes mit awk noch gut machbar ist, macht es lex einfacher, das Programm zu skalieren.


Formate konvertieren

Generell kann lex eines gut: ein Format in ein anderes konvertieren, so wie beispielsweise in diesem Forenthread gezeigt, als die Schachnotation in eine fuer LaTeX passende Form gebracht werden sollte: viewtopic.php?t=182940&start=25#p1290764
Lex ist hierbei flexibel genug, mit Abweichungen beim Whitespace problemlos klar zu kommen.


Abschluss

Ich hoffe, ich habe zeigen koennen, dass lex nicht nur fuer den Compilerbau zu gebrauchen ist. Sicherlich ist es ein fortgeschrittenes Programmierwerkzeug, aber fuer Vielprogrammierer kann es ein nuetzliches Hilfsmittel sein, wenn man sich mal ein bisschen damit vertraut gemacht hat. Erstaunlich finde ich immer wieder, wie alt (1975) und zugleich maechtig es ist.

Fuer diejenigen, die lex noch besser kennenlernen wollen, verweise ich auf das Original-Paper der Autoren: http://squoze.net/UNIX/v7/files/doc/20_lex.pdf Und dann einfach selber damit rumspielen.

POSIX-Beschreibung von lex: https://pubs.opengroup.org/onlinepubs/9 ... s/lex.html

[Meillo]

Ergaenzend noch ein Programm, das die jeweilige Uhrzeit einsetzt, wenn es ``TIME'' findet:

Code: Alles auswählen

%{
#include <time.h>
%}
%%
        char outstr[BUFSIZ];
        time_t t;
        struct tm *tmp;

"TIME"  {
        t = time(NULL);
        tmp = localtime(&t);
        strftime(outstr, sizeof(outstr), "%F %T", tmp);
        printf("<%s>", outstr);
}

Hier ist es notwendig %{ und %} zu verwenden.

(Auf die Fehlerbehandlung wurde verzichtet.)

[paedubucher]

Ich hatte lex schon einmal ausprobiert, es aber in der Form von PLY in einem Python-Projekt produktiv verwendet. Das hat so gut funktioniert, dass ich einen bestehenden Parser im selben Projekt habe durch PLY ersetzen können. D.h. ich habe auch den YACC-Teil verwendet.