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