lalr.c 10.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638
  1. #include "defs.h"
  2. typedef
  3. struct shorts
  4. {
  5. struct shorts *next;
  6. short value;
  7. }
  8. shorts;
  9. int tokensetsize;
  10. short *lookaheads;
  11. short *LAruleno;
  12. unsigned *LA;
  13. short *accessing_symbol;
  14. core **state_table;
  15. shifts **shift_table;
  16. reductions **reduction_table;
  17. short *goto_map;
  18. short *from_state;
  19. short *to_state;
  20. short **transpose();
  21. static int infinity;
  22. static int maxrhs;
  23. static int ngotos;
  24. static unsigned *F;
  25. static short **includes;
  26. static shorts **lookback;
  27. static short **R;
  28. static short *INDEX;
  29. static short *VERTICES;
  30. static int top;
  31. lalr()
  32. {
  33. tokensetsize = WORDSIZE(ntokens);
  34. set_state_table();
  35. set_accessing_symbol();
  36. set_shift_table();
  37. set_reduction_table();
  38. set_maxrhs();
  39. initialize_LA();
  40. set_goto_map();
  41. initialize_F();
  42. build_relations();
  43. compute_FOLLOWS();
  44. compute_lookaheads();
  45. }
  46. set_state_table()
  47. {
  48. register core *sp;
  49. state_table = NEW2(nstates, core *);
  50. for (sp = first_state; sp; sp = sp->next)
  51. state_table[sp->number] = sp;
  52. }
  53. set_accessing_symbol()
  54. {
  55. register core *sp;
  56. accessing_symbol = NEW2(nstates, short);
  57. for (sp = first_state; sp; sp = sp->next)
  58. accessing_symbol[sp->number] = sp->accessing_symbol;
  59. }
  60. set_shift_table()
  61. {
  62. register shifts *sp;
  63. shift_table = NEW2(nstates, shifts *);
  64. for (sp = first_shift; sp; sp = sp->next)
  65. shift_table[sp->number] = sp;
  66. }
  67. set_reduction_table()
  68. {
  69. register reductions *rp;
  70. reduction_table = NEW2(nstates, reductions *);
  71. for (rp = first_reduction; rp; rp = rp->next)
  72. reduction_table[rp->number] = rp;
  73. }
  74. set_maxrhs()
  75. {
  76. register short *itemp;
  77. register short *item_end;
  78. register int length;
  79. register int max;
  80. length = 0;
  81. max = 0;
  82. item_end = ritem + nitems;
  83. for (itemp = ritem; itemp < item_end; itemp++)
  84. {
  85. if (*itemp >= 0)
  86. {
  87. length++;
  88. }
  89. else
  90. {
  91. if (length > max) max = length;
  92. length = 0;
  93. }
  94. }
  95. maxrhs = max;
  96. }
  97. initialize_LA()
  98. {
  99. register int i, j, k;
  100. register reductions *rp;
  101. lookaheads = NEW2(nstates + 1, short);
  102. k = 0;
  103. for (i = 0; i < nstates; i++)
  104. {
  105. lookaheads[i] = k;
  106. rp = reduction_table[i];
  107. if (rp)
  108. k += rp->nreds;
  109. }
  110. lookaheads[nstates] = k;
  111. LA = NEW2(k * tokensetsize, unsigned);
  112. LAruleno = NEW2(k, short);
  113. lookback = NEW2(k, shorts *);
  114. k = 0;
  115. for (i = 0; i < nstates; i++)
  116. {
  117. rp = reduction_table[i];
  118. if (rp)
  119. {
  120. for (j = 0; j < rp->nreds; j++)
  121. {
  122. LAruleno[k] = rp->rules[j];
  123. k++;
  124. }
  125. }
  126. }
  127. }
  128. set_goto_map()
  129. {
  130. register shifts *sp;
  131. register int i;
  132. register int symbol;
  133. register int k;
  134. register short *temp_map;
  135. register int state2;
  136. register int state1;
  137. goto_map = NEW2(nvars + 1, short) - ntokens;
  138. temp_map = NEW2(nvars + 1, short) - ntokens;
  139. ngotos = 0;
  140. for (sp = first_shift; sp; sp = sp->next)
  141. {
  142. for (i = sp->nshifts - 1; i >= 0; i--)
  143. {
  144. symbol = accessing_symbol[sp->shift[i]];
  145. if (ISTOKEN(symbol)) break;
  146. if (ngotos == MAXSHORT)
  147. fatal("too many gotos");
  148. ngotos++;
  149. goto_map[symbol]++;
  150. }
  151. }
  152. k = 0;
  153. for (i = ntokens; i < nsyms; i++)
  154. {
  155. temp_map[i] = k;
  156. k += goto_map[i];
  157. }
  158. for (i = ntokens; i < nsyms; i++)
  159. goto_map[i] = temp_map[i];
  160. goto_map[nsyms] = ngotos;
  161. temp_map[nsyms] = ngotos;
  162. from_state = NEW2(ngotos, short);
  163. to_state = NEW2(ngotos, short);
  164. for (sp = first_shift; sp; sp = sp->next)
  165. {
  166. state1 = sp->number;
  167. for (i = sp->nshifts - 1; i >= 0; i--)
  168. {
  169. state2 = sp->shift[i];
  170. symbol = accessing_symbol[state2];
  171. if (ISTOKEN(symbol)) break;
  172. k = temp_map[symbol]++;
  173. from_state[k] = state1;
  174. to_state[k] = state2;
  175. }
  176. }
  177. FREE(temp_map + ntokens);
  178. }
  179. /* Map_goto maps a state/symbol pair into its numeric representation. */
  180. int
  181. map_goto(state, symbol)
  182. int state;
  183. int symbol;
  184. {
  185. register int high;
  186. register int low;
  187. register int middle;
  188. register int s;
  189. low = goto_map[symbol];
  190. high = goto_map[symbol + 1];
  191. for (;;)
  192. {
  193. assert(low <= high);
  194. middle = (low + high) >> 1;
  195. s = from_state[middle];
  196. if (s == state)
  197. return (middle);
  198. else if (s < state)
  199. low = middle + 1;
  200. else
  201. high = middle - 1;
  202. }
  203. }
  204. initialize_F()
  205. {
  206. register int i;
  207. register int j;
  208. register int k;
  209. register shifts *sp;
  210. register short *edge;
  211. register unsigned *rowp;
  212. register short *rp;
  213. register short **reads;
  214. register int nedges;
  215. register int stateno;
  216. register int symbol;
  217. register int nwords;
  218. nwords = ngotos * tokensetsize;
  219. F = NEW2(nwords, unsigned);
  220. reads = NEW2(ngotos, short *);
  221. edge = NEW2(ngotos + 1, short);
  222. nedges = 0;
  223. rowp = F;
  224. for (i = 0; i < ngotos; i++)
  225. {
  226. stateno = to_state[i];
  227. sp = shift_table[stateno];
  228. if (sp)
  229. {
  230. k = sp->nshifts;
  231. for (j = 0; j < k; j++)
  232. {
  233. symbol = accessing_symbol[sp->shift[j]];
  234. if (ISVAR(symbol))
  235. break;
  236. SETBIT(rowp, symbol);
  237. }
  238. for (; j < k; j++)
  239. {
  240. symbol = accessing_symbol[sp->shift[j]];
  241. if (nullable[symbol])
  242. edge[nedges++] = map_goto(stateno, symbol);
  243. }
  244. if (nedges)
  245. {
  246. reads[i] = rp = NEW2(nedges + 1, short);
  247. for (j = 0; j < nedges; j++)
  248. rp[j] = edge[j];
  249. rp[nedges] = -1;
  250. nedges = 0;
  251. }
  252. }
  253. rowp += tokensetsize;
  254. }
  255. SETBIT(F, 0);
  256. digraph(reads);
  257. for (i = 0; i < ngotos; i++)
  258. {
  259. if (reads[i])
  260. FREE(reads[i]);
  261. }
  262. FREE(reads);
  263. FREE(edge);
  264. }
  265. build_relations()
  266. {
  267. register int i;
  268. register int j;
  269. register int k;
  270. register short *rulep;
  271. register short *rp;
  272. register shifts *sp;
  273. register int length;
  274. register int nedges;
  275. register int done;
  276. register int state1;
  277. register int stateno;
  278. register int symbol1;
  279. register int symbol2;
  280. register short *shortp;
  281. register short *edge;
  282. register short *states;
  283. register short **new_includes;
  284. includes = NEW2(ngotos, short *);
  285. edge = NEW2(ngotos + 1, short);
  286. states = NEW2(maxrhs + 1, short);
  287. for (i = 0; i < ngotos; i++)
  288. {
  289. nedges = 0;
  290. state1 = from_state[i];
  291. symbol1 = accessing_symbol[to_state[i]];
  292. for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
  293. {
  294. length = 1;
  295. states[0] = state1;
  296. stateno = state1;
  297. for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
  298. {
  299. symbol2 = *rp;
  300. sp = shift_table[stateno];
  301. k = sp->nshifts;
  302. for (j = 0; j < k; j++)
  303. {
  304. stateno = sp->shift[j];
  305. if (accessing_symbol[stateno] == symbol2) break;
  306. }
  307. states[length++] = stateno;
  308. }
  309. add_lookback_edge(stateno, *rulep, i);
  310. length--;
  311. done = 0;
  312. while (!done)
  313. {
  314. done = 1;
  315. rp--;
  316. if (ISVAR(*rp))
  317. {
  318. stateno = states[--length];
  319. edge[nedges++] = map_goto(stateno, *rp);
  320. if (nullable[*rp] && length > 0) done = 0;
  321. }
  322. }
  323. }
  324. if (nedges)
  325. {
  326. includes[i] = shortp = NEW2(nedges + 1, short);
  327. for (j = 0; j < nedges; j++)
  328. shortp[j] = edge[j];
  329. shortp[nedges] = -1;
  330. }
  331. }
  332. new_includes = transpose(includes, ngotos);
  333. for (i = 0; i < ngotos; i++)
  334. if (includes[i])
  335. FREE(includes[i]);
  336. FREE(includes);
  337. includes = new_includes;
  338. FREE(edge);
  339. FREE(states);
  340. }
  341. add_lookback_edge(stateno, ruleno, gotono)
  342. int stateno, ruleno, gotono;
  343. {
  344. register int i, k;
  345. register int found;
  346. register shorts *sp;
  347. i = lookaheads[stateno];
  348. k = lookaheads[stateno + 1];
  349. found = 0;
  350. while (!found && i < k)
  351. {
  352. if (LAruleno[i] == ruleno)
  353. found = 1;
  354. else
  355. ++i;
  356. }
  357. assert(found);
  358. sp = NEW(shorts);
  359. sp->next = lookback[i];
  360. sp->value = gotono;
  361. lookback[i] = sp;
  362. }
  363. short **
  364. transpose(R, n)
  365. short **R;
  366. int n;
  367. {
  368. register short **new_R;
  369. register short **temp_R;
  370. register short *nedges;
  371. register short *sp;
  372. register int i;
  373. register int k;
  374. nedges = NEW2(n, short);
  375. for (i = 0; i < n; i++)
  376. {
  377. sp = R[i];
  378. if (sp)
  379. {
  380. while (*sp >= 0)
  381. nedges[*sp++]++;
  382. }
  383. }
  384. new_R = NEW2(n, short *);
  385. temp_R = NEW2(n, short *);
  386. for (i = 0; i < n; i++)
  387. {
  388. k = nedges[i];
  389. if (k > 0)
  390. {
  391. sp = NEW2(k + 1, short);
  392. new_R[i] = sp;
  393. temp_R[i] = sp;
  394. sp[k] = -1;
  395. }
  396. }
  397. FREE(nedges);
  398. for (i = 0; i < n; i++)
  399. {
  400. sp = R[i];
  401. if (sp)
  402. {
  403. while (*sp >= 0)
  404. *temp_R[*sp++]++ = i;
  405. }
  406. }
  407. FREE(temp_R);
  408. return (new_R);
  409. }
  410. compute_FOLLOWS()
  411. {
  412. digraph(includes);
  413. }
  414. compute_lookaheads()
  415. {
  416. register int i, n;
  417. register unsigned *fp1, *fp2, *fp3;
  418. register shorts *sp, *next;
  419. register unsigned *rowp;
  420. rowp = LA;
  421. n = lookaheads[nstates];
  422. for (i = 0; i < n; i++)
  423. {
  424. fp3 = rowp + tokensetsize;
  425. for (sp = lookback[i]; sp; sp = sp->next)
  426. {
  427. fp1 = rowp;
  428. fp2 = F + tokensetsize * sp->value;
  429. while (fp1 < fp3)
  430. *fp1++ |= *fp2++;
  431. }
  432. rowp = fp3;
  433. }
  434. for (i = 0; i < n; i++)
  435. for (sp = lookback[i]; sp; sp = next)
  436. {
  437. next = sp->next;
  438. FREE(sp);
  439. }
  440. FREE(lookback);
  441. FREE(F);
  442. }
  443. digraph(relation)
  444. short **relation;
  445. {
  446. register int i;
  447. infinity = ngotos + 2;
  448. INDEX = NEW2(ngotos + 1, short);
  449. VERTICES = NEW2(ngotos + 1, short);
  450. top = 0;
  451. R = relation;
  452. for (i = 0; i < ngotos; i++)
  453. INDEX[i] = 0;
  454. for (i = 0; i < ngotos; i++)
  455. {
  456. if (INDEX[i] == 0 && R[i])
  457. traverse(i);
  458. }
  459. FREE(INDEX);
  460. FREE(VERTICES);
  461. }
  462. traverse(i)
  463. register int i;
  464. {
  465. register unsigned *fp1;
  466. register unsigned *fp2;
  467. register unsigned *fp3;
  468. register int j;
  469. register short *rp;
  470. int height;
  471. unsigned *base;
  472. VERTICES[++top] = i;
  473. INDEX[i] = height = top;
  474. base = F + i * tokensetsize;
  475. fp3 = base + tokensetsize;
  476. rp = R[i];
  477. if (rp)
  478. {
  479. while ((j = *rp++) >= 0)
  480. {
  481. if (INDEX[j] == 0)
  482. traverse(j);
  483. if (INDEX[i] > INDEX[j])
  484. INDEX[i] = INDEX[j];
  485. fp1 = base;
  486. fp2 = F + j * tokensetsize;
  487. while (fp1 < fp3)
  488. *fp1++ |= *fp2++;
  489. }
  490. }
  491. if (INDEX[i] == height)
  492. {
  493. for (;;)
  494. {
  495. j = VERTICES[top--];
  496. INDEX[j] = infinity;
  497. if (i == j)
  498. break;
  499. fp1 = base;
  500. fp2 = F + j * tokensetsize;
  501. while (fp1 < fp3)
  502. *fp2++ = *fp1++;
  503. }
  504. }
  505. }