dfa/dfa.c

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