home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / linuxdoc-sgml-1.1 / sgmls-1.1 / ambig.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-03  |  10.1 KB  |  439 lines
  1. /* ambig.c -
  2.    Content model ambiguity checking.
  3.  
  4.      Written by James Clark (jjc@jclark.com).
  5. */
  6. /*
  7. This uses the construction in pp8-9 of [1], extended to deal with AND
  8. groups.
  9.  
  10. Note that it is not correct for the purposes of ambiguity analysis to
  11. handle AND groups by turning them into an OR group of SEQ groups
  12. (consider (a&b?)).
  13.  
  14. We build an automaton for the entire content model by adding the
  15. following case for AND:
  16.  
  17. nullable(v) := nullable(left child) and nullable(right child)
  18. if nullable(right child) then
  19.     for each x in last(left child) do
  20.        follow(v,x) = follow(left child,x) U first(right child);
  21. if nullable(left child) then
  22.     for each x in last(right child) do
  23.         follow(v,x) = follow(right child,x) U first(left child);
  24. first(v) := first(left child) U first(right child);
  25. last(v) := first(left child) U first(right child);
  26.  
  27. We also build an automaton for each AND group by building automata for
  28. each of the members of the AND group using the above procedure and
  29. then combine the members using:
  30.  
  31. for each x in last(left child) do
  32.    follow(v,x) = follow(left child,x) U first(right child);
  33. for each x in last(right child) do
  34.    follow(v,x) = follow(right child,x) U first(left child);
  35. first(v) := first(left child) U first(right child);
  36.  
  37. The content model is ambiguous just in case one of these automata is
  38. non-deterministic.  (Note that when checking determinism we need to
  39. check the `first' set as well as all the `follow' sets.)
  40.  
  41. Why is this correct?  Consider a primitive token in a member of an AND
  42. group.  There are two worst cases for ambiguity: firstly, when none of
  43. the other members of AND group have been matched; secondly, when just
  44. the nullable members remain to be matched.  The first case is not
  45. affected by context of the AND group (unless the first case is
  46. identical to the second case.)
  47.  
  48. Note that inclusions are not relevant for the purposes of determining
  49. the ambiguity of content models. Otherwise the case in clause
  50. 11.2.5.1:
  51.  
  52.    An element that can satisfy an element in the content model is
  53.    considered to do so, even if the element is also an inclusion.
  54.  
  55. could never arise.
  56.  
  57. [1] Anne Brueggemann-Klein, Regular Expressions into Finite Automata,
  58. Universitaet Freiburg, Institut fur Informatik, 33 July 1991.
  59. */
  60.  
  61. #include "sgmlincl.h"
  62.  
  63. /* Sets of states are represented by 0-terminated, ordered lists of
  64. indexes in gbuf. */
  65.  
  66. #define MAXSTATES (GRPGTCNT+2)
  67. #define listcat(x, y) strcat((char *)(x), (char *)(y))
  68. #define listcpy(x, y) strcpy((char *)(x), (char *)(y))
  69.  
  70. /* Information about a content token. */
  71.  
  72. struct contoken {
  73.      UNCH size;
  74.      UNCH nullable;
  75.      UNCH *first;
  76.      UNCH *last;
  77. };
  78.  
  79. static VOID contoken P((int, int, struct contoken *));
  80. static VOID andgroup P((int, int, struct contoken *));
  81. static VOID orgroup P((int, int, struct contoken *));
  82. static VOID seqgroup P((int, int, struct contoken *));
  83. static VOID andambig P((int));
  84. static int listambig P((UNCH *));
  85. static VOID listmerge P((UNCH *, UNCH *));
  86. static struct contoken *newcontoken P((void));
  87. static VOID freecontoken P((struct contoken *));
  88.  
  89.  
  90. /* Dynamically allocated vector of follow sets. */
  91.  
  92. static UNCH **follow;
  93. static UNCH *mergebuf;        /* for use by listmerge */
  94.  
  95. /* Set to non-zero if the content model is ambiguous. */
  96.  
  97. static int ambigsw;
  98.  
  99. /* Check the current content model (in gbuf) for ambiguity. */
  100.  
  101. VOID ambig()
  102. {
  103.      struct contoken *s;
  104.      int i;
  105.      
  106.      if (!follow) {
  107.       /* We can't allocate everything in one chunk, because that would
  108.          overflow a 16-bit unsigned if GRPGTCNT was 253. */
  109.       UNCH *ptr;
  110.       follow = (UNCH **)rmalloc(MAXSTATES*sizeof(UNCH *));
  111.       follow[0] = 0;
  112.       ptr = (UNCH *)rmalloc((MAXSTATES - 1)*MAXSTATES);
  113.       for (i = 1; i < MAXSTATES; i++) {
  114.            follow[i] = ptr;
  115.            ptr += MAXSTATES;
  116.       }
  117.       mergebuf = (UNCH *)rmalloc(MAXSTATES);
  118.      }
  119.  
  120.      for (i = 1; i < MAXSTATES; i++)
  121.       follow[i][0] = 0;
  122.  
  123.      ambigsw = 0;
  124.  
  125.      s = newcontoken();
  126.      contoken(1, 1, s);
  127.  
  128.      ambigsw = ambigsw || listambig(s->first);
  129.  
  130.      freecontoken(s);
  131.  
  132.      for (i = 1; !ambigsw && i < MAXSTATES; i++)
  133.       if (listambig(follow[i]))
  134.            ambigsw = 1;
  135.  
  136.      if (ambigsw)
  137.       mderr(137, (UNCH *)0, (UNCH *)0);
  138. }
  139.  
  140. /* Free memory used for ambiguity checking. */
  141.  
  142. VOID ambigfree()
  143. {
  144.      if (follow) {
  145.       frem((UNIV)follow[1]);
  146.       frem((UNIV)follow);
  147.       frem((UNIV)mergebuf);
  148.       follow = 0;
  149.      }
  150. }
  151.  
  152. /* Determine whether a list of primitive content tokens (each
  153. represented by its index in gbuf) is ambiguous. */
  154.  
  155. static
  156. int listambig(list)
  157. UNCH *list;
  158. {
  159.      UNCH *p;
  160.      int chars = 0;
  161.      int rc = 0;
  162.  
  163.      for (p = list; *p; p++) {
  164.       if ((gbuf[*p].ttype & TTMASK) == TTETD) {
  165.            struct etd *e = gbuf[*p].tu.thetd;
  166.            if (e->mark) {
  167.             rc = 1;
  168.             break;
  169.            }
  170.            e->mark = 1;
  171.       }
  172.       else {
  173.            assert((gbuf[*p].ttype & TTMASK) == TTCHARS);
  174.            if (chars) {
  175.             rc = 1;
  176.             break;
  177.            }
  178.            chars = 1;
  179.       }
  180.      }
  181.  
  182.      for (p = list; *p; p++)
  183.       if ((gbuf[*p].ttype & TTMASK) == TTETD)
  184.            gbuf[*p].tu.thetd->mark = 0;
  185.  
  186.      return rc;
  187. }
  188.  
  189.  
  190. /* Analyze a content token.  The `checkand' argument is needed to ensure
  191. that the algorithm is not exponential in the AND-group nesting depth.
  192. */
  193.  
  194. static
  195. VOID contoken(m, checkand, res)
  196. int m;                /* Index of content token in gbuf */
  197. int checkand;            /* Non-zero if AND groups should be checked */
  198. struct contoken *res;        /* Result */
  199. {
  200.      UNCH flags = gbuf[m].ttype;
  201.      switch (flags & TTMASK) {
  202.      case TTCHARS:
  203.      case TTETD:
  204.       res->first[0] = m;
  205.       res->first[1] = 0;
  206.       res->last[0] = m;
  207.       res->last[1] = 0;
  208.       res->size = 1;
  209.       res->nullable = 0;
  210.       break;
  211.      case TTAND:
  212.       if (checkand)
  213.            andambig(m);
  214.       andgroup(m, checkand, res);
  215.       break;
  216.      case TTOR:
  217.       orgroup(m, checkand, res);
  218.       break;
  219.      case TTSEQ:
  220.       seqgroup(m, checkand, res);
  221.       break;
  222.      default:
  223.       abort();
  224.      }
  225.      if (flags & TREP) {
  226.       UNCH *p;
  227.       for (p = res->last; *p; p++)
  228.            listmerge(follow[*p], res->first);
  229.      }
  230.      if (flags & TOPT)
  231.       res->nullable = 1;
  232. }
  233.  
  234. /* Check an AND group for ambiguity. */
  235.  
  236. static
  237. VOID andambig(m)
  238. int m;
  239. {
  240.      int i, tnum;
  241.      int lim;
  242.      struct contoken *curr;
  243.      struct contoken *next;
  244.  
  245.      tnum = gbuf[m].tu.tnum;
  246.      assert(tnum > 0);
  247.      curr = newcontoken();
  248.      next = newcontoken();
  249.      contoken(m + 1, 0, curr);
  250.      i = m + 1 + curr->size;
  251.      curr->size += 1;
  252.      for (--tnum; tnum > 0; --tnum) {
  253.       UNCH *p;
  254.       contoken(i, 0, next);
  255.       curr->size += next->size;
  256.       i += next->size;
  257.       for (p = curr->last; *p; p++)
  258.            listcat(follow[*p], next->first);
  259.       for (p = next->last; *p; p++)
  260.            listmerge(follow[*p], curr->first);
  261.       listcat(curr->first, next->first);
  262.       listcat(curr->last, next->last);
  263.      }
  264.      lim = m + curr->size;
  265.      for (i = m + 1; i < lim; i++) {
  266.       if (listambig(follow[i]))
  267.            ambigsw = 1;
  268.       follow[i][0] = 0;
  269.      }
  270.      freecontoken(curr);
  271.      freecontoken(next);
  272. }
  273.  
  274. /* Handle an AND group. */
  275.  
  276. static
  277. VOID andgroup(m, checkand, res)
  278. int m;
  279. int checkand;
  280. struct contoken *res;
  281. {
  282.      int i, tnum;
  283.      /* union of the first sets of nullable members of the group */
  284.      UNCH *nullablefirst;
  285.      struct contoken *next;
  286.  
  287.      tnum = gbuf[m].tu.tnum;
  288.      assert(tnum > 0);
  289.      contoken(m + 1, checkand, res);
  290.      nullablefirst = (UNCH *)rmalloc(MAXSTATES);
  291.      if (res->nullable)
  292.       listcpy(nullablefirst, res->first);
  293.      else
  294.       nullablefirst[0] = 0;
  295.      i = m + 1 + res->size;
  296.      res->size += 1;
  297.      next = newcontoken();
  298.      for (--tnum; tnum > 0; --tnum) {
  299.       UNCH *p;
  300.       contoken(i, checkand, next);
  301.       res->size += next->size;
  302.       i += next->size;
  303.       if (next->nullable)
  304.            for (p = res->last; *p; p++)
  305.             listcat(follow[*p], next->first);
  306.       for (p = next->last; *p; p++)
  307.            listmerge(follow[*p], nullablefirst);
  308.       listcat(res->first, next->first);
  309.       if (next->nullable)
  310.            listcat(nullablefirst, next->first);
  311.       listcat(res->last, next->last);
  312.       res->nullable &= next->nullable;
  313.      }
  314.      frem((UNIV)nullablefirst);
  315.      freecontoken(next);
  316. }
  317.  
  318. /* Handle a SEQ group. */
  319.  
  320. static
  321. VOID seqgroup(m, checkand, res)
  322. int m;
  323. int checkand;
  324. struct contoken *res;
  325. {
  326.      int i, tnum;
  327.      struct contoken *next;
  328.  
  329.      tnum = gbuf[m].tu.tnum;
  330.      assert(tnum > 0);
  331.      contoken(m + 1, checkand, res);
  332.      i = m + 1 + res->size;
  333.      res->size += 1;
  334.      next = newcontoken();
  335.      for (--tnum; tnum > 0; --tnum) {
  336.       UNCH *p;
  337.       contoken(i, checkand, next);
  338.       res->size += next->size;
  339.       i += next->size;
  340.       for (p = res->last; *p; p++)
  341.            listcat(follow[*p], next->first);
  342.       if (res->nullable)
  343.            listcat(res->first, next->first);
  344.       if (next->nullable)
  345.            listcat(res->last, next->last);
  346.       else
  347.            listcpy(res->last, next->last);
  348.       res->nullable &= next->nullable;
  349.      }
  350.      freecontoken(next);
  351. }
  352.  
  353. /* Handle an OR group. */
  354.  
  355. static
  356. VOID orgroup(m, checkand, res)
  357. int m;
  358. int checkand;
  359. struct contoken *res;
  360. {
  361.      int i, tnum;
  362.      struct contoken *next;
  363.  
  364.      tnum = gbuf[m].tu.tnum;
  365.      assert(tnum > 0);
  366.      contoken(m + 1, checkand, res);
  367.      i = m + 1 + res->size;
  368.      res->size += 1;
  369.      next = newcontoken();
  370.      for (--tnum; tnum > 0; --tnum) {
  371.       contoken(i, checkand, next);
  372.       res->size += next->size;
  373.       i += next->size;
  374.       listcat(res->first, next->first);
  375.       listcat(res->last, next->last);
  376.       res->nullable |= next->nullable;
  377.      }
  378.      freecontoken(next);
  379. }
  380.  
  381.  
  382. /* Merge the second ordered list into the first. */
  383.  
  384. static
  385. VOID listmerge(p, b)
  386. UNCH *p, *b;
  387. {
  388.      UNCH *a = mergebuf;
  389.  
  390.      strcpy((char *)a, (char *)p);
  391.  
  392.      for (;;) {
  393.       if (*a) {
  394.            if (*b) {
  395.             if (*a < *b)
  396.              *p++ = *a++;
  397.             else if (*a > *b)
  398.              *p++ = *b++;
  399.             else
  400.              a++;
  401.            }
  402.            else
  403.             *p++ = *a++;
  404.       }
  405.       else if (*b)
  406.            *p++ = *b++;
  407.       else
  408.            break;
  409.      }
  410.      *p = '\0';
  411. }
  412.  
  413. static
  414. struct contoken *newcontoken()
  415. {
  416.      struct contoken *p = (struct contoken *)rmalloc(sizeof(struct contoken)
  417.                              + MAXSTATES*2);
  418.      p->first = (UNCH *)(p + 1);
  419.      p->last = p->first + MAXSTATES;
  420.      return p;
  421. }
  422.  
  423. static
  424. VOID freecontoken(p)
  425. struct contoken *p;
  426. {
  427.      frem((UNIV)p);
  428. }
  429.  
  430. /*
  431. Local Variables:
  432. c-indent-level: 5
  433. c-continued-statement-offset: 5
  434. c-brace-offset: -5
  435. c-argdecl-indent: 0
  436. c-label-offset: -5
  437. End:
  438. */
  439.