home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / compiler / small_c / cb / sources / pat.c < prev    next >
Encoding:
Text File  |  1985-07-22  |  6.5 KB  |  248 lines
  1.  
  2. /*
  3. ** pat.c -- pattern making and matching functions
  4. */
  5.  
  6. /*
  7. ** addset -- put c in set & increment j
  8. */
  9. addset(c, set, j, maxsiz) char c, set[]; int *j, maxsiz; {
  10.   if(*j >= maxsiz) return NO;
  11.   set[*j]=c;
  12.   *j = *j + 1;
  13.   return YES;
  14.   }
  15.  
  16. /*
  17. ** amatch -- look for match starting at lin[from]
  18. */
  19. amatch(lin, from, pat) char lin[], pat[]; int from; {
  20.   int i, j, offset, stack;
  21.   stack = -1;
  22.   offset=from;
  23.   j=0;
  24.   while(pat[j]!=NULL) {
  25.     if(pat[j]==CLOSURE) {
  26.       stack=j;
  27.       j=j+CLOSIZE;
  28.       i=offset;
  29.       while(lin[i]!=NULL) {
  30.         if(omatch(lin, &i, pat, j)==NO) break;
  31.         }
  32.       pat[stack+COUNT]=i-offset;
  33.       pat[stack+START]=offset;
  34.       offset=i;
  35.       }
  36.     else if(omatch(lin, &offset, pat, j)==NO) {
  37.       while(stack >= 0) {
  38.         if(pat[stack+COUNT] > 0) break;
  39.         stack=pat[stack+PREVCL];
  40.         }
  41.       if(stack < 0) return -1;
  42.       pat[stack+COUNT]=pat[stack+COUNT]-1;
  43.       j=stack+CLOSIZE;
  44.       offset=pat[stack+START]+pat[stack+COUNT];
  45.       }
  46.     j=j+patsiz(pat, j);
  47.     }
  48.   return offset;
  49.   }
  50.  
  51. /*
  52. ** dodash -- expand array[i-1] - array[i+1] into set[j]...
  53. */
  54. dodash(valid, array, i, set, j, maxset)
  55.   char valid[], set[], array[]; int *i, *j, maxset; {
  56.   int k, limit;
  57.   *i = 1 + *i;
  58.   *j = -1 + *j;
  59.   limit=index(valid, esc(array, i));
  60.   k=index(valid, set[*j]);
  61.   while(k <= limit)
  62.     addset(valid[k++], set, j, maxset);
  63.   }
  64.  
  65. /*
  66. ** esc -- map array[i] into escaped char if appropriate
  67. */
  68. esc(array, i) char array[]; int *i; {
  69.   if(array[*i]!=ESCAPE) return array[*i];
  70.   else if(array[ *i + 1]==NULL)    /* esc not special at end */
  71.     return ESCAPE;
  72.   else {
  73.     *i= *i + 1;
  74.     if(array[*i]=='n') return '\n';
  75.     else if(array[*i]=='t') return '\t';
  76.     else if(array[*i]=='b') return '\b';
  77.     else if(array[*i]=='s') return ' ';
  78.     else return array[*i];
  79.     }
  80.   }
  81.  
  82. /*
  83. ** filset -- expand set in array into set stopping at delim
  84. */
  85. filset(delim, array, i, set, j, maxset)
  86.   char delim, array[], set[]; int *i, *j, maxset; {
  87.   char *digits, *lowalf, *upalf;
  88.   digits="0123456789";
  89.   lowalf="abcdefghijklmnopqrstuvwxyz";
  90.   upalf="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  91.   while((array[*i]!=delim)&(array[*i]!=NULL)) {
  92.     if(array[*i]==ESCAPE)
  93.       addset(esc(array, i), set, j, maxset);
  94.     else if(array[*i]!='-')
  95.       addset(array[*i], set, j, maxset);
  96.     else if((j <= 0)|(array[*i+1]==NULL))    /* literal - */
  97.       addset('-', set, j, maxset);
  98.     else if(index(digits, set[*j -1]) > -1)
  99.       dodash(digits, array, i, set, j, maxset);
  100.     else if(index(lowalf, set[*j -1]) > -1)
  101.       dodash(lowalf, array, i, set, j, maxset);
  102.     else if(index(upalf, set[*j -1]) > -1)
  103.       dodash(upalf, array, i, set, j, maxset);
  104.     else addset('-', set, j, maxset);
  105.     *i = *i + 1;
  106.     }
  107.   }
  108.  
  109. /*
  110. ** getccl -- expand char class at arg[i] into pat[j]
  111. */
  112. getccl(arg, i, pat, j) char arg[], pat[]; int *i, *j; {
  113.   int jstart;
  114.   *i = *i + 1;  /**** skip over '[' in arg ****/
  115.   if(arg[*i]==NOT) {
  116.     addset(NCCL, pat, j, MAXPAT);
  117.     *i = *i + 1;
  118.     }
  119.   else addset(CCL, pat, j, MAXPAT);
  120.   jstart = *j;
  121.   addset(0, pat, j, MAXPAT);  /**** leave room for count ****/
  122.   filset(CCLEND, arg, i, pat, j, MAXPAT);
  123.   pat[jstart] = *j - jstart - 1;
  124.   if(arg[*i]==CCLEND) return YES;
  125.   return ERR;
  126.   }
  127.  
  128. /*
  129. ** locate -- look for c in char class at pat[offset]
  130. */
  131. locate(c, pat, offset) char c, pat[]; int offset; {
  132.   int i;
  133.   /*
  134.   ** size of class is at pat[offset], characters follow
  135.   */
  136.   i=offset+pat[offset];
  137.   while( i > offset) {
  138.     if(c==pat[i--]) return YES;
  139.     }
  140.   return NO;
  141.   }
  142.  
  143. /*
  144. ** makpat -- make pattern from arg[from], end at delim
  145. */
  146. makpat(arg, from, delim, pat) char arg[], delim, pat[]; int from; {
  147.   int i, j, lastcl, lastj, lj;
  148.   j=lastj=0;
  149.   lastcl = -1;
  150.   i=from;
  151.   while((arg[i]!=delim)&(arg[i]!=NULL)) {
  152.     lj=j;
  153.     if(arg[i]==ANY) addset(ANY, pat, &j, MAXPAT);
  154.     else if((arg[i]==BOL)&(i==from)) addset(BOL, pat, &j, MAXPAT);
  155.     else if((arg[i]==EOL)&(arg[i+1]==delim)) addset(EOL, pat, &j, MAXPAT);
  156.     else if(arg[i]==CCL) {
  157.       if(getccl(arg, &i, pat, &j)==ERR) break;
  158.       }
  159.     else if((arg[i]==CLOSURE)&(i>from)) {
  160.       lj=lastj;
  161.       if((pat[lj]==BOL)|(pat[lj]==EOL)|(pat[lj]==CLOSURE)) break;
  162.       lastcl=stclos(pat, &j, &lastj, lastcl);
  163.       }
  164.     else {
  165.       addset(CHAR, pat, &j, MAXPAT);
  166.       addset(esc(arg, &i), pat, &j, MAXPAT);
  167.       }
  168.     lastj=lj;
  169.     ++i;
  170.     }
  171.   if((arg[i]!=delim)|(addset(NULL, pat, &j, MAXPAT)==NO)) return ERR;
  172.   return i;
  173.   }
  174.  
  175. /*
  176. ** match -- find match anywhere in line
  177. */
  178. match(line, pattern) char line[], pattern[]; {
  179.   int i;
  180.   i=0;
  181.   while(YES) {
  182.     if(amatch(line, i, pattern) >= 0) return YES;
  183.     if(line[i++]==NULL) return NO;
  184.     }
  185.   }
  186.  
  187. /*
  188. ** omatch -- try to match a single pattern at pat[j]
  189. */
  190. omatch(lin, i, pat, j) char lin[], pat[]; int *i, j; {
  191.   int bump;
  192.   bump = -1;
  193.   if(pat[j]==BOL) {
  194.     if(*i==0) bump=0;
  195.     }
  196.   else if(pat[j]==EOL) {
  197.     if(lin[*i]==NULL) bump=0;
  198.     }
  199.   else if(lin[*i]==NULL) return NO;
  200.   else if(pat[j]==CHAR) {
  201.     if(lin[*i]==pat[j+1]) bump=1;
  202.     }
  203.   else if(pat[j]==ANY) bump=1;
  204.   else if(pat[j]==CCL) {
  205.     if(locate(lin[*i], pat, j+1)==YES) bump=1;
  206.     }
  207.   else if(pat[j]==NCCL) {
  208.     if(locate(lin[*i], pat, j+1)==NO) bump=1;
  209.     }
  210.   else error("in omatch: can't happen\n");
  211.   if(bump >= 0) {
  212.     *i = *i + bump;
  213.     return YES;
  214.     }
  215.   return NO;
  216.   }
  217.  
  218. /*
  219. ** patsiz -- returns size of entry at pat[n]
  220. */
  221. patsiz(pat, n) char *pat; int n; {
  222.   pat=pat+n;
  223.   if(*pat==CHAR) return 2;
  224.   else if((*pat==BOL)|(*pat==EOL)|(*pat==ANY)) return 1;
  225.   else if((*pat==CCL)|(*pat==NCCL)) return (*(++pat)+2);
  226.   else if(*pat==CLOSURE) return CLOSIZE;
  227.   else error("in patsiz: can't happen\n");
  228.   }
  229.  
  230. /*
  231. ** stclos -- insert closure entry at pat[j]
  232. */
  233. stclos(pat, j, lastj, lastcl) char pat[]; int *j, *lastj, lastcl; {
  234.   int jp, jt;
  235.   jp = *j - 1;
  236.   while(jp >= *lastj) {   /**** make hole for closure ****/
  237.     jt = jp + CLOSIZE;
  238.     addset(pat[jp--], pat, &jt, MAXPAT);
  239.     }
  240.   *j = *j + CLOSIZE;
  241.   jp = *lastj;
  242.   addset(CLOSURE, pat, lastj, MAXPAT);  /** CLOSURE **/
  243.   addset(0, pat, lastj, MAXPAT);        /** COUNT **/
  244.   addset(lastcl, pat, lastj, MAXPAT);   /** PREVCL **/
  245.   addset(0, pat, lastj, MAXPAT);        /** START **/
  246.   return jp;
  247.   }
  248.