lr0.c 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598
  1. #include "defs.h"
  2. extern short *itemset;
  3. extern short *itemsetend;
  4. extern unsigned *ruleset;
  5. int nstates;
  6. core *first_state;
  7. shifts *first_shift;
  8. reductions *first_reduction;
  9. int get_state();
  10. core *new_state();
  11. static core **state_set;
  12. static core *this_state;
  13. static core *last_state;
  14. static shifts *last_shift;
  15. static reductions *last_reduction;
  16. static int nshifts;
  17. static short *shift_symbol;
  18. static short *redset;
  19. static short *shiftset;
  20. static short **kernel_base;
  21. static short **kernel_end;
  22. static short *kernel_items;
  23. allocate_itemsets()
  24. {
  25. register short *itemp;
  26. register short *item_end;
  27. register int symbol;
  28. register int i;
  29. register int count;
  30. register int max;
  31. register short *symbol_count;
  32. count = 0;
  33. symbol_count = NEW2(nsyms, short);
  34. item_end = ritem + nitems;
  35. for (itemp = ritem; itemp < item_end; itemp++)
  36. {
  37. symbol = *itemp;
  38. if (symbol >= 0)
  39. {
  40. count++;
  41. symbol_count[symbol]++;
  42. }
  43. }
  44. kernel_base = NEW2(nsyms, short *);
  45. kernel_items = NEW2(count, short);
  46. count = 0;
  47. max = 0;
  48. for (i = 0; i < nsyms; i++)
  49. {
  50. kernel_base[i] = kernel_items + count;
  51. count += symbol_count[i];
  52. if (max < symbol_count[i])
  53. max = symbol_count[i];
  54. }
  55. shift_symbol = symbol_count;
  56. kernel_end = NEW2(nsyms, short *);
  57. }
  58. allocate_storage()
  59. {
  60. allocate_itemsets();
  61. shiftset = NEW2(nsyms, short);
  62. redset = NEW2(nrules + 1, short);
  63. state_set = NEW2(nitems, core *);
  64. }
  65. append_states()
  66. {
  67. register int i;
  68. register int j;
  69. register int symbol;
  70. #ifdef TRACE
  71. fprintf(stderr, "Entering append_states()\n");
  72. #endif
  73. for (i = 1; i < nshifts; i++)
  74. {
  75. symbol = shift_symbol[i];
  76. j = i;
  77. while (j > 0 && shift_symbol[j - 1] > symbol)
  78. {
  79. shift_symbol[j] = shift_symbol[j - 1];
  80. j--;
  81. }
  82. shift_symbol[j] = symbol;
  83. }
  84. for (i = 0; i < nshifts; i++)
  85. {
  86. symbol = shift_symbol[i];
  87. shiftset[i] = get_state(symbol);
  88. }
  89. }
  90. free_storage()
  91. {
  92. FREE(shift_symbol);
  93. FREE(redset);
  94. FREE(shiftset);
  95. FREE(kernel_base);
  96. FREE(kernel_end);
  97. FREE(kernel_items);
  98. FREE(state_set);
  99. }
  100. generate_states()
  101. {
  102. allocate_storage();
  103. itemset = NEW2(nitems, short);
  104. ruleset = NEW2(WORDSIZE(nrules), unsigned);
  105. set_first_derives();
  106. initialize_states();
  107. while (this_state)
  108. {
  109. closure(this_state->items, this_state->nitems);
  110. save_reductions();
  111. new_itemsets();
  112. append_states();
  113. if (nshifts > 0)
  114. save_shifts();
  115. this_state = this_state->next;
  116. }
  117. finalize_closure();
  118. free_storage();
  119. }
  120. int
  121. get_state(symbol)
  122. int symbol;
  123. {
  124. register int key;
  125. register short *isp1;
  126. register short *isp2;
  127. register short *iend;
  128. register core *sp;
  129. register int found;
  130. register int n;
  131. #ifdef TRACE
  132. fprintf(stderr, "Entering get_state(%d)\n", symbol);
  133. #endif
  134. isp1 = kernel_base[symbol];
  135. iend = kernel_end[symbol];
  136. n = iend - isp1;
  137. key = *isp1;
  138. assert(0 <= key && key < nitems);
  139. sp = state_set[key];
  140. if (sp)
  141. {
  142. found = 0;
  143. while (!found)
  144. {
  145. if (sp->nitems == n)
  146. {
  147. found = 1;
  148. isp1 = kernel_base[symbol];
  149. isp2 = sp->items;
  150. while (found && isp1 < iend)
  151. {
  152. if (*isp1++ != *isp2++)
  153. found = 0;
  154. }
  155. }
  156. if (!found)
  157. {
  158. if (sp->link)
  159. {
  160. sp = sp->link;
  161. }
  162. else
  163. {
  164. sp = sp->link = new_state(symbol);
  165. found = 1;
  166. }
  167. }
  168. }
  169. }
  170. else
  171. {
  172. state_set[key] = sp = new_state(symbol);
  173. }
  174. return (sp->number);
  175. }
  176. initialize_states()
  177. {
  178. register int i;
  179. register short *start_derives;
  180. register core *p;
  181. start_derives = derives[start_symbol];
  182. for (i = 0; start_derives[i] >= 0; ++i)
  183. continue;
  184. p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
  185. if (p == 0) no_space();
  186. p->next = 0;
  187. p->link = 0;
  188. p->number = 0;
  189. p->accessing_symbol = 0;
  190. p->nitems = i;
  191. for (i = 0; start_derives[i] >= 0; ++i)
  192. p->items[i] = rrhs[start_derives[i]];
  193. first_state = last_state = this_state = p;
  194. nstates = 1;
  195. }
  196. new_itemsets()
  197. {
  198. register int i;
  199. register int shiftcount;
  200. register short *isp;
  201. register short *ksp;
  202. register int symbol;
  203. for (i = 0; i < nsyms; i++)
  204. kernel_end[i] = 0;
  205. shiftcount = 0;
  206. isp = itemset;
  207. while (isp < itemsetend)
  208. {
  209. i = *isp++;
  210. symbol = ritem[i];
  211. if (symbol > 0)
  212. {
  213. ksp = kernel_end[symbol];
  214. if (!ksp)
  215. {
  216. shift_symbol[shiftcount++] = symbol;
  217. ksp = kernel_base[symbol];
  218. }
  219. *ksp++ = i + 1;
  220. kernel_end[symbol] = ksp;
  221. }
  222. }
  223. nshifts = shiftcount;
  224. }
  225. core *
  226. new_state(symbol)
  227. int symbol;
  228. {
  229. register int n;
  230. register core *p;
  231. register short *isp1;
  232. register short *isp2;
  233. register short *iend;
  234. #ifdef TRACE
  235. fprintf(stderr, "Entering new_state(%d)\n", symbol);
  236. #endif
  237. if (nstates >= MAXSHORT)
  238. fatal("too many states");
  239. isp1 = kernel_base[symbol];
  240. iend = kernel_end[symbol];
  241. n = iend - isp1;
  242. p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
  243. p->accessing_symbol = symbol;
  244. p->number = nstates;
  245. p->nitems = n;
  246. isp2 = p->items;
  247. while (isp1 < iend)
  248. *isp2++ = *isp1++;
  249. last_state->next = p;
  250. last_state = p;
  251. nstates++;
  252. return (p);
  253. }
  254. /* show_cores is used for debugging */
  255. show_cores()
  256. {
  257. core *p;
  258. int i, j, k, n;
  259. int itemno;
  260. k = 0;
  261. for (p = first_state; p; ++k, p = p->next)
  262. {
  263. if (k) printf("\n");
  264. printf("state %d, number = %d, accessing symbol = %s\n",
  265. k, p->number, symbol_name[p->accessing_symbol]);
  266. n = p->nitems;
  267. for (i = 0; i < n; ++i)
  268. {
  269. itemno = p->items[i];
  270. printf("%4d ", itemno);
  271. j = itemno;
  272. while (ritem[j] >= 0) ++j;
  273. printf("%s :", symbol_name[rlhs[-ritem[j]]]);
  274. j = rrhs[-ritem[j]];
  275. while (j < itemno)
  276. printf(" %s", symbol_name[ritem[j++]]);
  277. printf(" .");
  278. while (ritem[j] >= 0)
  279. printf(" %s", symbol_name[ritem[j++]]);
  280. printf("\n");
  281. fflush(stdout);
  282. }
  283. }
  284. }
  285. /* show_ritems is used for debugging */
  286. show_ritems()
  287. {
  288. int i;
  289. for (i = 0; i < nitems; ++i)
  290. printf("ritem[%d] = %d\n", i, ritem[i]);
  291. }
  292. /* show_rrhs is used for debugging */
  293. show_rrhs()
  294. {
  295. int i;
  296. for (i = 0; i < nrules; ++i)
  297. printf("rrhs[%d] = %d\n", i, rrhs[i]);
  298. }
  299. /* show_shifts is used for debugging */
  300. show_shifts()
  301. {
  302. shifts *p;
  303. int i, j, k;
  304. k = 0;
  305. for (p = first_shift; p; ++k, p = p->next)
  306. {
  307. if (k) printf("\n");
  308. printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
  309. p->nshifts);
  310. j = p->nshifts;
  311. for (i = 0; i < j; ++i)
  312. printf("\t%d\n", p->shift[i]);
  313. }
  314. }
  315. save_shifts()
  316. {
  317. register shifts *p;
  318. register short *sp1;
  319. register short *sp2;
  320. register short *send;
  321. p = (shifts *) allocate((unsigned) (sizeof(shifts) +
  322. (nshifts - 1) * sizeof(short)));
  323. p->number = this_state->number;
  324. p->nshifts = nshifts;
  325. sp1 = shiftset;
  326. sp2 = p->shift;
  327. send = shiftset + nshifts;
  328. while (sp1 < send)
  329. *sp2++ = *sp1++;
  330. if (last_shift)
  331. {
  332. last_shift->next = p;
  333. last_shift = p;
  334. }
  335. else
  336. {
  337. first_shift = p;
  338. last_shift = p;
  339. }
  340. }
  341. save_reductions()
  342. {
  343. register short *isp;
  344. register short *rp1;
  345. register short *rp2;
  346. register int item;
  347. register int count;
  348. register reductions *p;
  349. register short *rend;
  350. count = 0;
  351. for (isp = itemset; isp < itemsetend; isp++)
  352. {
  353. item = ritem[*isp];
  354. if (item < 0)
  355. {
  356. redset[count++] = -item;
  357. }
  358. }
  359. if (count)
  360. {
  361. p = (reductions *) allocate((unsigned) (sizeof(reductions) +
  362. (count - 1) * sizeof(short)));
  363. p->number = this_state->number;
  364. p->nreds = count;
  365. rp1 = redset;
  366. rp2 = p->rules;
  367. rend = rp1 + count;
  368. while (rp1 < rend)
  369. *rp2++ = *rp1++;
  370. if (last_reduction)
  371. {
  372. last_reduction->next = p;
  373. last_reduction = p;
  374. }
  375. else
  376. {
  377. first_reduction = p;
  378. last_reduction = p;
  379. }
  380. }
  381. }
  382. set_derives()
  383. {
  384. register int i, k;
  385. register int lhs;
  386. register short *rules;
  387. derives = NEW2(nsyms, short *);
  388. rules = NEW2(nvars + nrules, short);
  389. k = 0;
  390. for (lhs = start_symbol; lhs < nsyms; lhs++)
  391. {
  392. derives[lhs] = rules + k;
  393. for (i = 0; i < nrules; i++)
  394. {
  395. if (rlhs[i] == lhs)
  396. {
  397. rules[k] = i;
  398. k++;
  399. }
  400. }
  401. rules[k] = -1;
  402. k++;
  403. }
  404. #ifdef DEBUG
  405. print_derives();
  406. #endif
  407. }
  408. free_derives()
  409. {
  410. FREE(derives[start_symbol]);
  411. FREE(derives);
  412. }
  413. #ifdef DEBUG
  414. print_derives()
  415. {
  416. register int i;
  417. register short *sp;
  418. printf("\nDERIVES\n\n");
  419. for (i = start_symbol; i < nsyms; i++)
  420. {
  421. printf("%s derives ", symbol_name[i]);
  422. for (sp = derives[i]; *sp >= 0; sp++)
  423. {
  424. printf(" %d", *sp);
  425. }
  426. putchar('\n');
  427. }
  428. putchar('\n');
  429. }
  430. #endif
  431. set_nullable()
  432. {
  433. register int i, j;
  434. register int empty;
  435. int done;
  436. nullable = MALLOC(nsyms);
  437. if (nullable == 0) no_space();
  438. for (i = 0; i < nsyms; ++i)
  439. nullable[i] = 0;
  440. done = 0;
  441. while (!done)
  442. {
  443. done = 1;
  444. for (i = 1; i < nitems; i++)
  445. {
  446. empty = 1;
  447. while ((j = ritem[i]) >= 0)
  448. {
  449. if (!nullable[j])
  450. empty = 0;
  451. ++i;
  452. }
  453. if (empty)
  454. {
  455. j = rlhs[-j];
  456. if (!nullable[j])
  457. {
  458. nullable[j] = 1;
  459. done = 0;
  460. }
  461. }
  462. }
  463. }
  464. #ifdef DEBUG
  465. for (i = 0; i < nsyms; i++)
  466. {
  467. if (nullable[i])
  468. printf("%s is nullable\n", symbol_name[i]);
  469. else
  470. printf("%s is not nullable\n", symbol_name[i]);
  471. }
  472. #endif
  473. }
  474. free_nullable()
  475. {
  476. FREE(nullable);
  477. }
  478. lr0()
  479. {
  480. set_derives();
  481. set_nullable();
  482. generate_states();
  483. }