开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 编译器/解释器 > 查看源码
rexpr.c
资源名称：pccts133.zip　[点击查看]
上传用户：itx_2006
上传日期：2007-01-06
资源大小：493k
文件大小：10k
源码类别：

编译器/解释器

开发平台：

Others

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.  */
  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"
  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
  109. static char *_c;
  110. static int token, tokchar;
  111. static NodePtr accept;
  112. static NodePtr freelist = NULL;
  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;
  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. }
  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;
  149. if ( automaton == accept && *s == '' ) return 1; /* match */
  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. }
  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;
  176. if ( andExpr(&g1) == -1 )
  177. {
  178. return -1;
  179. }
  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. }
  191. if ( token!='' ) return -1;
  193. *g = g1;
  194. return 1;
  195. }
  197. /*
  198.  * <andExpr>        ::= <expr> ( <expr> )*
  199.  */
  200. static
  201. andExpr(g)
  202. GraphPtr g;
  203. {
  204. Graph g1, g2;
  206. if ( expr(&g1) == -1 )
  207. {
  208. return -1;
  209. }
  211. while ( token==Atom || token=='{' || token=='(' || token=='~' || token=='[' )
  212. {
  213. if (expr(&g2) == -1) return -1;
  214. g1 = BuildNFA_AB(g1, g2);
  215. }
  217. *g = g1;
  218. return 1;
  219. }
  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 [] */
  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. }
  277. return -1;
  278. }
  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. }
  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;
  311. if ( token != Atom ) return -1;
  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 = '';
  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 = '';
  342. }
  343. return 1;
  344. }
  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. }
  390. /* N F A  B u i l d i n g  R o u t i n e s */
  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 memoryn"); exit(-1);}
  399. if ( freelist != NULL ) p->track = (ArcPtr) freelist;
  400. freelist = (NodePtr) p;
  401. return p;
  402. }
  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 memoryn"); exit(-1);}
  411. if ( freelist != NULL ) p->track = freelist;
  412. freelist = p;
  413. return p;
  414. }
  416. static
  417. ArcBetweenGraphNodes(i, j, label)
  418. NodePtr i, j;
  419. int label;
  420. {
  421. ArcPtr a;
  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. }
  430. static Graph
  431. BuildNFA_atom(label)
  432. int label;
  433. {
  434. Graph g;
  436. g.left = newNode();
  437. g.right = newNode();
  438. ArcBetweenGraphNodes(g.left, g.right, label);
  439. return( g );
  440. }
  442. static Graph
  443. BuildNFA_AB(A, B)
  444. Graph A, B;
  445. {
  446. Graph g;
  448. ArcBetweenGraphNodes(A.right, B.left, Epsilon);
  449. g.left = A.left;
  450. g.right = B.right;
  451. return( g );
  452. }
  454. static Graph
  455. BuildNFA_AorB(A, B)
  456. Graph A, B;
  457. {
  458. Graph g;
  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. }
  469. static Graph
  470. BuildNFA_set( s )
  471. char *s;
  472. {
  473. Graph g;
  475. if ( s == NULL ) return g;
  477. g.left = newNode();
  478. g.right = newNode();
  479. while ( *s != '' )
  480. {
  481. ArcBetweenGraphNodes(g.left, g.right, *s++);
  482. }
  483. return g;
  484. }
  486. static Graph
  487. BuildNFA_Astar( A )
  488. Graph A;
  489. {
  490. Graph g;
  492. g.left = newNode();
  493. g.right = newNode();
  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);
  500. return( g );
  501. }
  503. static Graph
  504. BuildNFA_Aplus( A )
  505. Graph A;
  506. {
  507. ArcBetweenGraphNodes(A.right, A.left, Epsilon);
  509. return( A );
  510. }
  512. static Graph
  513. BuildNFA_Aoptional( A )
  514. Graph A;
  515. {
  516. Graph g;
  518. g.left = newNode();
  519. g.right = newNode();
  521. ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  522. ArcBetweenGraphNodes(g.left, g.right, Epsilon);
  523. ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  525. return( g );
  526. }