reader.c

从lex&yacc说到编译器

int get_number()
{
    register int c;
    register int n;

    n = 0;
    for (c = *cptr; isdigit(c); c = *++cptr)
	n = 10*n + (c - '0');
    return (n);
}

// 
// Date: Mon, 29 Jun 1998 16:36:47 +0200
// From: Matthias Meixner <[e-mail]>
// Organization: TH Darmstadt, Mikroelektronische Systeme
// 
// While using your version of BTYacc (V2.1), I have found a bug. 
// It does not correctly
// handle typenames, if one typename is a prefix of another one and
// if this type is used after the longer one. In this case BTYacc 
// produces invalid code.
// 
// e.g. in:
// --------------------------------------------
// %{
//  
// #include <stdlib.h>
//   
//    struct List {
//       struct List *next;
//       int foo;
//    };
//  
// %}
// %union {
//    struct List *fooList;
//    int foo;
// }
//  
// %type <fooList> a
// %type <foo> b
//  
// %token <foo> A 
//  
// %%
//  
// a: b   {$$=malloc(sizeof(*$$));$$->next=NULL;$$->foo=$1;}
//  | a b {$$=malloc(sizeof(*$$));$$->next=$1;$$->foo=$2;}
//  
// b: A {$$=$1;}
// 
static char *cache_tag(char *tag, int len)
{
int	i;
char	*s;

    for (i = 0; i < ntags; ++i) {
	if (strncmp(tag, tag_table[i], len) == 0 &&  
	    // VM: this is bug fix proposed by Matthias Meixner
	    tag_table[i][len]==0)
	    return (tag_table[i]); }
    if (ntags >= tagmax) {
	tagmax += 16;
	tag_table = tag_table ? RENEW(tag_table, tagmax, char *)
			      : NEW2(tagmax, char *);
	if (tag_table == 0) no_space(); }
    s = MALLOC(len + 1);
    if (s == 0) no_space();
    strncpy(s, tag, len);
    s[len] = 0;
    tag_table[ntags++] = s;
    return s;
}

char *get_tag()
{
    register int c;
    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 = *++cptr; } while (IS_IDENT(c));

    c = nextc();
    if (c == EOF) unexpected_EOF();
    if (c != '>')
	illegal_tag(t_lineno, t_line, t_cptr);
    ++cptr;

    FREE(t_line);
    havetags = 1;
    return cache_tag(cache, cinc);
}

static char *scan_id(void)
{
char	*b = cptr;

    while (isalnum(*cptr) || *cptr == '_' || *cptr == '$') cptr++;
    return cache_tag(b, cptr-b);
}

void declare_tokens(int assoc)
{
    register int c;
    register 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(); } }
}

static void declare_argtypes(bucket *bp)
{
char	*tags[MAXARGS];
int	args = 0, c;

    if (bp->args >= 0) retyped_warning(bp->name);
    cptr++; /* skip open paren */
    for (;;) {
	c = nextc();
	if (c == EOF) unexpected_EOF();
	if (c != '<') syntax_error(lineno, line, cptr);
	tags[args++] = get_tag();
	c = nextc();
	if (c == ')') break;
	if (c == EOF) unexpected_EOF(); }
    cptr++; /* skip close paren */
    bp->args = args;
    if (!(bp->argnames = NEW2(args, char *))) no_space();
    if (!(bp->argtags = NEW2(args, char *))) no_space();
    while (--args >= 0) {
	bp->argtags[args] = tags[args];
	bp->argnames[args] = 0; }
}

void declare_types()
{
    register int c;
    register bucket *bp=0;
    char *tag=0;

    c = nextc();
    if (c == '<') {
	tag = get_tag();
	c = nextc(); }
    if (c == EOF) unexpected_EOF();

    for (;;) {
	c = nextc();
	if (isalpha(c) || c == '_' || c == '.' || c == '$') {
	    bp = get_name();
	    if (nextc() == '(')
		declare_argtypes(bp);
	    else
		bp->args = 0; }
	else if (c == '\'' || c == '"') {
	    bp = get_literal();
	    bp->args = 0; }
	else
	    return;

	if (tag) {
	    if (bp->tag && tag != bp->tag)
		retyped_warning(bp->name);
	    bp->tag = tag; } }
}

void declare_start()
{
    register int c;
    register 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()
{
    register int c, k;

    cache_size = 256;
    cache = MALLOC(cache_size);
    if (cache == 0) 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 TYPE:
	    declare_types();
	    break;
	case START:
	    declare_start();
	    break; } }
}

void initialize_grammar()
{
    nitems = 4;
    maxitems = 300;
    pitem = NEW2(maxitems, bucket *);
    if (pitem == 0) no_space();
    pitem[0] = 0;
    pitem[1] = 0;
    pitem[2] = 0;
    pitem[3] = 0;

    nrules = 3;
    maxrules = 100;
    plhs = NEW2(maxrules, bucket *);
    if (plhs == 0) no_space();
    plhs[0] = 0;
    plhs[1] = 0;
    plhs[2] = 0;
    rprec = NEW2(maxrules, Yshort);
    if (rprec == 0) no_space();
    rprec[0] = 0;
    rprec[1] = 0;
    rprec[2] = 0;
    rassoc = NEW2(maxrules, char);
    if (rassoc == 0) no_space();
    rassoc[0] = TOKEN;
    rassoc[1] = TOKEN;
    rassoc[2] = TOKEN;
}

