Question 1: =========== Consider the following class dictionary, object graph, sentence and the first sets. Find the UNKNOWNS. SchemeProgram = List(Exp). Exp : VarExp | LitExp | AppExp | ProcExp | AssignExp | IfExp . VarExp = Variable. Variable = DemIdent. LitExp = DemNumber. AppExp = "(" Exp List(Exp) ")". ProcExp = "(lambda" PList(Variable) List(Exp) ")". AssignExp = "(set!" VarExp Exp ")". IfExp = "(if" Exp Exp [ Exp] ")". // parameterized classes Stack(S) ~ "stack" {S} "end". List(S) ~ {S}. PList(S) ~ "(" {S} ")". Dummy = Stack(PList(Variable)). The object graph in textual representation. : SchemeProgram ( < exps > : Exp_List { : AppExp ( < rator > : ProcExp ( < formal > : Variable_PList { : Variable ( < id > : DemIdent "a" ) } < body > : Exp_List { : AppExp ( < rator > : ProcExp ( < formal > : Variable_PList { : Variable ( < id > : DemIdent "f" ) , : Variable ( < id > : DemIdent "a" ) } < body > : Exp_List { : AppExp ( < rator > : VarExp ( < var > : Variable ( < id > : DemIdent "f" ) ) < rand > : Exp_List { : VarExp ( < var > : Variable ( < id > : DemIdent "a" ) ) } ) } ) < rand > : Exp_List { : ProcExp ( < formal > : Variable_PList { : Variable ( < id > : DemIdent "b" ) } < body > : Exp_List { : AppExp ( < rator > : VarExp ( < var > : Variable ( < id > : DemIdent "plus" ) ) < rand > : Exp_List { : VarExp ( < var > : Variable ( < id > : DemIdent "b" ) ) , : LitExp ( < val > : DemNumber "3" ) } ) } ) , : LitExp ( < val > : DemNumber "100" ) } ) } ) < rand > : Exp_List { : LitExp ( < val > : DemNumber "10" ) } ) } ) The corresponding sentence: ((lambda (a) ((lambda (f a) (f a)) (lambda (b) (plus b 3)) 100)) 10) // First-sets and Follow-sets. SchemeProgram : firstset = { *epsilon* "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent } followset = { *eof* } Exp : firstset = { "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent } followset = { ")" "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent *eof* } VarExp : firstset = { *classterminal* DemIdent } followset = { "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent ")" *eof* } Variable : firstset = { *classterminal* DemIdent } followset = { ")" *classterminal* DemIdent "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *eof* } LitExp : firstset = { *classterminal* DemNumber } followset = { ")" "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent *eof* } AppExp : firstset = { "(" } followset = { ")" "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent *eof* } ProcExp : firstset = { "(lambda" } followset = { ")" "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent *eof* } AssignExp : firstset = { "(set!" } followset = { ")" "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent *eof* } IfExp : firstset = { "(if" } followset = { ")" "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent *eof* } Dummy : firstset = { "stack" } followset = { } Exp_List : firstset = { *epsilon* "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent } followset = { ")" *eof* } Variable_PList : firstset = { "(" } followset = { ")" "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent "end" } Variable_PList_Stack : firstset = { "stack" } followset = { } DemIdent : firstset = { *classterminal* DemIdent } followset = { ")" *classterminal* DemIdent "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *eof* } DemNumber : firstset = { *classterminal* DemNumber } followset = { ")" "(if" "(set!" "(lambda" "(" *classterminal* DemNumber *classterminal* DemIdent *eof* } Question 2: Consider the class dictionary from question 1, the following propagation patterns, propagation graphs and the C++ code. Find the UNKNOWNS. *operation* void driver() *traverse* *from* SchemeProgram *to-stop* Exp *wrapper* Exp (@ cout << "Expression = " << this << endl << "Free Variables: " << this -> findFreeVars() << endl; @) *operation* Variable_PList* findFreeVars() *wrapper* Exp *prefix* (@ return_val = this -> findFreeVars(new Variable_PList_Stack()); @) *operation* Variable_PList* findFreeVars (Variable_PList_Stack* boundVars) *init* (@ new Variable_PList(); @) *traverse* // For a given Exp-object find all Variable-objects it contains. // The formal parameters of a procedure can never be free; // Therefore, they need not be visited. *from* Exp *bypassing* -> *,formal,* *to* Variable *wrapper* ProcExp *prefix* // push (@ boundVars -> insert(formal); @) *suffix* // pop (@ boundVars -> get(); @) *wrapper* Variable *prefix* (@ if (!boundVars->contains(this)) return_val -> append(this); @) *operation* int contains(Variable* v) *init* (@ 0 @) *traverse* *from* Variable_PList_Stack *to* Variable *wrapper* Variable *prefix* (@ if (this -> g_equal(v)) return_val = 1; @) =========== Propagation graphs: Traversal directive: *from* { SchemeProgram } *to-stop* { Exp } Propagation graph for traversal: *source* { SchemeProgram } *target* { Exp } *paths* SchemeProgram = < exps > Exp_List . Exp : . Exp_List ~ { Exp } . Traversal directive: *from* Exp *bypassing* -> *,formal,* *to* Variable Propagation graph for traversal: *source* { Exp } *target* { Variable } *paths* Exp : VarExp | AppExp | ProcExp | AssignExp | IfExp . VarExp = < var > Variable . Variable = . AppExp = < rator > Exp < rand > Exp_List . ProcExp = < body > Exp_List . AssignExp = < lvalue > VarExp < rvalue > Exp . IfExp = < testExp > Exp < trueExp > Exp [ < falseExp > Exp ] . Exp_List ~ { Exp } . Traversal directive: *from* { Variable_PList_Stack } *to* { Variable } Propagation graph for traversal: *source* { Variable_PList_Stack } *target* { Variable } *paths* Variable = . Variable_PList ~ { Variable } . Variable_PList_Stack ~ { Variable_PList } . The C++ program: void SchemeProgram::driver( ) { // outgoing calls this->get_exps()->driver( ); } void Exp::driver( ) { // prefix class wrappers cout << "Expression = " << this << endl << "Free Variables: " << this -> findFreeVars() << endl; } void Exp_List::driver( ) { // outgoing calls Exp_list_iterator next_Exp(*this); Exp* each_Exp; while ( each_Exp = next_Exp() ) { each_Exp->driver( ); } } Variable_PList* Exp::findFreeVars( ) { Variable_PList* return_val; this->findFreeVars_( return_val ); return return_val; } void Exp::findFreeVars_( Variable_PList* & return_val ) { // prefix class wrappers return_val = this -> findFreeVars(new Variable_PList_Stack()); } Variable_PList* Exp::findFreeVars( Variable_PList_Stack* boundVars ) { Variable_PList* return_val = new Variable_PList(); ; this->findFreeVars_( return_val, boundVars ); return return_val; } void Exp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { } void VarExp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // outgoing calls this->get_var()->findFreeVars_( return_val, boundVars ); } void Variable::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // prefix class wrappers if (!boundVars->contains(this)) return_val -> append(this); } void AppExp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // outgoing calls this->get_rator()->findFreeVars_( return_val, boundVars ); this->get_rand()->findFreeVars_( return_val, boundVars ); } void ProcExp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // prefix class wrappers boundVars -> insert(formal); // outgoing calls this->get_body()->findFreeVars_( return_val, boundVars ); // suffix class wrappers boundVars -> get(); } void AssignExp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // outgoing calls this->get_lvalue()->findFreeVars_( return_val, boundVars ); this->get_rvalue()->findFreeVars_( return_val, boundVars ); } void IfExp::findFreeVars_( Variable_PList* & return_val, Variable_PList_Stack* boundVars ) { // outgoing calls this->get_testExp()->findFreeVars_( return_val, boundVars ); this->get_trueExp()->findFreeVars_( return_val, boundVars ); if ( this->get_falseExp() != NULL ) { this->get_falseExp()->findFreeVars_( return_val, boundVars ); } } etc. etc. etc. etc. etc. Question 3: ========== Write a program for printing all IfExp-objects contained in a SchemeProgram-object. *operation* void print_if_statements() *traverse* *from* UNKNOWN *wrapper* UNKNOWN Write a program which prints for a SchemeProgram-object all Variable-objects which appear in the formal part of some ProcExp-object. *operation* void print_formal_variables() *traverse* *from* UNKNOWN *wrapper* UNKNOWN Write a program which prints for a SchemeProgram-object all AssignExp-objects contained in some ProcExp-object. *operation* void print_assignments_in_procedure() *traverse* *from* SchemeProgram *to* ProcExp *wrapper* ProcExp *prefix* (@ this -> print_assignments_in_procedure2() ; @) *operation* void print_assignments_in_procedure2() *traverse* *from* ProcExp *to* AssignExp *wrapper* AssignExp *prefix* (@ cout << this ; @) Write a program which eliminates the else part (called falseExp-part) from all IfExp-objects contained in a SchemeProgram-object. *operation* void eliminate_else_part() *traverse* *from* UNKNOWN *wrapper* UNKNOWN sulution *operation* void print_formal_variables() *traverse* *from* SchemeProgram *via* ProcExp *through* -> *,formal,* *to* Variable *wrapper* Variable *prefix* (@ cout << this ; @) *operation* void print_assignments_in_procedure() *traverse* *from* SchemeProgram *to* ProcExp *wrapper* ProcExp *prefix* (@ this -> print_assignments_in_procedure2(); @) *operation* void print_assignments_in_procedure2() *traverse* *from* ProcExp *to* AssignExp *wrapper* AssignExp *prefix* (@ cout << this ; @) *operation* void eliminate_else_part() *traverse* *from* SchemeProgram *to* IfExp *wrapper* IfExp *prefix* (@ this -> set_falseExp(NULL); @)