fatbase

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

commit ed21e29ea4465ee431ddf57c02869955b47d74a2
parent 121f6601f24e6f9e5218ebefeec388514a918664
Author: Hiltjo Posthuma <hiltjo@codemadness.org>
Date:   Fri, 21 Nov 2014 20:10:39 +0100

add yacc

Diffstat:
Ayacc/Makefile | 19+++++++++++++++++++
Ayacc/closure.c | 250+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/defs.h | 366+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/error.c | 323+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/lalr.c | 601+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/lr0.c | 504+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/main.c | 362+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/mkpar.c | 370+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/output.c | 1205+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/reader.c | 1858+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/reallocarray.c | 38++++++++++++++++++++++++++++++++++++++
Ayacc/skeleton.c | 404+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/symtab.c | 151++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/util.h | 3+++
Ayacc/verbose.c | 351+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/warshall.c | 100+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/yacc.1 | 256+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/yyfix.1 | 108+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Ayacc/yyfix.sh | 73+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
19 files changed, 7342 insertions(+), 0 deletions(-)

diff --git a/yacc/Makefile b/yacc/Makefile @@ -0,0 +1,19 @@ +build: clean + cc -c *.c + cc -o yacc *.o + +clean: + rm -f *.o yacc + +# $OpenBSD: Makefile,v 1.5 2010/10/17 22:54:37 schwarze Exp $ +# +#PROG= yacc +#SRCS= closure.c error.c lalr.c lr0.c main.c mkpar.c output.c reader.c \ +# skeleton.c symtab.c verbose.c warshall.c +#MAN= yacc.1 yyfix.1 +# +#beforeinstall: +# ${INSTALL} ${INSTALL_COPY} -o ${BINOWN} -g ${BINGRP} -m ${BINMODE} \ +# ${.CURDIR}/yyfix.sh ${DESTDIR}${BINDIR}/yyfix +# +#.include <bsd.prog.mk> diff --git a/yacc/closure.c b/yacc/closure.c @@ -0,0 +1,250 @@ +/* $OpenBSD: closure.c,v 1.13 2014/03/13 01:18:22 tedu Exp $ */ +/* $NetBSD: closure.c,v 1.4 1996/03/19 03:21:29 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" + +short *itemset; +short *itemsetend; +unsigned *ruleset; + +static unsigned *first_derives; +static unsigned *EFF; + + +void +set_EFF(void) +{ + unsigned int *row; + int symbol, rowsize, i, rule; + short *sp; + + rowsize = WORDSIZE(nvars); + EFF = NEW2(nvars * rowsize, unsigned); + + row = EFF; + for (i = start_symbol; i < nsyms; i++) { + sp = derives[i]; + for (rule = *sp; rule > 0; rule = *++sp) { + symbol = ritem[rrhs[rule]]; + if (ISVAR(symbol)) { + symbol -= start_symbol; + SETBIT(row, symbol); + } + } + row += rowsize; + } + + reflexive_transitive_closure(EFF, nvars); + +#ifdef DEBUG + print_EFF(); +#endif +} + + +void +set_first_derives(void) +{ + unsigned int *rrow, *vrow; + unsigned int k, cword = 0; + int i, j, rule, rulesetsize, varsetsize; + short *rp; + + rulesetsize = WORDSIZE(nrules); + varsetsize = WORDSIZE(nvars); + first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; + + set_EFF(); + + rrow = first_derives + ntokens * rulesetsize; + for (i = start_symbol; i < nsyms; i++) { + vrow = EFF + ((i - ntokens) * varsetsize); + k = BITS_PER_WORD; + for (j = start_symbol; j < nsyms; k++, j++) { + if (k >= BITS_PER_WORD) { + cword = *vrow++; + k = 0; + } + + if (cword & (1 << k)) { + rp = derives[j]; + while ((rule = *rp++) >= 0) { + SETBIT(rrow, rule); + } + } + } + + vrow += varsetsize; + rrow += rulesetsize; + } + +#ifdef DEBUG + print_first_derives(); +#endif + + free(EFF); +} + + +void +closure(short *nucleus, int n) +{ + unsigned int i, word; + short *csp, *csend; + unsigned int *dsp, *rsp, *rsend; + int rulesetsize; + int ruleno, symbol, itemno; + + rulesetsize = WORDSIZE(nrules); + rsend = ruleset + rulesetsize; + memset(ruleset, 0, rulesetsize * sizeof(*ruleset)); + + csend = nucleus + n; + for (csp = nucleus; csp < csend; ++csp) { + symbol = ritem[*csp]; + if (ISVAR(symbol)) { + dsp = first_derives + symbol * rulesetsize; + rsp = ruleset; + while (rsp < rsend) + *rsp++ |= *dsp++; + } + } + + ruleno = 0; + itemsetend = itemset; + csp = nucleus; + for (rsp = ruleset; rsp < rsend; ++rsp) { + word = *rsp; + if (word) { + for (i = 0; i < BITS_PER_WORD; ++i) { + if (word & (1 << i)) { + itemno = rrhs[ruleno+i]; + while (csp < csend && *csp < itemno) + *itemsetend++ = *csp++; + *itemsetend++ = itemno; + while (csp < csend && *csp == itemno) + ++csp; + } + } + } + ruleno += BITS_PER_WORD; + } + + while (csp < csend) + *itemsetend++ = *csp++; + +#ifdef DEBUG + print_closure(n); +#endif +} + + + +void +finalize_closure(void) +{ + free(itemset); + free(ruleset); + free(first_derives + ntokens * WORDSIZE(nrules)); +} + + +#ifdef DEBUG + +void +print_closure(int n) +{ + short *isp; + + printf("\n\nn = %d\n\n", n); + for (isp = itemset; isp < itemsetend; isp++) + printf(" %d\n", *isp); +} + +void +print_EFF(void) +{ + int i, j; + unsigned int *rowp; + unsigned int k, word; + + printf("\n\nEpsilon Free Firsts\n"); + + for (i = start_symbol; i < nsyms; i++) { + printf("\n%s", symbol_name[i]); + rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); + word = *rowp++; + + k = BITS_PER_WORD; + for (j = 0; j < nvars; k++, j++) { + if (k >= BITS_PER_WORD) { + word = *rowp++; + k = 0; + } + + if (word & (1 << k)) + printf(" %s", symbol_name[start_symbol + j]); + } + } +} + +void +print_first_derives(void) +{ + int i, j; + unsigned int *rp; + unsigned int k, cword = 0; + + printf("\n\n\nFirst Derives\n"); + + for (i = start_symbol; i < nsyms; i++) { + printf("\n%s derives\n", symbol_name[i]); + rp = first_derives + i * WORDSIZE(nrules); + k = BITS_PER_WORD; + for (j = 0; j <= nrules; k++, j++) { + if (k >= BITS_PER_WORD) { + cword = *rp++; + k = 0; + } + + if (cword & (1 << k)) + printf(" %d\n", j); + } + } + + fflush(stdout); +} + +#endif diff --git a/yacc/defs.h b/yacc/defs.h @@ -0,0 +1,366 @@ +/* $OpenBSD: defs.h,v 1.17 2014/03/08 01:05:39 tedu Exp $ */ +/* $NetBSD: defs.h,v 1.6 1996/03/19 03:21:30 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)defs.h 5.6 (Berkeley) 5/24/93 + */ + +#include <assert.h> +#include <ctype.h> +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +/* machine-dependent definitions */ +/* the following definitions are for the Tahoe */ +/* they might have to be changed for other machines */ + +/* MAXCHAR is the largest unsigned character value */ +/* MAXSHORT is the largest value of a C short */ +/* MINSHORT is the most negative value of a C short */ +/* MAXTABLE is the maximum table size */ +/* BITS_PER_WORD is the number of bits in a C unsigned */ +/* WORDSIZE computes the number of words needed to */ +/* store n bits */ +/* BIT returns the value of the n-th bit starting */ +/* from r (0-indexed) */ +/* SETBIT sets the n-th bit starting from r */ + +#define MAXCHAR 255 +#define MAXSHORT 32767 +#define MINSHORT -32768 +#define MAXTABLE 32500 +#define BITS_PER_WORD 32 +#define WORDSIZE(n) (((n)+(BITS_PER_WORD-1))/BITS_PER_WORD) +#define BIT(r, n) ((((r)[(n)>>5])>>((n)&31))&1) +#define SETBIT(r, n) ((r)[(n)>>5]|=((unsigned)1<<((n)&31))) + + +/* character names */ + +#define NUL '\0' /* the null character */ +#define NEWLINE '\n' /* line feed */ +#define SP ' ' /* space */ +#define BS '\b' /* backspace */ +#define HT '\t' /* horizontal tab */ +#define VT '\013' /* vertical tab */ +#define CR '\r' /* carriage return */ +#define FF '\f' /* form feed */ +#define QUOTE '\'' /* single quote */ +#define DOUBLE_QUOTE '\"' /* double quote */ +#define BACKSLASH '\\' /* backslash */ + + +/* defines for constructing filenames */ + +#define CODE_SUFFIX ".code.c" +#define DEFINES_SUFFIX ".tab.h" +#define OUTPUT_SUFFIX ".tab.c" +#define VERBOSE_SUFFIX ".output" + + +/* keyword codes */ + +#define TOKEN 0 +#define LEFT 1 +#define RIGHT 2 +#define NONASSOC 3 +#define MARK 4 +#define TEXT 5 +#define TYPE 6 +#define START 7 +#define UNION 8 +#define IDENT 9 +#define EXPECT 10 + + +/* symbol classes */ + +#define UNKNOWN 0 +#define TERM 1 +#define NONTERM 2 + + +/* the undefined value */ + +#define UNDEFINED (-1) + + +/* action codes */ + +#define SHIFT 1 +#define REDUCE 2 + + +/* character macros */ + +#define IS_IDENT(c) (isalnum(c) || (c) == '_' || (c) == '.' || (c) == '$') +#define NUMERIC_VALUE(c) ((c) - '0') + + +/* symbol macros */ + +#define ISTOKEN(s) ((s) < start_symbol) +#define ISVAR(s) ((s) >= start_symbol) + + +/* storage allocation macros */ + +#define NEW(t) ((t*)allocate(sizeof(t))) +#define NEW2(n,t) ((t*)allocate((n)*sizeof(t))) + + +/* the structure of a symbol table entry */ + +typedef struct bucket bucket; +struct bucket { + struct bucket *link; + struct bucket *next; + char *name; + char *tag; + short value; + short index; + short prec; + char class; + char assoc; +}; + + +/* the structure of the LR(0) state machine */ + +typedef struct core core; +struct core { + struct core *next; + struct core *link; + short number; + short accessing_symbol; + short nitems; + short items[1]; +}; + + +/* the structure used to record shifts */ + +typedef struct shifts shifts; +struct shifts { + struct shifts *next; + short number; + short nshifts; + short shift[1]; +}; + + +/* the structure used to store reductions */ + +typedef struct reductions reductions; +struct reductions { + struct reductions *next; + short number; + short nreds; + short rules[1]; +}; + + +/* the structure used to represent parser actions */ + +typedef struct action action; +struct action { + struct action *next; + short symbol; + short number; + short prec; + char action_code; + char assoc; + char suppressed; +}; + + +/* global variables */ + +extern char dflag; +extern char lflag; +extern char rflag; +extern char tflag; +extern char vflag; +extern char *symbol_prefix; + +extern char *cptr; +extern char *line; +extern int lineno; +extern int outline; + +extern char *banner[]; +extern char *tables[]; +extern char *header[]; +extern char *body[]; +extern char *trailer[]; + +extern char *action_file_name; +extern char *code_file_name; +extern char *defines_file_name; +extern char *input_file_name; +extern char *output_file_name; +extern char *text_file_name; +extern char *union_file_name; +extern char *verbose_file_name; + +extern FILE *action_file; +extern FILE *code_file; +extern FILE *defines_file; +extern FILE *input_file; +extern FILE *output_file; +extern FILE *text_file; +extern FILE *union_file; +extern FILE *verbose_file; + +extern int nitems; +extern int nrules; +extern int nsyms; +extern int ntokens; +extern int nvars; +extern int ntags; + +extern char unionized; +extern char line_format[]; + +extern int start_symbol; +extern char **symbol_name; +extern short *symbol_value; +extern short *symbol_prec; +extern char *symbol_assoc; + +extern short *ritem; +extern short *rlhs; +extern short *rrhs; +extern short *rprec; +extern char *rassoc; + +extern short **derives; +extern char *nullable; + +extern bucket *first_symbol; +extern bucket *last_symbol; + +extern int nstates; +extern core *first_state; +extern shifts *first_shift; +extern reductions *first_reduction; +extern short *accessing_symbol; +extern core **state_table; +extern shifts **shift_table; +extern reductions **reduction_table; +extern unsigned *LA; +extern short *LAruleno; +extern short *lookaheads; +extern short *goto_map; +extern short *from_state; +extern short *to_state; + +extern action **parser; +extern int SRtotal; +extern int SRexpect; +extern int RRtotal; +extern short *SRconflicts; +extern short *RRconflicts; +extern short *defred; +extern short *rules_used; +extern short nunused; +extern short final_state; + +/* global functions */ + +extern void *allocate(size_t); +extern bucket *lookup(char *); +extern bucket *make_bucket(char *); +extern void set_first_derives(void); +extern void closure(short *, int); +extern void finalize_closure(void); + +extern void fatal(char *); + +extern void reflexive_transitive_closure(unsigned *, int); +extern void done(int); + +extern void no_space(void); +extern void open_error(char *); +extern void open_write_error(char *); +extern void unexpected_EOF(void); +extern void print_pos(char *, char *); +extern void syntax_error(int, char *, char *); +extern void unterminated_comment(int, char *, char *); +extern void unterminated_string(int, char *, char *); +extern void unterminated_text(int, char *, char *); +extern void unterminated_union(int, char *, char *); +extern void over_unionized(char *); +extern void illegal_tag(int, char *, char *); +extern void illegal_character(char *); +extern void used_reserved(char *); +extern void tokenized_start(char *); +extern void retyped_warning(char *); +extern void reprec_warning(char *); +extern void revalued_warning(char *); +extern void terminal_start(char *); +extern void restarted_warning(void); +extern void no_grammar(void); +extern void terminal_lhs(int); +extern void prec_redeclared(void); +extern void unterminated_action(int, char *, char *); +extern void dollar_warning(int, int); +extern void dollar_error(int, char *, char *); +extern void untyped_lhs(void); +extern void untyped_rhs(int, char *); +extern void unknown_rhs(int); +extern void default_action_warning(void); +extern void undefined_goal(char *); +extern void undefined_symbol_warning(char *); + +extern void lalr(void); + +extern void reader(void); +extern void lr0(void); +extern void free_nullable(void); +extern void free_derives(void); +extern void make_parser(void); +extern void verbose(void); +extern void output(void); +extern void free_parser(void); +extern void write_section(char *[]); + +extern void create_symbol_table(void); +extern void free_symbol_table(void); +extern void free_symbols(void); + + +/* system variables */ + +extern char *__progname; diff --git a/yacc/error.c b/yacc/error.c @@ -0,0 +1,323 @@ +/* $OpenBSD: error.c,v 1.14 2014/03/08 01:05:39 tedu Exp $ */ +/* $NetBSD: error.c,v 1.4 1996/03/19 03:21:32 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +/* routines for printing error messages */ + +#include "defs.h" + + +void +fatal(char *msg) +{ + fprintf(stderr, "%s: %s\n", input_file_name, msg); + done(2); +} + + +void +no_space(void) +{ + fprintf(stderr, "%s: yacc is out of space\n", input_file_name); + done(2); +} + + +void +open_error(char *filename) +{ + fprintf(stderr, "%s: cannot open source file %s\n", + input_file_name, filename); + done(2); +} + +void +open_write_error(char *filename) +{ + fprintf(stderr, "%s: cannot open target file %s for writing\n", + input_file_name, filename); + done(2); +} + +void +unexpected_EOF(void) +{ + fprintf(stderr, "%s:%d: unexpected end-of-file\n", + input_file_name, lineno); + done(1); +} + + +void +print_pos(char *st_line, char *st_cptr) +{ + char *s; + + if (st_line == 0) + return; + for (s = st_line; *s != '\n'; ++s) { + if (isprint((unsigned char)*s) || *s == '\t') + putc(*s, stderr); + else + putc('?', stderr); + } + putc('\n', stderr); + for (s = st_line; s < st_cptr; ++s) { + if (*s == '\t') + putc('\t', stderr); + else + putc(' ', stderr); + } + putc('^', stderr); + putc('\n', stderr); +} + +void +syntax_error(int st_lineno, char *st_line, char *st_cptr) +{ + fprintf(stderr, "%s:%d: syntax error\n", + input_file_name, st_lineno); + print_pos(st_line, st_cptr); + done(1); +} + +void +unterminated_comment(int c_lineno, char *c_line, char *c_cptr) +{ + fprintf(stderr, "%s:%d: unmatched /*\n", + input_file_name, c_lineno); + print_pos(c_line, c_cptr); + done(1); +} + +void +unterminated_string(int s_lineno, char *s_line, char *s_cptr) +{ + fprintf(stderr, "%s:%d:, unterminated string\n", + input_file_name, s_lineno); + print_pos(s_line, s_cptr); + done(1); +} + +void +unterminated_text(int t_lineno, char *t_line, char *t_cptr) +{ + fprintf(stderr, "%s:%d: unmatched %%{\n", + input_file_name, t_lineno); + print_pos(t_line, t_cptr); + done(1); +} + +void +unterminated_union(int u_lineno, char *u_line, char *u_cptr) +{ + fprintf(stderr, "%s:%d: unterminated %%union declaration\n", + input_file_name, u_lineno); + print_pos(u_line, u_cptr); + done(1); +} + +void +over_unionized(char *u_cptr) +{ + fprintf(stderr, "%s:%d: too many %%union declarations\n", + input_file_name, lineno); + print_pos(line, u_cptr); + done(1); +} + +void +illegal_tag(int t_lineno, char *t_line, char *t_cptr) +{ + fprintf(stderr, "%s:%d: illegal tag\n", + input_file_name, t_lineno); + print_pos(t_line, t_cptr); + done(1); +} + + +void +illegal_character(char *c_cptr) +{ + fprintf(stderr, "%s:%d: illegal character\n", + input_file_name, lineno); + print_pos(line, c_cptr); + done(1); +} + + +void +used_reserved(char *s) +{ + fprintf(stderr, "%s:%d: illegal use of reserved symbol %s\n", + input_file_name, lineno, s); + done(1); +} + +void +tokenized_start(char *s) +{ + fprintf(stderr, "%s:%d: the start symbol %s cannot be declared to be a token\n", + input_file_name, lineno, s); + done(1); +} + +void +retyped_warning(char *s) +{ + fprintf(stderr, "%s:%d: the type of %s has been redeclared\n", + input_file_name, lineno, s); +} + +void +reprec_warning(char *s) +{ + fprintf(stderr, "%s:%d: the precedence of %s has been redeclared\n", + input_file_name, lineno, s); +} + +void +revalued_warning(char *s) +{ + fprintf(stderr, "%s:%d: the value of %s has been redeclared\n", + input_file_name, lineno, s); +} + +void +terminal_start(char *s) +{ + fprintf(stderr, "%s:%d: the start symbol %s is a token\n", + input_file_name, lineno, s); + done(1); +} + +void +restarted_warning(void) +{ + fprintf(stderr, "%s:%d: the start symbol has been redeclared\n", + input_file_name, lineno); +} + +void +no_grammar(void) +{ + fprintf(stderr, "%s:%d: no grammar has been specified\n", + input_file_name, lineno); + done(1); +} + +void +terminal_lhs(int s_lineno) +{ + fprintf(stderr, "%s:%d: a token appears on the lhs of a production\n", + input_file_name, s_lineno); + done(1); +} + +void +prec_redeclared(void) +{ + fprintf(stderr, "%s:%d: conflicting %%prec specifiers\n", + input_file_name, lineno); +} + +void +unterminated_action(int a_lineno, char *a_line, char *a_cptr) +{ + fprintf(stderr, "%s:%d: unterminated action\n", + input_file_name, a_lineno); + print_pos(a_line, a_cptr); + done(1); +} + +void +dollar_warning(int a_lineno, int i) +{ + fprintf(stderr, "%s:%d: $%d references beyond the end of the current rule\n", + input_file_name, a_lineno, i); +} + +void +dollar_error(int a_lineno, char *a_line, char *a_cptr) +{ + fprintf(stderr, "%s:%d: illegal $-name\n", + input_file_name, a_lineno); + print_pos(a_line, a_cptr); + done(1); +} + + +void +untyped_lhs(void) +{ + fprintf(stderr, "%s:%d: $$ is untyped\n", + input_file_name, lineno); + done(1); +} + +void +untyped_rhs(int i, char *s) +{ + fprintf(stderr, "%s:%d: $%d (%s) is untyped\n", + input_file_name, lineno, i, s); + done(1); +} + +void +unknown_rhs(int i) +{ + fprintf(stderr, "%s:%d: $%d is untyped\n", + input_file_name, lineno, i); + done(1); +} + +void +default_action_warning(void) +{ + fprintf(stderr, "%s:%d: the default action assigns an undefined value to $$\n", + input_file_name, lineno); +} + +void +undefined_goal(char *s) +{ + fprintf(stderr, "%s: the start symbol %s is undefined\n", input_file_name, s); + done(1); +} + +void +undefined_symbol_warning(char *s) +{ + fprintf(stderr, "%s: the symbol %s is undefined\n", input_file_name, s); +} diff --git a/yacc/lalr.c b/yacc/lalr.c @@ -0,0 +1,601 @@ +/* $OpenBSD: lalr.c,v 1.17 2014/05/17 15:19:17 chl Exp $ */ +/* $NetBSD: lalr.c,v 1.4 1996/03/19 03:21:33 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" + +typedef struct shorts { + struct shorts *next; + short value; +} shorts; + +int tokensetsize; +short *lookaheads; +short *LAruleno; +unsigned *LA; +short *accessing_symbol; +core **state_table; +shifts **shift_table; +reductions **reduction_table; +short *goto_map; +short *from_state; +short *to_state; + +short **transpose(); +void set_state_table(void); +void set_accessing_symbol(void); +void set_shift_table(void); +void set_reduction_table(void); +void set_maxrhs(void); +void initialize_LA(void); +void set_goto_map(void); +void initialize_F(void); +void build_relations(void); +void compute_FOLLOWS(void); +void compute_lookaheads(void); +int map_goto(int, int); +void digraph(short **); +void add_lookback_edge(int, int, int); +void traverse(int); + +static int infinity; +static int maxrhs; +static int ngotos; +static unsigned *F; +static short **includes; +static shorts **lookback; +static short **R; +static short *INDEX; +static short *VERTICES; +static int top; + +void +lalr(void) +{ + tokensetsize = WORDSIZE(ntokens); + + set_state_table(); + set_accessing_symbol(); + set_shift_table(); + set_reduction_table(); + set_maxrhs(); + initialize_LA(); + set_goto_map(); + initialize_F(); + build_relations(); + compute_FOLLOWS(); + compute_lookaheads(); + free_derives(); + free_nullable(); +} + + +void +set_state_table(void) +{ + core *sp; + + state_table = NEW2(nstates, core *); + for (sp = first_state; sp; sp = sp->next) + state_table[sp->number] = sp; +} + + +void +set_accessing_symbol(void) +{ + core *sp; + + accessing_symbol = NEW2(nstates, short); + for (sp = first_state; sp; sp = sp->next) + accessing_symbol[sp->number] = sp->accessing_symbol; +} + + +void +set_shift_table(void) +{ + shifts *sp; + + shift_table = NEW2(nstates, shifts *); + for (sp = first_shift; sp; sp = sp->next) + shift_table[sp->number] = sp; +} + + +void +set_reduction_table(void) +{ + reductions *rp; + + reduction_table = NEW2(nstates, reductions *); + for (rp = first_reduction; rp; rp = rp->next) + reduction_table[rp->number] = rp; +} + + +void +set_maxrhs(void) +{ + short *itemp, *item_end; + int length, max; + + length = 0; + max = 0; + item_end = ritem + nitems; + for (itemp = ritem; itemp < item_end; itemp++) { + if (*itemp >= 0) { + length++; + } else { + if (length > max) max = length; + length = 0; + } + } + + maxrhs = max; +} + + +void +initialize_LA(void) +{ + int i, j, k; + reductions *rp; + + lookaheads = NEW2(nstates + 1, short); + + k = 0; + for (i = 0; i < nstates; i++) { + lookaheads[i] = k; + rp = reduction_table[i]; + if (rp) + k += rp->nreds; + } + lookaheads[nstates] = k; + + LA = NEW2(k * tokensetsize, unsigned); + LAruleno = NEW2(k, short); + lookback = NEW2(k, shorts *); + + k = 0; + for (i = 0; i < nstates; i++) { + rp = reduction_table[i]; + if (rp) { + for (j = 0; j < rp->nreds; j++) { + LAruleno[k] = rp->rules[j]; + k++; + } + } + } +} + +void +set_goto_map(void) +{ + shifts *sp; + int i, k, symbol; + int state1, state2; + short *temp_map; + + goto_map = NEW2(nvars + 1, short) - ntokens; + temp_map = NEW2(nvars + 1, short) - ntokens; + + ngotos = 0; + for (sp = first_shift; sp; sp = sp->next) { + for (i = sp->nshifts - 1; i >= 0; i--) { + symbol = accessing_symbol[sp->shift[i]]; + + if (ISTOKEN(symbol)) break; + + if (ngotos == MAXSHORT) + fatal("too many gotos"); + + ngotos++; + goto_map[symbol]++; + } + } + + k = 0; + for (i = ntokens; i < nsyms; i++) { + temp_map[i] = k; + k += goto_map[i]; + } + + for (i = ntokens; i < nsyms; i++) + goto_map[i] = temp_map[i]; + + goto_map[nsyms] = ngotos; + temp_map[nsyms] = ngotos; + + from_state = NEW2(ngotos, short); + to_state = NEW2(ngotos, short); + + for (sp = first_shift; sp; sp = sp->next) { + state1 = sp->number; + for (i = sp->nshifts - 1; i >= 0; i--) { + state2 = sp->shift[i]; + symbol = accessing_symbol[state2]; + + if (ISTOKEN(symbol)) break; + + k = temp_map[symbol]++; + from_state[k] = state1; + to_state[k] = state2; + } + } + + free(temp_map + ntokens); +} + + + +/* Map_goto maps a state/symbol pair into its numeric representation. */ + +int +map_goto(int state, int symbol) +{ + int high, low, middle, s; + + low = goto_map[symbol]; + high = goto_map[symbol + 1]; + + for (;;) { + assert(low <= high); + middle = (low + high) >> 1; + s = from_state[middle]; + if (s == state) + return (middle); + else if (s < state) + low = middle + 1; + else + high = middle - 1; + } +} + + +void +initialize_F(void) +{ + int i, j, k; + shifts *sp; + short *edge, *rp, **reads; + unsigned int *rowp; + int nedges, stateno, symbol, nwords; + + nwords = ngotos * tokensetsize; + F = NEW2(nwords, unsigned); + + reads = NEW2(ngotos, short *); + edge = NEW2(ngotos + 1, short); + nedges = 0; + + rowp = F; + for (i = 0; i < ngotos; i++) { + stateno = to_state[i]; + sp = shift_table[stateno]; + + if (sp) { + k = sp->nshifts; + + for (j = 0; j < k; j++) { + symbol = accessing_symbol[sp->shift[j]]; + if (ISVAR(symbol)) + break; + SETBIT(rowp, symbol); + } + + for (; j < k; j++) { + symbol = accessing_symbol[sp->shift[j]]; + if (nullable[symbol]) + edge[nedges++] = map_goto(stateno, symbol); + } + + if (nedges) { + reads[i] = rp = NEW2(nedges + 1, short); + + for (j = 0; j < nedges; j++) + rp[j] = edge[j]; + + rp[nedges] = -1; + nedges = 0; + } + } + + rowp += tokensetsize; + } + + SETBIT(F, 0); + digraph(reads); + + for (i = 0; i < ngotos; i++) { + if (reads[i]) + free(reads[i]); + } + + free(reads); + free(edge); +} + + +void +build_relations(void) +{ + int i, j, k; + short *rulep, *rp; + shifts *sp; + int length, nedges, done; + int state1, stateno, symbol1, symbol2; + short *shortp, *edge, *states; + short **new_includes; + + includes = NEW2(ngotos, short *); + edge = NEW2(ngotos + 1, short); + states = NEW2(maxrhs + 1, short); + + for (i = 0; i < ngotos; i++) { + nedges = 0; + state1 = from_state[i]; + symbol1 = accessing_symbol[to_state[i]]; + + for (rulep = derives[symbol1]; *rulep >= 0; rulep++) { + length = 1; + states[0] = state1; + stateno = state1; + + for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++) { + symbol2 = *rp; + sp = shift_table[stateno]; + k = sp->nshifts; + + for (j = 0; j < k; j++) { + stateno = sp->shift[j]; + if (accessing_symbol[stateno] == symbol2) + break; + } + + states[length++] = stateno; + } + + add_lookback_edge(stateno, *rulep, i); + + length--; + done = 0; + while (!done) { + done = 1; + rp--; + if (ISVAR(*rp)) { + stateno = states[--length]; + edge[nedges++] = map_goto(stateno, *rp); + if (nullable[*rp] && length > 0) + done = 0; + } + } + } + + if (nedges) { + includes[i] = shortp = NEW2(nedges + 1, short); + for (j = 0; j < nedges; j++) + shortp[j] = edge[j]; + shortp[nedges] = -1; + } + } + + new_includes = transpose(includes, ngotos); + + for (i = 0; i < ngotos; i++) + if (includes[i]) + free(includes[i]); + + free(includes); + + includes = new_includes; + + free(edge); + free(states); +} + +void +add_lookback_edge(int stateno, int ruleno, int gotono) +{ + int i, k, found; + shorts *sp; + + i = lookaheads[stateno]; + k = lookaheads[stateno + 1]; + found = 0; + while (!found && i < k) { + if (LAruleno[i] == ruleno) + found = 1; + else + ++i; + } + assert(found); + + sp = NEW(shorts); + sp->next = lookback[i]; + sp->value = gotono; + lookback[i] = sp; +} + + + +short ** +transpose(short **R, int n) +{ + short **new_R, **temp_R, *nedges, *sp; + int i, k; + + nedges = NEW2(n, short); + + for (i = 0; i < n; i++) { + sp = R[i]; + if (sp) { + while (*sp >= 0) + nedges[*sp++]++; + } + } + + new_R = NEW2(n, short *); + temp_R = NEW2(n, short *); + + for (i = 0; i < n; i++) { + k = nedges[i]; + if (k > 0) { + sp = NEW2(k + 1, short); + new_R[i] = sp; + temp_R[i] = sp; + sp[k] = -1; + } + } + + free(nedges); + + for (i = 0; i < n; i++) { + sp = R[i]; + if (sp) { + while (*sp >= 0) + *temp_R[*sp++]++ = i; + } + } + + free(temp_R); + + return (new_R); +} + + +void +compute_FOLLOWS(void) +{ + digraph(includes); +} + +void +compute_lookaheads(void) +{ + int i, n; + unsigned int *fp1, *fp2, *fp3; + shorts *sp, *next; + unsigned int *rowp; + + rowp = LA; + n = lookaheads[nstates]; + for (i = 0; i < n; i++) { + fp3 = rowp + tokensetsize; + for (sp = lookback[i]; sp; sp = sp->next) { + fp1 = rowp; + fp2 = F + tokensetsize * sp->value; + while (fp1 < fp3) + *fp1++ |= *fp2++; + } + rowp = fp3; + } + + for (i = 0; i < n; i++) + for (sp = lookback[i]; sp; sp = next) { + next = sp->next; + free(sp); + } + + free(lookback); + free(F); +} + +void +digraph(short **relation) +{ + int i; + + infinity = ngotos + 2; + INDEX = NEW2(ngotos + 1, short); + VERTICES = NEW2(ngotos + 1, short); + top = 0; + R = relation; + + memset(INDEX, 0, ngotos * sizeof(short)); + for (i = 0; i < ngotos; i++) + if (R[i]) + traverse(i); + + free(INDEX); + free(VERTICES); +} + + +void +traverse(int i) +{ + unsigned int *base, *fp1, *fp2, *fp3; + int j, height; + short *rp; + + VERTICES[++top] = i; + INDEX[i] = height = top; + + base = F + i * tokensetsize; + fp3 = base + tokensetsize; + + rp = R[i]; + if (rp) { + while ((j = *rp++) >= 0) { + if (INDEX[j] == 0) + traverse(j); + + if (INDEX[i] > INDEX[j]) + INDEX[i] = INDEX[j]; + + fp1 = base; + fp2 = F + j * tokensetsize; + + while (fp1 < fp3) + *fp1++ |= *fp2++; + } + } + + if (INDEX[i] == height) { + for (;;) { + j = VERTICES[top--]; + INDEX[j] = infinity; + + if (i == j) + break; + + fp1 = base; + fp2 = F + j * tokensetsize; + + while (fp1 < fp3) + *fp2++ = *fp1++; + } + } +} diff --git a/yacc/lr0.c b/yacc/lr0.c @@ -0,0 +1,504 @@ +/* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $ */ +/* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" + +extern short *itemset; +extern short *itemsetend; +extern unsigned *ruleset; + +int nstates; +core *first_state; +shifts *first_shift; +reductions *first_reduction; + +short get_state(int); +core *new_state(int); + +void allocate_itemsets(void); +void allocate_storage(void); +void append_states(void); +void free_storage(void); +void generate_states(void); +void initialize_states(void); +void new_itemsets(void); +void save_shifts(void); +void save_reductions(void); +void set_derives(void); +void print_derives(void); +void set_nullable(void); + +static core **state_set; +static core *this_state; +static core *last_state; +static shifts *last_shift; +static reductions *last_reduction; + +static int nshifts; +static short *shift_symbol; + +static short *redset; +static short *shiftset; + +static short **kernel_base; +static short **kernel_end; +static short *kernel_items; + +void +allocate_itemsets(void) +{ + short *itemp, *item_end; + int i, count, max, symbol; + short *symbol_count; + + count = 0; + symbol_count = NEW2(nsyms, short); + + item_end = ritem + nitems; + for (itemp = ritem; itemp < item_end; itemp++) { + symbol = *itemp; + if (symbol >= 0) { + count++; + symbol_count[symbol]++; + } + } + + kernel_base = NEW2(nsyms, short *); + kernel_items = NEW2(count, short); + + count = 0; + max = 0; + for (i = 0; i < nsyms; i++) { + kernel_base[i] = kernel_items + count; + count += symbol_count[i]; + if (max < symbol_count[i]) + max = symbol_count[i]; + } + + shift_symbol = symbol_count; + kernel_end = NEW2(nsyms, short *); +} + +void +allocate_storage(void) +{ + allocate_itemsets(); + shiftset = NEW2(nsyms, short); + redset = NEW2(nrules + 1, short); + state_set = NEW2(nitems, core *); +} + +void +append_states(void) +{ + int i, j, symbol; + +#ifdef TRACE + fprintf(stderr, "Entering append_states()\n"); +#endif + for (i = 1; i < nshifts; i++) { + symbol = shift_symbol[i]; + j = i; + while (j > 0 && shift_symbol[j - 1] > symbol) { + shift_symbol[j] = shift_symbol[j - 1]; + j--; + } + shift_symbol[j] = symbol; + } + + for (i = 0; i < nshifts; i++) { + symbol = shift_symbol[i]; + shiftset[i] = get_state(symbol); + } +} + +void +free_storage(void) +{ + free(shift_symbol); + free(redset); + free(shiftset); + free(kernel_base); + free(kernel_end); + free(kernel_items); + free(state_set); +} + + +void +generate_states(void) +{ + allocate_storage(); + itemset = NEW2(nitems, short); + ruleset = NEW2(WORDSIZE(nrules), unsigned); + set_first_derives(); + initialize_states(); + + while (this_state) { + closure(this_state->items, this_state->nitems); + save_reductions(); + new_itemsets(); + append_states(); + + if (nshifts > 0) + save_shifts(); + + this_state = this_state->next; + } + + finalize_closure(); + free_storage(); +} + + + +short +get_state(int symbol) +{ + int n, found, key; + short *isp1, *isp2, *iend; + core *sp; + +#ifdef TRACE + fprintf(stderr, "Entering get_state(%d)\n", symbol); +#endif + + isp1 = kernel_base[symbol]; + iend = kernel_end[symbol]; + n = iend - isp1; + + key = *isp1; + assert(0 <= key && key < nitems); + sp = state_set[key]; + if (sp) { + found = 0; + while (!found) { + if (sp->nitems == n) { + found = 1; + isp1 = kernel_base[symbol]; + isp2 = sp->items; + + while (found && isp1 < iend) { + if (*isp1++ != *isp2++) + found = 0; + } + } + if (!found) { + if (sp->link) { + sp = sp->link; + } else { + sp = sp->link = new_state(symbol); + found = 1; + } + } + } + } else { + state_set[key] = sp = new_state(symbol); + } + + return (sp->number); +} + + +void +initialize_states(void) +{ + int i; + short *start_derives; + core *p; + + start_derives = derives[start_symbol]; + for (i = 0; start_derives[i] >= 0; ++i) + continue; + + p = malloc(sizeof(core) + i * sizeof(short)); + if (p == NULL) + no_space(); + + p->next = 0; + p->link = 0; + p->number = 0; + p->accessing_symbol = 0; + p->nitems = i; + + for (i = 0; start_derives[i] >= 0; ++i) + p->items[i] = rrhs[start_derives[i]]; + + first_state = last_state = this_state = p; + nstates = 1; +} + +void +new_itemsets(void) +{ + int i, shiftcount; + short *isp, *ksp; + int symbol; + + memset(kernel_end, 0, nsyms * sizeof(short *)); + + shiftcount = 0; + isp = itemset; + while (isp < itemsetend) { + i = *isp++; + symbol = ritem[i]; + if (symbol > 0) { + ksp = kernel_end[symbol]; + if (!ksp) { + shift_symbol[shiftcount++] = symbol; + ksp = kernel_base[symbol]; + } + *ksp++ = i + 1; + kernel_end[symbol] = ksp; + } + } + + nshifts = shiftcount; +} + + + +core * +new_state(int symbol) +{ + int n; + core *p; + short *isp1, *isp2, *iend; + +#ifdef TRACE + fprintf(stderr, "Entering new_state(%d)\n", symbol); +#endif + + if (nstates >= MAXSHORT) + fatal("too many states"); + + isp1 = kernel_base[symbol]; + iend = kernel_end[symbol]; + n = iend - isp1; + + p = allocate(sizeof(core) + (n - 1) * sizeof(short)); + p->accessing_symbol = symbol; + p->number = nstates; + p->nitems = n; + + isp2 = p->items; + while (isp1 < iend) + *isp2++ = *isp1++; + + last_state->next = p; + last_state = p; + + nstates++; + + return (p); +} + + +void +save_shifts(void) +{ + shifts *p; + short *sp1, *sp2, *send; + + p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short)); + + p->number = this_state->number; + p->nshifts = nshifts; + + sp1 = shiftset; + sp2 = p->shift; + send = shiftset + nshifts; + + while (sp1 < send) + *sp2++ = *sp1++; + + if (last_shift) { + last_shift->next = p; + last_shift = p; + } else { + first_shift = p; + last_shift = p; + } +} + + +void +save_reductions(void) +{ + short *isp, *rp1, *rp2; + int item, count; + reductions *p; + short *rend; + + count = 0; + for (isp = itemset; isp < itemsetend; isp++) { + item = ritem[*isp]; + if (item < 0) { + redset[count++] = -item; + } + } + + if (count) { + p = allocate(sizeof(reductions) + (count - 1) * sizeof(short)); + + p->number = this_state->number; + p->nreds = count; + + rp1 = redset; + rp2 = p->rules; + rend = rp1 + count; + + while (rp1 < rend) + *rp2++ = *rp1++; + + if (last_reduction) { + last_reduction->next = p; + last_reduction = p; + } else { + first_reduction = p; + last_reduction = p; + } + } +} + +void +set_derives(void) +{ + int i, k, lhs; + short *rules; + + derives = NEW2(nsyms, short *); + rules = NEW2(nvars + nrules, short); + + k = 0; + for (lhs = start_symbol; lhs < nsyms; lhs++) { + derives[lhs] = rules + k; + for (i = 0; i < nrules; i++) { + if (rlhs[i] == lhs) { + rules[k] = i; + k++; + } + } + rules[k] = -1; + k++; + } + +#ifdef DEBUG + print_derives(); +#endif +} + +void +free_derives(void) +{ + free(derives[start_symbol]); + free(derives); +} + +#ifdef DEBUG +void +print_derives(void) +{ + int i; + short *sp; + + printf("\nDERIVES\n\n"); + + for (i = start_symbol; i < nsyms; i++) { + printf("%s derives ", symbol_name[i]); + for (sp = derives[i]; *sp >= 0; sp++) { + printf(" %d", *sp); + } + putchar('\n'); + } + + putchar('\n'); +} +#endif + +void +set_nullable(void) +{ + int i, j; + int empty; + int done; + + nullable = calloc(1, nsyms); + if (nullable == NULL) + no_space(); + + done = 0; + while (!done) { + done = 1; + for (i = 1; i < nitems; i++) { + empty = 1; + while ((j = ritem[i]) >= 0) { + if (!nullable[j]) + empty = 0; + ++i; + } + if (empty) { + j = rlhs[-j]; + if (!nullable[j]) { + nullable[j] = 1; + done = 0; + } + } + } + } + +#ifdef DEBUG + for (i = 0; i < nsyms; i++) { + if (nullable[i]) + printf("%s is nullable\n", symbol_name[i]); + else + printf("%s is not nullable\n", symbol_name[i]); + } +#endif +} + +void +free_nullable(void) +{ + free(nullable); +} + +void +lr0(void) +{ + set_derives(); + set_nullable(); + generate_states(); +} diff --git a/yacc/main.c b/yacc/main.c @@ -0,0 +1,362 @@ +/* $OpenBSD: main.c,v 1.26 2014/03/13 00:33:55 tedu Exp $ */ +/* $NetBSD: main.c,v 1.5 1996/03/19 03:21:38 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include <sys/types.h> +#include <fcntl.h> +#include <paths.h> +#include <signal.h> +#include <stdlib.h> +#include <unistd.h> +#include "defs.h" + +char dflag; +char lflag; +char rflag; +char tflag; +char vflag; + +char *symbol_prefix; +char *file_prefix = "y"; + +int lineno; +int outline; + +int explicit_file_name; + +char *action_file_name; +char *code_file_name; +char *defines_file_name; +char *input_file_name = ""; +char *output_file_name; +char *text_file_name; +char *union_file_name; +char *verbose_file_name; + +FILE *action_file; /* a temp file, used to save actions associated */ + /* with rules until the parser is written */ +FILE *code_file; /* y.code.c (used when the -r option is specified) */ +FILE *defines_file; /* y.tab.h */ +FILE *input_file; /* the input file */ +FILE *output_file; /* y.tab.c */ +FILE *text_file; /* a temp file, used to save text until all */ + /* symbols have been defined */ +FILE *union_file; /* a temp file, used to save the union */ + /* definition until all symbol have been */ + /* defined */ +FILE *verbose_file; /* y.output */ + +int nitems; +int nrules; +int nsyms; +int ntokens; +int nvars; + +int start_symbol; +char **symbol_name; +short *symbol_value; +short *symbol_prec; +char *symbol_assoc; + +short *ritem; +short *rlhs; +short *rrhs; +short *rprec; +char *rassoc; +short **derives; +char *nullable; + +void onintr(int); +void set_signals(void); +void usage(void); +void getargs(int, char *[]); +void create_file_names(void); +void open_files(void); + +volatile sig_atomic_t sigdie; + +void +done(int k) +{ + if (action_file) + unlink(action_file_name); + if (text_file) + unlink(text_file_name); + if (union_file) + unlink(union_file_name); + if (sigdie) + _exit(k); + exit(k); +} + + +void +onintr(int signo) +{ + sigdie = 1; + done(1); +} + + +void +set_signals(void) +{ +#ifdef SIGINT + if (signal(SIGINT, SIG_IGN) != SIG_IGN) + signal(SIGINT, onintr); +#endif +#ifdef SIGTERM + if (signal(SIGTERM, SIG_IGN) != SIG_IGN) + signal(SIGTERM, onintr); +#endif +#ifdef SIGHUP + if (signal(SIGHUP, SIG_IGN) != SIG_IGN) + signal(SIGHUP, onintr); +#endif +} + + +void +usage(void) +{ + fprintf(stderr, "usage: %s [-dlrtv] [-b file_prefix] [-o output_file] [-p symbol_prefix] file\n", __progname); + exit(1); +} + + +void +getargs(int argc, char *argv[]) +{ + int ch; + + while ((ch = getopt(argc, argv, "b:dlo:p:rtv")) != -1) { + switch (ch) { + case 'b': + file_prefix = optarg; + break; + + case 'd': + dflag = 1; + break; + + case 'l': + lflag = 1; + break; + + case 'o': + output_file_name = optarg; + explicit_file_name = 1; + break; + + case 'p': + symbol_prefix = optarg; + break; + + case 'r': + rflag = 1; + break; + + case 't': + tflag = 1; + break; + + case 'v': + vflag = 1; + break; + + default: + usage(); + } + } + argc -= optind; + argv += optind; + + if (argc != 1) + usage(); + if (strcmp(*argv, "-") == 0) + input_file = stdin; + else + input_file_name = *argv; +} + + +void * +allocate(size_t n) +{ + void *v; + + v = NULL; + if (n) { + v = calloc(1, n); + if (!v) + no_space(); + } + return (v); +} + +#define TEMPNAME(s, c, d, l) \ + (asprintf(&(s), "%.*s/yacc.%xXXXXXXXXXX", (int)(l), (d), (c))) + +void +create_file_names(void) +{ + size_t len; + char *tmpdir; + + if ((tmpdir = getenv("TMPDIR")) == NULL || *tmpdir == '\0') + tmpdir = _PATH_TMP; + + len = strlen(tmpdir); + if (tmpdir[len - 1] == '/') + len--; + + if (TEMPNAME(action_file_name, 'a', tmpdir, len) == -1 || + TEMPNAME(text_file_name, 'r', tmpdir, len) == -1 || + TEMPNAME(union_file_name, 'u', tmpdir, len) == -1) + no_space(); + + if (output_file_name == NULL) { + if (asprintf(&output_file_name, "%s%s", file_prefix, OUTPUT_SUFFIX) + == -1) + no_space(); + } + if (rflag) { + if (asprintf(&code_file_name, "%s%s", file_prefix, CODE_SUFFIX) == -1) + no_space(); + } else + code_file_name = output_file_name; + + if (dflag) { + if (explicit_file_name) { + char *suffix; + + defines_file_name = strdup(output_file_name); + if (defines_file_name == 0) + no_space(); + + /* does the output_file_name have a known suffix */ + if ((suffix = strrchr(output_file_name, '.')) != 0 && + (!strcmp(suffix, ".c") || /* good, old-fashioned C */ + !strcmp(suffix, ".C") || /* C++, or C on Windows */ + !strcmp(suffix, ".cc") || /* C++ */ + !strcmp(suffix, ".cxx") || /* C++ */ + !strcmp(suffix, ".cpp"))) {/* C++ (Windows) */ + strncpy(defines_file_name, output_file_name, + suffix - output_file_name + 1); + defines_file_name[suffix - output_file_name + 1] = 'h'; + defines_file_name[suffix - output_file_name + 2] = '\0'; + } else { + fprintf(stderr, "%s: suffix of output file name %s" + " not recognized, no -d file generated.\n", + __progname, output_file_name); + dflag = 0; + free(defines_file_name); + defines_file_name = 0; + } + } else { + if (asprintf(&defines_file_name, "%s%s", file_prefix, + DEFINES_SUFFIX) == -1) + no_space(); + } + } + if (vflag) { + if (asprintf(&verbose_file_name, "%s%s", file_prefix, + VERBOSE_SUFFIX) == -1) + no_space(); + } +} + + +void +open_files(void) +{ + int fd; + + create_file_names(); + + if (input_file == 0) { + input_file = fopen(input_file_name, "r"); + if (input_file == 0) + open_error(input_file_name); + } + fd = mkstemp(action_file_name); + if (fd == -1 || (action_file = fdopen(fd, "w")) == NULL) + open_error(action_file_name); + + fd = mkstemp(text_file_name); + if (fd == -1 || (text_file = fdopen(fd, "w")) == NULL) + open_error(text_file_name); + + if (vflag) { + verbose_file = fopen(verbose_file_name, "w"); + if (verbose_file == 0) + open_error(verbose_file_name); + } + if (dflag) { + defines_file = fopen(defines_file_name, "w"); + if (defines_file == NULL) + open_write_error(defines_file_name); + fd = mkstemp(union_file_name); + if (fd == -1 || (union_file = fdopen(fd, "w")) == NULL) + open_error(union_file_name); + } + output_file = fopen(output_file_name, "w"); + if (output_file == 0) + open_error(output_file_name); + + if (rflag) { + code_file = fopen(code_file_name, "w"); + if (code_file == 0) + open_error(code_file_name); + } else + code_file = output_file; +} + + +int +main(int argc, char *argv[]) +{ + set_signals(); + getargs(argc, argv); + open_files(); + reader(); + lr0(); + lalr(); + make_parser(); + verbose(); + output(); + done(0); + /* NOTREACHED */ + return (0); +} diff --git a/yacc/mkpar.c b/yacc/mkpar.c @@ -0,0 +1,370 @@ +/* $OpenBSD: mkpar.c,v 1.18 2014/03/13 00:59:34 tedu Exp $ */ +/* $NetBSD: mkpar.c,v 1.4 1996/03/19 03:21:39 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" + +action **parser; +int SRtotal; +int SRexpect = 0; +int RRtotal; +short *SRconflicts; +short *RRconflicts; +short *defred; +short *rules_used; +short nunused; +short final_state; + +static int SRcount; +static int RRcount; + +extern action *parse_actions(); +extern action *get_shifts(); +extern action *add_reductions(); +extern action *add_reduce(); + +short sole_reduction(int); +void free_action_row(action *); + +void find_final_state(void); +void unused_rules(void); +void remove_conflicts(void); +void total_conflicts(void); +void defreds(void); + + +void +make_parser(void) +{ + int i; + + parser = NEW2(nstates, action *); + for (i = 0; i < nstates; i++) + parser[i] = parse_actions(i); + + find_final_state(); + remove_conflicts(); + unused_rules(); + if (SRtotal + RRtotal > 0) + total_conflicts(); + defreds(); +} + + +action * +parse_actions(int stateno) +{ + action *actions; + + actions = get_shifts(stateno); + actions = add_reductions(stateno, actions); + return (actions); +} + + +action * +get_shifts(int stateno) +{ + action *actions, *temp; + shifts *sp; + short *to_state; + int i, k; + int symbol; + + actions = 0; + sp = shift_table[stateno]; + if (sp) { + to_state = sp->shift; + for (i = sp->nshifts - 1; i >= 0; i--) { + k = to_state[i]; + symbol = accessing_symbol[k]; + if (ISTOKEN(symbol)) { + temp = NEW(action); + temp->next = actions; + temp->symbol = symbol; + temp->number = k; + temp->prec = symbol_prec[symbol]; + temp->action_code = SHIFT; + temp->assoc = symbol_assoc[symbol]; + actions = temp; + } + } + } + return (actions); +} + +action * +add_reductions(int stateno, action * actions) +{ + int i, j, m, n; + int ruleno, tokensetsize; + unsigned *rowp; + + tokensetsize = WORDSIZE(ntokens); + m = lookaheads[stateno]; + n = lookaheads[stateno + 1]; + for (i = m; i < n; i++) { + ruleno = LAruleno[i]; + rowp = LA + i * tokensetsize; + for (j = ntokens - 1; j >= 0; j--) { + if (BIT(rowp, j)) + actions = add_reduce(actions, ruleno, j); + } + } + return (actions); +} + + +action * +add_reduce(action * actions, int ruleno, int symbol) +{ + action *temp, *prev, *next; + + prev = 0; + for (next = actions; next && next->symbol < symbol; next = next->next) + prev = next; + + while (next && next->symbol == symbol && next->action_code == SHIFT) { + prev = next; + next = next->next; + } + + while (next && next->symbol == symbol && + next->action_code == REDUCE && next->number < ruleno) { + prev = next; + next = next->next; + } + + temp = NEW(action); + temp->next = next; + temp->symbol = symbol; + temp->number = ruleno; + temp->prec = rprec[ruleno]; + temp->action_code = REDUCE; + temp->assoc = rassoc[ruleno]; + + if (prev) + prev->next = temp; + else + actions = temp; + + return (actions); +} + + +void +find_final_state(void) +{ + int goal, i; + short *to_state; + shifts *p; + + p = shift_table[0]; + to_state = p->shift; + goal = ritem[1]; + for (i = p->nshifts - 1; i >= 0; --i) { + final_state = to_state[i]; + if (accessing_symbol[final_state] == goal) + break; + } +} + + +void +unused_rules(void) +{ + int i; + action *p; + + rules_used = calloc(nrules, sizeof(short)); + if (rules_used == NULL) + no_space(); + + for (i = 0; i < nstates; ++i) { + for (p = parser[i]; p; p = p->next) { + if (p->action_code == REDUCE && p->suppressed == 0) + rules_used[p->number] = 1; + } + } + + nunused = 0; + for (i = 3; i < nrules; ++i) + if (!rules_used[i]) + ++nunused; + + if (nunused) { + if (nunused == 1) + fprintf(stderr, "%s: 1 rule never reduced\n", __progname); + else + fprintf(stderr, "%s: %d rules never reduced\n", __progname, + nunused); + } +} + + +void +remove_conflicts(void) +{ + int i; + int symbol; + action *p, *pref = NULL; + + SRtotal = 0; + RRtotal = 0; + SRconflicts = NEW2(nstates, short); + RRconflicts = NEW2(nstates, short); + for (i = 0; i < nstates; i++) { + SRcount = 0; + RRcount = 0; + symbol = -1; + for (p = parser[i]; p; p = p->next) { + if (p->symbol != symbol) { + pref = p; + symbol = p->symbol; + } else if (i == final_state && symbol == 0) { + SRcount++; + p->suppressed = 1; + } else if (pref->action_code == SHIFT) { + if (pref->prec > 0 && p->prec > 0) { + if (pref->prec < p->prec) { + pref->suppressed = 2; + pref = p; + } else if (pref->prec > p->prec) { + p->suppressed = 2; + } else if (pref->assoc == LEFT) { + pref->suppressed = 2; + pref = p; + } else if (pref->assoc == RIGHT) { + p->suppressed = 2; + } else { + pref->suppressed = 2; + p->suppressed = 2; + } + } else { + SRcount++; + p->suppressed = 1; + } + } else { + RRcount++; + p->suppressed = 1; + } + } + SRtotal += SRcount; + RRtotal += RRcount; + SRconflicts[i] = SRcount; + RRconflicts[i] = RRcount; + } +} + + +void +total_conflicts(void) +{ + /* Warn if s/r != expect or if any r/r */ + if ((SRtotal != SRexpect) || RRtotal) { + if (SRtotal == 1) + fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n", + input_file_name, __progname); + else if (SRtotal > 1) + fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n", + input_file_name, __progname, SRtotal); + } + if (RRtotal == 1) + fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n", + input_file_name, __progname); + else if (RRtotal > 1) + fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n", + input_file_name, __progname, RRtotal); +} + + +short +sole_reduction(int stateno) +{ + int count; + short ruleno; + action *p; + + count = 0; + ruleno = 0; + for (p = parser[stateno]; p; p = p->next) { + if (p->action_code == SHIFT && p->suppressed == 0) + return (0); + else if (p->action_code == REDUCE && p->suppressed == 0) { + if (ruleno > 0 && p->number != ruleno) + return (0); + if (p->symbol != 1) + ++count; + ruleno = p->number; + } + } + + if (count == 0) + return (0); + return (ruleno); +} + + +void +defreds(void) +{ + int i; + + defred = NEW2(nstates, short); + for (i = 0; i < nstates; i++) + defred[i] = sole_reduction(i); +} + +void +free_action_row(action * p) +{ + action *q; + + while (p) { + q = p->next; + free(p); + p = q; + } +} + +void +free_parser(void) +{ + int i; + + for (i = 0; i < nstates; i++) + free_action_row(parser[i]); + + free(parser); +} diff --git a/yacc/output.c b/yacc/output.c @@ -0,0 +1,1205 @@ +/* $OpenBSD: output.c,v 1.23 2014/03/13 01:18:22 tedu Exp $ */ +/* $NetBSD: output.c,v 1.4 1996/03/19 03:21:41 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" + +static int nvectors; +static int nentries; +static short **froms; +static short **tos; +static short *tally; +static short *width; +static short *state_count; +static short *order; +static short *base; +static short *pos; +static int maxtable; +static short *table; +static short *check; +static int lowzero; +static int high; + +void output_prefix(void); +void output_rule_data(void); +void output_yydefred(void); +void output_actions(void); +void token_actions(void); +void goto_actions(void); +int default_goto(int); +void save_column(int, int); +void sort_actions(void); +void pack_table(void); +int matching_vector(int); +int pack_vector(int); +void output_base(void); +void output_table(void); +void output_check(void); +int is_C_identifier(char *); +void output_defines(void); +void output_stored_text(void); +void output_debug(void); +void output_stype(void); +void output_trailing_text(void); +void output_semantic_actions(void); +void free_itemsets(void); +void free_shifts(void); +void free_reductions(void); + +void +output(void) +{ + free_itemsets(); + free_shifts(); + free_reductions(); + output_prefix(); + output_stored_text(); + output_defines(); + output_rule_data(); + output_yydefred(); + output_actions(); + free_parser(); + output_debug(); + output_stype(); + if (rflag) + write_section(tables); + write_section(header); + output_trailing_text(); + write_section(body); + output_semantic_actions(); + write_section(trailer); +} + + +void +output_prefix(void) +{ + if (symbol_prefix == NULL) + symbol_prefix = "yy"; + else { + ++outline; + fprintf(code_file, "#define yyparse %sparse\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yylex %slex\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyerror %serror\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yychar %schar\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyval %sval\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yylval %slval\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yydebug %sdebug\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yynerrs %snerrs\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyerrflag %serrflag\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyss %sss\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yysslim %ssslim\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyssp %sssp\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyvs %svs\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyvsp %svsp\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yystacksize %sstacksize\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yylhs %slhs\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yylen %slen\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yydefred %sdefred\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yydgoto %sdgoto\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yysindex %ssindex\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyrindex %srindex\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yygindex %sgindex\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yytable %stable\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yycheck %scheck\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyname %sname\n", symbol_prefix); + ++outline; + fprintf(code_file, "#define yyrule %srule\n", symbol_prefix); + } + ++outline; + fprintf(code_file, "#define YYPREFIX \"%s\"\n", symbol_prefix); +} + + +void +output_rule_data(void) +{ + int i; + int j; + + fprintf(output_file, + "const short %slhs[] =\n" + "\t{%42d,", symbol_prefix, symbol_value[start_symbol]); + + j = 10; + for (i = 3; i < nrules; i++) { + if (j >= 10) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } else + ++j; + fprintf(output_file, "%5d,", symbol_value[rlhs[i]]); + } + if (!rflag) + outline += 2; + fprintf(output_file, "\n};\n"); + + fprintf(output_file, + "const short %slen[] =\n" + "\t{%42d,", symbol_prefix, 2); + + j = 10; + for (i = 3; i < nrules; i++) { + if (j >= 10) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } else + j++; + fprintf(output_file, "%5d,", rrhs[i + 1] - rrhs[i] - 1); + } + if (!rflag) + outline += 2; + fprintf(output_file, "\n};\n"); +} + + +void +output_yydefred(void) +{ + int i, j; + + fprintf(output_file, + "const short %sdefred[] =\n" + "\t{%39d,", + symbol_prefix, (defred[0] ? defred[0] - 2 : 0)); + + j = 10; + for (i = 1; i < nstates; i++) { + if (j < 10) + ++j; + else { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } + fprintf(output_file, "%5d,", (defred[i] ? defred[i] - 2 : 0)); + } + + if (!rflag) + outline += 2; + fprintf(output_file, "\n};\n"); +} + + +void +output_actions(void) +{ + nvectors = 2 * nstates + nvars; + + froms = NEW2(nvectors, short *); + tos = NEW2(nvectors, short *); + tally = NEW2(nvectors, short); + width = NEW2(nvectors, short); + + token_actions(); + free(lookaheads); + free(LA); + free(LAruleno); + free(accessing_symbol); + + goto_actions(); + free(goto_map + ntokens); + free(from_state); + free(to_state); + + sort_actions(); + pack_table(); + output_base(); + output_table(); + output_check(); +} + + +void +token_actions(void) +{ + int i, j; + int shiftcount, reducecount; + int max, min; + short *actionrow, *r, *s; + action *p; + + actionrow = NEW2(2*ntokens, short); + for (i = 0; i < nstates; ++i) { + if (parser[i]) { + for (j = 0; j < 2 * ntokens; ++j) + actionrow[j] = 0; + shiftcount = 0; + reducecount = 0; + for (p = parser[i]; p; p = p->next) { + if (p->suppressed == 0) { + if (p->action_code == SHIFT) { + ++shiftcount; + actionrow[p->symbol] = p->number; + } else if (p->action_code == REDUCE && + p->number != defred[i]) { + ++reducecount; + actionrow[p->symbol + ntokens] = p->number; + } + } + } + + tally[i] = shiftcount; + tally[nstates+i] = reducecount; + width[i] = 0; + width[nstates+i] = 0; + if (shiftcount > 0) { + froms[i] = r = NEW2(shiftcount, short); + tos[i] = s = NEW2(shiftcount, short); + min = MAXSHORT; + max = 0; + for (j = 0; j < ntokens; ++j) { + if (actionrow[j]) { + if (min > symbol_value[j]) + min = symbol_value[j]; + if (max < symbol_value[j]) + max = symbol_value[j]; + *r++ = symbol_value[j]; + *s++ = actionrow[j]; + } + } + width[i] = max - min + 1; + } + if (reducecount > 0) { + froms[nstates+i] = r = NEW2(reducecount, short); + tos[nstates+i] = s = NEW2(reducecount, short); + min = MAXSHORT; + max = 0; + for (j = 0; j < ntokens; ++j) { + if (actionrow[ntokens+j]) { + if (min > symbol_value[j]) + min = symbol_value[j]; + if (max < symbol_value[j]) + max = symbol_value[j]; + *r++ = symbol_value[j]; + *s++ = actionrow[ntokens+j] - 2; + } + } + width[nstates+i] = max - min + 1; + } + } + } + free(actionrow); +} + +void +goto_actions(void) +{ + int i, j, k; + + state_count = NEW2(nstates, short); + + k = default_goto(start_symbol + 1); + fprintf(output_file, "const short %sdgoto[] =\n" + "\t{%40d,", symbol_prefix, k); + save_column(start_symbol + 1, k); + + j = 10; + for (i = start_symbol + 2; i < nsyms; i++) { + if (j >= 10) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } else + ++j; + + k = default_goto(i); + fprintf(output_file, "%5d,", k); + save_column(i, k); + } + + if (!rflag) + outline += 2; + fprintf(output_file, "\n};\n"); + free(state_count); +} + +int +default_goto(int symbol) +{ + int i; + int m; + int n; + int default_state; + int max; + + m = goto_map[symbol]; + n = goto_map[symbol + 1]; + + if (m == n) + return (0); + + memset(state_count, 0, nstates * sizeof(short)); + + for (i = m; i < n; i++) + state_count[to_state[i]]++; + + max = 0; + default_state = 0; + for (i = 0; i < nstates; i++) { + if (state_count[i] > max) { + max = state_count[i]; + default_state = i; + } + } + + return (default_state); +} + + + +void +save_column(int symbol, int default_state) +{ + int i; + int m; + int n; + short *sp; + short *sp1; + short *sp2; + int count; + int symno; + + m = goto_map[symbol]; + n = goto_map[symbol + 1]; + + count = 0; + for (i = m; i < n; i++) { + if (to_state[i] != default_state) + ++count; + } + if (count == 0) + return; + + symno = symbol_value[symbol] + 2*nstates; + + froms[symno] = sp1 = sp = NEW2(count, short); + tos[symno] = sp2 = NEW2(count, short); + + for (i = m; i < n; i++) { + if (to_state[i] != default_state) { + *sp1++ = from_state[i]; + *sp2++ = to_state[i]; + } + } + + tally[symno] = count; + width[symno] = sp1[-1] - sp[0] + 1; +} + +void +sort_actions(void) +{ + int i; + int j; + int k; + int t; + int w; + + order = NEW2(nvectors, short); + nentries = 0; + + for (i = 0; i < nvectors; i++) { + if (tally[i] > 0) { + t = tally[i]; + w = width[i]; + j = nentries - 1; + + while (j >= 0 && (width[order[j]] < w)) + j--; + + while (j >= 0 && (width[order[j]] == w) && + (tally[order[j]] < t)) + j--; + + for (k = nentries - 1; k > j; k--) + order[k + 1] = order[k]; + + order[j + 1] = i; + nentries++; + } + } +} + + +void +pack_table(void) +{ + int i; + int place; + int state; + + base = NEW2(nvectors, short); + pos = NEW2(nentries, short); + + maxtable = 1000; + table = NEW2(maxtable, short); + check = NEW2(maxtable, short); + + lowzero = 0; + high = 0; + + for (i = 0; i < maxtable; i++) + check[i] = -1; + + for (i = 0; i < nentries; i++) { + state = matching_vector(i); + + if (state < 0) + place = pack_vector(i); + else + place = base[state]; + + pos[i] = place; + base[order[i]] = place; + } + + for (i = 0; i < nvectors; i++) { + if (froms[i]) + free(froms[i]); + if (tos[i]) + free(tos[i]); + } + + free(froms); + free(tos); + free(pos); +} + + +/* The function matching_vector determines if the vector specified by */ +/* the input parameter matches a previously considered vector. The */ +/* test at the start of the function checks if the vector represents */ +/* a row of shifts over terminal symbols or a row of reductions, or a */ +/* column of shifts over a nonterminal symbol. Berkeley Yacc does not */ +/* check if a column of shifts over a nonterminal symbols matches a */ +/* previously considered vector. Because of the nature of LR parsing */ +/* tables, no two columns can match. Therefore, the only possible */ +/* match would be between a row and a column. Such matches are */ +/* unlikely. Therefore, to save time, no attempt is made to see if a */ +/* column matches a previously considered vector. */ +/* */ +/* Matching_vector is poorly designed. The test could easily be made */ +/* faster. Also, it depends on the vectors being in a specific */ +/* order. */ + +int +matching_vector(int vector) +{ + int i, j, k, t, w, match, prev; + + i = order[vector]; + if (i >= 2*nstates) + return (-1); + + t = tally[i]; + w = width[i]; + + for (prev = vector - 1; prev >= 0; prev--) { + j = order[prev]; + if (width[j] != w || tally[j] != t) + return (-1); + + match = 1; + for (k = 0; match && k < t; k++) { + if (tos[j][k] != tos[i][k] || + froms[j][k] != froms[i][k]) + match = 0; + } + + if (match) + return (j); + } + + return (-1); +} + + + +int +pack_vector(int vector) +{ + int i, j, k, l; + int t, loc, ok; + short *from, *to; + int newmax; + + i = order[vector]; + t = tally[i]; + assert(t); + + from = froms[i]; + to = tos[i]; + + j = lowzero - from[0]; + for (k = 1; k < t; ++k) + if (lowzero - from[k] > j) + j = lowzero - from[k]; + for (;; ++j) { + if (j == 0) + continue; + ok = 1; + for (k = 0; ok && k < t; k++) { + loc = j + from[k]; + if (loc >= maxtable) { + if (loc >= MAXTABLE) + fatal("maximum table size exceeded"); + + newmax = maxtable; + do { + newmax += 200; + } while (newmax <= loc); + table = realloc(table, newmax * sizeof(short)); + if (table == NULL) + no_space(); + check = realloc(check, newmax * sizeof(short)); + if (check == NULL) + no_space(); + for (l = maxtable; l < newmax; ++l) { + table[l] = 0; + check[l] = -1; + } + maxtable = newmax; + } + + if (check[loc] != -1) + ok = 0; + } + for (k = 0; ok && k < vector; k++) { + if (pos[k] == j) + ok = 0; + } + if (ok) { + for (k = 0; k < t; k++) { + loc = j + from[k]; + table[loc] = to[k]; + check[loc] = from[k]; + if (loc > high) + high = loc; + } + + while (check[lowzero] != -1) + ++lowzero; + + return (j); + } + } +} + + + +void +output_base(void) +{ + int i, j; + + fprintf(output_file, "const short %ssindex[] =\n" + "\t{%39d,", symbol_prefix, base[0]); + + j = 10; + for (i = 1; i < nstates; i++) { + if (j >= 10) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } else + ++j; + fprintf(output_file, "%5d,", base[i]); + } + + if (!rflag) + outline += 2; + fprintf(output_file, "};\n" + "const short %srindex[] =\n" + "\t{%39d,", symbol_prefix, base[nstates]); + + j = 10; + for (i = nstates + 1; i < 2*nstates; i++) { + if (j >= 10) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } else + ++j; + fprintf(output_file, "%5d,", base[i]); + } + + if (!rflag) + outline += 2; + fprintf(output_file, "};\n" + "const short %sgindex[] =\n" + "\t{%39d,", symbol_prefix, base[2*nstates]); + + j = 10; + for (i = 2*nstates + 1; i < nvectors - 1; i++) { + if (j >= 10) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } else + ++j; + fprintf(output_file, "%5d,", base[i]); + } + + if (!rflag) + outline += 2; + fprintf(output_file, "\n};\n"); + free(base); +} + + +void +output_table(void) +{ + int i, j; + + ++outline; + fprintf(code_file, "#define YYTABLESIZE %d\n", high); + fprintf(output_file, "const short %stable[] =\n" + "\t{%40d,", symbol_prefix, table[0]); + + j = 10; + for (i = 1; i <= high; i++) { + if (j >= 10) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } else + ++j; + fprintf(output_file, "%5d,", table[i]); + } + + if (!rflag) + outline += 2; + fprintf(output_file, "\n};\n"); + free(table); +} + + +void +output_check(void) +{ + int i, j; + + fprintf(output_file, "const short %scheck[] =\n" + "\t{%40d,", symbol_prefix, check[0]); + + j = 10; + for (i = 1; i <= high; i++) { + if (j >= 10) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 1; + } else + ++j; + fprintf(output_file, "%5d,", check[i]); + } + + if (!rflag) + outline += 2; + fprintf(output_file, "\n};\n"); + free(check); +} + + +int +is_C_identifier(char *name) +{ + char *s; + int c; + + s = name; + c = (unsigned char)*s; + if (c == '"') { + c = (unsigned char)*++s; + if (!isalpha(c) && c != '_' && c != '$') + return (0); + while ((c = (unsigned char)*++s) != '"') { + if (!isalnum(c) && c != '_' && c != '$') + return (0); + } + return (1); + } + + if (!isalpha(c) && c != '_' && c != '$') + return (0); + while ((c = (unsigned char)*++s)) { + if (!isalnum(c) && c != '_' && c != '$') + return (0); + } + return (1); +} + + +void +output_defines(void) +{ + int c, i; + char *s; + + for (i = 2; i < ntokens; ++i) { + s = symbol_name[i]; + if (is_C_identifier(s)) { + fprintf(code_file, "#define "); + if (dflag) + fprintf(defines_file, "#define "); + c = (unsigned char)*s; + if (c == '"') { + while ((c = (unsigned char)*++s) != '"') { + putc(c, code_file); + if (dflag) + putc(c, defines_file); + } + } else { + do { + putc(c, code_file); + if (dflag) + putc(c, defines_file); + } while ((c = (unsigned char)*++s)); + } + ++outline; + fprintf(code_file, " %d\n", symbol_value[i]); + if (dflag) + fprintf(defines_file, " %d\n", symbol_value[i]); + } + } + + ++outline; + fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]); + + if (dflag && unionized) { + fclose(union_file); + union_file = fopen(union_file_name, "r"); + if (union_file == NULL) + open_error(union_file_name); + while ((c = getc(union_file)) != EOF) + putc(c, defines_file); + fprintf(defines_file, " YYSTYPE;\n"); + fprintf(defines_file, "#endif /* YYSTYPE_DEFINED */\n"); + fprintf(defines_file, "extern YYSTYPE %slval;\n", + symbol_prefix); + } +} + + +void +output_stored_text(void) +{ + int c; + FILE *in, *out; + + fclose(text_file); + text_file = fopen(text_file_name, "r"); + if (text_file == NULL) + open_error(text_file_name); + in = text_file; + if ((c = getc(in)) == EOF) + return; + out = code_file; + if (c == '\n') + ++outline; + putc(c, out); + while ((c = getc(in)) != EOF) { + if (c == '\n') + ++outline; + putc(c, out); + } + if (!lflag) + fprintf(out, line_format, ++outline + 1, code_file_name); +} + + +void +output_debug(void) +{ + int i, j, k, max; + char **symnam, *s; + + ++outline; + fprintf(code_file, "#define YYFINAL %d\n", final_state); + outline += 3; + fprintf(code_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n", + tflag); + if (rflag) + fprintf(output_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n", + tflag); + + max = 0; + for (i = 2; i < ntokens; ++i) + if (symbol_value[i] > max) + max = symbol_value[i]; + ++outline; + fprintf(code_file, "#define YYMAXTOKEN %d\n", max); + + symnam = calloc(max+1, sizeof(char *)); + if (symnam == NULL) + no_space(); + + for (i = ntokens - 1; i >= 2; --i) + symnam[symbol_value[i]] = symbol_name[i]; + symnam[0] = "end-of-file"; + + if (!rflag) + ++outline; + fprintf(output_file, + "#if YYDEBUG\n" + "const char * const %sname[] =\n" + "\t{", symbol_prefix); + j = 80; + for (i = 0; i <= max; ++i) { + if ((s = symnam[i]) != '\0') { + if (s[0] == '"') { + k = 7; + while (*++s != '"') { + ++k; + if (*s == '\\') { + k += 2; + if (*++s == '\\') + ++k; + } + } + j += k; + if (j > 80) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = k; + } + fprintf(output_file, "\"\\\""); + s = symnam[i]; + while (*++s != '"') { + if (*s == '\\') { + fprintf(output_file, "\\\\"); + if (*++s == '\\') + fprintf(output_file, "\\\\"); + else + putc(*s, output_file); + } else + putc(*s, output_file); + } + fprintf(output_file, "\\\"\","); + } else if (s[0] == '\'') { + if (s[1] == '"') { + j += 7; + if (j > 80) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 7; + } + fprintf(output_file, "\"'\\\"'\","); + } else { + k = 5; + while (*++s != '\'') { + ++k; + if (*s == '\\') { + k += 2; + if (*++s == '\\') + ++k; + } + } + j += k; + if (j > 80) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = k; + } + fprintf(output_file, "\"'"); + s = symnam[i]; + while (*++s != '\'') { + if (*s == '\\') { + fprintf(output_file, "\\\\"); + if (*++s == '\\') + fprintf(output_file, "\\\\"); + else + putc(*s, output_file); + } else + putc(*s, output_file); + } + fprintf(output_file, "'\","); + } + } else { + k = strlen(s) + 3; + j += k; + if (j > 80) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = k; + } + putc('"', output_file); + do { + putc(*s, output_file); + } while (*++s); + fprintf(output_file, "\","); + } + } else { + j += 2; + if (j > 80) { + if (!rflag) + ++outline; + putc('\n', output_file); + j = 2; + } + fprintf(output_file, "0,"); + } + } + if (!rflag) + outline += 2; + fprintf(output_file, "\n};\n"); + free(symnam); + + if (!rflag) + ++outline; + fprintf(output_file, + "const char * const %srule[] =\n" + "\t{", symbol_prefix); + for (i = 2; i < nrules; ++i) { + fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]); + for (j = rrhs[i]; ritem[j] > 0; ++j) { + s = symbol_name[ritem[j]]; + if (s[0] == '"') { + fprintf(output_file, " \\\""); + while (*++s != '"') { + if (*s == '\\') { + if (s[1] == '\\') + fprintf(output_file, "\\\\\\\\"); + else + fprintf(output_file, "\\\\%c", s[1]); + ++s; + } else + putc(*s, output_file); + } + fprintf(output_file, "\\\""); + } else if (s[0] == '\'') { + if (s[1] == '"') + fprintf(output_file, " '\\\"'"); + else if (s[1] == '\\') { + if (s[2] == '\\') + fprintf(output_file, " '\\\\\\\\"); + else + fprintf(output_file, " '\\\\%c", s[2]); + s += 2; + while (*++s != '\'') + putc(*s, output_file); + putc('\'', output_file); + } else + fprintf(output_file, " '%c'", s[1]); + } else + fprintf(output_file, " %s", s); + } + if (!rflag) + ++outline; + fprintf(output_file, "\",\n"); + } + + if (!rflag) + outline += 2; + fprintf(output_file, "};\n#endif\n"); +} + + +void +output_stype(void) +{ + if (!unionized && ntags == 0) { + outline += 3; + fprintf(code_file, "#ifndef YYSTYPE\ntypedef int YYSTYPE;\n#endif\n"); + } +} + + +void +output_trailing_text(void) +{ + int c, last; + FILE *in, *out; + + if (line == 0) + return; + + in = input_file; + out = code_file; + c = (unsigned char)*cptr; + if (c == '\n') { + ++lineno; + if ((c = getc(in)) == EOF) + return; + if (!lflag) { + ++outline; + fprintf(out, line_format, lineno, input_file_name); + } + if (c == '\n') + ++outline; + putc(c, out); + last = c; + } else { + if (!lflag) { + ++outline; + fprintf(out, line_format, lineno, input_file_name); + } + do { + putc(c, out); + } while ((c = (unsigned char)*++cptr) != '\n'); + ++outline; + putc('\n', out); + last = '\n'; + } + + while ((c = getc(in)) != EOF) { + if (c == '\n') + ++outline; + putc(c, out); + last = c; + } + + if (last != '\n') { + ++outline; + putc('\n', out); + } + if (!lflag) + fprintf(out, line_format, ++outline + 1, code_file_name); +} + + +void +output_semantic_actions(void) +{ + int c, last; + FILE *out; + + fclose(action_file); + action_file = fopen(action_file_name, "r"); + if (action_file == NULL) + open_error(action_file_name); + + if ((c = getc(action_file)) == EOF) + return; + + out = code_file; + last = c; + if (c == '\n') + ++outline; + putc(c, out); + while ((c = getc(action_file)) != EOF) { + if (c == '\n') + ++outline; + putc(c, out); + last = c; + } + + if (last != '\n') { + ++outline; + putc('\n', out); + } + + if (!lflag) + fprintf(out, line_format, ++outline + 1, code_file_name); +} + + +void +free_itemsets(void) +{ + core *cp, *next; + + free(state_table); + for (cp = first_state; cp; cp = next) { + next = cp->next; + free(cp); + } +} + + +void +free_shifts(void) +{ + shifts *sp, *next; + + free(shift_table); + for (sp = first_shift; sp; sp = next) { + next = sp->next; + free(sp); + } +} + + + +void +free_reductions(void) +{ + reductions *rp, *next; + + free(reduction_table); + for (rp = first_reduction; rp; rp = next) { + next = rp->next; + free(rp); + } +} diff --git a/yacc/reader.c b/yacc/reader.c @@ -0,0 +1,1858 @@ +/* $OpenBSD: reader.c,v 1.29 2014/10/09 03:02:18 deraadt Exp $ */ +/* $NetBSD: reader.c,v 1.5 1996/03/19 03:21:43 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" +#include "util.h" + +/* The line size must be a positive integer. One hundred was chosen */ +/* because few lines in Yacc input grammars exceed 100 characters. */ +/* Note that if a line exceeds LINESIZE characters, the line buffer */ +/* will be expanded to accommodate it. */ + +#define LINESIZE 100 + +char *cache; +int cinc, cache_size; + +int ntags, tagmax; +char **tag_table; + +char saw_eof, unionized; +char *cptr, *line; +int linesize; + +bucket *goal; +int prec; +int gensym; +char last_was_action; + +int maxitems; +bucket **pitem; + +int maxrules; +bucket **plhs; + +int name_pool_size; +char *name_pool; + +void cachec(int); +void get_line(void); +char *dup_line(void); +void skip_comment(void); +int nextc(void); +int keyword(void); +void copy_ident(void); +void copy_text(void); +void copy_union(void); +bucket *get_literal(void); +int is_reserved(char *); +bucket *get_name(void); +int get_number(void); +char *get_tag(void); +void declare_tokens(int); +void declare_types(void); +void declare_start(void); +void handle_expect(void); +void read_declarations(void); +void initialize_grammar(void); +void expand_items(void); +void expand_rules(void); +void advance_to_start(void); +void start_rule(bucket *, int); +void end_rule(void); +void insert_empty_rule(void); +void add_symbol(void); +void copy_action(void); +int mark_symbol(void); +void read_grammar(void); +void free_tags(void); +void pack_names(void); +void check_symbols(void); +void pack_symbols(void); +void pack_grammar(void); +void print_grammar(void); + +char line_format[] = "#line %d \"%s\"\n"; + +void +cachec(int c) +{ + assert(cinc >= 0); + if (cinc >= cache_size) { + cache_size += 256; + cache = realloc(cache, cache_size); + if (cache == NULL) + no_space(); + } + cache[cinc] = c; + ++cinc; +} + + +void +get_line(void) +{ + FILE *f = input_file; + int c, i; + + if (saw_eof || (c = getc(f)) == EOF) { + if (line) { + free(line); + line = 0; + } + cptr = 0; + saw_eof = 1; + return; + } + if (line == NULL || linesize != (LINESIZE + 1)) { + if (line) + free(line); + linesize = LINESIZE + 1; + line = malloc(linesize); + if (line == NULL) + no_space(); + } + i = 0; + ++lineno; + for (;;) { + line[i] = c; + if (c == '\n') { + cptr = line; + return; + } + if (++i >= linesize) { + linesize += LINESIZE; + line = realloc(line, linesize); + if (line == NULL) + no_space(); + } + c = getc(f); + if (c == EOF) { + line[i] = '\n'; + saw_eof = 1; + cptr = line; + return; + } + } +} + + +char * +dup_line(void) +{ + char *p, *s, *t; + + if (line == NULL) + return (0); + s = line; + while (*s != '\n') + ++s; + p = malloc(s - line + 1); + if (p == NULL) + no_space(); + + s = line; + t = p; + while ((*t++ = *s++) != '\n') + continue; + return (p); +} + + +void +skip_comment(void) +{ + char *s; + int st_lineno = lineno; + char *st_line = dup_line(); + char *st_cptr = st_line + (cptr - line); + + s = cptr + 2; + for (;;) { + if (*s == '*' && s[1] == '/') { + cptr = s + 2; + free(st_line); + return; + } + if (*s == '\n') { + get_line(); + if (line == NULL) + unterminated_comment(st_lineno, st_line, st_cptr); + s = cptr; + } else + ++s; + } +} + + +int +nextc(void) +{ + char *s; + + if (line == NULL) { + get_line(); + if (line == NULL) + return (EOF); + } + s = cptr; + for (;;) { + switch (*s) { + case '\n': + get_line(); + if (line == NULL) + return (EOF); + s = cptr; + break; + + case ' ': + case '\t': + case '\f': + case '\r': + case '\v': + case ',': + case ';': + ++s; + break; + + case '\\': + cptr = s; + return ('%'); + + case '/': + if (s[1] == '*') { + cptr = s; + skip_comment(); + s = cptr; + break; + } else if (s[1] == '/') { + get_line(); + if (line == NULL) + return (EOF); + s = cptr; + break; + } + /* fall through */ + + default: + cptr = s; + return ((unsigned char) *s); + } + } +} + + +int +keyword(void) +{ + int c; + char *t_cptr = cptr; + + c = (unsigned char) *++cptr; + if (isalpha(c)) { + cinc = 0; + for (;;) { + if (isalpha(c)) { + if (isupper(c)) + c = tolower(c); + cachec(c); + } else if (isdigit(c) || c == '_' || c == '.' || c == '$') + cachec(c); + else + break; + c = (unsigned char) *++cptr; + } + cachec(NUL); + + if (strcmp(cache, "token") == 0 || strcmp(cache, "term") == 0) + return (TOKEN); + if (strcmp(cache, "type") == 0) + return (TYPE); + if (strcmp(cache, "left") == 0) + return (LEFT); + if (strcmp(cache, "right") == 0) + return (RIGHT); + if (strcmp(cache, "nonassoc") == 0 || strcmp(cache, "binary") == 0) + return (NONASSOC); + if (strcmp(cache, "start") == 0) + return (START); + if (strcmp(cache, "union") == 0) + return (UNION); + if (strcmp(cache, "ident") == 0) + return (IDENT); + if (strcmp(cache, "expect") == 0) + return (EXPECT); + } else { + ++cptr; + if (c == '{') + return (TEXT); + if (c == '%' || c == '\\') + return (MARK); + if (c == '<') + return (LEFT); + if (c == '>') + return (RIGHT); + if (c == '0') + return (TOKEN); + if (c == '2') + return (NONASSOC); + } + syntax_error(lineno, line, t_cptr); + /* NOTREACHED */ + return (0); +} + + +void +copy_ident(void) +{ + int c; + FILE *f = output_file; + + c = nextc(); + if (c == EOF) + unexpected_EOF(); + if (c != '"') + syntax_error(lineno, line, cptr); + ++outline; + fprintf(f, "#ident \""); + for (;;) { + c = (unsigned char) *++cptr; + if (c == '\n') { + fprintf(f, "\"\n"); + return; + } + putc(c, f); + if (c == '"') { + putc('\n', f); + ++cptr; + return; + } + } +} + + +void +copy_text(void) +{ + int c; + int quote; + FILE *f = text_file; + int need_newline = 0; + int t_lineno = lineno; + char *t_line = dup_line(); + char *t_cptr = t_line + (cptr - line - 2); + + if (*cptr == '\n') { + get_line(); + if (line == NULL) + unterminated_text(t_lineno, t_line, t_cptr); + } + if (!lflag) + fprintf(f, line_format, lineno, input_file_name); + +loop: + c = (unsigned char) *cptr++; + switch (c) { + case '\n': +next_line: + putc('\n', f); + need_newline = 0; + get_line(); + if (line) + goto loop; + unterminated_text(t_lineno, t_line, t_cptr); + + case '\'': + case '"': { + int s_lineno = lineno; + char *s_line = dup_line(); + char *s_cptr = s_line + (cptr - line - 1); + + quote = c; + putc(c, f); + for (;;) { + c = (unsigned char) *cptr++; + putc(c, f); + if (c == quote) { + need_newline = 1; + free(s_line); + goto loop; + } + if (c == '\n') + unterminated_string(s_lineno, s_line, s_cptr); + if (c == '\\') { + c = (unsigned char) *cptr++; + putc(c, f); + if (c == '\n') { + get_line(); + if (line == NULL) + unterminated_string(s_lineno, s_line, s_cptr); + } + } + } + } + + case '/': + putc(c, f); + need_newline = 1; + c = (unsigned char) *cptr; + if (c == '/') { + putc('*', f); + while ((c = (unsigned char) *++cptr) != '\n') { + if (c == '*' && cptr[1] == '/') + fprintf(f, "* "); + else + putc(c, f); + } + fprintf(f, "*/"); + goto next_line; + } + if (c == '*') { + int c_lineno = lineno; + char *c_line = dup_line(); + char *c_cptr = c_line + (cptr - line - 1); + + putc('*', f); + ++cptr; + for (;;) { + c = (unsigned char) *cptr++; + putc(c, f); + if (c == '*' && *cptr == '/') { + putc('/', f); + ++cptr; + free(c_line); + goto loop; + } + if (c == '\n') { + get_line(); + if (line == NULL) + unterminated_comment(c_lineno, c_line, c_cptr); + } + } + } + need_newline = 1; + goto loop; + + case '%': + case '\\': + if (*cptr == '}') { + if (need_newline) + putc('\n', f); + ++cptr; + free(t_line); + return; + } + /* fall through */ + + default: + putc(c, f); + need_newline = 1; + goto loop; + } +} + + +void +copy_union(void) +{ + int c, quote, depth; + int u_lineno = lineno; + char *u_line = dup_line(); + char *u_cptr = u_line + (cptr - line - 6); + + if (unionized) + over_unionized(cptr - 6); + unionized = 1; + + if (!lflag) + fprintf(text_file, line_format, lineno, input_file_name); + + fprintf(text_file, "#ifndef YYSTYPE_DEFINED\n"); + fprintf(text_file, "#define YYSTYPE_DEFINED\n"); + fprintf(text_file, "typedef union"); + if (dflag) + fprintf(union_file, "#ifndef YYSTYPE_DEFINED\n"); + if (dflag) + fprintf(union_file, "#define YYSTYPE_DEFINED\n"); + if (dflag) + fprintf(union_file, "typedef union"); + + depth = 0; +loop: + c = (unsigned char) *cptr++; + putc(c, text_file); + if (dflag) + putc(c, union_file); + switch (c) { + case '\n': +next_line: + get_line(); + if (line == NULL) + unterminated_union(u_lineno, u_line, u_cptr); + goto loop; + + case '{': + ++depth; + goto loop; + + case '}': + if (--depth == 0) { + fprintf(text_file, " YYSTYPE;\n"); + fprintf(text_file, "#endif /* YYSTYPE_DEFINED */\n"); + free(u_line); + return; + } + goto loop; + + case '\'': + case '"': { + int s_lineno = lineno; + char *s_line = dup_line(); + char *s_cptr = s_line + (cptr - line - 1); + + quote = c; + for (;;) { + c = (unsigned char) *cptr++; + putc(c, text_file); + if (dflag) + putc(c, union_file); + if (c == quote) { + free(s_line); + goto loop; + } + if (c == '\n') + unterminated_string(s_lineno, s_line, s_cptr); + if (c == '\\') { + c = (unsigned char) *cptr++; + putc(c, text_file); + if (dflag) + putc(c, union_file); + if (c == '\n') { + get_line(); + if (line == NULL) + unterminated_string(s_lineno, + s_line, s_cptr); + } + } + } + } + + case '/': + c = (unsigned char) *cptr; + if (c == '/') { + putc('*', text_file); + if (dflag) + putc('*', union_file); + while ((c = (unsigned char) *++cptr) != '\n') { + if (c == '*' && cptr[1] == '/') { + fprintf(text_file, "* "); + if (dflag) + fprintf(union_file, "* "); + } else { + putc(c, text_file); + if (dflag) + putc(c, union_file); + } + } + fprintf(text_file, "*/\n"); + if (dflag) + fprintf(union_file, "*/\n"); + goto next_line; + } + if (c == '*') { + int c_lineno = lineno; + char *c_line = dup_line(); + char *c_cptr = c_line + (cptr - line - 1); + + putc('*', text_file); + if (dflag) + putc('*', union_file); + ++cptr; + for (;;) { + c = (unsigned char) *cptr++; + putc(c, text_file); + if (dflag) + putc(c, union_file); + if (c == '*' && *cptr == '/') { + putc('/', text_file); + if (dflag) + putc('/', union_file); + ++cptr; + free(c_line); + goto loop; + } + if (c == '\n') { + get_line(); + if (line == NULL) + unterminated_comment(c_lineno, + c_line, c_cptr); + } + } + } + goto loop; + + default: + goto loop; + } +} + + +bucket * +get_literal(void) +{ + int c, quote, i, n; + char *s; + bucket *bp; + int s_lineno = lineno; + char *s_line = dup_line(); + char *s_cptr = s_line + (cptr - line); + + quote = (unsigned char) *cptr++; + cinc = 0; + for (;;) { + c = (unsigned char) *cptr++; + if (c == quote) + break; + if (c == '\n') + unterminated_string(s_lineno, s_line, s_cptr); + if (c == '\\') { + char *c_cptr = cptr - 1; + unsigned long ulval; + + c = (unsigned char) *cptr++; + switch (c) { + case '\n': + get_line(); + if (line == NULL) + unterminated_string(s_lineno, s_line, + s_cptr); + continue; + + case '0': + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + ulval = strtoul(cptr - 1, &s, 8); + if (s == cptr - 1 || ulval > MAXCHAR) + illegal_character(c_cptr); + c = (int) ulval; + cptr = s; + break; + + case 'x': + ulval = strtoul(cptr, &s, 16); + if (s == cptr || ulval > MAXCHAR) + illegal_character(c_cptr); + c = (int) ulval; + cptr = s; + break; + + case 'a': + c = 7; + break; + case 'b': + c = '\b'; + break; + case 'f': + c = '\f'; + break; + case 'n': + c = '\n'; + break; + case 'r': + c = '\r'; + break; + case 't': + c = '\t'; + break; + case 'v': + c = '\v'; + break; + } + } + cachec(c); + } + free(s_line); + + n = cinc; + s = malloc(n); + if (s == NULL) + no_space(); + + memcpy(s, cache, n); + + cinc = 0; + if (n == 1) + cachec('\''); + else + cachec('"'); + + for (i = 0; i < n; ++i) { + c = ((unsigned char *) s)[i]; + if (c == '\\' || c == cache[0]) { + cachec('\\'); + cachec(c); + } else if (isprint(c)) + cachec(c); + else { + cachec('\\'); + switch (c) { + case 7: + cachec('a'); + break; + case '\b': + cachec('b'); + break; + case '\f': + cachec('f'); + break; + case '\n': + cachec('n'); + break; + case '\r': + cachec('r'); + break; + case '\t': + cachec('t'); + break; + case '\v': + cachec('v'); + break; + default: + cachec(((c >> 6) & 7) + '0'); + cachec(((c >> 3) & 7) + '0'); + cachec((c & 7) + '0'); + break; + } + } + } + + if (n == 1) + cachec('\''); + else + cachec('"'); + + cachec(NUL); + bp = lookup(cache); + bp->class = TERM; + if (n == 1 && bp->value == UNDEFINED) + bp->value = *(unsigned char *) s; + free(s); + + return (bp); +} + + +int +is_reserved(char *name) +{ + char *s; + + if (strcmp(name, ".") == 0 || + strcmp(name, "$accept") == 0 || + strcmp(name, "$end") == 0) + return (1); + + if (name[0] == '$' && name[1] == '$' && isdigit((unsigned char) name[2])) { + s = name + 3; + while (isdigit((unsigned char) *s)) + ++s; + if (*s == NUL) + return (1); + } + return (0); +} + + +bucket * +get_name(void) +{ + int c; + + cinc = 0; + for (c = (unsigned char) *cptr; IS_IDENT(c); c = (unsigned char) *++cptr) + cachec(c); + cachec(NUL); + + if (is_reserved(cache)) + used_reserved(cache); + + return (lookup(cache)); +} + + +int +get_number(void) +{ + int c, n; + + n = 0; + for (c = (unsigned char) *cptr; isdigit(c); c = (unsigned char) *++cptr) + n = 10 * n + (c - '0'); + + return (n); +} + + +char * +get_tag(void) +{ + int c, i; + char *s; + int t_lineno = lineno; + char *t_line = dup_line(); + char *t_cptr = t_line + (cptr - line); + + ++cptr; + c = nextc(); + if (c == EOF) + unexpected_EOF(); + if (!isalpha(c) && c != '_' && c != '$') + illegal_tag(t_lineno, t_line, t_cptr); + + cinc = 0; + do { + cachec(c); + c = (unsigned char) *++cptr; + } while (IS_IDENT(c)); + cachec(NUL); + + c = nextc(); + if (c == EOF) + unexpected_EOF(); + if (c != '>') + illegal_tag(t_lineno, t_line, t_cptr); + free(t_line); + ++cptr; + + for (i = 0; i < ntags; ++i) { + if (strcmp(cache, tag_table[i]) == 0) + return (tag_table[i]); + } + + if (ntags >= tagmax) { + tagmax += 16; + tag_table = reallocarray(tag_table, tagmax, sizeof(char *)); + if (tag_table == NULL) + no_space(); + } + s = malloc(cinc); + if (s == NULL) + no_space(); + strlcpy(s, cache, cinc); + tag_table[ntags] = s; + ++ntags; + return (s); +} + + +void +declare_tokens(int assoc) +{ + int c; + bucket *bp; + int value; + char *tag = 0; + + if (assoc != TOKEN) + ++prec; + + c = nextc(); + if (c == EOF) + unexpected_EOF(); + if (c == '<') { + tag = get_tag(); + c = nextc(); + if (c == EOF) + unexpected_EOF(); + } + for (;;) { + if (isalpha(c) || c == '_' || c == '.' || c == '$') + bp = get_name(); + else if (c == '\'' || c == '"') + bp = get_literal(); + else + return; + + if (bp == goal) + tokenized_start(bp->name); + bp->class = TERM; + + if (tag) { + if (bp->tag && tag != bp->tag) + retyped_warning(bp->name); + bp->tag = tag; + } + if (assoc != TOKEN) { + if (bp->prec && prec != bp->prec) + reprec_warning(bp->name); + bp->assoc = assoc; + bp->prec = prec; + } + c = nextc(); + if (c == EOF) + unexpected_EOF(); + value = UNDEFINED; + if (isdigit(c)) { + value = get_number(); + if (bp->value != UNDEFINED && value != bp->value) + revalued_warning(bp->name); + bp->value = value; + c = nextc(); + if (c == EOF) + unexpected_EOF(); + } + } +} + + +/* + * %expect requires special handling as it really isn't part of the yacc + * grammar only a flag for yacc proper. + */ +void +declare_expect(int assoc) +{ + int c; + + if (assoc != EXPECT) + ++prec; + + /* + * Stay away from nextc - doesn't detect EOL and will read to EOF. + */ + c = (unsigned char) *++cptr; + if (c == EOF) + unexpected_EOF(); + + for (;;) { + if (isdigit(c)) { + SRexpect = get_number(); + break; + } + /* + * Looking for number before EOL. + * Spaces, tabs, and numbers are ok. + * Words, punc., etc. are syntax errors. + */ + else if (c == '\n' || isalpha(c) || !isspace(c)) { + syntax_error(lineno, line, cptr); + } else { + c = (unsigned char) *++cptr; + if (c == EOF) + unexpected_EOF(); + } + } +} + + +void +declare_types(void) +{ + int c; + bucket *bp; + char *tag; + + c = nextc(); + if (c == EOF) + unexpected_EOF(); + if (c != '<') + syntax_error(lineno, line, cptr); + tag = get_tag(); + + for (;;) { + c = nextc(); + if (isalpha(c) || c == '_' || c == '.' || c == '$') + bp = get_name(); + else if (c == '\'' || c == '"') + bp = get_literal(); + else + return; + + if (bp->tag && tag != bp->tag) + retyped_warning(bp->name); + bp->tag = tag; + } +} + + +void +declare_start(void) +{ + int c; + bucket *bp; + + c = nextc(); + if (c == EOF) + unexpected_EOF(); + if (!isalpha(c) && c != '_' && c != '.' && c != '$') + syntax_error(lineno, line, cptr); + bp = get_name(); + if (bp->class == TERM) + terminal_start(bp->name); + if (goal && goal != bp) + restarted_warning(); + goal = bp; +} + + +void +read_declarations(void) +{ + int c, k; + + cache_size = 256; + cache = malloc(cache_size); + if (cache == NULL) + no_space(); + + for (;;) { + c = nextc(); + if (c == EOF) + unexpected_EOF(); + if (c != '%') + syntax_error(lineno, line, cptr); + switch (k = keyword()) { + case MARK: + return; + + case IDENT: + copy_ident(); + break; + + case TEXT: + copy_text(); + break; + + case UNION: + copy_union(); + break; + + case TOKEN: + case LEFT: + case RIGHT: + case NONASSOC: + declare_tokens(k); + break; + + case EXPECT: + declare_expect(k); + break; + + case TYPE: + declare_types(); + break; + + case START: + declare_start(); + break; + } + } +} + + +void +initialize_grammar(void) +{ + nitems = 4; + maxitems = 300; + pitem = calloc(maxitems, sizeof(bucket *)); + if (pitem == NULL) + no_space(); + + nrules = 3; + maxrules = 100; + plhs = reallocarray(NULL, maxrules, sizeof(bucket *)); + if (plhs == NULL) + no_space(); + plhs[0] = 0; + plhs[1] = 0; + plhs[2] = 0; + rprec = reallocarray(NULL, maxrules, sizeof(short)); + if (rprec == NULL) + no_space(); + rprec[0] = 0; + rprec[1] = 0; + rprec[2] = 0; + rassoc = reallocarray(NULL, maxrules, sizeof(char)); + if (rassoc == NULL) + no_space(); + rassoc[0] = TOKEN; + rassoc[1] = TOKEN; + rassoc[2] = TOKEN; +} + + +void +expand_items(void) +{ + int olditems = maxitems; + + maxitems += 300; + pitem = reallocarray(pitem, maxitems, sizeof(bucket *)); + if (pitem == NULL) + no_space(); + memset(pitem + olditems, 0, (maxitems - olditems) * sizeof(bucket *)); +} + + +void +expand_rules(void) +{ + maxrules += 100; + plhs = reallocarray(plhs, maxrules, sizeof(bucket *)); + if (plhs == NULL) + no_space(); + rprec = reallocarray(rprec, maxrules, sizeof(short)); + if (rprec == NULL) + no_space(); + rassoc = reallocarray(rassoc, maxrules, sizeof(char)); + if (rassoc == NULL) + no_space(); +} + + +void +advance_to_start(void) +{ + int c; + bucket *bp; + char *s_cptr; + int s_lineno; + + for (;;) { + c = nextc(); + if (c != '%') + break; + s_cptr = cptr; + switch (keyword()) { + case MARK: + no_grammar(); + + case TEXT: + copy_text(); + break; + + case START: + declare_start(); + break; + + default: + syntax_error(lineno, line, s_cptr); + } + } + + c = nextc(); + if (!isalpha(c) && c != '_' && c != '.' && c != '_') + syntax_error(lineno, line, cptr); + bp = get_name(); + if (goal == NULL) { + if (bp->class == TERM) + terminal_start(bp->name); + goal = bp; + } + s_lineno = lineno; + c = nextc(); + if (c == EOF) + unexpected_EOF(); + if (c != ':') + syntax_error(lineno, line, cptr); + start_rule(bp, s_lineno); + ++cptr; +} + + +void +start_rule(bucket * bp, int s_lineno) +{ + if (bp->class == TERM) + terminal_lhs(s_lineno); + bp->class = NONTERM; + if (nrules >= maxrules) + expand_rules(); + plhs[nrules] = bp; + rprec[nrules] = UNDEFINED; + rassoc[nrules] = TOKEN; +} + + +void +end_rule(void) +{ + int i; + + if (!last_was_action && plhs[nrules]->tag) { + for (i = nitems - 1; pitem[i]; --i) + continue; + if (i == maxitems - 1 || pitem[i + 1] == 0 || + pitem[i + 1]->tag != plhs[nrules]->tag) + default_action_warning(); + } + last_was_action = 0; + if (nitems >= maxitems) + expand_items(); + pitem[nitems] = 0; + ++nitems; + ++nrules; +} + + +void +insert_empty_rule(void) +{ + bucket *bp, **bpp; + + assert(cache); + snprintf(cache, cache_size, "$$%d", ++gensym); + bp = make_bucket(cache); + last_symbol->next = bp; + last_symbol = bp; + bp->tag = plhs[nrules]->tag; + bp->class = NONTERM; + + if ((nitems += 2) > maxitems) + expand_items(); + bpp = pitem + nitems - 1; + *bpp-- = bp; + while ((bpp[0] = bpp[-1])) + --bpp; + + if (++nrules >= maxrules) + expand_rules(); + plhs[nrules] = plhs[nrules - 1]; + plhs[nrules - 1] = bp; + rprec[nrules] = rprec[nrules - 1]; + rprec[nrules - 1] = 0; + rassoc[nrules] = rassoc[nrules - 1]; + rassoc[nrules - 1] = TOKEN; +} + + +void +add_symbol(void) +{ + int c; + bucket *bp; + int s_lineno = lineno; + + c = (unsigned char) *cptr; + if (c == '\'' || c == '"') + bp = get_literal(); + else + bp = get_name(); + + c = nextc(); + if (c == ':') { + end_rule(); + start_rule(bp, s_lineno); + ++cptr; + return; + } + if (last_was_action) + insert_empty_rule(); + last_was_action = 0; + + if (++nitems > maxitems) + expand_items(); + pitem[nitems - 1] = bp; +} + + +void +copy_action(void) +{ + int c, i, n, depth, quote; + char *tag; + FILE *f = action_file; + int a_lineno = lineno; + char *a_line = dup_line(); + char *a_cptr = a_line + (cptr - line); + + if (last_was_action) + insert_empty_rule(); + last_was_action = 1; + + fprintf(f, "case %d:\n", nrules - 2); + if (!lflag) + fprintf(f, line_format, lineno, input_file_name); + if (*cptr == '=') + ++cptr; + + n = 0; + for (i = nitems - 1; pitem[i]; --i) + ++n; + + depth = 0; +loop: + c = (unsigned char) *cptr; + if (c == '$') { + if (cptr[1] == '<') { + int d_lineno = lineno; + char *d_line = dup_line(); + char *d_cptr = d_line + (cptr - line); + + ++cptr; + tag = get_tag(); + c = (unsigned char) *cptr; + if (c == '$') { + fprintf(f, "yyval.%s", tag); + ++cptr; + free(d_line); + goto loop; + } else if (isdigit(c)) { + i = get_number(); + if (i > n) + dollar_warning(d_lineno, i); + fprintf(f, "yyvsp[%d].%s", i - n, tag); + free(d_line); + goto loop; + } else if (c == '-' && isdigit((unsigned char) cptr[1])) { + ++cptr; + i = -get_number() - n; + fprintf(f, "yyvsp[%d].%s", i, tag); + free(d_line); + goto loop; + } else + dollar_error(d_lineno, d_line, d_cptr); + } else if (cptr[1] == '$') { + if (ntags) { + tag = plhs[nrules]->tag; + if (tag == NULL) + untyped_lhs(); + fprintf(f, "yyval.%s", tag); + } else + fprintf(f, "yyval"); + cptr += 2; + goto loop; + } else if (isdigit((unsigned char) cptr[1])) { + ++cptr; + i = get_number(); + if (ntags) { + if (i <= 0 || i > n) + unknown_rhs(i); + tag = pitem[nitems + i - n - 1]->tag; + if (tag == NULL) + untyped_rhs(i, pitem[nitems + i - n - 1]->name); + fprintf(f, "yyvsp[%d].%s", i - n, tag); + } else { + if (i > n) + dollar_warning(lineno, i); + fprintf(f, "yyvsp[%d]", i - n); + } + goto loop; + } else if (cptr[1] == '-') { + cptr += 2; + i = get_number(); + if (ntags) + unknown_rhs(-i); + fprintf(f, "yyvsp[%d]", -i - n); + goto loop; + } + } + if (isalpha(c) || c == '_' || c == '$') { + do { + putc(c, f); + c = (unsigned char) *++cptr; + } while (isalnum(c) || c == '_' || c == '$'); + goto loop; + } + putc(c, f); + ++cptr; + switch (c) { + case '\n': +next_line: + get_line(); + if (line) + goto loop; + unterminated_action(a_lineno, a_line, a_cptr); + + case ';': + if (depth > 0) + goto loop; + fprintf(f, "\nbreak;\n"); + free(a_line); + return; + + case '{': + ++depth; + goto loop; + + case '}': + if (--depth > 0) + goto loop; + fprintf(f, "\nbreak;\n"); + free(a_line); + return; + + case '\'': + case '"': { + int s_lineno = lineno; + char *s_line = dup_line(); + char *s_cptr = s_line + (cptr - line - 1); + + quote = c; + for (;;) { + c = (unsigned char) *cptr++; + putc(c, f); + if (c == quote) { + free(s_line); + goto loop; + } + if (c == '\n') + unterminated_string(s_lineno, s_line, s_cptr); + if (c == '\\') { + c = (unsigned char) *cptr++; + putc(c, f); + if (c == '\n') { + get_line(); + if (line == NULL) + unterminated_string(s_lineno, s_line, s_cptr); + } + } + } + } + + case '/': + c = (unsigned char) *cptr; + if (c == '/') { + putc('*', f); + while ((c = (unsigned char) *++cptr) != '\n') { + if (c == '*' && cptr[1] == '/') + fprintf(f, "* "); + else + putc(c, f); + } + fprintf(f, "*/\n"); + goto next_line; + } + if (c == '*') { + int c_lineno = lineno; + char *c_line = dup_line(); + char *c_cptr = c_line + (cptr - line - 1); + + putc('*', f); + ++cptr; + for (;;) { + c = (unsigned char) *cptr++; + putc(c, f); + if (c == '*' && *cptr == '/') { + putc('/', f); + ++cptr; + free(c_line); + goto loop; + } + if (c == '\n') { + get_line(); + if (line == NULL) + unterminated_comment(c_lineno, c_line, c_cptr); + } + } + } + goto loop; + + default: + goto loop; + } +} + + +int +mark_symbol(void) +{ + int c; + bucket *bp = NULL; + + c = (unsigned char) cptr[1]; + if (c == '%' || c == '\\') { + cptr += 2; + return (1); + } + if (c == '=') + cptr += 2; + else if ((c == 'p' || c == 'P') && + ((c = cptr[2]) == 'r' || c == 'R') && + ((c = cptr[3]) == 'e' || c == 'E') && + ((c = cptr[4]) == 'c' || c == 'C') && + ((c = (unsigned char) cptr[5], !IS_IDENT(c)))) + cptr += 5; + else + syntax_error(lineno, line, cptr); + + c = nextc(); + if (isalpha(c) || c == '_' || c == '.' || c == '$') + bp = get_name(); + else if (c == '\'' || c == '"') + bp = get_literal(); + else { + syntax_error(lineno, line, cptr); + /* NOTREACHED */ + } + + if (rprec[nrules] != UNDEFINED && bp->prec != rprec[nrules]) + prec_redeclared(); + + rprec[nrules] = bp->prec; + rassoc[nrules] = bp->assoc; + return (0); +} + + +void +read_grammar(void) +{ + int c; + + initialize_grammar(); + advance_to_start(); + + for (;;) { + c = nextc(); + if (c == EOF) + break; + if (isalpha(c) || c == '_' || c == '.' || c == '$' || c == '\'' || + c == '"') + add_symbol(); + else if (c == '{' || c == '=') + copy_action(); + else if (c == '|') { + end_rule(); + start_rule(plhs[nrules - 1], 0); + ++cptr; + } else if (c == '%') { + if (mark_symbol()) + break; + } else + syntax_error(lineno, line, cptr); + } + end_rule(); +} + + +void +free_tags(void) +{ + int i; + + if (tag_table == NULL) + return; + + for (i = 0; i < ntags; ++i) { + assert(tag_table[i]); + free(tag_table[i]); + } + free(tag_table); +} + + +void +pack_names(void) +{ + bucket *bp; + char *p, *s, *t; + + name_pool_size = 13; /* 13 == sizeof("$end") + sizeof("$accept") */ + for (bp = first_symbol; bp; bp = bp->next) + name_pool_size += strlen(bp->name) + 1; + name_pool = malloc(name_pool_size); + if (name_pool == NULL) + no_space(); + + strlcpy(name_pool, "$accept", name_pool_size); + strlcpy(name_pool + 8, "$end", name_pool_size - 8); + t = name_pool + 13; + for (bp = first_symbol; bp; bp = bp->next) { + p = t; + s = bp->name; + while ((*t++ = *s++)) + continue; + free(bp->name); + bp->name = p; + } +} + + +void +check_symbols(void) +{ + bucket *bp; + + if (goal->class == UNKNOWN) + undefined_goal(goal->name); + + for (bp = first_symbol; bp; bp = bp->next) { + if (bp->class == UNKNOWN) { + undefined_symbol_warning(bp->name); + bp->class = TERM; + } + } +} + + +void +pack_symbols(void) +{ + bucket *bp; + bucket **v; + int i, j, k, n; + + nsyms = 2; + ntokens = 1; + for (bp = first_symbol; bp; bp = bp->next) { + ++nsyms; + if (bp->class == TERM) + ++ntokens; + } + start_symbol = ntokens; + nvars = nsyms - ntokens; + + symbol_name = reallocarray(NULL, nsyms, sizeof(char *)); + if (symbol_name == NULL) + no_space(); + symbol_value = reallocarray(NULL, nsyms, sizeof(short)); + if (symbol_value == NULL) + no_space(); + symbol_prec = reallocarray(NULL, nsyms, sizeof(short)); + if (symbol_prec == NULL) + no_space(); + symbol_assoc = malloc(nsyms); + if (symbol_assoc == NULL) + no_space(); + + v = reallocarray(NULL, nsyms, sizeof(bucket *)); + if (v == NULL) + no_space(); + + v[0] = 0; + v[start_symbol] = 0; + + i = 1; + j = start_symbol + 1; + for (bp = first_symbol; bp; bp = bp->next) { + if (bp->class == TERM) + v[i++] = bp; + else + v[j++] = bp; + } + assert(i == ntokens && j == nsyms); + + for (i = 1; i < ntokens; ++i) + v[i]->index = i; + + goal->index = start_symbol + 1; + k = start_symbol + 2; + while (++i < nsyms) + if (v[i] != goal) { + v[i]->index = k; + ++k; + } + goal->value = 0; + k = 1; + for (i = start_symbol + 1; i < nsyms; ++i) { + if (v[i] != goal) { + v[i]->value = k; + ++k; + } + } + + k = 0; + for (i = 1; i < ntokens; ++i) { + n = v[i]->value; + if (n > 256) { + for (j = k++; j > 0 && symbol_value[j - 1] > n; --j) + symbol_value[j] = symbol_value[j - 1]; + symbol_value[j] = n; + } + } + + if (v[1]->value == UNDEFINED) + v[1]->value = 256; + + j = 0; + n = 257; + for (i = 2; i < ntokens; ++i) { + if (v[i]->value == UNDEFINED) { + while (j < k && n == symbol_value[j]) { + while (++j < k && n == symbol_value[j]) + continue; + ++n; + } + v[i]->value = n; + ++n; + } + } + + symbol_name[0] = name_pool + 8; + symbol_value[0] = 0; + symbol_prec[0] = 0; + symbol_assoc[0] = TOKEN; + for (i = 1; i < ntokens; ++i) { + symbol_name[i] = v[i]->name; + symbol_value[i] = v[i]->value; + symbol_prec[i] = v[i]->prec; + symbol_assoc[i] = v[i]->assoc; + } + symbol_name[start_symbol] = name_pool; + symbol_value[start_symbol] = -1; + symbol_prec[start_symbol] = 0; + symbol_assoc[start_symbol] = TOKEN; + for (++i; i < nsyms; ++i) { + k = v[i]->index; + symbol_name[k] = v[i]->name; + symbol_value[k] = v[i]->value; + symbol_prec[k] = v[i]->prec; + symbol_assoc[k] = v[i]->assoc; + } + + free(v); +} + + +void +pack_grammar(void) +{ + int i, j; + int assoc, prec; + + ritem = reallocarray(NULL, nitems, sizeof(short)); + if (ritem == NULL) + no_space(); + rlhs = reallocarray(NULL, nrules, sizeof(short)); + if (rlhs == NULL) + no_space(); + rrhs = reallocarray(NULL, nrules + 1, sizeof(short)); + if (rrhs == NULL) + no_space(); + rprec = reallocarray(rprec, nrules, sizeof(short)); + if (rprec == NULL) + no_space(); + rassoc = realloc(rassoc, nrules); + if (rassoc == NULL) + no_space(); + + ritem[0] = -1; + ritem[1] = goal->index; + ritem[2] = 0; + ritem[3] = -2; + rlhs[0] = 0; + rlhs[1] = 0; + rlhs[2] = start_symbol; + rrhs[0] = 0; + rrhs[1] = 0; + rrhs[2] = 1; + + j = 4; + for (i = 3; i < nrules; ++i) { + rlhs[i] = plhs[i]->index; + rrhs[i] = j; + assoc = TOKEN; + prec = 0; + while (pitem[j]) { + ritem[j] = pitem[j]->index; + if (pitem[j]->class == TERM) { + prec = pitem[j]->prec; + assoc = pitem[j]->assoc; + } + ++j; + } + ritem[j] = -i; + ++j; + if (rprec[i] == UNDEFINED) { + rprec[i] = prec; + rassoc[i] = assoc; + } + } + rrhs[i] = j; + + free(plhs); + free(pitem); +} + + +void +print_grammar(void) +{ + int i, j, k; + int spacing = 0; + FILE *f = verbose_file; + + if (!vflag) + return; + + k = 1; + for (i = 2; i < nrules; ++i) { + if (rlhs[i] != rlhs[i - 1]) { + if (i != 2) + fprintf(f, "\n"); + fprintf(f, "%4d %s :", i - 2, symbol_name[rlhs[i]]); + spacing = strlen(symbol_name[rlhs[i]]) + 1; + } else { + fprintf(f, "%4d ", i - 2); + j = spacing; + while (--j >= 0) + putc(' ', f); + putc('|', f); + } + + while (ritem[k] >= 0) { + fprintf(f, " %s", symbol_name[ritem[k]]); + ++k; + } + ++k; + putc('\n', f); + } +} + + +void +reader(void) +{ + write_section(banner); + create_symbol_table(); + read_declarations(); + read_grammar(); + free_symbol_table(); + free_tags(); + pack_names(); + check_symbols(); + pack_symbols(); + pack_grammar(); + free_symbols(); + print_grammar(); +} diff --git a/yacc/reallocarray.c b/yacc/reallocarray.c @@ -0,0 +1,38 @@ +/* $OpenBSD: reallocarray.c,v 1.1 2014/05/08 21:43:49 deraadt Exp $ */ +/* + * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <sys/types.h> +#include <errno.h> +#include <stdint.h> +#include <stdlib.h> + +/* + * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX + * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW + */ +#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4)) + +void * +reallocarray(void *optr, size_t nmemb, size_t size) +{ + if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) && + nmemb > 0 && SIZE_MAX / nmemb < size) { + errno = ENOMEM; + return NULL; + } + return realloc(optr, size * nmemb); +} diff --git a/yacc/skeleton.c b/yacc/skeleton.c @@ -0,0 +1,404 @@ +/* $OpenBSD: skeleton.c,v 1.35 2014/03/16 18:38:30 guenther Exp $ */ +/* $NetBSD: skeleton.c,v 1.10 1996/03/25 00:36:18 mrg Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" + +/* The definition of yysccsid in the banner should be replaced with */ +/* a #pragma ident directive if the target C compiler supports */ +/* #pragma ident directives. */ +/* */ +/* If the skeleton is changed, the banner should be changed so that */ +/* the altered version can be easily distinguished from the original. */ +/* */ +/* The #defines included with the banner are there because they are */ +/* useful in subsequent code. The macros #defined in the header or */ +/* the body either are not useful outside of semantic actions or */ +/* are conditional. */ + +char *banner[] = +{ + "#include <stdlib.h>", + "#include <string.h>", + "#define YYBYACC 1", + "#define YYMAJOR 1", + "#define YYMINOR 9", + "#define YYLEX yylex()", + "#define YYEMPTY -1", + "#define yyclearin (yychar=(YYEMPTY))", + "#define yyerrok (yyerrflag=0)", + "#define YYRECOVERING() (yyerrflag!=0)", + NULL +}; + + +char *tables[] = +{ + "extern const short yylhs[];", + "extern const short yylen[];", + "extern const short yydefred[];", + "extern const short yydgoto[];", + "extern const short yysindex[];", + "extern const short yyrindex[];", + "extern const short yygindex[];", + "extern const short yytable[];", + "extern const short yycheck[];", + "#if YYDEBUG", + "extern const char *const yyname[];", + "extern const char *const yyrule[];", + "#endif", + NULL +}; + + +char *header[] = +{ + "#ifdef YYSTACKSIZE", + "#undef YYMAXDEPTH", + "#define YYMAXDEPTH YYSTACKSIZE", + "#else", + "#ifdef YYMAXDEPTH", + "#define YYSTACKSIZE YYMAXDEPTH", + "#else", + "#define YYSTACKSIZE 10000", + "#define YYMAXDEPTH 10000", + "#endif", + "#endif", + "#define YYINITSTACKSIZE 200", + "/* LINTUSED */", + "int yydebug;", + "int yynerrs;", + "int yyerrflag;", + "int yychar;", + "short *yyssp;", + "YYSTYPE *yyvsp;", + "YYSTYPE yyval;", + "YYSTYPE yylval;", + "short *yyss;", + "short *yysslim;", + "YYSTYPE *yyvs;", + "unsigned int yystacksize;", + NULL +}; + + +char *body[] = +{ + "/* allocate initial stack or double stack size, up to YYMAXDEPTH */", + "static int yygrowstack(void)", + "{", + " unsigned int newsize;", + " long sslen;", + " short *newss;", + " YYSTYPE *newvs;", + "", + " if ((newsize = yystacksize) == 0)", + " newsize = YYINITSTACKSIZE;", + " else if (newsize >= YYMAXDEPTH)", + " return -1;", + " else if ((newsize *= 2) > YYMAXDEPTH)", + " newsize = YYMAXDEPTH;", + " sslen = yyssp - yyss;", + "#ifdef SIZE_MAX", + "#define YY_SIZE_MAX SIZE_MAX", + "#else", + "#define YY_SIZE_MAX 0xffffffffU", + "#endif", + " if (newsize && YY_SIZE_MAX / newsize < sizeof *newss)", + " goto bail;", + " newss = yyss ? (short *)realloc(yyss, newsize * sizeof *newss) :", + " (short *)malloc(newsize * sizeof *newss); /* overflow check above */", + " if (newss == NULL)", + " goto bail;", + " yyss = newss;", + " yyssp = newss + sslen;", + " if (newsize && YY_SIZE_MAX / newsize < sizeof *newvs)", + " goto bail;", + " newvs = yyvs ? (YYSTYPE *)realloc(yyvs, newsize * sizeof *newvs) :", + " (YYSTYPE *)malloc(newsize * sizeof *newvs); /* overflow check above */", + " if (newvs == NULL)", + " goto bail;", + " yyvs = newvs;", + " yyvsp = newvs + sslen;", + " yystacksize = newsize;", + " yysslim = yyss + newsize - 1;", + " return 0;", + "bail:", + " if (yyss)", + " free(yyss);", + " if (yyvs)", + " free(yyvs);", + " yyss = yyssp = NULL;", + " yyvs = yyvsp = NULL;", + " yystacksize = 0;", + " return -1;", + "}", + "", + "#define YYABORT goto yyabort", + "#define YYREJECT goto yyabort", + "#define YYACCEPT goto yyaccept", + "#define YYERROR goto yyerrlab", + "int", + "yyparse(void)", + "{", + " int yym, yyn, yystate;", + "#if YYDEBUG", + " const char *yys;", + "", + " if ((yys = getenv(\"YYDEBUG\")))", + " {", + " yyn = *yys;", + " if (yyn >= '0' && yyn <= '9')", + " yydebug = yyn - '0';", + " }", + "#endif /* YYDEBUG */", + "", + " yynerrs = 0;", + " yyerrflag = 0;", + " yychar = (-1);", + "", + " if (yyss == NULL && yygrowstack()) goto yyoverflow;", + " yyssp = yyss;", + " yyvsp = yyvs;", + " *yyssp = yystate = 0;", + "", + "yyloop:", + " if ((yyn = yydefred[yystate]) != 0) goto yyreduce;", + " if (yychar < 0)", + " {", + " if ((yychar = yylex()) < 0) yychar = 0;", + "#if YYDEBUG", + " if (yydebug)", + " {", + " yys = 0;", + " if (yychar <= YYMAXTOKEN) yys = yyname[yychar];", + " if (!yys) yys = \"illegal-symbol\";", + " printf(\"%sdebug: state %d, reading %d (%s)\\n\",", + " YYPREFIX, yystate, yychar, yys);", + " }", + "#endif", + " }", + " if ((yyn = yysindex[yystate]) && (yyn += yychar) >= 0 &&", + " yyn <= YYTABLESIZE && yycheck[yyn] == yychar)", + " {", + "#if YYDEBUG", + " if (yydebug)", + " printf(\"%sdebug: state %d, shifting to state %d\\n\",", + " YYPREFIX, yystate, yytable[yyn]);", + "#endif", + " if (yyssp >= yysslim && yygrowstack())", + " {", + " goto yyoverflow;", + " }", + " *++yyssp = yystate = yytable[yyn];", + " *++yyvsp = yylval;", + " yychar = (-1);", + " if (yyerrflag > 0) --yyerrflag;", + " goto yyloop;", + " }", + " if ((yyn = yyrindex[yystate]) && (yyn += yychar) >= 0 &&", + " yyn <= YYTABLESIZE && yycheck[yyn] == yychar)", + " {", + " yyn = yytable[yyn];", + " goto yyreduce;", + " }", + " if (yyerrflag) goto yyinrecovery;", + "#if defined(__GNUC__)", + " goto yynewerror;", + "#endif", + "yynewerror:", + " yyerror(\"syntax error\");", + "#if defined(__GNUC__)", + " goto yyerrlab;", + "#endif", + "yyerrlab:", + " ++yynerrs;", + "yyinrecovery:", + " if (yyerrflag < 3)", + " {", + " yyerrflag = 3;", + " for (;;)", + " {", + " if ((yyn = yysindex[*yyssp]) && (yyn += YYERRCODE) >= 0 &&", + " yyn <= YYTABLESIZE && yycheck[yyn] == YYERRCODE)", + " {", + "#if YYDEBUG", + " if (yydebug)", + " printf(\"%sdebug: state %d, error recovery shifting\\", + " to state %d\\n\", YYPREFIX, *yyssp, yytable[yyn]);", + "#endif", + " if (yyssp >= yysslim && yygrowstack())", + " {", + " goto yyoverflow;", + " }", + " *++yyssp = yystate = yytable[yyn];", + " *++yyvsp = yylval;", + " goto yyloop;", + " }", + " else", + " {", + "#if YYDEBUG", + " if (yydebug)", + " printf(\"%sdebug: error recovery discarding state %d\ +\\n\",", + " YYPREFIX, *yyssp);", + "#endif", + " if (yyssp <= yyss) goto yyabort;", + " --yyssp;", + " --yyvsp;", + " }", + " }", + " }", + " else", + " {", + " if (yychar == 0) goto yyabort;", + "#if YYDEBUG", + " if (yydebug)", + " {", + " yys = 0;", + " if (yychar <= YYMAXTOKEN) yys = yyname[yychar];", + " if (!yys) yys = \"illegal-symbol\";", + " printf(\"%sdebug: state %d, error recovery discards token %d\ + (%s)\\n\",", + " YYPREFIX, yystate, yychar, yys);", + " }", + "#endif", + " yychar = (-1);", + " goto yyloop;", + " }", + "yyreduce:", + "#if YYDEBUG", + " if (yydebug)", + " printf(\"%sdebug: state %d, reducing by rule %d (%s)\\n\",", + " YYPREFIX, yystate, yyn, yyrule[yyn]);", + "#endif", + " yym = yylen[yyn];", + " if (yym)", + " yyval = yyvsp[1-yym];", + " else", + " memset(&yyval, 0, sizeof yyval);", + " switch (yyn)", + " {", + NULL +}; + + +char *trailer[] = +{ + " }", + " yyssp -= yym;", + " yystate = *yyssp;", + " yyvsp -= yym;", + " yym = yylhs[yyn];", + " if (yystate == 0 && yym == 0)", + " {", + "#if YYDEBUG", + " if (yydebug)", + " printf(\"%sdebug: after reduction, shifting from state 0 to\\", + " state %d\\n\", YYPREFIX, YYFINAL);", + "#endif", + " yystate = YYFINAL;", + " *++yyssp = YYFINAL;", + " *++yyvsp = yyval;", + " if (yychar < 0)", + " {", + " if ((yychar = yylex()) < 0) yychar = 0;", + "#if YYDEBUG", + " if (yydebug)", + " {", + " yys = 0;", + " if (yychar <= YYMAXTOKEN) yys = yyname[yychar];", + " if (!yys) yys = \"illegal-symbol\";", + " printf(\"%sdebug: state %d, reading %d (%s)\\n\",", + " YYPREFIX, YYFINAL, yychar, yys);", + " }", + "#endif", + " }", + " if (yychar == 0) goto yyaccept;", + " goto yyloop;", + " }", + " if ((yyn = yygindex[yym]) && (yyn += yystate) >= 0 &&", + " yyn <= YYTABLESIZE && yycheck[yyn] == yystate)", + " yystate = yytable[yyn];", + " else", + " yystate = yydgoto[yym];", + "#if YYDEBUG", + " if (yydebug)", + " printf(\"%sdebug: after reduction, shifting from state %d \\", + "to state %d\\n\", YYPREFIX, *yyssp, yystate);", + "#endif", + " if (yyssp >= yysslim && yygrowstack())", + " {", + " goto yyoverflow;", + " }", + " *++yyssp = yystate;", + " *++yyvsp = yyval;", + " goto yyloop;", + "yyoverflow:", + " yyerror(\"yacc stack overflow\");", + "yyabort:", + " if (yyss)", + " free(yyss);", + " if (yyvs)", + " free(yyvs);", + " yyss = yyssp = NULL;", + " yyvs = yyvsp = NULL;", + " yystacksize = 0;", + " return (1);", + "yyaccept:", + " if (yyss)", + " free(yyss);", + " if (yyvs)", + " free(yyvs);", + " yyss = yyssp = NULL;", + " yyvs = yyvsp = NULL;", + " yystacksize = 0;", + " return (0);", + "}", + NULL +}; + + +void +write_section(char *section[]) +{ + int i; + char *s; + + for (i = 0; (s = section[i]); ++i) { + ++outline; + fputs(s, code_file); + putc('\n', code_file); + } +} diff --git a/yacc/symtab.c b/yacc/symtab.c @@ -0,0 +1,151 @@ +/* $OpenBSD: symtab.c,v 1.17 2014/03/13 00:56:39 tedu Exp $ */ +/* $NetBSD: symtab.c,v 1.4 1996/03/19 03:21:48 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" + +/* TABLE_SIZE is the number of entries in the symbol table. */ +/* TABLE_SIZE must be a power of two. */ + +#define TABLE_SIZE 1024 + + +bucket **symbol_table; +bucket *first_symbol; +bucket *last_symbol; + +int hash(char *); + + +int +hash(char *name) +{ + char *s; + int c, k; + + assert(name && *name); + s = name; + k = *s; + while ((c = *++s)) + k = (31 * k + c) & (TABLE_SIZE - 1); + + return (k); +} + + +bucket * +make_bucket(char *name) +{ + bucket *bp; + + assert(name); + bp = malloc(sizeof(bucket)); + if (bp == NULL) + no_space(); + bp->link = 0; + bp->next = 0; + bp->name = strdup(name); + if (bp->name == NULL) + no_space(); + bp->tag = 0; + bp->value = UNDEFINED; + bp->index = 0; + bp->prec = 0; + bp->class = UNKNOWN; + bp->assoc = TOKEN; + + return (bp); +} + + +bucket * +lookup(char *name) +{ + bucket *bp, **bpp; + + bpp = symbol_table + hash(name); + bp = *bpp; + + while (bp) { + if (strcmp(name, bp->name) == 0) + return (bp); + bpp = &bp->link; + bp = *bpp; + } + + *bpp = bp = make_bucket(name); + last_symbol->next = bp; + last_symbol = bp; + + return (bp); +} + + +void +create_symbol_table(void) +{ + bucket *bp; + + symbol_table = calloc(TABLE_SIZE, sizeof(bucket *)); + if (symbol_table == NULL) + no_space(); + + bp = make_bucket("error"); + bp->index = 1; + bp->class = TERM; + + first_symbol = bp; + last_symbol = bp; + symbol_table[hash("error")] = bp; +} + + +void +free_symbol_table(void) +{ + free(symbol_table); + symbol_table = 0; +} + + +void +free_symbols(void) +{ + bucket *p, *q; + + for (p = first_symbol; p; p = q) { + q = p->next; + free(p); + } +} diff --git a/yacc/util.h b/yacc/util.h @@ -0,0 +1,3 @@ +#include <sys/stat.h> + +void *reallocarray(void *, size_t, size_t); diff --git a/yacc/verbose.c b/yacc/verbose.c @@ -0,0 +1,351 @@ +/* $OpenBSD: verbose.c,v 1.13 2014/10/09 03:02:18 deraadt Exp $ */ +/* $NetBSD: verbose.c,v 1.4 1996/03/19 03:21:50 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" +#include "util.h" + +static short *null_rules; + +void log_unused(void); +void log_conflicts(void); +void print_state(int); +void print_conflicts(int); +void print_core(int); +void print_nulls(int); +void print_actions(int); +void print_shifts(action *); +void print_reductions(action *, int); +void print_gotos(int); + +void +verbose(void) +{ + int i; + + if (!vflag) + return; + + null_rules = reallocarray(NULL, nrules, sizeof(short)); + if (null_rules == NULL) + no_space(); + fprintf(verbose_file, "\f\n"); + for (i = 0; i < nstates; i++) + print_state(i); + free(null_rules); + + if (nunused) + log_unused(); + if (SRtotal || RRtotal) + log_conflicts(); + + fprintf(verbose_file, "\n\n%d terminals, %d nonterminals\n", ntokens, + nvars); + fprintf(verbose_file, "%d grammar rules, %d states\n", nrules - 2, + nstates); +} + + +void +log_unused(void) +{ + int i; + short *p; + + fprintf(verbose_file, "\n\nRules never reduced:\n"); + for (i = 3; i < nrules; ++i) { + if (!rules_used[i]) { + fprintf(verbose_file, "\t%s :", symbol_name[rlhs[i]]); + for (p = ritem + rrhs[i]; *p >= 0; ++p) + fprintf(verbose_file, " %s", symbol_name[*p]); + fprintf(verbose_file, " (%d)\n", i - 2); + } + } +} + + +void +log_conflicts(void) +{ + int i; + + fprintf(verbose_file, "\n\n"); + for (i = 0; i < nstates; i++) { + if (SRconflicts[i] || RRconflicts[i]) { + fprintf(verbose_file, "State %d contains ", i); + if (SRconflicts[i] == 1) + fprintf(verbose_file, "1 shift/reduce conflict"); + else if (SRconflicts[i] > 1) + fprintf(verbose_file, "%d shift/reduce conflicts", + SRconflicts[i]); + if (SRconflicts[i] && RRconflicts[i]) + fprintf(verbose_file, ", "); + if (RRconflicts[i] == 1) + fprintf(verbose_file, "1 reduce/reduce conflict"); + else if (RRconflicts[i] > 1) + fprintf(verbose_file, "%d reduce/reduce conflicts", + RRconflicts[i]); + fprintf(verbose_file, ".\n"); + } + } +} + + +void +print_state(int state) +{ + if (state) + fprintf(verbose_file, "\n\n"); + if (SRconflicts[state] || RRconflicts[state]) + print_conflicts(state); + fprintf(verbose_file, "state %d\n", state); + print_core(state); + print_nulls(state); + print_actions(state); +} + + +void +print_conflicts(int state) +{ + int symbol, act = REDUCE, number = 0; + action *p; + + symbol = -1; + for (p = parser[state]; p; p = p->next) { + if (p->suppressed == 2) + continue; + + if (p->symbol != symbol) { + symbol = p->symbol; + number = p->number; + if (p->action_code == SHIFT) + act = SHIFT; + else + act = REDUCE; + } else if (p->suppressed == 1) { + if (state == final_state && symbol == 0) { + fprintf(verbose_file, + "%d: shift/reduce conflict " + "(accept, reduce %d) on $end\n", + state, p->number - 2); + } else { + if (act == SHIFT) { + fprintf(verbose_file, + "%d: shift/reduce conflict " + "(shift %d, reduce %d) on %s\n", + state, number, p->number - 2, + symbol_name[symbol]); + } else { + fprintf(verbose_file, + "%d: reduce/reduce conflict " + "(reduce %d, reduce %d) on %s\n", + state, number - 2, p->number - 2, + symbol_name[symbol]); + } + } + } + } +} + + +void +print_core(int state) +{ + int i; + int k; + int rule; + core *statep; + short *sp; + short *sp1; + + statep = state_table[state]; + k = statep->nitems; + + for (i = 0; i < k; i++) { + sp1 = sp = ritem + statep->items[i]; + + while (*sp >= 0) + ++sp; + rule = -(*sp); + fprintf(verbose_file, "\t%s : ", symbol_name[rlhs[rule]]); + + for (sp = ritem + rrhs[rule]; sp < sp1; sp++) + fprintf(verbose_file, "%s ", symbol_name[*sp]); + + putc('.', verbose_file); + + while (*sp >= 0) { + fprintf(verbose_file, " %s", symbol_name[*sp]); + sp++; + } + fprintf(verbose_file, " (%d)\n", -2 - *sp); + } +} + + +void +print_nulls(int state) +{ + action *p; + int i, j, k, nnulls; + + nnulls = 0; + for (p = parser[state]; p; p = p->next) { + if (p->action_code == REDUCE && + (p->suppressed == 0 || p->suppressed == 1)) { + i = p->number; + if (rrhs[i] + 1 == rrhs[i + 1]) { + for (j = 0; j < nnulls && i > null_rules[j]; ++j) + continue; + + if (j == nnulls) { + ++nnulls; + null_rules[j] = i; + } else if (i != null_rules[j]) { + ++nnulls; + for (k = nnulls - 1; k > j; --k) + null_rules[k] = null_rules[k - 1]; + null_rules[j] = i; + } + } + } + } + + for (i = 0; i < nnulls; ++i) { + j = null_rules[i]; + fprintf(verbose_file, "\t%s : . (%d)\n", symbol_name[rlhs[j]], + j - 2); + } + fprintf(verbose_file, "\n"); +} + + +void +print_actions(int stateno) +{ + action *p; + shifts *sp; + int as; + + if (stateno == final_state) + fprintf(verbose_file, "\t$end accept\n"); + + p = parser[stateno]; + if (p) { + print_shifts(p); + print_reductions(p, defred[stateno]); + } + sp = shift_table[stateno]; + if (sp && sp->nshifts > 0) { + as = accessing_symbol[sp->shift[sp->nshifts - 1]]; + if (ISVAR(as)) + print_gotos(stateno); + } +} + + +void +print_shifts(action * p) +{ + int count; + action *q; + + count = 0; + for (q = p; q; q = q->next) { + if (q->suppressed < 2 && q->action_code == SHIFT) + ++count; + } + + if (count > 0) { + for (; p; p = p->next) { + if (p->action_code == SHIFT && p->suppressed == 0) + fprintf(verbose_file, "\t%s shift %d\n", + symbol_name[p->symbol], p->number); + } + } +} + + +void +print_reductions(action * p, int defred) +{ + int k, anyreds; + action *q; + + anyreds = 0; + for (q = p; q; q = q->next) { + if (q->action_code == REDUCE && q->suppressed < 2) { + anyreds = 1; + break; + } + } + + if (anyreds == 0) + fprintf(verbose_file, "\t. error\n"); + else { + for (; p; p = p->next) { + if (p->action_code == REDUCE && p->number != defred) { + k = p->number - 2; + if (p->suppressed == 0) + fprintf(verbose_file, "\t%s reduce %d\n", + symbol_name[p->symbol], k); + } + } + + if (defred > 0) + fprintf(verbose_file, "\t. reduce %d\n", defred - 2); + } +} + + +void +print_gotos(int stateno) +{ + int i, k; + int as; + short *to_state; + shifts *sp; + + putc('\n', verbose_file); + sp = shift_table[stateno]; + to_state = sp->shift; + for (i = 0; i < sp->nshifts; ++i) { + k = to_state[i]; + as = accessing_symbol[k]; + if (ISVAR(as)) + fprintf(verbose_file, "\t%s goto %d\n", + symbol_name[as], k); + } +} diff --git a/yacc/warshall.c b/yacc/warshall.c @@ -0,0 +1,100 @@ +/* $OpenBSD: warshall.c,v 1.11 2014/03/13 01:18:22 tedu Exp $ */ +/* $NetBSD: warshall.c,v 1.4 1996/03/19 03:21:51 jtc Exp $ */ + +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "defs.h" + +void transitive_closure(unsigned int *, int); + +void +transitive_closure(unsigned int *R, int n) +{ + int rowsize; + unsigned int i; + unsigned int *rowj, *rp, *rend, *ccol, *relend, *cword, *rowi; + + rowsize = WORDSIZE(n); + relend = R + n * rowsize; + + cword = R; + i = 0; + rowi = R; + while (rowi < relend) { + ccol = cword; + rowj = R; + + while (rowj < relend) { + if (*ccol & (1 << i)) { + rp = rowi; + rend = rowj + rowsize; + while (rowj < rend) + *rowj++ |= *rp++; + } else { + rowj += rowsize; + } + + ccol += rowsize; + } + + if (++i >= BITS_PER_WORD) { + i = 0; + cword++; + } + rowi += rowsize; + } +} + +void +reflexive_transitive_closure(unsigned int *R, int n) +{ + int rowsize; + unsigned int i; + unsigned int *rp, *relend; + + transitive_closure(R, n); + + rowsize = WORDSIZE(n); + relend = R + n * rowsize; + + i = 0; + rp = R; + while (rp < relend) { + *rp |= (1 << i); + if (++i >= BITS_PER_WORD) { + i = 0; + rp++; + } + rp += rowsize; + } +} diff --git a/yacc/yacc.1 b/yacc/yacc.1 @@ -0,0 +1,256 @@ +.\" $OpenBSD: yacc.1,v 1.30 2014/06/04 06:55:50 jmc Exp $ +.\" +.\" Copyright (c) 1989, 1990 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Robert Paul Corbett. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" from: @(#)yacc.1 5.7 (Berkeley) 7/30/91 +.\" +.Dd $Mdocdate: June 4 2014 $ +.Dt YACC 1 +.Os +.Sh NAME +.Nm yacc +.Nd an +.Tn LALR(1) +parser generator +.Sh SYNOPSIS +.Nm yacc +.Op Fl dlrtv +.Op Fl b Ar file_prefix +.Op Fl o Ar output_file +.Op Fl p Ar symbol_prefix +.Ar file +.Sh DESCRIPTION +.Nm +reads the grammar specification in +.Ar file +and generates an +.Tn LR(1) +parser for it. +The parsers consist of a set of +.Tn LALR(1) +parsing tables and a driver routine +written in the C programming language. +.Nm +normally writes the parse tables and the driver routine to the file +.Pa y.tab.c . +.Pp +The options are as follows: +.Bl -tag -width Ds +.It Fl b Ar file_prefix +The +.Fl b +option changes the prefix prepended to the output file names to +the string denoted by +.Ar file_prefix . +The default prefix is the character +.Ar y . +.It Fl d +The +.Fl d +option causes the header file +.Pa y.tab.h +to be written. +.It Fl l +If the +.Fl l +option is not specified, +.Nm +will insert #line directives in the generated code. +The #line directives let the C compiler relate errors in the +generated code to the user's original code. +If the +.Fl l +option is specified, +.Nm +will not insert the #line directives. +#line directives specified by the user will be retained. +.It Fl o Ar output_file +The +.Fl o +option specifies an explicit name for the parser's output file name instead +of the default. +The names of the other output files are constructed from +.Pa output_file +as described under the +.Fl d +and +.Fl v +options. +.It Fl p Ar symbol_prefix +The +.Fl p +option changes the prefix prepended to yacc-generated symbols to +the string denoted by +.Ar symbol_prefix . +The default prefix is the string +.Ar yy . +.It Fl r +The +.Fl r +option causes +.Nm +to produce separate files for code and tables. +The code file is named +.Pa y.code.c , +and the tables file is named +.Pa y.tab.c . +.It Fl t +The +.Fl t +option changes the preprocessor directives generated by +.Nm +so that debugging statements will be incorporated in the compiled code. +.It Fl v +The +.Fl v +option causes a human-readable description of the generated parser to +be written to the file +.Pa y.output . +.El +.Sh ENVIRONMENT +.Bl -tag -width TMPDIR +.It Ev TMPDIR +Name of directory where temporary files are to be created. +.El +.Sh TABLES +The names of the tables generated by this version of +.Nm +are +.Dq yylhs , +.Dq yylen , +.Dq yydefred , +.Dq yydgoto , +.Dq yysindex , +.Dq yyrindex , +.Dq yygindex , +.Dq yytable , +and +.Dq yycheck . +Two additional tables, +.Dq yyname +and +.Dq yyrule , +are created if +.Dv YYDEBUG +is defined and non-zero. +.Sh FILES +.Bl -tag -width /tmp/yacc.uXXXXXXXXXX -compact +.It Pa y.code.c +.It Pa y.tab.c +.It Pa y.tab.h +.It Pa y.output +.It Pa /tmp/yacc.aXXXXXXXXXX +.It Pa /tmp/yacc.tXXXXXXXXXX +.It Pa /tmp/yacc.uXXXXXXXXXX +.El +.Sh EXIT STATUS +.Ex -std yacc +.Sh DIAGNOSTICS +If there are rules that are never reduced, the number of such rules is +written to the standard error. +If there are any +.Tn LALR(1) +conflicts, the number of conflicts is also written +to the standard error. +.Sh SEE ALSO +.Xr yyfix 1 +.Rs +.%A F. DeRemer +.%A T. J. Pennello +.%D 1982 +.%J TOPLAS +.%N Issue 4 +.%P pp. 615\(en649 +.%T Efficient Computation of LALR(1) Look-Ahead Sets +.%V Volume 4 +.Re +.Sh STANDARDS +The +.Nm +utility is compliant with the +.St -p1003.1-2008 +specification, +though its presence is optional. +.Pp +The flags +.Op Fl or , +as well as the environment variable +.Ev TMPDIR , +are extensions to that specification. +.Sh HISTORY +.Nm +was originally developed at AT&T by +.An Stephen C. Johnson . +.Pp +Berkeley +.Nm +was originally developed using PCC on a VAX with the +intent of being as compatible as possible with +.At +.Nm . +Much is owed to the unflagging efforts of Keith Bostic. +His badgering kept me working on +.Nm +long after I was ready to quit. +.Pp +Berkeley +.Nm +is based on the excellent algorithm for computing +LALR(1) lookaheads developed by +.An Tom Pennello +and +.An Frank DeRemer . +The algorithm is described in their almost impenetrable article in +TOPLAS (see above). +.Pp +Finally, much credit must go to those who pointed out deficiencies +of earlier releases. +Among the most prolific contributors were +Benson I. Margulies, +Dave Gentzel, +Antoine Verheijen, +Peter S. Housel, +Dale Smith, +Ozan Yigit, +John Campbell, +Bill Sommerfeld, +Paul Hilfinger, +Gary Bridgewater, +Dave Bakken, +Dan Lanciani, +Richard Sargent, +and +Parag Patel. +.Sh AUTHORS +The +.Nm +utility was written by +.An Robert Corbett . diff --git a/yacc/yyfix.1 b/yacc/yyfix.1 @@ -0,0 +1,108 @@ +.\" $OpenBSD: yyfix.1,v 1.6 2014/11/15 14:41:02 bentley Exp $ +.\" Copyright (c) 1990, 1991 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" from: @(#)yyfix.1 5.4 (Berkeley) 3/23/93 +.\" +.Dd $Mdocdate: November 15 2014 $ +.Dt YYFIX 1 +.Os +.Sh NAME +.Nm yyfix +.Nd extract tables from y.tab.c +.Sh SYNOPSIS +.Nm yyfix +.Ar file +.Op Ar tables +.Sh DESCRIPTION +Programs have historically used a script (often named +.Pa :yyfix ) +to extract tables from the +.Xr yacc 1 +generated file +.Pa y.tab.c . +As the names of the tables generated by the current version of yacc +are different from those of historical versions of yacc, +the shell script +.Nm yyfix +is provided to simplify the transition. +.Pp +The first (and required) argument to +.Nm yyfix +is the name of the file where the extracted tables should be stored. +.Pp +If further command line arguments are specified, they are taken as +the list of tables to be extracted. +Otherwise, +.Nm yyfix +attempts to determine if the +.Pa y.tab.c +file is from an old or new +.Xr yacc 1 , +and extracts the appropriate tables. +.Pp +The tables +.Dq yyexca , +.Dq yyact , +.Dq yypact , +.Dq yypgo , +.Dq yyr1 , +.Dq yyr2 , +.Dq yychk , +and +.Dq yydef +are extracted +from historical versions of +.Xr yacc 1 . +.Pp +The tables +.Dq yylhs , +.Dq yylen , +.Dq yydefred , +.Dq yydgoto , +.Dq yysindex , +.Dq yyrindex , +.Dq yygindex , +.Dq yytable , +.Dq yyname , +.Dq yyrule , +and +.Dq yycheck , +are extracted from the current version of +.Xr yacc 1 . +.Sh FILES +.Bl -tag -width y.tab.c +.It Pa y.tab.c +File from which tables are extracted. +.El +.Sh SEE ALSO +.Xr yacc 1 +.Sh HISTORY +The +.Nm +command first appeared in +.Bx 4.4 . diff --git a/yacc/yyfix.sh b/yacc/yyfix.sh @@ -0,0 +1,73 @@ +#!/bin/sh - +# +# $OpenBSD: yyfix.sh,v 1.3 2009/06/12 13:33:29 sobrado Exp $ +# Copyright (c) 1990 The Regents of the University of California. +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# 3. Neither the name of the University nor the names of its contributors +# may be used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +# ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +# OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +# OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +# SUCH DAMAGE. +# +# from: @(#)yyfix.sh 5.2 (Berkeley) 5/12/90 +# +OLDYACC="yyexca yyact yypact yypgo yyr1 yyr2 yychk yydef" +NEWYACC="yylhs yylen yydefred yydgoto yysindex yyrindex yygindex \ + yytable yycheck" + +if [ $# -eq 0 ]; then + echo "usage: `basename $0` file [tables]" >&2 + exit 1 +fi + +file=$1 +>$file +shift + +if [ $# -eq 0 ] ; then + if grep yylhs y.tab.c > /dev/null ; then + if grep yyname y.tab.c > /dev/null ; then + NEWYACC="$NEWYACC yyname" + fi + if grep yyrule y.tab.c > /dev/null ; then + NEWYACC="$NEWYACC yyrule" + fi + set $NEWYACC + else + set $OLDYACC + fi +fi + +for i +do +ed - y.tab.c << END +/^\(.*\)$i[ ]*\[]/s//extern \1 $i[];\\ +\1 $i []/ +.ka +/}/kb +'br $file +'a,.w $file +'a,.d +w +q +END +done