CS 270 Programming Assignment PA8: Recursion

due Sunday, April 12th at 10:00pm, no late submissions.

Goals

For this assignment you will write programs in C and LC-3 assembly code. Both programs will perform the identical recursive algorithm. The goals of this programming assignment are:
  1. To solidify your understanding of the stack memory model.
  2. To understand how recursion is implemented in C and at the assembly level.
  3. To extend your assembly coding skills.

The Assignment

STEP ONE: C Program

Write a C program called pa8.c that reads a line of input from the user, without any prompt, and prints the reversed version of the line, with any and all of “aeiou” translated to “*”, followed by a newline. You may assume that the line will be no longer than eighty characters. Use the recursive algorithm as specified later in this document. The C program will consist of main() and the two functions described below. Do not use any global variables.

Required Functions

void reverse(char *s);
If the string s is non-empty, make a recursive call to reverse to print all the characters except the first one, and then print the first character, translated via the translate function. You may only use putchar to emit characters.

char translate(char c);
This function converts any of the five characters “aeiou” to a ‘*’. Any other character is returned unchanged. It doesn't print anything.

STEP TWO: LC-3 Program

Copy pa8.asm to your directory. It’s a starting point. Complete it.

Your LC-3 functions must follow exactly the stack protocol shown below, which is the one used by the LC-3 C compiler:

  1. The caller pushes parameters onto the stack.
  2. The callee makes room for the return value, if one exists.
  3. The callee pushes the return address of the caller from R7.
  4. The callee pushes the frame pointer of the caller from R5.
  5. The callee sets up its own frame pointer.
  6. The callee executes its function code.
  7. The callee stores the return value, if one exists, onto the stack.
  8. The callee pops the frame pointer of the caller to R5.
  9. The callee pops the return address of the caller to R7.
  10. The callee returns using the RET command.
  11. The caller pops the return value, if one exists, off the stack.
  12. The caller cleans up the stack to remove the parameters it pushed.
This stack protocol is shown in the code provided in pa8.asm. We recommend that you completely understand the provided code before you make changes. During lab hours we will be glad to explain the provided code, but we will not show you how to modify the code for the assignment.

Submission Instructions

Submit pa8.asm to the Checkin tab for preliminary testing.

Grading Criteria

We will test the assembly program with four strings (60 points). We will also run a test that verifies that the stack pointer is correctly restored (15 points).

Final testing will do the same thing as preliminary testing, but will use different values. The remaining score will come from examining the assembly program to make sure that reverse is implemented recursively, that proper stack protocol is used, and that the assembly code is properly commented, indented, etc. (25 points). Claiming “but it works!” will not get you anywhere.