dfa/dfa.c

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