COSC5315                Program-3		Due: 3/24/2005
	       Interpreter construction for a
	        String manipulation language
  ***********************************************************
  The Source program was last modified/corrected on 2/21/2003.
  ***********************************************************
  Consider the following string manipulating language L4
  that has the following basic instructions:

  ***NOTE***
  Due to HTML syntax conflicts, '<' is placed by '%'.

	1. V <- aV
	2. V <- V-
	3. if V ends Si goto L
	4. if V <> 0 goto L
	5. V <- 0
	6. goto L
	7. V <- V'

  Task: Write an interpreter in any language of your choice
        that will do the following:

	1. take a source program in the above language L4 and a pair of
	   two strings.
	2. interpret the source input program by executing it in finding
	   out the COUNT of occurrences of the first string in
	   the second, and
	3. output 
		a. the input program, and
		b. for each input pair of two strings,
	     	   input strings, and the COUNT.

  Additional requirements:
  1. Use the following source program as the input to your program:
	Z1 %- X1		// object string
	Z2 %- X2		// subject string
  D:	Z3 %- Z1		// object string, nonempty
	Z4 %- Z2		// subject
	Z2 %- Z2 -		// for the next cycle
  F:	If Z4 %> 0 goto G 	// subject not empty yet
	Goto E			// subject string empty and so done
  G:        If Z3 ends a goto A	// start of a cycle for comparing ends of  and ends of Z3
	If Z3 ends b goto B
	If Z3 ends c goto C
	//	else Z3 ends with d
	if Z4 ends d  goto I	//both ends match
	//	else failure so start next cycle
	Goto D
  A:	if Z4 ends a  goto I	// both ends match
	Goto D
  B:	if Z4 ends b goto I
	Goto D
  C:	if Z4 ends c goto I
	Goto D
  I:	//	both ends (Z3 and Z4) match and both non-empty.
	Z3 %- Z3-
	Z4 %- Z4-
	If Z3 %> 0  goto F	
	// Else goto YY	// Y++
///////////////////////////////////////////////
// Increment Y stringwise
  YY:	If Y %> 0 goto L
	Y %-  a Y
	Goto D		// to start next cycle
  L:	//	 Y is not zero
	Y2 %- Y		// to contain (prefix of Y except trailing  d's)+1
	Y3 %- Y		// A copy of Y to be used later
  //  drop all trailing d's from Y2 before incrementing it 
 MM:	If Y2 ends d goto M
	Goto MMM	// trailing d's are all gone from Y2
  M:	Y2 %- Y2 -
	Goto MM
  // now want Y2++ knowing that it does not end with a 'd'
 MMM:	Y4 %- Y2
	Y4 %- Y4 -
	If Y2 ends a goto LA
	If Y2 ends b goto LB
	If Y2 ends c goto LC
	//	Else Y2 empty: which is possible
	Y2 %-  a Y2	// Y2 done
	Goto LG
  LA:	Y2 %- 0
	Y2 %- b Y2
  LAB:	if Y4 %> 0  goto LAA
	//		Else Y2 done
	Goto LG
  LAA:	if Y4 ends a goto NA
	If Y4 ends b goto NB
	If Y4 ends c goto NC
	If Y4 ends d goto ND
  NA:	Y4 %- Y4-
	Y2 %- a Y2
	Goto LAB
  NB:	Y4 %- Y4-
	Y2 %- b Y2
	Goto LAB
  NC:	Y4 %- Y4-
	Y2 %- c Y2
	Goto LAB
  ND:	Y4 %- Y4-
	Y2 %- d Y2
	Goto LAB
  LB:	Y2 %- 0
	Y2 %- c Y2
	Goto LAB
  LC:	Y2 %- 0
	Y2 %- d Y2
	Goto LAB
///////////////////////////////////////////////////////////////////////
// Initialize Y by setting its trailing positions to a's using Y3
  LG:	Y %- 0
  LK:	If Y3 %> 0 goto LD	// not done
	Goto LE			// Initialization done as Y3 is empty
  LD:	If Y3 ends d goto LF
	Goto LE			// Initialization done
  LF:	Y3 %- Y3 -
	Y %- a Y
	Goto LK
//////////////////////////////////////////////////////////////////////////
// Copy Y2 to front of Y
  LE:	If Y2 %> 0 goto LH
	//	Else Y2 empty and Y is done
	Goto D
  LH:	If Y2 ends a goto LHA
	If Y2 ends b goto LHB
	If Y2 ends c goto LHC
	// Else it ends with d
	Y2 %- Y2 -
	Y  %- d Y
	Goto LE
  LHA:	Y2 %- Y2 -
	Y %- a Y
	Goto LE
  LHB:	Y2 %- Y2 -
	Y %- b Y
	Goto LE
  LHC:	Y2 %- Y2 –
	Y %- c Y
	Goto LE

  2. Use the following three input string pairs:	
		First pair:     aa,  	aaaacaaacaa  
		Second pair:   aba, 	ababababcdaba
 		Third pair:   aabb,  	bcaabbaabbaa

     Note the first pair's COUNT is ab (which is 6)