Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Mehrere meiner Programme haben eine Suchfunktion, die zwar halbwegs funktioniert, aber nicht perfekt ist. Da werden dann mehrere Begriffe auf mehrere Spalten angewendet. Dabei kann jeder Begriff ein Regulärer Ausdruck sein. Aber jetzt brauche ich etwas, dass auch für eine Volltextsuche brauchbar ist. Da bin ich jetzt auf die Idee gekommen so etwas als mathematische Formel auszudrücken. Etwa so:
Text-A UND (Text-B ODER Text-C)
oder
Text-A NOT Text-B
Da das Programm mäßig nicht einfach auszuwerten ist, dachte ich mir, das man so einen Ausdruck mit dem Shunting-yard-Algorithmus in UPN umwandeln könnte, was leichter auszuwerten ist. Dabei ist noch nicht klar, wie die Operatoren (farbig hinterlegt) und die Klammern aussehen sollten, um nicht mit den Regulären Ausdrücken zu kollidieren. Die Fragen sind jetzt, kann das funktionieren und was muss ich dabei berücksichtigen. Gibt es dazu evtl. schon entsprechende Anleitungen, an denen ich mich orientieren kann?
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12832
|
Ich bin nicht sicher, dass die Umwandlung in UPN und folgende Auswertung wirklich weniger aufwändig sind, als einen Parser für die Ausdruckssprache zu bauen. Mit ANTLR geht das recht gut und es gibt sogar eine IDE, mit der man Syntax testen und simulieren kann. (Hoffentlich gibt's die wirklich noch - ist schon eine Weile her, dass ich damit mal herumgespielt habe.) Zu der Frage, ob das überhaupt geht: Du musst halt die Tokens der Sprache so definieren, dass sie eindeutig erkannt und voneinander unterschieden werden können. Am Einfachsten definierst Du reguläre Ausdrücke so, dass die einen bestimmten Präfix haben, z.B. "/", wie das in vielen Sprachen vorkommt. Wenn Du auch reinen Text zum Erkennen benutzen willst, kannst Du den dann z.B. mit doppelten Anführungsstrichen einfassen. Das ist sowieso gut, weil Du sonst Text mit Leerzeichen schlecht erkennen kannst.
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
So einen Parser hatte ich schonmal gebaut. Und obwohl ich dazu den gut kommentierten Quelltext des Palo Alto Tiny BASICs vorliegen hatte, fand ich das recht aufwändig. Mein jetziger Anwendungsfall ist wahrscheinlich einfacher. Es gibt nur AND, OR, NOT und die Klammern. Und gerade die Klammern will ich loswerden. Ich brauche sie aber um Bedingungen zusammenzufassen.
Und das Ergebnis kann kann nur 0 oder 1 sein (ungültig ist auch 0). Heute Morgen ist mir die Idee gekommen, zur Auswertung einen Kellerautomaten zu nehmen. Der sieht nicht sehr kompliziert aus. In einer alten Anwendung (Liste mit Spalten) hatte ich die aufbereiteten Operanden so gespeichert:
| typedef struct {
int valid; // flag, needed for regfree
int field; // fieldindex
int mode; // Verknüpfungsmodus
int flag; // Flags for regex
char * src; // searchpattern text
regex_t regex;
} Src_Data;
|
und davon bis zu 16 Stück. Aber das funktioniert eigentlich nur als UND Verknüpfung gut. Der Verknüpfungsmodus (Operator) gehört da nicht hin! Kummer bereiten mir noch die Klammern, da diese ja auch in den Regulären Ausdrücken vorkommen. Und ich möchte ungern darauf verzichten so etwas als Suchbegriff eingeben zu können:
Ma[i,y]
Das komplizierteste ist wohl, die Regulären Ausdrücke und die Vernüpfungen der verschiedenen Suchmuster zu trennen.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12832
|
Dakuan schrieb: So einen Parser hatte ich schonmal gebaut. Und obwohl ich dazu den gut kommentierten Quelltext des Palo Alto Tiny BASICs vorliegen hatte, fand ich das recht aufwändig.
Ich weiß nicht, wie das implementiert ist, aber mit einem Tool wie ANTLR geht so etwas recht gut.
Mein jetziger Anwendungsfall ist wahrscheinlich einfacher. Es gibt nur AND, OR, NOT und die Klammern. Und gerade die Klammern will ich loswerden.
Das geht nicht, weil Du automatisch nur eine Präzedenz definieren kannst.
Und das Ergebnis kann kann nur 0 oder 1 sein (ungültig ist auch 0).
Macht ja nix.
Kummer bereiten mir noch die Klammern, da diese ja auch in den Regulären Ausdrücken vorkommen. Und ich möchte ungern darauf verzichten so etwas als Suchbegriff eingeben zu können:
Ma[i,y]
Das sind jetzt aber nicht die Klammern, die Du für die Kontrolle der Präzedenz benutzt willst. Von daher, kein Problem.
Das komplizierteste ist wohl, die Regulären Ausdrücke und die Vernüpfungen der verschiedenen Suchmuster zu trennen.
s.o. Du kannst ja auch && und || statt UND und ODER nehmen, was deutlich unwahrscheinlicher als gewünschter Suchtext sein könnte (kenne ja die Details Deines Anwendungsfalls nicht). Das hätte auch noch den Vorteil, dass niemand auf die Idee käme, das zu lokalisieren. ☺
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Ich weiß nicht, wie das implementiert ist, ...
Das war damals Assembler Quelltext. Vor den entsprechender EXPR Funktionen war dann eine Liste mit BNF Definitionen (sehr gewöhnungsbedürftig). ANTLR sieht interessant aus, erfordert aber wohl einiges an Einarbeitungszeit.
Das geht nicht, weil Du automatisch nur eine Präzedenz definieren kannst.
Dann sollte ich vielleicht versuchen direkt in UPN einzugeben. Wenn ich zwischen den einzelnen Regex-Ausdrücken eine UND Verknüpfung annehme, muss ich nur selten zusätzlich etwas eingeben. Bei den Klammern dachte ich eigentlich an die geschweiften. Die sind zwar auch reserviert, aber immer wenn ich damit etwas machen wollte, habe ich einen Fehler bekommen. Deswegen benutze ich die hierfür nicht mehr.
(kenne ja die Details Deines Anwendungsfalls nicht).
Das sind viele kurze und wenig lange Texte. Wenn ich da nach Begriffen suche, die häufig vorkommen, benötige ich einige Ausschlusskriterien, sonst muss ich wieder 1000 Dateien zu Fuß durchsuchen. p.s. die Verwendung von &&, || oder !! als Operatoren gefällt mir.
Das hätte auch noch den Vorteil, dass niemand auf die Idee käme, das zu lokalisieren.
Lokalisierung kommt bei mir nicht vor.
|
Cranvil
Anmeldungsdatum: 9. März 2019
Beiträge: 990
|
Ich habe da bisher noch nicht mit herumspielen können, aber bietet es sich evtl. an, die Dateien in eine SQLite-Datenbank zu packen und dort ein Plugin für die Volltextsuche zu verwenden (Link)?
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
... aber bietet es sich evtl. an, die Dateien in eine SQLite-Datenbank zu packen und dort ein Plugin für die Volltextsuche zu verwenden (Link)?
Könnte ich so machen. Aber das war nicht die Frage und einfacher sieht das auch nicht aus. Ich betrachte das Programmieren als eine Art Denksportaufgabe. Und solange selber programmieren noch erlaubt ist, möchte ich das eigentlich weiter betreiben (obwohl - siehe unten). Dazu kommt noch, das viele der Texte (ca. 20000) erst aus den Kommentarfeldern von Bilddateien extrahiert werden müssen. Andere sind Bestandteil meines selbstgestrickten Notizzettel Programms. Ich tendiere mehr und mehr dazu, das einmal auszuprobieren und habe daher gerade ein entsprechendes Testprogramm versucht. Dabei bin ich aber anscheinend über einen uralten gcc Bug 53119 gestolpert. Der Status fixed scheint bei Ubuntu noch nicht angekommen zu sein. Die Liste der Warnungen ist fast länger als der Quelltext. Hier mal ein Auszug:
| typedef struct {
char * src;
regex_t regex;
int regex_flags;
int count;
char type;
char field;
} FindData_t;
FindData_t accu = { 0, 0, 0, 0, OP_ACCU, 0 };
|
ergibt:
rfind.c:48:19: warning: missing braces around initializer [-Wmissing-braces]
FindData_t accu = { 0, 0, 0, 0, OP_ACCU, 0 };
^
{ }
Die weiteren Tabelleneinträge habe ich jetzt ausgelassen. Ich frage mich aber, warum das bei meinen bisherigen Programmen nicht aufgetreten ist und bin am überlegen zu meinem früheren Hobbys (Modelleisenbahn und Dampfmaschinenmodellbau) zurückzukehren. Kaputte Compiler machen jedenfalls keinen Spaß. Ob der ausgedachte Algorithmus trotzdem funktioniert, konnte ich noch nicht feststellen. Ist jetzt aber auch egal.
|
Cranvil
Anmeldungsdatum: 9. März 2019
Beiträge: 990
|
Gegen Ende des von dir verlinkten Bugs wird erwähnt, dass der Fix nur für einfache Fälle gefixt wurde und es noch komplexere Fälle (z.B. Link) gibt. Vielleicht hast du einen der komplexeren Fälle erwischt? Mangels besseren Wissens in C: Was passiert eigentlich, wenn du um die geschweiften Klammern nochmal einen Satz davon legst?
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Vielleicht hast du einen der komplexeren Fälle erwischt?
Ganz bestimmt nicht. Was ich gepostet habe ist schon der einfachste Fall (die anderen habe ich ausgeklammert). Ich benutze solche Konstrukte eigentlich schon lange ohne Probleme, allerdings nicht mit statischer Initialisierung. Die hatte ich hier nur eingesetzt, um um die ganze Eingabeprozedur und Syntaxprüfung zu umgehen. War aber wohl nicht meine beste Idee.
Was passiert eigentlich, wenn du um die geschweiften Klammern nochmal einen Satz davon legst?
Wurde auf stackoverflow auch schon vorgeschlagen, macht die Sache aber nur noch schlimmer.
rfind.c:48:1: warning: braces around scalar initializer
FindData_t accu = {{ 0, 0, 0, 0, OP_ACCU, 0 }};
^~~~~~~~~~
rfind.c:48:1: note: (near initialization for ‘accu.src’)
rfind.c:48:25: warning: excess elements in scalar initializer
FindData_t accu = {{ 0, 0, 0, 0, OP_ACCU, 0 }};
^
...
Die Warnung wird für jeden Parameter wiederholt. Aber das ist jetzt schon etwas OT. Ich muss mich jetzt erstmal beruhigen. Ob mein Algorithmus überhaupt funktioniert, kann ich erst feststellen, wenn ich den in mein Suchprogramm eingepasst und debuggt habe. Ob ich das morgen noch durchziehe weiss ich noch nicht.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12832
|
Poste doch mal die Kommandozeile des Compiler-Aufrufst. Vielleicht verwendest Du ja einfach eine ungünstige Sprachversion. Mit dem leicht modifizierten Beispiel aus dem Bug: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | $ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 18.04.3 LTS
Release: 18.04
Codename: bionic
$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ cat -n x.c
1 struct example {
2 int foo[2];
3 };
4
5 int main()
6 {
7 struct example ex = {0};
8 return ex.foo[0];
9 }
$ gcc -Wall x.c
$ gcc -ansi -Wall x.c
$ gcc -ansi -Wall -Wmissing-braces x.c
$ ./a.out
$ echo $?
0
|
Also scheint der Fix in dieser Version vorhanden.
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Ubuntu und Compiler Version sind die gleichen wie bei dir und auch das Beispiel wird kommentarlos übersetzt. Vielleicht habe ich doch etwas mit den Augen. Meine Datenfelder sind:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | #define OP_ACCU 1
#define OP_DATA 2
#define OP_AND 3
#define OP_OR 4
#define OP_NOT 5
typedef struct {
char * src;
regex_t regex;
int regex_flags;
int count;
char type;
char field; // currently not used
} FindData_t;
FindData_t input[] = {
{ "Bund", 0, 0, 0, OP_DATA, 0 },
{ "Musik", 0, 0, 0, OP_DATA, 0 },
{ 0, 0, 0, 0, OP_AND, 0 },
{ "Reaktor", 0, 0, 0, OP_DATA, 0 },
{ 0, 0, 0, 0, OP_AND, 0 },
{ 0, 0, 0, 0, 0, 0 },
};
FindData_t accu = { 0, 0, 0, 0, OP_ACCU, 0 };
FindData_t * op_stack[ MAX_STACK ];
int stack_ix = 0;
int input_cnt;
/* Funktionen folgen hier */
|
Das ergibt:
$ gcc -Wall -c -orfind rfind.c
rfind.c:37:22: warning: missing braces around initializer [-Wmissing-braces]
FindData_t input[] = {
^
{ "Bund", 0, 0, 0, OP_DATA, 0 },
{ }
...
rfind.c:37:22: warning: missing braces around initializer [-Wmissing-braces]
FindData_t input[] = {
^
{ "Bund", 0, 0, 0, OP_DATA, 0 },
{ }
{ "Musik", 0, 0, 0, OP_DATA, 0 },
{ }
{ 0, 0, 0, 0, OP_AND, 0 },
{ }
{ "Reaktor", 0, 0, 0, OP_DATA, 0 },
{ }
{ 0, 0, 0, 0, OP_AND, 0 },
{ }
{ 0, 0, 0, 0, 0, 0 },
{ }
rfind.c:46:19: warning: missing braces around initializer [-Wmissing-braces]
FindData_t accu = { 0, 0, 0, 0, OP_ACCU, 0 };
^
{ }
$
bei jeder Warnung kommt eine Zeile dazu. Vielleicht ist das doch zu kompliziert. Wenn ich die statische Initialisierung weg lasse geht es anscheinend. Da muss ich wohl extra 'ne Funktion zum initialisieren bauen, wird ja später sowiso benötigt. Übrigens, g++ scheint diesen Bug nicht zu haben. Meine statischen Menüs in der GUI funktionieren da jedenfalls.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12832
|
Das ist jetzt schwierig, weil die Zeilennummern nicht passen und das Beispiel offensichtlich auch nicht vollständig ist. Ich habe Dein letztes Beispiel mal ergänzt und die Lösung gefunden: Du musst das Muster mit dem Initialisierer rekursiv anwenden, d.h. strukturierte Felder in einer struct müssen ebenfalls entsprechend initialisiert werden. Ich habe das zweite Element einfach durch ein Array ersetzt, damit ich regex_t nicht brauchte. Ohne die Klammern beim Initialisierer bekomme ich die Fehler, die Du auch bekommst. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | #define OP_ACCU 1
#define OP_DATA 2
#define OP_AND 3
#define OP_OR 4
#define OP_NOT 5
#define MAX_STACK 19
typedef struct {
char * src;
char regex[4];
int regex_flags;
int count;
char type;
char field; // currently not used
} FindData_t;
FindData_t input[] = {
{ "Bund", {0}, 0, 0, OP_DATA, 0 },
{ "Musik", {0}, 0, 0, OP_DATA, 0 },
{ 0, {0}, 0, 0, OP_AND, 0 },
{ "Reaktor", {0}, 0, 0, OP_DATA, 0 },
{ 0, {0}, 0, 0, OP_AND, 0 },
{ 0, {0}, 0, 0, 0, 0 },
};
FindData_t accu = { 0, {0}, 0, 0, OP_ACCU, 0 };
FindData_t * op_stack[ MAX_STACK ];
int stack_ix = 0;
int input_cnt;
/* Funktionen folgen hier */
|
Das ergibt bei mir: | $ gcc -Wall -c y.c
$ ls -lt *.o
-rw-rw-r-- 1 x x 1648 Nov 10 17:14 y.o
|
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Ja, ich hatte nur die Datenfelder gepostet. Die Funktionen hatte ich weggelassen und main() war bis vor 2 Stunden auch noch nicht da. Ich wollte das als Modul in ein anderes Programm einbinden. Jetzt habe ich aber doch noch ein Minimalprogramm drumherum geschrieben, da es sich so besser debuggen lässt (sind ca. 260 Zeilen geworden).
Du musst das Muster mit dem Initialisierer rekursiv anwenden, d.h. strukturierte Felder in einer struct müssen ebenfalls entsprechend initialisiert werden.
Da wäre ich nie drauf gekommen. Das ist gut zu wissen. Dann stehe ich beim nächsten Mal nicht so hilflos da. Inzwischen habe ich aber komplett auf dynamische Initialisierung umgestellt und konnte auch schon den UPN-Evaluator etwas debuggen. Das sind für 3 Operatoren knapp 60 Zeilen geworden. UPN ist zwar etwas gewöhnungsbedürftig, aber nicht so schlimm wie befürchtet. Wenn ich das in eine GUI einbaue, kann ich die Eingabe der Operatoren, wie bei HP Taschenrechnern, auf Buttons abwälzen. Der nächste Schritt ist jetzt eine Trefferliste. Bisher Zähle ich die Treffer nur. Aber ich denke, heute sollte ich damit nicht mehr anfangen. Es ist immer gut, wenn man den Tag mit einem Erfolgserlebnis beenden kann.
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Oh man. Jetzt, bei den Aufräumarbeiten habe ich das Problem erkannt. Eigentlich hätte ich es schon vorher erkennen müssen, spätestens beim debuggen der veränderten Version. Der Debugger hat es mir ja gezeigt, aber ich hatte es nicht wahrgenommen. Der Punkt ist, dass regex_t selber eine komplexe Struktur ist. Die kann man nicht so einfach mit einer einzelnen Null initialisieren. Bei der statischen Initialisierung benötige ich aber einen Platzhalter, den ich bei der dynamischen aber einfach auslassen kann. Das ist der Unterschied. Allerdings wäre es hilfreich gewesen, wenn gcc direkt den zweiten Parameter angemeckert hätte anstatt die gesamte Struktur.
|
snafu1
Anmeldungsdatum: 5. September 2007
Beiträge: 2123
Wohnort: Gelsenkirchen
|
Das Vorinitialisieren mit Nullen ist doch gar nicht notwendig. Warum nicht einfach so?
| FindData_t accu = {.type = OP_ACCU};
|
|