Example 1: An interpreted deterministic top-down, left-right recursive descent context-free recogniser

Warning: This recogniser is far from being an optimised implementation. It is intended for teaching use only.

Note that in this recogniser, the grammar is represented in a switch statement, rather than being stored in a separate data structure.

// cf_recog_td_lr_d_int.pc
// D.Gibbon, 9 Nov 2001

// ------------------------------------

empty(string s){
	return (s=="");
}

match(string s1, string s2){
	return (s1==s2);
}

emit(string s){
	alert("Emit: "+s);
}

// ------------------------------------

first(string s){
	int firstlen;
	string f;
	firstlen=strstr(s," ",0);
	if(firstlen==-1)
		f=s;
	else
		f=strleft(s,firstlen);
	return f;
}


rest(string s){
	int firstlen;
	string r;
	firstlen=strstr(s," ",0);
	if(firstlen==-1)
		r="";
	else
		r=strright(s,strlen(s)-firstlen-1);
	return r;
}

// ------------------------------------

terminal(string s){
        return (s=="John"||s=="Mary"||s=="laughed"||s=="loud");
}

nonterminal(string s){
        return (s=="S"||s=="N"||s=="V"||s=="Adv");
}

initial(){
        return "S";
}

// ------------------------------------

rewrite(string f, string r){
string rhs;
	switch(f){
		case "S":
			rhs="N V Adv";
			break;
		case "N":
			rhs="John";
			break;
		case "V":
			rhs="laughed";
			break;
		case "Adv":
			rhs="loud";
			break;
	}
	if(r!="")
		r=" "+r;
	return rhs+r;
}

parse_deterministic(string in, string agenda){
	string inf,inr,derf,derr;
	if(empty(in))
		if(empty(agenda))
			emit("true");
		else
			emit("end of input");
	else
	if(empty(agenda))
		emit("end of agenda");
	else {
		inf=first(in);
		inr=rest(in);
		derf=first(agenda);
		derr=rest(agenda);
		if(terminal(derf))
			if(match(inf,derf))
				parse_deterministic(inr,derr);
			else emit("unknown terminal");
		else
			if(nonterminal(derf))
				parse_deterministic(in,rewrite(derf,derr));
			else
				emit("unknown nonterminal");
	}
}

main(){
	parse_deterministic("John laughed loud",initial());
}

Tasks:

1. Extract the grammar used in this example, and write it down with context-free rules. Standard: easy.
2. Write comments for this program, documenting what the different procedures do. Standard: medium.
3. Port this program to another language (e.g. JavaScript). Standard: hard.
4. Make the recogniser into a parser which builds structure descriptions in the form of well-formed labelled bracketings, e.g. (S (NP (Nom perfume)) (VP (V smells))). Standard: hard.
5. Add a user interface to your program which draws trees. Standard: hardest.