// parse.c
//    natural language top-down parser
//    per Boonserm teaching slides
//    Prabhas Chongstitvatana
//    17 Nov 2012

//    using list as main data structure

#include "ailib.h"
#include "parse.h"

#define   YES		1
#define   NO        0

int input, grammar, lexicon, state;

void error(char *mess){
    printf("%s\n",mess);
    exit(0);
}

void init(void){
    grammar = makegrammar();
    lexicon = makevocab();
    input = makeinput();
	state = makestate();
}

int isrule(int a){
    return head(a) == TYRULE;
}

int islex(int a){
    return head(a) == TYLEX;
}

// return item associate with key from ls
int asso(int key, int ls){
    int a;
    if( ls == NIL ) return NIL;
    a = head(ls);
    if( atom_eq(key,head(a)) ) return tail(a);
    return asso(key,tail(ls));
}

// match w to any words in set v (lexicon)
int match(int v, int w){
    if( v == NIL ) return NO;
    if( name_eq(head(v),w) ) return YES;
    return match(tail(v),w);
}

PRIVATE void print_rule(int lhs, int rhs){
    printf("rule: ");
    print_list(lhs);
    printf("-> ");
    print_list(rhs);
    nl();
}

PRIVATE void print_lex(int lhs, int rhs){
    printf("lex: ");
    print_list(lhs);
    printf("-> ");
    print_list(rhs);
    nl();
}

PRIVATE void print_match(int w){
	printf("match: ");
	print_list(w);
	nl();
}

int merge2(int ls1, int ls2);

// merge two lists into one
int merge(int ls1, int ls2){
	return merge2(revlist(ls1),ls2);
}

int merge2(int ls1, int ls2){
	if( ls1 == NIL ) return ls2;
	return merge2(tail(ls1),cons(head(ls1),ls2));
}

int subs2(int rules, int state, int inp){
	int a, s;
	if( rules == NIL ) return NIL;
	a = merge(head(rules),state);
	s = cons(a,list(inp));
	return cons(s,subs2(tail(rules),state,inp));
}

// check success ( NIL, (NIL))
int success(int s){
	return (head(s) == NIL) && (head(tail(s)) == NIL);
}

PRIVATE int cnt = 0;

int parse(int s){
	int s1, in, rule, t, rhs;

	if( cnt++ > 30 ) exit(0);	// prevent inf loop

	if( s == NIL ) return NO;
	s1 = head(s);		// s1, current state
	if( success(s1) ) return YES;
	print_list(s); nl();
	//  generate next state
	rule = head(s1);
	in = head(tail(s1));
	t = head(rule);		// first symbol
	if( islex(t) ){
		rhs = head(asso(t,lexicon));
		print_lex(t,rhs);
        if( match(rhs,head(in)) ){
        	print_match(head(in));
			// remove first symbol and move input
			s1 = cons(tail(rule),list(tail(in)));
			s = cons(s1,tail(s));
		}else{  // backup
			s = tail(s);
		}
	}else if( isrule(t) ){
		rhs = asso(t,grammar);
		print_rule(t,rhs);
		s1 = subs2(rhs,tail(rule),in);
		s = merge(s1,tail(s));
	}else{ // backup
		s = tail(s);
	}
	return parse(s);
}

int main(void){
    init();
	if( parse(state) )
		printf("yes");
	else
		printf("no");
    return 0;
}