void expand_items()
{
    maxitems += 300;
    pitem = RENEW(pitem, maxitems, bucket *);
    if (pitem == 0) no_space();
}

void expand_rules()
{
    maxrules += 100;
    plhs = RENEW(plhs, maxrules, bucket *);
    if (plhs == 0) no_space();
    rprec = RENEW(rprec, maxrules, Yshort);
    if (rprec == 0) no_space();
    rassoc = RENEW(rassoc, maxrules, char);
    if (rassoc == 0) no_space();
}

/* set in copy_args and incremented by the various routines that will rescan
** the argument list as appropriate */
static int rescan_lineno;

static char *copy_args(int *alen)
{
struct mstring	*s = msnew();
int		depth = 0, len = 1, c;
char		quote = 0;
int		a_lineno = lineno;
char		*a_line = dup_line();
char		*a_cptr = a_line + (cptr - line - 1);

    rescan_lineno = lineno;
    while ((c = *cptr++) != ')' || depth || quote) {
	if (c == ',' && !quote && !depth) {
	    len++;
	    mputc(s, 0);
	    continue; }
	mputc(s, c);
	if (c == '\n') {
	    get_line();
	    if (!line) {
		if (quote)
		    unterminated_string(a_lineno, a_line, a_cptr);
		else
		    unterminated_arglist(a_lineno, a_line, a_cptr); } }
	else if (quote) {
	    if (c == quote) quote = 0;
	    else if (c == '\\') {
		if (*cptr != '\n') mputc(s, *cptr++); } }
	else {
	    if (c == '(') depth++;
	    else if (c == ')') depth--;
	    else if (c == '\"' || c == '\'') quote = c; } }
    if (alen) *alen = len;
    FREE(a_line);
    return msdone(s);
}

static char *parse_id(char *p, char **save)
{
char	*b;

    while (isspace(*p)) if (*p++ == '\n') rescan_lineno++;
    if (!isalpha(*p) && *p != '_') return 0;
    b = p;
    while (isalnum(*p) || *p == '_' || *p == '$') p++;
    if (save) {
	*save = cache_tag(b, p-b); }
    return p;
}

static char *parse_int(char *p, int *save)
{
int	neg=0, val=0;

    while (isspace(*p)) if (*p++ == '\n') rescan_lineno++;
    if (*p == '-') {
	neg=1;
	p++; }
    if (!isdigit(*p)) return 0;
    while (isdigit(*p))
	val = val*10 + *p++ - '0';
    if (neg) val = -val;
    if (save) *save = val;
    return p;
}

static void parse_arginfo(bucket *a, char *args, int argslen)
{
char	*p=args, *tmp;
int	i, redec=0;

    if (a->args >= 0) {
	if (a->args != argslen)
	    error(rescan_lineno, 0, 0, "number of arguments of %s does't "
		  "agree with previous declaration", a->name);
	redec = 1; }
    else {
	if (!(a->args = argslen)) return;
	if (!(a->argnames = NEW2(argslen, char *)) ||
	    !(a->argtags = NEW2(argslen, char *)))
	    no_space(); }
    if (!args) return;
    for (i=0; i<argslen; i++) {
	while (isspace(*p)) if (*p++ == '\n') rescan_lineno++;
	if (*p++ != '$') bad_formals();
	while (isspace(*p)) if (*p++ == '\n') rescan_lineno++;
	if (*p == '<') {
	    havetags = 1;
	    if (!(p = parse_id(p+1, &tmp))) bad_formals();
	    while (isspace(*p)) if (*p++ == '\n') rescan_lineno++;
	    if (*p++ != '>') bad_formals();
	    if (redec) {
		if (a->argtags[i] != tmp)
		    error(rescan_lineno, 0, 0, "type of argument %d to %s "
			  "doesn't agree with previous declaration", i+1,
			  a->name); }
	    else
		a->argtags[i] = tmp; }
	else if (!redec)
	    a->argtags[i] = 0;
	if (!(p = parse_id(p, &a->argnames[i]))) bad_formals();
	while (isspace(*p)) if (*p++ == '\n') rescan_lineno++;
	if (*p++) bad_formals(); }
    free(args);
}

