Lab. # 9 of CS 216

More Recursion

Choice of one of four programs: Greatest Common Divisor ( gcd.a) for maximum 8/10 marks, this one is easy,
OR recursive factorial using real numbers (real4.a) OR a choice of one of 2 C programs to evaluate an arithmetic expression

Greatest Common Divisor

That means the largest number that wil divide evenly (with no remainder) both of 2 numbers. Here is this week's mips problem:
## Question:
## Write a function "gcd" that takes two
## numbers in $a0 and $a1, and returns their
## greatest common divisor. Both numbers will
## be greater than zero.
## Use Euclid's algorithm, based upon
## gcd(a, a) = a
## gcd(a, b) = gcd(b, a)
## gcd(a, b) = gcd(a-b, b) {use with a>b}

Euclid, a Greek mathematician who lived some time ago, figured out these facts, which can be used recursively, or repeatedly, to arrive at the GCD of any two numbers. He did not work with negative numbers, and probably had the use of an abacus, which makes subtraction easy

  1. gcd(a, a) = a  is obvious, a/a=1, with no remainder. No larger number will do (the remainder would be a)
  2. gcd(a, b) = gcd(b, a)   the order of the numbers doesn't matter, so we can in particular put the larger one first.
  3. gcd(a, b) = gcd(a-b, b)   Hmmmm. Lets see. If  some number x divides both a and b evenly, then (a-b)/x = a/x - b/x also has no remainder!
HOWEVER, repeated subtractions could take a very long time, for instance, the gcd (12345678,2) would involve around 6172838 subtractions of 2. Euclid probably never actually did this for such numbers. Would you be much faster with a calculator? So, might I suggest using rem instead. In that case, the first rule will need to be gcd(a, 0) = a.

Factorial -- real4.a

The factorial of an integer n, written n! is the proudct of all the numbers up to and including n, so 5! = 1*2*3*4*5.
This is defined recursively:
  1. 1! = 1
  2. n! = n *( (n-1)! (n > 1)
Since these numbers get big very fast, we will use real numbers, with floating decimal point, in fact we should use double precision (64 bit) numbers.
All real number operations are handeled by mips' floating point coprocessor, with which you will need to become familiar with in this problem, see float notes. in particular, note that double precision must use even numbers, because a double in $f2 uses the space of single $f2 and $f3. The print double service prints $f12.

The problem statement is:

##	Write a function ffact that will compute
##	the Factorial of the integer passed in $a0
##		0! = 1! = 1.0
##		n! = (n-1)! * n
##	calculate it as a real number using double precision
##	as factorials get very large very soon
##
##	return the answer in coprocessor register $f12
##

Evaluating an arithmetic expression: Do ONE of the following

I have created a C function, int gettoken(FILE *); that reads from a "file", such as stdin, and gets "tokens" that would appear in an arithmetic expression. These tokens are either (unsigned) integers, of possibly several digits, the 4 arithmetic operators (+ - * /) and parentheses. To distinguish the characters, they are returned as negative int's. Use this function in either of the following (It will be defined "above the cut line"). If it is called at the end of the input, an error exit will occur.

Both programs accept terminal input, for testing. mipsmark will run several pre-prepared tests.

If you encounter an error, write a message containing invalid and exit(0). Example:

if (op2==0) {puts("Divisionn by zero is invalid."); exit(0);}

Either evalprefix.c

Input will be a (possibly malformed) prefix expression. Write a function int preval(FILE *) to read the expression and (recursively) evaluate it. Note that you can call gettoken(somefile) to do the actual reading.

In your expression, you will need to separate adjacent numbers with some other character(s) such as a space.

Grammar:
S -> P
P -> O P P
P -> n
O -> + | - | * | /

>OR optionally evalinfix.c

Input will be a (possibly malformed) fully parenthesized infix expression. Write a function int inval(FILE *) to read the expression and (recursively) evaluate it. Note that you can call gettoken(somefile) to do the actual reading.

In your expression, you will need to add enough parentheses so that each operation has exactly 2 operands.

Grammar:    Our non-terminals could be called Expression, Term, and Operator
S -> E
E -> T O T
O -> + | - | * | /
T -> n
T -> ( E )

There are more possibilities to go wrong here. If you encounter an unexpected token, please print a message containing "invalid" or "Invalid."
My implementation uses the messages:
    Invalid expression, number or parenthesis expected
    Malformed, invalid operator

In two steps: Recognizing tokens, using a Finite State Machine (FSM) -- a Context-free Grammar for parsing expressions

As the whole parsing process would be complex based upon simply a character string, I recommend a two-step process, first recognizing valid "tokens", and then implementing evaluation based upon the "grammar" defined for the pre- or infix expressions.

Tokenizing: a "Regular Expression"

The regular expression that defines our tokens is:  [0-9][0-9]*|\+|\-|\*|\/||\(|\)

In this language, [] means a single character from a set of alternatives, * means zero or more repetitions of what preceeds it, and | gives alternate expressions. \ is an "escape", which should be used in front of all special characters, as most have meaning in regular expressions. So, in the above, \* means the actual character '*'

Thus, this RE means either a digit followed by zero or more digits (which should be converted into an integer), or one of 6 special characters we would expect in an arithmetic expression.

A FSM to recognize this pattern starts in a "start state" where it accepts input until either a digit or one of the 6 characters is found.

In state 2, a number has been started

Grammar rules

Once tokens are obtained, a good way to describe a valid syntax is with grammar rules. These are recursive (aha!) and consist of non-terminal symbols (UPPERcase) and terminal symbols (lower case, or special character). By convention, a set of grammar rules starts with S, for "Start."
Here is a simple baby grammar consisting of Nouns and Verbs. Baby can say things like "baby love mama" and "dog bite cat"

S -> N V N
N -> baby | mama | dog | cat
V -> love | eat | bite

A good way to use a grammar for programming is to create a function for each kind of non-terminal (P, E, and T in the two programming problems above).


"What we will do next week" : calctree.a where my code transforms a prefix expression into an actual tree of nodes, and you evaluate it recursively.
Prepared by Lin Jensen