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