pd.if.org Git - pccts/blob - support/rexpr/rexpr.c

   1 /*
   2  * This file contains code for
   3  *
   4  *      int rexpr(char *expr, char *s);
   5  *
   6  * which answers
   7  *
   8  *      1 if 's' is in the language described by the regular expression 'expr'
   9  *      0 if it is not
  10  *     -1 if the regular expression is invalid
  11  *
  12  * Language membership is determined by constructing a non-deterministic
  13  * finite automata (NFA) from the regular expression.  A depth-
  14  * first-search is performed on the NFA (graph) to check for a match of 's'.
  15  * Each non-epsilon arc consumes one character from 's'.  Backtracking is
  16  * performed to check all possible paths through the NFA.
  17  *
  18  * Regular expressions follow the meta-language:
  19  *
  20  * <regExpr>        ::= <andExpr> ( '|' <andExpr> )*
  21  *
  22  * <andExpr>        ::= <expr> ( <expr> )*
  23  *
  24  * <expr>           ::= {'~'} '[' <atomList> ']' <repeatSymbol>
  25  *                      | '(' <regExpr> ')' <repeatSymbol>
  26  *                      | '{' <regExpr> '}' <repeatSymbol>
  27  *                      | <atom> <repeatSymbol>
  28  *
  29  * <repeatSymbol>   ::= { '*' | '+' }
  30  *
  31  * <atomList>       ::= <atom> ( <atom> )*
  32  *                      | { <atomList> } <atom> '-' <atom> { <atomList> }
  33  *
  34  * <atom>           ::= Token[Atom]
  35  *
  36  * Notes:
  37  *              ~       means complement the set in [..]. i.e. all characters not listed
  38  *              *       means match 0 or more times (can be on expression or atom)
  39  *              +       means match 1 or more times (can be on expression or atom)
  40  *              {}      optional
  41  *              ()      grouping
  42  *              []      set of atoms
  43  *              x-y     all characters from x to y (found only in [..])
  44  *              \xx the character with value xx
  45  *
  46  * Examples:
  47  *              [a-z]+
  48  *                      match 1 or more lower-case letters (e.g. variable)
  49  *
  50  *              0x[0-9A-Fa-f]+
  51  *                      match a hex number with 0x on front (e.g. 0xA1FF)
  52  *
  53  *              [0-9]+.[0-9]+{e[0-9]+}
  54  *                      match a floating point number (e.g. 3.14e21)
  55  *
  56  * Code example:
  57  *              if ( rexpr("[a-zA-Z][a-zA-Z0-9]+", str) ) then str is keyword
  58  *
  59  * Terence Parr
  60  * Purdue University
  61  * April 1991
  62  */
  63
  64 #include <stdio.h>
  65 #include <ctype.h>
  66 #ifdef __STDC__
  67 #include <stdlib.h>
  68 #else
  69 #include <malloc.h>
  70 #endif
  71 #include "rexpr.h"
  72
  73 #ifdef __STDC__
  74 static int regExpr( GraphPtr g );
  75 static int andExpr( GraphPtr g );
  76 static int expr( GraphPtr g );
  77 static int repeatSymbol( GraphPtr g );
  78 static int atomList( char *p, int complement );
  79 static int next( void );
  80 static ArcPtr newGraphArc( void );
  81 static NodePtr newNode( void );
  82 static int ArcBetweenGraphNode( NodePtr i, NodePtr j, int label );
  83 static Graph BuildNFA_atom( int label );
  84 static Graph BuildNFA_AB( Graph A, Graph B );
  85 static Graph BuildNFA_AorB( Graph A, Graph B );
  86 static Graph BuildNFA_set( char *s );
  87 static Graph BuildNFA_Astar( Graph A );
  88 static Graph BuildNFA_Aplus( Graph A );
  89 static Graph BuildNFA_Aoptional( Graph A );
  90 #else
  91 static int regExpr();
  92 static int andExpr();
  93 static int expr();
  94 static int repeatSymbol();
  95 static int atomList();
  96 static int next();
  97 static ArcPtr newGraphArc();
  98 static NodePtr newNode();
  99 static int ArcBetweenGraphNode();
 100 static Graph BuildNFA_atom();
 101 static Graph BuildNFA_AB();
 102 static Graph BuildNFA_AorB();
 103 static Graph BuildNFA_set();
 104 static Graph BuildNFA_Astar();
 105 static Graph BuildNFA_Aplus();
 106 static Graph BuildNFA_Aoptional();
 107 #endif
 108
 109 static char *_c;
 110 static int token, tokchar;
 111 static NodePtr accept;
 112 static NodePtr freelist = NULL;
 113
 114 /*
 115  * return 1 if s in language described by expr
 116  *        0 if s is not
 117  *       -1 if expr is an invalid regular expression
 118  */
 119 rexpr(expr, s)
 120 char *expr, *s;
 121 {
 122         NodePtr p,q;
 123         Graph nfa;
 124         int result;
 125
 126         fprintf(stderr, "rexpr(%s,%s);\n", expr,s);
 127         freelist = NULL;
 128         _c = expr;
 129         next();
 130         if ( regExpr(&nfa) == -1 ) return -1;
 131         accept = nfa.right;
 132         result = match(nfa.left, s);
 133         /* free all your memory */
 134         p = q = freelist;
 135         while ( p!=NULL ) { q = p->track; free(p); p = q; }
 136         return result;
 137 }
 138
 139 /*
 140  * do a depth-first-search on the NFA looking for a path from start to
 141  * accept state labelled with the characters of 's'.
 142  */
 143 match(automaton, s)
 144 NodePtr automaton;
 145 char *s;
 146 {
 147         ArcPtr p;
 148
 149         if ( automaton == accept && *s == '\0' ) return 1;      /* match */
 150
 151         for (p=automaton->arcs; p!=NULL; p=p->next)                     /* try all arcs */
 152         {
 153                 if ( p->label == Epsilon )
 154                 {
 155                         if ( match(p->target, s) ) return 1;
 156                 }
 157                 else if ( p->label == *s )
 158                                 if ( match(p->target, s+1) ) return 1;
 159         }
 160         return 0;
 161 }
 162
 163 /*
 164  * <regExpr>        ::= <andExpr> ( '|' {<andExpr>} )*
 165  *
 166  * Return -1 if syntax error
 167  * Return  0 if none found
 168  * Return  1 if a regExrp was found
 169  */
 170 static
 171 regExpr(g)
 172 GraphPtr g;
 173 {
 174         Graph g1, g2;
 175
 176         if ( andExpr(&g1) == -1 )
 177         {
 178                 return -1;
 179         }
 180
 181         while ( token == '|' )
 182         {
 183                 int a;
 184                 next();
 185                 a = andExpr(&g2);
 186                 if ( a == -1 ) return -1;       /* syntax error below */
 187                 else if ( !a ) return 1;        /* empty alternative */
 188                 g1 = BuildNFA_AorB(g1, g2);
 189         }
 190
 191         if ( token!='\0' ) return -1;
 192
 193         *g = g1;
 194         return 1;
 195 }
 196
 197 /*
 198  * <andExpr>        ::= <expr> ( <expr> )*
 199  */
 200 static
 201 andExpr(g)
 202 GraphPtr g;
 203 {
 204         Graph g1, g2;
 205
 206         if ( expr(&g1) == -1 )
 207         {
 208                 return -1;
 209         }
 210
 211         while ( token==Atom || token=='{' || token=='(' || token=='~' || token=='[' )
 212         {
 213                 if (expr(&g2) == -1) return -1;
 214                 g1 = BuildNFA_AB(g1, g2);
 215         }
 216
 217         *g = g1;
 218         return 1;
 219 }
 220
 221 /*
 222  * <expr>           ::=    {'~'} '[' <atomList> ']' <repeatSymbol>
 223  *                      | '(' <regExpr> ')' <repeatSymbol>
 224  *                      | '{' <regExpr> '}' <repeatSymbol>
 225  *                      | <atom> <repeatSymbol>
 226  */
 227 static
 228 expr(g)
 229 GraphPtr g;
 230 {
 231         int complement = 0;
 232         char s[257];    /* alloc space for string of char in [] */
 233
 234         if ( token == '~' || token == '[' )
 235         {
 236                 if ( token == '~' ) {complement = 1; next();}
 237                 if ( token != '[' ) return -1;
 238                 next();
 239                 if ( atomList( s, complement ) == -1 ) return -1;
 240                 *g = BuildNFA_set( s );
 241                 if ( token != ']' ) return -1;
 242                 next();
 243                 repeatSymbol( g );
 244                 return 1;
 245         }
 246         if ( token == '(' )
 247         {
 248                 next();
 249                 if ( regExpr( g ) == -1 ) return -1;
 250                 if ( token != ')' ) return -1;
 251                 next();
 252                 repeatSymbol( g );
 253                 return 1;
 254         }
 255         if ( token == '{' )
 256         {
 257                 next();
 258                 if ( regExpr( g ) == -1 ) return -1;
 259                 if ( token != '}' ) return -1;
 260                 next();
 261                 /* S p e c i a l  C a s e   O p t i o n a l  {  } */
 262                 if ( token != '*' && token != '+' )
 263                 {
 264                         *g = BuildNFA_Aoptional( *g );
 265                 }
 266                 repeatSymbol( g );
 267                 return 1;
 268         }
 269         if ( token == Atom )
 270         {
 271                 *g = BuildNFA_atom( tokchar );
 272                 next();
 273                 repeatSymbol( g );
 274                 return 1;
 275         }
 276
 277         return -1;
 278 }
 279
 280 /*
 281  * <repeatSymbol>   ::= { '*' | '+' }
 282  */
 283 static
 284 repeatSymbol(g)
 285 GraphPtr g;
 286 {
 287         switch ( token )
 288         {
 289                 case '*' : *g = BuildNFA_Astar( *g ); next(); break;
 290                 case '+' : *g = BuildNFA_Aplus( *g ); next(); break;
 291         }
 292         return 1;
 293 }
 294
 295 /*
 296  * <atomList>       ::= <atom> { <atom> }*
 297  *                      { <atomList> } <atom> '-' <atom> { <atomList> }
 298  *
 299  * a-b is same as ab
 300  * q-a is same as q
 301  */
 302 static
 303 atomList(p, complement)
 304 char *p;
 305 int complement;
 306 {
 307         static unsigned char set[256];          /* no duplicates */
 308         int first, last, i;
 309         char *s = p;
 310
 311         if ( token != Atom ) return -1;
 312
 313         for (i=0; i<256; i++) set[i] = 0;
 314         while ( token == Atom )
 315         {
 316                 if ( !set[tokchar] ) *s++ = tokchar;
 317                 set[tokchar] = 1;                       /* Add atom to set */
 318                 next();
 319                 if ( token == '-' )             /* have we found '-' */
 320                 {
 321                         first = *(s-1);             /* Get last char */
 322                         next();
 323                         if ( token != Atom ) return -1;
 324                         else
 325                         {
 326                                 last = tokchar;
 327                         }
 328                         for (i = first+1; i <= last; i++)
 329                         {
 330                                 if ( !set[tokchar] ) *s++ = i;
 331                                 set[i] = 1;                     /* Add atom to set */
 332                         }
 333                         next();
 334                 }
 335         }
 336         *s = '\0';
 337         if ( complement )
 338         {
 339                 for (i=0; i<256; i++) set[i] = !set[i];
 340                 for (i=1,s=p; i<256; i++) if ( set[i] ) *s++ = i;
 341                 *s = '\0';
 342         }
 343         return 1;
 344 }
 345
 346 /* a somewhat stupid lexical analyzer */
 347 static
 348 next()
 349 {
 350         while ( *_c==' ' || *_c=='\t' || *_c=='\n' ) _c++;
 351         if ( *_c=='\\' )
 352         {
 353                 _c++;
 354                 if ( isdigit(*_c) )
 355                 {
 356                         int n=0;
 357                         while ( isdigit(*_c) )
 358                         {
 359                                 n = n*10 + (*_c++ - '0');
 360                         }
 361                         if ( n>255 ) n=255;
 362                         tokchar = n;
 363                 }
 364                 else
 365                 {
 366                         switch (*_c)
 367                         {
 368                                 case 'n' : tokchar = '\n'; break;
 369                                 case 't' : tokchar = '\t'; break;
 370                                 case 'r' : tokchar = '\r'; break;
 371                                 default  : tokchar = *_c;
 372                         }
 373                         _c++;
 374                 }
 375                 token = Atom;
 376         }
 377         else if ( isgraph(*_c) && *_c!='[' && *_c!='(' && *_c!='{' &&
 378                           *_c!='-' && *_c!='}' && *_c!=')' && *_c!=']' &&
 379                           *_c!='+' && *_c!='*' && *_c!='~' && *_c!='|' )
 380         {
 381                 token = Atom;
 382                 tokchar = *_c++;
 383         }
 384         else
 385         {
 386                 token = tokchar = *_c++;
 387         }
 388 }
 389
 390 /* N F A  B u i l d i n g  R o u t i n e s */
 391
 392 static
 393 ArcPtr
 394 newGraphArc()
 395 {
 396         ArcPtr p;
 397         p = (ArcPtr) calloc(1, sizeof(Arc));
 398         if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
 399         if ( freelist != NULL ) p->track = (ArcPtr) freelist;
 400         freelist = (NodePtr) p;
 401         return p;
 402 }
 403
 404 static
 405 NodePtr
 406 newNode()
 407 {
 408         NodePtr p;
 409         p = (NodePtr) calloc(1, sizeof(Node));
 410         if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
 411         if ( freelist != NULL ) p->track = freelist;
 412         freelist = p;
 413         return p;
 414 }
 415
 416 static
 417 ArcBetweenGraphNodes(i, j, label)
 418 NodePtr i, j;
 419 int label;
 420 {
 421         ArcPtr a;
 422
 423         a = newGraphArc();
 424         if ( i->arcs == NULL ) i->arctail = i->arcs = a;
 425         else {(i->arctail)->next = a; i->arctail = a;}
 426         a->label = label;
 427         a->target = j;
 428 }
 429
 430 static Graph
 431 BuildNFA_atom(label)
 432 int label;
 433 {
 434         Graph g;
 435
 436         g.left = newNode();
 437         g.right = newNode();
 438         ArcBetweenGraphNodes(g.left, g.right, label);
 439         return( g );
 440 }
 441
 442 static Graph
 443 BuildNFA_AB(A, B)
 444 Graph A, B;
 445 {
 446         Graph g;
 447
 448         ArcBetweenGraphNodes(A.right, B.left, Epsilon);
 449         g.left = A.left;
 450         g.right = B.right;
 451         return( g );
 452 }
 453
 454 static Graph
 455 BuildNFA_AorB(A, B)
 456 Graph A, B;
 457 {
 458         Graph g;
 459
 460         g.left = newNode();
 461         ArcBetweenGraphNodes(g.left, A.left, Epsilon);
 462         ArcBetweenGraphNodes(g.left, B.left, Epsilon);
 463         g.right = newNode();
 464         ArcBetweenGraphNodes(A.right, g.right, Epsilon);
 465         ArcBetweenGraphNodes(B.right, g.right, Epsilon);
 466         return( g );
 467 }
 468
 469 static Graph
 470 BuildNFA_set( s )
 471 char *s;
 472 {
 473         Graph g;
 474
 475         if ( s == NULL ) return g;
 476
 477         g.left = newNode();
 478         g.right = newNode();
 479         while ( *s != '\0' )
 480         {
 481                 ArcBetweenGraphNodes(g.left, g.right, *s++);
 482         }
 483         return g;
 484 }
 485
 486 static Graph
 487 BuildNFA_Astar( A )
 488 Graph A;
 489 {
 490         Graph g;
 491
 492         g.left = newNode();
 493         g.right = newNode();
 494
 495         ArcBetweenGraphNodes(g.left, A.left, Epsilon);
 496         ArcBetweenGraphNodes(g.left, g.right, Epsilon);
 497         ArcBetweenGraphNodes(A.right, g.right, Epsilon);
 498         ArcBetweenGraphNodes(A.right, A.left, Epsilon);
 499
 500         return( g );
 501 }
 502
 503 static Graph
 504 BuildNFA_Aplus( A )
 505 Graph A;
 506 {
 507         ArcBetweenGraphNodes(A.right, A.left, Epsilon);
 508
 509         return( A );
 510 }
 511
 512 static Graph
 513 BuildNFA_Aoptional( A )
 514 Graph A;
 515 {
 516         Graph g;
 517
 518         g.left = newNode();
 519         g.right = newNode();
 520
 521         ArcBetweenGraphNodes(g.left, A.left, Epsilon);
 522         ArcBetweenGraphNodes(g.left, g.right, Epsilon);
 523         ArcBetweenGraphNodes(A.right, g.right, Epsilon);
 524
 525         return( g );
 526 }