dfa/dfa.c

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