CSE 109 Final Examination  Friday   5 May 2006
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<SUGGESTED ANSWERS>>>>>>>>>>>>>>>>>>>>>>>>
1.  Questions 1 and 2 deal with different parts of the same problem.
Read both questions before starting.  Expressions like *&*a.b()->c.gg().e.f
are syntactically correct in C++ and satisfy the following syntax diagrams
for A, where  () denotes ovals and []
denotes boxes.                        X
  A     +-('&')--[A]--+               --[Y]----+------------------>
  ------|-('*')--[A]--|--->                 ^  |   +--('->')--+
        +--[X]--------+                     |  +-->|          |--[Y]-+
     Y              +-----------------+     |      +--('.')---+      |
     ----(Ident)----|                 |-->  +-<----------------<-----+
                    +--('(')--(')')---+

 (where, although not relevant to this question, Ident is a sequence of one
  or more lower case letters).
Write a class CParse that gets tokens from a lexical analyzer of type Flex
(see question 2) that returns one of the Flex constants AMPERSAND(0),
SPLAT(1), IDENT(2), PERIOD(3), ARROW(4), LPAR(5), RPAR(6), EOLN(7), and
JUNK(8).  The method parse() should determine whether a sequence of
tokens from one line of a file satisfies the above syntax. If the line
does, then parse() does nothing; if it does not, parse() diagnoses the
first error.  The following (sloppy) code shows how CParse would be used.
int main()
{ifstream f("cparse.dat");
 CParse p(f);
 p.parse();
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#ifndef CPARSE_H
#define CPARSE_H

class CParse
{public:
  CParse(istream &in=cin);
  void parse();
private:
  void A();
  void X();
  void Y();
  int tok;
  Flex f;
  static void check(bool b,char*mess);
};

CParse::CParse(istream &in):f(in)
{}

void CParse::parse()
{tok=f.next();
 A();
 check(tok==Flex::EOLN,"<--End of line expected\n");
}

void CParse::A()
{switch(tok)
  {case Flex::AMPERSAND:
  case Flex::SPLAT:
    tok=f.next();
    A();
    break;
  default: X();
  }
}

void CParse::X()
{Y();
 while(tok==Flex::PERIOD || tok==Flex::ARROW)
   {tok=f.next();
   Y();
   }
}

void CParse::Y()
{check(tok==Flex::IDENT," Ident, '*', or '&' expected");
 tok=f.next();
 if(tok==Flex::LPAR)
   {tok=f.next();
   check(tok==Flex::RPAR," ')' expected");
   tok=f.next();
   }
}

void CParse::check(bool b, char *mess)
{if(!b)
  {cout<<"<-- ERROR: "<<mess<<endl;
  exit(1);
  }
}
#endif
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2.  Write a class Flex that acts as a lexical analyzer for CParse above.
Class Flex can assume that the header for the class Scan we developed for p3
is stored in scan.h. Calls to the Flex method next() should echo to the
console each character it gets from Scan. Note that an Ident is a sequence
of one or more lowercase letters. Also, recall that scan has the following
methods: Scan(istream &in=cin);  char next();  void newLine();  void reset();
  bool good()const;
A (sloppy) program that uses Flex might look like:
int main()
{int sym;
 ifstream f("flex.dat");
 Flex flex(f);
 sym=flex.next();
 while(sym!=Flex::EOLN)
 {cout<<sym<<" ";
  sym=flex.next();
 }
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#ifndef FLEX_H
#define FLEX_H
#include "scan.h"
class Flex
{public:
  static const int AMPERSAND=0, SPLAT=1, IDENT=2, PERIOD=3,
    ARROW=4, LPAR=5, RPAR=6, EOLN=7, JUNK=8;
  Flex(istream &in=cin);
  int next();
private:
  Scan sc;
  char ch;
};

Flex::Flex(istream &in):sc(in){ch=' ';}

int Flex::next()
{int temp;
 while(ch==' ')
  {cout<<ch;
   ch=sc.next();
   }                  //get rid of white space
 if(ch>='a' && ch<='z')
   {while(ch>='a'&&ch<='z')
     {cout<<ch;
       ch=sc.next();
     }
   return IDENT;
   }
 cout<<ch;
  switch(ch)
    {case '&': temp=AMPERSAND; break;
    case '*': temp=SPLAT; break;
    case '\n': return EOLN;
    case '.': temp=PERIOD; break;
    case '(': temp=LPAR; break;
    case ')': temp=RPAR; break;
    case '-':
      ch=sc.next();
      cout<<ch;
      if(ch!='>')
         return JUNK;
      temp=ARROW;
      break;
    default: temp=JUNK;
    }
  ch=sc.next();
  return temp;
}
#endif
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
3.  Write a C program (compiled with "gcc -xc") that writes out a message
to the console stating whether two strings entered on the command line name
the same file or name two files with duplicate contents or name two files
with different contents.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <stdio.h>

void check(int b,char *messa,char *messb,char *messc);
int dup(char*a,char*b);

int main(int ct,char**arg)
{check(ct==3,"Usage: ",arg[0]," <inputFile1. <inputFile2>");
 if(strcmp(arg[1],arg[2])==0)
   printf("Same file\n");
 else
   if(dup(arg[1],arg[2]))
     printf("Duplicate files\n");
   else
     printf("Neither the same file nor duplicate files\n");
}

void check(int b,char *messa,char *messb,char *messc)
{if(!b)
  {fprintf(stderr,"%s%s%s\n",messa,messb,messc);
  exit(1);
  }
}

int dup(char*a,char*b)
{FILE *fa,*fb;
 char ach,bch;
 fa=fopen(a,"r");
 check(fa!=NULL," Failure to open '",a,"'");
 fb=fopen(b,"r");
 check(fb!=NULL," Failure to open '",b,"'");
 ach=getc(fa);
 bch=getc(fb);
 while(!feof(fa) && !feof(fb) && ach==bch)
   {ach=getc(fa);
   bch=getc(fb);
   }
 return feof(fa) && feof(fb);
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4.  Before answering this question read question 5, a related question. Write
the declaration and definition (code) for the class LUAcc which is meant to
store information for LTS user accounts: the first name, the last name, and the
user identifier.  It should have sufficient functionality so that the code
below produces the indicated output.  Your class need only store the first
15 characters of a name, discarding the rest, and can assume all user
identifiers have six or fewer characters.
 LUAcc x("Tom", "Mix", "TM203");
 cout<<x.get(LUAcc::FNAME)<<" "<<x.get(LUAcc::LNAME)
      <<" "<<x.get(LUAcc::EMAIL)<<endl;
 //OUTPUT: Tom Mix TM203
 x.set("MixedUp",LUAcc::LNAME);
 cout<<x.get(LUAcc::FNAME)<<" "<<x.get(LUAcc::LNAME)
      <<" "<<x.get(LUAcc::EMAIL)<<endl;
 //OUTPUT:  Tom MixedUp TM203
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
class LUAcc
{public:
  static const int FNAME=0, LNAME=1, EMAIL=2;
  LUAcc(char * fn, char*ln,char*em);
  void set(char *c,int var);
  const char * get(int var)const;
protected:
  char fname[16],lname[16],email[7];
  static void check(bool b, char *mess);
  static void copy(char *to, char *from, int limit);
};

LUAcc::LUAcc(char *fn,char*ln,char*em)
{copy(fname,fn,15);
 copy(lname,ln,15);
 copy(email,em,6);
}

void LUAcc::copy(char *to, char *from, int limit)
{int j;
 j=0;
 while(j<limit && from[j]!='\0')
   {to[j]=from[j];
   j++;
   }
 to[j]='\0';
}

void LUAcc::set(char *c, int var)
{check(var>=0 && var<=2,"Bad choice in set()");
 switch(var)
   {case 0: copy(fname,c,15); break;
   case 1: copy(lname,c,15); break;
   case 2: copy(email,c,6); break;
   }
}

const char * LUAcc::get(int var)const
{check(var>=0 && var<=2,"Bad choice in set()");
 switch(var)
   {case 0: return fname;
   case 1: return lname;
   case 2: return email;
   }
 return ""; //keep the compiler happy
}

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

5.  Write a subclass of LUAcc, called LUAX, which adds the ability to store
upto 10 aliases for the user ID (an improvement of LTS's policy of enabling
one alias).  The class LUAX should have sufficient functionality so that the
code below produces the indicated output.  Your class need only store the
first nine characters of an alias, discarding the rest (similar to unix on
the department machines which only uses the first eight characters of a
password).
 LUAX y("Tom", "Mix", "TM204");
 y+="Hellion";
 y+="Filly";
 cout<<y<<endl;
//OUTPUT: Mix, Tom. Userid: TM204. Aliases: Hellion, Filly
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
class LUAX:public LUAcc
{public:
  LUAX(char *fn,char*ln,char*em);
  LUAX & operator +=(char * st);
  friend ostream & operator<<(ostream &out,const LUAX & x);
private:
  int ct;
  char alias[10][11];
};

LUAX::LUAX(char *fn,char*ln,char*em):LUAcc(fn,ln,em),ct(0){}

LUAX & LUAX::operator+=(char *st)
{check(strlen(st)<=10,"Alias too long");
 check(ct<10,"Array overflow");
 copy(alias[ct],st,10);
 ct++;
}

ostream & operator<<(ostream &out,const LUAX & x)
{out<<x.get(LUAcc::LNAME)<<", "<<x.get(LUAcc::FNAME)<<". Userid: '"
    <<x.get(LUAcc::EMAIL)<<". Aliases: ";
 for(int j=0; j<x.ct;j++)
   {if(j>0)
     out<<", ";
   out<<x.alias[j];
   }
 return out;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
6.  Write the template for a class ShowRay which is intended to save the
reference to an array of some type and then display (parts of) the array
to the screen in various formats. The code below indicates how the templated
class should behave.

int y[10];
ShowRay<int> sy(y);
for(int j=0;j<10;j++)
 y[j]=j*j+6;
sy.show(3,6,'[',']','|');//show y[3]..y[6] surrounded by [] and separated by |
        //[ 15| 22| 31| 42]
sy.show(6,7,'{','}',',');
           //show y[6], y[7], surrounded by by {} and separated by ,
           //{ 42, 55}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#include <iostream>
using namespace std;
template <class X>
class ShowRay
{public:
  ShowRay(X * r);
  void show(int j, int k,char left='[', char right=']',char sep=',');
 private:
  X *ray;
};

template <class X>
ShowRay<X>::ShowRay(X *r):ray(r){}

template <class X>
void ShowRay<X>::show(int j, int k, char left, char right, char sep)
{cout<<left<<" ";
 for(int n=j; n<=k; n++)
   {if(n>j)
     cout<<sep<<" ";
   cout<<ray[n];
   }
 cout<<right;
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
7.  Write the MACH1 code that would be generated by an assembler for MCASM
programs when the assembler parses and generates code for the MCASM program
below.
    read x
    read y
    write x-x*y
    halt
    end
Hint: Recall the MACH1 code: read(0), write(1), load(2), store(3),
clear(4), add(5), sub(6), mult(7), div(8), addi(9), subi(10), multi(11),
divi(12), lte(13), gte(14), halt(15).
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
0 0     0
3 19    1   read x
0 0     2
3 20    3   read y
2 19    4
3 511   5   push x
2 19    6
3 510   7   push x
2 20    8
3 509   9   push x
2 510  10   load copy of x from stack
7 509  11   mult by stack copy of y
3 510  12   push x*y onto stack
2 511  13   load copy of x from stack
6 510  14   subtract x*y
3 511  15   store x-x*y on stack
2 511  16
1 0    17   write x-x*y
15 0
E
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
8.  Write out the output that occurs at the "dashed lines" for the C++
program below.

#include <iostream>
using namespace std;

class A
{public:
  A(int j=0):val(j){}
  virtual void x(){val++;}
  void y(){val+=2;}
  void z(){x(); y();}
  int val;
};

class B: public A
{public:
  B(int j=5){}
  void x(){val+=3;}
  void y(){val+=4;}
};

void x(int a, int *b, int **c)
{a=42;
 *b=6;
 *c=b;
 (**c)+=5;
}

int main()
{A a(5);
 a.z();
 cout<<a.val<<endl; //------------
 B d(3),e;
 d.x();
 cout<<d.val<<endl;//-------------
 e.val=5;
 e.A::x();
 cout<<e.val<<endl;//-------------
 e.val=5;
 e.z();
 cout<<e.val<<endl;//-------------
 int u=5,v,*w;
 x(u,&v,&w);
 *w+=2;
 cout<<u<<" "<<v<<" "<<*w<<endl;//---------
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
8
3
6
10
5 13 13
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>