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