Anführungs- und Schlusszeichen automatisch ersetzen

[Meillo]

Ich habe das Ganze jetzt auch noch einmal in C implementiert.

Nutze lieber isspace(3) und memset(3) statt deren Funktionalitaet selbst zu implementieren.

Zum Verstaendnis (hab nur kurz quer gelesen): Ich hab eine Weile gebraucht, zu verstehen, was buf[BUF_SIZE] ist. Eine sprechenderer Name, wie z.B. context[CTX_SIZE] oder lookahead[NLOOKAHEAD] haette hier das Verstaendnis erleichtert.

Ansonsten sieht's gut aus! -- Eine tolle Uebung.

[paedubucher]

Ich habe das Ganze jetzt auch noch einmal in C implementiert.

Nutze lieber isspace(3) und memset(3) statt deren Funktionalitaet selbst zu implementieren.

Danke! Ich habe schon seit Ewigkeiten nichts mehr in C gemacht, darum ist mir isspace entfallen. Und memset verwende ich so richtig, also zum initialisieren?

Code: Alles auswählen

memset(buf, 0, sizeof(int) * BUF_SIZE);

Zum Verstaendnis (hab nur kurz quer gelesen): Ich hab eine Weile gebraucht, zu verstehen, was buf[BUF_SIZE] ist. Eine sprechenderer Name, wie z.B. context[CTX_SIZE] oder lookahead[NLOOKAHEAD] haette hier das Verstaendnis erleichtert.

Es ist viel eher ein "look behind" als ein "look ahead". Wie wäre es mit "input_buf" oder "input_queue"? Oder halt einfach "lookbehind"?

Ansonsten sieht's gut aus! -- Eine tolle Uebung.

Danke! Und C programmieren macht auch extrem viel Spass. Es ist zwar immer ein Krampf für mich mit meinen bescheidenen Kenntnissen, aber der Kopf ist dabei richtig schön gefordert und die Zeit vergeht wie im Fluge.

[Meillo]

Und memset verwende ich so richtig, also zum initialisieren?

Code: Alles auswählen

memset(buf, 0, sizeof(int) * BUF_SIZE);

Korrekt ja, aber nicht unbedingt optimal. So funktioniert's auch wenn buf mal zum Array von char wird:

Code: Alles auswählen

memset(buf, 0, sizeof(buf));

(Ein Array weiss wieviel Speicher es belegt.)

Zum Verstaendnis (hab nur kurz quer gelesen): Ich hab eine Weile gebraucht, zu verstehen, was buf[BUF_SIZE] ist. Eine sprechenderer Name, wie z.B. context[CTX_SIZE] oder lookahead[NLOOKAHEAD] haette hier das Verstaendnis erleichtert.

Es ist viel eher ein "look behind" als ein "look ahead". Wie wäre es mit "input_buf" oder "input_queue"? Oder halt einfach "lookbehind"?

Hmm, ich stelle fest, ich habe noch nicht verstanden, was die Idee von buf[] und put_retaining() ist. Vielleicht waere es sinnvoll, den Ansatz grob in einem Kommentar darzulegen ... koennte beim Codeverstaendnis helfen. (Das was ich sehe entspricht keinem mir bekannten Ansatz (oder ich sehe es nur nicht). Ich wuerde nun anfangen, mit Papier und Bleistift durch den Code zu steppen, um herauszufinden was das Konzept hinter diesem Teil der Implementierung ist. Vielleicht koenntest du diesen Schritt durch einen passenden Kommentar teilweise ersparen.)

[paedubucher]

Und memset verwende ich so richtig, also zum initialisieren?

Code: Alles auswählen

memset(buf, 0, sizeof(int) * BUF_SIZE);

Korrekt ja, aber nicht unbedingt optimal. So funktioniert's auch wenn buf mal zum Array von char wird:

Code: Alles auswählen

memset(buf, 0, sizeof(buf));

(Ein Array weiss wieviel Speicher es belegt.)

Natürlich, vielen Dank!

