CSE 109 Test 1  Monday  17 November 2004
>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
1.  Assume the lexical analyzer from assignments p5-p8.  Assume a language
whose programs consist of zero or more lines of code, followed by a line
with "END", where each line has one of the forms:
    READ <identifier>
    WRITE <identifier>
    <identifier>++
    <identifier>--
Write a program that parses (determines syntactical correctness of) programs
entered at the console (keyboard).  The program should simply respond by
stating whether the program is correct.  Hint: Identifiers cannot be
declared, so only one pass is needed.
=========================================================================
class Parser
{public:
   Parser():lex(){}
   void parse();
 private:
   Lex lex;
   static void check(bool b, char * mess);
};

void main()
{Parser p;
 p.parse();
}

void Parser::parse()
{int tok,savetok;
 tok=lex.next();
 while(tok!=Lex::END)
  {switch(tok)
    {case Lex::WRITE:
     case Lex::READ: tok=lex.next();
                     check(tok==Lex::IDENT,"Identifier expected");
                     break;
     case Lex::IDENT: savetok=lex.next();
                      check(savetok==Lex::SPLUS || savetok==Lex::SMINUS,
                               " '+' or '-' expected");
                      tok=lex.next();
                      check(tok==savetok," '++' or '--' expected");
                      break;
    default: check(false," WRITE, READ, or Identifier expected");
   }
   tok=lex.next();
   check(tok=Lex::ENDOFLINE,"Junk at end of line");
   lex.newLine();
   tok=lex.next();
  }
 cout<<"\nThe parse succeeded\n";

}

void Parser::check(bool b, char *mess)
{if(!b)
  {cerr<<"ERROR: "<<mess<<endl;
   exit(1);
  }
}


2.  Assume a language whose symbols are 0, 1, <, <=, >, >=, ==, and !=.
Write a class Lex for this language.  Lex should read input from the console
(keyboard) and write no output. Instances of Lex should skip over blanks,
tabs, and linefeeds.  Given Lex lx;, calls to lx.next() should return 0 for 0,
1 for 1, 2 for <, 3 for <=, 4 for >, 5 for >=, 6 for ==, 7 for != and 8 for
anything else.
=========================================================================
#include <fstream.h>
class Lex
{public:
    static const int ZERO=0, ONE=1, LT=2, LTE=3, GT=4, GTE=5, EQ=6,
      NE=7, JUNK=8;
  Lex(){cin.get(ch);}
  int next();
private:
    char ch;
    void getch();
    int oneChar(int one);
    int twoChar(int one,int two);
};

void Lex::getch()
{while(cin.good() && (ch==' ' || ch=='\t' || ch=='\n'))
      cin.get(ch);
}

int Lex::oneChar(int op)
{cin.get(ch);
 return op;
}

int Lex::twoChar(int one,int two)
{cin.get(ch);
  if(ch!='=')
  return one;
 cin.get(ch);
 return two;
}

int Lex::next()
{getch();
  switch(ch)
  {case '0': return oneChar(ZERO);
  case '1':  return oneChar(ONE);
  case '<': return twoChar(LT,LTE);
  case '>': return twoChar(GT,GTE);
  case '=': return twoChar(JUNK,EQ);
  case '!': return twoChar(JUNK,NE);
  default: cin.get(ch); return JUNK;
  }
}

//<<<<<<<<<<<<NOT PART OF ANSWER, BUT IT CHECKS TO MAKE
//<<<<<<<<<<<<SURE THE CLASS WORKS
int main()
{Lex lex;
 char *tab[]={"ZERO", "ONE", "LT","LTE","GT", "GTE", "EQ", "NE", "JUNK"};
 int tok;
for(int j=0; j<10; j++)
  {tok=lex.next();
  cout<<"Your entered '"<<tab[tok]<<endl;
  }
}

3. Write a program that determines whether a line of text entered at the
console (keyboard) satisfies the syntax specified by the diagram S in the
following syntax diagrams, where parentheses stand for a circle or oval and
square brackets ([]) stand for boxes.  It should display nothing other than
the syntactical error, if there is one, or a message that the syntax is
acceptable.  Note that blanks (' ') and tabs ('\t') are not acceptable
characters.  Hint: No lexical analyzer is needed, because all symbols are
single characters.

   S
   ----->[A]-------------------------------------------->
            ^             |         ^               |
            |             |         |               |
            +-[A]<--(+)<--+         +--[A]<--(-)<---+

   A
   -------------->(0)-----------+
          |                     |
          +------>(1)---------->|
          |                     v
          +-->(*)-->[S]--(/)---------->
===========================================================
#include <fstream.h>
void S(char &ch);
void A(char &ch);
void check(bool b, char *mess);

int main()
{char ch;
 cin.get(ch);
 S(ch);
 check(ch=='\n',"End of line expected\n");
 cout<<"The syntax is okay\n";
}

void S(char &ch)
{A(ch);
 while(ch=='+')
  {cin.get(ch);
   A(ch);
  }
 while(ch=='-')
  {cin.get(ch);
   A(ch);
  }
}

void A(char &ch)
{switch(ch)
  {case '*': cin.get(ch);
             S(ch);
             check(ch=='/', " '/' expected");
   case '0':
   case '1': cin.get(ch); break;
   default: check(false," *, 0, or 1 expected");
  }
}

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


4. Write bigmach code that corresponds to the following MCASM program
Hint: Recall the codes Halt (0,0), Read (0,1), Write (0,2), Store (1),
Load (2), Increment (3), Decrement (4), Multiply (5), Divide (6),
Jump (7,0), Jump less (7,1), Jump greater (7,2), Jump equal (7,3).

     JMP PROG
     X  10
PROG READ REG0
     JMPLE TWO
     WRITE X
     HALT
TWO  WRITE Y
     HALT
Y    1024
END
=====================================================================
7 0 6     [4]
0 0 10   X  [5]
0 1 0     PROG read REG0  [6]
7 3 9    skip over goto if gt    [7]
7 0 11    goto TWO    [8]
0 2 5  write X    [9]
0 0 0    halt   [10]
0 2 13  two  write Y  [11]
0 0 0   halt   [12]
0 1 0   Y      [13]
E