API tools faq
paste
Guest User

Untitled

a guest
May 22nd, 2018
100
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 10.90 KB | None | 0 0
raw download clone embed print report
  1. #!/usr/bin/env python
  2.  
  3. import sys
  4.  
  5. class Lexer:
  6.  
  7.     BIN, OCT, HEX, DEC, REAL, LOGIC, VAR, IF, ELSE, WHILE,\
  8.         DO, FOR, TO, STEP, LBRA, RBRA, BEGIN, END,\
  9.         LPAR, RPAR, PLUS, MINUS, DIZ, MUL, DIV, KON, LESS,\
  10.         GREATER, LEQ, GEQ,\
  11.         EQUAL, NEQUAL, INV, SEMICOLON, EOF = range(16)
  12.  
  13.     WORDS = { 'if': IF, 'else': ELSE, 'do': DO, 'while': WHILE, 'for': FOR, 'to': TO, 'step': STEP,\
  14.                   'begin': LBRA, 'end': RBRA, ';': SEMICOLON, '(': LPAR, ')': RPAR,\
  15.                   '+': PLUS, '-': MINUS, '||': DIZ, '*': MUL, '/': DIV, '&&': KON,\
  16.                   '==': EQUAL, '!=': NEQUAL, '<': LESS, '>': GREATER,\
  17.                   '<=': LEQ, '>=': GEQ, '!': INV }
  18.     LOGICS = { 'true': 1, 'false': 0 }
  19.  
  20.     ch = ' ' # assume the first char is a space
  21.  
  22.     def error(self, msg):
  23.         print 'Lexer error: ', msg
  24.         sys.exit(1)
  25.  
  26.     def getc(self):
  27.             self.ch = sys.stdin.read(1)
  28.  
  29.     def next_tok(self):
  30.             self.value = None
  31.             self.sym = None
  32.             while self.sym == None:
  33.                 if self.ch.isspace():
  34.                     self.getc()
  35.                 elif self.ch.isdigit() or self.ch == '.':
  36.                     strval = ' '
  37.                     while self.ch.isdigit() or (self.ch in ['a', 'b', 'c', 'd', 'e', 'f']) or\
  38.                             self.ch == '.' or strval[-1] == 'e' and (self.ch in ['+', '-']):
  39.                         strval += self.ch.lower()
  40.                         self.getc()
  41.                     if (strval.find('.') != -1 or strval.find('e+') != -1 or strval.find('e-') != -1):
  42.                         self.value = float(strval)
  43.                         self.sym = REAL
  44.                     elif (strval[-1] == 'h'):
  45.                         self.value = int(strval[:-1], 16)
  46.                         self.sym = HEX
  47.                     elif (strval[-1] == 'o'):
  48.                         self.value = int(strval[:-1], 8)
  49.                         self.sym = OCT
  50.                     elif (strval[-1] == 'b'):
  51.                         self.value = int(strval[:-1], 2)
  52.                         self.sym = BIN
  53.                     elif (strval[-1].isdigit()):
  54.                         self.value = int(strval)
  55.                         self.sym = DEC
  56.                     else:
  57.                         self.error('Unknown specificator of type: ' + strval[-1]);
  58.                 elif self.ch.isalpha():
  59.                     ident = ''
  60.                     while self.ch.isalpha() or self.ch in ['>', '<', '!', '=', ';', '&', '|', '*', '+', '-', '/', ')', '(']:
  61.                         ident = ident + self.ch.lower()
  62.                         self.getc()
  63.                     if ident in Lexer.WORDS:
  64.                         self.sym = Lexer.WORDS[ident]
  65.                     elif ident in Lexer.LOGICS:
  66.                         self.sym = Lexer.LOGIC
  67.                         self.value = Lexer.LOGICS[ident]
  68.                     else:
  69.                         self.sym = Lexer.VAR
  70.                         self.value = ident
  71.                 else:
  72.                     self.error('Unexpected symbol: ' + self.ch)
  73.  
  74. class Node:
  75.     def __init__(self, kind, value = None, op1 = None, op2 = None, op3 = None):
  76.         self.kind = kind
  77.         self.value = value
  78.         self.op1 = op1
  79.         self.op2 = op2
  80.         self.op3 = op3
  81.  
  82. class Parser:
  83.  
  84.     VAR, CONST, ADD, SUB, LT, SET, IF1, IF2, WHILE, DO, EMPTY, SEQ, EXPR, PROG = range(14)
  85.  
  86.     def __init__(self, lexer):
  87.         self.lexer = lexer
  88.  
  89.     def error(self, msg):
  90.             print 'Parser error:', msg
  91.             sys.exit(1)
  92.  
  93.     def term(self):
  94.             if self.lexer.sym == Lexer.ID:
  95.                 n = Node(Parser.VAR, self.lexer.value)
  96.                 self.lexer.next_tok()
  97.                 return n
  98.             elif self.lexer.sym == Lexer.NUM:
  99.                 n = Node(Parser.CONST, self.lexer.value)
  100.                 self.lexer.next_tok()
  101.                 return n
  102.             else:
  103.                 return self.paren_expr()
  104.  
  105.     def summa(self):
  106.             n = self.term()
  107.             while self.lexer.sym == Lexer.PLUS or self.lexer.sym == Lexer.MINUS:
  108.                 if self.lexer.sym == Lexer.PLUS:
  109.                     kind = Parser.ADD
  110.                 else:
  111.                     kind = Parser.SUB
  112.                     self.lexer.next_tok()
  113.                     n = Node(kind, op1 = n, op2 = self.term())
  114.         return n
  115.  
  116.     def test(self):
  117.             n = self.summa()
  118.             if self.lexer.sym == Lexer.LESS:
  119.                 self.lexer.next_tok()
  120.                 n = Node(Parser.LT, op1 = n, op2 = self.summa())
  121.         return n
  122.  
  123.     def expr(self):
  124.             if self.lexer.sym != Lexer.ID:
  125.                 return self.test()
  126.             n = self.test()
  127.             if n.kind == Parser.VAR and self.lexer.sym == Lexer.EQUAL:
  128.                 self.lexer.next_tok()
  129.                 n = Node(Parser.SET, op1 = n, op2 = self.expr())
  130.         return n
  131.  
  132.     def paren_expr(self):
  133.             if self.lexer.sym != Lexer.LPAR:
  134.                 self.error('"(" expected')
  135.         self.lexer.next_tok()
  136.         n = self.expr()
  137.         if self.lexer.sym != Lexer.RPAR:
  138.                     self.error('")" expected')
  139.         self.lexer.next_tok()
  140.         return n
  141.  
  142.     def statement(self):
  143.             if self.lexer.sym == Lexer.IF:
  144.                 n = Node(Parser.IF1)
  145.                 self.lexer.next_tok()
  146.                 n.op1 = self.paren_expr()
  147.                 n.op2 = self.statement()
  148.                 if self.lexer.sym == Lexer.ELSE:
  149.                     n.kind = Parser.IF2
  150.                     self.lexer.next_tok()
  151.                     n.op3 = self.statement()
  152.         elif self.lexer.sym == Lexer.WHILE:
  153.                     n = Node(Parser.WHILE)
  154.                     self.lexer.next_tok()
  155.                     n.op1 = self.paren_expr()
  156.                     n.op2 = self.statement();
  157.         elif self.lexer.sym == Lexer.DO:
  158.                     n = Node(Parser.DO)
  159.                     self.lexer.next_tok()
  160.                     n.op1 = self.statement()
  161.                     if self.lexer.sym != Lexer.WHILE:
  162.                         self.error('"while" expected')
  163.             self.lexer.next_tok()
  164.             n.op2 = self.paren_expr()
  165.             if self.lexer.sym != Lexer.SEMICOLON:
  166.                             self.error('";" expected')
  167.         elif self.lexer.sym == Lexer.SEMICOLON:
  168.                     n = Node(Parser.EMPTY)
  169.                     self.lexer.next_tok()
  170.         elif self.lexer.sym == Lexer.LBRA:
  171.                     n = Node(Parser.EMPTY)
  172.                     self.lexer.next_tok()
  173.                     while self.lexer.sym != Lexer.RBRA:
  174.                         n = Node(Parser.SEQ, op1 = n, op2 = self.statement())
  175.             self.lexer.next_tok()
  176.         else:
  177.                     n = Node(Parser.EXPR, op1 = self.expr())
  178.                     if self.lexer.sym != Lexer.SEMICOLON:
  179.                         self.error('";" expected')
  180.             self.lexer.next_tok()
  181.         return n
  182.  
  183.     def parse(self):
  184.             self.lexer.next_tok()
  185.             node = Node(Parser.PROG, op1 = self.statement())
  186.             if (self.lexer.sym != Lexer.EOF):
  187.                 self.error("Invalid statement syntax")
  188.         return node
  189.  
  190. IFETCH, ISTORE, IPUSH, IPOP, IADD, ISUB, ILT, JZ, JNZ, JMP, HALT = range(11)
  191.  
  192. class Compiler:
  193.  
  194.     program = []
  195.     pc = 0
  196.  
  197.     def gen(self, command):
  198.         self.program.append(command)
  199.         self.pc = self.pc + 1
  200.  
  201.     def compile(self, node):
  202.             if node.kind == Parser.VAR:
  203.                 self.gen(IFETCH)
  204.                 self.gen(node.value)
  205.             elif node.kind == Parser.CONST:
  206.                 self.gen(IPUSH)
  207.                 self.gen(node.value)
  208.             elif node.kind == Parser.ADD:
  209.                 self.compile(node.op1)
  210.                 self.compile(node.op2)
  211.                 self.gen(IADD)
  212.             elif node.kind == Parser.SUB:
  213.                 self.compile(node.op1)
  214.                 self.compile(node.op2)
  215.                 self.gen(ISUB)
  216.             elif node.kind == Parser.LT:
  217.                 self.compile(node.op1)
  218.                 self.compile(node.op2)
  219.                 self.gen(ILT)
  220.             elif node.kind == Parser.SET:
  221.                 self.compile(node.op2)
  222.                 self.gen(ISTORE)
  223.                 self.gen(node.op1.value)
  224.             elif node.kind == Parser.IF1:
  225.                 self.compile(node.op1)
  226.                 self.gen(JZ); addr = self.pc; self.gen(0);
  227.                 self.compile(node.op2)
  228.                 self.program[addr] = self.pc
  229.             elif node.kind == Parser.IF2:
  230.                 self.compile(node.op1)
  231.                 self.gen(JZ); addr1 = self.pc; self.gen(0)
  232.                 self.compile(node.op2)
  233.                 self.gen(JMP); addr2 = self.pc; self.gen(0)
  234.                 self.program[addr1] = self.pc
  235.                 self.compile(node.op3)
  236.                 self.program[addr2] = self.pc
  237.             elif node.kind == Parser.WHILE:
  238.                 addr1 = self.pc
  239.                 self.compile(node.op1)
  240.                 self.gen(JZ); addr2 = self.pc; self.gen(0)
  241.                 self.compile(node.op2)
  242.                 self.gen(JMP); self.gen(addr1);
  243.                 self.program[addr2] = self.pc
  244.             elif node.kind == Parser.DO:
  245.                 addr = self.pc
  246.                 self.compile(node.op1)
  247.                 self.compile(node.op2)
  248.                 self.gen(JNZ);
  249.                 self.gen(addr);
  250.             elif node.kind == Parser.SEQ:
  251.                 self.compile(node.op1)
  252.                 self.compile(node.op2)
  253.             elif node.kind == Parser.EXPR:
  254.                 self.compile(node.op1);
  255.                 self.gen(IPOP)
  256.             elif node.kind == Parser.PROG:
  257.                 self.compile(node.op1);
  258.                 self.gen(HALT)
  259.         return self.program
  260.  
  261. class VirtualMachine:
  262.  
  263.     def run(self, program):
  264.         var = [0 for i in xrange(26)]
  265.         stack = []
  266.         pc = 0
  267.         while True:
  268.             op = program[pc]
  269.             if pc < len(program) - 1:
  270.                 arg = program[pc+1]
  271.  
  272.                 if op == IFETCH: stack.append(var[arg]); pc += 2
  273.                 elif op == ISTORE: var[arg] = stack.pop(); pc += 2
  274.                 elif op == IPUSH: stack.append(arg); pc += 2
  275.                 elif op == IPOP: stack.append(arg); stack.pop(); pc += 1
  276.                 elif op == IADD: stack[-2] += stack[-1]; stack.pop(); pc += 1
  277.                 elif op == ISUB: stack[-2] -= stack[-1]; stack.pop(); pc += 1
  278.                 elif op == ILT:
  279.                     if stack[-2] < stack[-1]:
  280.                         stack[-2] = 1
  281.                     else:
  282.                         stack[-2] = 0
  283.                         stack.pop(); pc += 1
  284.                 elif op == JZ:
  285.                     if stack.pop() == 0:
  286.                         pc = arg
  287.                     else:
  288.                         pc += 2
  289.                 elif op == JNZ:
  290.                     if stack.pop() != 0:
  291.                         pc = arg
  292.                     else:
  293.                         pc += 2
  294.                 elif op == JMP: pc = arg;
  295.                 elif op == HALT: break
  296.  
  297.         print 'Execution finished.'
  298.         for i in xrange(26):
  299.                     if var[i] != 0:
  300.                         print '%c = %d' % (chr(i+ord('a')), var[i])
  301.  
  302.  
  303. l = Lexer()
  304. p = Parser(l)
  305.  
  306. ast = p.parse()
  307.  
  308. c = Compiler()
  309. program = c.compile(ast)
  310.  
  311. vm = VirtualMachine()
  312. vm.run(program)
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!