3. RegEx-Engine in C

RegEx-Engine in C

  • ?

    Hallo Leute!

    Ich habe vor, einen regular Expression Compiler und Interpreter in C zu schreiben.

    Allerdings verstehe ich nicht, wie ich den Thompson-Algorithmus in C umsetzen kann, d.h. eine Liste von Nichtdeterministisch Endlichen Automaten aus einer Regular Expression erzeugen, den ich dann an den Interpreter weitergebe.

    Beispiel ist folgender, regulärer Audruck:

    *a(bc|de)f

    wie sehen hierfür die NFAs aus? Wie muss ich diesen Ausruck auswerten und die NFAs generieren?

    Ich habe zwar ein Beispiel auf http://www.codeguru.com/cpp/cpp/cpp_mfc/parsing/article.php/c4093/ gefunden (der eine Stack dafür verwendet) aber da ist bei mir irgend ein Logikfehler im Kopf, der mir an folgendem Problem zu schaffen macht:

    Wie erstelle ich einen Atomaten, der die Regular Expression (bc|df)* erkennt? Bei (a|b) ist es für mich noch nachvollziehbar, nicht aber bei mehreren Zeichen, da ja beide mit einem OR verknüft sind.

    UND NEIN: Ich will nicht auf Libraries wie POSIX zugreifen, da ich es wirklich verstehen und lernen will!

    Vielleicht könnt ihr mir helfen!!!

    Karl

    0
  • C

    Zuerst kannst du aus dem Ausdruck einen ε-NFA bauen:

    Aus den Terminalzeichen werden entsprechende Elementar-Automaten:

    a:

 S-(a)-E

    Aus der Konkatenation wird eine Nacheinanderausführung:

    A.B:

    +-----+  +-----+
 S--|  A  |--|  B  |--E
    +-----+  +-----+

    Aus der Alternative wird eine Parallelschaltung:

    a|b:

    +-----+
   -|  A  |-
  / +-----+ \
 S           E
  \ +-----+ /
   -|  B  |-
    +-----+

    Aus dem Kleene-Stern wird eine Rückkopplung:

    A*:

   +---------+
   v +-----+ |
 S-+-|  A  |-+
   | +-----|
   E

    (die einzelnen Verbindungen sind jeweils ε-Kanten zum S- bzw. vom E-Knoten des jeweiligen Teilgraphen)

    Womöglich kannst du diese Graphen schon so verwenden, wenn nicht, mußt du noch die ε-Kanten überbrücken.

    0
  • ?

    Hallo CStoll,

    wow danke erstmal für die schnelle Antwort.

    Das habe ich auch soweit schon verstanden, ich hab aber probleme, diese Logik in ein C-Programm - sprich den Compiler - umzusetzen.

    Ich muss mir ja quasi für jedes Zeichen das ich aus dem Ausdruck lese einen Automaten erzeugen - das ist klar. Aber WAS benötigt dieser Automat für Informationen? Muss ich den Automaten als dynamischen Baum aufbauen wie es diese Graphen beschreiben?

    Wie würde eine C-Struktur für solch eine Automatendefinition aussehen??

    Da hapert's bei mir immoment echt mit der logik. Kann auch sein, daß ich den Wald vor lauter Bäumen nicht sehe...

    Gruss,
    Karl69

    0
  • C

    Ohne Garantie (ich hab' mit NFA's und DFA's bisher nur theoretisch gearbeitet

    tyepdef struct NODE
{
  int out;            //Anzahl Nachfolger
  char* outc;         //Beschriftung der rausgehenden Kanten
  struct NODE** outn; //Nachfolger
} node;

void initnode(node* x,int nf)
{
  x->out=nf;
  x->outc=malloc(nf);
  x->outn=malloc(nf*sizeof(node*);
}

    (in outn speicherst du die Adressen der Nachfolger, in outc die zugehörigen Zeichen)

    bool parse(node* start, char* txt)
{
  if(start->out==0 && *txt==0) //Endzustand erreicht
    return true;
  bool ret=false;
  for(int i=0;i<start->out;++i)
  {
    if(start->outc[i]=='\0') // eps-Kante
      ret=parse(start->outn[i],txt);
    else if(start->outc[i]==*txt) //normale Kante
      ret=parse(start->outn[i],txt+1);
    if(ret) return true;
  }
  return false;
}
    0
  • ?

    Hi CStoll,

    Cool, einen ähnlichen Ansatz habe ich auch gehabt, jedenfalls von der Strukur her.
    Auch deine parse() Funktion ist für's erste sehr nützlich.

    Allerdings bist du noch einen Schritt zu weit. Mein Problem besteht nämlich darin, daß ich ja erstmal einen Automaten aus der Regular Expression compilieren muß.

    Mein Compiler sieht derzeit so aus, allerdings funktioniert er nicht so, wie er eigentlich soll. Ich weis auch wo das Problem liegt, mich würde aber in erster Linie interessieren, ob der Ansatz überhaupt Sinn macht.

    typedef struct NFA
{
	int			pnum;	/* Number of Possibilities */
	char*		pchr;	/* Next possible characters */
	struct NFA*	pnfa;	/* NFAs for next possibilities */ 
} nfa;

void indent( int i )
{
	for( ; i > 1; i-- )
		printf("\t");
}

char* compile( nfa* n, char* exp )
{
	char	*p;

	static	int	recoursion	= 0;

	n->pnum = 0;

	recoursion++;
	indent(recoursion);
	printf("starting compile() at >%s<\n", exp);
	getchar();

	p = exp;
	while( *p != '\0' )
	{
		indent(recoursion);
		printf("Reading character: >%c<\n", *p );

		switch( *p )
		{
			case '|':

				indent(recoursion);
				printf("leaving compile() with pointer to >%c<\n", *p);
				recoursion--;

				return p;

			default:	
				if( n->pnum == 0 )
				{
					n->pchr = (char*)malloc( sizeof(char) );
					n->pnfa = (nfa*)malloc( sizeof(nfa) );
				}
				else
				{
					n->pchr = (char*)realloc( (char*)n->pchr, 
								(n->pnum+1) * sizeof( char ) );
					n->pnfa = (nfa*)realloc( (nfa*)(n->pnfa), 
								(n->pnum+1) * sizeof( nfa ) );
				}
				n->pchr[ n->pnum ] = *p;

				p = compile( &(n->pnfa[ n->pnum ]), p + 1 );

				printf("backj...");

				n->pnum++;

				break;
		}
	}

	indent(recoursion);
	printf("leaving compile() with pointer to >%c<\n", *p);
	recoursion--;

	return p;
}

int main( int argc, char** argv )
{
	nfa machine;

	compile( &machine, "abc|b" );

	printf("ok");
	getchar();

	return 0;

}

    Das Problem ist bei der Regular Expression abc|b natürlich, daß das Programm in der dritten Rekursion auf das OR stößt, und daß beendet dann natürlich alle darunter liegenden Aufrufe einschließlich des Einstiegsaufrufes.

    Hast du evtl. noch eine Idee oder einen Verbesserungsvorschlag für mich? Denn wie ich sehe hast du das im Studium gemacht, ich lerne es im selbststudium. Ich habe bisher einen kleinen mathematischen Parser geschrieben, aber irgendwie werde ich nicht Schlau daraus, wenn ich diesen mathematischen Parser auf meine regular Expressions übertragen will.

    Grüße
    Karl69

    0
  • C

    Wenn du mit C++ arbeiten kannst, empfehle ich dir Boost::Spirit (siehe auch im Magazin), ansonsten gibt es noch Lex.

    0
  • ?

    CStoll schrieb:

    Wenn du mit C++ arbeiten kannst, empfehle ich dir Boost::Spirit (siehe auch im Magazin), ansonsten gibt es noch Lex.

    Hmm ja aber ich hatte doch erwähnt das ich das Teil selber hand-codieren will, ohne Lex/Yacc/Sonstwas. Der Ansatz ist doch m.E. richtig, oder sehe ich das falsch?

    Gruß
    Karl69

    0
  • C

    Ich vermute mal, deine Behandlung für | ist noch nicht richtig ausgereift - aber auf Anhieb fällt mir auch nichts ein, wie man das elegant lösen kann.

    PS: Wichtig ist nur, daß du bei Sonderzeichen ('|', '*', Klammern) nicht die komplette Rekursion beendest, sondern nur bis zur "richtigen" Stelle zurückläufst und dort weitermachst. Im Fall | bedeutet das: baue den Teilautomaten für den zweiten Operanden auf und klebe ihn mit dem vorhandenen Automaten für den ersten Operand zusammen.

    0
Anmelden zum Antworten