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