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