mkpar.c 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371
  1. #include "defs.h"
  2. action **parser;
  3. int SRtotal;
  4. int RRtotal;
  5. short *SRconflicts;
  6. short *RRconflicts;
  7. short *defred;
  8. short *rules_used;
  9. short nunused;
  10. short final_state;
  11. static int SRcount;
  12. static int RRcount;
  13. extern action *parse_actions();
  14. extern action *get_shifts();
  15. extern action *add_reductions();
  16. extern action *add_reduce();
  17. make_parser()
  18. {
  19. register int i;
  20. parser = NEW2(nstates, action *);
  21. for (i = 0; i < nstates; i++)
  22. parser[i] = parse_actions(i);
  23. find_final_state();
  24. remove_conflicts();
  25. unused_rules();
  26. if (SRtotal + RRtotal > 0) total_conflicts();
  27. defreds();
  28. }
  29. action *
  30. parse_actions(stateno)
  31. register int stateno;
  32. {
  33. register action *actions;
  34. actions = get_shifts(stateno);
  35. actions = add_reductions(stateno, actions);
  36. return (actions);
  37. }
  38. action *
  39. get_shifts(stateno)
  40. int stateno;
  41. {
  42. register action *actions, *temp;
  43. register shifts *sp;
  44. register short *to_state;
  45. register int i, k;
  46. register int symbol;
  47. actions = 0;
  48. sp = shift_table[stateno];
  49. if (sp)
  50. {
  51. to_state = sp->shift;
  52. for (i = sp->nshifts - 1; i >= 0; i--)
  53. {
  54. k = to_state[i];
  55. symbol = accessing_symbol[k];
  56. if (ISTOKEN(symbol))
  57. {
  58. temp = NEW(action);
  59. temp->next = actions;
  60. temp->symbol = symbol;
  61. temp->number = k;
  62. temp->prec = symbol_prec[symbol];
  63. temp->action_code = SHIFT;
  64. temp->assoc = symbol_assoc[symbol];
  65. actions = temp;
  66. }
  67. }
  68. }
  69. return (actions);
  70. }
  71. action *
  72. add_reductions(stateno, actions)
  73. int stateno;
  74. register action *actions;
  75. {
  76. register int i, j, m, n;
  77. register int ruleno, tokensetsize;
  78. register unsigned *rowp;
  79. tokensetsize = WORDSIZE(ntokens);
  80. m = lookaheads[stateno];
  81. n = lookaheads[stateno + 1];
  82. for (i = m; i < n; i++)
  83. {
  84. ruleno = LAruleno[i];
  85. rowp = LA + i * tokensetsize;
  86. for (j = ntokens - 1; j >= 0; j--)
  87. {
  88. if (BIT(rowp, j))
  89. actions = add_reduce(actions, ruleno, j);
  90. }
  91. }
  92. return (actions);
  93. }
  94. action *
  95. add_reduce(actions, ruleno, symbol)
  96. register action *actions;
  97. register int ruleno, symbol;
  98. {
  99. register action *temp, *prev, *next;
  100. prev = 0;
  101. for (next = actions; next && next->symbol < symbol; next = next->next)
  102. prev = next;
  103. while (next && next->symbol == symbol && next->action_code == SHIFT)
  104. {
  105. prev = next;
  106. next = next->next;
  107. }
  108. while (next && next->symbol == symbol &&
  109. next->action_code == REDUCE && next->number < ruleno)
  110. {
  111. prev = next;
  112. next = next->next;
  113. }
  114. temp = NEW(action);
  115. temp->next = next;
  116. temp->symbol = symbol;
  117. temp->number = ruleno;
  118. temp->prec = rprec[ruleno];
  119. temp->action_code = REDUCE;
  120. temp->assoc = rassoc[ruleno];
  121. if (prev)
  122. prev->next = temp;
  123. else
  124. actions = temp;
  125. return (actions);
  126. }
  127. find_final_state()
  128. {
  129. register int goal, i;
  130. register short *to_state;
  131. register shifts *p;
  132. p = shift_table[0];
  133. to_state = p->shift;
  134. goal = ritem[1];
  135. for (i = p->nshifts - 1; i >= 0; --i)
  136. {
  137. final_state = to_state[i];
  138. if (accessing_symbol[final_state] == goal) break;
  139. }
  140. }
  141. unused_rules()
  142. {
  143. register int i;
  144. register action *p;
  145. rules_used = (short *) MALLOC(nrules*sizeof(short));
  146. if (rules_used == 0) no_space();
  147. for (i = 0; i < nrules; ++i)
  148. rules_used[i] = 0;
  149. for (i = 0; i < nstates; ++i)
  150. {
  151. for (p = parser[i]; p; p = p->next)
  152. {
  153. if (p->action_code == REDUCE && p->suppressed == 0)
  154. rules_used[p->number] = 1;
  155. }
  156. }
  157. nunused = 0;
  158. for (i = 3; i < nrules; ++i)
  159. if (!rules_used[i]) ++nunused;
  160. if (nunused)
  161. if (nunused == 1)
  162. fprintf(stderr, "%s: 1 rule never reduced\n", myname);
  163. else
  164. fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
  165. }
  166. remove_conflicts()
  167. {
  168. register int i;
  169. register int symbol;
  170. register action *p, *q;
  171. SRtotal = 0;
  172. RRtotal = 0;
  173. SRconflicts = NEW2(nstates, short);
  174. RRconflicts = NEW2(nstates, short);
  175. for (i = 0; i < nstates; i++)
  176. {
  177. SRcount = 0;
  178. RRcount = 0;
  179. for (p = parser[i]; p; p = q->next)
  180. {
  181. symbol = p->symbol;
  182. q = p;
  183. while (q->next && q->next->symbol == symbol)
  184. q = q->next;
  185. if (i == final_state && symbol == 0)
  186. end_conflicts(p, q);
  187. else if (p != q)
  188. resolve_conflicts(p, q);
  189. }
  190. SRtotal += SRcount;
  191. RRtotal += RRcount;
  192. SRconflicts[i] = SRcount;
  193. RRconflicts[i] = RRcount;
  194. }
  195. }
  196. end_conflicts(p, q)
  197. register action *p, *q;
  198. {
  199. for (;;)
  200. {
  201. SRcount++;
  202. p->suppressed = 1;
  203. if (p == q) break;
  204. p = p->next;
  205. }
  206. }
  207. resolve_conflicts(first, last)
  208. register action *first, *last;
  209. {
  210. register action *p;
  211. register int count;
  212. count = 1;
  213. for (p = first; p != last; p = p->next)
  214. ++count;
  215. assert(count > 1);
  216. if (first->action_code == SHIFT && count == 2 &&
  217. first->prec > 0 && last->prec > 0)
  218. {
  219. if (first->prec == last->prec)
  220. {
  221. if (first->assoc == LEFT)
  222. first->suppressed = 2;
  223. else if (first->assoc == RIGHT)
  224. last->suppressed = 2;
  225. else
  226. {
  227. first->suppressed = 2;
  228. last->suppressed = 2;
  229. first->action_code = ERROR;
  230. last->action_code = ERROR;
  231. }
  232. }
  233. else if (first->prec < last->prec)
  234. first->suppressed = 2;
  235. else
  236. last->suppressed = 2;
  237. }
  238. else
  239. {
  240. if (first->action_code == SHIFT)
  241. SRcount += (count - 1);
  242. else
  243. RRcount += (count - 1);
  244. for (p = first; p != last; p = p->next, p->suppressed = 1)
  245. continue;
  246. }
  247. }
  248. total_conflicts()
  249. {
  250. fprintf(stderr, "%s: ", myname);
  251. if (SRtotal == 1)
  252. fprintf(stderr, "1 shift/reduce conflict");
  253. else if (SRtotal > 1)
  254. fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
  255. if (SRtotal && RRtotal)
  256. fprintf(stderr, ", ");
  257. if (RRtotal == 1)
  258. fprintf(stderr, "1 reduce/reduce conflict");
  259. else if (RRtotal > 1)
  260. fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
  261. fprintf(stderr, ".\n");
  262. }
  263. int
  264. sole_reduction(stateno)
  265. int stateno;
  266. {
  267. register int count, ruleno;
  268. register action *p;
  269. count = 0;
  270. ruleno = 0;
  271. for (p = parser[stateno]; p; p = p->next)
  272. {
  273. if (p->action_code == SHIFT && p->suppressed == 0)
  274. return (0);
  275. else if (p->action_code == REDUCE && p->suppressed == 0)
  276. {
  277. if (ruleno > 0 && p->number != ruleno)
  278. return (0);
  279. if (p->symbol != 1)
  280. ++count;
  281. ruleno = p->number;
  282. }
  283. }
  284. if (count == 0)
  285. return (0);
  286. return (ruleno);
  287. }
  288. defreds()
  289. {
  290. register int i;
  291. defred = NEW2(nstates, short);
  292. for (i = 0; i < nstates; i++)
  293. defred[i] = sole_reduction(i);
  294. }
  295. free_action_row(p)
  296. register action *p;
  297. {
  298. register action *q;
  299. while (p)
  300. {
  301. q = p->next;
  302. FREE(p);
  303. p = q;
  304. }
  305. }
  306. free_parser()
  307. {
  308. register int i;
  309. for (i = 0; i < nstates; i++)
  310. free_action_row(parser[i]);
  311. FREE(parser);
  312. }