home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 07 / trie / triecros.mod < prev   
Encoding:
Text File  |  1989-03-02  |  11.9 KB  |  302 lines
  1. MODULE TrieCrossRef;
  2. (* M.Holzherr, April 88, MacMETH2.4.
  3.    Analyseprogramm fuer syntaktisch korrekte MODULA-2  -  Programme. Auf ein
  4.    vom Benutzer zu bezeichnendes Ausgabefile werden alle Deklarationen eines
  5.    Moduls und alle in Prozeduren verwendeten, dort aber nicht deklarierten
  6.    Bezeichner aufgelistet. Voraussetzung fuer das Funktionieren dieses Ana-
  7.    lyseprogramms ist die Existenz eines Textfiles mit allen MODULA-2  -
  8.    Schluesselworten (* dieses wird als erstes vom Programm gelesen *) .
  9.  
  10.    IMPLEMENTATIONSSPEZIFISCHE BESONDERHEITEN : Die Prozeduren OpenInput
  11.    und OpenOutput verlangen zur Laufzeit die Eingabe des entsprechenden
  12.    Eingabe- bzw. Ausgabefilenamens. Schliesst man diesen Namen mit einem
  13.    Punkt ab, so wird zum Beispiel die Extension MOD an den Filenamen ange-
  14.    haengt, wenn der Aufruf "OpenInput( 'MOD' )" lautet
  15.  
  16.    Anpassung durch TOOLBOX:
  17.      Wurde mit TopSpeed-M2 auf MS-DOS getestet, der "strengere" Compiler
  18.      erforderte einige Korrekturen.                                        *)
  19.  
  20. FROM InOut IMPORT Write, Read, WriteLn, WriteString,
  21.        (* proc *) OpenInput, CloseInput, OpenOutput, CloseOutput,
  22.        (* Boolesche Variable *)   Done ;
  23. FROM Storage IMPORT ALLOCATE, DEALLOCATE; 
  24.   
  25. CONST (* Achtung, die folgenden Konstantenwerte sind nicht willkuerlich
  26.          gewaehlt. So bedeutet z.B.   begin = 4 , dass das Wort BEGIN  auf 
  27.          dem File mit den MODULA-Schluesselworten an 4. Stelle vorkommt.   *)
  28.       begin =  4;   case  = 10;   end  = 20;
  29.       for   = 25;   if    = 30;   loop = 36;
  30.       procedure = 48;   while = 62;   with  = 63;
  31.       
  32. TYPE TRIE = POINTER TO NODE;      (* Zeiger auf Woerterbuchknoten *)
  33.      NODE = RECORD
  34.               Char : CHAR;            
  35.               syNo : INTEGER;     (* SymbolNummer; syNo <> 0 <=> Wortende  *)   
  36.               vertical,           (* vertical   = Zeiger auf "Nachkomme"   *)
  37.               horizontal : TRIE   (* horizontal = Zeiger auf "Geschwister" *)  
  38.             END;                  
  39.             
  40. VAR  ch : CHAR;                    (* letzter vom File gelesener Buchstabe *)
  41.      triesPos, noOfCharsThisLine : INTEGER; 
  42.      syCounter : INTEGER;                        (* Laufnummer der Symbole *)
  43.      outputActif, mark : BOOLEAN; 
  44.      
  45. (* -1---- skipComment ueberspringt Kommentare (auch geschachtelte)  ------ *)
  46. PROCEDURE skipComment;
  47.   VAR c : CHAR;
  48. BEGIN
  49.   c:= ch; 
  50.   REPEAT 
  51.     IF (c = '(') & (ch = '*') THEN skipComment END;
  52.     c:= ch; Read(ch)
  53.   UNTIL (c = '*') & (ch = ')')
  54. END skipComment;
  55.  
  56. (* -2---- newLine beginnt eine neue, eingerueckte Zeile -----------------  *)
  57. PROCEDURE newLine;
  58.   VAR i : INTEGER;
  59. BEGIN
  60.   IF outputActif THEN
  61.     WriteLn; noOfCharsThisLine:= 0;
  62.     FOR i:= 0 TO triesPos - 1 DO
  63.       Write(' '); Write(' '); INC( noOfCharsThisLine,2)
  64.     END;
  65.   END;
  66. END newLine;
  67.  
  68. (* -3---- put schreibt A in den Eingabestrom, falls outputActif = TRUE --- *)
  69. PROCEDURE put( A : ARRAY OF CHAR );
  70.   VAR i : INTEGER;
  71. BEGIN
  72.   IF outputActif THEN
  73.     IF INTEGER(HIGH(A)) + noOfCharsThisLine > 75 THEN newLine; END;
  74.     FOR i:= 0 TO HIGH(A) DO
  75.       Write(A[i]);
  76.       INC( noOfCharsThisLine);
  77.     END;
  78.   END;
  79. END put;
  80.  
  81. (* -4---- putInt schreibt die Integerzahl val durch Aufruf von put ------- *)
  82. PROCEDURE putInt( val : INTEGER );
  83.   VAR a : ARRAY[0..0] OF CHAR;
  84. BEGIN
  85.   IF val >= 10 THEN putInt(val DIV 10) END;
  86.   a[0]:= CHR( val MOD 10 + INTEGER(ORD('0')) ); put(a)
  87. END putInt;  
  88.  
  89. (* -5- copy(t) zeigt auf eine 1:1 - Kopie des Woerterbuchs auf das t zeigt *) 
  90. PROCEDURE copy( t : TRIE ) : TRIE;
  91.   VAR q : TRIE;
  92. BEGIN
  93.   IF t = NIL THEN RETURN NIL
  94.   ELSE ALLOCATE(q, SIZE(NODE) ); 
  95.        q^ := t^;
  96.        q^.vertical:= copy( t^.vertical); 
  97.        q^.horizontal:= copy(t^.horizontal);
  98.        RETURN q 
  99.   END
  100. END copy;
  101.  
  102. (* -6- delete(t) gibt den Speicherplatz des Gebildes auf das t zeigt frei - *)
  103. PROCEDURE delete( VAR t : TRIE (* in/out *) );
  104. BEGIN
  105.   IF t <> NIL THEN 
  106.     delete(t^.vertical);
  107.     delete(t^.horizontal); 
  108.     DEALLOCATE( t, SIZE(NODE) ); 
  109.   END
  110. END delete;
  111.   
  112.  
  113. (* 7- insert liest ein Wort buchstabenweise und fuegt es in das Woerterbuch
  114.       ein, falls es nicht schon eingetragen ist. Beim Aufruf muss der erste
  115.       Buchstabe des Wortes schon gelesen sein.                        ----- *)
  116. PROCEDURE insert( VAR p : TRIE (* in/out *); VAR sy : INTEGER (* out *) );
  117.  
  118.   (* -7-1-- make erzeugt  neuen Knoten -- *)
  119.   PROCEDURE make( VAR p : TRIE (* out *) );
  120.   BEGIN
  121.     ALLOCATE( p, SIZE( NODE) ); 
  122.     WITH p^ DO Char:= ch; syNo:= 0; vertical:= NIL; horizontal:= NIL END;
  123.   END make;
  124.   
  125.   (* -7-2-- readAndInsertNextChar liest und verarbeitet das naechste Zeichen *)
  126.   PROCEDURE readAndInsertNextChar;
  127.     VAR Ch : CHAR; a : ARRAY[0..0] OF CHAR;
  128.   BEGIN
  129.     a[0]:= ch; put(a);
  130.     Read(ch); Ch:= CAP(ch);
  131.     IF  ( (Ch >= 'A') & (Ch <= 'Z') ) OR ( (ch >= '0') & (ch <= '9') ) THEN 
  132.       insert(p^.vertical, sy)
  133.     ELSE IF (p^.syNo = 0) THEN
  134.            IF mark THEN INC( syCounter ); p^.syNo:= syCounter 
  135.            ELSE  p^.syNo:= -1
  136.            END;
  137.          END;
  138.          sy:= p^.syNo;
  139.          WHILE  (ch = '^') OR (ch = '.')
  140.             OR ((Ch >= 'A') & (Ch <= 'Z')) OR ((ch >= '0') & (ch <= '9'))  DO
  141.            Read(ch); Ch:= CAP(ch)
  142.          END;
  143.     END;
  144.   END readAndInsertNextChar;
  145.  
  146.   VAR q : TRIE;
  147. BEGIN (* insert *) 
  148.   IF p = NIL THEN            
  149.     make(p); readAndInsertNextChar;
  150.   ELSIF p^.Char > ch THEN
  151.     make(q); q^.horizontal:= p; p:= q;
  152.     readAndInsertNextChar;
  153.   ELSIF p^.Char < ch THEN 
  154.     insert(p^.horizontal, sy)
  155.   ELSE readAndInsertNextChar;
  156.   END
  157. END insert;
  158.  
  159. (* 8- print schreibt den interessanteren Teil des Woerterbuchs p alphabetisch 
  160.      geordnet auf das Ausgabemedium  --------------------------------------- *)
  161.   VAR S : ARRAY[0..100] OF CHAR; (* S[0...level] = aktueller Wortteil *)
  162. PROCEDURE print( p : TRIE; level : INTEGER );
  163.   VAR i : INTEGER; a : ARRAY[0..0] OF CHAR;
  164. BEGIN
  165.   IF p <> NIL THEN
  166.     S[level]:= p^.Char;
  167.     IF p^.syNo = -1 THEN
  168.       IF noOfCharsThisLine > 65 THEN newLine END;
  169.       FOR i:= 0 TO level DO a[0]:= S[i]; put(a) END; 
  170.       put(' ');
  171.     END;
  172.     print(p^.vertical, level + 1);
  173.     print(p^.horizontal, level  );
  174.   END
  175. END print;
  176.  
  177. (* hier folgen Konstanten und Variablen, die nur vom Hauptprogramm benoetigt
  178.    werden                                                                    *)
  179.   CONST n = 20;
  180.   VAR c : CHAR; 
  181.       a : ARRAY[0..0] OF CHAR;
  182.       waitSemicolon  : BOOLEAN; (* waitSemicolon = TRUE <=> naechstes Semicolon
  183.                                    beendet eine Prozedur                     *)
  184.       equalSignFound : BOOLEAN; 
  185.       keys  : TRIE; (*zeigt auf Woerterbuch mit den MODULA-Schluesselwoertern*)
  186.       
  187.       Tries : ARRAY[0..n] OF TRIE; 
  188.                  (* Tries[i] zeigt auf das Woerterbuch der Bezeichner, die zur 
  189.                     aktuellen Prozedur der Verschachtelungstiefe i gehoert   *)
  190.       NoOfProcs : ARRAY[0..n] OF INTEGER; (* NoOfProcs[i] = Anzahl Prozeduren
  191.                                              der Verschachtelungstiefe i     *)
  192.       noOfEndExpected, rBracketExpected, i : INTEGER;
  193.       SY : INTEGER; 
  194. BEGIN (* TrieCrossRef *)
  195.   outputActif:= TRUE; mark:= TRUE; 
  196.   syCounter:= 0; noOfCharsThisLine:= 0; triesPos:= 0; NoOfProcs[triesPos]:= 0;
  197.   keys:= NIL; FOR i:= 0 TO n DO Tries[i]:= NIL END;
  198.   WriteString('Namen des Files mit den Modula-Schluesselwoertern eingeben :' );
  199.   OpenInput('MOD');
  200.   Read(ch);
  201.   WHILE Done DO        (* Done = FALSE bedeutet Fileende erreicht *)
  202.     IF (ch >= 'A') & (ch <= 'Z') THEN insert(keys, SY); put(' ') END; 
  203.     IF ch = '(' THEN Read(ch); IF ch = '*' THEN skipComment END   END;
  204.     Read(ch) 
  205.   END;             
  206.   CloseInput; WriteLn; 
  207.   WriteLn; Tries[triesPos]:= copy(keys);
  208.   noOfEndExpected:= 0; rBracketExpected:= 0; waitSemicolon:= FALSE;
  209.   WriteLn;
  210.   WriteString('Namen des zu analysierenden Programmfiles eingeben :');
  211.   OpenInput('MOD');
  212.   WriteLn;
  213.   WriteString('-- Cross-Reference-Analyse wird gleich gestartet! -- ');
  214.   WriteLn;
  215.   WriteString('Namen des Files eingeben, auf das die Analyse auszugeben ist:');
  216.   OpenOutput('MOD');
  217.   WriteString('DEKLARATIONEN UND NICHT LOKALE  BEZEICHNER  '  );
  218.   WriteLn; WriteLn;
  219.   Read(ch);
  220.   LOOP
  221.     IF NOT Done THEN (* Fileende erreicht *) EXIT END;
  222.     CASE ch OF
  223.       '(' : Read(ch); IF ch = '*' THEN 
  224.                         skipComment;                        Read(ch)
  225.                       ELSE put('('); INC(rBracketExpected); 
  226.                       END;                                
  227.     | ')' : put(')'); DEC(rBracketExpected);                Read(ch)
  228.     | '=' : put('= '); equalSignFound:= TRUE;               Read(ch) 
  229.     | ':' : put(': '); equalSignFound:= TRUE;               Read(ch)  
  230.     | ';' : put('; '); equalSignFound:= FALSE;
  231.                       IF waitSemicolon THEN
  232.                         outputActif:= TRUE; waitSemicolon:= FALSE; newLine;
  233.                       ELSIF (rBracketExpected = 0) THEN 
  234.                             newLine;      
  235.                       END;                                  Read(ch)
  236.     | "'", '"'  : c:= ch; a[0]:= ch; put(a);
  237.                   REPEAT Read(ch); a[0]:= ch; put(a) UNTIL ch = c; 
  238.                                                             Read(ch)
  239.     | '0'..'9'  : a[0]:= ch; put(a);                        Read(ch)
  240.     | 'a'..'z',
  241.       'A'..'Z'  : IF noOfCharsThisLine > 65 THEN newLine END;
  242.                   insert(Tries[triesPos],SY); put(' ');
  243.                   CASE SY OF case, for, if, loop, while, with :
  244.                              IF NOT mark THEN INC(noOfEndExpected) END;
  245.                   ELSE
  246.                   END;
  247.                   CASE SY OF
  248.                     begin : put('  ');
  249.                             FOR i:= 0 TO triesPos - 1 DO
  250.                               put('-'); putInt(NoOfProcs[i])
  251.                             END;
  252.                             put('- ');
  253.                             outputActif:= FALSE; mark:= FALSE;
  254.                             INC(noOfEndExpected);
  255.                   | end   : IF NOT mark THEN 
  256.                               DEC(noOfEndExpected);
  257.                               IF noOfEndExpected = 0 THEN
  258.                                 outputActif:= TRUE;
  259.                                 put('  GLOBAL DEKLARIERT   -> ');
  260.                                 print(Tries[triesPos], 0); put(' <-');
  261.                                 newLine;
  262.                                 DEC(triesPos);
  263.                                 IF triesPos < 0 THEN (* Moduleende erreicht *)
  264.                                   EXIT 
  265.                                 END;
  266.                                 outputActif:= FALSE;
  267.                                 waitSemicolon:= TRUE; mark:= TRUE
  268.                               END
  269.                             END
  270.                   | procedure 
  271.                           : IF NOT equalSignFound THEN 
  272.                           (* PROCEDURE leitet Prozedur ein, kein Prozedurtyp *)
  273.                               INC(NoOfProcs[triesPos]);
  274.                               FOR i:= 0 TO triesPos DO
  275.                                 put('-'); putInt(NoOfProcs[i])
  276.                               END;
  277.                               put('- ');
  278.                               INC(triesPos); NoOfProcs[triesPos]:= 0;
  279.                               delete(Tries[triesPos]); 
  280.                               Tries[triesPos]:= copy(keys)
  281.                             END
  282.                  ELSE
  283.                  END (* CASE *)
  284.     
  285.     ELSE IF ch <= ' ' THEN   
  286.            REPEAT Read(ch) UNTIL NOT Done OR (ch > ' ');
  287.            IF NOT Done THEN EXIT END
  288.          ELSE a[0]:= ch; put(a); put(' '); Read(ch)
  289.          END
  290.     END (* CASE *)
  291.   END; (* LOOP *)
  292.   CloseInput; CloseOutput;
  293.   WriteString('fertig'); Read(ch); 
  294.   END TrieCrossRef.                    
  295.          
  296.   
  297.  
  298.  
  299.    
  300.                  
  301.                                    
  302.