basinterp.py revision 4479:61d3ed46e373 
1# This file provides the runtime support for running a basic program
2# Assumes the program has been parsed using basparse.py
3
4import sys
5import math
6import random
7
8class 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
441