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)