Nächste Seite: Re: Artikel Debian Aufwärts: Graphen, Schaltwerke und Zahlen Vorherige Seite: Re:
/* expr ::= term | term + expr
* term ::= factor | factor * term
* factor ::= id | (expr)
*
* expr ::= term | term '|' expr
* term ::= factor | factor '*' term
* factor ::= ch | (expr)
*
* Wie wir sehen werden f"uhrt das nicht zum Ziel. Die Grammatik geht anders
*
* 1.) m"usste nach dem * auch ein | kommen k"onnen. Zur Not setzt man Klammern
*
* Aber der | Operator ist infix. Und der wiederholungsoperator ist Postfix - und hat nur einen Operanden
*
* Das heisst:
*
* expr ::= term | term '|' expr
* term ::= factor | factor '*'
* factor ::= id | (expr)
*/
/*
#include <stdio.h>
#include <stdlib.h>
char gettoken ();
void tokenback ();
void expr ();
void factor ();
void term ();
char matchexpr [] = "(((acasdasd|b)*)|c)|p";
int i = 0;
char gettoken () {
return matchexpr [i++];
}
void tokenback () {
i--;
}
void expr () {
term ();
if (gettoken () == '|')
expr ();
else
tokenback ();
return;
}
*/
/* Das geht nicht
void term () {
factor ();
if (gettoken () == '*')
term ();
else
tokenback ();
return;
}
*/
/*
void term () {
char ch;
factor ();
if ((ch = gettoken ()) == '*');
else if((ch >= 'a') \&\& (ch <= 'z')) {
tokenback ();
term ();
}
else
tokenback ();
return;
}
void factor () {
char ch = gettoken ();
if (ch == '(') {
expr ();
if (gettoken () != ')') {
fprintf (stderr, "Geschlossene Klammer vergessen");
exit (1);
}
}
else if ((ch >= 'a') \&\& (ch <= 'z'))
printf ("%cn", ch);
else {
fprintf (stderr, "Falsches Zeichen %c", ch);
exit (1);
}
return;
}
int main (void) {
expr ();
}
*/
/*
*
* Jetzt kommt der Automat. Jetzt m"ussen wir nachdenken, ohne Robert Sedgewick
* a 0 -> 0
* aa 0 -> 0
* aaa 0 -> 0 -> 0
* aaaa 0 -> 0 -> 0 -> 0
* a(a|b) 0 -> 0
* 0 -> 1
*
* Also, das erste, was wir merken, die Zeichen sind nicht unsere Zust"ande - also 'a' entspricht nicht 0 und 'b' 1
*
* a(a|b)* 0 -> 0
* 0 -> 1
* 0 -> 0 -> 0
* 0 -> 1 -> 0
* 0 -> 0 -> 1
* 0 -> 1 -> 1
*
* Also, wenn man das hintereinander schreibt
*
* a(a|b)* Da ist mir das aufgefallen
*
* Sagen wir
* abc
* dann ist a nicht der Zustand, aber es steht an Index 0
* b steht an Index 1
* c an Index 2
* Gut, der Witz bei den Automaten, es kann der eine Zustand folgen, oder der anderen. Deswegen brauchen wir einen Automaten
* Das ist logisch. wenn ich 10 Zust"ande Folgezust"ande haben k"onnte, kann ich das nach der Baumregel, auf zwei Folgezust"ande reduzieren
*
* state1 [0] = 1
* state2 [0] = 1
* state1 [1] = 2
* state2 [1] = 2
* ...
*
* So w"are das bei einer Zeichenkette wie
*
* abc
*
* Jetzt angenommen ich habe ein ODER dann kommt
*
* state1 [5] = 1
* state2 [5] = 4
*
* Ich weiss wie es geht! Bingo!
*
* Es ist ganz einfach
*
* Ich habe die States
*
* state1 [...]
* state2 [...]
*
* daneben habe ich noch etwas. Ein Feld, was f"ur jeden Zustand angibt, was das f"ur ein Zeichen ist. Das ist was anderes. Also ein Feld
*
* statechar [...]
* Dann habe ich
*
* state1 [...]
* state2 [...]
* statechar [...]
*
* Jetzt muss ich mir merken
*
* "abcd"
*
* state1 [0] = 1
* state2 [0] = 1
* state1 [1] = 2
* state2 [1] = 2
* state1 [2] = 3
* state2 [2] = 3
* ...
*
* Nebenbei ist
*
* statechar [0] = 'a'
* ...
*
* Gut, das wichtige ist, bei ODER das hat nichts mit dem Zeichen zu tun
*
* Wenn da steht
* a(a|b)
*
* Dann folgt auf
* state1[0] = 1
* state2[0] = 2
*
* Bei einer Wiederholung folgt auf
*
* a*b
*
* state1 [0] = 0
* state2 [0] = 1
*
* Jetzt merken wir, die Grammatik ist Falsches
*
* Weil bei arithmetischen Ausdrucken, folgt auf Operand Operator Operand
* Und jetzt haben wir Operand Operand
*
* Dann f"uhren wir noch eine Regel eine
*
*
* expr ::= term | term '|' expr
* term ::= factor | factor term | factor*
* factor ::= id | (expr)
*
* Das hat mit dem Automaten nichts zu tun. Unabh"angig ob das eine Wiederholung oder ein ODER ist, tut der Automat
*
* Bei einer Wiederholung zeigt der Zustand auf sich selber. Bei einem ODER zeigt der Vorg"angezustand entweder auf den Einen Zustand oder den anderen. Das sind aber Folgezust"ande
*
* */
#include <stdio.h>
#include <stdlib.h>
char gettoken ();
void tokenback ();
int expr ();
int factor ();
int term ();
//char matchexpr [] = "(((acasdasd|b)*)|c)|p";
char matchexpr [] = "qbc|defg";
int i = 0;
int j = 0;
int state1 [128];
int state2 [128];
char statechar [1024];
char gettoken () {
return matchexpr [i++];
}
void tokenback () {
i--;
}
int expr () {
int j1, j2;
int t;
t = j;
j++;
j1 = term ();
if (gettoken () == '|') {
j2 = expr ();
state1 [t] = j1;
state2 [t] = j2;
}
else {
state1 [t] = j1;
state2 [t] = j1;
tokenback ();
}
return j1;
}
int term () {
char ch;
int j1, j2;
j1 = factor ();
if ((ch = gettoken ()) == '*') {
j2 = j1;
if((ch >= 'a') \&\& (ch <= 'z')) {
tokenback ();
j2 = term ();
}
state1 [j1] = j1;
state2 [j1] = j2;
}
else if((ch >= 'a') \&\& (ch <= 'z')) {
tokenback ();
j2 = term ();
state1 [j1] = j2;
state2 [j1] = j2;
}
else
tokenback ();
return j1;
}
int factor () {
char ch = gettoken ();
int j1;
if (ch == '(') {
j1 = expr ();
if (gettoken () != ')') {
fprintf (stderr, "Geschlossene Klammer vergessen");
exit (1);
}
}
else if ((ch >= 'a') \&\& (ch <= 'z')) {
statechar [j] = ch;
j1 = j;
j++;
printf ("%cn", ch);
}
else {
fprintf (stderr, "Falsches Zeichen %c", ch);
exit (1);
}
return j1;
}
int main (void) {
int k;
expr ();
for (k = 0; k < 24; k++) {
printf ("state1[%i] = %in", k, state1[k]);
printf ("state2[%i] = %in", k, state2[k]);
printf ("statechar[%i] = %cn", k, statechar[k]);
}
}