Ukeoppgave uken 5 til 10. september 2007 (Oppgave 1, 2 og 4 er de viktigste å få med seg.) Oppgave 1 --------- Hva gjør dette RusC-programmet? int f[101]; func init () { int i, i1, i2; f[0] = 1; f[1] = f[0]; i = 2; while (i <= 100) { i1 = i - 1; i2 = i - 2; f[i] = f[i1] + f[i2]; i = i + 1; } } func main () { int i, res; init(); while (1) { putchar('?'); i = getint(); if (i < 0) { exit(0); } res = f[i]; putint(res); putchar(10); } } Oppgave 2 --------- Mitt første forsøk på skrive programmet i forrige oppgave så slik ut: int f[101]; func init () { int i, i1, i2; f[0] = 1; f[1] = f[0]; i = 2; while (i <= 100) { i1 = i - 1; i2 = i - 2; i = i + 1; f[i] = f[i1] + f[i2]; } } func main () { int i, res; init(); while (1) { putchar('?'); i = getint(); if (i < 0) { exit(0); } res = f[i]; putint(res); putchar(10); } } men når det kjøres, blir resultatet > rask xxx.rask Rask: Illegal address (PC=1053326473082)! DUMP ==== PC=1053326473082 Last 100 instructions: 145 146 147 148 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 120 121 122 123 124 149 150 151 1053326473082 Registers R0= 0 R1= 0 R2= 101 R3= 0 R4= 0 R5= 0 R6= 0 R7= 0 R8= 0 R9= 0 R10= 0 R11= 0 R12= 0 R13= 0 R14= 0 R15= 0 R16= 0 R17= 0 R18= 0 R19= 0 R20= 0 R21= 0 R22= 0 R23= 0 R24= 0 R25= 0 R26= 0 R27= 0 R28= 0 R29= 0 R30= 0 R31=1053326473082 Memory 0: 1600000000000156 211000000000000 1600000000009990 1 4: 1 0 2 1 8: 2 3 3 5 12: 6 8 11 14 16: 19 25 33 44 20: 58 77 102 135 24: 179 237 314 416 28: 551 730 967 1281 32: 1697 2248 2978 3945 36: 5226 6923 9171 12149 40: 16094 21320 28243 37414 44: 49563 65657 86977 115220 48: 152634 202197 267854 354831 52: 470051 622685 824882 1092736 56: 1447567 1917618 2540303 3365185 60: 4457921 5905488 7823106 10363409 64: 13728594 18186515 24092003 31915109 68: 42278518 56007112 74193627 98285630 72: 130200739 172479257 228486369 302679996 76: 400965626 531166365 703645622 932131991 80: 1234811987 1635777613 2166943978 2870589600 84: 3802721591 5037533578 6673311191 8840255169 88: 11710844769 15513566360 20551099938 27224411129 92: 36064666298 47775511067 63289077427 83840177365 96: 111064588494 147129254792 194904765859 258193843286 100: 342034020651 453098609145 600227863937 795132629796 104: 1053326473082 0 101 99 108: 98 331000000000104 303000000000105 201000000000001 112: 202000000000000 301020000000003 202000000000000 101020000000003 116: 202000000000001 301020000000003 201000000000002 301000000000106 120: 101000000000106 203010000000000 201000000000100 1101030000000001 124: 1401000000000149 101000000000106 203010000000000 201000000000001 128: 501030000000001 301000000000107 101000000000106 203010000000000 132: 201000000000002 501030000000001 301000000000108 101000000000106 136: 203010000000000 201000000000001 401030000000001 301000000000106 140: 102000000000107 101020000000003 203010000000000 102000000000108 144: 101020000000003 401030000000001 102000000000106 301020000000003 148: 1400000000000120 103000000000105 131000000000104 1700000000000000 152: 1 0 0 0 156: 331000000000152 303000000000153 1600000000000109 201000000000001 160: 1401000000000180 211000000000063 1600000000009993 1600000000009992 164: 301000000000154 101000000000154 203010000000000 201000000000000 168: 1001030000000001 1401000000000172 211000000000000 1600000000009990 172: 102000000000154 101020000000003 301000000000155 111000000000155 176: 1600000000009994 211000000000010 1600000000009993 1400000000000159 180: 103000000000153 131000000000152 1700000000000000 0 Hva gikk galt? Oppgave 3 --------- Oversett programmet i oppgave 1 til Raskas-kode. Oppgave 4 --------- Om vi kjører programmet i oppgave 1 gjennom RusC-kompilatoren med opsjonen -testscanner, får vi denne log-filen: 1: int f[101]; Scanner: intToken Scanner: nameToken f Scanner: leftBracketToken Scanner: numberToken 101 Scanner: rightBracketToken Scanner: semicolonToken 2: 3: func init () Scanner: funcToken Scanner: nameToken init_f Scanner: leftParToken Scanner: rightParToken 4: { Scanner: leftCurlToken 5: int i, i1, i2; Scanner: intToken Scanner: nameToken i Scanner: semicolonToken Scanner: nameToken i1 Scanner: semicolonToken Scanner: nameToken i2 Scanner: semicolonToken 6: 7: f[0] = 1; f[1] = f[0]; Scanner: nameToken f Scanner: leftBracketToken Scanner: numberToken 0 Scanner: assignToken Scanner: numberToken 1 Scanner: semicolonToken Scanner: nameToken f Scanner: leftBracketToken Scanner: numberToken 1 Scanner: assignToken Scanner: nameToken f Scanner: leftBracketToken Scanner: numberToken 0 Scanner: semicolonToken 8: i = 2; Scanner: nameToken i Scanner: assignToken Scanner: numberToken 2 Scanner: semicolonToken 9: while (i <= 100) { Scanner: whileToken Scanner: leftParToken Scanner: nameToken i Scanner: lessEqualToken Scanner: numberToken 100 Scanner: rightParToken Scanner: leftCurlToken 10: i1 = i - 1; i2 = i - 2; Scanner: nameToken i1 Scanner: assignToken Scanner: nameToken i Scanner: subtractToken Scanner: numberToken 1 Scanner: semicolonToken Scanner: nameToken i2 Scanner: assignToken Scanner: nameToken i Scanner: subtractToken Scanner: numberToken 2 Scanner: semicolonToken 11: f[i] = f[i1] + f[i2]; Scanner: nameToken f Scanner: leftBracketToken Scanner: nameToken i Scanner: rightBracketToken Scanner: assignToken Scanner: nameToken f Scanner: leftBracketToken Scanner: nameToken i1 Scanner: rightBracketToken Scanner: addToken Scanner: nameToken f Scanner: leftBracketToken Scanner: nameToken i2 Scanner: rightBracketToken Scanner: semicolonToken 12: i = i + 1; Scanner: nameToken i Scanner: assignToken Scanner: nameToken i Scanner: addToken Scanner: numberToken 1 Scanner: semicolonToken 13: } Scanner: rightCurlToken 14: } Scanner: rightCurlToken 15: 16: func main () Scanner: funcToken Scanner: nameToken main Scanner: leftParToken Scanner: rightParToken 17: { Scanner: leftCurlToken 18: int i, res; Scanner: intToken Scanner: nameToken i Scanner: commaToken Scanner: nameToken res Scanner: semicolonToken 19: 20: init(); Scanner: nameToken init Scanner: leftParToken Scanner: rightParToken Scanner: semicolonToken 21: while (1) { Scanner: whileToken Scanner: leftParToken Scanner: numberToken 1 Scanner: rightParToken Scanner: leftCurlToken 22: putchar('?'); i = getint(); Scanner: nameToken putchar Scanner: leftParToken Scanner: numberToken 63 Scanner: rightParToken Scanner: semicolonToken Scanner: nameToken i Scanner: assignToken Scanner: nameToken getint Scanner: leftParToken Scanner: rightParToken Scanner: semicolonToken 23: if (i < 0) { exit(0); } Scanner: ifToken Scanner: leftParToken Scanner: nameToken i Scanner: lessToken Scanner: numberToken 0 Scanner: rightParToken Scanner: leftCurlToken Scanner: nameToken exit Scanner: leftParToken Scanner: numberToken 0 Scanner: rightParToken Scanner: semicolonToken Scanner: rightCurlToken 24: res = f[i]; putint(res); putchar(10); Scanner: nameToken res Scanner: assignToken Scanner: nameToken f Scanner: leftBracketToken Scanner: nameToken i Scanner: rightBracketToken Scanner: semicolonToken Scanner: nameToken putint Scanner: leftParToken Scanner: nameToken res Scanner: rightParToken Scanner: semicolonToken Scanner: nameToken putchar Scanner: leftParToken Scanner: numberToken 10 Scanner: rightParToken Scanner: semicolonToken 25: } Scanner: rightCurlToken 26: } Scanner: rightCurlToken Scanner: eofToken Men, jeg har lagt inn tre feil. Hvilke? Oppgave 5 --------- Dette programmet func main () { int v; v = getint()-1; putint(v); putchar(10); } gir denne feilmeldingen når det skal kompileres: > rusc minus.rusc RusC error in line 5: Expected a semicolonToken but found a numberToken! Hva er galt? Oppgave 6 (for spesielt interesserte) --------- På forelesningen 4.9 viste jeg (på ark 7) oversettelsen av a[i] = 2*i + f(x); Den er på 11 instruksjoner. Det er mulig å gjøre dem med 6 instruksjoner; vis hvorledes. Hint. Siden dette er en optimaliseringskonkurranse, kan man se bort fra konvensjonen om bruken av R2- og R3-registrene.