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