Zum Verstaendnis (hab nur kurz quer gelesen): Ich hab eine Weile gebraucht, zu verstehen, was buf[BUF_SIZE] ist. Eine sprechenderer Name, wie z.B. context[CTX_SIZE] oder lookahead[NLOOKAHEAD] haette hier das Verstaendnis erleichtert.

Es ist viel eher ein "look behind" als ein "look ahead". Wie wäre es mit "input_buf" oder "input_queue"? Oder halt einfach "lookbehind"?

Hmm, ich stelle fest, ich habe noch nicht verstanden, was die Idee von buf[] und put_retaining() ist. Vielleicht waere es sinnvoll, den Ansatz grob in einem Kommentar darzulegen ... koennte beim Codeverstaendnis helfen. (Das was ich sehe entspricht keinem mir bekannten Ansatz (oder ich sehe es nur nicht). Ich wuerde nun anfangen, mit Papier und Bleistift durch den Code zu steppen, um herauszufinden was das Konzept hinter diesem Teil der Implementierung ist. Vielleicht koenntest du diesen Schritt durch einen passenden Kommentar teilweise ersparen.)

Nun, wenn es zum Verständnis Kommentare braucht, ist schon einmal etwas schlecht am Code, finde ich. Den Puffer brauche ich nur für die Ersetzung der Auslassungspunkte (...) und Gedankenstriche (--). Wenn getchar() einen Punkt oder ein Minus einliest, darf ich das Zeichen nicht direkt ausgeben, da schliesslich noch einmal zwei Punkte bzw. ein Minus folgen könnte(n). Und darum behalte ich diese Zeichen im Puffer. Und sobald dort der dritte Punkt bzw. das zweite Minus hineingekommen ist, kann ich das Zeichen für die Auslassungspunkte bzw. den Gedankenstrich ausgeben und den Puffer verwerfen. Wenn aber jetzt beispielsweise nur ein Punkt reinkommt und dann ein Schlusszeichen, dann muss ich den Puffer so ausgeben, wie er ist. Ansonsten wäre das Programm auch nur halb so lang.

[Meillo]

Zum Verstaendnis (hab nur kurz quer gelesen): Ich hab eine Weile gebraucht, zu verstehen, was buf[BUF_SIZE] ist. Eine sprechenderer Name, wie z.B. context[CTX_SIZE] oder lookahead[NLOOKAHEAD] haette hier das Verstaendnis erleichtert.

Es ist viel eher ein "look behind" als ein "look ahead". Wie wäre es mit "input_buf" oder "input_queue"? Oder halt einfach "lookbehind"?

Hmm, ich stelle fest, ich habe noch nicht verstanden, was die Idee von buf[] und put_retaining() ist. Vielleicht waere es sinnvoll, den Ansatz grob in einem Kommentar darzulegen ... koennte beim Codeverstaendnis helfen. (Das was ich sehe entspricht keinem mir bekannten Ansatz (oder ich sehe es nur nicht). Ich wuerde nun anfangen, mit Papier und Bleistift durch den Code zu steppen, um herauszufinden was das Konzept hinter diesem Teil der Implementierung ist. Vielleicht koenntest du diesen Schritt durch einen passenden Kommentar teilweise ersparen.)

Nun, wenn es zum Verständnis Kommentare braucht, ist schon einmal etwas schlecht am Code, finde ich. Den Puffer brauche ich nur für die Ersetzung der Auslassungspunkte (...) und Gedankenstriche (--). Wenn getchar() einen Punkt oder ein Minus einliest, darf ich das Zeichen nicht direkt ausgeben, da schliesslich noch einmal zwei Punkte bzw. ein Minus folgen könnte(n). Und darum behalte ich diese Zeichen im Puffer. Und sobald dort der dritte Punkt bzw. das zweite Minus hineingekommen ist, kann ich das Zeichen für die Auslassungspunkte bzw. den Gedankenstrich ausgeben und den Puffer verwerfen. Wenn aber jetzt beispielsweise nur ein Punkt reinkommt und dann ein Schlusszeichen, dann muss ich den Puffer so ausgeben, wie er ist. Ansonsten wäre das Programm auch nur halb so lang.

