Comp 212 - Spring 04 

Lab 11: Recursive Descent Parsing

Introduction

 This lab constitutes the implementation of a recursive descent parser discussed in lecture #30.

Lab Activities

Divide the lab into 3 groups.  Each group should set up a public share directory for all the lab mates to copy the code.

1. One group builds the union of tokens: AToken and its concrete variants
   
   • Union of Tokens

   public abstract class AToken {
       protected String _lexeme;
       protected AToken(String lex) { _lexeme = lex; }
       public String toString() { return_lexeme;}
       public abstract Object execute(ATokVisitor v, Object inp);
   }

   public class IdToken extends AToken{
       // constructor, etc.
       public Object execute(ATokVisitor v, Object inp) { 
           return v.idCase(this, inp);)
       }
   }
   
   // other concrete token classes to be written.

   • Token visitors: the variant behaviors of the tokens are encapsulated in an abstract visitor class, as follows.

   public abstract class ATokVisitor {
       /**
       * This is the case when the host is a concrete IdToken.
       * Throws an IllegalArgumentException as default behavior.
       * @param host a concrete IdToken.
       * @param inp the input needed for this ATokVisitor to perform its task.
       */
       protected abstract Object defaultCase(AToken host, Object inp) {
           // In many concrete cases, the code will look something like:
           // throw new IllegalArgumentException("Wrong token!");
       }
       public Object idCase(IdToken host, Object inp) {
           return defaultCase(host, inp);
       }
       // etc..., a method for each concrete token case to be written
   }

   This should be trivial.  After this group is done, it should split in two subgroups: one would join group 2 and the other would join group 3 in order to communicate their results to the other groups.
   

2. One group builds the tokenizer StreamTokWrapper: play around with TestStreamTokenizer and modify it using a file with a scheme arithmetic expression as input.  
   First, try to keep things simple and tokenize number and words that not alphanumeric.  
   Just try to get something to compile that can tokenize simple expressions such as  ( + xy 34).  You can work on enhancing the tokenizer later.
   
   public interface ITokenizer (
      public AToken getNextToken();
   }

   public class StreamTokWrapper implements ITokenizer {
       private StreamTokenizer _st;
       // constructor and methods, etc...
   }

3. One group write the recursive descent parser.  This will involve writing all the needed visitors as anonymous inner classes.  See the solution of homework #3 for all the required AST classes and interfaces.
   
   public interface IASTFactory {
       public IAST makeAST(); 
   }
   
   public class RdpASTFactory implements IASTFactory {
       private ITokenizer _tokenizer:
       public RdpASTFactory(ITokenizer tokenizer) { _tokenizer = tokenizer;}
       public IAST makeAST() { // etc...}
       private IAST makeLeaf() { // etc...}
       // other (private) factory methods, etc.
   }

To test the code, download the solution to homework #3, unzip it, and move the various java files into their appropriate subdirectories to match the packaging.

Have fun!

Dung X. Nguyen 
revised 03/29/2004