Semplice.c (13398B)
1 /* 2 * Exercise 12.27 3 * The Simple compiler 4 * 5 * WARNING: this code is *very* unstable! 6 * NO WARRANTY!! - USE AT YOUR OWN RISK!! 7 */ 8 9 #include <stdio.h> 10 #include <stdlib.h> 11 #include <string.h> 12 #include <ctype.h> 13 14 #define INPUT "source.s" 15 #define OUTPUT "fout.lms" 16 17 #define SIZE 255 18 #define BUF 100 19 20 /* Symbol table */ 21 typedef struct symtab_t { 22 int symbol; 23 char type; /* 'L', 'C' or 'V' */ 24 int location; /* from 00 to 99 */ 25 } Table; 26 27 /* Stack structure */ 28 typedef struct stack_t { 29 char c; 30 struct stack_t *next; 31 } Stack; 32 33 /* 34 * Prototypes 35 */ 36 char pop(Stack **stackp); 37 void push(Stack **stackp, char value); 38 void topostfix(char infix[], char postfix[]); 39 void evalpfexp(char *expr, Table *stab, int *icount, 40 int *t, int *emem, int *lmsmem); 41 int calculate(int op1, int op2, char operator); 42 int isoper(char c); 43 char isempty(Stack *stackp); 44 int precedence(char op1, char op2); 45 char stacktop(Stack *stackp); 46 int getcode(char *cmd); 47 int getsym(int c, int len, Table *stab); 48 void pw_lmsmem(int *lmsmem, const int size, char *o_file); 49 void showtab(Table *stab, const int size); 50 51 /* Compilation steps */ 52 void fstep(Table *stab, char *infile, int *lmsmem, int *flags); 53 void sstep(Table *stab, int *lmsmem, int *flags, int size); 54 55 /* The main function */ 56 int main(void) 57 { 58 int lmsmem[BUF], flags[BUF]; 59 Table stab[BUF]; 60 int c; 61 62 fstep( stab, (char *)INPUT, lmsmem, flags ); /* The 1st step */ 63 sstep( stab, lmsmem, flags, BUF ); /* The 2nd step */ 64 65 printf("\nShow the symbol table (y/n)?: "); 66 while( (c = fgetc(stdin)) != EOF ) { 67 if( c == 'y' ) { 68 showtab(stab, BUF); 69 break; 70 } 71 else if( c == 'n' ) 72 break; 73 else { 74 puts("\nInvalid input"); 75 printf("Show the symbol table (y/n)?: "); 76 } 77 } 78 79 putchar('\n'); 80 81 return 0; 82 } /* E0F main */ 83 84 /* 85 * First step: create the symbol table and some incomplete 86 * instruction putting them to the memory array "lmsmem" 87 */ 88 void fstep(Table *stab, char *infile, int *lmsmem, int *flags) 89 { 90 FILE *fd; 91 char cline[SIZE]; /* Current line */ 92 char postfix[BUF], *tokp; 93 94 const int size = BUF - 1; 95 int t = 0, icount = 0; 96 int emem = size; /* End memory */ 97 int x, i; 98 99 /* Initialize the data */ 100 for(i = 0; i < BUF; i++) { 101 lmsmem[i] = 0; 102 flags[i] = -1; 103 104 stab[i].location = 0; 105 stab[i].type = stab[i].symbol = '0'; 106 } 107 108 /* open the file */ 109 if( (fd = fopen(infile, "r")) == NULL ) { 110 printf("Cannot open the file: %s\n", infile); 111 exit(-1); 112 } 113 114 fgets(cline, sizeof(cline), fd); 115 cline[ strlen(cline) + 1 ] = '\0'; 116 while( !feof(fd) ) { 117 118 /* Line number */ 119 if( (tokp = strtok(cline, " ")) != NULL ) { 120 stab[t].symbol = atoi(tokp); 121 stab[t].type = 'L'; 122 stab[t].location = icount; 123 ++t; 124 } 125 126 if( (tokp = strtok(NULL, " ")) != NULL ) { 127 128 /* check the command */ 129 switch( getcode(tokp) ) { 130 case 1: /* rem */ 131 132 /* do nothing */ 133 134 break; 135 case 10: /* input */ 136 137 /* take the variable */ 138 if( (tokp = strtok(NULL, " ")) != NULL ) { 139 140 if( (x = getsym(*tokp, size, stab)) == -1 ) { 141 stab[t].symbol = *tokp; 142 stab[t].type = 'V'; 143 x = stab[t].location = emem--; 144 ++t; 145 } 146 else 147 x = stab[x].location; 148 149 lmsmem[icount] = 1000 + x; 150 } 151 152 ++icount; 153 break; 154 case 3: /* let */ 155 156 /* Add all symbols to the table */ 157 tokp = strtok(NULL, " "); 158 while( tokp != NULL ) { 159 if( !isoper(*tokp) && *tokp != '=' && 160 getsym(*tokp, size, stab) == -1 161 ) { 162 stab[t].symbol = *tokp; 163 stab[t].location = emem--; 164 stab[t].type = isdigit((int)*tokp) ? 'C' : 'V'; 165 ++t; 166 } 167 tokp = strtok(NULL, " "); 168 } 169 170 /* Retrieve the right side of the expression.. */ 171 for(x = 0; cline[x] != '='; x++) ; 172 x += 2; 173 174 memset(postfix, '\0', sizeof(postfix)); 175 176 while( cline[x] != '\0' ) { 177 strncat(postfix, &cline[x], sizeof(postfix)); 178 strncat(postfix, " ", sizeof(postfix)); 179 x += 2; 180 } 181 182 memset(cline, '\0', sizeof(cline)); 183 memcpy(cline, postfix, sizeof(cline)); 184 185 /* ..and convert it to postfix format */ 186 topostfix(cline, postfix); 187 188 /* 189 * Evalutate the results and create 190 * the Simpletron instructions 191 */ 192 evalpfexp(postfix, stab, &icount, &t, &emem, lmsmem); 193 194 ++icount; 195 break; 196 case 11: /* print */ 197 198 tokp = strtok(NULL, " "); /* Take the variable */ 199 x = getsym(*tokp, size, stab); 200 201 lmsmem[icount] = 1100 + stab[x].location; 202 203 ++icount; 204 break; 205 case 40: /* goto */ 206 207 tokp = strtok(NULL, " "); /* Take the line number */ 208 lmsmem[icount] = 4000; 209 if( (x = getsym(atoi(tokp), size, stab)) == -1 ) 210 flags[icount] = *tokp; 211 else 212 lmsmem[icount] += stab[x].location; 213 214 ++icount; 215 break; 216 case 6: /* if */ 217 218 tokp = strtok(NULL, " "); 219 if( (x = getsym(atoi(tokp), size, stab)) == -1 ) { 220 stab[t].symbol = *tokp; 221 stab[t].type = 'V'; 222 x = stab[t].location = emem--; 223 ++t; 224 } 225 else 226 x = stab[x].location; 227 228 lmsmem[icount++] = 2000 + x; /* +20x */ 229 230 tokp = strtok(NULL, " "); /* Skip the operator */ 231 tokp = strtok(NULL, " "); /* Read the 2nd variable */ 232 if( (x = getsym(*tokp, size, stab)) == -1 ) { 233 stab[t].symbol = *tokp; 234 stab[t].type = 'V'; 235 x = stab[t].location = emem--; 236 ++t; 237 } 238 else 239 x = stab[x].location; 240 241 lmsmem[icount++] = 3100 + x; /* +31x */ 242 243 /* Read the branch position */ 244 while( getcode(tokp) != 40 && tokp != NULL ) 245 tokp = strtok(NULL, " "); 246 tokp = strtok(NULL, " "); 247 248 /* Look for the destination in the symbol table */ 249 lmsmem[icount] = 4200; 250 if( (x = getsym(*tokp, size, stab)) == -1 ) { 251 flags[icount] = atoi(tokp); 252 } 253 else 254 lmsmem[icount] += stab[x].location; 255 256 ++icount; 257 break; 258 case 43: /* end */ 259 lmsmem[icount] = 4300; 260 261 ++icount; 262 263 break; 264 default: /* unknown command */ 265 puts("Some error.."); 266 } 267 } 268 269 fgets(cline, sizeof(cline), fd); 270 } 271 272 fclose(fd); /* Close the input file */ 273 274 } /* eof fstep() */ 275 276 /* 277 * Second step: find the incomplete instructions, complete them 278 * and write the results to the screen and in the OUTPUT file 279 */ 280 void sstep(Table *stab, int *lmsmem, int *flags, int size) 281 { 282 int i, x; 283 284 for(i = 0; i < size; i++) { 285 if( flags[i] != -1 ) { 286 x = getsym(flags[i], size, stab); 287 lmsmem[i] += stab[x].location; 288 } 289 } 290 291 /* Show the memory and write it to a file */ 292 pw_lmsmem(lmsmem, size, (char *)OUTPUT); 293 294 } /* eof sstep() */ 295 296 /* 297 * Print the whole LMS memory array 298 */ 299 void pw_lmsmem(int *lmsmem, const int size, char *o_file) 300 { 301 FILE *fd; 302 int i; 303 304 /* Open the file */ 305 if( (fd = fopen(o_file, "wb+")) == NULL ) { 306 printf("Cannot open the file: %s\n", o_file); 307 return; 308 } 309 310 puts("\n> Simpletron memory"); 311 for(i = 0; i < size && lmsmem[i]; i++) { 312 printf("%.2d: %+.4d\n", i, lmsmem[i]); 313 fprintf(fd, "%+.4d\n", lmsmem[i]); 314 } 315 316 fclose(fd); 317 } /* eof pw_lmsmem() */ 318 319 /* 320 * Print the whole symbol table 321 */ 322 void showtab(Table *stab, const int size) 323 { 324 int i; 325 326 puts("\n> Symbol table"); 327 328 for(i = 1; i < size; i++) { 329 if( stab[i - 1].type == '0' ) 330 break; 331 332 if( stab[i - 1].type == 'L' ) 333 printf("s[%2d] ", stab[i - 1].symbol); 334 else 335 printf("s[%2c] ", stab[i - 1].symbol); 336 337 printf("t[%1c] l[%.2d]\n", stab[i - 1].type, stab[i - 1].location); 338 } 339 } /* eof showtab() */ 340 341 /* 342 * Returns the position of 'c' in the Table 'stab' 343 */ 344 int getsym(int c, int len, Table *stab) 345 { 346 int i; 347 348 for(i = 0; i < len; i++) { 349 if( stab[i].symbol == c ) 350 return i; 351 } 352 353 return -1; 354 } /* eof getsym() */ 355 356 /* 357 * Returns the Simpletron operation code 358 * from the Simple instruction 'cmd' 359 */ 360 int getcode(char *cmd) 361 { 362 if( !memcmp(cmd, "rem", 3) ) 363 return 1; 364 else if( !memcmp(cmd, "input", 5) ) /* read - 10 */ 365 return 10; 366 else if( !memcmp(cmd, "let", 3) ) 367 return 3; 368 else if( !memcmp(cmd, "print", 5) ) /* write - 11 */ 369 return 11; 370 else if( !memcmp(cmd, "goto", 4) ) /* branch - 40 */ 371 return 40; 372 else if( !memcmp(cmd, "if", 2) ) 373 return 6; 374 else if( !memcmp(cmd, "end", 3) ) 375 return 43; 376 377 return 0; 378 } /* eof getcode() */ 379 380 /* 381 * Pop a value from top of the stack 382 */ 383 char pop(Stack **stackp) 384 { 385 Stack *tstackp; /* temporary stack pointer for free(3) */ 386 char ret = ( *stackp )->c; 387 388 tstackp = *stackp; 389 *stackp = ( *stackp )->next; 390 391 free(tstackp); 392 393 return ret; 394 } /* eof pop() */ 395 396 /* 397 * Push a value in top of the stack 398 */ 399 void push(Stack **stackp, char value) 400 { 401 Stack *newnode; 402 403 if( (newnode = malloc( sizeof(Stack) )) == NULL ) { 404 printf("push(): cannot allocate the memory\n"); 405 return; 406 } 407 newnode->c = value; 408 newnode->next = NULL; 409 410 newnode->next = *stackp, 411 *stackp = newnode; 412 413 } /* eof push() */ 414 415 /* 416 * Convert from infix format to reverse polish suffix 417 * E.g.: 418 * 419 * The expression (1 + 5) * 9 - 2 / 6 420 * will be equal to 1 5 + 9 * 2 6 / - 421 * 422 */ 423 void topostfix(char infix[], char postfix[]) 424 { 425 Stack *stackp = NULL; 426 int i = 0, j = 0; 427 428 push(&stackp, '('); 429 infix[ (int)strlen(infix) ] = ')'; 430 infix[ (int)strlen(infix) ] = '\0'; 431 432 while( ! isempty(stackp) ) { 433 if( isspace( (int)infix[i] ) ) ; 434 else if( infix[i] == '(' ) { 435 push(&stackp, '('); 436 } 437 else if( isoper(infix[i]) ) { 438 while( precedence(infix[i], stacktop(stackp)) != -1 ) { 439 postfix[j++] = pop(&stackp); 440 postfix[j++] = ' '; 441 } 442 443 push(&stackp, infix[i]); 444 } 445 else if( infix[i] == ')' ) { 446 while( stacktop(stackp) != '(' && isoper(stacktop(stackp)) ) { 447 postfix[j++] = pop(&stackp); 448 postfix[j++] = ' '; 449 } 450 pop(&stackp); /* remove the '(' from the stack */ 451 } 452 else { 453 postfix[j++] = infix[i]; 454 postfix[j++] = ' '; 455 } 456 457 ++i; 458 } 459 } /* eof topostfix() */ 460 461 /* 462 * Generate the Simpletron instructions from the 463 * reverse polish suffix notation expressions 464 */ 465 void evalpfexp(char *expr, Table *stab, int *icount, 466 int *t, int *emem, int *lmsmem) 467 { 468 Stack *stackp; 469 char *tokp; 470 int i, x, y; 471 472 expr[ (int)strlen(expr) + 1 ] = '\0'; 473 474 tokp = strtok(expr, " "); 475 while( tokp != NULL ) { 476 if( ! isoper( *tokp ) ) { 477 478 /* find the symbol in the table */ 479 for(i = 0; i < BUF; i++) { 480 if( *tokp == stab[i].symbol ) 481 break; 482 } 483 484 if( i == BUF ) { /* Not found */ 485 stab[*t].symbol = isdigit((int)*tokp) ? atoi(tokp) : *tokp; 486 stab[*t].type = isdigit((int)*tokp) ? 'C' : 'V'; 487 stab[*t].location = *emem--; 488 i = *t; 489 ++*t; 490 } 491 492 push(&stackp, stab[i].location); 493 } 494 else { 495 y = pop(&stackp); 496 x = pop(&stackp); 497 498 /* Make the instructions */ 499 lmsmem[(*icount)++] = 2000 + x; 500 lmsmem[(*icount)++] = 3000 + y; 501 lmsmem[(*icount)++] = 2100 + *emem; 502 lmsmem[(*icount)++] = 2000 + *emem; 503 lmsmem[(*icount)] = 2100 + x; 504 505 --*emem; 506 507 push(&stackp, lmsmem[*icount]); 508 } 509 510 tokp = strtok(NULL, " "); 511 } 512 513 } /* eof evalpfexp() */ 514 515 /* 516 * Calculate the value of expression "op1 operator op2" 517 */ 518 int calculate(int op1, int op2, char operator) 519 { 520 int i; 521 522 switch(operator) { 523 case '+': 524 return op1 + op2; 525 case '-': 526 return op1 - op2; 527 case '*': 528 return op1 * op2; 529 case '/': 530 if( !op2 ) { 531 printf("calculate(): cannot divide for zero\n"); 532 exit(-1); 533 } 534 else 535 return op1 / op2; 536 case '^': 537 for(i = op2, op2 = op1; i > 1; i--) { 538 op1 *= op2; 539 } 540 541 return op1; 542 case '%': 543 return op1 % op2; 544 } 545 546 return -1; 547 } /* eof calculate() */ 548 549 /* 550 * Check if 'c' is a valid operator 551 */ 552 int isoper(char c) 553 { 554 switch(c) { 555 case '+': 556 case '-': 557 case '*': 558 case '/': 559 case '^': 560 case '%': 561 return 1; 562 } 563 564 return 0; 565 } /* eof isoper() */ 566 567 /* 568 * Determine if the stack is empty this is a "predicate function" 569 */ 570 char isempty(Stack *stackp) 571 { 572 return stackp == NULL; 573 } /* eof isempty() */ 574 575 /* 576 * Determine if the priority of op1 is less then, equal to 577 * or greter then op2 and return respectively, -1, 0 and 1. 578 */ 579 int precedence(char op1, char op2) 580 { 581 int x = 2; 582 char *p = &op1; 583 584 while( x-- ) { 585 if( !x ) 586 p = &op2; 587 588 switch( *p ) { 589 case '%': 590 case '/': 591 case '*': 592 *p = '1'; 593 break; 594 case '-': 595 case '+': 596 *p = '2'; 597 break; 598 case '^': 599 *p = '3'; 600 break; 601 default: 602 return -1; 603 } 604 605 } 606 607 x = (op1 - '0') - (op2 - '0'); 608 609 if( x > 0 ) 610 return 1; 611 else if( x < 0 ) 612 return -1; 613 614 return 0; 615 } /* eof precedence() */ 616 617 /* 618 * As pop() but don't extract the value from top of stack 619 * This is a "predicate function" 620 */ 621 char stacktop(Stack *stackp) 622 { 623 return stackp->c; 624 } /* eof stacktop() */ 625