home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ctcoll95.zip / AEHNLICH / PARSER.C < prev    next >
C/C++ Source or Header  |  1995-04-06  |  4KB  |  123 lines
  1. /* parser.c: Muster-Parser als "Finite State Machine"
  2.  *
  3.  * (c) Guido Gronek, Lion Ges. f. Systementwicklung m.b.H. & c't 5/95
  4.  */
  5. #include <limits.h>
  6. #include <string.h>
  7. #include "parser.h"
  8.  
  9. static int init(), copen(), cinvrt(), cadd(), cminus();
  10.  
  11. int (*statefunc[]) () = {       /* Zustandsfunktionen der FSM */
  12. init,   user,   copen,  cinvrt, cadd,   cminus};
  13.  
  14. enum states {                        /* alle Zustaende der FSM */
  15. INIT, USER,  COPEN, CINVRT, CADD,  CMINUS,
  16. ERR, END};
  17.  
  18. int transtable[] = {              /* Zustandsuebergangstabelle */
  19. USER, USER,  CADD,  CADD,   CADD,  CADD,       /* T_CHAR */
  20. USER, USER,  CADD,  CADD,   CADD,  CADD,         /* T_QM */
  21. USER, USER,  CADD,  CADD,   CADD,  CADD,        /* T_STAR */
  22. COPEN,COPEN, ERR,   ERR,    ERR,   ERR,       /* T_LPAREN */
  23. USER, USER,  CINVRT,CADD,   CADD,  CADD,      /* T_CINVRT */
  24. USER, USER,  ERR,   ERR,    CMINUS,CADD,       /* T_MINUS */
  25. ERR,  ERR,   ERR,   ERR,    USER,  ERR,       /* T_RPAREN */
  26. END,  END,   ERR,   ERR,    ERR,   ERR,          /* T_EOT */
  27. ERR,  ERR,   ERR,   ERR,    ERR,   ERR,         /* T_ILL */
  28. USER, USER,  CADD,  CADD,   CADD,  CADD,      /* T_LBRAC */
  29. ERR,  USER,  CADD,  CADD,   CADD,  CADD,      /* T_RBRAC */
  30. ERR,  USER,  CADD,  CADD,   CADD,  CADD,      /* T_OR */
  31. };
  32.  
  33. struct token_t Token, Lasttoken;
  34. char *Pattern;
  35. charset_t Cset;
  36. int Protected;
  37. static rangefrom, csetfill;
  38.  
  39. /* gettoken() holt das naechstes Token
  40.  * Ergebnis: der Type des Token
  41.   */
  42. int gettoken(char **pattern)
  43. { int c, t = T_CHAR;
  44.   char *p = *pattern;
  45.  
  46.   Lasttoken = Token;
  47.   if ( (c = *p++) == '\\' ) {   /* durch Backslash geschuetzt */
  48.     if ( (c = *p++) == 0 )      /* Backslash am Ende */
  49.       t = T_ILL;                /* nicht erlaubt ! */
  50.   }
  51.   else {                      /* nicht geschuetztes Zeichen */
  52.     switch ( c ) {
  53.       case '?' : t = T_QM; break;
  54.       case '*' : t = T_STAR; break;
  55.       case '[' : t = T_LPAREN; break;
  56.       case ']' : t = T_RPAREN; break;
  57.       case '-' : t = T_MINUS; break;
  58.       case '{' : t = T_LBRAC; break;
  59.       case '}' : t = T_RBRAC; break;
  60.       case '|' : t = T_OR; break;
  61.       case '!' :
  62.       case '^' : t = T_CINVRT; break;
  63.       case 0   : t = T_EOT;
  64.     }
  65.   }
  66.   *pattern = p;
  67.   return Token.value = c, Token.type = t;
  68. }
  69.  
  70. int init(void)                      /* initialisiert den Parser */
  71. { memset(&Token,0,sizeof(Token));
  72.   return Protected = 0;
  73. }
  74.  
  75. int copen(void)                  /* oeffnet eine Zeichenklasse */
  76. { memset(&Cset,0,sizeof(Cset));
  77.   csetfill = 1;
  78.   return rangefrom = 0;
  79. }
  80.  
  81. int cinvrt(void)              /* erzeugt eine Komplement-Klasse */
  82. { memset(&Cset,1,sizeof(Cset));
  83.   return csetfill = 0;
  84. }
  85.  
  86. int cminus(void)   /* merkt sich Anfang eines Zeichenbereiches */
  87. { rangefrom = Lasttoken.value;
  88.   return 0;
  89. }
  90.  
  91. int cadd(void)                  /* fuegt Zeichen in Klasse ein */
  92. { int c, rangeto = Token.value;
  93.  
  94.   if ( !rangefrom ) rangefrom = rangeto;
  95.   if ( rangefrom > rangeto ) {
  96.     c = rangefrom; rangefrom = rangeto; rangeto = c;
  97.   }
  98.   for ( c = rangefrom; c <= rangeto; ++c )
  99.     Cset[c] = csetfill;
  100.   return rangefrom = 0;
  101. }
  102.  
  103. /* parsepattern():
  104.  * Durchlaueft in einer Schleife verschiedene Zustaende, bis ein
  105.  * Endzustand erreicht ist. Der jeweils naechste Zustand ergibt
  106.  * sich mit Hilfe einer Uebergangstabelle aus dem Zustand selbst
  107.  * und dem naechsten Token. Fuer jeden Zustand wird die passende
  108.  * Zustandsfunktion geholt und ausfuehrt.
  109.  */
  110. int parsepattern(char **pattern)
  111. { int state = INIT;                         /* Ausgangszustand */
  112.   Pattern = *pattern;
  113.  
  114.   do {
  115.     if ( statefunc[state]() )            /* Funktion ausfuehren */
  116.       state = ERR;
  117.     else
  118.       state = transtable[state+gettoken(&Pattern)];
  119.   } while ( state < ERR );
  120.   if ( Protected || Token.type==T_OR ) state = ERR;
  121.   return *pattern = Pattern-1 , (state  - END);
  122. }
  123.