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