Recursive grammar exercise

Excerpted from section 6.2 of the textbook:

A language is a set of strings of symbols from a finite alphabet. You can define the set of all syntactically correct Java programs. The set is the language

Java programs = {strings w: w is a syntactically correct Java program}

A grammar states the rules of a language, and uses several special symbols:

x | y means x or y
x y means x followed by y
< word > means any instance of word that definition defines

A grammar for the language

Java Ids = { w : w is a legal Java identifier}

is simple so we begin with it. A legal Java identifier begins with a letter and is followed by zero or more letters and digits. In this context, the underscore ( _ ) and dollar sign ( $ ) are letters. A syntax diagram is convenient for people to use (as shown in class), but a grammar is a better starting point if you want to write a method that will recognize an identifier.

A grammar for the language is

< identifier > = < Java letter > | < identifier > < Java letter > | < identifier > < digit > 
< Java letter > = a | b | ... | z | A | B | ... | Z | _ | $
< digit > = 0 | 1 | ... | 9

The definition reads as follows: An identifier is a letter, or an identifier followed by a letter, or an identifier followed by a digit. Note that identifier appears in its own definition: This grammar is recursive, as are many grammars.

The pseudocode for a recursive valued method that determines whether a String is in JavaIds follows:

isId (in w : String) : boolean
// Returns true if w is a legal Java identifier;
// Otherwise returns false.
   if (w is of length 1) { // base case
	if (w is a Java letter) {
		return true;
	}
	else {
		return false;
	}
   }
   else if (the last character of w is a Java letter or a digit) {
	return isId (w minus its last character)  // Point X
   }
   else {
	return false;
   } // end if

Exercise: Implement and test the above algorithm. Define helper methods as needed.