dfa/dfa.c

   1 /*
   2  * Copyright (C) 1994-1998, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: dfa.c,v $
   7  * Revision 1.22  1998-06-24 12:16:10  adam
   8  * Support for relations on text operands. Open range support in
   9  * DFA module (i.e. [-j], [g-]).
  10  *
  11  * Revision 1.21  1998/06/22 11:33:39  adam
  12  * Added two type casts.
  13  *
  14  * Revision 1.20  1998/06/08 14:40:44  adam
  15  * Fixed problem with signed character(s) in regular expressions.
  16  *
  17  * Revision 1.19  1998/01/12 14:39:39  adam
  18  * Fixed bug in term_Tnode.
  19  *
  20  * Revision 1.18  1997/09/29 09:05:17  adam
  21  * Thread safe DFA module. We simply had to put a few static vars to
  22  * the DFA_parse structure.
  23  *
  24  * Revision 1.17  1997/09/18 08:59:17  adam
  25  * Extra generic handle for the character mapping routines.
  26  *
  27  * Revision 1.16  1997/09/05 15:29:57  adam
  28  * Changed prototype for chr_map_input - added const.
  29  * Added support for C++, headers uses extern "C" for public definitions.
  30  *
  31  * Revision 1.15  1997/02/10 10:19:20  adam
  32  * Added facility for open character sets, eg [a-].
  33  *
  34  * Revision 1.14  1996/10/29 13:57:22  adam
  35  * Include of zebrautl.h instead of alexutil.h.
  36  *
  37  * Revision 1.13  1996/06/17 14:24:08  adam
  38  * Bug fix: read_charset didn't handle character mapping.
  39  *
  40  * Revision 1.12  1996/06/04 10:20:02  adam
  41  * Added support for character mapping.
  42  *
  43  * Revision 1.11  1996/01/08  19:15:24  adam
  44  * Allow single $ in expressions.
  45  *
  46  * Revision 1.10  1996/01/08  09:09:17  adam
  47  * Function dfa_parse got 'const' string argument.
  48  * New functions to define char mappings made public.
  49  *
  50  * Revision 1.9  1995/12/06  12:24:58  adam
  51  * Removed verbatim mode code.
  52  *
  53  * Revision 1.8  1995/12/06  09:09:58  adam
  54  * Work on left and right anchors.
  55  *
  56  * Revision 1.7  1995/11/27  09:23:02  adam
  57  * New berbatim hook in regular expressions. "[]n ..".
  58  *
  59  * Revision 1.6  1995/10/16  09:31:25  adam
  60  * Bug fix.
  61  *
  62  * Revision 1.5  1995/10/02  15:17:58  adam
  63  * Bug fix in dfa_delete.
  64  *
  65  * Revision 1.4  1995/09/28  09:18:52  adam
  66  * Removed various preprocessor defines.
  67  *
  68  * Revision 1.3  1995/09/04  12:33:26  adam
  69  * Various cleanup. YAZ util used instead.
  70  *
  71  * Revision 1.2  1995/01/25  11:30:50  adam
  72  * Simple error reporting when parsing regular expressions.
  73  * Memory usage reduced.
  74  *
  75  * Revision 1.1  1995/01/24  16:02:52  adam
  76  * New private header file in dfa module (dfap.h).
  77  * Module no longer uses yacc to parse regular expressions.
  78  *
  79  */
  80 #include <stdio.h>
  81 #include <assert.h>
  82
  83 #include <stdlib.h>
  84 #include <string.h>
  85 #include <ctype.h>
  86
  87 #include <zebrautl.h>
  88 #include "dfap.h"
  89 #include "imalloc.h"
  90
  91 #define DFA_OPEN_RANGE 1
  92
  93 #define CAT     16000
  94 #define OR      16001
  95 #define STAR    16002
  96 #define PLUS    16003
  97 #define EPSILON 16004
  98
  99 struct Tnode {
 100     union  {
 101         struct Tnode *p[2];   /* CAT,OR,STAR,PLUS (left,right) */
 102         short ch[2];          /* if ch[0] >= 0 then this Tnode represents */
 103                               /*   a character in range [ch[0]..ch[1]]    */
 104                               /* otherwise ch[0] represents */
 105                               /*   accepting no (-acceptno) */
 106     } u;
 107     unsigned pos : 15;        /* CAT/OR/STAR/EPSILON or non-neg. position */
 108     unsigned nullable : 1;
 109     Set firstpos;             /* first positions */
 110     Set lastpos;              /* last positions */
 111 };
 112
 113 struct Tblock {               /* Tnode bucket (block) */
 114     struct Tblock *next;      /* pointer to next bucket */
 115     struct Tnode *tarray;     /* array of nodes in bucket */
 116 };
 117
 118 #define TADD 64
 119 #define STATE_HASH 199
 120 #define POSET_CHUNK 100
 121
 122 int debug_dfa_trav  = 0;
 123 int debug_dfa_tran  = 0;
 124 int debug_dfa_followpos = 0;
 125 int dfa_verbose = 0;
 126
 127 static struct Tnode *mk_Tnode      (struct DFA_parse *parse_info);
 128 static struct Tnode *mk_Tnode_cset (struct DFA_parse *parse_info,
 129                                     BSet charset);
 130 static void        term_Tnode      (struct DFA_parse *parse_info);
 131
 132 static void
 133     del_followpos  (struct DFA_parse *parse_info),
 134     init_pos       (struct DFA_parse *parse_info),
 135     del_pos        (struct DFA_parse *parse_info),
 136     mk_dfa_tran    (struct DFA_parse *parse_info, struct DFA_states *dfas),
 137     add_follow     (struct DFA_parse *parse_info, Set lastpos, Set firstpos),
 138     dfa_trav       (struct DFA_parse *parse_info, struct Tnode *n),
 139     init_followpos (struct DFA_parse *parse_info),
 140     pr_tran        (struct DFA_parse *parse_info, struct DFA_states *dfas),
 141     pr_verbose     (struct DFA_parse *parse_info, struct DFA_states *dfas),
 142     pr_followpos   (struct DFA_parse *parse_info),
 143     out_char       (int c),
 144     lex            (struct DFA_parse *parse_info);
 145
 146 static int
 147     nextchar       (struct DFA_parse *parse_info, int *esc),
 148     read_charset   (struct DFA_parse *parse_info);
 149
 150 static const char
 151     *str_char      (unsigned c);
 152
 153 #define L_LP 1
 154 #define L_RP 2
 155 #define L_CHAR 3
 156 #define L_CHARS 4
 157 #define L_ANY 5
 158 #define L_ALT 6
 159 #define L_ANYZ 7
 160 #define L_WILD 8
 161 #define L_QUEST 9
 162 #define L_CLOS1 10
 163 #define L_CLOS0 11
 164 #define L_END 12
 165 #define L_START 13
 166
 167
 168 static struct Tnode *expr_1 (struct DFA_parse *parse_info),
 169                     *expr_2 (struct DFA_parse *parse_info),
 170                     *expr_3 (struct DFA_parse *parse_info),
 171                     *expr_4 (struct DFA_parse *parse_info);
 172
 173 static struct Tnode *expr_1 (struct DFA_parse *parse_info)
 174 {
 175     struct Tnode *t1, *t2, *tn;
 176
 177     if (!(t1 = expr_2 (parse_info)))
 178         return t1;
 179     while (parse_info->lookahead == L_ALT)
 180     {
 181         lex (parse_info);
 182         if (!(t2 = expr_2 (parse_info)))
 183             return t2;
 184
 185         tn = mk_Tnode (parse_info);
 186         tn->pos = OR;
 187         tn->u.p[0] = t1;
 188         tn->u.p[1] = t2;
 189         t1 = tn;
 190     }
 191     return t1;
 192 }
 193
 194 static struct Tnode *expr_2 (struct DFA_parse *parse_info)
 195 {
 196     struct Tnode *t1, *t2, *tn;
 197
 198     if (!(t1 = expr_3 (parse_info)))
 199         return t1;
 200     while (parse_info->lookahead == L_WILD ||
 201            parse_info->lookahead == L_ANYZ ||
 202            parse_info->lookahead == L_ANY ||
 203            parse_info->lookahead == L_LP ||
 204            parse_info->lookahead == L_CHAR ||
 205            parse_info->lookahead == L_CHARS)
 206     {
 207         if (!(t2 = expr_3 (parse_info)))
 208             return t2;
 209
 210         tn = mk_Tnode (parse_info);
 211         tn->pos = CAT;
 212         tn->u.p[0] = t1;
 213         tn->u.p[1] = t2;
 214         t1 = tn;
 215     }
 216     return t1;
 217 }
 218
 219 static struct Tnode *expr_3 (struct DFA_parse *parse_info)
 220 {
 221     struct Tnode *t1, *tn;
 222
 223     if (!(t1 = expr_4 (parse_info)))
 224         return t1;
 225     if (parse_info->lookahead == L_CLOS0)
 226     {
 227         lex (parse_info);
 228         tn = mk_Tnode (parse_info);
 229         tn->pos = STAR;
 230         tn->u.p[0] = t1;
 231         t1 = tn;
 232     }
 233     else if (parse_info->lookahead == L_CLOS1)
 234     {
 235         lex (parse_info);
 236         tn = mk_Tnode (parse_info);
 237         tn->pos = PLUS;
 238         tn->u.p[0] = t1;
 239         t1 = tn;
 240     }
 241     else if (parse_info->lookahead == L_QUEST)
 242     {
 243         lex (parse_info);
 244         tn = mk_Tnode(parse_info);
 245         tn->pos = OR;
 246         tn->u.p[0] = t1;
 247         tn->u.p[1] = mk_Tnode(parse_info);
 248         tn->u.p[1]->pos = EPSILON;
 249         t1 = tn;
 250     }
 251     return t1;
 252 }
 253
 254 static struct Tnode *expr_4 (struct DFA_parse *parse_info)
 255 {
 256     struct Tnode *t1;
 257
 258     switch (parse_info->lookahead)
 259     {
 260     case L_LP:
 261         lex (parse_info);
 262         if (!(t1 = expr_1 (parse_info)))
 263             return t1;
 264         if (parse_info->lookahead == L_RP)
 265             lex (parse_info);
 266         else
 267             return NULL;
 268         break;
 269     case L_CHAR:
 270         t1 = mk_Tnode(parse_info);
 271         t1->pos = ++parse_info->position;
 272         t1->u.ch[1] = t1->u.ch[0] = parse_info->look_ch;
 273         lex (parse_info);
 274         break;
 275     case L_CHARS:
 276         t1 = mk_Tnode_cset (parse_info, parse_info->look_chars);
 277         lex (parse_info);
 278         break;
 279     case L_ANY:
 280         t1 = mk_Tnode_cset (parse_info, parse_info->anyset);
 281         lex (parse_info);
 282         break;
 283     case L_ANYZ:
 284         t1 = mk_Tnode(parse_info);
 285         t1->pos = OR;
 286         t1->u.p[0] = mk_Tnode_cset (parse_info, parse_info->anyset);
 287         t1->u.p[1] = mk_Tnode(parse_info);
 288         t1->u.p[1]->pos = EPSILON;
 289         lex (parse_info);
 290         break;
 291     case L_WILD:
 292         t1 = mk_Tnode(parse_info);
 293         t1->pos = STAR;
 294         t1->u.p[0] = mk_Tnode_cset (parse_info, parse_info->anyset);
 295         lex (parse_info);
 296     default:
 297         t1 = NULL;
 298     }
 299     return t1;
 300 }
 301
 302 static void do_parse (struct DFA_parse *parse_info, const char **s,
 303                       struct Tnode **tnp)
 304 {
 305     int start_anchor_flag = 0;
 306     struct Tnode *t1, *t2, *tn;
 307
 308     parse_info->err_code = 0;
 309     parse_info->expr_ptr =  * (const unsigned char **) s;
 310
 311     parse_info->inside_string = 0;
 312     lex (parse_info);
 313     if (parse_info->lookahead == L_START)
 314     {
 315         start_anchor_flag = 1;
 316         lex (parse_info);
 317     }
 318     if (parse_info->lookahead == L_END)
 319     {
 320         t1 = mk_Tnode (parse_info);
 321         t1->pos = ++parse_info->position;
 322         t1->u.ch[1] = t1->u.ch[0] = '\n';
 323         lex (parse_info);
 324     }
 325     else
 326     {
 327         t1 = expr_1 (parse_info);
 328         if (t1 && parse_info->lookahead == L_END)
 329         {
 330             t2 = mk_Tnode (parse_info);
 331             t2->pos = ++parse_info->position;
 332             t2->u.ch[1] = t2->u.ch[0] = '\n';
 333
 334             tn = mk_Tnode (parse_info);
 335             tn->pos = CAT;
 336             tn->u.p[0] = t1;
 337             tn->u.p[1] = t2;
 338             t1 = tn;
 339
 340             lex (parse_info);
 341         }
 342     }
 343     if (t1 && parse_info->lookahead == 0)
 344     {
 345         t2 = mk_Tnode(parse_info);
 346         t2->pos = ++parse_info->position;
 347         t2->u.ch[0] = -(++parse_info->rule);
 348         t2->u.ch[1] = start_anchor_flag ? 0 : -(parse_info->rule);
 349
 350         *tnp = mk_Tnode(parse_info);
 351         (*tnp)->pos = CAT;
 352         (*tnp)->u.p[0] = t1;
 353         (*tnp)->u.p[1] = t2;
 354     }
 355     else
 356     {
 357         if (!parse_info->err_code)
 358         {
 359             if (parse_info->lookahead == L_RP)
 360                 parse_info->err_code = DFA_ERR_RP;
 361             else if (parse_info->lookahead == L_LP)
 362                 parse_info->err_code = DFA_ERR_LP;
 363             else
 364                 parse_info->err_code = DFA_ERR_SYNTAX;
 365         }
 366     }
 367     *s = (const char *) parse_info->expr_ptr;
 368 }
 369
 370 static int nextchar (struct DFA_parse *parse_info, int *esc)
 371 {
 372     *esc = 0;
 373     if (*parse_info->expr_ptr == '\0')
 374         return 0;
 375     else if (*parse_info->expr_ptr != '\\')
 376         return *parse_info->expr_ptr++;
 377     *esc = 1;
 378     switch (*++parse_info->expr_ptr)
 379     {
 380     case '\r':
 381     case '\n':
 382     case '\0':
 383         return '\\';
 384     case '\t':
 385         ++parse_info->expr_ptr;
 386         return ' ';
 387     case 'n':
 388         ++parse_info->expr_ptr;
 389         return '\n';
 390     case 't':
 391         ++parse_info->expr_ptr;
 392         return '\t';
 393     case 'r':
 394         ++parse_info->expr_ptr;
 395         return '\r';
 396     case 'f':
 397         ++parse_info->expr_ptr;
 398         return '\f';
 399     default:
 400         return *parse_info->expr_ptr++;
 401     }
 402 }
 403
 404 static int nextchar_set (struct DFA_parse *parse_info, int *esc)
 405 {
 406     if (*parse_info->expr_ptr == ' ')
 407     {
 408         *esc = 0;
 409         return *parse_info->expr_ptr++;
 410     }
 411     return nextchar (parse_info, esc);
 412 }
 413
 414 static int read_charset (struct DFA_parse *parse_info)
 415 {
 416     int i, ch0, ch1, esc0, esc1, cc = 0;
 417     parse_info->look_chars = mk_BSet (&parse_info->charset);
 418     res_BSet (parse_info->charset, parse_info->look_chars);
 419
 420     ch0 = nextchar_set (parse_info, &esc0);
 421     if (!esc0 && ch0 == '^')
 422     {
 423         cc = 1;
 424         ch0 = nextchar_set (parse_info, &esc0);
 425     }
 426     while (ch0 != 0)
 427     {
 428         if (!esc0 && ch0 == ']')
 429             break;
 430         if (!esc0 && ch0 == '-')
 431         {
 432             ch1 = ch0;
 433             esc1 = esc0;
 434             ch0 = 1;
 435             add_BSet (parse_info->charset, parse_info->look_chars, ch0);
 436         }
 437         else
 438         {
 439             if (parse_info->cmap)
 440             {
 441                 const char **mapto;
 442                 char mapfrom[2];
 443                 const char *mcp = mapfrom;
 444                 mapfrom[0] = ch0;
 445                 mapto = (*parse_info->cmap)(parse_info->cmap_data, &mcp, 1);
 446                 assert (mapto);
 447                 ch0 = mapto[0][0];
 448             }
 449             add_BSet (parse_info->charset, parse_info->look_chars, ch0);
 450             ch1 = nextchar_set (parse_info, &esc1);
 451         }
 452         if (!esc1 && ch1 == '-')
 453         {
 454             int open_range = 0;
 455             if ((ch1 = nextchar_set (parse_info, &esc1)) == 0)
 456                 break;
 457 #if DFA_OPEN_RANGE
 458             if (!esc1 && ch1 == ']')
 459             {
 460                 ch1 = 255;
 461                 open_range = 1;
 462             }
 463 #else
 464             if (!esc1 && ch1 == ']')
 465             {
 466                 add_BSet (parse_info->charset, parse_info->look_chars, '-');
 467                 break;
 468             }
 469 #endif
 470             if (!open_range && parse_info->cmap)
 471             {
 472                 const char **mapto;
 473                 char mapfrom[2];
 474                 const char *mcp = mapfrom;
 475                 mapfrom[0] = ch1;
 476                 mapto = (*parse_info->cmap) (parse_info->cmap_data, &mcp, 1);
 477                 assert (mapto);
 478                 ch1 = mapto[0][0];
 479             }
 480             for (i=ch0; ++i<=ch1;)
 481                 add_BSet (parse_info->charset, parse_info->look_chars, i);
 482             if (!open_range)
 483                 ch0 = nextchar_set (parse_info, &esc0);
 484             else
 485                 break;
 486         }
 487         else
 488         {
 489             esc0 = esc1;
 490             ch0 = ch1;
 491         }
 492     }
 493     if (cc)
 494         com_BSet (parse_info->charset, parse_info->look_chars);
 495     return L_CHARS;
 496 }
 497
 498 static int map_l_char (struct DFA_parse *parse_info)
 499 {
 500     const char **mapto;
 501     const char *cp0 = (const char *) (parse_info->expr_ptr-1);
 502     int i = 0, len = strlen(cp0);
 503
 504     if (cp0[0] == 1 && cp0[1])
 505     {
 506         parse_info->expr_ptr++;
 507         parse_info->look_ch = ((unsigned char *) cp0)[1];
 508         return L_CHAR;
 509     }
 510     if (!parse_info->cmap)
 511         return L_CHAR;
 512
 513     mapto = (*parse_info->cmap) (parse_info->cmap_data, &cp0, len);
 514     assert (mapto);
 515
 516     parse_info->expr_ptr = (const unsigned char *) cp0;
 517     parse_info->look_ch = ((unsigned char **) mapto)[i][0];
 518     logf (LOG_DEBUG, "map from %c to %d", parse_info->expr_ptr[-1], parse_info->look_ch);
 519     return L_CHAR;
 520 }
 521
 522 static int lex_sub(struct DFA_parse *parse_info)
 523 {
 524     int esc;
 525     while ((parse_info->look_ch = nextchar (parse_info, &esc)) != 0)
 526         if (parse_info->look_ch == '\"')
 527         {
 528             if (esc)
 529                 return map_l_char (parse_info);
 530             parse_info->inside_string = !parse_info->inside_string;
 531         }
 532         else if (esc || parse_info->inside_string)
 533             return map_l_char (parse_info);
 534         else if (parse_info->look_ch == '[')
 535             return read_charset(parse_info);
 536         else
 537         {
 538             const int *cc;
 539             for (cc = parse_info->charMap; *cc; cc += 2)
 540                 if (*cc == parse_info->look_ch)
 541                 {
 542                     if (!cc[1])
 543                         --parse_info->expr_ptr;
 544                     return cc[1];
 545                 }
 546             return map_l_char (parse_info);
 547         }
 548     return 0;
 549 }
 550
 551 static void lex (struct DFA_parse *parse_info)
 552 {
 553     parse_info->lookahead = lex_sub (parse_info);
 554 }
 555
 556 static const char *str_char (unsigned c)
 557 {
 558     static char s[6];
 559     s[0] = '\\';
 560     if (c < 32 || c >= 127)
 561         switch (c)
 562         {
 563         case '\r':
 564             strcpy (s+1, "r");
 565             break;
 566         case '\n':
 567             strcpy (s+1, "n");
 568             break;
 569         case '\t':
 570             strcpy (s+1, "t");
 571             break;
 572         default:
 573             sprintf (s+1, "x%02x", c);
 574             break;
 575         }
 576     else
 577         switch (c)
 578         {
 579         case '\"':
 580             strcpy (s+1, "\"");
 581             break;
 582         case '\'':
 583             strcpy (s+1, "\'");
 584             break;
 585         case '\\':
 586             strcpy (s+1, "\\");
 587             break;
 588         default:
 589             s[0] = c;
 590             s[1] = '\0';
 591         }
 592     return s;
 593 }
 594
 595 static void out_char (int c)
 596 {
 597     printf ("%s", str_char (c));
 598 }
 599
 600 static void term_Tnode (struct DFA_parse *parse_info)
 601 {
 602     struct Tblock *t, *t1;
 603     for (t = parse_info->start; (t1 = t);)
 604     {
 605         t=t->next;
 606         ifree (t1->tarray);
 607         ifree (t1);
 608     }
 609 }
 610
 611 static struct Tnode *mk_Tnode (struct DFA_parse *parse_info)
 612 {
 613     struct Tblock *tnew;
 614
 615     if (parse_info->use_Tnode == parse_info->max_Tnode)
 616     {
 617         tnew = (struct Tblock *) imalloc (sizeof(struct Tblock));
 618         tnew->tarray = (struct Tnode *) imalloc (TADD*sizeof(struct Tnode));
 619         if (!tnew->tarray)
 620             return NULL;
 621         if (parse_info->use_Tnode == 0)
 622             parse_info->start = tnew;
 623         else
 624             parse_info->end->next = tnew;
 625         parse_info->end = tnew;
 626         tnew->next = NULL;
 627         parse_info->max_Tnode += TADD;
 628     }
 629     return parse_info->end->tarray+(parse_info->use_Tnode++ % TADD);
 630 }
 631
 632 struct Tnode *mk_Tnode_cset (struct DFA_parse *parse_info, BSet charset)
 633 {
 634     struct Tnode *tn1, *tn0 = mk_Tnode(parse_info);
 635     int ch1, ch0 = trav_BSet (parse_info->charset, charset, 0);
 636     if (ch0 == -1)
 637         tn0->pos = EPSILON;
 638     else
 639     {
 640         tn0->u.ch[0] = ch0;
 641         tn0->pos = ++parse_info->position;
 642         ch1 = travi_BSet (parse_info->charset, charset, ch0+1) ;
 643         if (ch1 == -1)
 644             tn0->u.ch[1] = parse_info->charset->size;
 645         else
 646         {
 647             tn0->u.ch[1] = ch1-1;
 648             while ((ch0=trav_BSet (parse_info->charset, charset, ch1)) != -1)
 649             {
 650                 tn1 = mk_Tnode(parse_info);
 651                 tn1->pos = OR;
 652                 tn1->u.p[0] = tn0;
 653                 tn0 = tn1;
 654                 tn1 = tn0->u.p[1] = mk_Tnode(parse_info);
 655                 tn1->u.ch[0] = ch0;
 656                 tn1->pos = ++(parse_info->position);
 657                 if ((ch1 = travi_BSet (parse_info->charset, charset,
 658                                        ch0+1)) == -1)
 659                 {
 660                     tn1->u.ch[1] = parse_info->charset->size;
 661                     break;
 662                 }
 663                 tn1->u.ch[1] = ch1-1;
 664             }
 665         }
 666     }
 667     return tn0;
 668 }
 669
 670 static void del_followpos (struct DFA_parse *parse_info)
 671 {
 672     ifree (parse_info->followpos);
 673 }
 674
 675 static void init_pos (struct DFA_parse *parse_info)
 676 {
 677     parse_info->posar = (struct Tnode **) imalloc (sizeof(struct Tnode*)
 678                                        * (1+parse_info->position));
 679 }
 680
 681 static void del_pos (struct DFA_parse *parse_info)
 682 {
 683     ifree (parse_info->posar);
 684 }
 685
 686 static void add_follow (struct DFA_parse *parse_info,
 687                         Set lastpos, Set firstpos)
 688 {
 689     while (lastpos)
 690     {
 691         parse_info->followpos[lastpos->value] =
 692             union_Set (parse_info->poset,
 693                        parse_info->followpos[lastpos->value], firstpos);
 694         lastpos = lastpos->next;
 695     }
 696 }
 697
 698 static void dfa_trav (struct DFA_parse *parse_info, struct Tnode *n)
 699 {
 700     struct Tnode **posar = parse_info->posar;
 701     SetType poset = parse_info->poset;
 702
 703     switch (n->pos)
 704     {
 705     case CAT:
 706         dfa_trav (parse_info, n->u.p[0]);
 707         dfa_trav (parse_info, n->u.p[1]);
 708         n->nullable = n->u.p[0]->nullable & n->u.p[1]->nullable;
 709         n->firstpos = mk_Set (poset);
 710         n->firstpos = union_Set (poset, n->firstpos, n->u.p[0]->firstpos);
 711         if (n->u.p[0]->nullable)
 712             n->firstpos = union_Set (poset, n->firstpos, n->u.p[1]->firstpos);
 713         n->lastpos = mk_Set (poset);
 714         n->lastpos = union_Set (poset, n->lastpos, n->u.p[1]->lastpos);
 715         if (n->u.p[1]->nullable)
 716             n->lastpos = union_Set (poset, n->lastpos, n->u.p[0]->lastpos);
 717
 718         add_follow (parse_info, n->u.p[0]->lastpos, n->u.p[1]->firstpos);
 719
 720         n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
 721         n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
 722         n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
 723         n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
 724         if (debug_dfa_trav)
 725             printf ("CAT");
 726         break;
 727     case OR:
 728         dfa_trav (parse_info, n->u.p[0]);
 729         dfa_trav (parse_info, n->u.p[1]);
 730         n->nullable = n->u.p[0]->nullable | n->u.p[1]->nullable;
 731
 732         n->firstpos = merge_Set (poset, n->u.p[0]->firstpos,
 733                                  n->u.p[1]->firstpos);
 734         n->lastpos = merge_Set (poset, n->u.p[0]->lastpos,
 735                                 n->u.p[1]->lastpos);
 736         n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
 737         n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
 738         n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
 739         n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
 740         if (debug_dfa_trav)
 741             printf ("OR");
 742         break;
 743     case PLUS:
 744         dfa_trav (parse_info, n->u.p[0]);
 745         n->nullable = n->u.p[0]->nullable;
 746         n->firstpos = n->u.p[0]->firstpos;
 747         n->lastpos = n->u.p[0]->lastpos;
 748         add_follow (parse_info, n->lastpos, n->firstpos);
 749         if (debug_dfa_trav)
 750             printf ("PLUS");
 751         break;
 752     case STAR:
 753         dfa_trav (parse_info, n->u.p[0]);
 754         n->nullable = 1;
 755         n->firstpos = n->u.p[0]->firstpos;
 756         n->lastpos = n->u.p[0]->lastpos;
 757         add_follow (parse_info, n->lastpos, n->firstpos);
 758         if (debug_dfa_trav)
 759             printf ("STAR");
 760         break;
 761     case EPSILON:
 762         n->nullable = 1;
 763         n->lastpos = mk_Set (poset);
 764         n->firstpos = mk_Set (poset);
 765         if (debug_dfa_trav)
 766             printf ("EPSILON");
 767         break;
 768     default:
 769         posar[n->pos] = n;
 770         n->nullable = 0;
 771         n->firstpos = mk_Set (poset);
 772         n->firstpos = add_Set (poset, n->firstpos, n->pos);
 773         n->lastpos = mk_Set (poset);
 774         n->lastpos = add_Set (poset, n->lastpos, n->pos);
 775         if (debug_dfa_trav)
 776             if (n->u.ch[0] < 0)
 777                 printf ("#%d (n#%d)", -n->u.ch[0], -n->u.ch[1]);
 778             else if (n->u.ch[1] > n->u.ch[0])
 779             {
 780                 putchar ('[');
 781                 out_char (n->u.ch[0]);
 782                 if (n->u.ch[1] > n->u.ch[0]+1)
 783                     putchar ('-');
 784                 out_char (n->u.ch[1]);
 785                 putchar (']');
 786             }
 787             else
 788                 out_char (n->u.ch[0]);
 789     }
 790     if (debug_dfa_trav)
 791     {
 792         printf ("\n nullable : %c\n", n->nullable ? '1' : '0');
 793         printf (" firstpos :");
 794         pr_Set (poset, n->firstpos);
 795         printf (" lastpos  :");
 796         pr_Set (poset, n->lastpos);
 797     }
 798 }
 799
 800 static void init_followpos (struct DFA_parse *parse_info)
 801 {
 802     Set *fa;
 803     int i;
 804     parse_info->followpos = fa =
 805         (Set *) imalloc (sizeof(Set) * (1+parse_info->position));
 806     for (i = parse_info->position+1; --i >= 0; fa++)
 807         *fa = mk_Set (parse_info->poset);
 808 }
 809
 810 static void mk_dfa_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
 811 {
 812     int i, j, c;
 813     int max_char;
 814     short *pos, *pos_i;
 815     Set tran_set;
 816     int char_0, char_1;
 817     struct DFA_state *dfa_from, *dfa_to;
 818     struct Tnode **posar;
 819     SetType poset;
 820     Set *followpos;
 821
 822     assert (parse_info);
 823
 824     posar = parse_info->posar;
 825     max_char = parse_info->charset->size;
 826     pos = (short *) imalloc (sizeof(*pos) * (parse_info->position+1));
 827
 828     tran_set = cp_Set (parse_info->poset, parse_info->root->firstpos);
 829     i = add_DFA_state (dfas, &tran_set, &dfa_from);
 830     assert (i);
 831     dfa_from->rule_no = 0;
 832     poset = parse_info->poset;
 833     followpos = parse_info->followpos;
 834     while ((dfa_from = get_DFA_state (dfas)))
 835     {
 836         pos_i = pos;
 837         j = i = 0;
 838         for (tran_set = dfa_from->set; tran_set; tran_set = tran_set->next)
 839             if ((c = posar[tran_set->value]->u.ch[0]) >= 0 && c <= max_char)
 840                 *pos_i++ = tran_set->value;
 841             else if (c < 0)
 842             {
 843                 if (i == 0 || c > i)
 844                     i = c;
 845                 c = posar[tran_set->value]->u.ch[1];
 846                 if (j == 0 || c > j)
 847                     j = c;
 848             }
 849         *pos_i = -1;
 850         dfa_from->rule_no = -i;
 851         dfa_from->rule_nno = -j;
 852
 853         for (char_1 = 0; char_1 <= max_char; char_1++)
 854         {
 855             char_0 = max_char+1;
 856             for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
 857                 if (posar[i]->u.ch[1] >= char_1
 858                     && (c=posar[i]->u.ch[0]) < char_0)
 859                     if (c < char_1)
 860                         char_0 = char_1;
 861                     else
 862                         char_0 = c;
 863
 864             if (char_0 > max_char)
 865                 break;
 866
 867             char_1 = max_char;
 868
 869             tran_set = mk_Set (poset);
 870             for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
 871             {
 872                 if ((c=posar[i]->u.ch[0]) > char_0 && c <= char_1)
 873                     char_1 = c - 1;                /* forward chunk */
 874                 else if ((c=posar[i]->u.ch[1]) >= char_0 && c < char_1)
 875                     char_1 = c;                    /* backward chunk */
 876                 if (posar[i]->u.ch[1] >= char_0 && posar[i]->u.ch[0] <= char_0)
 877                     tran_set = union_Set (poset, tran_set, followpos[i]);
 878             }
 879             if (tran_set)
 880             {
 881                 add_DFA_state (dfas, &tran_set, &dfa_to);
 882                 add_DFA_tran (dfas, dfa_from, char_0, char_1, dfa_to->no);
 883             }
 884         }
 885     }
 886     ifree (pos);
 887     sort_DFA_states (dfas);
 888 }
 889
 890 static void pr_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
 891 {
 892     struct DFA_state *s;
 893     struct DFA_tran *tran;
 894     int prev_no, i, c, no;
 895
 896     for (no=0; no < dfas->no; ++no)
 897     {
 898         s = dfas->sortarray[no];
 899         assert (s->no == no);
 900         printf ("DFA state %d", no);
 901         if (s->rule_no)
 902             printf ("#%d", s->rule_no);
 903         if (s->rule_nno)
 904             printf (" #%d", s->rule_nno);
 905
 906         putchar (':');
 907         pr_Set (parse_info->poset, s->set);
 908         prev_no = -1;
 909         for (i=s->tran_no, tran=s->trans; --i >= 0; tran++)
 910         {
 911             if (prev_no != tran->to)
 912             {
 913                 if (prev_no != -1)
 914                     printf ("]\n");
 915                 printf (" goto %d on [", tran->to);
 916                 prev_no = tran->to;
 917             }
 918             for (c = tran->ch[0]; c <= tran->ch[1]; c++)
 919                 printf ("%s", str_char(c));
 920         }
 921         if (prev_no != -1)
 922             printf ("]\n");
 923         putchar ('\n');
 924     }
 925 }
 926
 927 static void pr_verbose (struct DFA_parse *parse_info, struct DFA_states *dfas)
 928 {
 929     long i, j;
 930     int k;
 931     printf ("%d/%d tree nodes used, %d bytes each\n",
 932         parse_info->use_Tnode, parse_info->max_Tnode, sizeof (struct Tnode));
 933     k = inf_BSetHandle (parse_info->charset, &i, &j);
 934     printf ("%ld/%ld character sets, %d bytes each\n",
 935             i/k, j/k, k*sizeof(BSetWord));
 936     k = inf_SetType (parse_info->poset, &i, &j);
 937     printf ("%ld/%ld poset items, %d bytes each\n", i, j, k);
 938     printf ("%d DFA states\n", dfas->no);
 939 }
 940
 941 static void pr_followpos (struct DFA_parse *parse_info)
 942 {
 943     struct Tnode **posar = parse_info->posar;
 944     int i;
 945     printf ("\nfollowsets:\n");
 946     for (i=1; i <= parse_info->position; i++)
 947     {
 948         printf ("%3d:", i);
 949         pr_Set (parse_info->poset, parse_info->followpos[i]);
 950         putchar ('\t');
 951
 952         if (posar[i]->u.ch[0] < 0)
 953             printf ("#%d", -posar[i]->u.ch[0]);
 954         else if (posar[i]->u.ch[1] > posar[i]->u.ch[0])
 955         {
 956             putchar ('[');
 957             out_char (posar[i]->u.ch[0]);
 958             if (posar[i]->u.ch[1] > posar[i]->u.ch[0]+1)
 959                 putchar ('-');
 960             out_char (posar[i]->u.ch[1]);
 961             putchar (']');
 962         }
 963         else
 964             out_char (posar[i]->u.ch[0]);
 965         putchar ('\n');
 966     }
 967     putchar ('\n');
 968 }
 969
 970 void dfa_parse_cmap_clean (struct DFA *d)
 971 {
 972     struct DFA_parse *dfa = d->parse_info;
 973
 974     assert (dfa);
 975     if (!dfa->charMap)
 976     {
 977         dfa->charMapSize = 7;
 978         dfa->charMap = imalloc (dfa->charMapSize * sizeof(*dfa->charMap));
 979     }
 980     dfa->charMap[0] = 0;
 981 }
 982
 983 void dfa_parse_cmap_new (struct DFA *d, const int *cmap)
 984 {
 985     struct DFA_parse *dfa = d->parse_info;
 986     const int *cp;
 987     int size;
 988
 989     assert (dfa);
 990     for (cp = cmap; *cp; cp += 2)
 991         ;
 992     size = cp - cmap + 1;
 993     if (size > dfa->charMapSize)
 994     {
 995         if (dfa->charMap)
 996             ifree (dfa->charMap);
 997         dfa->charMapSize = size;
 998         dfa->charMap = imalloc (size * sizeof(*dfa->charMap));
 999     }
1000     memcpy (dfa->charMap, cmap, size * sizeof(*dfa->charMap));
1001 }
1002
1003 void dfa_parse_cmap_del (struct DFA *d, int from)
1004 {
1005     struct DFA_parse *dfa = d->parse_info;
1006     int *cc;
1007
1008     assert (dfa);
1009     for (cc = dfa->charMap; *cc; cc += 2)
1010         if (*cc == from)
1011         {
1012             while ((cc[0] = cc[2]))
1013             {
1014                 cc[1] = cc[3];
1015                 cc += 2;
1016             }
1017             break;
1018         }
1019 }
1020
1021 void dfa_parse_cmap_add (struct DFA *d, int from, int to)
1022 {
1023     struct DFA_parse *dfa = d->parse_info;
1024     int *cc;
1025     int indx, size;
1026
1027     assert (dfa);
1028     for (cc = dfa->charMap; *cc; cc += 2)
1029         if (*cc == from)
1030         {
1031             cc[1] = to;
1032             return ;
1033         }
1034     indx = cc - dfa->charMap;
1035     size = dfa->charMapSize;
1036     if (indx >= size)
1037     {
1038         int *cn = imalloc ((size+16) * sizeof(*dfa->charMap));
1039         memcpy (cn, dfa->charMap, indx*sizeof(*dfa->charMap));
1040         ifree (dfa->charMap);
1041         dfa->charMap = cn;
1042         dfa->charMapSize = size+16;
1043     }
1044     dfa->charMap[indx] = from;
1045     dfa->charMap[indx+1] = to;
1046     dfa->charMap[indx+2] = 0;
1047 }
1048
1049 void dfa_parse_cmap_thompson (struct DFA *d)
1050 {
1051     static int thompson_chars[] =
1052     {
1053         '*',  L_CLOS0,
1054         '+',  L_CLOS1,
1055         '|',  L_ALT,
1056         '^',  L_START,
1057         '$',  L_END,
1058         '?',  L_QUEST,
1059         '.',  L_ANY,
1060         '(',  L_LP,
1061         ')',  L_RP,
1062         ' ',  0,
1063         '\t', 0,
1064         '\n', 0,
1065         0
1066     };
1067     dfa_parse_cmap_new (d, thompson_chars);
1068 }
1069
1070 static struct DFA_parse *dfa_parse_init (void)
1071 {
1072     struct DFA_parse *parse_info =
1073         (struct DFA_parse *) imalloc (sizeof (struct DFA_parse));
1074
1075     parse_info->charset = mk_BSetHandle (255, 20);
1076     parse_info->position = 0;
1077     parse_info->rule = 0;
1078     parse_info->root = NULL;
1079
1080     parse_info->anyset = mk_BSet (&parse_info->charset);
1081     res_BSet (parse_info->charset, parse_info->anyset);
1082     add_BSet (parse_info->charset, parse_info->anyset, '\n');
1083     com_BSet (parse_info->charset, parse_info->anyset);
1084     parse_info->use_Tnode = parse_info->max_Tnode = 0;
1085     parse_info->start = parse_info->end = NULL;
1086     parse_info->charMap = NULL;
1087     parse_info->charMapSize = 0;
1088     parse_info->cmap = NULL;
1089     return parse_info;
1090 }
1091
1092 static void rm_dfa_parse (struct DFA_parse **dfap)
1093 {
1094     struct DFA_parse *parse_info = *dfap;
1095     assert (parse_info);
1096     term_Tnode(parse_info);
1097     rm_BSetHandle (&parse_info->charset);
1098     ifree (parse_info->charMap);
1099     ifree (parse_info);
1100     *dfap = NULL;
1101 }
1102
1103 static struct DFA_states *mk_dfas (struct DFA_parse *dfap, int poset_chunk)
1104 {
1105     struct DFA_states *dfas;
1106     struct DFA_parse *parse_info = dfap;
1107
1108     assert (poset_chunk > 10);
1109     assert (dfap);
1110
1111     parse_info->poset = mk_SetType (poset_chunk);
1112     init_pos(parse_info);
1113     init_followpos(parse_info);
1114     assert (parse_info->root);
1115     dfa_trav (parse_info, parse_info->root);
1116
1117     if (debug_dfa_followpos)
1118         pr_followpos(parse_info);
1119     init_DFA_states (&dfas, parse_info->poset, STATE_HASH);
1120     mk_dfa_tran (parse_info, dfas);
1121     if (debug_dfa_tran)
1122         pr_tran (parse_info, dfas);
1123     if (dfa_verbose)
1124         pr_verbose (parse_info, dfas);
1125     del_pos(parse_info);
1126     del_followpos(parse_info);
1127     rm_SetType (parse_info->poset);
1128     return dfas;
1129 }
1130
1131 struct DFA *dfa_init (void)
1132 {
1133     struct DFA *dfa;
1134
1135     dfa = imalloc (sizeof(*dfa));
1136     dfa->parse_info = dfa_parse_init ();
1137     dfa->state_info = NULL;
1138     dfa->states = NULL;
1139     dfa_parse_cmap_thompson (dfa);
1140     return dfa;
1141 }
1142
1143 void dfa_set_cmap (struct DFA *dfa, void *vp,
1144                    const char **(*cmap)(void *vp, const char **from, int len))
1145 {
1146     dfa->parse_info->cmap = cmap;
1147     dfa->parse_info->cmap_data = vp;
1148 }
1149
1150 int dfa_parse (struct DFA *dfa, const char **pattern)
1151 {
1152     struct Tnode *top;
1153     struct DFA_parse *parse_info;
1154
1155     assert (dfa);
1156     assert (dfa->parse_info);
1157     parse_info = dfa->parse_info;
1158     do_parse (parse_info, pattern, &top);
1159     if (parse_info->err_code)
1160         return parse_info->err_code;
1161     if ( !dfa->parse_info->root )
1162         dfa->parse_info->root = top;
1163     else
1164     {
1165         struct Tnode *n;
1166
1167         n = mk_Tnode (parse_info);
1168         n->pos = OR;
1169         n->u.p[0] = dfa->parse_info->root;
1170         n->u.p[1] = top;
1171         dfa->parse_info->root = n;
1172     }
1173     return 0;
1174 }
1175
1176 void dfa_mkstate (struct DFA *dfa)
1177 {
1178     assert (dfa);
1179
1180     dfa->state_info = mk_dfas (dfa->parse_info, POSET_CHUNK);
1181     dfa->no_states = dfa->state_info->no;
1182     dfa->states = dfa->state_info->sortarray;
1183     rm_dfa_parse (&dfa->parse_info);
1184 }
1185
1186 void dfa_delete (struct DFA **dfap)
1187 {
1188     assert (dfap);
1189     assert (*dfap);
1190     if ((*dfap)->parse_info)
1191         rm_dfa_parse (&(*dfap)->parse_info);
1192     if ((*dfap)->state_info)
1193         rm_DFA_states (&(*dfap)->state_info);
1194     ifree (*dfap);
1195     *dfap = NULL;
1196 }