2 * Copyright (C) 1994, Index Data I/S
4 * Sebastian Hammer, Adam Dickmeiss
7 * Revision 1.11 1996-01-08 19:15:24 adam
8 * Allow single $ in expressions.
10 * Revision 1.10 1996/01/08 09:09:17 adam
11 * Function dfa_parse got 'const' string argument.
12 * New functions to define char mappings made public.
14 * Revision 1.9 1995/12/06 12:24:58 adam
15 * Removed verbatim mode code.
17 * Revision 1.8 1995/12/06 09:09:58 adam
18 * Work on left and right anchors.
20 * Revision 1.7 1995/11/27 09:23:02 adam
21 * New berbatim hook in regular expressions. "[]n ..".
23 * Revision 1.6 1995/10/16 09:31:25 adam
26 * Revision 1.5 1995/10/02 15:17:58 adam
27 * Bug fix in dfa_delete.
29 * Revision 1.4 1995/09/28 09:18:52 adam
30 * Removed various preprocessor defines.
32 * Revision 1.3 1995/09/04 12:33:26 adam
33 * Various cleanup. YAZ util used instead.
35 * Revision 1.2 1995/01/25 11:30:50 adam
36 * Simple error reporting when parsing regular expressions.
37 * Memory usage reduced.
39 * Revision 1.1 1995/01/24 16:02:52 adam
40 * New private header file in dfa module (dfap.h).
41 * Module no longer uses yacc to parse regular expressions.
63 struct Tnode *p[2]; /* CAT,OR,STAR,PLUS (left,right) */
64 short ch[2]; /* if ch[0] >= 0 then this Tnode represents */
65 /* a character in range [ch[0]..ch[1]] */
66 /* otherwise ch[0] represents */
67 /* accepting no (-acceptno) */
69 unsigned pos : 15; /* CAT/OR/STAR/EPSILON or non-neg. position */
70 unsigned nullable : 1;
71 Set firstpos; /* first positions */
72 Set lastpos; /* last positions */
75 struct Tblock { /* Tnode bucket (block) */
76 struct Tblock *next; /* pointer to next bucket */
77 struct Tnode *tarray; /* array of nodes in bucket */
81 #define STATE_HASH 199
82 #define POSET_CHUNK 100
84 int debug_dfa_trav = 0;
85 int debug_dfa_tran = 0;
86 int debug_dfa_followpos = 0;
89 static struct DFA_parse *parse_info = NULL;
92 static int inside_string;
93 static const unsigned char *expr_ptr;
94 static struct Tnode **posar;
97 static Set *followpos;
99 static struct Tnode *mk_Tnode (void);
100 static struct Tnode *mk_Tnode_cset (BSet charset);
101 static void term_Tnode (void);
104 del_followpos (void),
107 mk_dfa_tran (struct DFA_states *dfas),
108 add_follow (Set lastpos, Set firstpos),
109 dfa_trav (struct Tnode *n),
110 init_followpos (void),
111 pr_tran (struct DFA_states *dfas),
112 pr_verbose (struct DFA_states *dfas),
122 *str_char (unsigned c);
138 static int lookahead;
139 static unsigned look_ch;
140 static BSet look_chars;
142 static struct Tnode *expr_1 (void),
147 static struct Tnode *expr_1 (void)
149 struct Tnode *t1, *t2, *tn;
151 if (!(t1 = expr_2 ()))
153 while (lookahead == L_ALT)
156 if (!(t2 = expr_2 ()))
168 static struct Tnode *expr_2 (void)
170 struct Tnode *t1, *t2, *tn;
172 if (!(t1 = expr_3 ()))
174 while (lookahead == L_WILD ||
175 lookahead == L_ANYZ ||
176 lookahead == L_ANY ||
178 lookahead == L_CHAR ||
179 lookahead == L_CHARS)
181 if (!(t2 = expr_3 ()))
193 static struct Tnode *expr_3 (void)
195 struct Tnode *t1, *tn;
197 if (!(t1 = expr_4 ()))
199 if (lookahead == L_CLOS0)
207 else if (lookahead == L_CLOS1)
215 else if (lookahead == L_QUEST)
221 tn->u.p[1] = mk_Tnode();
222 tn->u.p[1]->pos = EPSILON;
228 static struct Tnode *expr_4 (void)
236 if (!(t1 = expr_1 ()))
238 if (lookahead == L_RP)
245 t1->pos = ++parse_info->position;
246 t1->u.ch[1] = t1->u.ch[0] = look_ch;
250 t1 = mk_Tnode_cset (look_chars);
254 t1 = mk_Tnode_cset (parse_info->anyset);
260 t1->u.p[0] = mk_Tnode_cset (parse_info->anyset);
261 t1->u.p[1] = mk_Tnode();
262 t1->u.p[1]->pos = EPSILON;
268 t1->u.p[0] = mk_Tnode_cset (parse_info->anyset);
276 static void do_parse (struct DFA_parse *dfap, const char **s,
279 int start_anchor_flag = 0;
280 struct Tnode *t1, *t2, *tn;
284 expr_ptr = (const unsigned char *) *s;
288 if (lookahead == L_START)
290 start_anchor_flag = 1;
293 if (lookahead == L_END)
296 t1->pos = ++parse_info->position;
297 t1->u.ch[1] = t1->u.ch[0] = '\n';
303 if (t1 && lookahead == L_END)
306 t2->pos = ++parse_info->position;
307 t2->u.ch[1] = t2->u.ch[0] = '\n';
318 if (t1 && lookahead == 0)
321 t2->pos = ++parse_info->position;
322 t2->u.ch[0] = -(++parse_info->rule);
323 t2->u.ch[1] = start_anchor_flag ? 0 : -(parse_info->rule);
334 if (lookahead == L_RP)
335 err_code = DFA_ERR_RP;
336 else if (lookahead == L_LP)
337 err_code = DFA_ERR_LP;
339 err_code = DFA_ERR_SYNTAX;
342 *s = (const char *) expr_ptr;
345 static int nextchar (int *esc)
348 if (*expr_ptr == '\0')
350 else if (*expr_ptr != '\\')
379 static int nextchar_set (int *esc)
381 if (*expr_ptr == ' ')
386 return nextchar (esc);
389 static int read_charset (void)
391 int i, ch0, ch1, esc0, esc1, cc = 0;
392 look_chars = mk_BSet (&parse_info->charset);
393 res_BSet (parse_info->charset, look_chars);
395 ch0 = nextchar_set (&esc0);
396 if (!esc0 && ch0 == '^')
399 ch0 = nextchar_set (&esc0);
403 if (!esc0 && ch0 == ']')
405 add_BSet (parse_info->charset, look_chars, ch0);
406 ch1 = nextchar_set (&esc1);
407 if (!esc1 && ch1 == '-')
409 if ((ch1 = nextchar_set (&esc1)) == 0)
411 if (!esc1 && ch1 == ']')
413 add_BSet (parse_info->charset, look_chars, '-');
416 for (i=ch0; ++i<=ch1;)
417 add_BSet (parse_info->charset, look_chars, i);
418 ch0 = nextchar_set (&esc0);
427 com_BSet (parse_info->charset, look_chars);
431 static int lex_sub(void)
434 while ((look_ch = nextchar (&esc)) != 0)
439 inside_string = !inside_string;
441 else if (esc || inside_string)
443 else if (look_ch == '[')
444 return read_charset();
448 for (cc = parse_info->charMap; *cc; cc += 2)
460 static void lex (void)
462 lookahead = lex_sub ();
465 static const char *str_char (unsigned c)
482 sprintf (s+1, "x%02x", c);
504 static void out_char (int c)
506 printf ("%s", str_char (c));
509 static void term_Tnode (void)
511 struct Tblock *t, *t1;
512 for (t = parse_info->start; (t1 = t);)
520 static struct Tnode *mk_Tnode (void)
524 if (parse_info->use_Tnode == parse_info->max_Tnode)
526 tnew = (struct Tblock *) imalloc (sizeof(struct Tblock));
527 tnew->tarray = (struct Tnode *) imalloc (TADD*sizeof(struct Tnode));
530 if (parse_info->use_Tnode == 0)
531 parse_info->start = tnew;
533 parse_info->end->next = tnew;
534 parse_info->end = tnew;
536 parse_info->max_Tnode += TADD;
538 return parse_info->end->tarray+(parse_info->use_Tnode++ % TADD);
541 struct Tnode *mk_Tnode_cset (BSet charset)
543 struct Tnode *tn1, *tn0 = mk_Tnode();
544 int ch1, ch0 = trav_BSet (parse_info->charset, charset, 0);
550 tn0->pos = ++parse_info->position;
551 ch1 = travi_BSet (parse_info->charset, charset, ch0+1) ;
553 tn0->u.ch[1] = parse_info->charset->size;
556 tn0->u.ch[1] = ch1-1;
557 while ((ch0=trav_BSet (parse_info->charset, charset, ch1)) != -1)
563 tn1 = tn0->u.p[1] = mk_Tnode();
565 tn1->pos = ++(parse_info->position);
566 if ((ch1 = travi_BSet (parse_info->charset, charset,
569 tn1->u.ch[1] = parse_info->charset->size;
572 tn1->u.ch[1] = ch1-1;
579 static void del_followpos (void)
584 static void init_pos (void)
586 posar = (struct Tnode **) imalloc (sizeof(struct Tnode*)
587 * (1+parse_info->position));
590 static void del_pos (void)
595 static void add_follow (Set lastpos, Set firstpos)
599 followpos[lastpos->value] =
600 union_Set (poset, followpos[lastpos->value], firstpos);
601 lastpos = lastpos->next;
605 static void dfa_trav (struct Tnode *n)
610 dfa_trav (n->u.p[0]);
611 dfa_trav (n->u.p[1]);
612 n->nullable = n->u.p[0]->nullable & n->u.p[1]->nullable;
613 n->firstpos = mk_Set (poset);
614 n->firstpos = union_Set (poset, n->firstpos, n->u.p[0]->firstpos);
615 if (n->u.p[0]->nullable)
616 n->firstpos = union_Set (poset, n->firstpos, n->u.p[1]->firstpos);
617 n->lastpos = mk_Set (poset);
618 n->lastpos = union_Set (poset, n->lastpos, n->u.p[1]->lastpos);
619 if (n->u.p[1]->nullable)
620 n->lastpos = union_Set (poset, n->lastpos, n->u.p[0]->lastpos);
622 add_follow (n->u.p[0]->lastpos, n->u.p[1]->firstpos);
624 n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
625 n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
626 n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
627 n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
632 dfa_trav (n->u.p[0]);
633 dfa_trav (n->u.p[1]);
634 n->nullable = n->u.p[0]->nullable | n->u.p[1]->nullable;
636 n->firstpos = merge_Set (poset, n->u.p[0]->firstpos,
637 n->u.p[1]->firstpos);
638 n->lastpos = merge_Set (poset, n->u.p[0]->lastpos,
640 n->u.p[0]->firstpos = rm_Set (poset, n->u.p[0]->firstpos);
641 n->u.p[0]->lastpos = rm_Set (poset, n->u.p[0]->lastpos);
642 n->u.p[1]->firstpos = rm_Set (poset, n->u.p[1]->firstpos);
643 n->u.p[1]->lastpos = rm_Set (poset, n->u.p[1]->lastpos);
648 dfa_trav (n->u.p[0]);
649 n->nullable = n->u.p[0]->nullable;
650 n->firstpos = n->u.p[0]->firstpos;
651 n->lastpos = n->u.p[0]->lastpos;
652 add_follow (n->lastpos, n->firstpos);
657 dfa_trav (n->u.p[0]);
659 n->firstpos = n->u.p[0]->firstpos;
660 n->lastpos = n->u.p[0]->lastpos;
661 add_follow (n->lastpos, n->firstpos);
667 n->lastpos = mk_Set (poset);
668 n->firstpos = mk_Set (poset);
675 n->firstpos = mk_Set (poset);
676 n->firstpos = add_Set (poset, n->firstpos, n->pos);
677 n->lastpos = mk_Set (poset);
678 n->lastpos = add_Set (poset, n->lastpos, n->pos);
681 printf ("#%d (n#%d)", -n->u.ch[0], -n->u.ch[1]);
682 else if (n->u.ch[1] > n->u.ch[0])
685 out_char (n->u.ch[0]);
686 if (n->u.ch[1] > n->u.ch[0]+1)
688 out_char (n->u.ch[1]);
692 out_char (n->u.ch[0]);
696 printf ("\n nullable : %c\n", n->nullable ? '1' : '0');
697 printf (" firstpos :");
698 pr_Set (poset, n->firstpos);
699 printf (" lastpos :");
700 pr_Set (poset, n->lastpos);
704 static void init_followpos (void)
708 followpos = fa = (Set *) imalloc (sizeof(Set) * (1+parse_info->position));
709 for (i = parse_info->position+1; --i >= 0; fa++)
710 *fa = mk_Set (poset);
713 static void mk_dfa_tran (struct DFA_states *dfas)
720 struct DFA_state *dfa_from, *dfa_to;
723 max_char = parse_info->charset->size;
724 pos = (short *) imalloc (sizeof(*pos) * (parse_info->position+1));
726 tran_set = cp_Set (poset, parse_info->root->firstpos);
727 i = add_DFA_state (dfas, &tran_set, &dfa_from);
729 dfa_from->rule_no = 0;
730 while ((dfa_from = get_DFA_state (dfas)))
734 for (tran_set = dfa_from->set; tran_set; tran_set = tran_set->next)
735 if ((c = posar[tran_set->value]->u.ch[0]) >= 0 && c <= max_char)
736 *pos_i++ = tran_set->value;
741 c = posar[tran_set->value]->u.ch[1];
746 dfa_from->rule_no = -i;
747 dfa_from->rule_nno = -j;
749 for (char_1 = 0; char_1 <= max_char; char_1++)
752 for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
753 if (posar[i]->u.ch[1] >= char_1
754 && (c=posar[i]->u.ch[0]) < char_0)
760 if (char_0 > max_char)
765 tran_set = mk_Set (poset);
766 for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
768 if ((c=posar[i]->u.ch[0]) > char_0 && c <= char_1)
769 char_1 = c - 1; /* forward chunk */
770 else if ((c=posar[i]->u.ch[1]) >= char_0 && c < char_1)
771 char_1 = c; /* backward chunk */
772 if (posar[i]->u.ch[1] >= char_0 && posar[i]->u.ch[0] <= char_0)
773 tran_set = union_Set (poset, tran_set, followpos[i]);
777 add_DFA_state (dfas, &tran_set, &dfa_to);
778 add_DFA_tran (dfas, dfa_from, char_0, char_1, dfa_to->no);
783 sort_DFA_states (dfas);
786 static void pr_tran (struct DFA_states *dfas)
789 struct DFA_tran *tran;
790 int prev_no, i, c, no;
792 for (no=0; no < dfas->no; ++no)
794 s = dfas->sortarray[no];
795 assert (s->no == no);
796 printf ("DFA state %d", no);
798 printf ("#%d", s->rule_no);
800 printf (" #%d", s->rule_nno);
803 pr_Set (poset, s->set);
805 for (i=s->tran_no, tran=s->trans; --i >= 0; tran++)
807 if (prev_no != tran->to)
811 printf (" goto %d on [", tran->to);
814 for (c = tran->ch[0]; c <= tran->ch[1]; c++)
815 printf ("%s", str_char(c));
823 static void pr_verbose (struct DFA_states *dfas)
827 printf ("%d/%d tree nodes used, %d bytes each\n",
828 parse_info->use_Tnode, parse_info->max_Tnode, sizeof (struct Tnode));
829 k = inf_BSetHandle (parse_info->charset, &i, &j);
830 printf ("%ld/%ld character sets, %d bytes each\n",
831 i/k, j/k, k*sizeof(BSetWord));
832 k = inf_SetType (poset, &i, &j);
833 printf ("%ld/%ld poset items, %d bytes each\n", i, j, k);
834 printf ("%d DFA states\n", dfas->no);
837 static void pr_followpos (void)
840 printf ("\nfollowsets:\n");
841 for (i=1; i <= parse_info->position; i++)
844 pr_Set (poset, followpos[i]);
847 if (posar[i]->u.ch[0] < 0)
848 printf ("#%d", -posar[i]->u.ch[0]);
849 else if (posar[i]->u.ch[1] > posar[i]->u.ch[0])
852 out_char (posar[i]->u.ch[0]);
853 if (posar[i]->u.ch[1] > posar[i]->u.ch[0]+1)
855 out_char (posar[i]->u.ch[1]);
859 out_char (posar[i]->u.ch[0]);
865 void dfa_parse_cmap_clean (struct DFA *d)
867 struct DFA_parse *dfa = d->parse_info;
872 dfa->charMapSize = 7;
873 dfa->charMap = imalloc (dfa->charMapSize * sizeof(*dfa->charMap));
878 void dfa_parse_cmap_new (struct DFA *d, const int *cmap)
880 struct DFA_parse *dfa = d->parse_info;
885 for (cp = cmap; *cp; cp += 2)
887 size = cp - cmap + 1;
888 if (size > dfa->charMapSize)
891 ifree (dfa->charMap);
892 dfa->charMapSize = size;
893 dfa->charMap = imalloc (size * sizeof(*dfa->charMap));
895 memcpy (dfa->charMap, cmap, size * sizeof(*dfa->charMap));
898 void dfa_parse_cmap_del (struct DFA *d, int from)
900 struct DFA_parse *dfa = d->parse_info;
904 for (cc = dfa->charMap; *cc; cc += 2)
907 while ((cc[0] = cc[2]))
916 void dfa_parse_cmap_add (struct DFA *d, int from, int to)
918 struct DFA_parse *dfa = d->parse_info;
923 for (cc = dfa->charMap; *cc; cc += 2)
929 indx = cc - dfa->charMap;
930 size = dfa->charMapSize;
933 int *cn = imalloc ((size+16) * sizeof(*dfa->charMap));
934 memcpy (cn, dfa->charMap, indx*sizeof(*dfa->charMap));
935 ifree (dfa->charMap);
937 dfa->charMapSize = size+16;
939 dfa->charMap[indx] = from;
940 dfa->charMap[indx+1] = to;
941 dfa->charMap[indx+2] = 0;
944 void dfa_parse_cmap_thompson (struct DFA *d)
946 static int thompson_chars[] =
962 dfa_parse_cmap_new (d, thompson_chars);
965 static struct DFA_parse *dfa_parse_init (void)
967 parse_info = (struct DFA_parse *) imalloc (sizeof (struct DFA_parse));
969 parse_info->charset = mk_BSetHandle (255, 20);
970 parse_info->position = 0;
971 parse_info->rule = 0;
972 parse_info->root = NULL;
974 parse_info->anyset = mk_BSet (&parse_info->charset);
975 res_BSet (parse_info->charset, parse_info->anyset);
976 add_BSet (parse_info->charset, parse_info->anyset, '\n');
977 com_BSet (parse_info->charset, parse_info->anyset);
978 parse_info->use_Tnode = parse_info->max_Tnode = 0;
979 parse_info->charMap = NULL;
980 parse_info->charMapSize = 0;
984 static void rm_dfa_parse (struct DFA_parse **dfap)
989 rm_BSetHandle (&parse_info->charset);
990 ifree (parse_info->charMap);
995 static struct DFA_states *mk_dfas (struct DFA_parse *dfap, int poset_chunk)
997 struct DFA_states *dfas;
999 assert (poset_chunk > 10);
1003 poset = mk_SetType (poset_chunk);
1006 assert (parse_info->root);
1007 dfa_trav (parse_info->root);
1009 if (debug_dfa_followpos)
1011 init_DFA_states (&dfas, poset, STATE_HASH);
1023 struct DFA *dfa_init (void)
1027 dfa = imalloc (sizeof(*dfa));
1028 dfa->parse_info = dfa_parse_init ();
1029 dfa->state_info = NULL;
1031 dfa_parse_cmap_thompson (dfa);
1035 int dfa_parse (struct DFA *dfa, const char **pattern)
1040 assert (dfa->parse_info);
1041 do_parse (dfa->parse_info, pattern, &top);
1044 if ( !dfa->parse_info->root )
1045 dfa->parse_info->root = top;
1052 n->u.p[0] = dfa->parse_info->root;
1054 dfa->parse_info->root = n;
1059 void dfa_mkstate (struct DFA *dfa)
1063 dfa->state_info = mk_dfas (dfa->parse_info, POSET_CHUNK);
1064 dfa->no_states = dfa->state_info->no;
1065 dfa->states = dfa->state_info->sortarray;
1066 rm_dfa_parse (&dfa->parse_info);
1069 void dfa_delete (struct DFA **dfap)
1073 if ((*dfap)->parse_info)
1074 rm_dfa_parse (&(*dfap)->parse_info);
1075 if ((*dfap)->state_info)
1076 rm_DFA_states (&(*dfap)->state_info);