mkpar.c 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357
  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, *pref;
  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. symbol = -1;
  180. for (p = parser[i]; p; p = p->next)
  181. {
  182. if (p->symbol != symbol)
  183. {
  184. pref = p;
  185. symbol = p->symbol;
  186. }
  187. else if (i == final_state && symbol == 0)
  188. {
  189. SRcount++;
  190. p->suppressed = 1;
  191. }
  192. else if (pref->action_code == SHIFT)
  193. {
  194. if (pref->prec > 0 && p->prec > 0)
  195. {
  196. if (pref->prec < p->prec)
  197. {
  198. pref->suppressed = 2;
  199. pref = p;
  200. }
  201. else if (pref->prec > p->prec)
  202. {
  203. p->suppressed = 2;
  204. }
  205. else if (pref->assoc == LEFT)
  206. {
  207. pref->suppressed = 2;
  208. pref = p;
  209. }
  210. else if (pref->assoc == RIGHT)
  211. {
  212. p->suppressed = 2;
  213. }
  214. else
  215. {
  216. pref->suppressed = 2;
  217. p->suppressed = 2;
  218. }
  219. }
  220. else
  221. {
  222. SRcount++;
  223. p->suppressed = 1;
  224. }
  225. }
  226. else
  227. {
  228. RRcount++;
  229. p->suppressed = 1;
  230. }
  231. }
  232. SRtotal += SRcount;
  233. RRtotal += RRcount;
  234. SRconflicts[i] = SRcount;
  235. RRconflicts[i] = RRcount;
  236. }
  237. }
  238. total_conflicts()
  239. {
  240. fprintf(stderr, "%s: ", myname);
  241. if (SRtotal == 1)
  242. fprintf(stderr, "1 shift/reduce conflict");
  243. else if (SRtotal > 1)
  244. fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
  245. if (SRtotal && RRtotal)
  246. fprintf(stderr, ", ");
  247. if (RRtotal == 1)
  248. fprintf(stderr, "1 reduce/reduce conflict");
  249. else if (RRtotal > 1)
  250. fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
  251. fprintf(stderr, ".\n");
  252. }
  253. int
  254. sole_reduction(stateno)
  255. int stateno;
  256. {
  257. register int count, ruleno;
  258. register action *p;
  259. count = 0;
  260. ruleno = 0;
  261. for (p = parser[stateno]; p; p = p->next)
  262. {
  263. if (p->action_code == SHIFT && p->suppressed == 0)
  264. return (0);
  265. else if (p->action_code == REDUCE && p->suppressed == 0)
  266. {
  267. if (ruleno > 0 && p->number != ruleno)
  268. return (0);
  269. if (p->symbol != 1)
  270. ++count;
  271. ruleno = p->number;
  272. }
  273. }
  274. if (count == 0)
  275. return (0);
  276. return (ruleno);
  277. }
  278. defreds()
  279. {
  280. register int i;
  281. defred = NEW2(nstates, short);
  282. for (i = 0; i < nstates; i++)
  283. defred[i] = sole_reduction(i);
  284. }
  285. free_action_row(p)
  286. register action *p;
  287. {
  288. register action *q;
  289. while (p)
  290. {
  291. q = p->next;
  292. FREE(p);
  293. p = q;
  294. }
  295. }
  296. free_parser()
  297. {
  298. register int i;
  299. for (i = 0; i < nstates; i++)
  300. free_action_row(parser[i]);
  301. FREE(parser);
  302. }