Recursive-Descent Recognizer

6.18, 6.19, 6.20, 6.23, 6.25, 6.26, 6.42, 6.48, 6.49, 6.50, 6.51


6.15 Finish writing the the pseudocode for a recursive-descent recognizer for the English grammar of Section 6.2 that was begun in Section 6.6.


void sentence() {
    nounPhrase();
    verbPhrase();
}


void nounPhrase() {
    article();
    noun();
}


void article() {
    if (token == "a") {
        match("a", "a expected");
    } 
    else if (token == "the") {
        match("the", "the expected");
    }
    else {
        error("article expected");
    }
}


void noun() {


    if (token == "girl") {
        match("girl", "girl expected");
    } 
    else if (token == "dog") {
        match("dog", "dog expected");
    }
    else {
        error("noun expected");
    }


}


void verbPhrase() {


    verb();
    nounPhrase();


}


void verb() {


    if (token == "sees") {
        match("sees", "sees expected");
    } 
    else if (token == "pets") {
        match("pets", "pets expected");
    }
    else {
        error("verb expected");
    }


}


void match(TokenType expected, char* message) {
    if (token == expected) {
        getToken();
    }
    else {
        error(message);
    }
}


6.16 


The following implementation is coded up in Java with the StringTokenizer class: 
http://pastie.org/3746764

The idea is to go through a string and the token to a word, and then process that word seeing..

/**
 * 
 */
package com.knownasilya.hw.pl;

import java.util.StringTokenizer; 


/**
 * @author ilya radchenko
 *
 */
public class RDR {

 private String token;
 private StringTokenizer st;
 private boolean isSentence = true;
 private boolean endOfSentence = false;
 
 
 RDR(String sentence){
  st = new StringTokenizer(sentence, " ");
 }

 
 private void sentence(){
  nounPhrase();
  verbPhrase();
 }
 
 private void nounPhrase(){
  article();
  noun();
 }
 
 private void article(){
  if (token.equals("a")) {
         match("a", "a expected");
     } 
     else if (token.equals("the")) {
         match("the", "the expected");
     }
     else {
      isSentence = false;
      System.out.println("article expected");
     }
 }
 
 private void noun() {
     if (token.equals("girl")) {
         match("girl", "girl expected");
     } 
     else if (token.equals("dog")) {
         match("dog", "dog expected");
     }
     else {
      isSentence = false;
      System.out.println("noun expected");
     }
 }

 private void verbPhrase() {
     verb();
     nounPhrase();
 }

 private void verb() {
     if (token.equals("sees")) {
         match("sees", "sees expected");
     } 
     else if (token.equals("pets")) {
         match("pets", "pets expected");
     }
     else {
      isSentence = false;
      System.out.println("verb expected");
     }
 }
 
 private void match(String expected, String message) {
     if (token.equals(expected)) {
      if(st.hasMoreTokens()){
       System.out.println("Match: " + token);
       token = st.nextToken();
      }
      else {
       System.out.println("Match: " + token);
       endOfSentence = true;
      }
     }
     else {
         System.out.println(message);
     }
 }
 
 public String parse(){
  while(st.hasMoreTokens() && !endOfSentence){
   token = st.nextToken();
   this.sentence();
  }
  
  if(isSentence){
   return "The given text was a proper sentence.";
  }
  else {
   return "The given text was NOT a proper sentence.";
  }
 }


 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  RDR test = new RDR("the girl pets a dog");
  
  System.out.println(test.parse());
 }

}

6.18 Modify the recursive-descent calculator program of Figure 6.24 to use the grammar of Figure 6.26 and the scanner of Figure 6.1 (so that the calculator also skips blanks appropriately).