Gerichtete Graphen mit SQL lösen – Teil 2

von Scott Stephens am 29. Juli 2004 , 09:40 Uhr

Diese Tabelle A kann verwendet werden, um in verschiedenen Programmiersprachen Code zu erzeugen, der Zeichen aus Strings effizient verarbeitet. Der einzige Code, der in einem Erkennungsprogramm verwendet wird, ist die „accept“-Spalte der Tabelle mit den Zuständen und die Spalten für Eingabe (input) und den nächsten Zustand (next state) aus der Tabelle mit den Übergängen. Hier ein Beispiel in C:

#include <stdio.h> 
typedef struct state state; 
typedef struct trans trans; 
struct state 
{ 
int accept; /* Token-Wert oder 0 */ 
int offset; /* Offset für die Tabelle der Übergänge */ 
int count; 
}; 
struct trans 
{ 
char input; /* Eingabezeichen */ 
int next; /* nächster Zustand */ 
}; 
state statetbl[8] = 
{ 
{0,0,1}, /* 0: Ausgangszustand */ 
{0,1,3}, /* 1: Zustand ‚A‘ */ 
{0,4,1}, /* 2: Zustand ‚AA‘ */ 
{0,5,1}, /* 3: Zustand ‚AB‘ */ 
{0,6,1}, /* 4: Zustand ‚AS‘ */ 
{1,7,0}, /* 5: Zustand ‚AAA‘ */ 
{2,7,0}, /* 6: Zustand ‚ABC‘ */ 
{3,7,0}, /* 7: Zustand ‚ASC‘ */ 
}; 
trans trantbl[7] = 
{ 
{‚A‘,1}, /* 0: Ausgangszustand -> ‚A‘ */ 
{‚A‘,2}, /* 1: ‚A‘ -> ‚AA‘ */ 
{‚B‘,3}, /* 2: ‚A‘ -> ‚AB‘ */ 
{‚S‘,4}, /* 3: ‚A‘ -> ‚AS‘ */ 
{‚A‘,5}, /* 4: ‚AA‘ -> ‚AAA‘ */ 
{‚C‘,6}, /* 5: ‚AB‘ -> ‚ABC‘ */ 
{‚C‘,7}, /* 6: ‚AS‘ -> ‚ASC‘ */ 
}; 
/* Bei Eingabe des aktuellen Zustands und des Eingabezeichens wird der nächste Zustand zurückgegeben. */ 
int move(int state,char input) 
{ 
int i; 
for (i = 0;i<statetbl[state].count;i++)
{
if (trantbl[statetbl[state].offset+i].input == input)
return trantbl[statetbl[state].offset+i].next;
}
return -1; /* unbekannter Übergang */
}
int main(int argc,char* argv[])
{
int i,next,state;
if (argc < 2)
{
fprintf(stderr,"Usage: %s "tokens..."n",argv[0]);
return 1;
}
/* erstes Argument parsen */
state = 0;
for (i=0;argv[1][i];i++)
{
next = move(state,argv[1][i]);
if (next == -1) state = 0;
else
{
state = next;
if (statetbl[state].accept)
printf("recognized token#%dn",statetbl[state].accept);
}
}
return 0;
}

Daraufhin lässt sich das Programm ausführen: es gibt die erkannten Token auf der Kommandozeile aus:

Inhalt

Gerichtete Graphen mit SQL lösen – Teil 2

Neueste Kommentare

Noch keine Kommentare zu Gerichtete Graphen mit SQL lösen – Teil 2

Vielen Dank für Ihren Kommentar.
Ihr Kommentar wurde gespeichert und wartet auf Moderation.

Schreibe einen Kommentar Antworten abbrechen

Neueste Kommentare

Noch keine Kommentare zu Gerichtete Graphen mit SQL lösen – Teil 2

Vielen Dank für Ihren Kommentar.Ihr Kommentar wurde gespeichert und wartet auf Moderation.

Schreibe einen Kommentar Antworten abbrechen

Vielen Dank für Ihren Kommentar.
Ihr Kommentar wurde gespeichert und wartet auf Moderation.