Diese Erklaerung war aeusserst hilfreich. Solche konzeptionellen Kommentare finde ich bei Code sehr sinnvoll. Ich gehoere nicht zu denen, die meinen, dass Code keine Kommentare haben sollte. Und manche Arten vom Kommentaren kann man auch mit viel Anstrengung nicht unnoetig machen. Aber ich sehe es schon auch so, dass man versuchen sollte, den Code so aussagekraeftig oder so erwartungsgemaess zu gestalten, dass Kommentare weitgehend ueberfluessig werden.

Dein Ansatz hier ist, nachdem ich deine Beschreibung nun gelesen habe, nachvollziehbar und sinnhaft. Auf diesen Ansatz waere ich selber aber eher nicht gekommen. Darum hatte ich erstmal Verstaendnisprobleme. (Das was du hast ist uebrigens tatsaechlich ein Puffer im klassischen Sinn, insofern ist die Benennung treffend.) Wie du an meinen Anmerkungen sehen kannst, haette ich eher die Umsetzung eines Lookaheads erwartet, also das Vorauslesen der naechsten paar Zeichen um das aktuelle zu entscheiden, statt wie in deinem Fall, die Zeichen erstmal in den Puffer zu schieben und dort evtl. nochmal zu veraendern bevor sie ausgegeben werden. (Ein Lookback ist das uebrigens nicht, weil du nicht nur schaust sondern auch darin rumaenderst.) Ich nehme mir gerne die Freiheit, zu behaupten, dass der Lookahead-Ansatz klarer, simpler und verbreiteter ist. ... du wolltest ja sowieso das C-Programmieren ueben.

[paedubucher]

Diese Erklaerung war aeusserst hilfreich. Solche konzeptionellen Kommentare finde ich bei Code sehr sinnvoll. Ich gehoere nicht zu denen, die meinen, dass Code keine Kommentare haben sollte. Und manche Arten vom Kommentaren kann man auch mit viel Anstrengung nicht unnoetig machen. Aber ich sehe es schon auch so, dass man versuchen sollte, den Code so aussagekraeftig oder so erwartungsgemaess zu gestalten, dass Kommentare weitgehend ueberfluessig werden.

Genau das meinte ich. Leider ist es nicht immer möglich, solchen aussagekräftigen Code zu schreiben. Es ist halt ein Ideal. Die Kommentare, die ich eingefügt habe, die erklären, was denn der jeweilige Programmzweig macht, verabscheue ich eigentlich. Aber dennoch helfen sie dabei, die Übersicht zu behalten.

Wie du an meinen Anmerkungen sehen kannst, haette ich eher die Umsetzung eines Lookaheads erwartet, also das Vorauslesen der naechsten paar Zeichen um das aktuelle zu entscheiden, statt wie in deinem Fall, die Zeichen erstmal in den Puffer zu schieben und dort evtl. nochmal zu veraendern bevor sie ausgegeben werden.

Das ist natürlich auch eine Möglichkeit. Ich habe das nicht in Betracht gezogen, weil ich mir zu Beginn noch gar nicht über das geschilderte Problem im Klaren war. Und ein Vorauslesen bedarf natürlich weiterer "!= EOF"-Prüfungen, was aber zu einer wesentlich geringeren Komplexität führen würde, als ich sie jetzt habe.

(Ein Lookback ist das uebrigens nicht, weil du nicht nur schaust sondern auch darin rumaenderst.) Ich nehme mir gerne die Freiheit, zu behaupten, dass der Lookahead-Ansatz klarer, simpler und verbreiteter ist. ... du wolltest ja sowieso das C-Programmieren ueben.

Im Puffer selber ändere ich nichts. Ich gebe alles direkt aus. Den Lookahead-Ansatz werde ich aber bei Gelegenheit auch versuchen. Und dann lasse ich die beiden Programme einmal gegeneinander antreten. Ein Puffer für vier Zeichen ist für einen Java-Programmierer natürlich vernachlässigbar, das Durchschieben des Puffers bei jedem eingelesenen Zeichen ist jedoch in den meisten Fällen völlig unnötig.

