conflicts.c 15 KB

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