conflicts.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770
  1. /* Find and resolve or report look-ahead conflicts for bison,
  2. Copyright (C) 1984, 1989 Free Software Foundation, Inc.
  3. This file is part of Bison, the GNU Compiler Compiler.
  4. Bison is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU General Public License as published by
  6. the Free Software Foundation; either version 2, or (at your option)
  7. any later version.
  8. Bison is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11. GNU General Public License for more details.
  12. You should have received a copy of the GNU General Public License
  13. along with Bison; see the file COPYING. If not, write to
  14. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  15. #ifdef _AIX
  16. #pragma alloca
  17. #endif
  18. #include <stdio.h>
  19. #include "system.h"
  20. #include "machine.h"
  21. #include "new.h"
  22. #include "files.h"
  23. #include "gram.h"
  24. #include "state.h"
  25. #ifndef __GNUC__
  26. #undef alloca
  27. #define alloca __builtin_alloca
  28. #else
  29. #ifdef HAVE_ALLOCA_H
  30. #include <alloca.h>
  31. #else
  32. #ifndef _AIX
  33. extern char *alloca ();
  34. #endif
  35. #endif
  36. #endif
  37. extern char **tags;
  38. extern int tokensetsize;
  39. extern char *consistent;
  40. extern short *accessing_symbol;
  41. extern shifts **shift_table;
  42. extern unsigned *LA;
  43. extern short *LAruleno;
  44. extern short *lookaheads;
  45. extern int verboseflag;
  46. void set_conflicts();
  47. void resolve_sr_conflict();
  48. void flush_shift();
  49. void log_resolution();
  50. void total_conflicts();
  51. void count_sr_conflicts();
  52. void count_rr_conflicts();
  53. char any_conflicts;
  54. char *conflicts;
  55. errs **err_table;
  56. int expected_conflicts;
  57. static unsigned *shiftset;
  58. static unsigned *lookaheadset;
  59. static int src_total;
  60. static int rrc_total;
  61. static int src_count;
  62. static int rrc_count;
  63. void
  64. initialize_conflicts()
  65. {
  66. register int i;
  67. /* register errs *sp; JF unused */
  68. conflicts = NEW2(nstates, char);
  69. shiftset = NEW2(tokensetsize, unsigned);
  70. lookaheadset = NEW2(tokensetsize, unsigned);
  71. err_table = NEW2(nstates, errs *);
  72. any_conflicts = 0;
  73. for (i = 0; i < nstates; i++)
  74. set_conflicts(i);
  75. }
  76. void
  77. set_conflicts(state)
  78. int state;
  79. {
  80. register int i;
  81. register int k;
  82. register shifts *shiftp;
  83. register unsigned *fp2;
  84. register unsigned *fp3;
  85. register unsigned *fp4;
  86. register unsigned *fp1;
  87. register int symbol;
  88. if (consistent[state]) return;
  89. for (i = 0; i < tokensetsize; i++)
  90. lookaheadset[i] = 0;
  91. shiftp = shift_table[state];
  92. if (shiftp)
  93. {
  94. k = shiftp->nshifts;
  95. for (i = 0; i < k; i++)
  96. {
  97. symbol = accessing_symbol[shiftp->shifts[i]];
  98. if (ISVAR(symbol)) break;
  99. SETBIT(lookaheadset, symbol);
  100. }
  101. }
  102. k = lookaheads[state + 1];
  103. fp4 = lookaheadset + tokensetsize;
  104. /* loop over all rules which require lookahead in this state */
  105. /* first check for shift-reduce conflict, and try to resolve using precedence */
  106. for (i = lookaheads[state]; i < k; i++)
  107. if (rprec[LAruleno[i]])
  108. {
  109. fp1 = LA + i * tokensetsize;
  110. fp2 = fp1;
  111. fp3 = lookaheadset;
  112. while (fp3 < fp4)
  113. {
  114. if (*fp2++ & *fp3++)
  115. {
  116. resolve_sr_conflict(state, i);
  117. break;
  118. }
  119. }
  120. }
  121. /* loop over all rules which require lookahead in this state */
  122. /* Check for conflicts not resolved above. */
  123. for (i = lookaheads[state]; i < k; i++)
  124. {
  125. fp1 = LA + i * tokensetsize;
  126. fp2 = fp1;
  127. fp3 = lookaheadset;
  128. while (fp3 < fp4)
  129. {
  130. if (*fp2++ & *fp3++)
  131. {
  132. conflicts[state] = 1;
  133. any_conflicts = 1;
  134. }
  135. }
  136. fp2 = fp1;
  137. fp3 = lookaheadset;
  138. while (fp3 < fp4)
  139. *fp3++ |= *fp2++;
  140. }
  141. }
  142. /* Attempt to resolve shift-reduce conflict for one rule
  143. by means of precedence declarations.
  144. It has already been checked that the rule has a precedence.
  145. A conflict is resolved by modifying the shift or reduce tables
  146. so that there is no longer a conflict. */
  147. void
  148. resolve_sr_conflict(state, lookaheadnum)
  149. int state;
  150. int lookaheadnum;
  151. {
  152. register int i;
  153. register int mask;
  154. register unsigned *fp1;
  155. register unsigned *fp2;
  156. register int redprec;
  157. /* Extra parens avoid errors on Ultrix 4.3. */
  158. errs *errp = (errs *) alloca ((sizeof(errs) + ntokens * sizeof(short)));
  159. short *errtokens = errp->errs;
  160. /* find the rule to reduce by to get precedence of reduction */
  161. redprec = rprec[LAruleno[lookaheadnum]];
  162. mask = 1;
  163. fp1 = LA + lookaheadnum * tokensetsize;
  164. fp2 = lookaheadset;
  165. for (i = 0; i < ntokens; i++)
  166. {
  167. if ((mask & *fp2 & *fp1) && sprec[i])
  168. /* Shift-reduce conflict occurs for token number i
  169. and it has a precedence.
  170. The precedence of shifting is that of token i. */
  171. {
  172. if (sprec[i] < redprec)
  173. {
  174. if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
  175. *fp2 &= ~mask; /* flush the shift for this token */
  176. flush_shift(state, i);
  177. }
  178. else if (sprec[i] > redprec)
  179. {
  180. if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  181. *fp1 &= ~mask; /* flush the reduce for this token */
  182. }
  183. else
  184. {
  185. /* Matching precedence levels.
  186. For left association, keep only the reduction.
  187. For right association, keep only the shift.
  188. For nonassociation, keep neither. */
  189. switch (sassoc[i])
  190. {
  191. case RIGHT_ASSOC:
  192. if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
  193. break;
  194. case LEFT_ASSOC:
  195. if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
  196. break;
  197. case NON_ASSOC:
  198. if (verboseflag) log_resolution(state, lookaheadnum, i, "an error");
  199. break;
  200. }
  201. if (sassoc[i] != RIGHT_ASSOC)
  202. {
  203. *fp2 &= ~mask; /* flush the shift for this token */
  204. flush_shift(state, i);
  205. }
  206. if (sassoc[i] != LEFT_ASSOC)
  207. {
  208. *fp1 &= ~mask; /* flush the reduce for this token */
  209. }
  210. if (sassoc[i] == NON_ASSOC)
  211. {
  212. /* Record an explicit error for this token. */
  213. *errtokens++ = i;
  214. }
  215. }
  216. }
  217. mask <<= 1;
  218. if (mask == 0)
  219. {
  220. mask = 1;
  221. fp2++; fp1++;
  222. }
  223. }
  224. errp->nerrs = errtokens - errp->errs;
  225. if (errp->nerrs)
  226. {
  227. /* Some tokens have been explicitly made errors. Allocate
  228. a permanent errs structure for this state, to record them. */
  229. i = (char *) errtokens - (char *) errp;
  230. err_table[state] = (errs *) xmalloc ((unsigned int)i);
  231. bcopy (errp, err_table[state], i);
  232. }
  233. else
  234. err_table[state] = 0;
  235. }
  236. /* turn off the shift recorded for the specified token in the specified state.
  237. Used when we resolve a shift-reduce conflict in favor of the reduction. */
  238. void
  239. flush_shift(state, token)
  240. int state;
  241. int token;
  242. {
  243. register shifts *shiftp;
  244. register int k, i;
  245. /* register unsigned symbol; JF unused */
  246. shiftp = shift_table[state];
  247. if (shiftp)
  248. {
  249. k = shiftp->nshifts;
  250. for (i = 0; i < k; i++)
  251. {
  252. if (shiftp->shifts[i] && token == accessing_symbol[shiftp->shifts[i]])
  253. (shiftp->shifts[i]) = 0;
  254. }
  255. }
  256. }
  257. void
  258. log_resolution(state, LAno, token, resolution)
  259. int state, LAno, token;
  260. char *resolution;
  261. {
  262. fprintf(foutput,
  263. "Conflict in state %d between rule %d and token %s resolved as %s.\n",
  264. state, LAruleno[LAno], tags[token], resolution);
  265. }
  266. void
  267. conflict_log()
  268. {
  269. register int i;
  270. src_total = 0;
  271. rrc_total = 0;
  272. for (i = 0; i < nstates; i++)
  273. {
  274. if (conflicts[i])
  275. {
  276. count_sr_conflicts(i);
  277. count_rr_conflicts(i);
  278. src_total += src_count;
  279. rrc_total += rrc_count;
  280. }
  281. }
  282. total_conflicts();
  283. }
  284. void
  285. verbose_conflict_log()
  286. {
  287. register int i;
  288. src_total = 0;
  289. rrc_total = 0;
  290. for (i = 0; i < nstates; i++)
  291. {
  292. if (conflicts[i])
  293. {
  294. count_sr_conflicts(i);
  295. count_rr_conflicts(i);
  296. src_total += src_count;
  297. rrc_total += rrc_count;
  298. fprintf(foutput, "State %d contains", i);
  299. if (src_count == 1)
  300. fprintf(foutput, " 1 shift/reduce conflict");
  301. else if (src_count > 1)
  302. fprintf(foutput, " %d shift/reduce conflicts", src_count);
  303. if (src_count > 0 && rrc_count > 0)
  304. fprintf(foutput, " and");
  305. if (rrc_count == 1)
  306. fprintf(foutput, " 1 reduce/reduce conflict");
  307. else if (rrc_count > 1)
  308. fprintf(foutput, " %d reduce/reduce conflicts", rrc_count);
  309. putc('.', foutput);
  310. putc('\n', foutput);
  311. }
  312. }
  313. total_conflicts();
  314. }
  315. void
  316. total_conflicts()
  317. {
  318. extern int fixed_outfiles;
  319. if (src_total == expected_conflicts && rrc_total == 0)
  320. return;
  321. if (fixed_outfiles)
  322. {
  323. /* If invoked under the name `yacc', use the output format
  324. specified by POSIX. */
  325. fprintf(stderr, "conflicts: ");
  326. if (src_total > 0)
  327. fprintf(stderr, " %d shift/reduce", src_total);
  328. if (src_total > 0 && rrc_total > 0)
  329. fprintf(stderr, ",");
  330. if (rrc_total > 0)
  331. fprintf(stderr, " %d reduce/reduce", rrc_total);
  332. putc('\n', stderr);
  333. }
  334. else
  335. {
  336. fprintf(stderr, "%s contains", infile);
  337. if (src_total == 1)
  338. fprintf(stderr, " 1 shift/reduce conflict");
  339. else if (src_total > 1)
  340. fprintf(stderr, " %d shift/reduce conflicts", src_total);
  341. if (src_total > 0 && rrc_total > 0)
  342. fprintf(stderr, " and");
  343. if (rrc_total == 1)
  344. fprintf(stderr, " 1 reduce/reduce conflict");
  345. else if (rrc_total > 1)
  346. fprintf(stderr, " %d reduce/reduce conflicts", rrc_total);
  347. putc('.', stderr);
  348. putc('\n', stderr);
  349. }
  350. }
  351. void
  352. count_sr_conflicts(state)
  353. int state;
  354. {
  355. register int i;
  356. register int k;
  357. register int mask;
  358. register shifts *shiftp;
  359. register unsigned *fp1;
  360. register unsigned *fp2;
  361. register unsigned *fp3;
  362. register int symbol;
  363. src_count = 0;
  364. shiftp = shift_table[state];
  365. if (!shiftp) return;
  366. for (i = 0; i < tokensetsize; i++)
  367. {
  368. shiftset[i] = 0;
  369. lookaheadset[i] = 0;
  370. }
  371. k = shiftp->nshifts;
  372. for (i = 0; i < k; i++)
  373. {
  374. if (! shiftp->shifts[i]) continue;
  375. symbol = accessing_symbol[shiftp->shifts[i]];
  376. if (ISVAR(symbol)) break;
  377. SETBIT(shiftset, symbol);
  378. }
  379. k = lookaheads[state + 1];
  380. fp3 = lookaheadset + tokensetsize;
  381. for (i = lookaheads[state]; i < k; i++)
  382. {
  383. fp1 = LA + i * tokensetsize;
  384. fp2 = lookaheadset;
  385. while (fp2 < fp3)
  386. *fp2++ |= *fp1++;
  387. }
  388. fp1 = shiftset;
  389. fp2 = lookaheadset;
  390. while (fp2 < fp3)
  391. *fp2++ &= *fp1++;
  392. mask = 1;
  393. fp2 = lookaheadset;
  394. for (i = 0; i < ntokens; i++)
  395. {
  396. if (mask & *fp2)
  397. src_count++;
  398. mask <<= 1;
  399. if (mask == 0)
  400. {
  401. mask = 1;
  402. fp2++;
  403. }
  404. }
  405. }
  406. void
  407. count_rr_conflicts(state)
  408. int state;
  409. {
  410. register int i;
  411. register int j;
  412. register int count;
  413. register unsigned mask;
  414. register unsigned *baseword;
  415. register unsigned *wordp;
  416. register int m;
  417. register int n;
  418. rrc_count = 0;
  419. m = lookaheads[state];
  420. n = lookaheads[state + 1];
  421. if (n - m < 2) return;
  422. mask = 1;
  423. baseword = LA + m * tokensetsize;
  424. for (i = 0; i < ntokens; i++)
  425. {
  426. wordp = baseword;
  427. count = 0;
  428. for (j = m; j < n; j++)
  429. {
  430. if (mask & *wordp)
  431. count++;
  432. wordp += tokensetsize;
  433. }
  434. if (count >= 2) rrc_count++;
  435. mask <<= 1;
  436. if (mask == 0)
  437. {
  438. mask = 1;
  439. baseword++;
  440. }
  441. }
  442. }
  443. void
  444. print_reductions(state)
  445. int state;
  446. {
  447. register int i;
  448. register int j;
  449. register int k;
  450. register unsigned *fp1;
  451. register unsigned *fp2;
  452. register unsigned *fp3;
  453. register unsigned *fp4;
  454. register int rule;
  455. register int symbol;
  456. register unsigned mask;
  457. register int m;
  458. register int n;
  459. register int default_LA;
  460. register int default_rule;
  461. register int cmax;
  462. register int count;
  463. register shifts *shiftp;
  464. register errs *errp;
  465. int nodefault = 0;
  466. for (i = 0; i < tokensetsize; i++)
  467. shiftset[i] = 0;
  468. shiftp = shift_table[state];
  469. if (shiftp)
  470. {
  471. k = shiftp->nshifts;
  472. for (i = 0; i < k; i++)
  473. {
  474. if (! shiftp->shifts[i]) continue;
  475. symbol = accessing_symbol[shiftp->shifts[i]];
  476. if (ISVAR(symbol)) break;
  477. /* if this state has a shift for the error token,
  478. don't use a default rule. */
  479. if (symbol == error_token_number) nodefault = 1;
  480. SETBIT(shiftset, symbol);
  481. }
  482. }
  483. errp = err_table[state];
  484. if (errp)
  485. {
  486. k = errp->nerrs;
  487. for (i = 0; i < k; i++)
  488. {
  489. if (! errp->errs[i]) continue;
  490. symbol = errp->errs[i];
  491. SETBIT(shiftset, symbol);
  492. }
  493. }
  494. m = lookaheads[state];
  495. n = lookaheads[state + 1];
  496. if (n - m == 1 && ! nodefault)
  497. {
  498. default_rule = LAruleno[m];
  499. fp1 = LA + m * tokensetsize;
  500. fp2 = shiftset;
  501. fp3 = lookaheadset;
  502. fp4 = lookaheadset + tokensetsize;
  503. while (fp3 < fp4)
  504. *fp3++ = *fp1++ & *fp2++;
  505. mask = 1;
  506. fp3 = lookaheadset;
  507. for (i = 0; i < ntokens; i++)
  508. {
  509. if (mask & *fp3)
  510. fprintf(foutput, " %-4s\t[reduce using rule %d (%s)]\n",
  511. tags[i], default_rule, tags[rlhs[default_rule]]);
  512. mask <<= 1;
  513. if (mask == 0)
  514. {
  515. mask = 1;
  516. fp3++;
  517. }
  518. }
  519. fprintf(foutput, " $default\treduce using rule %d (%s)\n\n",
  520. default_rule, tags[rlhs[default_rule]]);
  521. }
  522. else if (n - m >= 1)
  523. {
  524. cmax = 0;
  525. default_LA = -1;
  526. fp4 = lookaheadset + tokensetsize;
  527. if (! nodefault)
  528. for (i = m; i < n; i++)
  529. {
  530. fp1 = LA + i * tokensetsize;
  531. fp2 = shiftset;
  532. fp3 = lookaheadset;
  533. while (fp3 < fp4)
  534. *fp3++ = *fp1++ & ( ~ (*fp2++));
  535. count = 0;
  536. mask = 1;
  537. fp3 = lookaheadset;
  538. for (j = 0; j < ntokens; j++)
  539. {
  540. if (mask & *fp3)
  541. count++;
  542. mask <<= 1;
  543. if (mask == 0)
  544. {
  545. mask = 1;
  546. fp3++;
  547. }
  548. }
  549. if (count > cmax)
  550. {
  551. cmax = count;
  552. default_LA = i;
  553. default_rule = LAruleno[i];
  554. }
  555. fp2 = shiftset;
  556. fp3 = lookaheadset;
  557. while (fp3 < fp4)
  558. *fp2++ |= *fp3++;
  559. }
  560. for (i = 0; i < tokensetsize; i++)
  561. shiftset[i] = 0;
  562. if (shiftp)
  563. {
  564. k = shiftp->nshifts;
  565. for (i = 0; i < k; i++)
  566. {
  567. if (! shiftp->shifts[i]) continue;
  568. symbol = accessing_symbol[shiftp->shifts[i]];
  569. if (ISVAR(symbol)) break;
  570. SETBIT(shiftset, symbol);
  571. }
  572. }
  573. mask = 1;
  574. fp1 = LA + m * tokensetsize;
  575. fp2 = shiftset;
  576. for (i = 0; i < ntokens; i++)
  577. {
  578. int defaulted = 0;
  579. if (mask & *fp2)
  580. count = 1;
  581. else
  582. count = 0;
  583. fp3 = fp1;
  584. for (j = m; j < n; j++)
  585. {
  586. if (mask & *fp3)
  587. {
  588. if (count == 0)
  589. {
  590. if (j != default_LA)
  591. {
  592. rule = LAruleno[j];
  593. fprintf(foutput, " %-4s\treduce using rule %d (%s)\n",
  594. tags[i], rule, tags[rlhs[rule]]);
  595. }
  596. else defaulted = 1;
  597. count++;
  598. }
  599. else
  600. {
  601. if (defaulted)
  602. {
  603. rule = LAruleno[default_LA];
  604. fprintf(foutput, " %-4s\treduce using rule %d (%s)\n",
  605. tags[i], rule, tags[rlhs[rule]]);
  606. defaulted = 0;
  607. }
  608. rule = LAruleno[j];
  609. fprintf(foutput, " %-4s\t[reduce using rule %d (%s)]\n",
  610. tags[i], rule, tags[rlhs[rule]]);
  611. }
  612. }
  613. fp3 += tokensetsize;
  614. }
  615. mask <<= 1;
  616. if (mask == 0)
  617. {
  618. mask = 1;
  619. /* We tried incrementing just fp1, and just fp2; both seem wrong.
  620. It seems necessary to increment both in sync. */
  621. fp1++;
  622. fp2++;
  623. }
  624. }
  625. if (default_LA >= 0)
  626. {
  627. fprintf(foutput, " $default\treduce using rule %d (%s)\n",
  628. default_rule, tags[rlhs[default_rule]]);
  629. }
  630. putc('\n', foutput);
  631. }
  632. }
  633. void
  634. finalize_conflicts()
  635. {
  636. FREE(conflicts);
  637. FREE(shiftset);
  638. FREE(lookaheadset);
  639. }