Prahaladha's picture
sync learned_computer: 75 files from /dev/shm/neucpu
30bd7c0 verified
Raw History Blame Contribute Delete
14.3 kB
"""TinyC: a small C subset compiled to Tiny8.
Supported: global byte variables and byte arrays (`int x = 3, a[10];` - every value is 0..255, wrapping), assignment and
compound assignment (= += -= *= /= %= &= |= ^=), ++ / --, if / else, while, for, break, continue, print(expr) (writes
the value to the output tape), input() (reads the next byte of the input tape), halt. Expressions: + - * / % & | ^,
<< >> by a constant, == != < > <= >= (unsigned), && || ! ~ unary -, parentheses, numbers, 'c' characters, a[i].
Registers r0..r5 hold expression temporaries by depth; variables live in RAM from address 0 up.
"""
import re
import tiny8
TOK = re.compile(r"\s*(?:(0x[0-9a-fA-F]+|\d+)|('.')|([A-Za-z_]\w*)|(==|!=|<=|>=|&&|\|\||<<|>>|\+\+|--|\+=|-=|\*=|/=|%=|&=|\|=|\^=|[-+*/%&|^~!<>=(){}\[\];,]))")
KEYWORDS = {"int", "char", "byte", "unsigned", "if", "else", "while", "for", "break", "continue", "print", "input", "halt"}
def tokenize(src):
src = re.sub(r"//[^\n]*", "", src)
src = re.sub(r"/\*.*?\*/", "", src, flags=re.S)
out, i = [], 0
while i < len(src):
if src[i:].strip() == "":
break
m = TOK.match(src, i)
if not m:
raise SyntaxError(f"bad character near: {src[i:i + 20]!r}")
num, ch, ident, op = m.groups()
out.append(("num", int(num, 0) & 255) if num else ("num", ord(ch[1]) & 255) if ch else ("id", ident) if ident else ("op", op))
i = m.end()
out.append(("eof", None))
return out
class Parser:
def __init__(self, toks):
self.t, self.i = toks, 0
def peek(self, k=0):
return self.t[self.i + k]
def eat(self, kind=None, val=None):
tk = self.t[self.i]
if (kind and tk[0] != kind) or (val is not None and tk[1] != val):
raise SyntaxError(f"expected {val or kind}, got {tk[1]!r}")
self.i += 1
return tk
def at(self, val):
return self.t[self.i][1] == val and self.t[self.i][0] in ("op", "id")
def program(self):
out = []
while self.peek()[0] != "eof":
out.append(self.stmt())
return out
def stmt(self):
if self.at("{"):
self.eat()
body = []
while not self.at("}"):
body.append(self.stmt())
self.eat()
return ("block", body)
if self.at("int") or self.at("char") or self.at("byte") or self.at("unsigned"):
while self.at("int") or self.at("char") or self.at("byte") or self.at("unsigned"):
self.eat()
decls = []
while True:
name = self.eat("id")[1]
size, init = None, None
if self.at("["):
self.eat()
size = self.eat("num")[1]
self.eat("op", "]")
if self.at("="):
self.eat()
init = self.expr()
decls.append((name, size, init))
if self.at(","):
self.eat()
continue
break
self.eat("op", ";")
return ("decl", decls)
if self.at("if"):
self.eat()
self.eat("op", "(")
c = self.expr()
self.eat("op", ")")
a = self.stmt()
b = None
if self.at("else"):
self.eat()
b = self.stmt()
return ("if", c, a, b)
if self.at("while"):
self.eat()
self.eat("op", "(")
c = self.expr()
self.eat("op", ")")
return ("while", c, self.stmt())
if self.at("for"):
self.eat()
self.eat("op", "(")
init = None if self.at(";") else self.simple()
self.eat("op", ";")
c = None if self.at(";") else self.expr()
self.eat("op", ";")
stp = None if self.at(")") else self.simple()
self.eat("op", ")")
return ("for", init, c, stp, self.stmt())
if self.at("break") or self.at("continue") or self.at("halt"):
k = self.eat()[1]
self.eat("op", ";")
return (k,)
if self.at("print"):
self.eat()
self.eat("op", "(")
e = self.expr()
self.eat("op", ")")
self.eat("op", ";")
return ("print", e)
s = self.simple()
self.eat("op", ";")
return s
def simple(self):
if self.at("++") or self.at("--"):
op = self.eat()[1]
lv = self.lvalue()
return ("assign", lv, ("bin", "+" if op == "++" else "-", lv, ("num", 1)))
lv = self.lvalue()
if self.at("++") or self.at("--"):
op = self.eat()[1]
return ("assign", lv, ("bin", "+" if op == "++" else "-", lv, ("num", 1)))
op = self.eat("op")[1]
e = self.expr()
if op == "=":
return ("assign", lv, e)
if op in ("+=", "-=", "*=", "/=", "%=", "&=", "|=", "^="):
return ("assign", lv, ("bin", op[0], lv, e))
raise SyntaxError(f"bad assignment operator {op}")
def lvalue(self):
name = self.eat("id")[1]
if self.at("["):
self.eat()
idx = self.expr()
self.eat("op", "]")
return ("idx", name, idx)
return ("var", name)
LEVELS = [["||"], ["&&"], ["|"], ["^"], ["&"], ["==", "!="], ["<", ">", "<=", ">="], ["<<", ">>"], ["+", "-"], ["*", "/", "%"]]
def expr(self, lvl=0):
if lvl == len(self.LEVELS):
return self.unary()
a = self.expr(lvl + 1)
while self.peek()[0] == "op" and self.peek()[1] in self.LEVELS[lvl]:
op = self.eat()[1]
b = self.expr(lvl + 1)
a = ("bin", op, a, b)
return a
def unary(self):
if self.peek()[0] == "op" and self.peek()[1] in ("-", "!", "~"):
op = self.eat()[1]
return ("un", op, self.unary())
return self.primary()
def primary(self):
tk = self.peek()
if tk[0] == "num":
self.eat()
return ("num", tk[1])
if self.at("input"):
self.eat()
self.eat("op", "(")
self.eat("op", ")")
return ("input",)
if self.at("("):
self.eat()
e = self.expr()
self.eat("op", ")")
return e
if tk[0] == "id":
return self.lvalue()
raise SyntaxError(f"unexpected {tk[1]!r}")
REL = {"<", ">", "<=", ">=", "==", "!="}
class Gen:
MAXD = 5 # expression temporaries r0..r5
def __init__(self):
self.code, self.vars, self.next_addr, self.nlab, self.loops = [], {}, 0, 0, []
def label(self, tag="L"):
self.nlab += 1
return f"{tag}{self.nlab}"
def emit(self, s):
self.code.append(s)
def var(self, name, size=None):
if name not in self.vars:
n = size or 1
if self.next_addr + n > 100: # 100..127 kept for the stack
raise ValueError("out of RAM for variables")
self.vars[name] = (self.next_addr, size)
self.next_addr += n
return self.vars[name]
def addr(self, name):
if name not in self.vars:
raise NameError(f"undeclared variable {name}")
return self.vars[name][0]
def reg(self, d):
if d > self.MAXD:
raise ValueError("expression too deep")
return f"r{d}"
# ---- expressions: result in r{d}
def expr(self, e, d):
r = self.reg(d)
k = e[0]
if k == "num":
self.emit(f"LDI {r}, {e[1] & 255}")
elif k == "var":
self.emit(f"LDA {r}, {self.addr(e[1])}")
elif k == "idx":
self.expr(e[2], d)
self.emit(f"ADDI {r}, {self.addr(e[1])}")
self.emit(f"LD {r}, {r}")
elif k == "input":
self.emit(f"IN {r}")
elif k == "un":
if e[1] == "-":
self.expr(e[2], d)
r2 = self.reg(d + 1)
self.emit(f"LDI {r2}, 0")
self.emit(f"SUB {r2}, {r}")
self.emit(f"MOV {r}, {r2}")
elif e[1] == "~":
self.expr(e[2], d)
r2 = self.reg(d + 1)
self.emit(f"LDI {r2}, 255")
self.emit(f"XOR {r}, {r2}")
else:
self.boolean(e, d)
elif k == "bin":
op, a, b = e[1], e[2], e[3]
if op in REL or op in ("&&", "||"):
self.boolean(e, d)
elif op in ("<<", ">>"):
if b[0] != "num":
raise ValueError("shift by a constant only")
self.expr(a, d)
for _ in range(min(b[1], 8)):
self.emit(f"{'SHL' if op == '<<' else 'SHR'} {r}")
else:
self.expr(a, d)
if op in ("+", "-") and b[0] == "num":
self.emit(f"{'ADDI' if op == '+' else 'SUBI'} {r}, {b[1] & 255}")
return
self.expr(b, d + 1)
name = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV", "%": "MOD", "&": "AND", "|": "OR", "^": "XOR"}[op]
self.emit(f"{name} {r}, {self.reg(d + 1)}")
else:
raise ValueError(f"bad expression {e}")
def boolean(self, e, d):
r = self.reg(d)
lf, le = self.label("F"), self.label("E")
self.jump(e, lf, False, d)
self.emit(f"LDI {r}, 1")
self.emit(f"JMP {le}")
self.emit(f"{lf}:")
self.emit(f"LDI {r}, 0")
self.emit(f"{le}:")
# ---- conditions: jump to `lab` when cond == want
def jump(self, e, lab, want, d=0):
if e[0] == "un" and e[1] == "!":
return self.jump(e[2], lab, not want, d)
if e[0] == "bin" and e[1] == "&&":
if want:
skip = self.label("S")
self.jump(e[2], skip, False, d)
self.jump(e[3], lab, True, d)
self.emit(f"{skip}:")
else:
self.jump(e[2], lab, False, d)
self.jump(e[3], lab, False, d)
return
if e[0] == "bin" and e[1] == "||":
if want:
self.jump(e[2], lab, True, d)
self.jump(e[3], lab, True, d)
else:
skip = self.label("S")
self.jump(e[2], skip, True, d)
self.jump(e[3], lab, False, d)
self.emit(f"{skip}:")
return
if e[0] == "bin" and e[1] in REL:
op, a, b = e[1], e[2], e[3]
ra, rb = self.reg(d), self.reg(d + 1)
if op in (">", "<="): # swap so the test is a borrow test on b - a
a, b = b, a
op = "<" if op == ">" else ">="
self.expr(a, d)
if b[0] == "num":
self.emit(f"CMPI {ra}, {b[1] & 255}")
else:
self.expr(b, d + 1)
self.emit(f"CMP {ra}, {rb}")
flag_true = {"<": "JC", ">=": "JNC", "==": "JZ", "!=": "JNZ"}[op]
flag_false = {"JC": "JNC", "JNC": "JC", "JZ": "JNZ", "JNZ": "JZ"}[flag_true]
self.emit(f"{flag_true if want else flag_false} {lab}")
return
self.expr(e, d)
self.emit(f"CMPI {self.reg(d)}, 0")
self.emit(f"{'JNZ' if want else 'JZ'} {lab}")
# ---- statements
def stmt(self, s):
k = s[0]
if k == "block":
for x in s[1]:
self.stmt(x)
elif k == "decl":
for name, size, init in s[1]:
self.var(name, size)
if init is not None:
self.expr(init, 0)
self.emit(f"STA r0, {self.addr(name)}")
elif k == "assign":
lv, e = s[1], s[2]
if lv[0] == "var":
self.expr(e, 0)
self.emit(f"STA r0, {self.addr(lv[1])}")
else:
self.expr(e, 0)
self.expr(lv[2], 1)
self.emit(f"ADDI r1, {self.addr(lv[1])}")
self.emit("ST r0, r1")
elif k == "print":
self.expr(s[1], 0)
self.emit("OUT r0")
elif k == "if":
lelse, lend = self.label("ELSE"), self.label("ENDIF")
self.jump(s[1], lelse, False)
self.stmt(s[2])
if s[3] is not None:
self.emit(f"JMP {lend}")
self.emit(f"{lelse}:")
if s[3] is not None:
self.stmt(s[3])
self.emit(f"{lend}:")
elif k == "while":
top, end = self.label("WTOP"), self.label("WEND")
self.emit(f"{top}:")
self.jump(s[1], end, False)
self.loops.append((top, end))
self.stmt(s[2])
self.loops.pop()
self.emit(f"JMP {top}")
self.emit(f"{end}:")
elif k == "for":
top, cont, end = self.label("FTOP"), self.label("FCONT"), self.label("FEND")
if s[1] is not None:
self.stmt(s[1])
self.emit(f"{top}:")
if s[2] is not None:
self.jump(s[2], end, False)
self.loops.append((cont, end))
self.stmt(s[4])
self.loops.pop()
self.emit(f"{cont}:")
if s[3] is not None:
self.stmt(s[3])
self.emit(f"JMP {top}")
self.emit(f"{end}:")
elif k == "break":
self.emit(f"JMP {self.loops[-1][1]}")
elif k == "continue":
self.emit(f"JMP {self.loops[-1][0]}")
elif k == "halt":
self.emit("HALT r0")
else:
raise ValueError(f"bad statement {s}")
def compile_c(src):
"""C source -> (ROM bytes, assembly lines). Raises on unsupported code or a program over 256 bytes."""
ast = Parser(tokenize(src)).program()
g = Gen()
for s in ast:
g.stmt(s)
g.emit("HALT")
asm = [x if x.endswith(":") else x.replace("HALT r0", "HALT") for x in g.code]
return tiny8.assemble(asm), asm