fatbase

portable OpenBSD tools
git clone git://git.2f30.org/fatbase
Log | Files | Refs

reader.c (32959B)


      1 /* $OpenBSD: reader.c,v 1.29 2014/10/09 03:02:18 deraadt Exp $	 */
      2 /* $NetBSD: reader.c,v 1.5 1996/03/19 03:21:43 jtc Exp $	 */
      3 
      4 /*
      5  * Copyright (c) 1989 The Regents of the University of California.
      6  * All rights reserved.
      7  *
      8  * This code is derived from software contributed to Berkeley by
      9  * Robert Paul Corbett.
     10  *
     11  * Redistribution and use in source and binary forms, with or without
     12  * modification, are permitted provided that the following conditions
     13  * are met:
     14  * 1. Redistributions of source code must retain the above copyright
     15  *    notice, this list of conditions and the following disclaimer.
     16  * 2. Redistributions in binary form must reproduce the above copyright
     17  *    notice, this list of conditions and the following disclaimer in the
     18  *    documentation and/or other materials provided with the distribution.
     19  * 3. Neither the name of the University nor the names of its contributors
     20  *    may be used to endorse or promote products derived from this software
     21  *    without specific prior written permission.
     22  *
     23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     33  * SUCH DAMAGE.
     34  */
     35 
     36 #include "defs.h"
     37 #include "util.h"
     38 
     39 /* The line size must be a positive integer.  One hundred was chosen	 */
     40 /* because few lines in Yacc input grammars exceed 100 characters.	 */
     41 /* Note that if a line exceeds LINESIZE characters, the line buffer	 */
     42 /* will be expanded to accommodate it.					 */
     43 
     44 #define LINESIZE 100
     45 
     46 char *cache;
     47 int cinc, cache_size;
     48 
     49 int ntags, tagmax;
     50 char **tag_table;
     51 
     52 char saw_eof, unionized;
     53 char *cptr, *line;
     54 int linesize;
     55 
     56 bucket *goal;
     57 int prec;
     58 int gensym;
     59 char last_was_action;
     60 
     61 int maxitems;
     62 bucket **pitem;
     63 
     64 int maxrules;
     65 bucket **plhs;
     66 
     67 int name_pool_size;
     68 char *name_pool;
     69 
     70 void cachec(int);
     71 void get_line(void);
     72 char *dup_line(void);
     73 void skip_comment(void);
     74 int nextc(void);
     75 int keyword(void);
     76 void copy_ident(void);
     77 void copy_text(void);
     78 void copy_union(void);
     79 bucket *get_literal(void);
     80 int is_reserved(char *);
     81 bucket *get_name(void);
     82 int get_number(void);
     83 char *get_tag(void);
     84 void declare_tokens(int);
     85 void declare_types(void);
     86 void declare_start(void);
     87 void handle_expect(void);
     88 void read_declarations(void);
     89 void initialize_grammar(void);
     90 void expand_items(void);
     91 void expand_rules(void);
     92 void advance_to_start(void);
     93 void start_rule(bucket *, int);
     94 void end_rule(void);
     95 void insert_empty_rule(void);
     96 void add_symbol(void);
     97 void copy_action(void);
     98 int mark_symbol(void);
     99 void read_grammar(void);
    100 void free_tags(void);
    101 void pack_names(void);
    102 void check_symbols(void);
    103 void pack_symbols(void);
    104 void pack_grammar(void);
    105 void print_grammar(void);
    106 
    107 char line_format[] = "#line %d \"%s\"\n";
    108 
    109 void
    110 cachec(int c)
    111 {
    112 	assert(cinc >= 0);
    113 	if (cinc >= cache_size) {
    114 		cache_size += 256;
    115 		cache = realloc(cache, cache_size);
    116 		if (cache == NULL)
    117 			no_space();
    118 	}
    119 	cache[cinc] = c;
    120 	++cinc;
    121 }
    122 
    123 
    124 void
    125 get_line(void)
    126 {
    127 	FILE *f = input_file;
    128 	int c, i;
    129 
    130 	if (saw_eof || (c = getc(f)) == EOF) {
    131 		if (line) {
    132 			free(line);
    133 			line = 0;
    134 		}
    135 		cptr = 0;
    136 		saw_eof = 1;
    137 		return;
    138 	}
    139 	if (line == NULL || linesize != (LINESIZE + 1)) {
    140 		if (line)
    141 			free(line);
    142 		linesize = LINESIZE + 1;
    143 		line = malloc(linesize);
    144 		if (line == NULL)
    145 			no_space();
    146 	}
    147 	i = 0;
    148 	++lineno;
    149 	for (;;) {
    150 		line[i] = c;
    151 		if (c == '\n') {
    152 			cptr = line;
    153 			return;
    154 		}
    155 		if (++i >= linesize) {
    156 			linesize += LINESIZE;
    157 			line = realloc(line, linesize);
    158 			if (line == NULL)
    159 				no_space();
    160 		}
    161 		c = getc(f);
    162 		if (c == EOF) {
    163 			line[i] = '\n';
    164 			saw_eof = 1;
    165 			cptr = line;
    166 			return;
    167 		}
    168 	}
    169 }
    170 
    171 
    172 char *
    173 dup_line(void)
    174 {
    175 	char *p, *s, *t;
    176 
    177 	if (line == NULL)
    178 		return (0);
    179 	s = line;
    180 	while (*s != '\n')
    181 		++s;
    182 	p = malloc(s - line + 1);
    183 	if (p == NULL)
    184 		no_space();
    185 
    186 	s = line;
    187 	t = p;
    188 	while ((*t++ = *s++) != '\n')
    189 		continue;
    190 	return (p);
    191 }
    192 
    193 
    194 void
    195 skip_comment(void)
    196 {
    197 	char *s;
    198 	int st_lineno = lineno;
    199 	char *st_line = dup_line();
    200 	char *st_cptr = st_line + (cptr - line);
    201 
    202 	s = cptr + 2;
    203 	for (;;) {
    204 		if (*s == '*' && s[1] == '/') {
    205 			cptr = s + 2;
    206 			free(st_line);
    207 			return;
    208 		}
    209 		if (*s == '\n') {
    210 			get_line();
    211 			if (line == NULL)
    212 				unterminated_comment(st_lineno, st_line, st_cptr);
    213 			s = cptr;
    214 		} else
    215 			++s;
    216 	}
    217 }
    218 
    219 
    220 int
    221 nextc(void)
    222 {
    223 	char *s;
    224 
    225 	if (line == NULL) {
    226 		get_line();
    227 		if (line == NULL)
    228 			return (EOF);
    229 	}
    230 	s = cptr;
    231 	for (;;) {
    232 		switch (*s) {
    233 		case '\n':
    234 			get_line();
    235 			if (line == NULL)
    236 				return (EOF);
    237 			s = cptr;
    238 			break;
    239 
    240 		case ' ':
    241 		case '\t':
    242 		case '\f':
    243 		case '\r':
    244 		case '\v':
    245 		case ',':
    246 		case ';':
    247 			++s;
    248 			break;
    249 
    250 		case '\\':
    251 			cptr = s;
    252 			return ('%');
    253 
    254 		case '/':
    255 			if (s[1] == '*') {
    256 				cptr = s;
    257 				skip_comment();
    258 				s = cptr;
    259 				break;
    260 			} else if (s[1] == '/') {
    261 				get_line();
    262 				if (line == NULL)
    263 					return (EOF);
    264 				s = cptr;
    265 				break;
    266 			}
    267 			/* fall through */
    268 
    269 		default:
    270 			cptr = s;
    271 			return ((unsigned char) *s);
    272 		}
    273 	}
    274 }
    275 
    276 
    277 int
    278 keyword(void)
    279 {
    280 	int c;
    281 	char *t_cptr = cptr;
    282 
    283 	c = (unsigned char) *++cptr;
    284 	if (isalpha(c)) {
    285 		cinc = 0;
    286 		for (;;) {
    287 			if (isalpha(c)) {
    288 				if (isupper(c))
    289 					c = tolower(c);
    290 				cachec(c);
    291 			} else if (isdigit(c) || c == '_' || c == '.' || c == '$')
    292 				cachec(c);
    293 			else
    294 				break;
    295 			c = (unsigned char) *++cptr;
    296 		}
    297 		cachec(NUL);
    298 
    299 		if (strcmp(cache, "token") == 0 || strcmp(cache, "term") == 0)
    300 			return (TOKEN);
    301 		if (strcmp(cache, "type") == 0)
    302 			return (TYPE);
    303 		if (strcmp(cache, "left") == 0)
    304 			return (LEFT);
    305 		if (strcmp(cache, "right") == 0)
    306 			return (RIGHT);
    307 		if (strcmp(cache, "nonassoc") == 0 || strcmp(cache, "binary") == 0)
    308 			return (NONASSOC);
    309 		if (strcmp(cache, "start") == 0)
    310 			return (START);
    311 		if (strcmp(cache, "union") == 0)
    312 			return (UNION);
    313 		if (strcmp(cache, "ident") == 0)
    314 			return (IDENT);
    315 		if (strcmp(cache, "expect") == 0)
    316 			return (EXPECT);
    317 	} else {
    318 		++cptr;
    319 		if (c == '{')
    320 			return (TEXT);
    321 		if (c == '%' || c == '\\')
    322 			return (MARK);
    323 		if (c == '<')
    324 			return (LEFT);
    325 		if (c == '>')
    326 			return (RIGHT);
    327 		if (c == '0')
    328 			return (TOKEN);
    329 		if (c == '2')
    330 			return (NONASSOC);
    331 	}
    332 	syntax_error(lineno, line, t_cptr);
    333 	/* NOTREACHED */
    334 	return (0);
    335 }
    336 
    337 
    338 void
    339 copy_ident(void)
    340 {
    341 	int c;
    342 	FILE *f = output_file;
    343 
    344 	c = nextc();
    345 	if (c == EOF)
    346 		unexpected_EOF();
    347 	if (c != '"')
    348 		syntax_error(lineno, line, cptr);
    349 	++outline;
    350 	fprintf(f, "#ident \"");
    351 	for (;;) {
    352 		c = (unsigned char) *++cptr;
    353 		if (c == '\n') {
    354 			fprintf(f, "\"\n");
    355 			return;
    356 		}
    357 		putc(c, f);
    358 		if (c == '"') {
    359 			putc('\n', f);
    360 			++cptr;
    361 			return;
    362 		}
    363 	}
    364 }
    365 
    366 
    367 void
    368 copy_text(void)
    369 {
    370 	int c;
    371 	int quote;
    372 	FILE *f = text_file;
    373 	int need_newline = 0;
    374 	int t_lineno = lineno;
    375 	char *t_line = dup_line();
    376 	char *t_cptr = t_line + (cptr - line - 2);
    377 
    378 	if (*cptr == '\n') {
    379 		get_line();
    380 		if (line == NULL)
    381 			unterminated_text(t_lineno, t_line, t_cptr);
    382 	}
    383 	if (!lflag)
    384 		fprintf(f, line_format, lineno, input_file_name);
    385 
    386 loop:
    387 	c = (unsigned char) *cptr++;
    388 	switch (c) {
    389 	case '\n':
    390 next_line:
    391 		putc('\n', f);
    392 		need_newline = 0;
    393 		get_line();
    394 		if (line)
    395 			goto loop;
    396 		unterminated_text(t_lineno, t_line, t_cptr);
    397 
    398 	case '\'':
    399 	case '"': {
    400 		int s_lineno = lineno;
    401 		char *s_line = dup_line();
    402 		char *s_cptr = s_line + (cptr - line - 1);
    403 
    404 		quote = c;
    405 		putc(c, f);
    406 		for (;;) {
    407 			c = (unsigned char) *cptr++;
    408 			putc(c, f);
    409 			if (c == quote) {
    410 				need_newline = 1;
    411 				free(s_line);
    412 				goto loop;
    413 			}
    414 			if (c == '\n')
    415 				unterminated_string(s_lineno, s_line, s_cptr);
    416 			if (c == '\\') {
    417 				c = (unsigned char) *cptr++;
    418 				putc(c, f);
    419 				if (c == '\n') {
    420 					get_line();
    421 					if (line == NULL)
    422 						unterminated_string(s_lineno, s_line, s_cptr);
    423 				}
    424 			}
    425 		}
    426 	}
    427 
    428 	case '/':
    429 		putc(c, f);
    430 		need_newline = 1;
    431 		c = (unsigned char) *cptr;
    432 		if (c == '/') {
    433 			putc('*', f);
    434 			while ((c = (unsigned char) *++cptr) != '\n') {
    435 				if (c == '*' && cptr[1] == '/')
    436 					fprintf(f, "* ");
    437 				else
    438 					putc(c, f);
    439 			}
    440 			fprintf(f, "*/");
    441 			goto next_line;
    442 		}
    443 		if (c == '*') {
    444 			int c_lineno = lineno;
    445 			char *c_line = dup_line();
    446 			char *c_cptr = c_line + (cptr - line - 1);
    447 
    448 			putc('*', f);
    449 			++cptr;
    450 			for (;;) {
    451 				c = (unsigned char) *cptr++;
    452 				putc(c, f);
    453 				if (c == '*' && *cptr == '/') {
    454 					putc('/', f);
    455 					++cptr;
    456 					free(c_line);
    457 					goto loop;
    458 				}
    459 				if (c == '\n') {
    460 					get_line();
    461 					if (line == NULL)
    462 						unterminated_comment(c_lineno, c_line, c_cptr);
    463 				}
    464 			}
    465 		}
    466 		need_newline = 1;
    467 		goto loop;
    468 
    469 	case '%':
    470 	case '\\':
    471 		if (*cptr == '}') {
    472 			if (need_newline)
    473 				putc('\n', f);
    474 			++cptr;
    475 			free(t_line);
    476 			return;
    477 		}
    478 		/* fall through */
    479 
    480 	default:
    481 		putc(c, f);
    482 		need_newline = 1;
    483 		goto loop;
    484 	}
    485 }
    486 
    487 
    488 void
    489 copy_union(void)
    490 {
    491 	int c, quote, depth;
    492 	int u_lineno = lineno;
    493 	char *u_line = dup_line();
    494 	char *u_cptr = u_line + (cptr - line - 6);
    495 
    496 	if (unionized)
    497 		over_unionized(cptr - 6);
    498 	unionized = 1;
    499 
    500 	if (!lflag)
    501 		fprintf(text_file, line_format, lineno, input_file_name);
    502 
    503 	fprintf(text_file, "#ifndef YYSTYPE_DEFINED\n");
    504 	fprintf(text_file, "#define YYSTYPE_DEFINED\n");
    505 	fprintf(text_file, "typedef union");
    506 	if (dflag)
    507 		fprintf(union_file, "#ifndef YYSTYPE_DEFINED\n");
    508 	if (dflag)
    509 		fprintf(union_file, "#define YYSTYPE_DEFINED\n");
    510 	if (dflag)
    511 		fprintf(union_file, "typedef union");
    512 
    513 	depth = 0;
    514 loop:
    515 	c = (unsigned char) *cptr++;
    516 	putc(c, text_file);
    517 	if (dflag)
    518 		putc(c, union_file);
    519 	switch (c) {
    520 	case '\n':
    521 next_line:
    522 		get_line();
    523 		if (line == NULL)
    524 			unterminated_union(u_lineno, u_line, u_cptr);
    525 		goto loop;
    526 
    527 	case '{':
    528 		++depth;
    529 		goto loop;
    530 
    531 	case '}':
    532 		if (--depth == 0) {
    533 			fprintf(text_file, " YYSTYPE;\n");
    534 			fprintf(text_file, "#endif /* YYSTYPE_DEFINED */\n");
    535 			free(u_line);
    536 			return;
    537 		}
    538 		goto loop;
    539 
    540 	case '\'':
    541 	case '"': {
    542 		int s_lineno = lineno;
    543 		char *s_line = dup_line();
    544 		char *s_cptr = s_line + (cptr - line - 1);
    545 
    546 		quote = c;
    547 		for (;;) {
    548 			c = (unsigned char) *cptr++;
    549 			putc(c, text_file);
    550 			if (dflag)
    551 				putc(c, union_file);
    552 			if (c == quote) {
    553 				free(s_line);
    554 				goto loop;
    555 			}
    556 			if (c == '\n')
    557 				unterminated_string(s_lineno, s_line, s_cptr);
    558 			if (c == '\\') {
    559 				c = (unsigned char) *cptr++;
    560 				putc(c, text_file);
    561 				if (dflag)
    562 					putc(c, union_file);
    563 				if (c == '\n') {
    564 					get_line();
    565 					if (line == NULL)
    566 						unterminated_string(s_lineno,
    567 						    s_line, s_cptr);
    568 				}
    569 			}
    570 		}
    571 	}
    572 
    573 	case '/':
    574 		c = (unsigned char) *cptr;
    575 		if (c == '/') {
    576 			putc('*', text_file);
    577 			if (dflag)
    578 				putc('*', union_file);
    579 			while ((c = (unsigned char) *++cptr) != '\n') {
    580 				if (c == '*' && cptr[1] == '/') {
    581 					fprintf(text_file, "* ");
    582 					if (dflag)
    583 						fprintf(union_file, "* ");
    584 				} else {
    585 					putc(c, text_file);
    586 					if (dflag)
    587 						putc(c, union_file);
    588 				}
    589 			}
    590 			fprintf(text_file, "*/\n");
    591 			if (dflag)
    592 				fprintf(union_file, "*/\n");
    593 			goto next_line;
    594 		}
    595 		if (c == '*') {
    596 			int c_lineno = lineno;
    597 			char *c_line = dup_line();
    598 			char *c_cptr = c_line + (cptr - line - 1);
    599 
    600 			putc('*', text_file);
    601 			if (dflag)
    602 				putc('*', union_file);
    603 			++cptr;
    604 			for (;;) {
    605 				c = (unsigned char) *cptr++;
    606 				putc(c, text_file);
    607 				if (dflag)
    608 					putc(c, union_file);
    609 				if (c == '*' && *cptr == '/') {
    610 					putc('/', text_file);
    611 					if (dflag)
    612 						putc('/', union_file);
    613 					++cptr;
    614 					free(c_line);
    615 					goto loop;
    616 				}
    617 				if (c == '\n') {
    618 					get_line();
    619 					if (line == NULL)
    620 						unterminated_comment(c_lineno,
    621 						    c_line, c_cptr);
    622 				}
    623 			}
    624 		}
    625 		goto loop;
    626 
    627 	default:
    628 		goto loop;
    629 	}
    630 }
    631 
    632 
    633 bucket *
    634 get_literal(void)
    635 {
    636 	int c, quote, i, n;
    637 	char *s;
    638 	bucket *bp;
    639 	int s_lineno = lineno;
    640 	char *s_line = dup_line();
    641 	char *s_cptr = s_line + (cptr - line);
    642 
    643 	quote = (unsigned char) *cptr++;
    644 	cinc = 0;
    645 	for (;;) {
    646 		c = (unsigned char) *cptr++;
    647 		if (c == quote)
    648 			break;
    649 		if (c == '\n')
    650 			unterminated_string(s_lineno, s_line, s_cptr);
    651 		if (c == '\\') {
    652 			char *c_cptr = cptr - 1;
    653 			unsigned long ulval;
    654 
    655 			c = (unsigned char) *cptr++;
    656 			switch (c) {
    657 			case '\n':
    658 				get_line();
    659 				if (line == NULL)
    660 					unterminated_string(s_lineno, s_line,
    661 					    s_cptr);
    662 				continue;
    663 
    664 			case '0':
    665 			case '1':
    666 			case '2':
    667 			case '3':
    668 			case '4':
    669 			case '5':
    670 			case '6':
    671 			case '7':
    672 				ulval = strtoul(cptr - 1, &s, 8);
    673 				if (s == cptr - 1 || ulval > MAXCHAR)
    674 					illegal_character(c_cptr);
    675 				c = (int) ulval;
    676 				cptr = s;
    677 				break;
    678 
    679 			case 'x':
    680 				ulval = strtoul(cptr, &s, 16);
    681 				if (s == cptr || ulval > MAXCHAR)
    682 					illegal_character(c_cptr);
    683 				c = (int) ulval;
    684 				cptr = s;
    685 				break;
    686 
    687 			case 'a':
    688 				c = 7;
    689 				break;
    690 			case 'b':
    691 				c = '\b';
    692 				break;
    693 			case 'f':
    694 				c = '\f';
    695 				break;
    696 			case 'n':
    697 				c = '\n';
    698 				break;
    699 			case 'r':
    700 				c = '\r';
    701 				break;
    702 			case 't':
    703 				c = '\t';
    704 				break;
    705 			case 'v':
    706 				c = '\v';
    707 				break;
    708 			}
    709 		}
    710 		cachec(c);
    711 	}
    712 	free(s_line);
    713 
    714 	n = cinc;
    715 	s = malloc(n);
    716 	if (s == NULL)
    717 		no_space();
    718 
    719 	memcpy(s, cache, n);
    720 
    721 	cinc = 0;
    722 	if (n == 1)
    723 		cachec('\'');
    724 	else
    725 		cachec('"');
    726 
    727 	for (i = 0; i < n; ++i) {
    728 		c = ((unsigned char *) s)[i];
    729 		if (c == '\\' || c == cache[0]) {
    730 			cachec('\\');
    731 			cachec(c);
    732 		} else if (isprint(c))
    733 			cachec(c);
    734 		else {
    735 			cachec('\\');
    736 			switch (c) {
    737 			case 7:
    738 				cachec('a');
    739 				break;
    740 			case '\b':
    741 				cachec('b');
    742 				break;
    743 			case '\f':
    744 				cachec('f');
    745 				break;
    746 			case '\n':
    747 				cachec('n');
    748 				break;
    749 			case '\r':
    750 				cachec('r');
    751 				break;
    752 			case '\t':
    753 				cachec('t');
    754 				break;
    755 			case '\v':
    756 				cachec('v');
    757 				break;
    758 			default:
    759 				cachec(((c >> 6) & 7) + '0');
    760 				cachec(((c >> 3) & 7) + '0');
    761 				cachec((c & 7) + '0');
    762 				break;
    763 			}
    764 		}
    765 	}
    766 
    767 	if (n == 1)
    768 		cachec('\'');
    769 	else
    770 		cachec('"');
    771 
    772 	cachec(NUL);
    773 	bp = lookup(cache);
    774 	bp->class = TERM;
    775 	if (n == 1 && bp->value == UNDEFINED)
    776 		bp->value = *(unsigned char *) s;
    777 	free(s);
    778 
    779 	return (bp);
    780 }
    781 
    782 
    783 int
    784 is_reserved(char *name)
    785 {
    786 	char *s;
    787 
    788 	if (strcmp(name, ".") == 0 ||
    789 	    strcmp(name, "$accept") == 0 ||
    790 	    strcmp(name, "$end") == 0)
    791 		return (1);
    792 
    793 	if (name[0] == '$' && name[1] == '$' && isdigit((unsigned char) name[2])) {
    794 		s = name + 3;
    795 		while (isdigit((unsigned char) *s))
    796 			++s;
    797 		if (*s == NUL)
    798 			return (1);
    799 	}
    800 	return (0);
    801 }
    802 
    803 
    804 bucket *
    805 get_name(void)
    806 {
    807 	int c;
    808 
    809 	cinc = 0;
    810 	for (c = (unsigned char) *cptr; IS_IDENT(c); c = (unsigned char) *++cptr)
    811 		cachec(c);
    812 	cachec(NUL);
    813 
    814 	if (is_reserved(cache))
    815 		used_reserved(cache);
    816 
    817 	return (lookup(cache));
    818 }
    819 
    820 
    821 int
    822 get_number(void)
    823 {
    824 	int c, n;
    825 
    826 	n = 0;
    827 	for (c = (unsigned char) *cptr; isdigit(c); c = (unsigned char) *++cptr)
    828 		n = 10 * n + (c - '0');
    829 
    830 	return (n);
    831 }
    832 
    833 
    834 char *
    835 get_tag(void)
    836 {
    837 	int c, i;
    838 	char *s;
    839 	int t_lineno = lineno;
    840 	char *t_line = dup_line();
    841 	char *t_cptr = t_line + (cptr - line);
    842 
    843 	++cptr;
    844 	c = nextc();
    845 	if (c == EOF)
    846 		unexpected_EOF();
    847 	if (!isalpha(c) && c != '_' && c != '$')
    848 		illegal_tag(t_lineno, t_line, t_cptr);
    849 
    850 	cinc = 0;
    851 	do {
    852 		cachec(c);
    853 		c = (unsigned char) *++cptr;
    854 	} while (IS_IDENT(c));
    855 	cachec(NUL);
    856 
    857 	c = nextc();
    858 	if (c == EOF)
    859 		unexpected_EOF();
    860 	if (c != '>')
    861 		illegal_tag(t_lineno, t_line, t_cptr);
    862 	free(t_line);
    863 	++cptr;
    864 
    865 	for (i = 0; i < ntags; ++i) {
    866 		if (strcmp(cache, tag_table[i]) == 0)
    867 			return (tag_table[i]);
    868 	}
    869 
    870 	if (ntags >= tagmax) {
    871 		tagmax += 16;
    872 		tag_table = reallocarray(tag_table, tagmax, sizeof(char *));
    873 		if (tag_table == NULL)
    874 			no_space();
    875 	}
    876 	s = malloc(cinc);
    877 	if (s == NULL)
    878 		no_space();
    879 	strlcpy(s, cache, cinc);
    880 	tag_table[ntags] = s;
    881 	++ntags;
    882 	return (s);
    883 }
    884 
    885 
    886 void
    887 declare_tokens(int assoc)
    888 {
    889 	int c;
    890 	bucket *bp;
    891 	int value;
    892 	char *tag = 0;
    893 
    894 	if (assoc != TOKEN)
    895 		++prec;
    896 
    897 	c = nextc();
    898 	if (c == EOF)
    899 		unexpected_EOF();
    900 	if (c == '<') {
    901 		tag = get_tag();
    902 		c = nextc();
    903 		if (c == EOF)
    904 			unexpected_EOF();
    905 	}
    906 	for (;;) {
    907 		if (isalpha(c) || c == '_' || c == '.' || c == '$')
    908 			bp = get_name();
    909 		else if (c == '\'' || c == '"')
    910 			bp = get_literal();
    911 		else
    912 			return;
    913 
    914 		if (bp == goal)
    915 			tokenized_start(bp->name);
    916 		bp->class = TERM;
    917 
    918 		if (tag) {
    919 			if (bp->tag && tag != bp->tag)
    920 				retyped_warning(bp->name);
    921 			bp->tag = tag;
    922 		}
    923 		if (assoc != TOKEN) {
    924 			if (bp->prec && prec != bp->prec)
    925 				reprec_warning(bp->name);
    926 			bp->assoc = assoc;
    927 			bp->prec = prec;
    928 		}
    929 		c = nextc();
    930 		if (c == EOF)
    931 			unexpected_EOF();
    932 		value = UNDEFINED;
    933 		if (isdigit(c)) {
    934 			value = get_number();
    935 			if (bp->value != UNDEFINED && value != bp->value)
    936 				revalued_warning(bp->name);
    937 			bp->value = value;
    938 			c = nextc();
    939 			if (c == EOF)
    940 				unexpected_EOF();
    941 		}
    942 	}
    943 }
    944 
    945 
    946 /*
    947  * %expect requires special handling as it really isn't part of the yacc
    948  * grammar only a flag for yacc proper.
    949  */
    950 void
    951 declare_expect(int assoc)
    952 {
    953 	int c;
    954 
    955 	if (assoc != EXPECT)
    956 		++prec;
    957 
    958 	/*
    959          * Stay away from nextc - doesn't detect EOL and will read to EOF.
    960          */
    961 	c = (unsigned char) *++cptr;
    962 	if (c == EOF)
    963 		unexpected_EOF();
    964 
    965 	for (;;) {
    966 		if (isdigit(c)) {
    967 			SRexpect = get_number();
    968 			break;
    969 		}
    970 		/*
    971 	         * Looking for number before EOL.
    972 	         * Spaces, tabs, and numbers are ok.
    973 	         * Words, punc., etc. are syntax errors.
    974 	         */
    975 		else if (c == '\n' || isalpha(c) || !isspace(c)) {
    976 			syntax_error(lineno, line, cptr);
    977 		} else {
    978 			c = (unsigned char) *++cptr;
    979 			if (c == EOF)
    980 				unexpected_EOF();
    981 		}
    982 	}
    983 }
    984 
    985 
    986 void
    987 declare_types(void)
    988 {
    989 	int c;
    990 	bucket *bp;
    991 	char *tag;
    992 
    993 	c = nextc();
    994 	if (c == EOF)
    995 		unexpected_EOF();
    996 	if (c != '<')
    997 		syntax_error(lineno, line, cptr);
    998 	tag = get_tag();
    999 
   1000 	for (;;) {
   1001 		c = nextc();
   1002 		if (isalpha(c) || c == '_' || c == '.' || c == '$')
   1003 			bp = get_name();
   1004 		else if (c == '\'' || c == '"')
   1005 			bp = get_literal();
   1006 		else
   1007 			return;
   1008 
   1009 		if (bp->tag && tag != bp->tag)
   1010 			retyped_warning(bp->name);
   1011 		bp->tag = tag;
   1012 	}
   1013 }
   1014 
   1015 
   1016 void
   1017 declare_start(void)
   1018 {
   1019 	int c;
   1020 	bucket *bp;
   1021 
   1022 	c = nextc();
   1023 	if (c == EOF)
   1024 		unexpected_EOF();
   1025 	if (!isalpha(c) && c != '_' && c != '.' && c != '$')
   1026 		syntax_error(lineno, line, cptr);
   1027 	bp = get_name();
   1028 	if (bp->class == TERM)
   1029 		terminal_start(bp->name);
   1030 	if (goal && goal != bp)
   1031 		restarted_warning();
   1032 	goal = bp;
   1033 }
   1034 
   1035 
   1036 void
   1037 read_declarations(void)
   1038 {
   1039 	int c, k;
   1040 
   1041 	cache_size = 256;
   1042 	cache = malloc(cache_size);
   1043 	if (cache == NULL)
   1044 		no_space();
   1045 
   1046 	for (;;) {
   1047 		c = nextc();
   1048 		if (c == EOF)
   1049 			unexpected_EOF();
   1050 		if (c != '%')
   1051 			syntax_error(lineno, line, cptr);
   1052 		switch (k = keyword()) {
   1053 		case MARK:
   1054 			return;
   1055 
   1056 		case IDENT:
   1057 			copy_ident();
   1058 			break;
   1059 
   1060 		case TEXT:
   1061 			copy_text();
   1062 			break;
   1063 
   1064 		case UNION:
   1065 			copy_union();
   1066 			break;
   1067 
   1068 		case TOKEN:
   1069 		case LEFT:
   1070 		case RIGHT:
   1071 		case NONASSOC:
   1072 			declare_tokens(k);
   1073 			break;
   1074 
   1075 		case EXPECT:
   1076 			declare_expect(k);
   1077 			break;
   1078 
   1079 		case TYPE:
   1080 			declare_types();
   1081 			break;
   1082 
   1083 		case START:
   1084 			declare_start();
   1085 			break;
   1086 		}
   1087 	}
   1088 }
   1089 
   1090 
   1091 void
   1092 initialize_grammar(void)
   1093 {
   1094 	nitems = 4;
   1095 	maxitems = 300;
   1096 	pitem = calloc(maxitems, sizeof(bucket *));
   1097 	if (pitem == NULL)
   1098 		no_space();
   1099 
   1100 	nrules = 3;
   1101 	maxrules = 100;
   1102 	plhs = reallocarray(NULL, maxrules, sizeof(bucket *));
   1103 	if (plhs == NULL)
   1104 		no_space();
   1105 	plhs[0] = 0;
   1106 	plhs[1] = 0;
   1107 	plhs[2] = 0;
   1108 	rprec = reallocarray(NULL, maxrules, sizeof(short));
   1109 	if (rprec == NULL)
   1110 		no_space();
   1111 	rprec[0] = 0;
   1112 	rprec[1] = 0;
   1113 	rprec[2] = 0;
   1114 	rassoc = reallocarray(NULL, maxrules, sizeof(char));
   1115 	if (rassoc == NULL)
   1116 		no_space();
   1117 	rassoc[0] = TOKEN;
   1118 	rassoc[1] = TOKEN;
   1119 	rassoc[2] = TOKEN;
   1120 }
   1121 
   1122 
   1123 void
   1124 expand_items(void)
   1125 {
   1126 	int olditems = maxitems;
   1127 
   1128 	maxitems += 300;
   1129 	pitem = reallocarray(pitem, maxitems, sizeof(bucket *));
   1130 	if (pitem == NULL)
   1131 		no_space();
   1132 	memset(pitem + olditems, 0, (maxitems - olditems) * sizeof(bucket *));
   1133 }
   1134 
   1135 
   1136 void
   1137 expand_rules(void)
   1138 {
   1139 	maxrules += 100;
   1140 	plhs = reallocarray(plhs, maxrules, sizeof(bucket *));
   1141 	if (plhs == NULL)
   1142 		no_space();
   1143 	rprec = reallocarray(rprec, maxrules, sizeof(short));
   1144 	if (rprec == NULL)
   1145 		no_space();
   1146 	rassoc = reallocarray(rassoc, maxrules, sizeof(char));
   1147 	if (rassoc == NULL)
   1148 		no_space();
   1149 }
   1150 
   1151 
   1152 void
   1153 advance_to_start(void)
   1154 {
   1155 	int c;
   1156 	bucket *bp;
   1157 	char *s_cptr;
   1158 	int s_lineno;
   1159 
   1160 	for (;;) {
   1161 		c = nextc();
   1162 		if (c != '%')
   1163 			break;
   1164 		s_cptr = cptr;
   1165 		switch (keyword()) {
   1166 		case MARK:
   1167 			no_grammar();
   1168 
   1169 		case TEXT:
   1170 			copy_text();
   1171 			break;
   1172 
   1173 		case START:
   1174 			declare_start();
   1175 			break;
   1176 
   1177 		default:
   1178 			syntax_error(lineno, line, s_cptr);
   1179 		}
   1180 	}
   1181 
   1182 	c = nextc();
   1183 	if (!isalpha(c) && c != '_' && c != '.' && c != '_')
   1184 		syntax_error(lineno, line, cptr);
   1185 	bp = get_name();
   1186 	if (goal == NULL) {
   1187 		if (bp->class == TERM)
   1188 			terminal_start(bp->name);
   1189 		goal = bp;
   1190 	}
   1191 	s_lineno = lineno;
   1192 	c = nextc();
   1193 	if (c == EOF)
   1194 		unexpected_EOF();
   1195 	if (c != ':')
   1196 		syntax_error(lineno, line, cptr);
   1197 	start_rule(bp, s_lineno);
   1198 	++cptr;
   1199 }
   1200 
   1201 
   1202 void
   1203 start_rule(bucket * bp, int s_lineno)
   1204 {
   1205 	if (bp->class == TERM)
   1206 		terminal_lhs(s_lineno);
   1207 	bp->class = NONTERM;
   1208 	if (nrules >= maxrules)
   1209 		expand_rules();
   1210 	plhs[nrules] = bp;
   1211 	rprec[nrules] = UNDEFINED;
   1212 	rassoc[nrules] = TOKEN;
   1213 }
   1214 
   1215 
   1216 void
   1217 end_rule(void)
   1218 {
   1219 	int i;
   1220 
   1221 	if (!last_was_action && plhs[nrules]->tag) {
   1222 		for (i = nitems - 1; pitem[i]; --i)
   1223 			continue;
   1224 		if (i == maxitems - 1 || pitem[i + 1] == 0 ||
   1225 		    pitem[i + 1]->tag != plhs[nrules]->tag)
   1226 			default_action_warning();
   1227 	}
   1228 	last_was_action = 0;
   1229 	if (nitems >= maxitems)
   1230 		expand_items();
   1231 	pitem[nitems] = 0;
   1232 	++nitems;
   1233 	++nrules;
   1234 }
   1235 
   1236 
   1237 void
   1238 insert_empty_rule(void)
   1239 {
   1240 	bucket *bp, **bpp;
   1241 
   1242 	assert(cache);
   1243 	snprintf(cache, cache_size, "$$%d", ++gensym);
   1244 	bp = make_bucket(cache);
   1245 	last_symbol->next = bp;
   1246 	last_symbol = bp;
   1247 	bp->tag = plhs[nrules]->tag;
   1248 	bp->class = NONTERM;
   1249 
   1250 	if ((nitems += 2) > maxitems)
   1251 		expand_items();
   1252 	bpp = pitem + nitems - 1;
   1253 	*bpp-- = bp;
   1254 	while ((bpp[0] = bpp[-1]))
   1255 		--bpp;
   1256 
   1257 	if (++nrules >= maxrules)
   1258 		expand_rules();
   1259 	plhs[nrules] = plhs[nrules - 1];
   1260 	plhs[nrules - 1] = bp;
   1261 	rprec[nrules] = rprec[nrules - 1];
   1262 	rprec[nrules - 1] = 0;
   1263 	rassoc[nrules] = rassoc[nrules - 1];
   1264 	rassoc[nrules - 1] = TOKEN;
   1265 }
   1266 
   1267 
   1268 void
   1269 add_symbol(void)
   1270 {
   1271 	int c;
   1272 	bucket *bp;
   1273 	int s_lineno = lineno;
   1274 
   1275 	c = (unsigned char) *cptr;
   1276 	if (c == '\'' || c == '"')
   1277 		bp = get_literal();
   1278 	else
   1279 		bp = get_name();
   1280 
   1281 	c = nextc();
   1282 	if (c == ':') {
   1283 		end_rule();
   1284 		start_rule(bp, s_lineno);
   1285 		++cptr;
   1286 		return;
   1287 	}
   1288 	if (last_was_action)
   1289 		insert_empty_rule();
   1290 	last_was_action = 0;
   1291 
   1292 	if (++nitems > maxitems)
   1293 		expand_items();
   1294 	pitem[nitems - 1] = bp;
   1295 }
   1296 
   1297 
   1298 void
   1299 copy_action(void)
   1300 {
   1301 	int c, i, n, depth, quote;
   1302 	char *tag;
   1303 	FILE *f = action_file;
   1304 	int a_lineno = lineno;
   1305 	char *a_line = dup_line();
   1306 	char *a_cptr = a_line + (cptr - line);
   1307 
   1308 	if (last_was_action)
   1309 		insert_empty_rule();
   1310 	last_was_action = 1;
   1311 
   1312 	fprintf(f, "case %d:\n", nrules - 2);
   1313 	if (!lflag)
   1314 		fprintf(f, line_format, lineno, input_file_name);
   1315 	if (*cptr == '=')
   1316 		++cptr;
   1317 
   1318 	n = 0;
   1319 	for (i = nitems - 1; pitem[i]; --i)
   1320 		++n;
   1321 
   1322 	depth = 0;
   1323 loop:
   1324 	c = (unsigned char) *cptr;
   1325 	if (c == '$') {
   1326 		if (cptr[1] == '<') {
   1327 			int d_lineno = lineno;
   1328 			char *d_line = dup_line();
   1329 			char *d_cptr = d_line + (cptr - line);
   1330 
   1331 			++cptr;
   1332 			tag = get_tag();
   1333 			c = (unsigned char) *cptr;
   1334 			if (c == '$') {
   1335 				fprintf(f, "yyval.%s", tag);
   1336 				++cptr;
   1337 				free(d_line);
   1338 				goto loop;
   1339 			} else if (isdigit(c)) {
   1340 				i = get_number();
   1341 				if (i > n)
   1342 					dollar_warning(d_lineno, i);
   1343 				fprintf(f, "yyvsp[%d].%s", i - n, tag);
   1344 				free(d_line);
   1345 				goto loop;
   1346 			} else if (c == '-' && isdigit((unsigned char) cptr[1])) {
   1347 				++cptr;
   1348 				i = -get_number() - n;
   1349 				fprintf(f, "yyvsp[%d].%s", i, tag);
   1350 				free(d_line);
   1351 				goto loop;
   1352 			} else
   1353 				dollar_error(d_lineno, d_line, d_cptr);
   1354 		} else if (cptr[1] == '$') {
   1355 			if (ntags) {
   1356 				tag = plhs[nrules]->tag;
   1357 				if (tag == NULL)
   1358 					untyped_lhs();
   1359 				fprintf(f, "yyval.%s", tag);
   1360 			} else
   1361 				fprintf(f, "yyval");
   1362 			cptr += 2;
   1363 			goto loop;
   1364 		} else if (isdigit((unsigned char) cptr[1])) {
   1365 			++cptr;
   1366 			i = get_number();
   1367 			if (ntags) {
   1368 				if (i <= 0 || i > n)
   1369 					unknown_rhs(i);
   1370 				tag = pitem[nitems + i - n - 1]->tag;
   1371 				if (tag == NULL)
   1372 					untyped_rhs(i, pitem[nitems + i - n - 1]->name);
   1373 				fprintf(f, "yyvsp[%d].%s", i - n, tag);
   1374 			} else {
   1375 				if (i > n)
   1376 					dollar_warning(lineno, i);
   1377 				fprintf(f, "yyvsp[%d]", i - n);
   1378 			}
   1379 			goto loop;
   1380 		} else if (cptr[1] == '-') {
   1381 			cptr += 2;
   1382 			i = get_number();
   1383 			if (ntags)
   1384 				unknown_rhs(-i);
   1385 			fprintf(f, "yyvsp[%d]", -i - n);
   1386 			goto loop;
   1387 		}
   1388 	}
   1389 	if (isalpha(c) || c == '_' || c == '$') {
   1390 		do {
   1391 			putc(c, f);
   1392 			c = (unsigned char) *++cptr;
   1393 		} while (isalnum(c) || c == '_' || c == '$');
   1394 		goto loop;
   1395 	}
   1396 	putc(c, f);
   1397 	++cptr;
   1398 	switch (c) {
   1399 	case '\n':
   1400 next_line:
   1401 		get_line();
   1402 		if (line)
   1403 			goto loop;
   1404 		unterminated_action(a_lineno, a_line, a_cptr);
   1405 
   1406 	case ';':
   1407 		if (depth > 0)
   1408 			goto loop;
   1409 		fprintf(f, "\nbreak;\n");
   1410 		free(a_line);
   1411 		return;
   1412 
   1413 	case '{':
   1414 		++depth;
   1415 		goto loop;
   1416 
   1417 	case '}':
   1418 		if (--depth > 0)
   1419 			goto loop;
   1420 		fprintf(f, "\nbreak;\n");
   1421 		free(a_line);
   1422 		return;
   1423 
   1424 	case '\'':
   1425 	case '"': {
   1426 		int s_lineno = lineno;
   1427 		char *s_line = dup_line();
   1428 		char *s_cptr = s_line + (cptr - line - 1);
   1429 
   1430 		quote = c;
   1431 		for (;;) {
   1432 			c = (unsigned char) *cptr++;
   1433 			putc(c, f);
   1434 			if (c == quote) {
   1435 				free(s_line);
   1436 				goto loop;
   1437 			}
   1438 			if (c == '\n')
   1439 				unterminated_string(s_lineno, s_line, s_cptr);
   1440 			if (c == '\\') {
   1441 				c = (unsigned char) *cptr++;
   1442 				putc(c, f);
   1443 				if (c == '\n') {
   1444 					get_line();
   1445 					if (line == NULL)
   1446 						unterminated_string(s_lineno, s_line, s_cptr);
   1447 				}
   1448 			}
   1449 		}
   1450 	}
   1451 
   1452 	case '/':
   1453 		c = (unsigned char) *cptr;
   1454 		if (c == '/') {
   1455 			putc('*', f);
   1456 			while ((c = (unsigned char) *++cptr) != '\n') {
   1457 				if (c == '*' && cptr[1] == '/')
   1458 					fprintf(f, "* ");
   1459 				else
   1460 					putc(c, f);
   1461 			}
   1462 			fprintf(f, "*/\n");
   1463 			goto next_line;
   1464 		}
   1465 		if (c == '*') {
   1466 			int c_lineno = lineno;
   1467 			char *c_line = dup_line();
   1468 			char *c_cptr = c_line + (cptr - line - 1);
   1469 
   1470 			putc('*', f);
   1471 			++cptr;
   1472 			for (;;) {
   1473 				c = (unsigned char) *cptr++;
   1474 				putc(c, f);
   1475 				if (c == '*' && *cptr == '/') {
   1476 					putc('/', f);
   1477 					++cptr;
   1478 					free(c_line);
   1479 					goto loop;
   1480 				}
   1481 				if (c == '\n') {
   1482 					get_line();
   1483 					if (line == NULL)
   1484 						unterminated_comment(c_lineno, c_line, c_cptr);
   1485 				}
   1486 			}
   1487 		}
   1488 		goto loop;
   1489 
   1490 	default:
   1491 		goto loop;
   1492 	}
   1493 }
   1494 
   1495 
   1496 int
   1497 mark_symbol(void)
   1498 {
   1499 	int c;
   1500 	bucket *bp = NULL;
   1501 
   1502 	c = (unsigned char) cptr[1];
   1503 	if (c == '%' || c == '\\') {
   1504 		cptr += 2;
   1505 		return (1);
   1506 	}
   1507 	if (c == '=')
   1508 		cptr += 2;
   1509 	else if ((c == 'p' || c == 'P') &&
   1510 	    ((c = cptr[2]) == 'r' || c == 'R') &&
   1511 	    ((c = cptr[3]) == 'e' || c == 'E') &&
   1512 	    ((c = cptr[4]) == 'c' || c == 'C') &&
   1513 	    ((c = (unsigned char) cptr[5], !IS_IDENT(c))))
   1514 		cptr += 5;
   1515 	else
   1516 		syntax_error(lineno, line, cptr);
   1517 
   1518 	c = nextc();
   1519 	if (isalpha(c) || c == '_' || c == '.' || c == '$')
   1520 		bp = get_name();
   1521 	else if (c == '\'' || c == '"')
   1522 		bp = get_literal();
   1523 	else {
   1524 		syntax_error(lineno, line, cptr);
   1525 		/* NOTREACHED */
   1526 	}
   1527 
   1528 	if (rprec[nrules] != UNDEFINED && bp->prec != rprec[nrules])
   1529 		prec_redeclared();
   1530 
   1531 	rprec[nrules] = bp->prec;
   1532 	rassoc[nrules] = bp->assoc;
   1533 	return (0);
   1534 }
   1535 
   1536 
   1537 void
   1538 read_grammar(void)
   1539 {
   1540 	int c;
   1541 
   1542 	initialize_grammar();
   1543 	advance_to_start();
   1544 
   1545 	for (;;) {
   1546 		c = nextc();
   1547 		if (c == EOF)
   1548 			break;
   1549 		if (isalpha(c) || c == '_' || c == '.' || c == '$' || c == '\'' ||
   1550 		    c == '"')
   1551 			add_symbol();
   1552 		else if (c == '{' || c == '=')
   1553 			copy_action();
   1554 		else if (c == '|') {
   1555 			end_rule();
   1556 			start_rule(plhs[nrules - 1], 0);
   1557 			++cptr;
   1558 		} else if (c == '%') {
   1559 			if (mark_symbol())
   1560 				break;
   1561 		} else
   1562 			syntax_error(lineno, line, cptr);
   1563 	}
   1564 	end_rule();
   1565 }
   1566 
   1567 
   1568 void
   1569 free_tags(void)
   1570 {
   1571 	int i;
   1572 
   1573 	if (tag_table == NULL)
   1574 		return;
   1575 
   1576 	for (i = 0; i < ntags; ++i) {
   1577 		assert(tag_table[i]);
   1578 		free(tag_table[i]);
   1579 	}
   1580 	free(tag_table);
   1581 }
   1582 
   1583 
   1584 void
   1585 pack_names(void)
   1586 {
   1587 	bucket *bp;
   1588 	char *p, *s, *t;
   1589 
   1590 	name_pool_size = 13;	/* 13 == sizeof("$end") + sizeof("$accept") */
   1591 	for (bp = first_symbol; bp; bp = bp->next)
   1592 		name_pool_size += strlen(bp->name) + 1;
   1593 	name_pool = malloc(name_pool_size);
   1594 	if (name_pool == NULL)
   1595 		no_space();
   1596 
   1597 	strlcpy(name_pool, "$accept", name_pool_size);
   1598 	strlcpy(name_pool + 8, "$end", name_pool_size - 8);
   1599 	t = name_pool + 13;
   1600 	for (bp = first_symbol; bp; bp = bp->next) {
   1601 		p = t;
   1602 		s = bp->name;
   1603 		while ((*t++ = *s++))
   1604 			continue;
   1605 		free(bp->name);
   1606 		bp->name = p;
   1607 	}
   1608 }
   1609 
   1610 
   1611 void
   1612 check_symbols(void)
   1613 {
   1614 	bucket *bp;
   1615 
   1616 	if (goal->class == UNKNOWN)
   1617 		undefined_goal(goal->name);
   1618 
   1619 	for (bp = first_symbol; bp; bp = bp->next) {
   1620 		if (bp->class == UNKNOWN) {
   1621 			undefined_symbol_warning(bp->name);
   1622 			bp->class = TERM;
   1623 		}
   1624 	}
   1625 }
   1626 
   1627 
   1628 void
   1629 pack_symbols(void)
   1630 {
   1631 	bucket *bp;
   1632 	bucket **v;
   1633 	int i, j, k, n;
   1634 
   1635 	nsyms = 2;
   1636 	ntokens = 1;
   1637 	for (bp = first_symbol; bp; bp = bp->next) {
   1638 		++nsyms;
   1639 		if (bp->class == TERM)
   1640 			++ntokens;
   1641 	}
   1642 	start_symbol = ntokens;
   1643 	nvars = nsyms - ntokens;
   1644 
   1645 	symbol_name = reallocarray(NULL, nsyms, sizeof(char *));
   1646 	if (symbol_name == NULL)
   1647 		no_space();
   1648 	symbol_value = reallocarray(NULL, nsyms, sizeof(short));
   1649 	if (symbol_value == NULL)
   1650 		no_space();
   1651 	symbol_prec = reallocarray(NULL, nsyms, sizeof(short));
   1652 	if (symbol_prec == NULL)
   1653 		no_space();
   1654 	symbol_assoc = malloc(nsyms);
   1655 	if (symbol_assoc == NULL)
   1656 		no_space();
   1657 
   1658 	v = reallocarray(NULL, nsyms, sizeof(bucket *));
   1659 	if (v == NULL)
   1660 		no_space();
   1661 
   1662 	v[0] = 0;
   1663 	v[start_symbol] = 0;
   1664 
   1665 	i = 1;
   1666 	j = start_symbol + 1;
   1667 	for (bp = first_symbol; bp; bp = bp->next) {
   1668 		if (bp->class == TERM)
   1669 			v[i++] = bp;
   1670 		else
   1671 			v[j++] = bp;
   1672 	}
   1673 	assert(i == ntokens && j == nsyms);
   1674 
   1675 	for (i = 1; i < ntokens; ++i)
   1676 		v[i]->index = i;
   1677 
   1678 	goal->index = start_symbol + 1;
   1679 	k = start_symbol + 2;
   1680 	while (++i < nsyms)
   1681 		if (v[i] != goal) {
   1682 			v[i]->index = k;
   1683 			++k;
   1684 		}
   1685 	goal->value = 0;
   1686 	k = 1;
   1687 	for (i = start_symbol + 1; i < nsyms; ++i) {
   1688 		if (v[i] != goal) {
   1689 			v[i]->value = k;
   1690 			++k;
   1691 		}
   1692 	}
   1693 
   1694 	k = 0;
   1695 	for (i = 1; i < ntokens; ++i) {
   1696 		n = v[i]->value;
   1697 		if (n > 256) {
   1698 			for (j = k++; j > 0 && symbol_value[j - 1] > n; --j)
   1699 				symbol_value[j] = symbol_value[j - 1];
   1700 			symbol_value[j] = n;
   1701 		}
   1702 	}
   1703 
   1704 	if (v[1]->value == UNDEFINED)
   1705 		v[1]->value = 256;
   1706 
   1707 	j = 0;
   1708 	n = 257;
   1709 	for (i = 2; i < ntokens; ++i) {
   1710 		if (v[i]->value == UNDEFINED) {
   1711 			while (j < k && n == symbol_value[j]) {
   1712 				while (++j < k && n == symbol_value[j])
   1713 					continue;
   1714 				++n;
   1715 			}
   1716 			v[i]->value = n;
   1717 			++n;
   1718 		}
   1719 	}
   1720 
   1721 	symbol_name[0] = name_pool + 8;
   1722 	symbol_value[0] = 0;
   1723 	symbol_prec[0] = 0;
   1724 	symbol_assoc[0] = TOKEN;
   1725 	for (i = 1; i < ntokens; ++i) {
   1726 		symbol_name[i] = v[i]->name;
   1727 		symbol_value[i] = v[i]->value;
   1728 		symbol_prec[i] = v[i]->prec;
   1729 		symbol_assoc[i] = v[i]->assoc;
   1730 	}
   1731 	symbol_name[start_symbol] = name_pool;
   1732 	symbol_value[start_symbol] = -1;
   1733 	symbol_prec[start_symbol] = 0;
   1734 	symbol_assoc[start_symbol] = TOKEN;
   1735 	for (++i; i < nsyms; ++i) {
   1736 		k = v[i]->index;
   1737 		symbol_name[k] = v[i]->name;
   1738 		symbol_value[k] = v[i]->value;
   1739 		symbol_prec[k] = v[i]->prec;
   1740 		symbol_assoc[k] = v[i]->assoc;
   1741 	}
   1742 
   1743 	free(v);
   1744 }
   1745 
   1746 
   1747 void
   1748 pack_grammar(void)
   1749 {
   1750 	int i, j;
   1751 	int assoc, prec;
   1752 
   1753 	ritem = reallocarray(NULL, nitems, sizeof(short));
   1754 	if (ritem == NULL)
   1755 		no_space();
   1756 	rlhs = reallocarray(NULL, nrules, sizeof(short));
   1757 	if (rlhs == NULL)
   1758 		no_space();
   1759 	rrhs = reallocarray(NULL, nrules + 1, sizeof(short));
   1760 	if (rrhs == NULL)
   1761 		no_space();
   1762 	rprec = reallocarray(rprec, nrules, sizeof(short));
   1763 	if (rprec == NULL)
   1764 		no_space();
   1765 	rassoc = realloc(rassoc, nrules);
   1766 	if (rassoc == NULL)
   1767 		no_space();
   1768 
   1769 	ritem[0] = -1;
   1770 	ritem[1] = goal->index;
   1771 	ritem[2] = 0;
   1772 	ritem[3] = -2;
   1773 	rlhs[0] = 0;
   1774 	rlhs[1] = 0;
   1775 	rlhs[2] = start_symbol;
   1776 	rrhs[0] = 0;
   1777 	rrhs[1] = 0;
   1778 	rrhs[2] = 1;
   1779 
   1780 	j = 4;
   1781 	for (i = 3; i < nrules; ++i) {
   1782 		rlhs[i] = plhs[i]->index;
   1783 		rrhs[i] = j;
   1784 		assoc = TOKEN;
   1785 		prec = 0;
   1786 		while (pitem[j]) {
   1787 			ritem[j] = pitem[j]->index;
   1788 			if (pitem[j]->class == TERM) {
   1789 				prec = pitem[j]->prec;
   1790 				assoc = pitem[j]->assoc;
   1791 			}
   1792 			++j;
   1793 		}
   1794 		ritem[j] = -i;
   1795 		++j;
   1796 		if (rprec[i] == UNDEFINED) {
   1797 			rprec[i] = prec;
   1798 			rassoc[i] = assoc;
   1799 		}
   1800 	}
   1801 	rrhs[i] = j;
   1802 
   1803 	free(plhs);
   1804 	free(pitem);
   1805 }
   1806 
   1807 
   1808 void
   1809 print_grammar(void)
   1810 {
   1811 	int i, j, k;
   1812 	int spacing = 0;
   1813 	FILE *f = verbose_file;
   1814 
   1815 	if (!vflag)
   1816 		return;
   1817 
   1818 	k = 1;
   1819 	for (i = 2; i < nrules; ++i) {
   1820 		if (rlhs[i] != rlhs[i - 1]) {
   1821 			if (i != 2)
   1822 				fprintf(f, "\n");
   1823 			fprintf(f, "%4d  %s :", i - 2, symbol_name[rlhs[i]]);
   1824 			spacing = strlen(symbol_name[rlhs[i]]) + 1;
   1825 		} else {
   1826 			fprintf(f, "%4d  ", i - 2);
   1827 			j = spacing;
   1828 			while (--j >= 0)
   1829 				putc(' ', f);
   1830 			putc('|', f);
   1831 		}
   1832 
   1833 		while (ritem[k] >= 0) {
   1834 			fprintf(f, " %s", symbol_name[ritem[k]]);
   1835 			++k;
   1836 		}
   1837 		++k;
   1838 		putc('\n', f);
   1839 	}
   1840 }
   1841 
   1842 
   1843 void
   1844 reader(void)
   1845 {
   1846 	write_section(banner);
   1847 	create_symbol_table();
   1848 	read_declarations();
   1849 	read_grammar();
   1850 	free_symbol_table();
   1851 	free_tags();
   1852 	pack_names();
   1853 	check_symbols();
   1854 	pack_symbols();
   1855 	pack_grammar();
   1856 	free_symbols();
   1857 	print_grammar();
   1858 }