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