"""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