closure.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265
  1. #include "defs.h"
  2. short *itemset;
  3. short *itemsetend;
  4. unsigned *ruleset;
  5. static unsigned *first_derives;
  6. static unsigned *EFF;
  7. set_EFF()
  8. {
  9. register unsigned *row;
  10. register int symbol;
  11. register short *sp;
  12. register int rowsize;
  13. register int i;
  14. register int rule;
  15. rowsize = WORDSIZE(nvars);
  16. EFF = NEW2(nvars * rowsize, unsigned);
  17. row = EFF;
  18. for (i = start_symbol; i < nsyms; i++)
  19. {
  20. sp = derives[i];
  21. for (rule = *sp; rule > 0; rule = *++sp)
  22. {
  23. symbol = ritem[rrhs[rule]];
  24. if (ISVAR(symbol))
  25. {
  26. symbol -= start_symbol;
  27. SETBIT(row, symbol);
  28. }
  29. }
  30. row += rowsize;
  31. }
  32. reflexive_transitive_closure(EFF, nvars);
  33. #ifdef DEBUG
  34. print_EFF();
  35. #endif
  36. }
  37. set_first_derives()
  38. {
  39. register unsigned *rrow;
  40. register unsigned *vrow;
  41. register int j;
  42. register unsigned mask;
  43. register unsigned cword;
  44. register short *rp;
  45. int rule;
  46. int i;
  47. int rulesetsize;
  48. int varsetsize;
  49. rulesetsize = WORDSIZE(nrules);
  50. varsetsize = WORDSIZE(nvars);
  51. first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  52. set_EFF();
  53. rrow = first_derives + ntokens * rulesetsize;
  54. for (i = start_symbol; i < nsyms; i++)
  55. {
  56. vrow = EFF + ((i - ntokens) * varsetsize);
  57. cword = *vrow++;
  58. mask = 1;
  59. for (j = start_symbol; j < nsyms; j++)
  60. {
  61. if (cword & mask)
  62. {
  63. rp = derives[j];
  64. while ((rule = *rp++) >= 0)
  65. {
  66. SETBIT(rrow, rule);
  67. }
  68. }
  69. mask <<= 1;
  70. if (mask == 0)
  71. {
  72. cword = *vrow++;
  73. mask = 1;
  74. }
  75. }
  76. vrow += varsetsize;
  77. rrow += rulesetsize;
  78. }
  79. #ifdef DEBUG
  80. print_first_derives();
  81. #endif
  82. FREE(EFF);
  83. }
  84. closure(nucleus, n)
  85. short *nucleus;
  86. int n;
  87. {
  88. register int ruleno;
  89. register unsigned word;
  90. register unsigned mask;
  91. register short *csp;
  92. register unsigned *dsp;
  93. register unsigned *rsp;
  94. register int rulesetsize;
  95. short *csend;
  96. unsigned *rsend;
  97. int symbol;
  98. int itemno;
  99. rulesetsize = WORDSIZE(nrules);
  100. rsp = ruleset;
  101. rsend = ruleset + rulesetsize;
  102. for (rsp = ruleset; rsp < rsend; rsp++)
  103. *rsp = 0;
  104. csend = nucleus + n;
  105. for (csp = nucleus; csp < csend; ++csp)
  106. {
  107. symbol = ritem[*csp];
  108. if (ISVAR(symbol))
  109. {
  110. dsp = first_derives + symbol * rulesetsize;
  111. rsp = ruleset;
  112. while (rsp < rsend)
  113. *rsp++ |= *dsp++;
  114. }
  115. }
  116. ruleno = 0;
  117. itemsetend = itemset;
  118. csp = nucleus;
  119. for (rsp = ruleset; rsp < rsend; ++rsp)
  120. {
  121. word = *rsp;
  122. if (word == 0)
  123. ruleno += BITS_PER_WORD;
  124. else
  125. {
  126. mask = 1;
  127. while (mask)
  128. {
  129. if (word & mask)
  130. {
  131. itemno = rrhs[ruleno];
  132. while (csp < csend && *csp < itemno)
  133. *itemsetend++ = *csp++;
  134. *itemsetend++ = itemno;
  135. while (csp < csend && *csp == itemno)
  136. ++csp;
  137. }
  138. mask <<= 1;
  139. ++ruleno;
  140. }
  141. }
  142. }
  143. while (csp < csend)
  144. *itemsetend++ = *csp++;
  145. #ifdef DEBUG
  146. print_closure(n);
  147. #endif
  148. }
  149. finalize_closure()
  150. {
  151. FREE(itemset);
  152. FREE(ruleset);
  153. FREE(first_derives + ntokens * WORDSIZE(nrules));
  154. }
  155. #ifdef DEBUG
  156. print_closure(n)
  157. int n;
  158. {
  159. register short *isp;
  160. printf("\n\nn = %d\n\n", n);
  161. for (isp = itemset; isp < itemsetend; isp++)
  162. printf(" %d\n", *isp);
  163. }
  164. print_EFF()
  165. {
  166. register int i, j, k;
  167. register unsigned *rowp;
  168. register unsigned word;
  169. register unsigned mask;
  170. printf("\n\nEpsilon Free Firsts\n");
  171. for (i = start_symbol; i < nsyms; i++)
  172. {
  173. printf("\n%s", symbol_name[i]);
  174. rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  175. word = *rowp++;
  176. mask = 1;
  177. for (j = 0; j < nvars; j++)
  178. {
  179. if (word & mask)
  180. printf(" %s", symbol_name[start_symbol + j]);
  181. mask <<= 1;
  182. if (mask == 0)
  183. {
  184. word = *rowp++;
  185. mask = 1;
  186. }
  187. }
  188. }
  189. }
  190. print_first_derives()
  191. {
  192. register int i;
  193. register int j;
  194. register unsigned *rp;
  195. register unsigned cword;
  196. register unsigned mask;
  197. printf("\n\n\nFirst Derives\n");
  198. for (i = start_symbol; i < nsyms; i++)
  199. {
  200. printf("\n%s derives\n", symbol_name[i]);
  201. rp = first_derives + i * WORDSIZE(nrules);
  202. cword = *rp++;
  203. mask = 1;
  204. for (j = 0; j <= nrules; j++)
  205. {
  206. if (cword & mask)
  207. printf(" %d\n", j);
  208. mask <<= 1;
  209. if (mask == 0)
  210. {
  211. cword = *rp++;
  212. mask = 1;
  213. }
  214. }
  215. }
  216. fflush(stdout);
  217. }
  218. #endif