home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / Secret Solutions Folder / Problem 10 - Interpreter / Solution.cp < prev    next >
Encoding:
Text File  |  1998-06-20  |  8.2 KB  |  320 lines  |  [TEXT/CWIE]
  1. /*
  2. Problem 10 - Interpreter
  3.  
  4. Write an interpreter for this simple 32-bit integer language with 26 registers labeled A-Z.
  5.  
  6. type RegisterArray = array[0..25] of UInt32;
  7.  
  8. procedure Interpret( source: Handle; var result: RegisterArray );
  9.  
  10. source consists of a number of lines of the form:
  11.  
  12. [<label>:][<tab><instruction><tab><operand-list>]<cr>
  13.  
  14. <label> is a sequence of at least two alphanumerics (0-9a-zA-Z_) (casesensitive).
  15. <operand-list> is a sequence of operators seperated by commas
  16. other than the tabs and crs, no white space is allowed.
  17.  
  18. <instruction> (and appropriate operands are:
  19.  
  20. MOVE    <value>,<register>            (set <register> to <value>)
  21. ADD     <value1>,<value2>,<register>  (set <register> to <value1>+<value2>)
  22. SUB     <value1>,<value2>,<register>  (set <register> to <value1>-<value2>)
  23. JMP     <label>                       (jump to line labeled with <label>)
  24. JEQ     <value1>,<value2>,<label>     (jump to <label> if <value1> = <value2>)
  25. JLE     <value1>,<value2>,<label>     (jump to <label> if <value1> <= <value2>)
  26. JSR     <label>                       (jump to subroutine at <label>)
  27. RTS                                   (return from subroutine)
  28. PUSH    <value>                       (push value on to stack)
  29. POP     <register>                    (pop value from stack)
  30. [others?]
  31.  
  32. <register> is a single letter
  33. <number> is an optioanl minus sign followed by decimal digits
  34. <value> is a <register> or a <number>
  35.  
  36. Note that the data stack and subroutine stack are independent stacks.  A RTS is used to stop the program (that is, consider that you have JSRed to the initial line of the source handle).  For example:
  37.  
  38.     PUSH    10
  39.     JSR    setA
  40.     JSE setB
  41.     RTS
  42. setA:
  43.     POP    A
  44.     RTS
  45. setB:    MOVE    A,B
  46.     RTS
  47.     
  48. Interpret takes the source handle and JSRs to it, presetting the registers according to the register array.  When the code returns, the register array is set to the final value of all the registers.  Both subroutine and data stacks should be large (at least 1000 entries each).
  49. */
  50.  
  51. #include "Solution.h"
  52. #include <stdio.h>
  53. #include <stdlib.h>
  54. #include <string.h>
  55.   
  56.  #define NOTDELIMITER(x) (((x)!='\t') && ((x)!=',') && ((x)!='\r'))
  57.  
  58. // Fill in your solution and then submit this folder
  59.  
  60. // Team Name: FILL IN YOUR TEAM NAME!
  61. typedef enum {kNULL=0,kMove=1,kAdd,kSub,kJmp,kJeq,kJle,kJsr,kRts,kPush,kPop} OpCode;
  62.  
  63. char *OpCodeStrings[] = {
  64.     "    ","MOVE","ADD","SUB","JMP","JEQ","JLE","JSR","RTS","PUSH","POP"
  65. };
  66.  
  67. #define kNumCommands (sizeof(OpCodeStrings)/sizeof(char *))
  68.  
  69. typedef struct Instruction {
  70.     UInt32 programCounter;
  71.     UInt32 branchPC;
  72.     char *label;
  73.     char *branchLabel;
  74.     SInt32 value1;
  75.     SInt32 value2;
  76.     SInt32 reg;
  77.     OpCode theCode;
  78.     UInt32 labelLength;
  79.     Boolean value1IsRegister;
  80.     Boolean value2IsRegister;
  81. } Instruction;
  82.  
  83. static char *GetValue(char *p, SInt32 *value, Boolean *valueIsRegister)
  84. {
  85.     char s[256];
  86.     char *q = s;
  87.     if ((*p>='A') && (*p<='Z')) {
  88.         *valueIsRegister = true;
  89.         *value = *p-'A';
  90.         p++;
  91.     } else {
  92.         while (NOTDELIMITER(*p) ) *q++=*p++;
  93.         *q++=0;
  94.         sscanf( s, "%ld", value );
  95.     }
  96.     return p+1;    /* skip comma, cr, or tab */
  97. }
  98.  
  99. static char *FindLabel(char *p, UInt32 *branchPC, Instruction *program, long numInstructions)
  100. {
  101.     int i;
  102.     Boolean foundIt=false;
  103.     for (i=0; i<numInstructions; i++,program++) {
  104.         if (program->label)
  105.             if (0 == strncmp(p,program->label,program->labelLength)) {
  106.                 foundIt = true;
  107.                 *branchPC = i;
  108.                 break;
  109.             }
  110.     }
  111.     if (!foundIt) DebugStr("\p did not find label");
  112.     while (*p++!='\r') ;
  113.     return p;
  114. }
  115.  
  116. #define PUSH(pc,stack,stackCtr) \
  117.    stack[stackCtr] = pc; \
  118.    stackCtr++;
  119.  
  120. #define POP(val,stack,stackCtr) \
  121.    val = stack[--stackCtr]; 
  122.   
  123.  static void GetValue12(Instruction *pc, RegisterArray reg, SInt32 *val1, SInt32 *val2)
  124.  {
  125.         if (pc->value1IsRegister) {
  126.             *val1 = reg[pc->value1];
  127.         } else {
  128.             *val1 = pc->value1;
  129.         }
  130.         if (pc->value2IsRegister) {
  131.             *val2 = reg[pc->value2];
  132.         } else {
  133.             *val2 = pc->value2;
  134.         }
  135. }
  136.  
  137.  static void ParseInstructions(char *sourceP, Instruction *program, int instructionCount)
  138.  {
  139.      char *p;
  140.      int i,j,opCodeLen;
  141.      Instruction *pc;
  142.      
  143.      p = sourceP;
  144.     for (i=0; i<instructionCount; i++) {
  145.         pc = &program[i];
  146.         pc->programCounter = i;
  147.         pc->label = 0;
  148.         pc->branchPC = 0xffffffff;
  149.         pc->branchLabel = 0;
  150.         pc->value1 = 0xffffffff;
  151.         pc->value2 = 0xffffffff;
  152.         pc->reg = 0xffffffff;
  153.         pc->theCode = kNULL;
  154.         pc->value1IsRegister = false;
  155.         pc->value2IsRegister = false;
  156.         if (*p != '\t') {
  157.             char *labelStart = p;
  158.             pc->label = p;
  159.             while (*p!=':') p++;
  160.             pc->labelLength = p - labelStart;
  161.             p++;        /* skip colon */
  162.             if (*p=='\t') p++;
  163.         } else {
  164.             p++;
  165.         }
  166.         opCodeLen = 0;
  167.         while (NOTDELIMITER(*(p+opCodeLen))) opCodeLen++;
  168.         for (j=1; j<kNumCommands; j++) {
  169.             if (0==strncmp(p,OpCodeStrings[j],opCodeLen)) {
  170.                 pc->theCode = (OpCode)j;
  171.             }
  172.         }
  173.         p += opCodeLen+1;
  174.         switch (pc->theCode) {
  175.         Boolean betterBeTrue;
  176.         case kMove:
  177.             p = GetValue(p,&pc->value1,&pc->value1IsRegister);
  178.             p = GetValue(p,&pc->reg,&betterBeTrue);
  179.             break;
  180.         case kAdd:
  181.         case kSub:
  182.             p = GetValue(p,&pc->value1,&pc->value1IsRegister);
  183.             p = GetValue(p,&pc->value2,&pc->value2IsRegister);
  184.             p = GetValue(p,&pc->reg,&betterBeTrue);
  185.             if (!betterBeTrue) DebugStr("\p problem parsing Add/Sub register");
  186.             break;
  187.         case kJmp:
  188.         case kJsr:
  189.             pc->branchLabel = p;
  190.             while (*p++!='\r') ;
  191.             break;
  192.         case kJeq:
  193.         case kJle:
  194.             p = GetValue(p,&pc->value1,&pc->value1IsRegister);
  195.             p = GetValue(p,&pc->value2,&pc->value2IsRegister);
  196.             pc->branchLabel = p;
  197.             while (*p++!='\r') ;
  198.             break;
  199.         case kRts:
  200.             break;
  201.         case kPush:
  202.             p = GetValue(p,&pc->value1,&pc->value1IsRegister);
  203.             break;
  204.         case kPop:
  205.             p = GetValue(p,&pc->reg,&betterBeTrue);
  206.             if (!betterBeTrue) DebugStr("\p problem parsing Pop register");
  207.             break;
  208.         default:
  209.             DebugStr("\p could not parse instruction");
  210.         }
  211.     }
  212. /* parse labels */
  213.     for (i=0; i<instructionCount; i++) {
  214.         pc = &program[i];
  215.         if (pc->branchLabel != 0) {
  216.             p = FindLabel(pc->branchLabel,&pc->branchPC,program,instructionCount);
  217.         }
  218.     }
  219. }
  220.  
  221.  static void Execute(Instruction *program, RegisterArray reg)
  222.  {
  223.      Instruction *pc;
  224.      UInt32 pcIndex = 0;
  225.     SInt32 *subroutineStack,*dataStack;
  226.     SInt32 subroutineStackCtr = 0;
  227.     SInt32 dataStackCtr = 0;
  228.     Boolean done;
  229.  
  230.     subroutineStack = (SInt32 *)NewPtrClear(1000*sizeof(UInt32));
  231.     if (0==subroutineStack) DebugStr("\p problem allocating subroutineStack");
  232.     dataStack = (SInt32 *)NewPtrClear(1000*sizeof(UInt32));
  233.     if (0==dataStack) DebugStr("\p problem allocating dataStack");
  234.     
  235.     done = false;
  236.     while (!done) {
  237.         SInt32 val1,val2;
  238.         pc = &program[pcIndex];
  239.         GetValue12(pc,reg,&val1,&val2);
  240.         switch (pc->theCode) {
  241.         case kMove:
  242.             if (pc->value1IsRegister) {
  243.                 reg[pc->reg] = reg[pc->value1];
  244.             } else {
  245.                 reg[pc->reg] = pc->value1;
  246.             }
  247.             pcIndex++;
  248.             break;
  249.         case kAdd:
  250.             reg[pc->reg] = val1+val2;
  251.             pcIndex++;
  252.             break;
  253.         case kSub:
  254.             reg[pc->reg] = val1-val2;
  255.             pcIndex++;
  256.             break;
  257.         case kJmp:
  258.             pcIndex = pc->branchPC;
  259.             break;
  260.         case kJsr:
  261.             PUSH(pcIndex+1,subroutineStack,subroutineStackCtr)
  262.             pcIndex = pc->branchPC;
  263.             break;
  264.         case kJeq:
  265.             if (val1==val2) pcIndex = pc->branchPC;
  266.             else pcIndex++;
  267.             break;
  268.         case kJle:
  269.             if (val1<=val2) pcIndex = pc->branchPC;
  270.             else pcIndex++;
  271.             break;
  272.         case kRts:
  273.             if (subroutineStackCtr<=0) done=true;
  274.             else POP(pcIndex,subroutineStack,subroutineStackCtr)
  275.             break;
  276.         case kPush:
  277.             PUSH(val1,dataStack,dataStackCtr)
  278.             pcIndex++;
  279.             break;
  280.         case kPop:
  281.             POP(reg[pc->reg],dataStack,dataStackCtr)
  282.             pcIndex++;
  283.             break;
  284.         default:
  285.             DebugStr("\p should not get here");
  286.             break;
  287.         }
  288.     }
  289.     DisposePtr((Ptr)dataStack);
  290.     DisposePtr((Ptr)subroutineStack);
  291.  }
  292.  
  293. pascal void Interpret( Handle source,  RegisterArray result )
  294. {
  295.     char *sourceP = *source;
  296.     char *p;
  297.     RegisterArray reg;
  298.     Instruction *program;
  299.     int i,instructionCount;
  300.     SInt32 sourceCharCount = GetHandleSize(source);
  301.     
  302. /* initialize registers */
  303.     for (i=0; i<26; i++) reg[i]=result[i];
  304.     instructionCount = 0;
  305. /* count instructions */
  306.     p = sourceP;
  307.     while (p < sourceP + sourceCharCount) {
  308.         if (*p++=='\r') ++instructionCount;
  309.     }
  310.     program = (Instruction *)NewPtrClear(instructionCount*sizeof(Instruction));
  311.     if (0==program) DebugStr("\p not enough mem for program");
  312. /* parse instructions */
  313.     ParseInstructions(sourceP,program,instructionCount);
  314. /* execute instructions */
  315.     Execute(program,reg);
  316.     
  317.     DisposePtr((Ptr)program);
  318.     for (i=0; i<26; i++) result[i]=reg[i];
  319. }
  320.