Dann hätte ich noch eine ideologische Frage
Die meisten Tools lassen sich mit "tool dateiname" aufrufen. Dazu muss ich aber Parameterhandling und das Einlesen der Datei selber implementieren. Das sind vielleicht noch einmal 10 Zeilen, also nicht sonderlich tragisch, aber meiner Meinung nach ist das dennoch unnötige Komplexität, da ich das Programm ja auch als "tool <dateiname" aufrufen kann. Was würdest du in diesem Fall machen?
Andererseits will ich ja auch wieder etwas C lernen, von daher sollte ich jetzt nicht so faul sein

[Meillo]

Diese Erklaerung war aeusserst hilfreich. Solche konzeptionellen Kommentare finde ich bei Code sehr sinnvoll. Ich gehoere nicht zu denen, die meinen, dass Code keine Kommentare haben sollte. Und manche Arten vom Kommentaren kann man auch mit viel Anstrengung nicht unnoetig machen. Aber ich sehe es schon auch so, dass man versuchen sollte, den Code so aussagekraeftig oder so erwartungsgemaess zu gestalten, dass Kommentare weitgehend ueberfluessig werden.

Genau das meinte ich. Leider ist es nicht immer möglich, solchen aussagekräftigen Code zu schreiben. Es ist halt ein Ideal. Die Kommentare, die ich eingefügt habe, die erklären, was denn der jeweilige Programmzweig macht, verabscheue ich eigentlich. Aber dennoch helfen sie dabei, die Übersicht zu behalten.

Ich finde die momentan vorhandenen Kommentare keinesfalls verabscheuungswuerdig, sondern vielmehr sinnvoll eingesetzt. Jetzt noch zu Beginn ein mehrzeiliger Kommentarblock, der das verwendete Verfahren konzeptionell beschreibt, dann faende ich die Kommentierung passend.

Und ein Vorauslesen bedarf natürlich weiterer "!= EOF"-Prüfungen

Nicht unbedingt. Wenn du statt getchar(3) eine eigene getchar_buffererd() verwendest. Die gepufferte Variante schiebt das EOF nur durch. Dann waere als Lookahead vielleicht eine Funktion char *lookahead(int numchars) hilfreich, die du dann etwa so nutzen koenntest: if (strncmp("...", lookahead(3), 3)==0) {...}. Auf diese Weise waere die Pufferung dann in die beiden Funktionen getchar_buffered() und lookahead() gekapselt. (Du greifst momentan aus dem sonstigen Code direkt in den Puffer rein, hast also keine Kapselung des Puffers ... was bei deinem kleinen Programm aber auch kein zu grosses Problem ist.)

(Ein Lookback ist das uebrigens nicht, weil du nicht nur schaust sondern auch darin rumaenderst.) Ich nehme mir gerne die Freiheit, zu behaupten, dass der Lookahead-Ansatz klarer, simpler und verbreiteter ist. ... du wolltest ja sowieso das C-Programmieren ueben.

Im Puffer selber ändere ich nichts. Ich gebe alles direkt aus.

Ja, mein Fehler.

Wenn ich jetzt nochmal drueber nachdenke, dann wird das wohl in beiden Faellen ziemlich aehnlich sein, nur halt jeweils nur anders rum.

Den Lookahead-Ansatz werde ich aber bei Gelegenheit auch versuchen.

Ich beobachte und kommentiere deine Versuche gerne weiter. (Ob ich selber noch dazu komme, eine Variante zu implementieren, kann ich noch nicht sagen.)

Dann hätte ich noch eine ideologische Frage
Die meisten Tools lassen sich mit "tool dateiname" aufrufen. Dazu muss ich aber Parameterhandling und das Einlesen der Datei selber implementieren. Das sind vielleicht noch einmal 10 Zeilen, also nicht sonderlich tragisch, aber meiner Meinung nach ist das dennoch unnötige Komplexität, da ich das Programm ja auch als "tool <dateiname" aufrufen kann. Was würdest du in diesem Fall machen?

