Example 2: A compiled non-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 the grammar used in this example is completely integrated into the program:

1. The grammar rules are represented directly as procedures.
2. The nonterminal symbols are used to name the procedures.
3. The right hand side of each grammar rule is represented as a composed function of non-terminal symbols, with the innermost function corresponding to the leftmost nonterminal symbol.
4. The procedures return the unparsed rightmost portion of the string for further processing at the next level up in procedures which represent the composed function.
5. If a terminal symbol match fails, a "fail!" string is returned which is used to halt processing at each level in the procedures which represent the composed function.

Note that this compiled grammar style is not very suitable for continuous development purposes. It would be much better to develop the grammar as context-free rules, and write a translation program which compiles the grammar into a program, adding all the necessary procedural details.

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

// Utilities

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;
}

// Pre-terminal (lexical) rules

v(string in){
	string f,r,out;
	f=first(in);r=rest(in);
	if(f=="saw"||f=="met"||f=="laughed")
		out=r;
	else
		out="!";
	return out;
}

n(string in){
	string f,r,out;
	f=first(in);r=rest(in);
	if(f=="dog"||f=="cat")
		out=r;
	else
		out="!";
	return out;
}

adj(string in){
	string f,r,out;
	f=first(in);r=rest(in);
	if(f=="small"||f=="big"||f=="black")
		out=r;
	else
		out="!";
	return out;
}

det(string in){
	string f,r,out;
	f=first(in);r=rest(in);
	if(f=="the"||f=="this"||f=="a")
		out=r;
	else
		out="!";
	return out;
}

// Non-terminal (phrasal) rules

nom(string in){
	string out;
	if(in=="!")
		out=in;
	else {
		out=nom(adj(in));
		if(out=="!")
			out=n(in);
	}
	return out;
}

np(string in){
	string out;
	if(in=="!")
		out=in;
	else {
		out=nom(det(in));
		if(out=="!")
			out=nom(in);
	}
	return out;
}

vp(string in){
	string out;
	if(in=="!")
		out=in;
	else {
		out=np(v(in));
		if(out=="!")
			out=v(in);
	}
	return out;
}

s(string in){
	string out;
	out=vp(np(in));
	return out;
}

main(){
	string in,out;
	in="the big big black dog saw a cat";
	while(in!=""){
		in=getsd("Input: ",in);
		if(in!=""){
			out=s(in);
			if(out=="")
				puts("Accepted!"+"\n");
			else
				puts("Rejected!"+"\n");
		}
	}
}

Tasks:

1. Extract the grammar used in this example, and write it down with context-f ree 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 t he form of well-formed labelled bracketings, e.g. (S (NP (Nom perfume)) (VP (V s mells))). Standard: hard.
5. Add a user interface to your program which draws trees. Standard: hardest.