2 * Copyright (C) 1994-1998, Index Data
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.24 1998-10-28 10:48:55 adam
8 * Added type cast to prevent warning.
10 * Revision 1.23 1998/09/02 14:15:28 adam
11 * Zebra uses GNU Configure.
13 * Revision 1.22 1998/06/24 12:16:10 adam
14 * Support for relations on text operands. Open range support in
15 * DFA module (i.e. [-j], [g-]).
17 * Revision 1.21 1998/06/22 11:33:39 adam
18 * Added two type casts.
20 * Revision 1.20 1998/06/08 14:40:44 adam
21 * Fixed problem with signed character(s) in regular expressions.
23 * Revision 1.19 1998/01/12 14:39:39 adam
24 * Fixed bug in term_Tnode.
26 * Revision 1.18 1997/09/29 09:05:17 adam
27 * Thread safe DFA module. We simply had to put a few static vars to
28 * the DFA_parse structure.
30 * Revision 1.17 1997/09/18 08:59:17 adam
31 * Extra generic handle for the character mapping routines.
33 * Revision 1.16 1997/09/05 15:29:57 adam
34 * Changed prototype for chr_map_input - added const.
35 * Added support for C++, headers uses extern "C" for public definitions.
37 * Revision 1.15 1997/02/10 10:19:20 adam
38 * Added facility for open character sets, eg [a-].
40 * Revision 1.14 1996/10/29 13:57:22 adam
41 * Include of zebrautl.h instead of alexutil.h.
43 * Revision 1.13 1996/06/17 14:24:08 adam
44 * Bug fix: read_charset didn't handle character mapping.
46 * Revision 1.12 1996/06/04 10:20:02 adam
47 * Added support for character mapping.
49 * Revision 1.11 1996/01/08 19:15:24 adam
50 * Allow single $ in expressions.
52 * Revision 1.10 1996/01/08 09:09:17 adam
53 * Function dfa_parse got 'const' string argument.
54 * New functions to define char mappings made public.
56 * Revision 1.9 1995/12/06 12:24:58 adam
57 * Removed verbatim mode code.
59 * Revision 1.8 1995/12/06 09:09:58 adam
60 * Work on left and right anchors.
62 * Revision 1.7 1995/11/27 09:23:02 adam
63 * New berbatim hook in regular expressions. "[]n ..".
65 * Revision 1.6 1995/10/16 09:31:25 adam
68 * Revision 1.5 1995/10/02 15:17:58 adam
69 * Bug fix in dfa_delete.
71 * Revision 1.4 1995/09/28 09:18:52 adam
72 * Removed various preprocessor defines.
74 * Revision 1.3 1995/09/04 12:33:26 adam
75 * Various cleanup. YAZ util used instead.
77 * Revision 1.2 1995/01/25 11:30:50 adam
78 * Simple error reporting when parsing regular expressions.
79 * Memory usage reduced.
81 * Revision 1.1 1995/01/24 16:02:52 adam
82 * New private header file in dfa module (dfap.h).
83 * Module no longer uses yacc to parse regular expressions.
97 #define DFA_OPEN_RANGE 1
103 #define EPSILON 16004
107 struct Tnode *p[2]; /* CAT,OR,STAR,PLUS (left,right) */
108 short ch[2]; /* if ch[0] >= 0 then this Tnode represents */
109 /* a character in range [ch[0]..ch[1]] */
110 /* otherwise ch[0] represents */
111 /* accepting no (-acceptno) */
113 unsigned pos : 15; /* CAT/OR/STAR/EPSILON or non-neg. position */
114 unsigned nullable : 1;
115 Set firstpos; /* first positions */
116 Set lastpos; /* last positions */
119 struct Tblock { /* Tnode bucket (block) */
120 struct Tblock *next; /* pointer to next bucket */
121 struct Tnode *tarray; /* array of nodes in bucket */
125 #define STATE_HASH 199
126 #define POSET_CHUNK 100
128 int debug_dfa_trav = 0;
129 int debug_dfa_tran = 0;
130 int debug_dfa_followpos = 0;
133 static struct Tnode *mk_Tnode (struct DFA_parse *parse_info);
134 static struct Tnode *mk_Tnode_cset (struct DFA_parse *parse_info,
136 static void term_Tnode (struct DFA_parse *parse_info);
139 del_followpos (struct DFA_parse *parse_info),
140 init_pos (struct DFA_parse *parse_info),
141 del_pos (struct DFA_parse *parse_info),
142 mk_dfa_tran (struct DFA_parse *parse_info, struct DFA_states *dfas),
143 add_follow (struct DFA_parse *parse_info, Set lastpos, Set firstpos),
144 dfa_trav (struct DFA_parse *parse_info, struct Tnode *n),
145 init_followpos (struct DFA_parse *parse_info),
146 pr_tran (struct DFA_parse *parse_info, struct DFA_states *dfas),
147 pr_verbose (struct DFA_parse *parse_info, struct DFA_states *dfas),
148 pr_followpos (struct DFA_parse *parse_info),
150 lex (struct DFA_parse *parse_info);
153 nextchar (struct DFA_parse *parse_info, int *esc),
154 read_charset (struct DFA_parse *parse_info);
157 *str_char (unsigned c);
174 static struct Tnode *expr_1 (struct DFA_parse *parse_info),
175 *expr_2 (struct DFA_parse *parse_info),
176 *expr_3 (struct DFA_parse *parse_info),
177 *expr_4 (struct DFA_parse *parse_info);
179 static struct Tnode *expr_1 (struct DFA_parse *parse_info)
181 struct Tnode *t1, *t2, *tn;
183 if (!(t1 = expr_2 (parse_info)))
185 while (parse_info->lookahead == L_ALT)
188 if (!(t2 = expr_2 (parse_info)))
191 tn = mk_Tnode (parse_info);
200 static struct Tnode *expr_2 (struct DFA_parse *parse_info)
202 struct Tnode *t1, *t2, *tn;
204 if (!(t1 = expr_3 (parse_info)))
206 while (parse_info->lookahead == L_WILD ||
207 parse_info->lookahead == L_ANYZ ||
208 parse_info->lookahead == L_ANY ||
209 parse_info->lookahead == L_LP ||
210 parse_info->lookahead == L_CHAR ||
211 parse_info->lookahead == L_CHARS)
213 if (!(t2 = expr_3 (parse_info)))
216 tn = mk_Tnode (parse_info);
225 static struct Tnode *expr_3 (struct DFA_parse *parse_info)
227 struct Tnode *t1, *tn;
229 if (!(t1 = expr_4 (parse_info)))
231 if (parse_info->lookahead == L_CLOS0)
234 tn = mk_Tnode (parse_info);
239 else if (parse_info->lookahead == L_CLOS1)
242 tn = mk_Tnode (parse_info);
247 else if (parse_info->lookahead == L_QUEST)
250 tn = mk_Tnode(parse_info);
253 tn->u.p[1] = mk_Tnode(parse_info);
254 tn->u.p[1]->pos = EPSILON;
260 static struct Tnode *expr_4 (struct DFA_parse *parse_info)
264 switch (parse_info->lookahead)
268 if (!(t1 = expr_1 (parse_info)))
270 if (parse_info->lookahead == L_RP)
276 t1 = mk_Tnode(parse_info);
277 t1->pos = ++parse_info->position;
278 t1->u.ch[1] = t1->u.ch[0] = parse_info->look_ch;
282 t1 = mk_Tnode_cset (parse_info, parse_info->look_chars);
286 t1 = mk_Tnode_cset (parse_info, parse_info->anyset);
290 t1 = mk_Tnode(parse_info);
292 t1->u.p[0] = mk_Tnode_cset (parse_info, parse_info->anyset);
293 t1->u.p[1] = mk_Tnode(parse_info);
294 t1->u.p[1]->pos = EPSILON;
298 t1 = mk_Tnode(parse_info);
300 t1->u.p[0] = mk_Tnode_cset (parse_info, parse_info->anyset);
308 static void do_parse (struct DFA_parse *parse_info, const char **s,
311 int start_anchor_flag = 0;
312 struct Tnode *t1, *t2, *tn;
314 parse_info->err_code = 0;
315 parse_info->expr_ptr = * (const unsigned char **) s;
317 parse_info->inside_string = 0;
319 if (parse_info->lookahead == L_START)
321 start_anchor_flag = 1;
324 if (parse_info->lookahead == L_END)
326 t1 = mk_Tnode (parse_info);
327 t1->pos = ++parse_info->position;
328 t1->u.ch[1] = t1->u.ch[0] = '\n';
333 t1 = expr_1 (parse_info);
334 if (t1 && parse_info->lookahead == L_END)
336 t2 = mk_Tnode (parse_info);
337 t2->pos = ++parse_info->position;
338 t2->u.ch[1] = t2->u.ch[0] = '\n';
340 tn = mk_Tnode (parse_info);
349 if (t1 && parse_info->lookahead == 0)
351 t2 = mk_Tnode(parse_info);
352 t2->pos = ++parse_info->position;
353 t2->u.ch[0] = -(++parse_info->rule);
354 t2->u.ch[1] = start_anchor_flag ? 0 : -(parse_info->rule);
356 *tnp = mk_Tnode(parse_info);
363 if (!parse_info->err_code)
365 if (parse_info->lookahead == L_RP)
366 parse_info->err_code = DFA_ERR_RP;
367 else if (parse_info->lookahead == L_LP)
368 parse_info->err_code = DFA_ERR_LP;
370 parse_info->err_code = DFA_ERR_SYNTAX;
373 *s = (const char *) parse_info->expr_ptr;
376 static int nextchar (struct DFA_parse *parse_info, int *esc)
379 if (*parse_info->expr_ptr == '\0')
381 else if (*parse_info->expr_ptr != '\\')
382 return *parse_info->expr_ptr++;
384 switch (*++parse_info->expr_ptr)
391 ++parse_info->expr_ptr;
394 ++parse_info->expr_ptr;
397 ++parse_info->expr_ptr;
400 ++parse_info->expr_ptr;
403 ++parse_info->expr_ptr;
406 return *parse_info->expr_ptr++;
410 static int nextchar_set (struct DFA_parse *parse_info, int *esc)
412 if (*parse_info->expr_ptr == ' ')
415 return *parse_info->expr_ptr++;
417 return nextchar (parse_info, esc);
420 static int read_charset (struct DFA_parse *parse_info)
422 int i, ch0, ch1, esc0, esc1, cc = 0;
423 parse_info->look_chars = mk_BSet (&parse_info->charset);
424 res_BSet (parse_info->charset, parse_info->look_chars);
426 ch0 = nextchar_set (parse_info, &esc0);
427 if (!esc0 && ch0 == '^')
430 ch0 = nextchar_set (parse_info, &esc0);
434 if (!esc0 && ch0 == ']')
436 if (!esc0 && ch0 == '-')
441 add_BSet (parse_info->charset, parse_info->look_chars, ch0);
445 if (parse_info->cmap)
449 const char *mcp = mapfrom;
451 mapto = (*parse_info->cmap)(parse_info->cmap_data, &mcp, 1);
455 add_BSet (parse_info->charset, parse_info->look_chars, ch0);
456 ch1 = nextchar_set (parse_info, &esc1);
458 if (!esc1 && ch1 == '-')
461 if ((ch1 = nextchar_set (parse_info, &esc1)) == 0)
464 if (!esc1 && ch1 == ']')
470 if (!esc1 && ch1 == ']')
472 add_BSet (parse_info->charset, parse_info->look_chars, '-');
476 if (!open_range && parse_info->cmap)
480 const char *mcp = mapfrom;
482 mapto = (*parse_info->cmap) (parse_info->cmap_data, &mcp, 1);
486 for (i=ch0; ++i<=ch1;)
487 add_BSet (parse_info->charset, parse_info->look_chars, i);
489 ch0 = nextchar_set (parse_info, &esc0);
500 com_BSet (parse_info->charset, parse_info->look_chars);
504 static int map_l_char (struct DFA_parse *parse_info)
507 const char *cp0 = (const char *) (parse_info->expr_ptr-1);
508 int i = 0, len = strlen(cp0);
510 if (cp0[0] == 1 && cp0[1])
512 parse_info->expr_ptr++;
513 parse_info->look_ch = ((unsigned char *) cp0)[1];
516 if (!parse_info->cmap)
519 mapto = (*parse_info->cmap) (parse_info->cmap_data, &cp0, len);
522 parse_info->expr_ptr = (const unsigned char *) cp0;
523 parse_info->look_ch = ((unsigned char **) mapto)[i][0];
524 logf (LOG_DEBUG, "map from %c to %d", parse_info->expr_ptr[-1], parse_info->look_ch);
528 static int lex_sub(struct DFA_parse *parse_info)
531 while ((parse_info->look_ch = nextchar (parse_info, &esc)) != 0)
532 if (parse_info->look_ch == '\"')
535 return map_l_char (parse_info);
536 parse_info->inside_string = !parse_info->inside_string;
538 else if (esc || parse_info->inside_string)
539 return map_l_char (parse_info);
540 else if (parse_info->look_ch == '[')
541 return read_charset(parse_info);
545 for (cc = parse_info->charMap; *cc; cc += 2)
546 if (*cc == (int) (parse_info->look_ch))
549 --parse_info->expr_ptr;
552 return map_l_char (parse_info);
557 static void lex (struct DFA_parse *parse_info)
559 parse_info->lookahead = lex_sub (parse_info);
562 static const char *str_char (unsigned c)
566 if (c < 32 || c >= 127)
579 sprintf (s+1, "x%02x", c);
601 static void out_char (int c)
603 printf ("%s", str_char (c));
606 static void term_Tnode (struct DFA_parse *parse_info)
608 struct Tblock *t, *t1;
609 for (t = parse_info->start; (t1 = t);)
617 static struct Tnode *mk_Tnode (struct DFA_parse *parse_info)
621 if (parse_info->use_Tnode == parse_info->max_Tnode)
623 tnew = (struct Tblock *) imalloc (sizeof(struct Tblock));
624 tnew->tarray = (struct Tnode *) imalloc (TADD*sizeof(struct Tnode));
627 if (parse_info->use_Tnode == 0)
628 parse_info->start = tnew;
630 parse_info->end->next = tnew;
631 parse_info->end = tnew;
633 parse_info->max_Tnode += TADD;
635 return parse_info->end->tarray+(parse_info->use_Tnode++ % TADD);
638 struct Tnode *mk_Tnode_cset (struct DFA_parse *parse_info, BSet charset)
640 struct Tnode *tn1, *tn0 = mk_Tnode(parse_info);
641 int ch1, ch0 = trav_BSet (parse_info->charset, charset, 0);
647 tn0->pos = ++parse_info->position;
648 ch1 = travi_BSet (parse_info->charset, charset, ch0+1) ;
650 tn0->u.ch[1] = parse_info->charset->size;
653 tn0->u.ch[1] = ch1-1;
654 while ((ch0=trav_BSet (parse_info->charset, charset, ch1)) != -1)
656 tn1 = mk_Tnode(parse_info);
660 tn1 = tn0->u.p[1] = mk_Tnode(parse_info);
662 tn1->pos = ++(parse_info->position);
663 if ((ch1 = travi_BSet (parse_info->charset, charset,
666 tn1->u.ch[1] = parse_info->charset->size;
669 tn1->u.ch[1] = ch1-1;
676 static void del_followpos (struct DFA_parse *parse_info)
678 ifree (parse_info->followpos);
681 static void init_pos (struct DFA_parse *parse_info)
683 parse_info->posar = (struct Tnode **) imalloc (sizeof(struct Tnode*)
684 * (1+parse_info->position));
687 static void del_pos (struct DFA_parse *parse_info)
689 ifree (parse_info->posar);
692 static void add_follow (struct DFA_parse *parse_info,
693 Set lastpos, Set firstpos)
697 parse_info->followpos[lastpos->value] =
698 union_Set (parse_info->poset,
699 parse_info->followpos[lastpos->value], firstpos);
700 lastpos = lastpos->next;
704 static void dfa_trav (struct DFA_parse *parse_info, struct Tnode *n)
706 struct Tnode **posar = parse_info->posar;
707 SetType poset = parse_info->poset;
712 dfa_trav (parse_info, n->u.p[0]);
713 dfa_trav (parse_info, n->u.p[1]);
714 n->nullable = n->u.p[0]->nullable & n->u.p[1]->nullable;
715 n->firstpos = mk_Set (poset);
716 n->firstpos = union_Set (poset, n->firstpos, n->u.p[0]->firstpos);
717 if (n->u.p[0]->nullable)
718 n->firstpos = union_Set (poset, n->firstpos, n->u.p[1]->firstpos);
719 n->lastpos = mk_Set (poset);
720 n->lastpos = union_Set (poset, n->lastpos, n->u.p[1]->lastpos);
721 if (n->u.p[1]->nullable)
722 n->lastpos = union_Set (poset, n->lastpos, n->u.p[0]->lastpos);
724 add_follow (parse_info, n->u.p[0]->lastpos, n->u.p[1]->firstpos);
726 n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
727 n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
728 n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
729 n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
734 dfa_trav (parse_info, n->u.p[0]);
735 dfa_trav (parse_info, n->u.p[1]);
736 n->nullable = n->u.p[0]->nullable | n->u.p[1]->nullable;
738 n->firstpos = merge_Set (poset, n->u.p[0]->firstpos,
739 n->u.p[1]->firstpos);
740 n->lastpos = merge_Set (poset, n->u.p[0]->lastpos,
742 n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
743 n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
744 n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
745 n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
750 dfa_trav (parse_info, n->u.p[0]);
751 n->nullable = n->u.p[0]->nullable;
752 n->firstpos = n->u.p[0]->firstpos;
753 n->lastpos = n->u.p[0]->lastpos;
754 add_follow (parse_info, n->lastpos, n->firstpos);
759 dfa_trav (parse_info, n->u.p[0]);
761 n->firstpos = n->u.p[0]->firstpos;
762 n->lastpos = n->u.p[0]->lastpos;
763 add_follow (parse_info, n->lastpos, n->firstpos);
769 n->lastpos = mk_Set (poset);
770 n->firstpos = mk_Set (poset);
777 n->firstpos = mk_Set (poset);
778 n->firstpos = add_Set (poset, n->firstpos, n->pos);
779 n->lastpos = mk_Set (poset);
780 n->lastpos = add_Set (poset, n->lastpos, n->pos);
784 printf ("#%d (n#%d)", -n->u.ch[0], -n->u.ch[1]);
785 else if (n->u.ch[1] > n->u.ch[0])
788 out_char (n->u.ch[0]);
789 if (n->u.ch[1] > n->u.ch[0]+1)
791 out_char (n->u.ch[1]);
795 out_char (n->u.ch[0]);
800 printf ("\n nullable : %c\n", n->nullable ? '1' : '0');
801 printf (" firstpos :");
802 pr_Set (poset, n->firstpos);
803 printf (" lastpos :");
804 pr_Set (poset, n->lastpos);
808 static void init_followpos (struct DFA_parse *parse_info)
812 parse_info->followpos = fa =
813 (Set *) imalloc (sizeof(Set) * (1+parse_info->position));
814 for (i = parse_info->position+1; --i >= 0; fa++)
815 *fa = mk_Set (parse_info->poset);
818 static void mk_dfa_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
825 struct DFA_state *dfa_from, *dfa_to;
826 struct Tnode **posar;
832 posar = parse_info->posar;
833 max_char = parse_info->charset->size;
834 pos = (short *) imalloc (sizeof(*pos) * (parse_info->position+1));
836 tran_set = cp_Set (parse_info->poset, parse_info->root->firstpos);
837 i = add_DFA_state (dfas, &tran_set, &dfa_from);
839 dfa_from->rule_no = 0;
840 poset = parse_info->poset;
841 followpos = parse_info->followpos;
842 while ((dfa_from = get_DFA_state (dfas)))
846 for (tran_set = dfa_from->set; tran_set; tran_set = tran_set->next)
847 if ((c = posar[tran_set->value]->u.ch[0]) >= 0 && c <= max_char)
848 *pos_i++ = tran_set->value;
853 c = posar[tran_set->value]->u.ch[1];
858 dfa_from->rule_no = -i;
859 dfa_from->rule_nno = -j;
861 for (char_1 = 0; char_1 <= max_char; char_1++)
864 for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
865 if (posar[i]->u.ch[1] >= char_1
866 && (c=posar[i]->u.ch[0]) < char_0)
874 if (char_0 > max_char)
879 tran_set = mk_Set (poset);
880 for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
882 if ((c=posar[i]->u.ch[0]) > char_0 && c <= char_1)
883 char_1 = c - 1; /* forward chunk */
884 else if ((c=posar[i]->u.ch[1]) >= char_0 && c < char_1)
885 char_1 = c; /* backward chunk */
886 if (posar[i]->u.ch[1] >= char_0 && posar[i]->u.ch[0] <= char_0)
887 tran_set = union_Set (poset, tran_set, followpos[i]);
891 add_DFA_state (dfas, &tran_set, &dfa_to);
892 add_DFA_tran (dfas, dfa_from, char_0, char_1, dfa_to->no);
897 sort_DFA_states (dfas);
900 static void pr_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
903 struct DFA_tran *tran;
904 int prev_no, i, c, no;
906 for (no=0; no < dfas->no; ++no)
908 s = dfas->sortarray[no];
909 assert (s->no == no);
910 printf ("DFA state %d", no);
912 printf ("#%d", s->rule_no);
914 printf (" #%d", s->rule_nno);
917 pr_Set (parse_info->poset, s->set);
919 for (i=s->tran_no, tran=s->trans; --i >= 0; tran++)
921 if (prev_no != tran->to)
925 printf (" goto %d on [", tran->to);
928 for (c = tran->ch[0]; c <= tran->ch[1]; c++)
929 printf ("%s", str_char(c));
937 static void pr_verbose (struct DFA_parse *parse_info, struct DFA_states *dfas)
941 printf ("%d/%d tree nodes used, %d bytes each\n",
942 parse_info->use_Tnode, parse_info->max_Tnode, sizeof (struct Tnode));
943 k = inf_BSetHandle (parse_info->charset, &i, &j);
944 printf ("%ld/%ld character sets, %d bytes each\n",
945 i/k, j/k, k*sizeof(BSetWord));
946 k = inf_SetType (parse_info->poset, &i, &j);
947 printf ("%ld/%ld poset items, %d bytes each\n", i, j, k);
948 printf ("%d DFA states\n", dfas->no);
951 static void pr_followpos (struct DFA_parse *parse_info)
953 struct Tnode **posar = parse_info->posar;
955 printf ("\nfollowsets:\n");
956 for (i=1; i <= parse_info->position; i++)
959 pr_Set (parse_info->poset, parse_info->followpos[i]);
962 if (posar[i]->u.ch[0] < 0)
963 printf ("#%d", -posar[i]->u.ch[0]);
964 else if (posar[i]->u.ch[1] > posar[i]->u.ch[0])
967 out_char (posar[i]->u.ch[0]);
968 if (posar[i]->u.ch[1] > posar[i]->u.ch[0]+1)
970 out_char (posar[i]->u.ch[1]);
974 out_char (posar[i]->u.ch[0]);
980 void dfa_parse_cmap_clean (struct DFA *d)
982 struct DFA_parse *dfa = d->parse_info;
987 dfa->charMapSize = 7;
988 dfa->charMap = imalloc (dfa->charMapSize * sizeof(*dfa->charMap));
993 void dfa_parse_cmap_new (struct DFA *d, const int *cmap)
995 struct DFA_parse *dfa = d->parse_info;
1000 for (cp = cmap; *cp; cp += 2)
1002 size = cp - cmap + 1;
1003 if (size > dfa->charMapSize)
1006 ifree (dfa->charMap);
1007 dfa->charMapSize = size;
1008 dfa->charMap = imalloc (size * sizeof(*dfa->charMap));
1010 memcpy (dfa->charMap, cmap, size * sizeof(*dfa->charMap));
1013 void dfa_parse_cmap_del (struct DFA *d, int from)
1015 struct DFA_parse *dfa = d->parse_info;
1019 for (cc = dfa->charMap; *cc; cc += 2)
1022 while ((cc[0] = cc[2]))
1031 void dfa_parse_cmap_add (struct DFA *d, int from, int to)
1033 struct DFA_parse *dfa = d->parse_info;
1038 for (cc = dfa->charMap; *cc; cc += 2)
1044 indx = cc - dfa->charMap;
1045 size = dfa->charMapSize;
1048 int *cn = imalloc ((size+16) * sizeof(*dfa->charMap));
1049 memcpy (cn, dfa->charMap, indx*sizeof(*dfa->charMap));
1050 ifree (dfa->charMap);
1052 dfa->charMapSize = size+16;
1054 dfa->charMap[indx] = from;
1055 dfa->charMap[indx+1] = to;
1056 dfa->charMap[indx+2] = 0;
1059 void dfa_parse_cmap_thompson (struct DFA *d)
1061 static int thompson_chars[] =
1077 dfa_parse_cmap_new (d, thompson_chars);
1080 static struct DFA_parse *dfa_parse_init (void)
1082 struct DFA_parse *parse_info =
1083 (struct DFA_parse *) imalloc (sizeof (struct DFA_parse));
1085 parse_info->charset = mk_BSetHandle (255, 20);
1086 parse_info->position = 0;
1087 parse_info->rule = 0;
1088 parse_info->root = NULL;
1090 parse_info->anyset = mk_BSet (&parse_info->charset);
1091 res_BSet (parse_info->charset, parse_info->anyset);
1092 add_BSet (parse_info->charset, parse_info->anyset, '\n');
1093 com_BSet (parse_info->charset, parse_info->anyset);
1094 parse_info->use_Tnode = parse_info->max_Tnode = 0;
1095 parse_info->start = parse_info->end = NULL;
1096 parse_info->charMap = NULL;
1097 parse_info->charMapSize = 0;
1098 parse_info->cmap = NULL;
1102 static void rm_dfa_parse (struct DFA_parse **dfap)
1104 struct DFA_parse *parse_info = *dfap;
1105 assert (parse_info);
1106 term_Tnode(parse_info);
1107 rm_BSetHandle (&parse_info->charset);
1108 ifree (parse_info->charMap);
1113 static struct DFA_states *mk_dfas (struct DFA_parse *dfap, int poset_chunk)
1115 struct DFA_states *dfas;
1116 struct DFA_parse *parse_info = dfap;
1118 assert (poset_chunk > 10);
1121 parse_info->poset = mk_SetType (poset_chunk);
1122 init_pos(parse_info);
1123 init_followpos(parse_info);
1124 assert (parse_info->root);
1125 dfa_trav (parse_info, parse_info->root);
1127 if (debug_dfa_followpos)
1128 pr_followpos(parse_info);
1129 init_DFA_states (&dfas, parse_info->poset, STATE_HASH);
1130 mk_dfa_tran (parse_info, dfas);
1132 pr_tran (parse_info, dfas);
1134 pr_verbose (parse_info, dfas);
1135 del_pos(parse_info);
1136 del_followpos(parse_info);
1137 rm_SetType (parse_info->poset);
1141 struct DFA *dfa_init (void)
1145 dfa = imalloc (sizeof(*dfa));
1146 dfa->parse_info = dfa_parse_init ();
1147 dfa->state_info = NULL;
1149 dfa_parse_cmap_thompson (dfa);
1153 void dfa_set_cmap (struct DFA *dfa, void *vp,
1154 const char **(*cmap)(void *vp, const char **from, int len))
1156 dfa->parse_info->cmap = cmap;
1157 dfa->parse_info->cmap_data = vp;
1160 int dfa_parse (struct DFA *dfa, const char **pattern)
1163 struct DFA_parse *parse_info;
1166 assert (dfa->parse_info);
1167 parse_info = dfa->parse_info;
1168 do_parse (parse_info, pattern, &top);
1169 if (parse_info->err_code)
1170 return parse_info->err_code;
1171 if ( !dfa->parse_info->root )
1172 dfa->parse_info->root = top;
1177 n = mk_Tnode (parse_info);
1179 n->u.p[0] = dfa->parse_info->root;
1181 dfa->parse_info->root = n;
1186 void dfa_mkstate (struct DFA *dfa)
1190 dfa->state_info = mk_dfas (dfa->parse_info, POSET_CHUNK);
1191 dfa->no_states = dfa->state_info->no;
1192 dfa->states = dfa->state_info->sortarray;
1193 rm_dfa_parse (&dfa->parse_info);
1196 void dfa_delete (struct DFA **dfap)
1200 if ((*dfap)->parse_info)
1201 rm_dfa_parse (&(*dfap)->parse_info);
1202 if ((*dfap)->state_info)
1203 rm_DFA_states (&(*dfap)->state_info);