Sehe ich auch so, dass es doof ist, dass man diese allzu uebliche Sache kompliziert und fehleranfaellig selbst implementieren muss. getopt(3) ist leider nicht so der riesen Hit. Das ist z.B. etwas, das ich an Perl liebe: while (<>) {...} -- es tut einfach das Richtige.

Da du fragst, was ich denke, wie es sein sollte: Unix Filter sollten von den als Argumente uebergebenen Dateien lesen oder von Stdin, falls keine uebergeben wurden. (Wenn `-' uebergeben wurde, sollte an dieser Stelle von Stdin gelesen werden.)

Es gibt nur wenige Filter, denen man keine Dateien als Argumente uebergeben kann, tr(1) ist das klassische Beispiel. Dort liegt es aber daran, dass man sonst nicht zwischen dem optinalen SET2 und einem optionalen Dateinamenargument unterscheiden koennte. Man haette also die Set-Angabe aendern muessen.

[paedubucher]

Ich habe jetzt eine Version komplett ohne Puffer geschrieben. Es geht zwar schon in die Richtung Spaghetticode, aber es hält sich noch im Rahmen. Jetzt brauche ich nur noch das Filehandling zu schreiben.
Das neue Programm scheint auch ca. 10% schneller zu laufen als das alte, wobei solche amateurhaften Messungen immer mit Vorsicht zu geniessen sind. Die Performancesteigerung ist aber durchaus nachvollziehbar.

[paedubucher]

Ich habe jetzt eine Version komplett ohne Puffer geschrieben. Es geht zwar schon in die Richtung Spaghetticode, aber es hält sich noch im Rahmen. Jetzt brauche ich nur noch das Filehandling zu schreiben.
Das neue Programm scheint auch ca. 10% schneller zu laufen als das alte, wobei solche amateurhaften Messungen immer mit Vorsicht zu geniessen sind. Die Performancesteigerung ist aber durchaus nachvollziehbar.

Das Programm funktioniert leider nicht korrekt. Wenn nach einem Punkt ein Schlusszeichen kommt, darf das nicht einfach ausgegeben werden, es muss durch die gleiche Logik laufen. Darum habe ich den Ansatz wieder verworfen.

Darum jetzt zu meillos lookahead-Ansatz und etwas Programmier-Pädagogik

Ich habe einen kleinen Puffer, der immer einige Zeichen aufnehmen kann.

Code: Alles auswählen

#define LOOKAHEAD 10
int buf[LOOKAHEAD];
int buf_i;

buf_i ist immer der aktuelle Index, wo als nächstes geschrieben werden kann. Gelesen soll nur von der Stelle 0 werden. Nun habe ich drei Funktionen:

Code: Alles auswählen

int buf_getchar();
void buf_discard(int n);
char *buf_next(int n);

Die erste ist ein getchar, das mit einem Puffer arbeitet, dazu gleich. Die zweite schiebt den Puffer um n Stellen nach links, rechts wird mit 0 aufgefüllt.

Code: Alles auswählen

void buf_discard(int n)
{
    int i;

    while (n--) {
        for (i = 0; i < LOOKAHEAD - 1; i++) {
            buf[i] = buf[i + 1];
        }
        buf[i] = 0;
        buf_i--;
    }
}

Die dritte Funktion gibt die nächsten n Zeichen des Puffers zurück. Wenn zu wenig da ist, enthält der String eben den Wert 0 für die übrigen Stellen.

Code: Alles auswählen

char *buf_next(int n)
{
    int i;
    char *str = (char*)malloc(sizeof(char) * n);
    for (i = 0; i < n; i++) {
        str[i] = (i < buf_i) ? buf[i] : 0;
    }
    return str;
}

Nun kommt das Hauptproblem: buf_getchar():

Code: Alles auswählen

int buf_getchar()
{
    int c;

    if (buf_i > 0) {
        c = buf[0];
        buf_discard(1);
        return c;
    } else {
        do {
            c = getchar();
            buf[buf_i++] = c;
        } while (c != '\n' && c != EOF && buf_i < LOOKAHEAD);
    }
    c = buf[0];
    buf_discard(1);
    return c;
}

Wenn der Buffer nicht leer ist (buf_i > 0), wird das Zeichen links vom Puffer unter c abgespeichert, der Puffer einmal nach links durchgeschoben, und c zurückgegeben. Wenn hingegen noch nichts im Puffer ist, wird soviel eingelesen, wie möglich (bis zu EOF, \n oder halt, bis der Puffer voll ist). Nach dem erfolgten Einlesen wird nun wiederum das Zeichen ganz links zurückgegeben und der Puffer nach links durchgeschoben.
Nun stehe ich vor einem Henne-Ei-Problem: Wenn der Puffer etwas drin hat, aber noch nicht voll ist, sollte ich ja zunächst probieren, noch etwas hineinzulesen, bevor ich ihn aufbrauche. Der Puffer soll ja immer soviel laden, wie möglich. Ob etwas zu lesen ist weiss ich aber erst, wenn ich getchar() aufrufe. Und wenn ich das tue, aber nichts zu lesen ist, bleibt das ganze dort hängen.
Ich müsste ja irgendwie herausfinden können, ob da noch was zu lesen ist. Soll ich mir merken, warum das puffern abgebrochen wurde? Wenn es durch \n bzw. EOF war, dann ist halt nichts mehr zu lesen, wenn es aber durch Erreichen der Pufferlänge war, soll ich versuchen weiterzulesen? Das könnte ein Ansatz sein...
Oder sollte ich einfach einen input-Buffer bauen, der sich laufend vergrössert, sodass er immer die ganze Zeile halten kann?

[paedubucher]

Soll ich mir merken, warum das puffern abgebrochen wurde? Wenn es durch \n bzw. EOF war, dann ist halt nichts mehr zu lesen, wenn es aber durch Erreichen der Pufferlänge war, soll ich versuchen weiterzulesen? Das könnte ein Ansatz sein...

Einmal das Problem ausformuliert, einmal kurz probiert, und schon habe ich eine Lösung:

Code: Alles auswählen

bool buf_finished;
/* ... */
int buf_getchar()
{
    int c;

    if (buf_finished && buf_i) {
        c = buf[0];
        buf_discard(1);
        return c;
    } else {
        do {
            c = getchar();
            buf[buf_i++] = c;
            buf_finished = (c == '\n' || c == EOF);
        } while (!buf_finished && buf_i < LOOKAHEAD);
    }
    c = buf[0];
    buf_discard(1);
    return c;
}

Wenn als letztes Zeichen \n oder EOF eingelesen wurde, muss nichts mehr gepuffert, sondern darf nur noch "konsumiert" werden. Wenn das Einlesen hingegen aufgrund eines vollen Puffers beendet wurde, muss da noch etwas zum Einlesen sein. Dann kann ich problemlos weiterlesen. Scheint zu klappen...
Hier noch der ganze Code.

Nachtrag: Jetzt habe ich das zum Vergleich noch mit sed implementiert:

Code: Alles auswählen

s/\.\.\./…/g
s/--/‒/g
s/ '/ ‹/g
s/^'/‹/g
s/'/›/g
s/"'/«‹/g
s/ "/ «/g
s/^"/«/g
s/"/»/g

Und einen kleinen Performance-Test dazu geschrieben, der jeweils 4 Millionen Zeilen verarbeitet:

Code: Alles auswählen

#!/bin/bash

echo "testing C implementation"
time ./smart_quotes <test-1m.txt >out.txt

echo -e "\ntesting sed implementation"
time sed -f smart_quotes.sed test-1m.txt >out.txt

Und hier ist das Ergebnis (mit musl-gcc, statisch):

Code: Alles auswählen

testing C implementation

real    0m10.929s
user    0m9.120s
sys     0m0.780s

testing sed implementation

real    0m15.695s
user    0m13.664s
sys     0m0.428s

Mit -O3 komme ich sogar auf 7.8 Sekunden runter. Ein Performance-Gewinn von 50-100%.