home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / pccts1.zip / SUPPORT / REXPR / REXPR.C < prev    next >
C/C++ Source or Header  |  1993-09-01  |  10KB  |  515 lines
  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.  
  67. #define Atom    256        /* token Atom (an impossible char value) */
  68. #define Epsilon    257        /* epsilon arc (an impossible char value) */
  69.  
  70. /* track field must be same for all node types */
  71. typedef struct _a {
  72.                     struct _a *track;    /* track mem allocation */
  73.                     int label;
  74.                     struct _a *next;
  75.                     struct _n *target;
  76.                 } Arc, *ArcPtr;
  77.  
  78. typedef struct _n {
  79.                     struct _n *track;
  80.                     ArcPtr arcs, arctail;
  81.                 } Node, *NodePtr;
  82.  
  83. typedef struct    {
  84.                     NodePtr left,
  85.                              right;
  86.                 } Graph, *GraphPtr;
  87.  
  88. static char *_c;
  89. static int token, tokchar;
  90. static NodePtr accept;
  91. static NodePtr freelist = NULL;
  92.  
  93. Graph    BuildNFA_Aoptional(),
  94.         BuildNFA_Aplus(),
  95.         BuildNFA_Astar(),
  96.         BuildNFA_set(),
  97.         BuildNFA_AorB(),
  98.         BuildNFA_AB(),
  99.         BuildNFA_atom();
  100. char    *calloc();
  101.  
  102. /*
  103.  * return 1 if s in language described by expr
  104.  *        0 if s is not
  105.  *       -1 if expr is an invalid regular expression
  106.  */
  107. rexpr(expr, s)
  108. char *expr, *s;
  109. {
  110.     NodePtr p,q;
  111.     Graph nfa;
  112.     int result;
  113.  
  114.     fprintf(stderr, "rexpr(%s,%s);\n", expr,s);
  115.     freelist = NULL;
  116.     _c = expr;
  117.     next();
  118.     if ( regExpr(&nfa) == -1 ) return -1;
  119.     accept = nfa.right;
  120.     result = match(nfa.left, s);
  121.     /* free all your memory */
  122.     p = q = freelist;
  123.     while ( p!=NULL ) { q = p->track; free(p); p = q; }
  124.     return result;
  125. }
  126.  
  127. /*
  128.  * do a depth-first-search on the NFA looking for a path from start to
  129.  * accept state labelled with the characters of 's'.
  130.  */
  131. match(automaton, s)
  132. NodePtr automaton;
  133. char *s;
  134. {
  135.     ArcPtr p;
  136.     
  137.     if ( automaton == accept && *s == '\0' ) return 1;    /* match */
  138.  
  139.     for (p=automaton->arcs; p!=NULL; p=p->next)            /* try all arcs */
  140.     {
  141.         if ( p->label == Epsilon )
  142.         {
  143.             if ( match(p->target, s) ) return 1;
  144.         }
  145.         else if ( p->label == *s )
  146.                 if ( match(p->target, s+1) ) return 1;
  147.     }
  148.     return 0;
  149. }
  150.  
  151. /*
  152.  * <regExpr>        ::= <andExpr> ( '|' {<andExpr>} )*
  153.  *
  154.  * Return -1 if syntax error
  155.  * Return  0 if none found
  156.  * Return  1 if a regExrp was found
  157.  */
  158. static
  159. regExpr(g)
  160. GraphPtr g;
  161. {
  162.     Graph g1, g2;
  163.     
  164.     if ( andExpr(&g1) == -1 )
  165.     {
  166.         return -1;
  167.     }
  168.     
  169.     while ( token == '|' )
  170.     {
  171.         int a;
  172.         next();
  173.         a = andExpr(&g2);
  174.         if ( a == -1 ) return -1;    /* syntax error below */
  175.         else if ( !a ) return 1;    /* empty alternative */
  176.         g1 = BuildNFA_AorB(g1, g2);
  177.     }
  178.     
  179.     if ( token!='\0' ) return -1;
  180.  
  181.     *g = g1;
  182.     return 1;
  183. }
  184.  
  185. /*
  186.  * <andExpr>        ::= <expr> ( <expr> )*
  187.  */
  188. static
  189. andExpr(g)
  190. GraphPtr g;
  191. {
  192.     Graph g1, g2;
  193.     
  194.     if ( expr(&g1) == -1 )
  195.     {
  196.         return -1;
  197.     }
  198.     
  199.     while ( token==Atom || token=='{' || token=='(' || token=='~' || token=='[' )
  200.     {
  201.         if (expr(&g2) == -1) return -1;
  202.         g1 = BuildNFA_AB(g1, g2);
  203.     }
  204.     
  205.     *g = g1;
  206.     return 1;
  207. }
  208.  
  209. /*
  210.  * <expr>           ::=    {'~'} '[' <atomList> ']' <repeatSymbol>
  211.  *                      | '(' <regExpr> ')' <repeatSymbol>
  212.  *                      | '{' <regExpr> '}' <repeatSymbol>
  213.  *                      | <atom> <repeatSymbol>
  214.  */
  215. static
  216. expr(g)
  217. GraphPtr g;
  218. {
  219.     int complement = 0;
  220.     char s[257];    /* alloc space for string of char in [] */
  221.     
  222.     if ( token == '~' || token == '[' )
  223.     {
  224.         if ( token == '~' ) {complement = 1; next();}
  225.         if ( token != '[' ) return -1;
  226.         next();
  227.         if ( atomList( s, complement ) == -1 ) return -1;
  228.         *g = BuildNFA_set( s );
  229.         if ( token != ']' ) return -1;
  230.         next();
  231.         repeatSymbol( g );
  232.         return 1;
  233.     }
  234.     if ( token == '(' )
  235.     {
  236.         next();
  237.         if ( regExpr( g ) == -1 ) return -1;
  238.         if ( token != ')' ) return -1;
  239.         next();
  240.         repeatSymbol( g );
  241.         return 1;
  242.     }
  243.     if ( token == '{' )
  244.     {
  245.         next();
  246.         if ( regExpr( g ) == -1 ) return -1;
  247.         if ( token != '}' ) return -1;
  248.         next();
  249.         /* S p e c i a l  C a s e   O p t i o n a l  {  } */
  250.         if ( token != '*' && token != '+' )
  251.         {
  252.             *g = BuildNFA_Aoptional( *g );
  253.         }
  254.         repeatSymbol( g );
  255.         return 1;
  256.     }
  257.     if ( token == Atom )
  258.     {
  259.         *g = BuildNFA_atom( tokchar );
  260.         next();
  261.         repeatSymbol( g );
  262.         return 1;
  263.     }
  264.     
  265.     return -1;
  266. }
  267.  
  268. /*
  269.  * <repeatSymbol>   ::= { '*' | '+' }
  270.  */
  271. static
  272. repeatSymbol(g)
  273. GraphPtr g;
  274. {
  275.     switch ( token )
  276.     {
  277.         case '*' : *g = BuildNFA_Astar( *g ); next(); break;
  278.         case '+' : *g = BuildNFA_Aplus( *g ); next(); break;
  279.     }
  280.     return 1;
  281. }
  282.  
  283. /*
  284.  * <atomList>       ::= <atom> { <atom> }*
  285.  *                      { <atomList> } <atom> '-' <atom> { <atomList> }
  286.  *
  287.  * a-b is same as ab
  288.  * q-a is same as q
  289.  */
  290. static
  291. atomList(p, complement)
  292. char *p;
  293. int complement;
  294. {
  295.     static unsigned char set[256];        /* no duplicates */
  296.     int first, last, i;
  297.     char *s = p;
  298.     
  299.     if ( token != Atom ) return -1;
  300.     
  301.     for (i=0; i<256; i++) set[i] = 0;
  302.     while ( token == Atom )
  303.     {
  304.         if ( !set[tokchar] ) *s++ = tokchar;
  305.         set[tokchar] = 1;                /* Add atom to set */
  306.         next();
  307.         if ( token == '-' )             /* have we found '-' */
  308.         {
  309.             first = *(s-1);             /* Get last char */
  310.             next();
  311.             if ( token != Atom ) return -1;
  312.             else
  313.             {
  314.                 last = tokchar;
  315.             }
  316.             for (i = first+1; i <= last; i++)
  317.             {
  318.                 if ( !set[tokchar] ) *s++ = i;
  319.                 set[i] = 1;                /* Add atom to set */
  320.             }
  321.             next();
  322.         }
  323.     }
  324.     *s = '\0';
  325.     if ( complement )
  326.     {
  327.         for (i=0; i<256; i++) set[i] = !set[i];
  328.         for (i=1,s=p; i<256; i++) if ( set[i] ) *s++ = i;
  329.         *s = '\0';
  330.     }
  331.     return 1;
  332. }
  333.  
  334. /* a somewhat stupid lexical analyzer */
  335. static
  336. next()
  337. {
  338.     while ( *_c==' ' || *_c=='\t' || *_c=='\n' ) _c++;
  339.     if ( *_c=='\\' )
  340.     {
  341.         _c++;
  342.         if ( isdigit(*_c) )
  343.         {
  344.             int n=0;
  345.             while ( isdigit(*_c) )
  346.             {
  347.                 n = n*10 + (*_c++ - '0');
  348.             }
  349.             if ( n>255 ) n=255;
  350.             tokchar = n;
  351.         }
  352.         else
  353.         {
  354.             switch (*_c)
  355.             {
  356.                 case 'n' : tokchar = '\n'; break;
  357.                 case 't' : tokchar = '\t'; break;
  358.                 case 'r' : tokchar = '\r'; break;
  359.                 default  : tokchar = *_c;
  360.             }
  361.             _c++;
  362.         }
  363.         token = Atom;
  364.     }
  365.     else if ( isgraph(*_c) && *_c!='[' && *_c!='(' && *_c!='{' &&
  366.               *_c!='-' && *_c!='}' && *_c!=')' && *_c!=']' &&
  367.               *_c!='+' && *_c!='*' && *_c!='~' && *_c!='|' )
  368.     {
  369.         token = Atom;
  370.         tokchar = *_c++;
  371.     }
  372.     else
  373.     {
  374.         token = tokchar = *_c++;
  375.     }
  376. }
  377.  
  378. /* N F A  B u i l d i n g  R o u t i n e s */
  379.  
  380. static
  381. ArcPtr
  382. newGraphArc()
  383. {
  384.     ArcPtr p;
  385.     p = (ArcPtr) calloc(1, sizeof(Arc));
  386.     if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
  387.     if ( freelist != NULL ) p->track = (ArcPtr) freelist;
  388.     freelist = (NodePtr) p;
  389.     return p;
  390. }
  391.  
  392. static
  393. NodePtr
  394. newNode()
  395. {
  396.     NodePtr p;
  397.     p = (NodePtr) calloc(1, sizeof(Node));
  398.     if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
  399.     if ( freelist != NULL ) p->track = freelist;
  400.     freelist = p;
  401.     return p;
  402. }
  403.  
  404. static
  405. ArcBetweenGraphNodes(i, j, label)
  406. NodePtr i, j;
  407. int label;
  408. {
  409.     ArcPtr a;
  410.     
  411.     a = newGraphArc();
  412.     if ( i->arcs == NULL ) i->arctail = i->arcs = a;
  413.     else {(i->arctail)->next = a; i->arctail = a;}
  414.     a->label = label;
  415.     a->target = j;
  416. }
  417.  
  418. static Graph
  419. BuildNFA_atom(label)
  420. int label;
  421. {
  422.     Graph g;
  423.     
  424.     g.left = newNode();
  425.     g.right = newNode();
  426.     ArcBetweenGraphNodes(g.left, g.right, label);
  427.     return( g );
  428. }
  429.  
  430. static Graph
  431. BuildNFA_AB(A, B)
  432. Graph A, B;
  433. {
  434.     Graph g;
  435.     
  436.     ArcBetweenGraphNodes(A.right, B.left, Epsilon);
  437.     g.left = A.left;
  438.     g.right = B.right;
  439.     return( g );
  440. }
  441.  
  442. static Graph
  443. BuildNFA_AorB(A, B)
  444. Graph A, B;
  445. {
  446.     Graph g;
  447.     
  448.     g.left = newNode();
  449.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  450.     ArcBetweenGraphNodes(g.left, B.left, Epsilon);
  451.     g.right = newNode();
  452.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  453.     ArcBetweenGraphNodes(B.right, g.right, Epsilon);
  454.     return( g );
  455. }
  456.  
  457. static Graph
  458. BuildNFA_set( s )
  459. char *s;
  460. {
  461.     Graph g;
  462.     
  463.     if ( s == NULL ) return g;
  464.     
  465.     g.left = newNode();
  466.     g.right = newNode();
  467.     while ( *s != '\0' )
  468.     {
  469.         ArcBetweenGraphNodes(g.left, g.right, *s++);
  470.     }
  471.     return g;
  472. }
  473.  
  474. static Graph
  475. BuildNFA_Astar( A )
  476. Graph A;
  477. {
  478.     Graph g;
  479.  
  480.     g.left = newNode();
  481.     g.right = newNode();
  482.     
  483.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  484.     ArcBetweenGraphNodes(g.left, g.right, Epsilon);
  485.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  486.     ArcBetweenGraphNodes(A.right, A.left, Epsilon);
  487.     
  488.     return( g );
  489. }
  490.  
  491. static Graph
  492. BuildNFA_Aplus( A )
  493. Graph A;
  494. {
  495.     ArcBetweenGraphNodes(A.right, A.left, Epsilon);
  496.     
  497.     return( A );
  498. }
  499.  
  500. static Graph
  501. BuildNFA_Aoptional( A )
  502. Graph A;
  503. {
  504.     Graph g;
  505.     
  506.     g.left = newNode();
  507.     g.right = newNode();
  508.     
  509.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  510.     ArcBetweenGraphNodes(g.left, g.right, Epsilon);
  511.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  512.     
  513.     return( g );
  514. }
  515.