static char *compile_arg(char **theptr, char *yyvaltag)
{
char		*p = *theptr;
struct mstring	*c = msnew();
int		i, j, n;
Yshort		*offsets=0, maxoffset;
bucket		**rhs;

    maxoffset = n = 0;
    for (i = nitems - 1; pitem[i]; --i) {
	n++;
	if (pitem[i]->class != ARGUMENT)
	    maxoffset++; }
    if (maxoffset > 0) {
	offsets = NEW2(maxoffset+1, Yshort);
	if (offsets == 0) no_space(); }
    for (j=0, i++; i<nitems; i++)
	if (pitem[i]->class != ARGUMENT)
	    offsets[++j] = i - nitems + 1;
    rhs = pitem + nitems - 1;

    if (yyvaltag)
	msprintf(c, "yyval.%s = ", yyvaltag);
    else
	msprintf(c, "yyval = ");
    while (*p) {
      if (*p == '$') {
	char	*tag = 0;
	if (*++p == '<')
	  if (!(p = parse_id(++p, &tag)) || *p++ != '>')
	    illegal_tag(rescan_lineno, 0, 0);
	if (isdigit(*p) || *p == '-') {
	  int val;
	  if (!(p = parse_int(p, &val)))
	    dollar_error(rescan_lineno, 0, 0);
	  if (val <= 0) i = val - n;
	  else if (val > maxoffset) {
	    dollar_warning(rescan_lineno, val);
	    i = val - maxoffset; 
	  } else {
	    i = offsets[val];
	    if (!tag && !(tag = rhs[i]->tag) && havetags)
	      untyped_rhs(val, rhs[i]->name); 
	  }
	  msprintf(c, "yyvsp[%d]", i);
	  if (tag) msprintf(c, ".%s", tag);
	  else if (havetags)
	    unknown_rhs(val); 
	} else if (isalpha(*p) || *p == '_') {
	  char	*arg;
	  if (!(p = parse_id(p, &arg)))
	    dollar_error(rescan_lineno, 0, 0);
	  for (i=plhs[nrules]->args-1; i>=0; i--)
	    if (arg == plhs[nrules]->argnames[i]) break;
	  if (i<0)
	    error(rescan_lineno, 0, 0, "unknown argument $%s", arg);
	  if (!tag)
	    tag = plhs[nrules]->argtags[i];
	  msprintf(c, "yyvsp[%d]", i - plhs[nrules]->args + 1 - n);
	  if (tag) msprintf(c, ".%s", tag);
	  else if (havetags)
	    error(rescan_lineno, 0, 0, "untyped argument $%s", arg); }
	else
	  dollar_error(rescan_lineno, 0, 0); 
      } else {
	if (*p == '\n') rescan_lineno++;
	mputc(c, *p++); 
      } 
    }
    *theptr = p;
    if (maxoffset > 0) FREE(offsets);
    return msdone(c);
}

#define ARG_CACHE_SIZE	1024
static struct arg_cache {
    struct arg_cache	*next;
    char		*code;
    int			rule;
    } *arg_cache[ARG_CACHE_SIZE];

static int lookup_arg_cache(char *code)
{
struct arg_cache	*entry;

    entry = arg_cache[strnshash(code) % ARG_CACHE_SIZE];
    while (entry) {
	if (!strnscmp(entry->code, code)) return entry->rule;
	entry = entry->next; }
    return -1;
}

static void insert_arg_cache(char *code, int rule)
{
struct arg_cache	*entry = NEW(struct arg_cache);
int			i;

    if (!entry) no_space();
    i = strnshash(code) % ARG_CACHE_SIZE;
    entry->code = code;
    entry->rule = rule;
    entry->next = arg_cache[i];
    arg_cache[i] = entry;
}

static void clean_arg_cache(void)
{
struct arg_cache	*e, *t;
int			i;

    for (i=0; i<ARG_CACHE_SIZE; i++) {
	for (e=arg_cache[i]; (t=e); e=e->next, FREE(t))
	    free(e->code);
	arg_cache[i] = 0; }
}

void advance_to_start()
{
    register int c;
    register bucket *bp;
    char *s_cptr;
    int s_lineno;
    char	*args = 0;
    int		argslen = 0;

    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 == 0) {
	if (bp->class == TERM)
	    terminal_start(bp->name);
	goal = bp; }

    s_lineno = lineno;
    c = nextc();
    if (c == EOF) unexpected_EOF();
    if (c == '(') {
	++cptr;
	args = copy_args(&argslen);
	if (args == 0) no_space();
	c = nextc(); }
    if (c != ':') syntax_error(lineno, line, cptr);
    start_rule(bp, s_lineno);
    parse_arginfo(bp, args, argslen);
    ++cptr;
}

void start_rule(bucket *bp, int s_lineno)
{
    if (bp->class == TERM)
	terminal_lhs(s_lineno);
    bp->class = NONTERM;
    if (!bp->index) bp->index = nrules;
    if (nrules >= maxrules)
	expand_rules();
    plhs[nrules] = bp;
    rprec[nrules] = UNDEFINED;
    rassoc[nrules] = TOKEN;
}

void end_rule()
{
    register int i;

    if (!last_was_action && plhs[nrules]->tag) {
	for (i = nitems - 1; pitem[i]; --i) continue;
	if (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()
{
    register bucket *bp, **bpp;

    assert(cache);
    sprintf(cache, "$$%d", ++gensym);
    bp = make_bucket(cache);
    last_symbol->next = bp;
    last_symbol = bp;
    bp->tag = plhs[nrules]->tag;
    bp->class = ACTION;