#include #include #define grenze1 39 /* Indexgrenzen fuer Array mit Produktionen */ #define grenze2 7 #define grenze3 7 #define error 0 #define shift -1 #define konst 10 #define epsilon 99 /* Epsilon soll als Token 99 definiert sein */ #define NIL 200 /* Falls ein Listenelement leer ist wird NIL gespeichert */ #define anzterm 99 /* Variable fuer die Anzahl von Terminaltoken */ #define read "r" /* fr den Lesezugriff auf die Datei */ typedef struct IntListe /* Definition eines einfachen Listenelements */ { int element; struct IntListe *next; } listelement; typedef struct ikmenge /* Definition der Liste, die die Menge der LR-Aus- kuenfte zu einem Wort repraesentieren soll */ { int linkeseite; /* Non-Terminal, das abgeleitet wird */ int vorpunkt [grenze3]; /* Wort, das direkt abgeleitet werden kann (vor dem Punkt in der LR-Auskunft) */ int hinterpunkt [grenze3]; /* Wort, das nach shiften abgeleitet werden kann (hinter dem Punkt) */ int fortsetzung; /* Look-Ahead-Anteil der Auskunft */ struct ikmenge *next; } ikelementmenge; typedef struct iklist /* Definition der Baumstruktur mit den LR-Auskuenften */ { ikelementmenge *element; /* Element der Menge der LR1-Auskunft zu einem bestimmten Wort */ struct iklist *vater; /* Vater des aktuellen Knoten des Baumes */ struct iklist *sohn; /* erster Nachfolger des Knotens */ struct iklist *bruder; /* rechter Bruder des Knotens */ int wort; /* wort gibt das letzte Zeichen des Wortes an von dem die LR- Menge abhaengt */ } ikliste; typedef struct kellermenge /* Struktur des Kellers bei der Erstellung des Ableitungsbaumes */ { int token, zeile, spalte; /* uebergebener Token mit Zeile und Spalte */ char name[konst]; /* Attribut zu dem Token */ ikliste *z; /* Zeiger auf den Anfang einer LR-Mengen-Liste */ struct kellermenge *prev; /* Vorgaenger */ struct kellermenge *next; /* Nachfolger */ } keller; typedef struct /* Struktur zur Speicherung einer Ableitung */ { int links; /* linke Seite der Ableitung */ int rechts[grenze3]; /* rechte Seite der Ableitung */ } ableitung; typedef struct liste /* Struktur zur Speicherung des Ableitungsbaumes */ { int token, zeile, spalte; char name[konst]; int dateizeile; struct liste *prev; struct liste *next; } ableitungbaum; struct zeile /* struct zeile ist eine Datenstruktur, die nur */ { /* innerhalb der Dateiverwaltung als Zwischenspeicher */ int zahl1; /* benutzt wird */ char name [konst]; int zahl2; int zahl3; }; /* Einlesen der Ableitungsregeln der Grammatik erste Dimension beschreibt die Nummer der Regel, zweite Dimension beschreibt Nummer der Alternative dabei haben die Non-Terminal-Symbole die Nummer der Regel, die sie bilden zu 100 addiert */ int mml [grenze1] [grenze2] [grenze3] = {{{1, 101, 85, 102, 81}}, {{2}}, {{3, 103, 119, 4}, {3, 119, 4}}, {{104}, {113}, {104, 113}}, {{105, 80}, {105, 80, 104}}, {{5, 106, 82, 107}}, {{2}}, {{108}, {109}}, {{6}, {7}, {8}}, {{9, 86, 110, 87, 10, 108}}, {{111, 82, 112}, {111, 82, 112, 88, 110}}, {{131, 80}}, {{131, 80}}, {{114, 80}, {114, 80, 113}}, {{11, 115, 116, 85, 102}}, {{2}}, {{83, 84}, {83, 117, 84}}, {{2, 82, 118}, {2, 82, 118, 88, 117}}, {{107}, {11}}, {{120}, {120, 80, 119}}, {{123}, {121}}, {{122, 82, 123}}, {{2}}, {{124}, {138}}, {{125}, {126}, {127}, {128}, {102}}, {{132, 12, 129}}, {{13, 122}}, {{115, 134}, {26, 83, 132, 84}, {27, 134}}, {{14, 37, 15, 119, 16}}, {{130}, {131}}, {{53}, {54}, {132}, {83, 17, 130, 84}, {83, 130, 18, 130, 84}, {83, 130, 84}, {83, 131, 19, 131, 84}}, {{51}, {52}, {132}, {83, 20, 131, 84}, {83, 131, 21, 131, 84}, {83, 131, 84}}, {{106}, {106, 86, 133, 87}}, {{131}, {131, 88, 133}}, {{83, 84}, {83, 135, 84}}, {{136}, {136, 88, 135}}, {{129}, {115}}, {{130}}, {{22, 137, 23, 119, 24, 119, 25}}}; /* Hat man ein Token > 99 so beschreibt dies eindeutig ein Non-Terminal, das abgeleitet werden kann. Die Grammatik ist nun so aufgebaut, dass man bei Subtrahierung von 100 von der Tokennummer automatisch die zugehörige Regelnummer erhaelt. */ int mml [grenze1] [grenze2] [grenze3]; ikliste *anfangbaum; ikelementmenge *aktuell2element, *aktuellelement, *jkmenge, *anfangjk; int groessebaum = sizeof(ikliste); int groesseikmenge = sizeof(ikelementmenge); int kellergroesse = sizeof(keller); int baumgroesse = sizeof(ableitungbaum); int terminal[anzterm]={0}; /* Array fuer Terminalsymbole */ int nonterminal[grenze1]={0}; /* boolsche Variable, ob Nonterminal schon geprueft fuer Prozedur l1_sprache */ int wort; int i, j, k, l; /* Laufvariablen */ int ende; /* Wahrheitswert fuer Schleifenende */ int gefunden; /* Boolsche Variable */ int zyklisch; /* boolsche Variable, ob Grammatik zyklisch ist */ listelement *aktuell, *aktuell2; /* aktuelle Listenelement */ listelement *anfang, *anfang2; /* Listenanfang (anfang fuer Liste der Epsi- lonabl. und anfang2 fuer Liste mit Zykel */ int elemgroesse = sizeof(listelement); /* Variable fuer Elementgroesse */ FILE *filezeiger; /* Zeiger auf File Strukturvariable */ int dateizeiger; /* z„hlt in der Dateiverwaltung intern die Anzahl */ /* der File Eintr„ge */ /********** Function Deklarationen fr Dateiverwaltung **************/ struct zeile dateizeilelesen( int nummer,int *dateiende); void einlesen(int *token,char name[konst],int *zeile, int *spalte,int *dateiende); /* Die Funktion prueft, ob uebergebene Produktionsregel bereits in der Menge der Epsilon-Ableitungen enthalten ist */ int inmenge(int produktion, listelement *anfang) /* produktion: Eingabevariable Nummer der uebergebenen Produktion *anfang: Eingabevariable zeigt auf Anfang der Liste mit Epsilon- Ableitungen */ { listelement *zeiger; int gefunden=0; zeiger=anfang; while (((*zeiger).element!=NIL) && (!gefunden)) { if (produktion==(*zeiger).element) { gefunden=1; } else { zeiger=(*zeiger).next; } } return(gefunden); } /* Die Prozedur bestimmt L1-Sprache zu einem gegebenen Wort, wobei im Feld terminal an die Stelle im Feld eine 1 gesetzt wird, wenn die Nummer einer Terminalnummer entspricht, welches Element der Sprache ist */ void l1_sprache(int delta) /* delta Eingabevariable Wort zu dem L1-Sprache bestimmt werden soll */ { int j, k; if (delta <= 99) /* wenn uebergebenes Wort Terminal, dann Terminal in Menge eintragen */ { terminal[delta]=1; } else { if (!nonterminal[delta-100]) /* falls das uebergebene Nonterminal noch nicht untersucht worden ist */ { j=0; nonterminal[delta-100]=1; /* Kennzeichnung, dass das Nonterminal unter- sucht wird */ /* solange es noch Alternativen der Ableitung gibt, muessen diese unter- sucht werden. */ while ((j 0 */ } /* end if !nonterminal */ } /* end if (else) delta <= 99 */ } /* end prozedur */ /* Funktion, die prueft, ob uebergebenes Element bereits in LR-Menge vor- handen ist */ int inlrmenge(ikelementmenge *aktuell, ikelementmenge *anfang) /* *aktuell Eingabevariable Element, das auf Vorhandensein ueberprueft werden soll *anfang Eingabevariable Anfang der LR-Menge, in der das zu ueber- pruefende Element gesucht werden soll */ { int i,j=0; int gefunden=0; int ungleich; while ((anfang->next!=NULL) && (!gefunden)) { ungleich=0; j++; if (anfang->linkeseite==aktuell->linkeseite) { for (i=0; ivorpunkt[i]!=aktuell->vorpunkt[i]) { ungleich=1; } } if (!ungleich) { for (i=0; ihinterpunkt[i]!=aktuell->hinterpunkt[i]) { ungleich=1; } } } if ((!ungleich) && (anfang->fortsetzung==aktuell->fortsetzung)) { gefunden=1; } } /* end if anfang->linkeseite */ anfang=anfang->next; } /* end while */ return(gefunden); } /* end inlrmenge */ /* Prozedur prueft, ob uebergebene LR-Information bereits im Baum mit den LR-Mengen enthalten ist */ int inbaum(ikliste *knoten) { int i, j; int gefunden, weiter; ikliste *aktuell; ikelementmenge *lrmenge; lrmenge=knoten->element; gefunden=0; aktuell=knoten->vater; while((aktuell!=NULL) && (!gefunden)) { weiter=1; while((lrmenge->next!=0) && (weiter)) { if(!inlrmenge(lrmenge, aktuell->element)) { weiter=0; } lrmenge=lrmenge->next; } /* end while (weiter) */ if(weiter) { gefunden=1; } aktuell=aktuell->vater; lrmenge=knoten->element; } return(gefunden); } /* end inbaum */ /* Bestimmung der LR1-Menge zu Epsilon, dabei bildet diese Menge die Wurzel des Baumes mit den LR1-Mengen */ void lr1mengeeps() { int i, j; anfangbaum=malloc(groessebaum); /* Wurzel fuer den Baum mit LR-Auskuenften wird allociert */ anfangbaum->wort=epsilon; anfangbaum->element=malloc(groesseikmenge); anfangjk=malloc(groesseikmenge); /* Liste fuer Menge der kanonischen Kollek- tion wird initialisiert */ jkmenge=anfangjk; jkmenge->next=NULL; /* wenn kein Nachfolger mehr vorhanden ist, zeigt next=NULL immer das Ende der Liste an */ aktuellelement=anfangbaum->element; /* externer Zeiger wird generiert,damit der interne Zeiger auf die LR-Menge nicht verloren geht*/ aktuellelement->next=NULL; anfangbaum->vater=anfangbaum->sohn=anfangbaum->bruder=NULL; /* wie bei next */ j=0; /* Erstellung der Menge I1(epsilon) */ while ((jlinkeseite=100; /* Speicherung des Startsymbols als linke Seite der LR-Auskunft */ jkmenge->linkeseite=100; /* gleiche Eintraege muessen auch fuer die kanonische Kollektion erstellt werden */ jkmenge->vorpunkt[0]=aktuellelement->vorpunkt[0]=epsilon; /* Speicherung des Epsilons */ for (i=1; ivorpunkt[i]=aktuellelement->vorpunkt[i]=0; } for (i=0; ihinterpunkt[i]=aktuellelement->hinterpunkt[i]=(mml[0] [j] [i]); } /* end for */ jkmenge->fortsetzung=aktuellelement->fortsetzung=epsilon; aktuellelement->next=malloc(groesseikmenge); /* Erstellung eines neuen Elements der LR1-Menge */ aktuellelement=aktuellelement->next; jkmenge->next=malloc(groesseikmenge); jkmenge=jkmenge->next; j++; } /* end while */ aktuellelement->next=NULL; /* letzte Element in der Liste wird markiert */ jkmenge->next=NULL; aktuell2element=anfangbaum->element; /* Liste wird von vorne wieder durchsucht*/ while (aktuell2element->next!=NULL) /* solange nicht das letzte Element erreicht ist, wenn das letzte Element der Liste erreicht ist, hat keine Aenderung der Menge stattgefunden */ { wort=aktuell2element->hinterpunkt[0]; /* erste Wort auf der rechten Seite der aktuellen LR- Informa- tion wird ueber prueft */ if (wort >= 100) /* falls das Zeichen ein Nonterminal ist, muss eine neue LR-Information in die Liste aufgenommen werden */ { j=0; /* solange noch Alternativen der Ableitung des Non-Terminals vorhanden sind */ while ((jhinterpunkt[1]); k=1; /* solange die Zeichen hinter dem Komma nach Epsilon ableitbar sind, muessen auch noch die Ableitungen des Nachfolgewortes ueberprueft werden */ while ((inmenge(aktuell2element->hinterpunkt[k], anfang)) && (khinterpunkt[k]); } /* wenn auch das letzte Zeichen hinter dem Komma der LR-Aus- kunft nach Epsilon ableitbar ist, muss auch noch der Look-Ahead in die Menge der ableitbaren Worte eingetragen werden */ if (inmenge(aktuell2element->hinterpunkt[k], anfang)) { terminal[aktuell2element->fortsetzung]=1; } /* die Worte auf die abgeleitet werden kann, werden hinter das Komma in der LR-Auskunft als Look-Ahead geschrieben */ for (k=1; k<=epsilon; k++) { if (terminal[k] == 1) { /* fuer jedes gefundene Wort, wird eine neue LR-Auskunft in die Liste geschrieben */ jkmenge->linkeseite=aktuellelement->linkeseite=wort; jkmenge->vorpunkt[0]=aktuellelement->vorpunkt[0]=epsilon; for (i=1; ivorpunkt[i]=aktuellelement->vorpunkt[i]=0; } /* rechte Seite der Ableitung wird in LR-Auskunft einge- tragen */ for (i=0; ihinterpunkt[i]= aktuellelement->hinterpunkt[i] =mml[wort-100] [j] [i]; } /* gefundene Wort wird als Look-Ahead eingetragen */ jkmenge->fortsetzung=aktuellelement->fortsetzung =k; /* falls LR-Auskunft noch nicht vorhanden */ if (!inlrmenge(aktuellelement, anfangbaum->element)) { /* Zeiger wird weitergesetzt */ aktuellelement->next=malloc(groesseikmenge); aktuellelement=aktuellelement->next; aktuellelement->next=NULL; /* wenn Element auch noch nicht in der kanonischen Kollektion vorhanden, muá der Zeiger weiterge- setzt werden, um das Element in die Liste aufzu- nehmen */ if (!inlrmenge(jkmenge,anfangjk)) { jkmenge->next=malloc(groesseikmenge); jkmenge=jkmenge->next; jkmenge->next=NULL; } } /* Wenn lr-Auskunft schon in der Menge enthalten ist, war der Eintrag nicht noetig, so dass kein neues Listenelement eingefuegt werden muss und das aktuelle Element der leere Puffer mit aktuell.next =NULL ist */ } /* end if (terminal) */ } /* end for k */ j++; } /* end while (j=100)*/ /* naechste Element in der Liste wird untersucht */ aktuell2element=aktuell2element->next; } /* end while (aktuell2element->!=0) */ } /* end lr1mengeeps */ /* Erstellt den Baum mit den LR1-Mengen zu den verschiedenen Woertern */ void lr1menge(ikliste *aktuellbaum) /* *aktuellbaum Eingabevariable Zeiger auf Knoten der aktuellen LR1- Menge */ { int i,j,k,l; int gefunden, jungfrau; /* boolsche Variablen */ ikliste *sohn, *bruder; /* Zeiger fuer neue Knoten */ ikelementmenge *aktuell; /* Zeiger auf die LR-Menge des uebergebenen Knotens */ ikelementmenge *sohnmenge; /* Zeiger der LR-Menge zu einem neu generierten Sohn */ aktuellbaum->sohn=malloc(groessebaum); /* zum aktuellen Knoten wird ein Sohn generiert */ aktuellbaum->sohn->element=malloc(groesseikmenge); bruder=aktuellbaum->sohn; /* externer Zeiger auf den Sohn des uebergebenen Knotens wird generiert */ bruder->vater=aktuellbaum; /* der Vater des Sohnes wird gespeichert */ bruder->bruder=NULL; /* alle Nachfolger werden erst auf NULL gesetzt */ bruder->sohn=NULL; sohnmenge=bruder->element; /* externer Zeiger wird auf den LR-Mengen-Anfang gesetzt */ sohnmenge->next=NULL; /* letzte Listenelement auf NULL setzen */ /* Bestimmung der zum uebergebenden Knoten nachfolgenden LR-Mengen */ for (i=1; i<=(grenze1+100); i++) { aktuell=aktuellbaum->element; /* externer Zeiger wird auf den Listenan- fang der LR-Menge des uebergebenen Knotens gesetzt */ gefunden=0; /* Wenn das Wort nicht in der LR-Menge gefunden wird bleibt gefunden auf 0 */ if (i!=epsilon) /* nur fuer epsilon braucht keine neue LR-Menge angelegt zu werden */ { /* Erstellung neuer LR-Informationen durch Shiften */ while (aktuell->next!=NULL) /* solange bis das Ende der Vorgaenger- menge noch nicht erreicht ist */ { /* fuer jedes Wort wird geprueft, ob das Wort in der Vorgaenger-LR- Menge direkt hinter dem Punkt auftritt */ if (aktuell->hinterpunkt[0]==i) { gefunden=1; /* falls untersuchte Element gefunden wurde */ /* es wird eine neue LR-Menge erstellt, wobei nur die Elemente der Vorgaengermenge hinter dem Punkt eine Position nach links geschoben werden */ jkmenge->linkeseite=sohnmenge->linkeseite=aktuell->linkeseite; jungfrau=1; /* Es werden die Daten aus der Vorgaengermenge uebernommen, nur dass das erste Zeichen hinter dem Punkt vor den Punkt geshiftet wird */ for (k=0; kvorpunkt[k]==0) || (aktuell->vorpunkt[k]== epsilon)) && (jungfrau)) { jkmenge->vorpunkt[k]=sohnmenge->vorpunkt[k]=i; jungfrau=0; } else /* die restlichen Daten werden uebernommen */ { jkmenge->vorpunkt[k]=sohnmenge->vorpunkt[k] =aktuell->vorpunkt[k]; } } for (k=1; khinterpunkt[k-1]=sohnmenge->hinterpunkt[k-1] =aktuell->hinterpunkt[k]; } /* falls kein weiteres Zeichen in der Vorgaengermenge hinter dem Punkt steht, wird fuer die neue LR-Auskunft hinter dem Punkt ein Epsilon gesetzt */ if (aktuell->hinterpunkt[1]==0) { jkmenge->hinterpunkt[0]=sohnmenge->hinterpunkt[0]=epsilon; } /* letzte Wort hinter dem Punkt muss nach dem Shiften 0 sein */ jkmenge->hinterpunkt[grenze3-1]= sohnmenge->hinterpunkt[grenze3-1]=0; jkmenge->fortsetzung=sohnmenge->fortsetzung =aktuell->fortsetzung; sohnmenge->next=malloc(groesseikmenge); sohnmenge=sohnmenge->next; sohnmenge->next=NULL; /* falls Element noch nicht in der kanonischen Kollektion ent- halten ist, wird Element uebernommen, indem der Zeiger weitergesetzt wird.*/ if (!inlrmenge(jkmenge,anfangjk)) { jkmenge->next=malloc(groesseikmenge); jkmenge=jkmenge->next; jkmenge->next=NULL; } } /* end if */ aktuell=aktuell->next; } /* end while (aktuell->next!=0) (Shiften)*/ /* aktuell wird auf den Anfang der Liste der LR-Menge des neu erstellten Knotens gesetzt, damit die Liste von vorne zum Ver- gleich durchlaufen werden kann */ aktuell=bruder->element; /* ACHTUNG haette besser in eine Prozedur gefasst werden sollen */ /* Eintragen neuer LR-Auskuenfte in die LR-Menge */ while (aktuell->next!=NULL) /* solange nicht das letzte Element erreicht ist, wenn das letzte Element der Liste erreicht ist, hat keine Aenderung der Menge stattgefunden */ { wort=aktuell->hinterpunkt[0]; /* erste Wort auf der rechten Seite der aktuellen LR-Informa- tion wird ueber prueft */ if (wort >= 100) /* falls das Zeichen ein Nonterminal ist, muss eine neue LR-Information in die Liste aufgenommen werden */ { j=0; /* solange noch Alternativen der Ableitung des Non-Terminals vorhanden sind */ while ((jhinterpunkt[1]); k=1; /* solange die Zeichen hinter dem Punkt nach Epsilon ableitbar sind, muessen auch noch die Ableitungen des Nachfolgewortes ueberprueft werden */ while ((inmenge(aktuell->hinterpunkt[k], anfang)) && (khinterpunkt[k]); } /* wenn auch das letzte Zeichen hinter dem Punkt der LR-Auskunft nach Epsilon ableitbar ist, muss auch noch der Look-Ahead in die Menge der ableitbaren Worte eingetragen werden */ if (inmenge(aktuell->hinterpunkt[k], anfang)) { terminal[aktuell->fortsetzung]=1; } /* die Worte auf die abgeleitet werden kann, werden hinter das Komma in der LR-Auskunft als Look-Ahead geschrieben */ for (k=1; k<=epsilon; k++) { if (terminal[k] == 1) { /* fuer jedes gefundene Wort, wird eine neue LR-Auskunft in die Liste geschrieben */ jkmenge->linkeseite=sohnmenge->linkeseite=wort; jkmenge->vorpunkt[0]=sohnmenge->vorpunkt[0] =epsilon; /* keine weiteren Eintr„ge vor dem Punkt */ for (l=1; lvorpunkt[l]=sohnmenge->vorpunkt[l]=0; } /* rechte Seite der Ableitung wird in LR-Auskunft einge- tragen */ for (l=0; lhinterpunkt[l] =sohnmenge->hinterpunkt[l] =mml[wort-100] [j] [l]; } /* gefundene Wort wird als Look-Ahead eingetragen */ sohnmenge->fortsetzung=terminal[k]; /* falls neu erstellte LR-Information noch nicht in der Menge vorhanden ist */ if (!inlrmenge(sohnmenge, bruder->element)) { /* Zeiger wird weitergesetzt */ sohnmenge->next=malloc(groesseikmenge); sohnmenge=sohnmenge->next; sohnmenge->next=NULL; } /* Wenn lr-Auskunft schon in der Menge enthalten ist, war der Eintrag nicht noetig, so dass kein neues Listenelement eingefuegt werden muss und das aktuelle Element der leere Puffer mit sohnmenge.next=NULL ist */ /* falls Element noch nicht in kanonischer Kollektion enthalten */ if (!inlrmenge(jkmenge, anfangjk)) { jkmenge->next=malloc(groesseikmenge); jkmenge=jkmenge->next; jkmenge->next=NULL; } } /* end if (terminal) */ } /* end for k */ j++; } /* end while (j=100)*/ /* naechste Element in der Liste wird untersucht */ aktuell=aktuell->next; } /* end while (aktuell->!=0) */ /* wenn ein neues Element in die LR1-Menge zum betrachteten Wort eingefuegt wurde, muss ein neuer Bruder fuer ein neues Wort angelegt werden */ if (gefunden) { bruder->wort=i; /* in dem Knoten wird das letzte Zeichen des Wortes von dem die LR-Menge abhaengt gespei- chert */ /* falls zu dem aktuellen Knoten noch keine identische LR-Infor- mation im Baum gefunden wurde, muessen die Nachfolger-LR-Infor- mationen zu diesem Knoten bestimmt werden */ if(!inbaum(bruder)) { lr1menge(bruder); } /* ein neuer Bruder im Baum wird generiert, in dem die Nachfolge- LR-menge des uebergebenen Knotens, entsprechend des aktuell neu hinzugenommenen Zeichens, gespeichert werden */ bruder->bruder=malloc(groessebaum); bruder->bruder->element=malloc(groesseikmenge); bruder=bruder->bruder; bruder->sohn=NULL; bruder->bruder=NULL; bruder->vater=aktuellbaum; sohnmenge=bruder->element; sohnmenge->next=NULL; } } /* end if (i!=epsilon) */ } /* end for (i) */ } /* end lr1menge */ /* Die Analyseaktionsfunktion */ ableitung f(ikelementmenge *zeiger, int token) /* *zeiger Eingabevariable Beinhaltet den Listenanfang der Liste, die die zu ueberpruefende LR-Menge repraesentiert token Eingabevariable Der Token, der als letztes aus der Tokenliste eingelesen wurde und damit den Look-Ahead in der geprueften LR-Menge darstellt */ { ableitung regel; /* In Regel wird die gefundene Ableitungsregel gespeichert ergibt die Funktion shift oder error wird shift bzw. error in links gespeichert */ int fehler=0; /* boolsche Variable fr Funktionsabbruch */ int i; /* Schleifenzaehler */ regel.links=error; while ((zeiger->next!=NULL) && (!fehler)) { if ((zeiger->hinterpunkt[0]==epsilon) && (zeiger->fortsetzung==token)) { if (regel.links==error) { regel.links=zeiger->linkeseite; i=0; while (ivorpunkt[i]; i++; } } else /* if (regel.links!=error) */ { regel.links=error; fehler=1; } } /* end if (hinterpunkt[0]==epsilon) */ /* Falls das Zeichen hinter dem Punkt ein Terminal ist, und es gleich dem uebergebenen Token ist, muss evtl. geshiftet werden */ if ((zeiger->hinterpunkt[0]==token) && (tokennext; } /* end while */ if (fehler) { printf("Keine LR1-Grammatik!"); } printf("%i\n",regel.links); return(regel); } /* end f */ /* Die Goto-Funktion */ ikliste *g(ikliste *zeiger, int token) /* *zeiger Eingabevariable Der Zeiger auf den Listenanfang der betrachteten LR-Menge token Eingabevariable Der neu eingelesene Token der an das Wort der aktuellen LR-Menge angehaengt wird, und zu dem die neue LR-Menge gesucht wird */ { int gefunden=0; /* boolsche Variable */ ikliste *aktuell; /* Variable, die den Listenanfang der neuen LR-Menge speichert */ ikelementmenge *zeiger2; /* nur zum Test der LR-Menge */ if (zeiger==NULL) /* falls alle Elemente im Keller geloescht wurden, ist ein Fehler aufgetreten */ { printf("fehler in Goto-Funktion!"); aktuell=anfangbaum; } else { aktuell=zeiger->sohn; /* Die neue LR-Menge wird in den S”hnen des aktuellen Knotens mit der alten LR-Menge gesucht */ /* Solange noch nicht alle S”hne durchsucht sind und die richtige LR- Menge noch nicht gefunden wurde */ while((aktuell->bruder!=NULL) && (!gefunden)) { if (aktuell->wort==token) /* Wird der Knoten mit dem uebergebenen Wort gefunden, kann die Suche abgebrochen werden */ { gefunden=1; /* nur zum Test der LR-Mengen */ zeiger2=anfangbaum->element; while(zeiger2->next!=NULL) { printf("%i: %i, %i, %i, %i, %i\n",token,zeiger2->linkeseite, zeiger2->vorpunkt[0],zeiger2->hinterpunkt[0], zeiger2->hinterpunkt[1],zeiger2->fortsetzung); zeiger2=zeiger2->next; } } else { aktuell=aktuell->bruder; /* sonst wird beim Bruder weitergesucht */ } } /* end while */ if (!gefunden) /* falls die LR-Menge nicht gefunden wurde, wird auch kein Zeiger fuer die LR-Menge uebergeben */ { aktuell=NULL; } } /* end if (zeiger=NULL) */ return(aktuell); } /* end g */ /********************** Function dateizeilelesen ****************/ struct zeile dateizeilelesen(int nummer,int *dateiende) /* Die einzige Anwendung dieser Function ist innerhalb der Function */ /* einlesen. Sie dient zur Dateiverwaltung. */ { struct zeile z; int i; if ((filezeiger = fopen("ausgabe",read)) ==NULL) printf("Datei konnte nicht geoeffnet werden\n"); else { for(i = 1;i<=nummer;i +=1) if (fscanf(filezeiger,"%d %10s %d %d",&z.zahl1,z.name,&z.zahl2, &z.zahl3)!=4) { i=nummer+1; *dateiende = 1; } } fclose(filezeiger); return(z); } /***********************Function einlesen *********************/ void einlesen(int *token,char name[konst],int *zeile, int *spalte,int *dateiende) /* Diese function liest aus der Datei "ausgabe." die Zeile mit der Nummer dateizeiger. Dateizeiger l„uft dabei immer im Hauptprg mit. In dateiende ist nach der Function gespeichert ob das Dateiende erreicht wurde (dateiende ist dann true).Vorsicht, wenn dateiende dann darf mit den bergebenen Werten nicht mehr gearbeitet werden */ { struct zeile z; z = dateizeilelesen(dateizeiger,dateiende); *token = z.zahl1; strcpy(name,z.name); *zeile = z.zahl2; *spalte = z.zahl3; dateizeiger++; /* z„hlt intern die globale Variable hoch */ } /* Funktion, die den Ableitungsbaum erstellt */ void ableitungsbaum() { keller *at, *hilfzeiger; /* Zeiger fuer den Keller mit den uebergebenen Token und den zugehoerigen LR-Mengen */ int laenge; /* Bestimmt die Laenge der rechten Seite einer Ableitung */ ableitung regel; /* In regel wird die Ableitung gespeichert, die die Funktionsanalysefunktion ergeben hat */ int links; /* linke Seite der gefundenen Ableitungsregel */ int gefunden, gefunden2; int ende, fehler; /* boolsche Variablen, die anzeigen ob die Tokenliste ab- gearbeitet ist oder ein fehler aufgetreten ist*/ ikliste *z; /* Zeiger auf den Listenanfang der betrachteten LR-Menge */ int spalte, zeile, token; /* Werte des Tokens, Zeile und Spalte die aus der Tokenliste eingelesen werden */ int dateiende; /* Wahrheitswert, fr Dateiende beim einlesen */ int anzahl; int knoten, dateizeile; /* Knoten ist die Tokennummer, die als Knoten in dem Ableitungsbaum gespeichert wird */ /* dateizeile ist die Zeilennummer des Vaters */ int zaehler,i, j; char name[konst]; /* Attribut des eingelesenen Tokens */ ableitungbaum *baum, *hilfzeiger2, *anfang; i=dateizeile=ende=fehler=0; z=anfangbaum; /* Am Anfang wird die LR-Menge von epsilon betrachtet deren Listenanfang am Anfang des Baumes mit den LR-Mengen steht */ at=malloc(kellergroesse); /* Der Keller wird initialisiert */ at->next=NULL; at->prev=NULL; at->token=0; at->zeile=0; at->spalte=0; strcpy(at->name,"0"); at->z=z; anfang=baum=malloc(baumgroesse); /* Initialisierung der Liste fuer Ableitungsbaum*/ baum->token=baum->spalte=baum->zeile=0; strcpy(baum->name,"0"); baum->prev=baum->next=NULL; /* Einlesen des ersten Tokens des Programms */ einlesen(&token,name,&zeile,&spalte,&dateiende); /* Der Ableitungsbaum wird so lange erstellt, bis ein Syntaxfehler entdeckt wurde oder das Ende der Tokenliste erreicht ist */ while ((!ende) && (!fehler)) { regel=f(z->element,token); /* Das Ergebnis der Analyseaktionsfunktion wird in regel gespeichert */ links=regel.links; /* bei einer Fehlermeldung kann die Funktion abgebrochen werden */ if (links==error) { fehler=1; } else { if (links==shift) { /* wenn bei shift kein Token mehr folgt, ist dies fehlerhaft */ if (token==epsilon) { fehler=1; } else /* if token!=epsilon */ { z=g(at->z,token); /* Der Zeiger wird auf die nachfolgende LR-Menge gesetzt */ if (z==NULL) /* Ist z=Null, so ist die LR-Menge leer */ { fehler=1; printf("%dhallo",token); } else /* if z!=NULL */ { hilfzeiger=at; /* Ein neues Kellerelement wird eingefuegt */ at->next=malloc(kellergroesse); at=at->next; at->prev=hilfzeiger; at->token=token; at->zeile=zeile; at->spalte=spalte; strcpy(at->name,name); at->z=z; at->next=NULL; /* Einlesen des naechsten Tokens des Programms */ i++; einlesen(&token,name,&zeile,&spalte,&dateiende); } } /* end if (token=epsilon) */ } /* end if links=shift */ else /* else if (links=shift) */ { /* wenn die Aktionsanalysefunktion eine Ableitung liefert */ /* Bestimmung der Laenge der rechten Ableitungsseite */ /* Es muessen im Keller so viele Elemente geloescht werden, wie sie auf der rechten Ableitungsseite gefunden wurden, dabei wird das Epsilon nicht mitgezaehlt, weil es kein Token ist */ gefunden2=gefunden=anzahl=laenge=0; while ((laenge=100) { anzahl++; } laenge++; } /* end while */ /* Loeschen der obersten Elemente des Kellers */ for (j=1; j<=laenge; j++) { /* wenn ein Terminal ausser den Sonderzeichen gefunden wurde, wird es in den Ableitungsbaum eingefuegt */ if (at->token<80) { baum->token=at->token; gefunden=1; strcpy(name,at->name); baum->spalte=at->spalte; baum->zeile=at->zeile; } /* ist noch kein Terminal gefunden, so wird das erste gefundene Sonderzeichen in den Ableitungsbaum eingefuegt. */ if ((!gefunden) && ((at->token>=80) && (at->token<100))) { baum->token=at->token; strcpy(name,at->name); baum->spalte=at->spalte; baum->zeile=at->zeile; gefunden2=1; } else { /* falls ueberhaupt kein Terminal auf der rechten Ableitungs- seite gefunden wurde, wird das erste Non-Terminal einge- tragen */ if ((!gefunden) && (!gefunden2)) { baum->token=80; strcpy(name,at->name); baum->spalte=at->spalte; baum->zeile=at->zeile; } } /* Loeschen des Elements im Tokenstrom */ hilfzeiger=at; at=at->prev; at->next=NULL; free(hilfzeiger); } /* end for */ /* Speichern der Ableitung in Ableitungsbaum */ dateizeile++; /* baum->token=knoten; baum->zeile=dzeile; Wird wahrscheinlich nicht mehr gebraucht baum->spalte=dspalte;*/ /* strcpy(baum->name,name); */ /* Da die Zeilennummer des Vaters im Ableitungsbaum noch nicht be- kannt ist, wird die Zeilennummer erst auf Null gesetzt */ baum->dateizeile=0; hilfzeiger2=baum; zaehler=0; /* Dieser neue Knoten hat soviele Nachfolger wie Non-Terminals ge- funden wurden. Fuer diese Nachfolger wird jetzt die Dateizeile als Vater in die jeweiligen Knoten eingetragen. */ while (zaehlerprev; if (baum->dateizeile==0); { baum->dateizeile=dateizeile; zaehler++; } } baum=hilfzeiger2; /* neues Ableitungsbaumelement wird erzeugt */ baum->next=malloc(baumgroesse); baum=baum->next; baum->prev=hilfzeiger2; baum->next=NULL; /* Ist der Keller wieder auf ein Element reduziert und die Ableitung ist das Startsymbol und das Ende der Tokenliste ist erreicht, ter- miniert an dieser Stelle die Funktion */ if ((at->prev==NULL) && (links==100) && (token==epsilon)) { ende=1; } else { z=g(at->z, links); /* sonst muss wieder eine neue LR-Menge in den Keller eingefuegt werden mit dem Non-Termi- nal auf das reduziert wurde */ if (z==NULL) /* Die LR-Menge ist leer */ { fehler=1; } else { hilfzeiger=at; /* Erstellen des neuen Kellerelements */ at->next=malloc(kellergroesse); at=at->next; at->prev=hilfzeiger; at->token=links; at->zeile=0; at->spalte=0; strcpy(at->name,"0"); at->z=z; at->next=NULL; } /* end if (z=NULL); */ } /* end if (links=100...) */ } /* end if (else links=shift) */ } /* end if (links=fehler) */ } /* end while */ if (fehler) { printf("Fehler in %i. Zeile, %i. Spalte",zeile,spalte); } else { i=0; baum=anfang; while((baum->next!=NULL) && (i!=5)) { printf("%i, %i, %i, %i\n", baum->token, baum->zeile, baum->spalte,baum->dateizeile); i++; baum=baum->next; } } } /* end ableitungsbaum */ void main () { /* Anfang main */ dateizeiger=1; /*globale Variable wird in der Function einlesen benutzt */ /*clrscr();*/ anfang = malloc(elemgroesse); /* Listenanfang wird initialisiert */ aktuell = anfang; for (i=0; i= 100) /* nur Nonterminal-Symbole werden untersucht */ { i=0; /* Ueberpruefung, ob alle anderen Symbole nach Epsilon abgeleitet werden können */ while ((i= 100 */ } /* end for k */ } /* end for j */ if ((*aktuell2).next==NULL) { ende=1; } else { l=((*aktuell2).element-100); aktuell2=(*aktuell2).next; } } if (zyklisch==1) { printf("Grammatik ist zyklisch\n"); } else { printf("Grammatik ist nicht zyklisch\n"); } lr1mengeeps(); if (anfangbaum->element->next!=NULL) { lr1menge(anfangbaum); } ableitungsbaum(); } /* end main */