CSE 321 Closed Lab 5 Warm-up Exercise

This will be a fun closed lab. You will be implementing a recursive descent evaluator for arithmetic expressions by implementing the five procedures listed below. These procedures are based on the following context-free grammar for arithmetic expressions:

<expression>     -->  <term> { + <term> | - <term> }
<term>           -->  <factor> { * <factor> | / <factor> } 
<factor>         -->  ( <expression> ) | <digit sequence>
<digit sequence> -->  <digit> { <digit> }
<digit>          -->  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Notice that there are five procedures corresponding to each of the five nonterminal symbols of this grammar. This means that a tokenizer will not be used in your solution. Instead, your procedures will, when appropriate, get input characters from the text string source_text, that is a parameter to each of the procedures. Notice also that each procedure has a character parameter c. c plays the role of a "look ahead" character when each procedure is called and plays the role of a "look ahead" character when execution of each procedure is complete. This is analogous to the "look ahead" token discussed in class. Also, there will be no white space in the text string source_text, so that your program does not need to deal with white space. (Said in other words, each character in source_text's prefix will be from the set of characters {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '(', ')', '+', '-', '*', '/'}.)

Parts of the specifications of the procedures are not done formally, although they could be. If you have questions about the meaning of the informal specifications, be sure to ask. The notation [<nonterminal symbol> DERIVES some_string_of_character] means that the string of character can be derived from the nonterminal symbol using the rewrite rules of the grammar above (as we discussed in class).

Hints:

A string p being a proper prefix of a string s means both that the length of p is strictly less than (less than but not equal to) the length of s and that p is a prefix of s.
The To_Integer (programming) function returns the ASCII value of a character parameter. For example, To_Integer ('1') returns 49.
The Is_Digit (programming) function returns true if and only if a given character is a digit. For example, Is_Digit ('3') returns true, and Is_Digit ('a') returns false.

It might be a good idea to use emacs to create the procedure bodies for these procedures before closed lab Friday. That way, you'll be able to copy and paste the bodies into the test driver. Have fun!

    /*!
	math definition DIGIT_CHAR: finite set of character is
	    {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}

	math definition IS_DIGIT_CHAR (
		c: character
	    ): boolean is
	    c is in DIGIT_CHAR

	math definition IS_LONGEST_DERIVABLE_PROPER_PREFIX_OF (
		nts: NON_TERMINAL_SYMBOL
		p:   string of character
		s:   string of character
	    ): boolean is
	    p is proper prefix of s and
	    [nts DERIVES p] and
	    for all x: string of character
		    where (0 < |x| and p * x is proper prefix of s)
		(not [nts DERIVES p * x])
    !*/

    global_procedure Evaluate_Expression (
	    alters   Text& source_text,
	    alters   Character& c,
	    produces Integer& value
	);
    /*!
	requires
	    there exists x: string of character
		(x is proper prefix of source_text and
		 [<expression> DERIVES <c> * x])
	ensures
	    there exists x: string of character 
		(#source_text = x * <c> * source_text and
		 IS_LONGEST_DERIVABLE_PROPER_PREFIX_OF
		     (<expression>, <#c> * x, <#c> * #source_text) and
		 value = [value of the expression represented by <#c> * x])
    !*/

    global_procedure Evaluate_Term (
	    alters   Text& source_text,
	    alters   Character& c,
	    produces Integer& value
	);
    /*!
	requires
	    there exists x: string of character
		(x is proper prefix of source_text and
		 [<term> DERIVES <c> * x])
	ensures
	    there exists x: string of character 
		(#source_text = x * <c> * source_text and
		 IS_LONGEST_DERIVABLE_PROPER_PREFIX_OF
		     (<term>, <#c> * x, <#c> * #source_text) and
		 value = [value of the term represented by <#c> * x])
    !*/

    global_procedure Evaluate_Factor (
	    alters   Text& source_text,
	    alters   Character& c,
	    produces Integer& value
	);
    /*!
	requires
	    there exists x: string of character
		(x is proper prefix of source_text and
		 [<factor> DERIVES <c> * x])
	ensures
	    there exists x: string of character
		(#source_text = x * <c> * source_text and
		 IS_LONGEST_DERIVABLE_PROPER_PREFIX_OF
		     (<factor>, <#c> * x, <#c> * #source_text) and
		 value = [value of the factor represented by <#c> * x])
    !*/

    global_procedure Evaluate_Digit_Sequence (
	    alters   Text& source_text,
	    alters   Character& c,
	    produces Integer& value
	);
    /*!
	requires
	    IS_DIGIT_CHAR (c) and
	    there exists nd: character
		(not IS_DIGIT_CHAR (nd) and
		 <nd> is substring of source_text)
	ensures
	    there exists x: string of DIGIT_CHAR 
		(#source_text = x * <c> * source_text and
		 not IS_DIGIT_CHAR (c) and
		 value = TO_INTEGER (<#c> * x))
    !*/

    global_procedure Evaluate_Digit (
	    alters   Text& source_text,
	    alters   Character& c,
	    produces Integer& value
	);
    /*!
	requires
	    IS_DIGIT_CHAR (c) and
	    source_text /= empty_string
	ensures
	    value = TO_INTEGER (#c) - TO_INTEGER ('0') and
	    #source_text = <c> * source_text
    !*/