CSc 109 Test 2     Wednesday  25 April 2001
   SUGGESTED ANSWERS
   1.  (See also question 2, which uses the answer to this question)
   Write a class Toke which reads from an input stream and analyzes the
   stream one character at a time.  The class should have the public method
   sym() which returns an int and public method next() which gets the next
   character in the input stream.  The method sym() only returns one of four
   possible values:  if the character read is '{' then sym() returns
   Toke::LPAR, if the character read is '}' then sym() returns Toke::RPAR,
   if the character read is '\n' then sym() returns Toke::EOLN; otherwise
   sym() returns Toke::JUNK.  In practice, the above constants should have
   the values LPAR==0, RPAR==1, EOLN==2, JUNK==3.  The class Toke might be
   used as follows:
       Toke t(cin);

       cout<<t.sym()<<endl;
       t.next();
       cout<<t.sym()<<endl;
       ....


class Toke{
  public:
    static const int LPAR=0, RPAR=1, EOLN=2, JUNK=3;
    Toke(istream &in);
    int sym();
    void next();
  private:
    istream *fin;
    int val;
    char ch;
};

Toke::Toke(istream &in){
  fin=&in;
  ch='z';  //junk to prime the pump
  next();
}

int Toke::sym(){
  return val;
}

void Toke::next(){
  if(fin->good())
    fin->get(ch);
  if(!fin->good())
    ch='\n';
  switch(ch){
    case '{': val = LPAR; break;
    case '}': val = RPAR; break;
    case '\n': val = EOLN; break;
    default: val=JUNK;
  }
}

   2.  Assume we have the grammar given by the following syntax diagrams.
                                                             -
   Here I denote circles with parentheses () and boxes by   | |
                    -             -                          -
      S--> ({) --> |T| -->(})--> |T| -->
                    -             -
      T ------------------          (T could be replaced by nothing)
          |               |
          |       -       |
          +----->|S|------------>
                  -
   Write a class Par which preforms a recursive descent parse on a line
   of text, verifying whether the line satisfies the syntax of the above
   diagrams.  The class Par should use the class developed in question 1,
   on the assumption your answer to question 1 is correct.  For the sample
   code below, the instance of Par should either write "correct" or an error
   message, depending on whether the text entered is correct.  IT IS CRUCIAL
   THAT YOU USE A RECURSIVE DESCENT PARSE.

     Par p(cin);
     p.parse();

class Par{
  public:
    Par(istream &in);
    void parse();
  private:
    Toke *t;
    void S();
    void T();
    void check(bool ok, char *mess);
};

Par::Par(istream &in){
 t=new Toke(in);
 check(t!=NULL, "Heap overflow");
}

void Par::S(){
  if(t->sym()==Toke::LPAR){
    t->next();
    T();
    check(t->sym()==Toke::RPAR," ')' expected");
    t->next();
    T();
  }
  else
    check(false," '(' expected");
}

void Par::T(){
  switch(t->sym()){
    case Toke::LPAR:  S(); break;
    case Toke::RPAR :
    case Toke::EOLN : break;
    default: check(false, " ')' or eoln expected");
  }
}

void Par::parse(){
  S();
  cout<<"Accepted\n";
}

void Par::check(bool ok, char *mess){
  if(!ok){
    cout<<"ERROR: "<<mess<<endl;
    exit(1);
  }
}

   3.  Below I have written a parse table for the grammar in question 2.
   Fill in the table below the parse table to show each step of the
   parse which uses the parse table to parse the line of text '{{}{}}'.  You
   may use the symbols S, T, {, and } in the stack and in the 'Token' column,
   although the stack would actually store ints.

              LPAR   RPAR    EOLN     JUNK
                {      }       \n
                0      1        2        3
         -------------------------------------
        S  4 | {T}T   error   error     error
        T  5 |  S     lambda  lambda    error

     Token       Symbol Stack         Action
               (top on the left)      (action taken to produce next line)
     ---------------------------------------------------------------------
      {            S                   pop, push
     ---------------------------------------------------------------------
      {         {T}T                   match, next
     ---------------------------------------------------------------------
      {          T}T                   pop, push
     ---------------------------------------------------------------------
      {          S}T                   pop, push
     ---------------------------------------------------------------------
      {        {T}T}T                  match, next
     ---------------------------------------------------------------------
      }         T}T}T                  pop
     ---------------------------------------------------------------------
      }          }T}T                  match, next
     ---------------------------------------------------------------------
      {           T}T                  pop, push
     ---------------------------------------------------------------------
      {           S}T                  pop, push
     ---------------------------------------------------------------------
      {         {T}T}T                 match, next
     ---------------------------------------------------------------------
      }          T}T}T                 pop
     ---------------------------------------------------------------------
      }           }T}T                 match, next
     ---------------------------------------------------------------------
      }            T}T                 pop
     ---------------------------------------------------------------------
      }             }T                 match, next
     ---------------------------------------------------------------------
     EOLN           T                  pop
     ---------------------------------------------------------------------
     EOLN                              accept
     ---------------------------------------------------------------------


   4.  Suppose we added the symbol ">>" to the syntax of bool expression in
   the Simple Language.  In particular, <exp1> >> <exp2> would be true if the
   absolute value of <exp1> is >= the absolute value of <exp2).  Also suppose
   that the virtual stack starts at FF and "goes down" in memory.
   Finally, suppose that the values of <exp1> and <exp2> are stored on the
   stack, <exp1> at StkPtr+2 and <exp2> at StkPtr+1. Write the sasm code which
   should be generated for the expression
       IF <exp1> >> <exp2> GOTO ONE
   where the code for the evaluation of <exp1> and <exp2>) has already been
   generated. To simplify matters, you may use decimal numbers to indicate
   addresses.  For example, one might write
       load  240
       add
       store 38
   Hint:  |a|>=|b| if and only if a*a >= b*b.
   Assume StkPtr=247, ONE=44, PC=31

     load 249
     load 249
     mult
     load 248
     load 248
     mult
     sub
     branchge 44