![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to output.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / bison|
Return to output.c CVS log | Up to [Apple XNU] / GNUtools / bison |
1.1 root 1: /* Output the generated parsing program for bison,
2: Copyright (C) 1984, 1986, 1989 Free Software Foundation, Inc.
3:
4: This file is part of Bison, the GNU Compiler Compiler.
5:
6: Bison is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: Bison is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with Bison; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20:
21: /* functions to output parsing data to various files. Entries are:
22:
23: output_headers ()
24:
25: Output constant strings to the beginning of certain files.
26:
27: output_trailers()
28:
29: Output constant strings to the ends of certain files.
30:
31: output ()
32:
33: Output the parsing tables and the parser code to ftable.
34:
35: The parser tables consist of these tables.
36: Starred ones needed only for the semantic parser.
37:
38: yytranslate = vector mapping yylex's token numbers into bison's token numbers.
39:
40: yytname = vector of string-names indexed by bison token number
41:
42: yyrline = vector of line-numbers of all rules. For yydebug printouts.
43:
44: yyrhs = vector of items of all rules.
45: This is exactly what ritems contains. For yydebug and for semantic
46: parser.
47:
48: yyprhs[r] = index in yyrhs of first item for rule r.
49:
50: yyr1[r] = symbol number of symbol that rule r derives.
51:
52: yyr2[r] = number of symbols composing right hand side of rule r.
53:
54: * yystos[s] = the symbol number of the symbol that leads to state s.
55:
56: yydefact[s] = default rule to reduce with in state s,
57: when yytable doesn't specify something else to do.
58: Zero means the default is an error.
59:
60: yydefgoto[i] = default state to go to after a reduction of a rule that
61: generates variable ntokens + i, except when yytable
62: specifies something else to do.
63:
64: yypact[s] = index in yytable of the portion describing state s.
65: The lookahead token's type is used to index that portion
66: to find out what to do.
67:
68: If the value in yytable is positive,
69: we shift the token and go to that state.
70:
71: If the value is negative, it is minus a rule number to reduce by.
72:
73: If the value is zero, the default action from yydefact[s] is used.
74:
75: yypgoto[i] = the index in yytable of the portion describing
76: what to do after reducing a rule that derives variable i + ntokens.
77: This portion is indexed by the parser state number
78: as of before the text for this nonterminal was read.
79: The value from yytable is the state to go to.
80:
81: yytable = a vector filled with portions for different uses,
82: found via yypact and yypgoto.
83:
84: yycheck = a vector indexed in parallel with yytable.
85: It indicates, in a roundabout way, the bounds of the
86: portion you are trying to examine.
87:
88: Suppose that the portion of yytable starts at index p
89: and the index to be examined within the portion is i.
90: Then if yycheck[p+i] != i, i is outside the bounds
91: of what is actually allocated, and the default
92: (from yydefact or yydefgoto) should be used.
93: Otherwise, yytable[p+i] should be used.
94:
95: YYFINAL = the state number of the termination state.
96: YYFLAG = most negative short int. Used to flag ??
97: YYNTBASE = ntokens.
98:
99: */
100:
101: #include <stdio.h>
102: #include "system.h"
103: #include "machine.h"
104: #include "new.h"
105: #include "files.h"
106: #include "gram.h"
107: #include "state.h"
108:
109:
110: extern int debugflag;
111: extern int nolinesflag;
112:
113: extern char **tags;
114: extern int tokensetsize;
115: extern int final_state;
116: extern core **state_table;
117: extern shifts **shift_table;
118: extern errs **err_table;
119: extern reductions **reduction_table;
120: extern short *accessing_symbol;
121: extern unsigned *LA;
122: extern short *LAruleno;
123: extern short *lookaheads;
124: extern char *consistent;
125: extern short *goto_map;
126: extern short *from_state;
127: extern short *to_state;
128:
129: void output_token_translations();
130: void output_gram();
131: void output_stos();
132: void output_rule_data();
133: void output_defines();
134: void output_actions();
135: void token_actions();
136: void save_row();
137: void goto_actions();
138: void save_column();
139: void sort_actions();
140: void pack_table();
141: void output_base();
142: void output_table();
143: void output_check();
144: void output_parser();
145: void output_program();
146: void free_itemset();
147: void free_shifts();
148: void free_reductions();
149: void free_itemsets();
150: int action_row();
151: int default_goto();
152: int matching_state();
153: int pack_vector();
154:
155: extern void berror();
156: extern void fatals();
157:
158: static int nvectors;
159: static int nentries;
160: static short **froms;
161: static short **tos;
162: static short *tally;
163: static short *width;
164: static short *actrow;
165: static short *state_count;
166: static short *order;
167: static short *base;
168: static short *pos;
169: static short *table;
170: static short *check;
171: static int lowzero;
172: static int high;
173:
174:
175:
176: #define GUARDSTR "\n#include \"%s\"\nextern int yyerror;\n\
177: extern int yycost;\nextern char * yymsg;\nextern YYSTYPE yyval;\n\n\
178: yyguard(n, yyvsp, yylsp)\nregister int n;\nregister YYSTYPE *yyvsp;\n\
179: register YYLTYPE *yylsp;\n\
180: {\n yyerror = 0;\nyycost = 0;\n yymsg = 0;\nswitch (n)\n {"
181:
182: #define ACTSTR "\n#include \"%s\"\nextern YYSTYPE yyval;\
183: \nextern int yychar;\
184: yyaction(n, yyvsp, yylsp)\nregister int n;\nregister YYSTYPE *yyvsp;\n\
185: register YYLTYPE *yylsp;\n{\n switch (n)\n{"
186:
187: #define ACTSTR_SIMPLE "\n switch (yyn) {\n"
188:
189:
190: void
191: output_headers()
192: {
193: if (semantic_parser)
194: fprintf(fguard, GUARDSTR, attrsfile);
195: fprintf(faction, (semantic_parser ? ACTSTR : ACTSTR_SIMPLE), attrsfile);
196: /* if (semantic_parser) JF moved this below
197: fprintf(ftable, "#include \"%s\"\n", attrsfile);
198: fprintf(ftable, "#include <stdio.h>\n\n");
199: */
200:
201: /* Rename certain symbols if -p was specified. */
202: if (spec_name_prefix)
203: {
204: fprintf(ftable, "#define yyparse %sparse\n", spec_name_prefix);
205: fprintf(ftable, "#define yylex %slex\n", spec_name_prefix);
206: fprintf(ftable, "#define yyerror %serror\n", spec_name_prefix);
207: fprintf(ftable, "#define yylval %slval\n", spec_name_prefix);
208: fprintf(ftable, "#define yychar %schar\n", spec_name_prefix);
209: fprintf(ftable, "#define yydebug %sdebug\n", spec_name_prefix);
210: fprintf(ftable, "#define yynerrs %snerrs\n", spec_name_prefix);
211: }
212: }
213:
214:
215: void
216: output_trailers()
217: {
218: if (semantic_parser)
219: {
220: fprintf(fguard, "\n }\n}\n");
221: fprintf(faction, "\n }\n}\n");
222: }
223: else
224: fprintf(faction, "\n}\n");
225: }
226:
227:
228: void
229: output()
230: {
231: int c;
232:
233: /* output_token_defines(ftable); / * JF put out token defines FIRST */
234: if (!semantic_parser) /* JF Put out other stuff */
235: {
236: rewind(fattrs);
237: while ((c=getc(fattrs))!=EOF)
238: putc(c,ftable);
239: }
240:
241: if (debugflag)
242: fprintf(ftable, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n\n",
243: !!debugflag);
244:
245: if (semantic_parser)
246: fprintf(ftable, "#include \"%s\"\n", attrsfile);
247: fprintf(ftable, "#include <stdio.h>\n\n");
248:
249: /* Make "const" do nothing if not in ANSI C. */
250: fprintf (ftable, "#ifndef __cplusplus\n#ifndef __STDC__\n#define const\n#endif\n#endif\n\n");
251:
252: free_itemsets();
253: output_defines();
254: output_token_translations();
255: /* if (semantic_parser) */
256: /* This is now unconditional because debugging printouts can use it. */
257: output_gram();
258: FREE(ritem);
259: if (semantic_parser)
260: output_stos();
261: output_rule_data();
262: output_actions();
263: output_parser();
264: output_program();
265: }
266:
267:
268: void
269: output_token_translations()
270: {
271: register int i, j;
272: /* register short *sp; JF unused */
273:
274: if (translations)
275: {
276: fprintf(ftable,
277: "\n#define YYTRANSLATE(x) ((unsigned)(x) <= %d ? yytranslate[x] : %d)\n",
278: max_user_token_number, nsyms);
279:
280: if (ntokens < 127) /* play it very safe; check maximum element value. */
281: fprintf(ftable, "\nstatic const char yytranslate[] = { 0");
282: else
283: fprintf(ftable, "\nstatic const short yytranslate[] = { 0");
284:
285: j = 10;
286: for (i = 1; i <= max_user_token_number; i++)
287: {
288: putc(',', ftable);
289:
290: if (j >= 10)
291: {
292: putc('\n', ftable);
293: j = 1;
294: }
295: else
296: {
297: j++;
298: }
299:
300: fprintf(ftable, "%6d", token_translations[i]);
301: }
302:
303: fprintf(ftable, "\n};\n");
304: }
305: else
306: {
307: fprintf(ftable, "\n#define YYTRANSLATE(x) (x)\n");
308: }
309: }
310:
311:
312: void
313: output_gram()
314: {
315: register int i;
316: register int j;
317: register short *sp;
318:
319: /* With the ordinary parser,
320: yyprhs and yyrhs are needed only for yydebug. */
321: if (!semantic_parser)
322: fprintf(ftable, "\n#if YYDEBUG != 0");
323:
324: fprintf(ftable, "\nstatic const short yyprhs[] = { 0");
325:
326: j = 10;
327: for (i = 1; i <= nrules; i++)
328: {
329: putc(',', ftable);
330:
331: if (j >= 10)
332: {
333: putc('\n', ftable);
334: j = 1;
335: }
336: else
337: {
338: j++;
339: }
340:
341: fprintf(ftable, "%6d", rrhs[i]);
342: }
343:
344: fprintf(ftable, "\n};\n");
345:
346: fprintf(ftable, "\nstatic const short yyrhs[] = {%6d", ritem[0]);
347:
348: j = 10;
349: for (sp = ritem + 1; *sp; sp++)
350: {
351: putc(',', ftable);
352:
353: if (j >= 10)
354: {
355: putc('\n', ftable);
356: j = 1;
357: }
358: else
359: {
360: j++;
361: }
362:
363: if (*sp > 0)
364: fprintf(ftable, "%6d", *sp);
365: else
366: fprintf(ftable, " 0");
367: }
368:
369: fprintf(ftable, "\n};\n");
370:
371: if(!semantic_parser)
372: fprintf(ftable, "\n#endif\n");
373: }
374:
375:
376: void
377: output_stos()
378: {
379: register int i;
380: register int j;
381:
382: fprintf(ftable, "\nstatic const short yystos[] = { 0");
383:
384: j = 10;
385: for (i = 1; i < nstates; i++)
386: {
387: putc(',', ftable);
388:
389: if (j >= 10)
390: {
391: putc('\n', ftable);
392: j = 1;
393: }
394: else
395: {
396: j++;
397: }
398:
399: fprintf(ftable, "%6d", accessing_symbol[i]);
400: }
401:
402: fprintf(ftable, "\n};\n");
403: }
404:
405:
406: void
407: output_rule_data()
408: {
409: register int i;
410: register int j;
411:
412: fprintf(ftable, "\n#if YYDEBUG != 0\nstatic const short yyrline[] = { 0");
413:
414: j = 10;
415: for (i = 1; i <= nrules; i++)
416: {
417: putc(',', ftable);
418:
419: if (j >= 10)
420: {
421: putc('\n', ftable);
422: j = 1;
423: }
424: else
425: {
426: j++;
427: }
428:
429: fprintf(ftable, "%6d", rline[i]);
430: }
431:
432: /* Output the table of symbol names. */
433:
434: fprintf(ftable,
435: "\n};\n\nstatic const char * const yytname[] = { \"%s\"",
436: tags[0]);
437:
438: j = strlen (tags[0]) + 44;
439: for (i = 1; i <= nsyms; i++)
440: {
441: register char *p;
442: putc(',', ftable);
443: j++;
444:
445: if (j > 75)
446: {
447: putc('\n', ftable);
448: j = 0;
449: }
450:
451: putc ('\"', ftable);
452: j++;
453:
454: for (p = tags[i]; p && *p; p++)
455: {
456: if (*p == '"' || *p == '\\')
457: {
458: fprintf(ftable, "\\%c", *p);
459: j += 2;
460: }
461: else if (*p == '\n')
462: {
463: fprintf(ftable, "\\n");
464: j += 2;
465: }
466: else if (*p == '\t')
467: {
468: fprintf(ftable, "\\t");
469: j += 2;
470: }
471: else if (*p == '\b')
472: {
473: fprintf(ftable, "\\b");
474: j += 2;
475: }
476: else if (*p < 040 || *p >= 0177)
477: {
478: fprintf(ftable, "\\%03o", *p);
479: j += 4;
480: }
481: else
482: {
483: putc(*p, ftable);
484: j++;
485: }
486: }
487:
488: putc ('\"', ftable);
489: j++;
490: }
491:
492: fprintf(ftable, "\n};\n#endif\n\nstatic const short yyr1[] = { 0");
493:
494: j = 10;
495: for (i = 1; i <= nrules; i++)
496: {
497: putc(',', ftable);
498:
499: if (j >= 10)
500: {
501: putc('\n', ftable);
502: j = 1;
503: }
504: else
505: {
506: j++;
507: }
508:
509: fprintf(ftable, "%6d", rlhs[i]);
510: }
511:
512: FREE(rlhs + 1);
513:
514: fprintf(ftable, "\n};\n\nstatic const short yyr2[] = { 0");
515:
516: j = 10;
517: for (i = 1; i < nrules; i++)
518: {
519: putc(',', ftable);
520:
521: if (j >= 10)
522: {
523: putc('\n', ftable);
524: j = 1;
525: }
526: else
527: {
528: j++;
529: }
530:
531: fprintf(ftable, "%6d", rrhs[i + 1] - rrhs[i] - 1);
532: }
533:
534: putc(',', ftable);
535: if (j >= 10)
536: putc('\n', ftable);
537:
538: fprintf(ftable, "%6d\n};\n", nitems - rrhs[nrules] - 1);
539: FREE(rrhs + 1);
540: }
541:
542:
543: void
544: output_defines()
545: {
546: fprintf(ftable, "\n\n#define\tYYFINAL\t\t%d\n", final_state);
547: fprintf(ftable, "#define\tYYFLAG\t\t%d\n", MINSHORT);
548: fprintf(ftable, "#define\tYYNTBASE\t%d\n", ntokens);
549: }
550:
551:
552:
553: /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable and yycheck. */
554:
555: void
556: output_actions()
557: {
558: nvectors = nstates + nvars;
559:
560: froms = NEW2(nvectors, short *);
561: tos = NEW2(nvectors, short *);
562: tally = NEW2(nvectors, short);
563: width = NEW2(nvectors, short);
564:
565: token_actions();
566: free_shifts();
567: free_reductions();
568: FREE(lookaheads);
569: FREE(LA);
570: FREE(LAruleno);
571: FREE(accessing_symbol);
572:
573: goto_actions();
574: FREE(goto_map + ntokens);
575: FREE(from_state);
576: FREE(to_state);
577:
578: sort_actions();
579: pack_table();
580: output_base();
581: output_table();
582: output_check();
583: }
584:
585:
586:
587: /* figure out the actions for the specified state, indexed by lookahead token type.
588:
589: The yydefact table is output now. The detailed info
590: is saved for putting into yytable later. */
591:
592: void
593: token_actions()
594: {
595: register int i;
596: register int j;
597: register int k;
598:
599: actrow = NEW2(ntokens, short);
600:
601: k = action_row(0);
602: fprintf(ftable, "\nstatic const short yydefact[] = {%6d", k);
603: save_row(0);
604:
605: j = 10;
606: for (i = 1; i < nstates; i++)
607: {
608: putc(',', ftable);
609:
610: if (j >= 10)
611: {
612: putc('\n', ftable);
613: j = 1;
614: }
615: else
616: {
617: j++;
618: }
619:
620: k = action_row(i);
621: fprintf(ftable, "%6d", k);
622: save_row(i);
623: }
624:
625: fprintf(ftable, "\n};\n");
626: FREE(actrow);
627: }
628:
629:
630:
631: /* Decide what to do for each type of token if seen as the lookahead token in specified state.
632: The value returned is used as the default action (yydefact) for the state.
633: In addition, actrow is filled with what to do for each kind of token,
634: index by symbol number, with zero meaning do the default action.
635: The value MINSHORT, a very negative number, means this situation
636: is an error. The parser recognizes this value specially.
637:
638: This is where conflicts are resolved. The loop over lookahead rules
639: considered lower-numbered rules last, and the last rule considered that likes
640: a token gets to handle it. */
641:
642: int
643: action_row(state)
644: int state;
645: {
646: register int i;
647: register int j;
648: register int k;
649: register int m;
650: register int n;
651: register int count;
652: register int default_rule;
653: register int nreds;
654: register int max;
655: register int rule;
656: register int shift_state;
657: register int symbol;
658: register unsigned mask;
659: register unsigned *wordp;
660: register reductions *redp;
661: register shifts *shiftp;
662: register errs *errp;
663: int nodefault = 0; /* set nonzero to inhibit having any default reduction */
664:
665: for (i = 0; i < ntokens; i++)
666: actrow[i] = 0;
667:
668: default_rule = 0;
669: nreds = 0;
670: redp = reduction_table[state];
671:
672: if (redp)
673: {
674: nreds = redp->nreds;
675:
676: if (nreds >= 1)
677: {
678: /* loop over all the rules available here which require lookahead */
679: m = lookaheads[state];
680: n = lookaheads[state + 1];
681:
682: for (i = n - 1; i >= m; i--)
683: {
684: rule = - LAruleno[i];
685: wordp = LA + i * tokensetsize;
686: mask = 1;
687:
688: /* and find each token which the rule finds acceptable to come next */
689: for (j = 0; j < ntokens; j++)
690: {
691: /* and record this rule as the rule to use if that token follows. */
692: if (mask & *wordp)
693: actrow[j] = rule;
694:
695: mask <<= 1;
696: if (mask == 0)
697: {
698: mask = 1;
699: wordp++;
700: }
701: }
702: }
703: }
704: }
705:
706: shiftp = shift_table[state];
707:
708: /* now see which tokens are allowed for shifts in this state.
709: For them, record the shift as the thing to do. So shift is preferred to reduce. */
710:
711: if (shiftp)
712: {
713: k = shiftp->nshifts;
714:
715: for (i = 0; i < k; i++)
716: {
717: shift_state = shiftp->shifts[i];
718: if (! shift_state) continue;
719:
720: symbol = accessing_symbol[shift_state];
721:
722: if (ISVAR(symbol))
723: break;
724:
725: actrow[symbol] = shift_state;
726:
727: /* do not use any default reduction if there is a shift for error */
728:
729: if (symbol == error_token_number) nodefault = 1;
730: }
731: }
732:
733: errp = err_table[state];
734:
735: /* See which tokens are an explicit error in this state
736: (due to %nonassoc). For them, record MINSHORT as the action. */
737:
738: if (errp)
739: {
740: k = errp->nerrs;
741:
742: for (i = 0; i < k; i++)
743: {
744: symbol = errp->errs[i];
745: actrow[symbol] = MINSHORT;
746: }
747: }
748:
749: /* now find the most common reduction and make it the default action for this state. */
750:
751: if (nreds >= 1 && ! nodefault)
752: {
753: if (consistent[state])
754: default_rule = redp->rules[0];
755: else
756: {
757: max = 0;
758: for (i = m; i < n; i++)
759: {
760: count = 0;
761: rule = - LAruleno[i];
762:
763: for (j = 0; j < ntokens; j++)
764: {
765: if (actrow[j] == rule)
766: count++;
767: }
768:
769: if (count > max)
770: {
771: max = count;
772: default_rule = rule;
773: }
774: }
775:
776: /* actions which match the default are replaced with zero,
777: which means "use the default" */
778:
779: if (max > 0)
780: {
781: for (j = 0; j < ntokens; j++)
782: {
783: if (actrow[j] == default_rule)
784: actrow[j] = 0;
785: }
786:
787: default_rule = - default_rule;
788: }
789: }
790: }
791:
792: /* If have no default rule, the default is an error.
793: So replace any action which says "error" with "use default". */
794:
795: if (default_rule == 0)
796: for (j = 0; j < ntokens; j++)
797: {
798: if (actrow[j] == MINSHORT)
799: actrow[j] = 0;
800: }
801:
802: return (default_rule);
803: }
804:
805:
806: void
807: save_row(state)
808: int state;
809: {
810: register int i;
811: register int count;
812: register short *sp;
813: register short *sp1;
814: register short *sp2;
815:
816: count = 0;
817: for (i = 0; i < ntokens; i++)
818: {
819: if (actrow[i] != 0)
820: count++;
821: }
822:
823: if (count == 0)
824: return;
825:
826: froms[state] = sp1 = sp = NEW2(count, short);
827: tos[state] = sp2 = NEW2(count, short);
828:
829: for (i = 0; i < ntokens; i++)
830: {
831: if (actrow[i] != 0)
832: {
833: *sp1++ = i;
834: *sp2++ = actrow[i];
835: }
836: }
837:
838: tally[state] = count;
839: width[state] = sp1[-1] - sp[0] + 1;
840: }
841:
842:
843:
844: /* figure out what to do after reducing with each rule,
845: depending on the saved state from before the beginning
846: of parsing the data that matched this rule.
847:
848: The yydefgoto table is output now. The detailed info
849: is saved for putting into yytable later. */
850:
851: void
852: goto_actions()
853: {
854: register int i;
855: register int j;
856: register int k;
857:
858: state_count = NEW2(nstates, short);
859:
860: k = default_goto(ntokens);
861: fprintf(ftable, "\nstatic const short yydefgoto[] = {%6d", k);
862: save_column(ntokens, k);
863:
864: j = 10;
865: for (i = ntokens + 1; i < nsyms; i++)
866: {
867: putc(',', ftable);
868:
869: if (j >= 10)
870: {
871: putc('\n', ftable);
872: j = 1;
873: }
874: else
875: {
876: j++;
877: }
878:
879: k = default_goto(i);
880: fprintf(ftable, "%6d", k);
881: save_column(i, k);
882: }
883:
884: fprintf(ftable, "\n};\n");
885: FREE(state_count);
886: }
887:
888:
889:
890: int
891: default_goto(symbol)
892: int symbol;
893: {
894: register int i;
895: register int m;
896: register int n;
897: register int default_state;
898: register int max;
899:
900: m = goto_map[symbol];
901: n = goto_map[symbol + 1];
902:
903: if (m == n)
904: return (-1);
905:
906: for (i = 0; i < nstates; i++)
907: state_count[i] = 0;
908:
909: for (i = m; i < n; i++)
910: state_count[to_state[i]]++;
911:
912: max = 0;
913: default_state = -1;
914:
915: for (i = 0; i < nstates; i++)
916: {
917: if (state_count[i] > max)
918: {
919: max = state_count[i];
920: default_state = i;
921: }
922: }
923:
924: return (default_state);
925: }
926:
927:
928: void
929: save_column(symbol, default_state)
930: int symbol;
931: int default_state;
932: {
933: register int i;
934: register int m;
935: register int n;
936: register short *sp;
937: register short *sp1;
938: register short *sp2;
939: register int count;
940: register int symno;
941:
942: m = goto_map[symbol];
943: n = goto_map[symbol + 1];
944:
945: count = 0;
946: for (i = m; i < n; i++)
947: {
948: if (to_state[i] != default_state)
949: count++;
950: }
951:
952: if (count == 0)
953: return;
954:
955: symno = symbol - ntokens + nstates;
956:
957: froms[symno] = sp1 = sp = NEW2(count, short);
958: tos[symno] = sp2 = NEW2(count, short);
959:
960: for (i = m; i < n; i++)
961: {
962: if (to_state[i] != default_state)
963: {
964: *sp1++ = from_state[i];
965: *sp2++ = to_state[i];
966: }
967: }
968:
969: tally[symno] = count;
970: width[symno] = sp1[-1] - sp[0] + 1;
971: }
972:
973:
974:
975: /* the next few functions decide how to pack
976: the actions and gotos information into yytable. */
977:
978: void
979: sort_actions()
980: {
981: register int i;
982: register int j;
983: register int k;
984: register int t;
985: register int w;
986:
987: order = NEW2(nvectors, short);
988: nentries = 0;
989:
990: for (i = 0; i < nvectors; i++)
991: {
992: if (tally[i] > 0)
993: {
994: t = tally[i];
995: w = width[i];
996: j = nentries - 1;
997:
998: while (j >= 0 && (width[order[j]] < w))
999: j--;
1000:
1001: while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
1002: j--;
1003:
1004: for (k = nentries - 1; k > j; k--)
1005: order[k + 1] = order[k];
1006:
1007: order[j + 1] = i;
1008: nentries++;
1009: }
1010: }
1011: }
1012:
1013:
1014: void
1015: pack_table()
1016: {
1017: register int i;
1018: register int place;
1019: register int state;
1020:
1021: base = NEW2(nvectors, short);
1022: pos = NEW2(nentries, short);
1023: table = NEW2(MAXTABLE, short);
1024: check = NEW2(MAXTABLE, short);
1025:
1026: lowzero = 0;
1027: high = 0;
1028:
1029: for (i = 0; i < nvectors; i++)
1030: base[i] = MINSHORT;
1031:
1032: for (i = 0; i < MAXTABLE; i++)
1033: check[i] = -1;
1034:
1035: for (i = 0; i < nentries; i++)
1036: {
1037: state = matching_state(i);
1038:
1039: if (state < 0)
1040: place = pack_vector(i);
1041: else
1042: place = base[state];
1043:
1044: pos[i] = place;
1045: base[order[i]] = place;
1046: }
1047:
1048: for (i = 0; i < nvectors; i++)
1049: {
1050: if (froms[i])
1051: FREE(froms[i]);
1052: if (tos[i])
1053: FREE(tos[i]);
1054: }
1055:
1056: FREE(froms);
1057: FREE(tos);
1058: FREE(pos);
1059: }
1060:
1061:
1062:
1063: int
1064: matching_state(vector)
1065: int vector;
1066: {
1067: register int i;
1068: register int j;
1069: register int k;
1070: register int t;
1071: register int w;
1072: register int match;
1073: register int prev;
1074:
1075: i = order[vector];
1076: if (i >= nstates)
1077: return (-1);
1078:
1079: t = tally[i];
1080: w = width[i];
1081:
1082: for (prev = vector - 1; prev >= 0; prev--)
1083: {
1084: j = order[prev];
1085: if (width[j] != w || tally[j] != t)
1086: return (-1);
1087:
1088: match = 1;
1089: for (k = 0; match && k < t; k++)
1090: {
1091: if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
1092: match = 0;
1093: }
1094:
1095: if (match)
1096: return (j);
1097: }
1098:
1099: return (-1);
1100: }
1101:
1102:
1103:
1104: int
1105: pack_vector(vector)
1106: int vector;
1107: {
1108: register int i;
1109: register int j;
1110: register int k;
1111: register int t;
1112: register int loc;
1113: register int ok;
1114: register short *from;
1115: register short *to;
1116:
1117: i = order[vector];
1118: t = tally[i];
1119:
1120: if (t == 0)
1121: berror("pack_vector");
1122:
1123: from = froms[i];
1124: to = tos[i];
1125:
1126: for (j = lowzero - from[0]; j < MAXTABLE; j++)
1127: {
1128: ok = 1;
1129:
1130: for (k = 0; ok && k < t; k++)
1131: {
1132: loc = j + from[k];
1133: if (loc > MAXTABLE)
1134: fatals("maximum table size (%d) exceeded",MAXTABLE);
1135:
1136: if (table[loc] != 0)
1137: ok = 0;
1138: }
1139:
1140: for (k = 0; ok && k < vector; k++)
1141: {
1142: if (pos[k] == j)
1143: ok = 0;
1144: }
1145:
1146: if (ok)
1147: {
1148: for (k = 0; k < t; k++)
1149: {
1150: loc = j + from[k];
1151: table[loc] = to[k];
1152: check[loc] = from[k];
1153: }
1154:
1155: while (table[lowzero] != 0)
1156: lowzero++;
1157:
1158: if (loc > high)
1159: high = loc;
1160:
1161: return (j);
1162: }
1163: }
1164:
1165: berror("pack_vector");
1166: return 0; /* JF keep lint happy */
1167: }
1168:
1169:
1170:
1171: /* the following functions output yytable, yycheck
1172: and the vectors whose elements index the portion starts */
1173:
1174: void
1175: output_base()
1176: {
1177: register int i;
1178: register int j;
1179:
1180: fprintf(ftable, "\nstatic const short yypact[] = {%6d", base[0]);
1181:
1182: j = 10;
1183: for (i = 1; i < nstates; i++)
1184: {
1185: putc(',', ftable);
1186:
1187: if (j >= 10)
1188: {
1189: putc('\n', ftable);
1190: j = 1;
1191: }
1192: else
1193: {
1194: j++;
1195: }
1196:
1197: fprintf(ftable, "%6d", base[i]);
1198: }
1199:
1200: fprintf(ftable, "\n};\n\nstatic const short yypgoto[] = {%6d", base[nstates]);
1201:
1202: j = 10;
1203: for (i = nstates + 1; i < nvectors; i++)
1204: {
1205: putc(',', ftable);
1206:
1207: if (j >= 10)
1208: {
1209: putc('\n', ftable);
1210: j = 1;
1211: }
1212: else
1213: {
1214: j++;
1215: }
1216:
1217: fprintf(ftable, "%6d", base[i]);
1218: }
1219:
1220: fprintf(ftable, "\n};\n");
1221: FREE(base);
1222: }
1223:
1224:
1225: void
1226: output_table()
1227: {
1228: register int i;
1229: register int j;
1230:
1231: fprintf(ftable, "\n\n#define\tYYLAST\t\t%d\n\n", high);
1232: fprintf(ftable, "\nstatic const short yytable[] = {%6d", table[0]);
1233:
1234: j = 10;
1235: for (i = 1; i <= high; i++)
1236: {
1237: putc(',', ftable);
1238:
1239: if (j >= 10)
1240: {
1241: putc('\n', ftable);
1242: j = 1;
1243: }
1244: else
1245: {
1246: j++;
1247: }
1248:
1249: fprintf(ftable, "%6d", table[i]);
1250: }
1251:
1252: fprintf(ftable, "\n};\n");
1253: FREE(table);
1254: }
1255:
1256:
1257: void
1258: output_check()
1259: {
1260: register int i;
1261: register int j;
1262:
1263: fprintf(ftable, "\nstatic const short yycheck[] = {%6d", check[0]);
1264:
1265: j = 10;
1266: for (i = 1; i <= high; i++)
1267: {
1268: putc(',', ftable);
1269:
1270: if (j >= 10)
1271: {
1272: putc('\n', ftable);
1273: j = 1;
1274: }
1275: else
1276: {
1277: j++;
1278: }
1279:
1280: fprintf(ftable, "%6d", check[i]);
1281: }
1282:
1283: fprintf(ftable, "\n};\n");
1284: FREE(check);
1285: }
1286:
1287:
1288:
1289: /* copy the parser code into the ftable file at the end. */
1290:
1291: void
1292: output_parser()
1293: {
1294: register int c;
1295: #ifdef DONTDEF
1296: FILE *fpars;
1297: #else
1298: #define fpars fparser
1299: #endif
1300:
1301: if (pure_parser)
1302: fprintf(ftable, "#define YYPURE 1\n\n");
1303:
1304: #ifdef DONTDEF /* JF no longer needed 'cuz open_extra_files changes the
1305: currently open parser from bison.simple to bison.hairy */
1306: if (semantic_parser)
1307: fpars = fparser;
1308: else fpars = fparser1;
1309: #endif
1310:
1311: /* Loop over lines in the standard parser file. */
1312:
1313: while (1)
1314: {
1315: int write_line = 1;
1316:
1317: c = getc(fpars);
1318:
1319: /* See if the line starts with `#line.
1320: If so, set write_line to 0. */
1321: if (nolinesflag)
1322: if (c == '#')
1323: {
1324: c = getc(fpars);
1325: if (c == 'l')
1326: {
1327: c = getc(fpars);
1328: if (c == 'i')
1329: {
1330: c = getc(fpars);
1331: if (c == 'n')
1332: {
1333: c = getc(fpars);
1334: if (c == 'e')
1335: write_line = 0;
1336: else
1337: fprintf(ftable, "#lin");
1338: }
1339: else
1340: fprintf(ftable, "#li");
1341: }
1342: else
1343: fprintf(ftable, "#l");
1344: }
1345: else
1346: fprintf(ftable, "#");
1347: }
1348:
1349: /* now write out the line... */
1350: for ( ; c != '\n' && c != EOF; c = getc(fpars))
1351: if (write_line)
1352: if (c == '$')
1353: {
1354: /* `$' in the parser file indicates where to put the actions.
1355: Copy them in at this point. */
1356: rewind(faction);
1357: for(c=getc(faction);c!=EOF;c=getc(faction))
1358: putc(c,ftable);
1359: }
1360: else
1361: putc(c, ftable);
1362: if (c == EOF)
1363: break;
1364: putc(c, ftable);
1365: }
1366: }
1367:
1368:
1369: void
1370: output_program()
1371: {
1372: register int c;
1373: extern int lineno;
1374:
1375: if (!nolinesflag)
1376: fprintf(ftable, "#line %d \"%s\"\n", lineno, infile);
1377:
1378: c = getc(finput);
1379: while (c != EOF)
1380: {
1381: putc(c, ftable);
1382: c = getc(finput);
1383: }
1384: }
1385:
1386:
1387: void
1388: free_itemsets()
1389: {
1390: register core *cp,*cptmp;
1391:
1392: FREE(state_table);
1393:
1394: for (cp = first_state; cp; cp = cptmp) {
1395: cptmp=cp->next;
1396: FREE(cp);
1397: }
1398: }
1399:
1400:
1401: void
1402: free_shifts()
1403: {
1404: register shifts *sp,*sptmp;/* JF derefrenced freed ptr */
1405:
1406: FREE(shift_table);
1407:
1408: for (sp = first_shift; sp; sp = sptmp) {
1409: sptmp=sp->next;
1410: FREE(sp);
1411: }
1412: }
1413:
1414:
1415: void
1416: free_reductions()
1417: {
1418: register reductions *rp,*rptmp;/* JF fixed freed ptr */
1419:
1420: FREE(reduction_table);
1421:
1422: for (rp = first_reduction; rp; rp = rptmp) {
1423: rptmp=rp->next;
1424: FREE(rp);
1425: }
1426: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.