2 * Copyright (C) 1994-1996, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.15 1997-02-10 10:19:20 adam
8 * Added facility for open character sets, eg [a-].
10 * Revision 1.14 1996/10/29 13:57:22 adam
11 * Include of zebrautl.h instead of alexutil.h.
13 * Revision 1.13 1996/06/17 14:24:08 adam
14 * Bug fix: read_charset didn't handle character mapping.
16 * Revision 1.12 1996/06/04 10:20:02 adam
17 * Added support for character mapping.
19 * Revision 1.11 1996/01/08 19:15:24 adam
20 * Allow single $ in expressions.
22 * Revision 1.10 1996/01/08 09:09:17 adam
23 * Function dfa_parse got 'const' string argument.
24 * New functions to define char mappings made public.
26 * Revision 1.9 1995/12/06 12:24:58 adam
27 * Removed verbatim mode code.
29 * Revision 1.8 1995/12/06 09:09:58 adam
30 * Work on left and right anchors.
32 * Revision 1.7 1995/11/27 09:23:02 adam
33 * New berbatim hook in regular expressions. "[]n ..".
35 * Revision 1.6 1995/10/16 09:31:25 adam
38 * Revision 1.5 1995/10/02 15:17:58 adam
39 * Bug fix in dfa_delete.
41 * Revision 1.4 1995/09/28 09:18:52 adam
42 * Removed various preprocessor defines.
44 * Revision 1.3 1995/09/04 12:33:26 adam
45 * Various cleanup. YAZ util used instead.
47 * Revision 1.2 1995/01/25 11:30:50 adam
48 * Simple error reporting when parsing regular expressions.
49 * Memory usage reduced.
51 * Revision 1.1 1995/01/24 16:02:52 adam
52 * New private header file in dfa module (dfap.h).
53 * Module no longer uses yacc to parse regular expressions.
67 #define DFA_OPEN_RANGE 1
77 struct Tnode *p[2]; /* CAT,OR,STAR,PLUS (left,right) */
78 short ch[2]; /* if ch[0] >= 0 then this Tnode represents */
79 /* a character in range [ch[0]..ch[1]] */
80 /* otherwise ch[0] represents */
81 /* accepting no (-acceptno) */
83 unsigned pos : 15; /* CAT/OR/STAR/EPSILON or non-neg. position */
84 unsigned nullable : 1;
85 Set firstpos; /* first positions */
86 Set lastpos; /* last positions */
89 struct Tblock { /* Tnode bucket (block) */
90 struct Tblock *next; /* pointer to next bucket */
91 struct Tnode *tarray; /* array of nodes in bucket */
95 #define STATE_HASH 199
96 #define POSET_CHUNK 100
98 int debug_dfa_trav = 0;
99 int debug_dfa_tran = 0;
100 int debug_dfa_followpos = 0;
103 static struct DFA_parse *parse_info = NULL;
106 static int inside_string;
107 static const unsigned char *expr_ptr;
108 static struct Tnode **posar;
110 static SetType poset;
111 static Set *followpos;
113 static struct Tnode *mk_Tnode (void);
114 static struct Tnode *mk_Tnode_cset (BSet charset);
115 static void term_Tnode (void);
118 del_followpos (void),
121 mk_dfa_tran (struct DFA_states *dfas),
122 add_follow (Set lastpos, Set firstpos),
123 dfa_trav (struct Tnode *n),
124 init_followpos (void),
125 pr_tran (struct DFA_states *dfas),
126 pr_verbose (struct DFA_states *dfas),
136 *str_char (unsigned c);
152 static int lookahead;
153 static unsigned look_ch;
154 static BSet look_chars;
156 static struct Tnode *expr_1 (void),
161 static struct Tnode *expr_1 (void)
163 struct Tnode *t1, *t2, *tn;
165 if (!(t1 = expr_2 ()))
167 while (lookahead == L_ALT)
170 if (!(t2 = expr_2 ()))
182 static struct Tnode *expr_2 (void)
184 struct Tnode *t1, *t2, *tn;
186 if (!(t1 = expr_3 ()))
188 while (lookahead == L_WILD ||
189 lookahead == L_ANYZ ||
190 lookahead == L_ANY ||
192 lookahead == L_CHAR ||
193 lookahead == L_CHARS)
195 if (!(t2 = expr_3 ()))
207 static struct Tnode *expr_3 (void)
209 struct Tnode *t1, *tn;
211 if (!(t1 = expr_4 ()))
213 if (lookahead == L_CLOS0)
221 else if (lookahead == L_CLOS1)
229 else if (lookahead == L_QUEST)
235 tn->u.p[1] = mk_Tnode();
236 tn->u.p[1]->pos = EPSILON;
242 static struct Tnode *expr_4 (void)
250 if (!(t1 = expr_1 ()))
252 if (lookahead == L_RP)
259 t1->pos = ++parse_info->position;
260 t1->u.ch[1] = t1->u.ch[0] = look_ch;
264 t1 = mk_Tnode_cset (look_chars);
268 t1 = mk_Tnode_cset (parse_info->anyset);
274 t1->u.p[0] = mk_Tnode_cset (parse_info->anyset);
275 t1->u.p[1] = mk_Tnode();
276 t1->u.p[1]->pos = EPSILON;
282 t1->u.p[0] = mk_Tnode_cset (parse_info->anyset);
290 static void do_parse (struct DFA_parse *dfap, const char **s,
293 int start_anchor_flag = 0;
294 struct Tnode *t1, *t2, *tn;
298 expr_ptr = (const unsigned char *) *s;
302 if (lookahead == L_START)
304 start_anchor_flag = 1;
307 if (lookahead == L_END)
310 t1->pos = ++parse_info->position;
311 t1->u.ch[1] = t1->u.ch[0] = '\n';
317 if (t1 && lookahead == L_END)
320 t2->pos = ++parse_info->position;
321 t2->u.ch[1] = t2->u.ch[0] = '\n';
332 if (t1 && lookahead == 0)
335 t2->pos = ++parse_info->position;
336 t2->u.ch[0] = -(++parse_info->rule);
337 t2->u.ch[1] = start_anchor_flag ? 0 : -(parse_info->rule);
348 if (lookahead == L_RP)
349 err_code = DFA_ERR_RP;
350 else if (lookahead == L_LP)
351 err_code = DFA_ERR_LP;
353 err_code = DFA_ERR_SYNTAX;
356 *s = (const char *) expr_ptr;
359 static int nextchar (int *esc)
362 if (*expr_ptr == '\0')
364 else if (*expr_ptr != '\\')
393 static int nextchar_set (int *esc)
395 if (*expr_ptr == ' ')
400 return nextchar (esc);
403 static int read_charset (void)
405 int i, ch0, ch1, esc0, esc1, cc = 0;
406 look_chars = mk_BSet (&parse_info->charset);
407 res_BSet (parse_info->charset, look_chars);
409 ch0 = nextchar_set (&esc0);
410 if (!esc0 && ch0 == '^')
413 ch0 = nextchar_set (&esc0);
417 if (!esc0 && ch0 == ']')
419 if (parse_info->cmap)
421 char **mapto, mapfrom[2];
422 const char *mcp = mapfrom;
424 mapto = (*parse_info->cmap)(&mcp, 1);
428 add_BSet (parse_info->charset, look_chars, ch0);
429 ch1 = nextchar_set (&esc1);
430 if (!esc1 && ch1 == '-')
433 if ((ch1 = nextchar_set (&esc1)) == 0)
436 if (!esc1 && ch1 == ']')
442 if (!esc1 && ch1 == ']')
444 add_BSet (parse_info->charset, look_chars, '-');
448 if (!open_range && parse_info->cmap)
450 char **mapto, mapfrom[2];
451 const char *mcp = mapfrom;
453 mapto = (*parse_info->cmap) (&mcp, 1);
457 for (i=ch0; ++i<=ch1;)
458 add_BSet (parse_info->charset, look_chars, i);
460 ch0 = nextchar_set (&esc0);
471 com_BSet (parse_info->charset, look_chars);
475 static int map_l_char (void)
478 const char *cp0 = (const char *) (expr_ptr-1);
479 int i = 0, len = strlen(cp0);
481 if (cp0[0] == 1 && cp0[1])
487 if (!parse_info->cmap)
490 mapto = (*parse_info->cmap) (&cp0, len);
493 expr_ptr = (const unsigned char *) cp0;
494 look_ch = mapto[i][0];
495 logf (LOG_DEBUG, "map from %c to %d", expr_ptr[-1], look_ch);
499 static int lex_sub(void)
502 while ((look_ch = nextchar (&esc)) != 0)
506 return map_l_char ();
507 inside_string = !inside_string;
509 else if (esc || inside_string)
510 return map_l_char ();
511 else if (look_ch == '[')
512 return read_charset();
516 for (cc = parse_info->charMap; *cc; cc += 2)
523 return map_l_char ();
528 static void lex (void)
530 lookahead = lex_sub ();
533 static const char *str_char (unsigned c)
550 sprintf (s+1, "x%02x", c);
572 static void out_char (int c)
574 printf ("%s", str_char (c));
577 static void term_Tnode (void)
579 struct Tblock *t, *t1;
580 for (t = parse_info->start; (t1 = t);)
588 static struct Tnode *mk_Tnode (void)
592 if (parse_info->use_Tnode == parse_info->max_Tnode)
594 tnew = (struct Tblock *) imalloc (sizeof(struct Tblock));
595 tnew->tarray = (struct Tnode *) imalloc (TADD*sizeof(struct Tnode));
598 if (parse_info->use_Tnode == 0)
599 parse_info->start = tnew;
601 parse_info->end->next = tnew;
602 parse_info->end = tnew;
604 parse_info->max_Tnode += TADD;
606 return parse_info->end->tarray+(parse_info->use_Tnode++ % TADD);
609 struct Tnode *mk_Tnode_cset (BSet charset)
611 struct Tnode *tn1, *tn0 = mk_Tnode();
612 int ch1, ch0 = trav_BSet (parse_info->charset, charset, 0);
618 tn0->pos = ++parse_info->position;
619 ch1 = travi_BSet (parse_info->charset, charset, ch0+1) ;
621 tn0->u.ch[1] = parse_info->charset->size;
624 tn0->u.ch[1] = ch1-1;
625 while ((ch0=trav_BSet (parse_info->charset, charset, ch1)) != -1)
631 tn1 = tn0->u.p[1] = mk_Tnode();
633 tn1->pos = ++(parse_info->position);
634 if ((ch1 = travi_BSet (parse_info->charset, charset,
637 tn1->u.ch[1] = parse_info->charset->size;
640 tn1->u.ch[1] = ch1-1;
647 static void del_followpos (void)
652 static void init_pos (void)
654 posar = (struct Tnode **) imalloc (sizeof(struct Tnode*)
655 * (1+parse_info->position));
658 static void del_pos (void)
663 static void add_follow (Set lastpos, Set firstpos)
667 followpos[lastpos->value] =
668 union_Set (poset, followpos[lastpos->value], firstpos);
669 lastpos = lastpos->next;
673 static void dfa_trav (struct Tnode *n)
678 dfa_trav (n->u.p[0]);
679 dfa_trav (n->u.p[1]);
680 n->nullable = n->u.p[0]->nullable & n->u.p[1]->nullable;
681 n->firstpos = mk_Set (poset);
682 n->firstpos = union_Set (poset, n->firstpos, n->u.p[0]->firstpos);
683 if (n->u.p[0]->nullable)
684 n->firstpos = union_Set (poset, n->firstpos, n->u.p[1]->firstpos);
685 n->lastpos = mk_Set (poset);
686 n->lastpos = union_Set (poset, n->lastpos, n->u.p[1]->lastpos);
687 if (n->u.p[1]->nullable)
688 n->lastpos = union_Set (poset, n->lastpos, n->u.p[0]->lastpos);
690 add_follow (n->u.p[0]->lastpos, n->u.p[1]->firstpos);
692 n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
693 n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
694 n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
695 n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
700 dfa_trav (n->u.p[0]);
701 dfa_trav (n->u.p[1]);
702 n->nullable = n->u.p[0]->nullable | n->u.p[1]->nullable;
704 n->firstpos = merge_Set (poset, n->u.p[0]->firstpos,
705 n->u.p[1]->firstpos);
706 n->lastpos = merge_Set (poset, n->u.p[0]->lastpos,
708 n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
709 n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
710 n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
711 n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
716 dfa_trav (n->u.p[0]);
717 n->nullable = n->u.p[0]->nullable;
718 n->firstpos = n->u.p[0]->firstpos;
719 n->lastpos = n->u.p[0]->lastpos;
720 add_follow (n->lastpos, n->firstpos);
725 dfa_trav (n->u.p[0]);
727 n->firstpos = n->u.p[0]->firstpos;
728 n->lastpos = n->u.p[0]->lastpos;
729 add_follow (n->lastpos, n->firstpos);
735 n->lastpos = mk_Set (poset);
736 n->firstpos = mk_Set (poset);
743 n->firstpos = mk_Set (poset);
744 n->firstpos = add_Set (poset, n->firstpos, n->pos);
745 n->lastpos = mk_Set (poset);
746 n->lastpos = add_Set (poset, n->lastpos, n->pos);
749 printf ("#%d (n#%d)", -n->u.ch[0], -n->u.ch[1]);
750 else if (n->u.ch[1] > n->u.ch[0])
753 out_char (n->u.ch[0]);
754 if (n->u.ch[1] > n->u.ch[0]+1)
756 out_char (n->u.ch[1]);
760 out_char (n->u.ch[0]);
764 printf ("\n nullable : %c\n", n->nullable ? '1' : '0');
765 printf (" firstpos :");
766 pr_Set (poset, n->firstpos);
767 printf (" lastpos :");
768 pr_Set (poset, n->lastpos);
772 static void init_followpos (void)
776 followpos = fa = (Set *) imalloc (sizeof(Set) * (1+parse_info->position));
777 for (i = parse_info->position+1; --i >= 0; fa++)
778 *fa = mk_Set (poset);
781 static void mk_dfa_tran (struct DFA_states *dfas)
788 struct DFA_state *dfa_from, *dfa_to;
791 max_char = parse_info->charset->size;
792 pos = (short *) imalloc (sizeof(*pos) * (parse_info->position+1));
794 tran_set = cp_Set (poset, parse_info->root->firstpos);
795 i = add_DFA_state (dfas, &tran_set, &dfa_from);
797 dfa_from->rule_no = 0;
798 while ((dfa_from = get_DFA_state (dfas)))
802 for (tran_set = dfa_from->set; tran_set; tran_set = tran_set->next)
803 if ((c = posar[tran_set->value]->u.ch[0]) >= 0 && c <= max_char)
804 *pos_i++ = tran_set->value;
809 c = posar[tran_set->value]->u.ch[1];
814 dfa_from->rule_no = -i;
815 dfa_from->rule_nno = -j;
817 for (char_1 = 0; char_1 <= max_char; char_1++)
820 for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
821 if (posar[i]->u.ch[1] >= char_1
822 && (c=posar[i]->u.ch[0]) < char_0)
828 if (char_0 > max_char)
833 tran_set = mk_Set (poset);
834 for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
836 if ((c=posar[i]->u.ch[0]) > char_0 && c <= char_1)
837 char_1 = c - 1; /* forward chunk */
838 else if ((c=posar[i]->u.ch[1]) >= char_0 && c < char_1)
839 char_1 = c; /* backward chunk */
840 if (posar[i]->u.ch[1] >= char_0 && posar[i]->u.ch[0] <= char_0)
841 tran_set = union_Set (poset, tran_set, followpos[i]);
845 add_DFA_state (dfas, &tran_set, &dfa_to);
846 add_DFA_tran (dfas, dfa_from, char_0, char_1, dfa_to->no);
851 sort_DFA_states (dfas);
854 static void pr_tran (struct DFA_states *dfas)
857 struct DFA_tran *tran;
858 int prev_no, i, c, no;
860 for (no=0; no < dfas->no; ++no)
862 s = dfas->sortarray[no];
863 assert (s->no == no);
864 printf ("DFA state %d", no);
866 printf ("#%d", s->rule_no);
868 printf (" #%d", s->rule_nno);
871 pr_Set (poset, s->set);
873 for (i=s->tran_no, tran=s->trans; --i >= 0; tran++)
875 if (prev_no != tran->to)
879 printf (" goto %d on [", tran->to);
882 for (c = tran->ch[0]; c <= tran->ch[1]; c++)
883 printf ("%s", str_char(c));
891 static void pr_verbose (struct DFA_states *dfas)
895 printf ("%d/%d tree nodes used, %d bytes each\n",
896 parse_info->use_Tnode, parse_info->max_Tnode, sizeof (struct Tnode));
897 k = inf_BSetHandle (parse_info->charset, &i, &j);
898 printf ("%ld/%ld character sets, %d bytes each\n",
899 i/k, j/k, k*sizeof(BSetWord));
900 k = inf_SetType (poset, &i, &j);
901 printf ("%ld/%ld poset items, %d bytes each\n", i, j, k);
902 printf ("%d DFA states\n", dfas->no);
905 static void pr_followpos (void)
908 printf ("\nfollowsets:\n");
909 for (i=1; i <= parse_info->position; i++)
912 pr_Set (poset, followpos[i]);
915 if (posar[i]->u.ch[0] < 0)
916 printf ("#%d", -posar[i]->u.ch[0]);
917 else if (posar[i]->u.ch[1] > posar[i]->u.ch[0])
920 out_char (posar[i]->u.ch[0]);
921 if (posar[i]->u.ch[1] > posar[i]->u.ch[0]+1)
923 out_char (posar[i]->u.ch[1]);
927 out_char (posar[i]->u.ch[0]);
933 void dfa_parse_cmap_clean (struct DFA *d)
935 struct DFA_parse *dfa = d->parse_info;
940 dfa->charMapSize = 7;
941 dfa->charMap = imalloc (dfa->charMapSize * sizeof(*dfa->charMap));
946 void dfa_parse_cmap_new (struct DFA *d, const int *cmap)
948 struct DFA_parse *dfa = d->parse_info;
953 for (cp = cmap; *cp; cp += 2)
955 size = cp - cmap + 1;
956 if (size > dfa->charMapSize)
959 ifree (dfa->charMap);
960 dfa->charMapSize = size;
961 dfa->charMap = imalloc (size * sizeof(*dfa->charMap));
963 memcpy (dfa->charMap, cmap, size * sizeof(*dfa->charMap));
966 void dfa_parse_cmap_del (struct DFA *d, int from)
968 struct DFA_parse *dfa = d->parse_info;
972 for (cc = dfa->charMap; *cc; cc += 2)
975 while ((cc[0] = cc[2]))
984 void dfa_parse_cmap_add (struct DFA *d, int from, int to)
986 struct DFA_parse *dfa = d->parse_info;
991 for (cc = dfa->charMap; *cc; cc += 2)
997 indx = cc - dfa->charMap;
998 size = dfa->charMapSize;
1001 int *cn = imalloc ((size+16) * sizeof(*dfa->charMap));
1002 memcpy (cn, dfa->charMap, indx*sizeof(*dfa->charMap));
1003 ifree (dfa->charMap);
1005 dfa->charMapSize = size+16;
1007 dfa->charMap[indx] = from;
1008 dfa->charMap[indx+1] = to;
1009 dfa->charMap[indx+2] = 0;
1012 void dfa_parse_cmap_thompson (struct DFA *d)
1014 static int thompson_chars[] =
1030 dfa_parse_cmap_new (d, thompson_chars);
1033 static struct DFA_parse *dfa_parse_init (void)
1035 parse_info = (struct DFA_parse *) imalloc (sizeof (struct DFA_parse));
1037 parse_info->charset = mk_BSetHandle (255, 20);
1038 parse_info->position = 0;
1039 parse_info->rule = 0;
1040 parse_info->root = NULL;
1042 parse_info->anyset = mk_BSet (&parse_info->charset);
1043 res_BSet (parse_info->charset, parse_info->anyset);
1044 add_BSet (parse_info->charset, parse_info->anyset, '\n');
1045 com_BSet (parse_info->charset, parse_info->anyset);
1046 parse_info->use_Tnode = parse_info->max_Tnode = 0;
1047 parse_info->charMap = NULL;
1048 parse_info->charMapSize = 0;
1049 parse_info->cmap = NULL;
1053 static void rm_dfa_parse (struct DFA_parse **dfap)
1056 assert (parse_info);
1058 rm_BSetHandle (&parse_info->charset);
1059 ifree (parse_info->charMap);
1064 static struct DFA_states *mk_dfas (struct DFA_parse *dfap, int poset_chunk)
1066 struct DFA_states *dfas;
1068 assert (poset_chunk > 10);
1072 poset = mk_SetType (poset_chunk);
1075 assert (parse_info->root);
1076 dfa_trav (parse_info->root);
1078 if (debug_dfa_followpos)
1080 init_DFA_states (&dfas, poset, STATE_HASH);
1092 struct DFA *dfa_init (void)
1096 dfa = imalloc (sizeof(*dfa));
1097 dfa->parse_info = dfa_parse_init ();
1098 dfa->state_info = NULL;
1100 dfa_parse_cmap_thompson (dfa);
1104 void dfa_set_cmap (struct DFA *dfa, char **(*cmap)(const char **from, int len))
1106 dfa->parse_info->cmap = cmap;
1109 int dfa_parse (struct DFA *dfa, const char **pattern)
1114 assert (dfa->parse_info);
1115 do_parse (dfa->parse_info, pattern, &top);
1118 if ( !dfa->parse_info->root )
1119 dfa->parse_info->root = top;
1126 n->u.p[0] = dfa->parse_info->root;
1128 dfa->parse_info->root = n;
1133 void dfa_mkstate (struct DFA *dfa)
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);
1143 void dfa_delete (struct DFA **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);