Next: /media/sda-magnetic/david/compilerbau/pattern-matching/1th-episode/reg7.c Up: www02102026002 Previous: /media/sda-magnetic/david/compilerbau/pattern-matching/1th-episode/reg5.c
/* 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ührt das nicht zum Ziel. Die Grammatik geht anders
*
* 1.) müsste nach dem * auch ein | kommen können. 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 ("%c\n", ch);
else {
fprintf (stderr, "Falsches Zeichen %c", ch);
exit (1);
}
return;
}
int main (void) {
expr ();
}
*/
/*
*
* Jetzt kommt der Automat. Jetzt müssen 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ände - 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ände Folgezustände haben könnte, kann ich das nach der Baumregel, auf zwei Folgezustände reduzieren
*
* state1 [0] = 1
* state2 [0] = 1
* state1 [1] = 2
* state2 [1] = 2
* ...
*
* So wäre 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ür jeden Zustand angibt, was das für 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ühren 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ängig 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ängezustand entweder auf den Einen Zustand oder den anderen. Das sind aber Folgezustände
*
* */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char gettoken ();
void tokenback ();
//char matchexpr [] = "(((acasdasd|b)*)|c)|p";
char matchexpr [] = "(c(ab)*c)*d;";
//char matchexpr [] = "qbc|defg";
int i = 0;
int state1 [128];
int state2 [128];
char statechar [1024];
char gettoken () {
printf ("%c\n", matchexpr [i]);
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 expr
* term ::= factor | factor*
* factor ::= id | (expr)
* */
/* expr ::= term | term + expr
* term ::= factor | factor * term
* factor ::= id | (expr)
*/
int expr (int);
int term (int);
int factor (int);
int expr (int j) {
int ch;
term (j);
if ((ch = gettoken ()) == '+')
expr (j);
else if ((ch >= 'a') && (ch <= 'z')) {
tokenback ();
expr (j);
}
else if (ch == '(') {
tokenback ();
factor (j);
}
else
tokenback ();
}
int term (int j) {
int ch;
factor (j);
if ((ch = gettoken ()) == '*')
term (j);
else if (ch == '(') {
tokenback ();
factor (j);
}
else
tokenback ();
}
int factor (int j) {
int ch = gettoken ();
if (ch == '(') {
expr (j);
if (gettoken () != ')') {
fprintf (stderr, "fehler ) vergessen");
exit (1);
}
}
else if ((ch >= 'a') && (ch <= 'z'))
printf ("%c\n", ch);
else {
fprintf (stderr, "fehler %c unbekanntes zeichen\n", ch);
exit (1);
}
}
/*
int expr (int j) {
int j1, j2;
j2 = j1 = term (j+1);
if (j1 == -1)
return -1;
if (gettoken () == '|')
j2 = expr (j);
else
tokenback ();
state1 [j] = j1;
state2 [j] = j2;
return j;
}
int term (int j) {
int ch;
int j1, j2;
printf ("%c ...\n", matchexpr [i]);
j1 = factor (j);
if (j1 == -1)
return -1;
if ((ch = gettoken ()) == '*')
j2 = term (j+1);
else if ((ch >= 'a') && (ch <= 'z')) {
tokenback ();
j2 = j1 = term (j+1);
}
else
tokenback ();
state1 [j] = j1;
state2 [j] = j2;
return j;
}
int factor (int j) {
int ch = gettoken ();
if (ch == '(') {
j = expr (j);
if (gettoken () != ')') {
printf ("Klammer schliessen vergessen");
exit (1);
}
}
else if ((ch >= 'a') && (ch <= 'z')) {
printf ("%c ...\n", ch);
statechar [j] = ch;
}
else if (ch == ';')
return -1;
else {
printf ("Unbekanntes Zeichen %c", ch);
exit (1);
}
return j;
}
*/
int main (void) {
int k;
expr (0);
/*
for (k = 0; k < 24; k++) {
printf ("state1[%i] = %i\n", k, state1[k]);
printf ("state2[%i] = %i\n", k, state2[k]);
printf ("statechar[%i] = %c\n", k, statechar[k]);
}*/
}