CSE 109  Test 2 Wednesday 14 April 2004
>>>>>>>>>>>SUGGESTED ANSWERS
1.  Write a Simple Language Program that reads in an integer and
writes out the largest square less than or equal to the absolute
value of the number. For example, if the number is 29 then the program
would write out 25; if the number is -16 then the program would write
out 16.
=======================================================
        READ N
        IF N>0 GOTO POSITIVE
        N=0-N
   POSITIVE:
        SQUARE=1
   LOOP:
        IF SQUARE*SQUARE>N GOTO FINISH
        SQUARE=SQUARE+1
        GOTO LOOP
   FINISH:
        WRITE (SQUARE-1)*(SQUARE-1)
   HALT
end

2.  Write Simple Machine code that corresponds to the following Simple
Language Program. (Recall Simple Machine operators: halt(0), read(1),
write(2), load(3), store(4), add(5), sub(6), mul(7), div(8), branchle(9),
branchge(A), branch(B)).

    READ X
    IF X<=2 GOTO ONE
    WRITE 5
  ONE:
    HALT
  end
===========================================
    100
    40B
    30B
    309
    600
    908
    30A
    200
    0
    2
    5

3.  Assume class Lex is a lexical analyzer that reads input from cin and
returns one of the following (distinct) int constants:  Lex::A, Lex::B,
Lex::C, Lex::ENDOFLINE, and Lex::JUNK when the instance method next() is
called.  Write the declaration and definitions (code) for the class Parse
which has a method parse(). Given the declaration Parse p;, the
call p.parse() either displays "good" if the line of text obeys the syntax
for S given by the diagrams below.  Otherwise, it displays "bad".  Note that
() denotes a circle and [] denotes a rectangle.

  S                       T                         U
  ---->(A)-->[T]--->      ---->(C)--[S]-->[A]-->    -----(B)-----------
     |           |          |                 |              |      |
     +-->[T]-----+          +-->[U]-----------+             (B)<----+
=========================================================
class Parse
{public:
  Parse();
  void parse();
 private:
  void S();
  void T();
  void U();
  static void check(bool b);
  Lex lexer;
  int tok;
};

Parse::Parse()
{}

void Parse::parse()
{tok=lexer.next();
 S();
 check(tok==Lex::ENDOFLINE);
 cout<<"good\n";
}

void Parse::S()
{if(tok==Lex::A)
  {tok=lexer.next();
   T();
  }
 else
  T();
}

void Parse::T()
{if(tok==Lex::C)
  {tok=lexer.next();
   S();
   check(tok==Lex::A);
   tok=lexer.next();
  }
 else U();
}

void Parse::U()
{check(tok==Lex::B);
 tok=lexer.next();
 while(tok==Lex;;B)
  tok=lexer.next();
}

void Parse::check(bool b)
{if(!b)
  {cerr<<"\nbad\n";
   exit(1);
  }
}


4.  Write the declaration and definitionS (code) for the class Lex in
question 3.  The method next() should ignore blanks and tabs.  It should
return A for 'A', B, for 'B', C for 'C', ENDOFLINE for '\n', and JUNK for
any other character.
===================================================================
class Lex
{public:
  Lex();
  int next();
  static const int A=0,B=1,C=2,ENDOFLINE=3,JUNK=4;
 private:
  char ch;
};

Lex::Lex(){}

int Lex::next()
{
 cin.get(ch);
 while(ch==' ' || ch=='\t')
  cin.get(ch);
 switch(ch)
 {case 'A':return A;
  case 'B':return B;
  case 'C':return C;
  case '\n':return ENDOFLINE;
  default: return JUNK;
 }
 return -1;
}