/***************************************************************/ /* Prof. Dr. Carsten Vogt */ /* FH Koeln, Fak. 07 / Nachrichtentechnik */ /* http://www.nt.fh-koeln.de/vogt */ /* */ /* Beispielprogramm Nr. 74 */ /* der frueheren Vorlesung Datenverarbeitung */ /* */ /* Das Programm analysiert den Aufbau eines arithmetischen */ /* Ausdrucks und wertet ihn aus. Dabei wird die Methode */ /* des rekursiven Abstiegs verwendet. */ /* */ /* Akzeptiert werden Ausdruecke mit ganzen Zahlen und den */ /* Operatoren +, -, *, /. Klammerung ist zulaessig. Der ge- */ /* samte Ausdruck und Teilausdruecke in Klammern duerfen mit */ /* einem negativen Vorzeichen - beginnen, nicht jedoch mit */ /* einem positiven Vorzeichen +. */ /***************************************************************/ #include #include #include #include /*******************/ /* Typdefinitionen */ /*******************/ /* struct token: Eintraege der Tokenliste Die Tokenliste wird bei der "lexikalischen Analyse" aus der Stringdarstellung des arithmetischen Ausdrucks aufgebaut - siehe Funktion lexikal(). Sie enthaelt die "Token", aus denen der Ausdruck besteht, also seine Zahlen, Operatoren und Klammern. Ein Token kann somit entweder ein Zahl oder ein Zeichen sein. */ typedef struct token { char zeichen; /* wird verwendet, wenn Token ein Zeichen ist. zulaessige Eintraege: (,),+,-,*,/ Eintrag ' ' bedeutet: Token ist Zahl. */ int wert; /* numerischer Wert, wenn Token eine Zahl ist. Eintrag nur gueltig, wenn zeichen==' ' */ struct token *next; /* naechster Listeneintrag */ } token; /* struct baumeintrag: Eintraege des Strukturbaums Der Strukturbaum wird bei der "Syntaxanalyse" aus der Tokenliste aufgebaut - siehe Funktion syntausdr(). Er gibt den syntaktischen Aufbau des Ausdrucks an, zeigt also, wie er aus Teilausdruecken zusammengesetzt ist. Dies ermoeglicht seine Auswertung - siehe Funktion auswert(). Ein Baumeintrag enthaelt - aehnlich wie ein Token - entweder einen Operanden oder einen Wert. */ typedef struct baumeintrag { char operator; /* zulaessige Eintraege: +,-,*,/,' ' */ int wert; /* wert nur gueltig, wenn operator==' ' */ struct baumeintrag *links, *rechts; /* linker u. rechter Teilbaum */ } baumeintrag; /************************/ /* Lexikalische Analyse */ /************************/ token *lexikal(char *ausdr) { /* Die Funktion fuehrt fuer ausdr (= Stringdarstellung des arith- metischen Ausdrucks) eine lexikalische Analyse durch. Sie liefert als Rueckgabewert eine entsprechende Tokenliste mit seinen Zahlenwerten, Klammern und Operatoren. Die Tokenliste enthaelt die Token in umgekehrter Reihenfolge, da sich so die Syntaxanalyse besser durchfuehren laesst. */ token *toklist=NULL; /* zeigt auf die bislang aufgebaute Liste */ token *neu; /* Hilfszeiger fuer neues Listenelement */ unsigned lg=strlen(ausdr); /* Anzahl der Zeichen des Ausdrucks */ int i=0,j; /* Laufvariablen */ char zahlstring[15]; /* Stringdarstellung einer Zahl */ while (i'9') /* Zeichen gefunden: Zeichen in den neuen Listeneintrag uebernehmen und Index i inkrementieren */ neu->zeichen=ausdr[i++]; else { /* Zahl gefunden: Ziffern nach zahlstring uebertragen, dabei Index i inkrementieren */ j=0; do { zahlstring[j++]=ausdr[i++]; } while(ausdr[i]>='0'&&ausdr[i]<='9'); /* Abbruch, wenn Zahl zuende */ /* Stringendezeichen anhaengen */ zahlstring[j]='\0'; /* Umwandlung des Ziffernstrings nach int und Zuweisung an neuen Listeneintrag */ neu->wert=atoi(zahlstring); /* Token enthaelt Zahl, also Zeichen auf ' ' setzen */ neu->zeichen=' '; } /* Einfuegen des neuen Eintrags in die Tokenliste */ if (toklist==NULL) { /* Tokenliste war bisher leer */ toklist=neu; toklist->next=NULL; } else { /* Tokenliste war nicht leer: Einfuegen des neuen Tokens vorne */ neu->next=toklist; toklist=neu; } } /* Ende der while-Schleife zum Durchlaufen des Strings ausdr */ return toklist; } /********************************************/ /* Syntaxanalyse = Aufbau des Strukturbaums */ /********************************************/ /* Die folgenden Funktionen fuehren auf Grundlage einer Token- liste eine Syntaxanalyse durch und liefern als Rueckgabewert den zugehoerigen Strukturbaum des arithmetischen Ausdrucks. Die Vorgehensweise basiert auf der folgenden BNF-Darstellung der Syntax von Ausdruecken: ::= + | - | ::= * | / | ::= | () Ein Ausdruck besteht also aus einem oder mehreren Termen, die durch + oder - miteinander verknuepft sind, ein Term besteht aus einem oder mehreren Faktoren, die durch * oder / verknuepft sind, und ein Faktor ist eine Zahl oder ein Ausdruck in Klammern. Die Funktion syntausdr() wird als erste aufgerufen und versucht, in der Tokenliste ein Muster zu finden, das der ersten Regel ent- spricht. Sie ruft dazu zunaechst die Funktion syntterm() auf, die nach einem Term am Ende der Liste sucht, prueft dann, ob vor die- sem Term ein + oder - steht und ob der Teil davor wiederum ein Ausdruck ist. Die Funktion syntterm() zur Analyse von Termen geht analog anhand der zweiten Regel vor und ruft dabei die Funktion syntfaktor() auf, die ihrerseits nach einer Zahl oder einem Ausdruck in Klammern sucht. Die Analyse geschieht also von hinten nach vorn, weshalb die Token- liste durch lexikal() von hinten nach vorn aufgebaut wurde (siehe oben). Teile der Tokenliste, die durch die syntxxx()-Funktionen "verbraucht" wurden, werden jeweils aus der Tokenliste entfernt. Die Tokenliste wird daher per Referenz (= Doppelzeiger **) an die Funktionen uebergeben, damit diese die Liste veraendern (d.h. ver- kuerzen) koennen. Wird bei der Analyse ein Zeichen gefunden, das aufgrund der Regeln an dieser Stelle nicht stehen duerfte (also z.B. eine falsche Klam- mer oder zwei Operatoren unmittelbar hintereinander), oder ist der Ausdruck unvollstaendig, so wird die Analyse mit Fehlermeldung abgebrochen (Funktion error()). */ void error() { /* Die Funktion meldet einen syntaktischen Fehler und terminiert das Programm. */ printf("syntaktischer Fehler!\n"); getch(); exit(-1); } baumeintrag *syntausdr(token **toklist); /* Prototyp, da indirekter rekursiver Aufruf moeglich */ baumeintrag *syntfaktor(token **toklist) { /* Die Funktion sucht nach einem Faktor am Anfang der Liste *toklist (also am Ende des Ausdrucks). Sie baut einen Syntaxbaum fuer diesen Faktor auf, liefert einen Zeiger auf dessen Wurzel zurueck und kuerzt die Tokenliste ent- sprechend. */ baumeintrag *pt; /* Hilfszeiger zum Aufbau des Syntaxbaums */ /* Pruefung, ob erster oder zweiter Teil der 3. BNF-Regel vor- liegt */ if ((*toklist)->zeichen==')') { /* aktuelles Token deutet auf zweiten Teil der Regel hin: Ende eines Teilausdrucks in Klammern */ /* Token fuer ')'streichen */ (*toklist)=(*toklist)->next; /* Suche nach Teilausdruck vor ')', Aufbau des entsprechenden Teilbaums und Zwischenspeichern in pt. Wird dieser Ausdruck nicht gefunden, so bricht syntausdr() die Analyse ab. */ pt=syntausdr(toklist); /* Test, ob zugehuerige Klammer '(' vorhanden. Wenn nein: Fehler. Wenn ja: '(' aus Tokenliste streichen. */ if ((*toklist==NULL)||((*toklist)->zeichen!='(')) error(); (*toklist)=(*toklist)->next; } else { /* zweiter Teil der Regel trifft nicht zu, also Suche nach einzelner Zahl */ /* Pruefung, ob einzelne Zahl vorliegt */ if ((*toklist)->zeichen!=' ') /* Wenn zeichen!=' ': Token ist Operand -> Fehler */ error(); /* neuen Teilbaum (= Blattknoten) fuer Zahl erzeugen */ pt=(baumeintrag *)(malloc(sizeof(baumeintrag))); if (pt==NULL) { printf("Fehler bei malloc\n"); getch(); exit(-1); } /* Einfuegen des Werts */ pt->operator=' '; pt->wert=(*toklist)->wert; /* Linker und rechter Unterbaum sind leer */ pt->links=pt->rechts=NULL; /* Zahl aus Tokenliste streichen */ (*toklist)=(*toklist)->next; } /* Zeiger auf Teilbaum zurueckliefern */ return pt; } baumeintrag *syntterm(token **toklist) { /* Die Funktion sucht nach einem Term am Anfang der Liste *toklist (also am Ende des Ausdrucks). Sie baut einen Syntaxbaum fuer diesen Term auf, liefert einen Zeiger auf dessen Wurzel zurueck und kuerzt die Tokenliste ent- sprechend. */ baumeintrag *pt, *pthilf; /* Hilfszeiger fuer Baumaufbau */ /* Suche nach einem Faktor am Anfang der Liste (= Ende des Ausdrucks) und Zwischenspeichern des Strukturbaums fuer diesen Faktor in pt. BNF-Regel 2 besagt, dass bei einem syntaktisch korrekten Ausdruck der Faktor auf alle Faelle vorhanden sein muss */ pt=syntfaktor(toklist); /* Pruefung, ob vor dem Faktor ein * oder / mit einem weiteren Teil-Term vorliegt (BNF-Regel 2, Teil 1 oder 2) */ if ((*toklist!=NULL)&&((*toklist)->zeichen=='*' ||(*toklist)->zeichen=='/')) { /* Wenn ja: Term besteht aus einem Faktor und einem Term, die mit * oder / verknuepft sind. -> Aufbau eines entsprechenden Teilbaums, dessen Wurzel der Operator ist und dessen Unterbaeume dem Faktor und dem Term entsprechen. */ /* Erzeugung des Wurzelknotens und Eintragung des Operators */ pthilf=(baumeintrag *)(malloc(sizeof(baumeintrag))); if (pthilf==NULL) { printf("Fehler bei malloc\n"); getch(); exit(-1); } pthilf->operator=(*toklist)->zeichen; /* rechter Unterbaum = gefundener Faktor */ pthilf->rechts=pt; /* Streichen des Operanden aus der Tokenliste */ (*toklist)=(*toklist)->next; /* Aufbau des linken Unterbaums fuer den Term. Wenn kein syntaktisch korrekter Term vorhanden ist, bricht syntterm() die Analyse ab. */ pthilf->links=syntterm(toklist); pt=pthilf; } /* Rueckgabe des aufgebauten Syntaxbaums */ return pt; } baumeintrag *syntausdr(token **toklist) { /* Die Funktion sucht nach einem Ausdruck in der Liste *toklist. Sie baut einen Syntaxbaum fuer diesen Term auf, liefert einen Zeiger auf dessen Wurzel zurueck und kuerzt die Tokenliste entsprechend. */ baumeintrag *pt, *pthilf; /* Hilfszeiger fuer Baumaufbau */ /* Suche nach einem Term am Anfang der Liste (= Ende des Ausdrucks) und Zwischenspeichern des Strukturbaums fuer diesen Term in pt. BNF-Regel 2 besagt, dass bei einem syntaktisch korrekten Ausdruck der Term auf alle Faelle vorhanden sein muss. */ pt=syntterm(toklist); /* Pruefung, ob der (Teil-)Ausdruck eine einzelne Zahl mit negativem Vorzeichen ist. Das ist der Fall, wenn vor dem durch syntterm gelieferten Term ein Minuszeichen steht, das der Anfang des Gesamtausdrucks ist oder vor dem sich eine geoeffnete Klammer befindet. */ if (((*toklist)!=NULL)&&((*toklist)->zeichen=='-') &&((*toklist)->next==NULL ||(*toklist)->next->zeichen=='(')) { /* Negierung des in pt eingetragenen Werts */ pt->wert=-pt->wert; /* Streichung des Minuszeichens aus der Tokenliste */ (*toklist)=(*toklist)->next; /* Rueckgabe des aufgebauten Baums */ return pt; } /* Pruefung ob der Ausdruck nur aus einem einzelnen Term besteht. Das ist der Fall, wenn sich davor kein weiterer Ausdruck mit + oder - anschliesst (siehe BNF-Regel 1) */ if (*toklist==NULL|| (((*toklist)->zeichen!='+') &&((*toklist)->zeichen!='-'))) /* Ausdruck besteht nur aus einem Term: Rueckgabe des Struktur- baums fuer diesen Term. */ return pt; /* Ausdruck besteht aus einem Term und einem weiteren (Teil-)Ausdruck (siehe BNF-Regel 1) -> Aufbau eines entsprechenden Strukturbaums */ /* Erzeugung des Wurzelknotens fuer diesen Strukturbaum */ pthilf=(baumeintrag *)(malloc(sizeof(baumeintrag))); if (pthilf==NULL) { printf("Fehler bei malloc\n"); getch(); exit(-1); } /* rechter Unterbaum = oben gefundener Term */ pthilf->rechts=pt; /* Wurzeleintrag = Operand */ pthilf->operator=(*toklist)->zeichen; /* Streichen des Operanden aus der Tokenliste */ (*toklist)=(*toklist)->next; /* Aufbau des Strukturbaums fuer den Teilausdruck und Uebernahme als linken Unterbaum */ pthilf->links=syntausdr(toklist); /* Rueckgabe des aufgebauten Strukturbaums */ return pthilf; } /********************************/ /* Auswertung des Strukturbaums */ /********************************/ int auswert(baumeintrag *struktbaum) { /* Die Funktion wertet den durch struktbaum beschriebenen arithmetischen Ausdruck aus und liefert seinen Wert zurueck. Sie geht dabei wie folgt vor: Ist der Wurzeleintrag ein Operator, so werden der linke und der rechte Unterbaum durch rekursiven Aufruf auswertet und die Ergebnisse anhand des Operators verknuepft. Ist der Wurzeleintrag ein Wert, so wird unmittelbar dieser Wert zurueckgeliefert. */ switch (struktbaum->operator) { case ' ': /* Wurzeleintrag ist Wert */ return struktbaum->wert; case '+': /* Wurzeleintrag ist Operand + */ return auswert(struktbaum->links)+auswert(struktbaum->rechts); case '-': /* Wurzeleintrag ist Operand - */ return auswert(struktbaum->links)-auswert(struktbaum->rechts); case '*': /* Wurzeleintrag ist Operand * */ return auswert(struktbaum->links)*auswert(struktbaum->rechts); case '/': /* Wurzeleintrag ist Operand / */ return auswert(struktbaum->links)/auswert(struktbaum->rechts); } /* Ende switch */ } /*******************/ /* Kontrollausgabe */ /*******************/ void listausg(token *tokenliste) { /* Funktion zur Ausgabe der Tokenliste */ token *tkhilf; printf("\nTokenliste in umgekehrter Reihenfolge:\n\n"); tkhilf = tokenliste; while (tkhilf!=NULL) { if (tkhilf->zeichen!=' ') printf("%c ",tkhilf->zeichen); else printf("%d ",tkhilf->wert); tkhilf = tkhilf->next; }; printf("\n\n"); } void baumausg_rek(baumeintrag *baum,int space) { /* rekursive Hilfsfunktion fuer die Baumausgabe (siehe Beispiel 68 der Vorlesung) */ const int tab=4; int i; if (baum==NULL) return; baumausg_rek(baum->rechts,space+1); for (i=1;i<=space*tab;i++) printf(" "); if (baum->operator!=' ') printf("%c\n",baum->operator); else printf("%d\n",baum->wert); baumausg_rek(baum->links,space+1); } void baumausg(baumeintrag *baum) { /* Funktion zur Ausgabe des Strukturbaums */ printf("Strukturbaum:\n\n"); baumausg_rek(baum,0); printf("\n"); } /*****************/ /* Hauptprogramm */ /*****************/ main() { char ausdruck[80]; /* auszuwertender arithm. Ausdruck (Eingabe durch Benutzer) */ token *tokenliste; /* zeigt auf erstes Element der Tokenliste (Aufbau durch Funktion lexikal()) */ baumeintrag *strukturbaum; /* zeigt auf Wurzel des Strukturbaums (Aufbau durch Funktion syntausdr()) */ /* Ausdruck von der Tastatur einlesen */ printf("Bitte arithmetischen Ausdruck eingeben: "); gets(ausdruck); /* Lexikalische Analyse = Aufbau der Tokenliste */ tokenliste=lexikal(ausdruck); /* Kontrollgabe der Tokenliste */ listausg(tokenliste); /* Syntaxanalyse = Aufbau des Strukturbaums */ strukturbaum=syntausdr(&tokenliste); /* Wenn Tokenliste durch Syntaxanalyse nicht vollstaendig bearbeitet werden konnte: Syntaxfehler */ if (tokenliste!=NULL) error(); /* Kontrollausgabe des Strukturbaums */ baumausg(strukturbaum); /* Auswertung des Ausdrucks und Ausgabe des Resultats */ printf("\nWert des Ausdrucks: %d\n",auswert(strukturbaum)); getch(); }