%{

	#include <string.h>
	#include <stdio.h>
	#include <ctype.h>
	#include <stdlib.h>
	
	typedef struct _List {
		int type;		//0 - number, 1 - edef, 2 - fnode
		int number;
		char *edef;
		struct _List *fnode;	//first node
		struct _List *next;
	} List;
	
	typedef struct _Definition {
		char *name;
		List *list;
	} Definition;
	
	typedef struct _MyType {
		char string[20];
		int number;
		List *list;
	} MyType;
	#define YYSTYPE MyType
	#define DEF_COUNT 32
	int yylex (void);
	void yyerror (char const *);
	
	Definition global_def[DEF_COUNT];
	int global_def_i = 0;
	
	
List *list_new(int type)
{
	List *ret = malloc(sizeof(List));
	memset(ret, 0, sizeof(List));
	ret -> type = type;
	return ret;
}
List *get_list(char *name)
{
	int i;
	for (i = 0; i < global_def_i; ++i) {
		if (strcmp(name, global_def[i].name) == 0) return global_def[i].list;
	}
	return NULL;
}

int is_equal_list(List *a, List *b)
{
	if (a -> type == b -> type && a -> type != 1) {
		if (a -> type == 0) {
			if (a -> number == b -> number)  return 1;
			else return 0;
		} else {
			List *ta = a -> fnode, *tb = b -> fnode;
			while(ta && tb) {
				if (!is_equal_list(ta, tb)) return 0;
				ta = ta -> next;
				tb = tb -> next;
			}
			if (ta != tb) return 0;
			else return 1;	//all NULL
		}
	}
	if (a -> type == 1 && strcmp(a -> edef, b -> edef) == 0) return 1;
	
	if (a -> type == 1) {
		List *ta = get_list(a -> edef);
		if (ta == NULL) return 0;
		return is_equal_list(ta, b);
	}
	if (b -> type == 1) {
		List *tb = get_list(b -> edef);
		if (tb == NULL) return 0;
		return is_equal_list(a, tb);
	}
	return 0;
}

int is_equal_str(char *a1, char *a2)
{
	List *lt1 = get_list(a1), *lt2 = get_list(a2);
	
	if (!lt1 || !lt2) return 0;
	return is_equal_list(lt1, lt2);
}

%}

%token NUMBER STRING
%token EOD EOE

%%
input:
        | definitions EOD interrogations EOE
;

definitions: STRING '=' dlist {
		global_def[global_def_i].name = strdup($1.string);
		global_def[global_def_i].list = $3.list;
		global_def_i ++;
	}
	| definitions STRING '=' dlist {
		global_def[global_def_i].name = strdup($2.string);
		global_def[global_def_i].list = $4.list;
		global_def_i ++;
	}
;

dlist: NUMBER {
		List *a = list_new(0);
		a -> number = $1.number;
		$$.list = a;
	}
	| STRING {
		List *a = list_new(1);
		a -> edef = strdup($1.string);
		$$.list = a;
	}
	| '(' list_group ')' {
		List *a = list_new(2);
		a -> fnode = $2.list;
		$$.list = a;
	}
;

list_group: dlist {
		$$.list = $1.list;
	}
	| dlist list_group {
		$1.list -> next = $2.list;
		$$.list = $1.list;
	}
;

interrogations: STRING '?' STRING {
		if (is_equal_str($1.string, $3.string)) {
			printf("1\n");
		} else {
			printf("0\n");
		}
	}
	| interrogations STRING '?' STRING {
		if (is_equal_str($2.string, $4.string)) {
			printf("1\n");
		} else {
			printf("0\n");
		}
	}
;

%%

int main (int argc, char *argv[])
{
	int i;
	freopen(argv[1], "r", stdin);
	yyparse ();
}


int yylex (void)
{
	int c;
	
	while ((c = getchar ()) == ' ' || c == '\t' || c == '\n');

	if (isdigit (c)) {
		ungetc (c, stdin);
		scanf ("%d", &yylval.number);
		return NUMBER;
	} else if (isalpha (c)) {
		int i = 0;
		ungetc (c, stdin);
		while (isalpha( (c = getchar()) )) {
			yylval.string[i++] = c;
		}
		ungetc (c, stdin);
		yylval.string[i] = 0;
		for (i--; i >= 0; --i) yylval.string[i] = toupper(yylval.string[i]);
		if (strcmp(yylval.string, "EOD") == 0) return EOD;
		if (strcmp(yylval.string, "EOE") == 0) return EOE;
		return STRING;
	}
	
	if (c == EOF) return 0;
	return c;
}

void yyerror (char const *s)
{
	fprintf (stderr, "%s\n", s);
}

=============================================================================
不要用bison编译（生成c代码太长），用byacc编译。。。
不过还是不行，不知是词法分析不行还是有什么情况没考虑到。
大伙帮忙看看。

• 有没有注意到样例中这一句 (53) lda 2008-09-22 01:54:08