CS61CL Fall 2009 Homework 5 Due 11 59 Wed 9 30 Create a directory cs61cl xx hw5 and place one file in it for each problem Prob1 txt will be an annotated version of what appears below The others prob2 s prob3 s prob4 s will be mips assembly language files that run correctly under MARS Problem 1 On the following page you will find a print out of a solution to table c of hw3 with the lines numbered In this problem we will use that example to learn a bit about testing methodology All too often in CS lab course people write all the code put it together and hope it works It never does An alternative approach is proceed systematically testing portions as you go A good test should cover each and every line of code For example the following simple program int main struct table t initTable printf empty table n printTable t stdout return 0 Tests lines 43 47 120 122 125 126 Get out your highlighter and check it 1 a Which lines are tested if we expand this to int main struct table t initTable printf empty table n printTable t stdout t addDef def 6 t printf def before use n printTable t stdout return 0 Answer 1 b The following expands this to cover the rest of function add use In the comment for each new line of code indicate the additional lines it covers and the case it checks int main struct table t initTable printf empty table n printTable t stdout t addDef def 6 t t addDef eef 7 t t addDef bef 8 t t addDef def 9 t printTable t stdout return 0 1 c The following expands this to cover all of addUse and add useNode In the comment for each new line of code indicate the additional lines it covers and the case it checks int main struct table t initTable printf empty table n printTable t stdout t addDef def 6 t t addDef eef 7 t t addDef bef 8 t t addDef def 9 t t addUse def 10 t t addUse def 11 t t addUse undef 12 t t addUse aa undef 12 t printTable t stdout t initTable t addUse undef 12 t addUse undefined completely empty printTable t stdout return 0 1 include stdlib h 2 include stdio h 3 include string h 4 include table h 5 6 7 A symbol table is an ordered linked list of table elements 8 Each element contains the name of the symbol the line number at which 9 it was defined 1 if no definition has yet been processed and the 10 sequence of line numbers in which the symbol was used 11 12 13 struct useNode 14 int pos 15 struct useNode next 16 17 18 struct useNode add useNode struct useNode head int pos 19 struct useNode t head 20 struct useNode n malloc sizeof struct useNode 21 n pos pos 22 n next NULL 23 if t NULL return n new entry is entire list 24 while t next t t next add entry to the end of the list 25 t next n 26 return head 27 28 29 struct tableElement 30 char symbolName 31 int defPos 32 struct useNode uses 33 struct tableElement next 34 35 36 struct table 37 struct tableElement head 38 39 40 41 Returns an empty table 42 43 struct table initTable 44 struct table rtn malloc sizeof struct table 45 rtn head NULL 46 return rtn 47 48 49 struct tableElement newElement char symbol int def struct tableElement next 50 struct tableElement n malloc sizeof struct tableElement 51 n symbolName char malloc strlen symbol 1 52 strcpy n symbolName symbol 53 n defPos def 54 n uses NULL 55 n next next 56 return n 57 58 59 60 Returns the result of adding a definition for the given symbol 61 in the line with the given number to the table 62 63 struct table addDef char symbol int lineNum struct table symbols 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 struct tableElement n struct tableElement prev NULL struct tableElement p symbols head if p NULL Start new list n newElement symbol lineNum p symbols head n else Locate point before insertion while p strcmp symbol p symbolName 0 prev p p p next if p strcmp symbol p symbolName 0 p defPos lineNum else n newElement symbol lineNum p n next p if prev prev next n else symbols head n return symbols returns the result of adding a use of the given table in the line with the given number to the table struct table addUse char symbol int lineNum struct table symbols struct tableElement n struct tableElement prev NULL struct tableElement p symbols head Find point of insertion or update while p strcmp symbol p symbolName 0 prev p p p next if p strcmp symbol p symbolName 0 Already defined p uses add useNode p uses lineNum Add use else n newElement symbol 1 p Create undef entry n uses add useNode n uses lineNum n next p if prev prev next n else symbols head n return symbols void printTableElem struct tableElement elem FILE out struct useNode u elem uses fprintf out s t d elem symbolName elem defPos while u fprintf out t d u pos u u next fprintf out n void printTable struct table symbols FILE out struct tableElement p symbols head while p printTableElem p out p p next Problem 2 The complete the code for the function PrintIntArray so that it prints each element of the array passed to it by calling printInt Be sure to set up a correct stack frame and respect the register conventions such that it could be called in setting other than the particular test case here data A eol word 0 1 2 3 4 5 6 7 8 9 asciiz n text jal main li v0 10 syscall default runtime at start of text printString li v0 4 syscall jr ra printInt li v0 1 syscall jr ra printIntArray jr ra addi sw sp sp 4 ra 0 sp li la jal la jal a0 10 a1 A printIntArray a0 eol printString lw addi jr ra 0 sp sp sp 4 ra main printIntArray int n int A Problem 3 The following defines vsum and vadd as in your hw3 Modify main so that it allocates an array of ints D in its stack frame and calls VADD with that instead of the statically allocated array C Use the print code from problem 2 data A B C word 0 1 2 3 4 5 6 7 8 9 word 9 8 7 6 5 4 3 2 1 0 word 0 0 0 0 0 0 …
View Full Document
Unlocking...