ext/ply/example/BASIC/basinterp.py

   1 # This file provides the runtime support for running a basic program
   2 # Assumes the program has been parsed using basparse.py
   3
   4 import sys
   5 import math
   6 import random
   7
   8 class BasicInterpreter:
   9
  10     # Initialize the interpreter. prog is a dictionary
  11     # containing (line,statement) mappings
  12     def __init__(self,prog):
  13          self.prog = prog
  14
  15          self.functions = {           # Built-in function table
  16              'SIN' : lambda z: math.sin(self.eval(z)),
  17              'COS' : lambda z: math.cos(self.eval(z)),
  18              'TAN' : lambda z: math.tan(self.eval(z)),
  19              'ATN' : lambda z: math.atan(self.eval(z)),
  20              'EXP' : lambda z: math.exp(self.eval(z)),
  21              'ABS' : lambda z: abs(self.eval(z)),
  22              'LOG' : lambda z: math.log(self.eval(z)),
  23              'SQR' : lambda z: math.sqrt(self.eval(z)),
  24              'INT' : lambda z: int(self.eval(z)),
  25              'RND' : lambda z: random.random()
  26          }
  27
  28     # Collect all data statements
  29     def collect_data(self):
  30          self.data = []
  31          for lineno in self.stat:
  32               if self.prog[lineno][0] == 'DATA':
  33                   self.data = self.data + self.prog[lineno][1]
  34          self.dc = 0                  # Initialize the data counter
  35
  36     # Check for end statements
  37     def check_end(self):
  38          has_end = 0
  39          for lineno in self.stat:
  40              if self.prog[lineno][0] == 'END' and not has_end:
  41                   has_end = lineno
  42          if not has_end:
  43              print "NO END INSTRUCTION"
  44              self.error = 1
  45          if has_end != lineno:
  46              print "END IS NOT LAST"
  47              self.error = 1
  48
  49     # Check loops
  50     def check_loops(self):
  51          for pc in range(len(self.stat)):
  52              lineno = self.stat[pc]
  53              if self.prog[lineno][0] == 'FOR':
  54                   forinst = self.prog[lineno]
  55                   loopvar = forinst[1]
  56                   for i in range(pc+1,len(self.stat)):
  57                        if self.prog[self.stat[i]][0] == 'NEXT':
  58                             nextvar = self.prog[self.stat[i]][1]
  59                             if nextvar != loopvar: continue
  60                             self.loopend[pc] = i
  61                             break
  62                   else:
  63                        print "FOR WITHOUT NEXT AT LINE" % self.stat[pc]
  64                        self.error = 1
  65
  66     # Evaluate an expression
  67     def eval(self,expr):
  68         etype = expr[0]
  69         if etype == 'NUM': return expr[1]
  70         elif etype == 'GROUP': return self.eval(expr[1])
  71         elif etype == 'UNARY':
  72              if expr[1] == '-': return -self.eval(expr[2])
  73         elif etype == 'BINOP':
  74              if expr[1] == '+': return self.eval(expr[2])+self.eval(expr[3])
  75              elif expr[1] == '-': return self.eval(expr[2])-self.eval(expr[3])
  76              elif expr[1] == '*': return self.eval(expr[2])*self.eval(expr[3])
  77              elif expr[1] == '/': return float(self.eval(expr[2]))/self.eval(expr[3])
  78              elif expr[1] == '^': return abs(self.eval(expr[2]))**self.eval(expr[3])
  79         elif etype == 'VAR':
  80              var,dim1,dim2 = expr[1]
  81              if not dim1 and not dim2:
  82                   if self.vars.has_key(var):
  83                        return self.vars[var]
  84                   else:
  85                        print "UNDEFINED VARIABLE", var, "AT LINE", self.stat[self.pc]
  86                        raise RuntimeError
  87              # May be a list lookup or a function evaluation
  88              if dim1 and not dim2:
  89                 if self.functions.has_key(var):
  90                       # A function
  91                       return self.functions[var](dim1)
  92                 else:
  93                       # A list evaluation
  94                       if self.lists.has_key(var):
  95                             dim1val = self.eval(dim1)
  96                             if dim1val < 1 or dim1val > len(self.lists[var]):
  97                                  print "LIST INDEX OUT OF BOUNDS AT LINE", self.stat[self.pc]
  98                                  raise RuntimeError
  99                             return self.lists[var][dim1val-1]
 100              if dim1 and dim2:
 101                  if self.tables.has_key(var):
 102                       dim1val = self.eval(dim1)
 103                       dim2val = self.eval(dim2)
 104                       if dim1val < 1 or dim1val > len(self.tables[var]) or dim2val < 1 or dim2val > len(self.tables[var][0]):
 105                            print "TABLE INDEX OUT OUT BOUNDS AT LINE", self.stat[self.pc]
 106                            raise RuntimeError
 107                       return self.tables[var][dim1val-1][dim2val-1]
 108              print "UNDEFINED VARIABLE", var, "AT LINE", self.stat[self.pc]
 109              raise RuntimeError
 110
 111     # Evaluate a relational expression
 112     def releval(self,expr):
 113          etype = expr[1]
 114          lhs   = self.eval(expr[2])
 115          rhs   = self.eval(expr[3])
 116          if etype == '<':
 117              if lhs < rhs: return 1
 118              else: return 0
 119
 120          elif etype == '<=':
 121              if lhs <= rhs: return 1
 122              else: return 0
 123
 124          elif etype == '>':
 125              if lhs > rhs: return 1
 126              else: return 0
 127
 128          elif etype == '>=':
 129              if lhs >= rhs: return 1
 130              else: return 0
 131
 132          elif etype == '=':
 133              if lhs == rhs: return 1
 134              else: return 0
 135
 136          elif etype == '<>':
 137              if lhs != rhs: return 1
 138              else: return 0
 139
 140     # Assignment
 141     def assign(self,target,value):
 142         var, dim1, dim2 = target
 143         if not dim1 and not dim2:
 144             self.vars[var] = self.eval(value)
 145         elif dim1 and not dim2:
 146             # List assignment
 147             dim1val = self.eval(dim1)
 148             if not self.lists.has_key(var):
 149                  self.lists[var] = [0]*10
 150
 151             if dim1val > len(self.lists[var]):
 152                  print "DIMENSION TOO LARGE AT LINE", self.stat[self.pc]
 153                  raise RuntimeError
 154             self.lists[var][dim1val-1] = self.eval(value)
 155         elif dim1 and dim2:
 156             dim1val = self.eval(dim1)
 157             dim2val = self.eval(dim2)
 158             if not self.tables.has_key(var):
 159                  temp = [0]*10
 160                  v = []
 161                  for i in range(10): v.append(temp[:])
 162                  self.tables[var] = v
 163             # Variable already exists
 164             if dim1val > len(self.tables[var]) or dim2val > len(self.tables[var][0]):
 165                  print "DIMENSION TOO LARGE AT LINE", self.stat[self.pc]
 166                  raise RuntimeError
 167             self.tables[var][dim1val-1][dim2val-1] = self.eval(value)
 168
 169     # Change the current line number
 170     def goto(self,linenum):
 171          if not self.prog.has_key(linenum):
 172               print "UNDEFINED LINE NUMBER %d AT LINE %d" % (linenum, self.stat[self.pc])
 173               raise RuntimeError
 174          self.pc = self.stat.index(linenum)
 175
 176     # Run it
 177     def run(self):
 178         self.vars   = { }            # All variables
 179         self.lists  = { }            # List variables
 180         self.tables = { }            # Tables
 181         self.loops  = [ ]            # Currently active loops
 182         self.loopend= { }            # Mapping saying where loops end
 183         self.gosub  = None           # Gosub return point (if any)
 184         self.error  = 0              # Indicates program error
 185
 186         self.stat = self.prog.keys()      # Ordered list of all line numbers
 187         self.stat.sort()
 188         self.pc = 0                  # Current program counter
 189
 190         # Processing prior to running
 191
 192         self.collect_data()          # Collect all of the data statements
 193         self.check_end()
 194         self.check_loops()
 195
 196         if self.error: raise RuntimeError
 197
 198         while 1:
 199             line  = self.stat[self.pc]
 200             instr = self.prog[line]
 201
 202             op = instr[0]
 203
 204             # END and STOP statements
 205             if op == 'END' or op == 'STOP':
 206                  break           # We're done
 207
 208             # GOTO statement
 209             elif op == 'GOTO':
 210                  newline = instr[1]
 211                  self.goto(newline)
 212                  continue
 213
 214             # PRINT statement
 215             elif op == 'PRINT':
 216                  plist = instr[1]
 217                  out = ""
 218                  for label,val in plist:
 219                      if out:
 220                           out += ' '*(15 - (len(out) % 15))
 221                      out += label
 222                      if val:
 223                           if label: out += " "
 224                           eval = self.eval(val)
 225                           out += str(eval)
 226                  sys.stdout.write(out)
 227                  end = instr[2]
 228                  if not (end == ',' or end == ';'):
 229                      sys.stdout.write("\n")
 230                  if end == ',': sys.stdout.write(" "*(15-(len(out) % 15)))
 231                  if end == ';': sys.stdout.write(" "*(3-(len(out) % 3)))
 232
 233             # LET statement
 234             elif op == 'LET':
 235                  target = instr[1]
 236                  value  = instr[2]
 237                  self.assign(target,value)
 238
 239             # READ statement
 240             elif op == 'READ':
 241                  for target in instr[1]:
 242                       if self.dc < len(self.data):
 243                           value = ('NUM',self.data[self.dc])
 244                           self.assign(target,value)
 245                           self.dc += 1
 246                       else:
 247                           # No more data.  Program ends
 248                           return
 249             elif op == 'IF':
 250                  relop = instr[1]
 251                  newline = instr[2]
 252                  if (self.releval(relop)):
 253                      self.goto(newline)
 254                      continue
 255
 256             elif op == 'FOR':
 257                  loopvar = instr[1]
 258                  initval = instr[2]
 259                  finval  = instr[3]
 260                  stepval = instr[4]
 261
 262                  # Check to see if this is a new loop
 263                  if not self.loops or self.loops[-1][0] != self.pc:
 264                         # Looks like a new loop. Make the initial assignment
 265                         newvalue = initval
 266                         self.assign((loopvar,None,None),initval)
 267                         if not stepval: stepval = ('NUM',1)
 268                         stepval = self.eval(stepval)    # Evaluate step here
 269                         self.loops.append((self.pc,stepval))
 270                  else:
 271                         # It's a repeat of the previous loop
 272                         # Update the value of the loop variable according to the step
 273                         stepval = ('NUM',self.loops[-1][1])
 274                         newvalue = ('BINOP','+',('VAR',(loopvar,None,None)),stepval)
 275
 276                  if self.loops[-1][1] < 0: relop = '>='
 277                  else: relop = '<='
 278                  if not self.releval(('RELOP',relop,newvalue,finval)):
 279                       # Loop is done. Jump to the NEXT
 280                       self.pc = self.loopend[self.pc]
 281                       self.loops.pop()
 282                  else:
 283                       self.assign((loopvar,None,None),newvalue)
 284
 285             elif op == 'NEXT':
 286                  if not self.loops:
 287                        print "NEXT WITHOUT FOR AT LINE",line
 288                        return
 289
 290                  nextvar = instr[1]
 291                  self.pc = self.loops[-1][0]
 292                  loopinst = self.prog[self.stat[self.pc]]
 293                  forvar = loopinst[1]
 294                  if nextvar != forvar:
 295                        print "NEXT DOESN'T MATCH FOR AT LINE", line
 296                        return
 297                  continue
 298             elif op == 'GOSUB':
 299                  newline = instr[1]
 300                  if self.gosub:
 301                        print "ALREADY IN A SUBROUTINE AT LINE", line
 302                        return
 303                  self.gosub = self.stat[self.pc]
 304                  self.goto(newline)
 305                  continue
 306
 307             elif op == 'RETURN':
 308                  if not self.gosub:
 309                       print "RETURN WITHOUT A GOSUB AT LINE",line
 310                       return
 311                  self.goto(self.gosub)
 312                  self.gosub = None
 313
 314             elif op == 'FUNC':
 315                  fname = instr[1]
 316                  pname = instr[2]
 317                  expr  = instr[3]
 318                  def eval_func(pvalue,name=pname,self=self,expr=expr):
 319                       self.assign((pname,None,None),pvalue)
 320                       return self.eval(expr)
 321                  self.functions[fname] = eval_func
 322
 323             elif op == 'DIM':
 324                  for vname,x,y in instr[1]:
 325                      if y == 0:
 326                           # Single dimension variable
 327                           self.lists[vname] = [0]*x
 328                      else:
 329                           # Double dimension variable
 330                           temp = [0]*y
 331                           v = []
 332                           for i in range(x):
 333                               v.append(temp[:])
 334                           self.tables[vname] = v
 335
 336             self.pc += 1
 337
 338     # Utility functions for program listing
 339     def expr_str(self,expr):
 340         etype = expr[0]
 341         if etype == 'NUM': return str(expr[1])
 342         elif etype == 'GROUP': return "(%s)" % self.expr_str(expr[1])
 343         elif etype == 'UNARY':
 344              if expr[1] == '-': return "-"+str(expr[2])
 345         elif etype == 'BINOP':
 346              return "%s %s %s" % (self.expr_str(expr[2]),expr[1],self.expr_str(expr[3]))
 347         elif etype == 'VAR':
 348               return self.var_str(expr[1])
 349
 350     def relexpr_str(self,expr):
 351          return "%s %s %s" % (self.expr_str(expr[2]),expr[1],self.expr_str(expr[3]))
 352
 353     def var_str(self,var):
 354          varname,dim1,dim2 = var
 355          if not dim1 and not dim2: return varname
 356          if dim1 and not dim2: return "%s(%s)" % (varname, self.expr_str(dim1))
 357          return "%s(%s,%s)" % (varname, self.expr_str(dim1),self.expr_str(dim2))
 358
 359     # Create a program listing
 360     def list(self):
 361          stat = self.prog.keys()      # Ordered list of all line numbers
 362          stat.sort()
 363          for line in stat:
 364              instr = self.prog[line]
 365              op = instr[0]
 366              if op in ['END','STOP','RETURN']:
 367                    print line, op
 368                    continue
 369              elif op == 'REM':
 370                    print line, instr[1]
 371              elif op == 'PRINT':
 372                    print line, op,
 373                    first = 1
 374                    for p in instr[1]:
 375                          if not first: print ",",
 376                          if p[0] and p[1]: print '"%s"%s' % (p[0],self.expr_str(p[1])),
 377                          elif p[1]: print self.expr_str(p[1]),
 378                          else: print '"%s"' % (p[0],),
 379                          first = 0
 380                    if instr[2]: print instr[2]
 381                    else: print
 382              elif op == 'LET':
 383                    print line,"LET",self.var_str(instr[1]),"=",self.expr_str(instr[2])
 384              elif op == 'READ':
 385                    print line,"READ",
 386                    first = 1
 387                    for r in instr[1]:
 388                          if not first: print ",",
 389                          print self.var_str(r),
 390                          first = 0
 391                    print ""
 392              elif op == 'IF':
 393                    print line,"IF %s THEN %d" % (self.relexpr_str(instr[1]),instr[2])
 394              elif op == 'GOTO' or op == 'GOSUB':
 395                    print line, op, instr[1]
 396              elif op == 'FOR':
 397                    print line,"FOR %s = %s TO %s" % (instr[1],self.expr_str(instr[2]),self.expr_str(instr[3])),
 398                    if instr[4]: print "STEP %s" % (self.expr_str(instr[4])),
 399                    print
 400              elif op == 'NEXT':
 401                    print line,"NEXT", instr[1]
 402              elif op == 'FUNC':
 403                    print line,"DEF %s(%s) = %s" % (instr[1],instr[2],self.expr_str(instr[3]))
 404              elif op == 'DIM':
 405                    print line,"DIM",
 406                    first = 1
 407                    for vname,x,y in instr[1]:
 408                          if not first: print ",",
 409                          first = 0
 410                          if y == 0:
 411                                print "%s(%d)" % (vname,x),
 412                          else:
 413                                print "%s(%d,%d)" % (vname,x,y),
 414
 415                    print
 416              elif op == 'DATA':
 417                    print line,"DATA",
 418                    first = 1
 419                    for v in instr[1]:
 420                         if not first: print ",",
 421                         first = 0
 422                         print v,
 423                    print
 424
 425     # Erase the current program
 426     def new(self):
 427          self.prog = {}
 428
 429     # Insert statements
 430     def add_statements(self,prog):
 431          for line,stat in prog.items():
 432               self.prog[line] = stat
 433
 434     # Delete a statement
 435     def del_line(self,lineno):
 436          try:
 437              del self.prog[lineno]
 438          except KeyError:
 439              pass
 440