Nächste Seite: Re: Artikel Debian Aufwärts: Graphen, Schaltwerke und Zahlen Vorherige Seite: Re: Artikel Debian
https://www.davidvajda.de/viewtopic.php?p=1184#p1184">
/* 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 ();
char matchexpr [] = "((((acasdasd|b)*)|c)|p)|l";
//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--;
}
/* Das einfachste: Auf zeichen folgt Zeichen
*
*
* chr ::= ch | ch chr
* a
* aa
* aaa
*
* chr ::= rpt | rpt chr
* rpt ::= ch | *ch
*
* chr ::= sel | sel chr
* sel ::= rpt | + rpt sel // + rpt rpt
* rpt ::= ch | *ch
* ch ::= id | (chr)
*
* chr ::= sel | sel chr
* sel ::= rpt | rpt + sel // + rpt rpt
* rpt ::= ch | ch*
* ch ::= id | (chr)
*
* chr ::= expr | expr chr
* expr ::= term | term '|' expr
* term ::= factor | factor*
* factor ::= id | (expr)
* chr ::= expr | expr chr
* expr ::= term | term '|' term
* term ::= factor | factor*
* factor ::= id | (expr)
* */
int chr ();
int expr ();
int term ();
int factor ();
int chr () {
int ch;
expr ();
ch = gettoken ();
if ((ch >= 'a') \&\& (ch <= 'z')) {
tokenback ();
chr ();
}
else
tokenback();
}
int expr () {
term ();
if (gettoken () == '|')
term ();
else
tokenback ();
}
int term () {
factor ();
if (gettoken () == '*');
else
tokenback ();
}
int factor () {
int ch = gettoken ();
if (ch == '(') {
chr ();
if (gettoken () != ')') {
printf ("Klammer schliessen vergessen");
exit (1);
}
}
else if ((ch >= 'a') | (ch <= 'z'))
printf ("%cn", ch);
else {
printf ("Unbekanntes Zeichen");
exit (1);
}
}
int main (void) {
int k;
chr ();
}