lisp.py

#! /usr/bin/env python3

class Atom:
    def __init__(self, typ, val):
        self.typ = typ
        self.val = val

    def __repr__(self):
        r = None
        if self.typ == "string":
            r = f'"{self.val}"'
        else:
            r = str(self.val)
        return f"atom(type={self.typ}, val={r})"


class Parser:
    def __init__(self, text):
        self.text = text
        self.idx = 0

    def debug_context(self):
        print(self.text[self.idx :])

    def parse(self):
        return self.expr()

    def eat(self):
        c = self.text[self.idx]
        self.idx += 1
        return c

    def slurp(self, c):
        while self.match(c):
            pass

    def force_match(self, c):
        if self.peek() != c:
            raise Exception(f"Expected {c} but got {text[0]}")
        self.eat()

    def match(self, c):
        is_match = self.test(c)
        if is_match:
            self.eat()
        return is_match

    def test(self, c):
        if isinstance(c, list):
            return any(self.peek() == ch for ch in c)
        return self.peek() == c

    def peek(self):
        return self.text[self.idx]

    def atom(self):
        if self.match('"'):
            s = ""
            while not self.test(['"']):
                s += self.eat()
            self.force_match('"')
            return Atom("string", s)
        if self.peek().isnumeric():
            i = ""
            while not self.test([" ", ")"]):
                c = self.eat()
                if c.isalpha():
                    raise Exception("Identifier cannot start with digits")
                i += c
            return Atom("number", int(i))
        elif self.peek() in ["+", "-", "/", "*"]:
            c = self.eat()
            self.force_match(" ")
            return Atom("op", c)
        else:
            ident = ""
            while not self.test([" ", ")"]):
                c = self.eat()
                if not c.isalnum():
                    raise Exception(f"Identifier: {ident} must be alphanumeric")
                ident += c
            return Atom("sym", ident)

    def expr(self):
        self.force_match("(")
        ast = []
        while not self.test(")"):
            self.slurp(" ")
            if self.test(")"):
                break

            if self.test("("):
                ast.append(self.expr())
            else:
                ast.append(self.atom())
        self.force_match(")")
        return ast


if __name__ == "__main__":
    parser = Parser('(first (list 1 (+ 2 3) 9 "a"))')
    ast = parser.parse()
    print(str(ast))