home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / dtx9101 / parser / firstfol.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1991-09-12  |  4.5 KB  |  151 lines
  1. (* ------------------------------------------------------ *)
  2. (*                    FIRSTFOL.PAS                        *)
  3. (*  2.Programm: Erzeugt die First(n) einer Satzform bzw.  *)
  4. (*              die Follow(n) eines Nonterminals.         *)
  5. (*              Die Regeln werden wieder als Strings      *)
  6. (*              eingegeben; die Analyse erfolgt über      *)
  7. (*              einfachste Stringverarbeitung.            *)
  8. (*      (c) 1991 Andreas Tengicki & DMV-Verlag            *)
  9. (* ------------------------------------------------------ *)
  10. PROGRAM FirstFol;
  11.  
  12. USES FiFoQueu, Regeln, Zketten;
  13.  
  14. CONST
  15.   Count_Max = 10;
  16.  
  17. VAR
  18.   Inp, Out  : FiFo_Satz_Ptr;
  19.   Element,
  20.   Satzform  : Fifo_Element;
  21.   Regel     : Regel_Feld;
  22.   RegelAnz,
  23.   n, Modus,
  24.   Pos,
  25.   Pos2, i,
  26.   CountStop : INTEGER;
  27.   Erg       : STRING;
  28.   NonTerm,
  29.   c         : CHAR;
  30.   Flag      : BOOLEAN;
  31.  
  32.   FUNCTION nTest(Satzform : STRING; Pos : INTEGER) : BOOLEAN;
  33.     (* prüft, ob die N auf POS folgenden Symbole der *)
  34.     (* SATZFORM Terminals sind.                      *)
  35.   VAR
  36.     Flag : BOOLEAN;
  37.     i    : INTEGER;
  38.   BEGIN
  39.     Flag := TRUE;
  40.     i    := 1;
  41.     WHILE Flag AND (i <= n) AND
  42.                    (i+Pos <= LenStr(Satzform)) DO BEGIN
  43.       IF Satzform[i+Pos] IN ['A'..'Z'] THEN Flag := FALSE;
  44.       INC(i);
  45.     END;
  46.     nTest := Flag;
  47.   END;
  48.  
  49.   FUNCTION Follow(    Satzform : STRING;
  50.                   VAR Ergebnis : STRING) : BOOLEAN;
  51.     (* - ist TRUE, falls ein follow(n) von nonterm  *)
  52.     (*   in SATZFORM enthalten ist, und gibt das    *)
  53.     (*   follow(n) als ERGEBNIS zurueck.            *)
  54.     (* - sonst FALSE, ERGEBNIS ist dann undefiniert *)
  55.   VAR
  56.     Flag : BOOLEAN;
  57.     Pos  : INTEGER;
  58.   BEGIN
  59.     Pos  := InStr(NonTerm, Satzform);
  60.     Flag := (Pos = 0);
  61.     IF Flag THEN
  62.       Flag := nTest(Satzform, Pos);
  63.     IF Flag THEN
  64.       Ergebnis := TeilStr(Satzform, Pos+1, Pos+n);
  65.     Follow := Flag;
  66.   END;
  67.  
  68. BEGIN
  69.   WriteLn;
  70.   WriteLn;
  71.   WriteLn('Parserstrategien 2.Programm:');
  72.   WriteLn('     First-Follow-Erzeugung');
  73.  
  74.     (* Initialisierungen *)
  75.   FiFo_Init_d(Inp, Out);
  76.  
  77.     (* Eingaben *)
  78.   Regeleingabe(RegelAnz, Regel);
  79.   REPEAT
  80.     Write('Modus (0:First-, 1:Follow-Erzeugung): ');
  81.     ReadLn(Modus);
  82.     IF Modus = 0 THEN BEGIN
  83.       Write('Satzform: ');
  84.       InpStr(Satzform.Satz);
  85.       Write('n: ');  ReadLn(n);
  86.     END ELSE BEGIN
  87.       Write('Startsymbol: ');
  88.       InpStr(Satzform.Satz);
  89.       Write('n: ');  ReadLn(n);
  90.       Write('Zu untersuchendes Nonterminal: ');
  91.       InpChr(NonTerm);
  92.     END;
  93.     Element.Satz  := Satzform.Satz;
  94.     Element.Last  := '';
  95.     Element.Count := -1;
  96.     FiFo_In_d(Inp, Out, Element);
  97.  
  98.      (* Analyseschleife *)
  99.     CountStop := 0;
  100.     REPEAT
  101.       Fifo_Out_d(Inp, Out, Element);
  102.       IF Element.Count = 0 THEN BEGIN
  103.         IF Modus = 0 THEN BEGIN
  104.             (* Wort könnte ausgegeben werden *)
  105.           IF nTest(Element.Satz, 0) THEN
  106.             WriteLn(TeilStr(Element.Satz, 1, n));
  107.  
  108.         END ELSE IF Follow(Element.Satz, Erg) THEN BEGIN
  109.           Element.Last := Erg;
  110.           WriteLn(Erg);
  111.         END;
  112.           (* gemäß Regel ersetzen, falls Satzform noch  *)
  113.           (* interessant ist.                           *)
  114.         IF Element.Count > Count_Max THEN
  115.           INC(CountStop)
  116.         ELSE BEGIN
  117.           Satzform := Element;
  118.           FOR i := 1 TO RegelAnz DO BEGIN
  119.             Pos := InStr(Regel[i].l, Satzform.Satz);
  120.             IF Pos <> 0 THEN BEGIN
  121.               Element := Satzform;
  122.               Ersetze(Element.Satz, Regel[i], Pos);
  123.                 (* wurde First/Follow verändert ?      *)
  124.               IF Modus = 0 THEN BEGIN
  125.                 IF Pos > n THEN        (* First-Modus  *)
  126.                   INC(Element.Count)
  127.                 ELSE
  128.                   Element.Count := 0
  129.               END ELSE BEGIN           (* Follow-Modus *)
  130.                 IF Follow(Element.Satz, Erg) THEN
  131.                   IF Erg = Element.Last THEN
  132.                     INC(Element.Count)
  133.                   ELSE
  134.                     Element.Count := 0
  135.                 ELSE
  136.                   INC(Element.Count);
  137.               END;
  138.               FiFo_In_d(Inp, Out, Element);
  139.             END;
  140.           END;
  141.         END;
  142.       END;
  143.     UNTIL (Inp = NIL);
  144.     WriteLn('Abbruch bei ', CountStop:1, ' Satzformen.');
  145.  
  146.     Write('Nochmal [j/n]: ');  InpChr(c);
  147.   UNTIL c = 'n';
  148. END.
  149. (* ------------------------------------------------------ *)
  150. (*               Ende von FIRSTFOL.PAS                    *)
  151.