Forem: sma

Lets build a simple interpreter from scratch in python, pt.11: Parser

sma — Tue, 04 Jul 2023 06:17:43 +0000

Simple parser in Python #02 - YouTube

Parsing assignments

youtube.com

Lets build a simple interpreter from scratch in python, pt.10: Tokenizer

sma — Mon, 19 Oct 2020 19:46:57 +0000

Coding a program using only recursive lists is very difficult and tedious. This kind of hard work must be done by computers. The first challenge we have to overcome is that we somehow transform human-readable program code into a structure that can be easily processed by the interpreter. Symbols, words, and values must be separated into small meaningful structures, which are called tokens. In this post we will convert this:

a=1;

to this:

[["name","a"], ["eq","="], ["number",1], ["semi",";"]]

["name","a"] is a token like [type, value] . We currently don't need to create a Token class for simplicity's sake.

Warning: The code below does not check for edge cases. It was written to reach the result as soon as possible instead of wasting time to trying to be idiomatic.
Lets try:

# We need a generator function that yields items of strings or lists:
def gen(xs):
    for x in xs:
        yield x

def tokenize(xs):
    isalpha=lambda x: (x>="a" and x<="z") or (x>="A" and x<="Z") or x=="_"
    reserved="function,set,get,print,return,if,else,for,while,break,continue".split(",")
    symbols={"(":"lparen",")":"rparen","{":"lcurly","}":"rcurly",",":"comma",";":"semi",
             "=":"equal"}
    g=gen(xs)
    i=next(g)
    tokens=[]
    buf=""
    try:
        while True:
            # Skip whitespace;
            while i in " \r\n\t":
                i=next(g);

            # Token starts with alphas ;
            if isalpha(i):
                # and continues with alphanumeric
                while isalpha(i) or i in "0123456789":
                    buf+=i
                    i=next(g)
                if buf in reserved:
                    tokens.append( [buf,buf] )
                else:
                    tokens.append( ["name",buf] )
                buf=""

            # We found a string;
            if i in "\"'":
                delimiter=i
                i=next(g)
                while i!=delimiter:
                    buf+=i
                    i=next(g)
                # Skip delimiter;
                i=next(g) 
                tokens.append( ["string",buf] )
                buf=""

            # We found a symbol;
            if i in "(){};=,":
                tokens.append( [symbols[i],i] )
                i=next(g)

            # We found a number;
            if i in "+-0123456789":
                while i in "+-0123456789.e":
                    buf+=i
                    i=next(g)
                if "e" in buf or "." in buf:
                    tokens.append( ["number",float(buf)] )
                else:
                    tokens.append( ["number",int(buf)] )
                buf=""

    except StopIteration:
        pass
    return tokens

# test it;
print(tokenize("if (gt(a,b)) return a; else return b;"))

output:

[['if', 'if'], ['lparen', '('], ['name', 'gt'], ['lparen', '('], ['name', 'a'], ['comma', ','], ['name', 'b'], ['rparen', ')'], ['rparen', ')'], ['return', 'return'], ['name', 'a'], ['semi', ';'], ['else', 'else'], ['return', 'return'], ['name', 'b'], ['semi', ';']]

It works :P

In the next post we will write a parser class that converts 'a=1;' to '["Set","a",1]'

Lets build a simple interpreter from scratch in python, pt.09: Function Call, Return

sma — Sat, 03 Oct 2020 20:57:08 +0000

In this post we are implementing Function, Call and Return:

# This is required for returning without primitives
class Empty:
    pass

class Interpreter:

    # Updated constructor for holding our functions

    def __init__(self):
        self.scope= [{}]
        self.loop_stack=[]
        self.funcs = {}

    #....(previous code)....

    # Updated to check if we returned or not
    def If(self,xs):
        _,cond,trueblock,elseblock=xs
        if self.eval(cond):
            if isinstance(trueblock[0],list):
                for x in trueblock:
                    self.eval(x)
                    # Return check
                    if "retval" in self.scope[-1]:
                        return                        
            else:
                self.eval(trueblock)
        else:
            if elseblock:
                if isinstance(elseblock[0],list):
                    for x in elseblock:
                        self.eval(x)
                        # Return check
                        if "retval" in self.scope[-1]:
                            return                        
                else:
                    self.eval(elseblock)



    # Updated:        
    def While(self,xs):
        self.loop_stack.append({"break":False,"continue":False})
        _ , cond , block = xs
        while self.eval(cond):
            if isinstance(block[0],list):
                for x in block:
                    self.eval(x)
                    # Return check
                    if "retval" in self.scope[-1]:
                        self.loop_stack.pop()
                        return                        
                    if self.loop_stack[-1]["break"]:
                        self.loop_stack.pop()
                        return
                    if self.loop_stack[-1]["continue"]:
                        self.loop_stack[-1]["continue"]=False
                        break
            else:
                self.eval(block)
        self.loop_stack.pop()

    # Updated:
    def For(self,xs):
        self.loop_stack.append({"break":False,"continue":False})        
        _, inits, cond, increments, block = xs
        for x in inits: 
            self.eval(x)
        while self.eval(cond):
            if isinstance(block[0],list):
                for x in block:
                    self.eval(x)
                    # Return check
                    if "retval" in self.scope[-1]:
                        self.loop_stack.pop()
                        return                                            
                    if self.loop_stack[-1]["break"]:
                        self.loop_stack.pop()
                        return
                    if self.loop_stack[-1]["continue"]:
                        self.loop_stack[-1]["continue"]=False
                        break
            else:
                self.eval(block) 
            for x in increments:
                self.eval(x)
        self.loop_stack.pop()

    #New: Define a function
    def Function(self,xs):
        _, name, params, block = xs
        self.funcs[name]={"params":params,"block":block}

    #New:
    def Return(self,xs):
        if len(self.scope)<2: # we are in global scope
            print("error: 'return' must be in function")
            exit(1)
        # Return with value
        if len(xs)>1:
            self.scope[-1]["retval"]=self.eval(xs[1])
        # Return without value
        else:
            self.scope[-1]["retval"]=Empty()

    # New:
    def Call(self,xs):
        _, funcname, params = xs
        # Before adding scope to scope list,
        scope={}
        func=self.funcs[funcname]
        # we must evaluate function params in current scope,
        for i,p in enumerate(func["params"]):
            scope[p]=self.eval(params[i])
        self.scope.append(scope)
        # now we are in new scope,
        for x in func["block"]:
            self.eval(x)
            if "retval" in self.scope[-1]:
                break
        retval=self.scope[-1]["retval"]
        self.scope.pop()
        return retval

code=[

    ["Function","fibonacci",["n"], [

        ["If",["Lte",["Get","n"],1], 
            ["Return",["Get","n"]],[]
        ],

        ["Return",
            ["Add",
                ["Call","fibonacci",[["Sub",["Get","n"],1]]],
                ["Call","fibonacci",[["Sub",["Get","n"],2]]]
            ]
        ]
    ]],

    ["Print","fibonacci(15) = ", ["Call","fibonacci",[15]]],

    ["Return"]
]

interpreter=Interpreter()

interpreter.run(code)

Output:

fibonacci(15) = 610
error: 'return' must be in function

Link to complete code.

Lets build a simple interpreter from scratch in python, pt.08: For loop

sma — Sat, 03 Oct 2020 19:46:28 +0000

In this post we are implementing the 'for' loop:

class Interpreter:
    def __init__(self):
        self.scope=[{}]
        self.loop_stack=[]

    # ...(previous code)...

    # 'For' loop is not much different from 'while' loop
    # for(inits; cond; increments) {block}

    def For(self,xs):
        self.loop_stack.append({"break":False,"continue":False})        
        _, inits, cond, increments, block = xs
        for x in inits: 
            self.eval(x)
        while self.eval(cond):
            if isinstance(block[0],list):
                for x in block:
                    self.eval(x)
                    if self.loop_stack[-1]["break"]:
                        self.loop_stack.pop()
                        return
                    if self.loop_stack[-1]["continue"]:
                        self.loop_stack[-1]["continue"]=False
                        break
            else:
                self.eval(block) 
            for x in increments:
                self.eval(x)
        self.loop_stack.pop()

code=[

    ["Set","sum",0],

    ["For", [["Set","i",0]], 
            ["Lt", ["Get","i"], 100], 
            [["Set","i", ["Add",["Get","i"], 1] ]],   
    [   

        ["Set","sum", ["Add",["Get", "sum"],["Get","i"]]],

        ["Print","i=",["Get","i"],", sum=",["Get","sum"]],

        ["If", ["Eq", ["Get", "i"], 10], 
             ["Break"],[]
        ],


    ]],

]

interpreter=Interpreter()

interpreter.run(code)

Output:

i=0, sum=0
i=1, sum=1
i=2, sum=3
i=3, sum=6
i=4, sum=10
i=5, sum=15
i=6, sum=21
i=7, sum=28
i=8, sum=36
i=9, sum=45
i=10, sum=55

Link to complete code.

Part 9: Function,Call,Return

Lets build a simple interpreter from scratch in python, pt.07: Break, Continue

sma — Sat, 03 Oct 2020 19:27:51 +0000

In this post we are implementing 'Break' and 'Continue':

class Interpreter:

    # Modified constructor:
    # loop_stack holds "break" and "continue" status of
    # inner loops:

    def __init__(self):
        self.scope=[{}]
        self.loop_stack=[]

    #....(previous code)....

    def Break(self,xs):
        self.loop_stack[-1]["break"]=True

    def Continue(self,xs):
        self.loop_stack[-1]["continue"]=True

    def While(self,xs):
        # New:
        self.loop_stack.append({"break":False,"continue":False})
        _ , cond , block = xs
        while self.eval(cond):
            if isinstance(block[0],list):
                for x in block:
                    # While evaluating block,
                    self.eval(x)
                    # If break is called, exit from python loop
                    if self.loop_stack[-1]["break"]:
                        self.loop_stack.pop()
                        return
                    # If continue is called, break this for loop :)
                    if self.loop_stack[-1]["continue"]:
                        self.loop_stack[-1]["continue"]=False
                        break
            else:
                self.eval(block)
        self.loop_stack.pop()


# This is AST, not for humans, this is for interpreters
# I think it is very readable :P

ast =[

    ["Set","i",0],

    ["While", ["Lt", ["Get","i"], 100], [
        ["Set","i",["Add",["Get","i"],1]],

        ["If", ["Eq", ["Get", "i"], 5], 
             ["Break"],[]
        ],
        ["Print",["Get","i"]],

    ]],

    ["Print",["Mul","-",40]],

    ["Set","i",0],

    ["While", ["Lt", ["Get","i"], 100], [       
        ["Set","i",["Add",["Get","i"],1]],

        ["If", ["Lt", ["Get", "i"], 95], 
             ["Continue"],[]
        ],
        ["Print",["Get","i"]],

    ]],    

    ["Print",["Mul","-",40]],

    ["Set","i",0],

    ["While", ["Lt", ["Get","i"], 100], [       

        ["Set","i",["Add",["Get","i"],1]],

        ["If", ["Gte", ["Get", "i"], 5], 
             ["Break"],[]
        ],        

        ["Set","j",0],

        ["While", ["Lt", ["Get","j"], 100], [       
            ["Set","j",["Add",["Get","j"],1]],

            ["If", ["Gte", ["Get", "j"], 5], 
                ["Break"],[]
            ],
            ["Print",["Mul",["Get","i"],["Get","j"]], ","],

        ]],

        ["Print"]

    ]],     
]

interpreter=Interpreter()

interpreter.run(ast)

Output:

1
2
3
4
----------------------------------------
95
96
97
98
99
100
----------------------------------------
1,2,3,4,
2,4,6,8,
3,6,9,12,
4,8,12,16,

Link to complete code.

Part 8: For loop

Lets build a simple interpreter from scratch in python, pt.06: While loop

sma — Sat, 03 Oct 2020 19:01:37 +0000

In this post we are implementing the 'while' loop:

class Interpreter:

    # ....(previous code)....

    def While(self,xs):
        _ , cond , block = xs
        while self.eval(cond):
            if isinstance(block[0],list):
                for x in block:
                    self.eval(x)
            else:
                self.eval(block)

code=[

    ["Set","sum",0],

    ["Set","i",0],

    ["While", ["Lt", ["Get","i"], 100], [

        ["Set","i", ["Add",["Get","i"], 1] ],
        ["Set","sum", ["Add",["Get", "sum"],["Get","i"]]]
    ]],

    ["Print","sum(1..100) = ",["Get","sum"] ]
]

interpreter=Interpreter()

interpreter.run(code)

Output:

sum(1..100) = 5050

Link to complete code: part6
Links: Patreon Twitter

Part 7: Break and Continue

Lets build a simple interpreter from scratch in python, pt.05: Defining variables

sma — Sat, 03 Oct 2020 18:43:18 +0000

In this post we are defining variables and using them:

class Interpreter:

    # Modified constructor: scope is list of dicts
    # First dict holds global variables, 
    # Last dict holds called function's scope variables

    def __init__(self):
        self.scope=[{}]

    # ....(previous code).... 

    # When we call Set we always create or update variable
    # in last scope: 

    def Set(self,xs):
        _, key, val = xs
        self.scope[-1][key] = self.eval(val)

    # When we call Get we first look into last scope(function scope),
    # if variable is not found then we look into first scope(globals)    
    def Get(self,xs):
        _, var = xs
        if var in self.scope[-1]:
            return self.scope[-1][var]
        elif var in self.scope[0]:
            return self.scope[0][var]
        raise Exception("error: variable not found: "+var)


code=[

    ["Set","answer",  ["Mul",6, 7],  ],
    ["Print", "Answer is: ", ["Get", "answer"] ]
]

interpreter=Interpreter()

interpreter.run(code)

Output:

Answer is: 42

Part 6: While loop

Lets build a simple interpreter from scratch in python, pt.04: Comparison functions

sma — Sat, 03 Oct 2020 18:19:52 +0000

In this post we are adding comparison functions to our interpreter:

class Interpreter:

    # .... previous code ....

    def Lt(self,xs):
        return self.eval(xs[1]) < self.eval(xs[2])
    def Gt(self,xs):
        return self.eval(xs[1]) > self.eval(xs[2])
    def Lte(self,xs):
        return not self.Gt(xs)
    def Gte(self,xs):
        return not self.Lt(xs)
    def Eq(self,xs):
        return self.eval(xs[1]) == self.eval(xs[2])
    def NotEq(self,xs):
        return not self.Eq(xs)

code=[

    ["If",["Lte",3,5],
       ["Print","3 <= 5"],
       ["Print","3 > 5"]   
    ],

    ["If",["NotEq",3,5],
       ["Print","3 != 5"],
       ["Print","3 == 5"]   
    ]   
]

interpreter=Interpreter()

interpreter.run(code)

Output:

3 <= 5
3 != 5

Part 5: Variables

Lets build a simple interpreter from scratch in python, pt.03: If/Else

sma — Sat, 03 Oct 2020 18:11:37 +0000

Bite sized posts are continuing. In this post we are implementing If keyword:

class Interpreter:

    # ... previous code ...

    def If(self,xs):
        _, cond, trueblock, falseblock = xs
        if self.eval(cond):
            if isinstance(trueblock[0],list):
                for x in trueblock:
                    self.eval(x)
            else:
                self.eval(trueblock)
        else:
            if falseblock:
                if isinstance(falseblock[0],list):
                    for x in falseblock:
                        self.eval(x)
                else:
                    self.eval(falseblock)
code=[

    ["If",True,
       # True block, 3 statements
       [["Print","answer is 42"],
        ["Print","that is 21*2"],
        ["Print","that is just an ordinary number"]],

       # False block
       ["Print","answer is something else"]   
    ],

    ["Print",["Mul","-",42]],

    ["If",False,
       ["Print","answer is 42"],
       ["Print","answer is something else"]   
    ]   
]

interpreter=Interpreter()

interpreter.run(code)

Output:

answer is 42
that is 21*2
that is just an ordinary number
------------------------------------------
answer is something else

Part 4: Comparison functions

Lets build a simple interpreter from scratch in python, pt.02 Basic Arithmetic

sma — Sat, 03 Oct 2020 17:28:09 +0000

There are many great tutorials about this subject on the internet written by clever people. Maybe my post will not be as great as them or academic style like them but i will always try to keep it simple as possible as. KISS

In this post we are adding basic arithmetic to our interpreter.

class Interpreter:
    def __init__(self):
        pass

    def run(self,code):
        for xs in code:
            self.eval(xs)

    def eval(self,xs):
        if isinstance(xs,list):
            return self.__getattribute__(xs[0])(xs)
        return xs

    def Print(self,xs):
        if len(xs)==1:
            print()
            return
        l=len(xs)-1
        for i,x in enumerate(xs[1:]):
            e=self.eval(x)
            if i<l-1:
                print(e,end="")
            else:
                if e!=",":
                    print(e)
                else:
                    print(e,end="")

    # Basic arithmetic operations,
    # Notice how we call self.eval function recursively:

    def Add(self,xs):
        return self.eval(xs[1])+self.eval(xs[2])
    def Sub(self,xs):
        return self.eval(xs[1])-self.eval(xs[2])
    def Mul(self,xs):
        return self.eval(xs[1])*self.eval(xs[2])
    def Div(self,xs):
        return self.eval(xs[1])/self.eval(xs[2])

code=[

    ["Print","3 + 5 = ", ["Add", 3, 5]  ],

    ["Print","1 - 2 * 3 = ", ["Sub", 1, ["Mul", 2, 3] ] ],

    ["Print",["Add", "Hello ", "again "],"W",["Mul","o",10],"rld!"],

]

interpreter=Interpreter()

interpreter.run(code)

Output:

3 + 5 = 8
1 - 2 * 3 = -5
Hello again Woooooooooorld!

Part 3: If/Else

Lets build a simple interpreter from scratch in python, pt.01

sma — Sat, 03 Oct 2020 15:54:53 +0000

Hi!.
In this blog series we will see that will i be sucessful or not in my attempt to build a programming language, an interpreter, a parser, a compiler and a virtual machine. For any questions starting with 'why' the answer is always 'why not?' except theese:

Why Python? Python lets you focus on problem rather than fighting with language itself.
Why not Rust? Rust is causing hair loss while fighting against it.
Why not C? It explodes many times in your hands. You lose your hands.

If code that i write is not idiomatic and tastefull for you please ignore it.
Lets get started.

class Interpreter:
    def __init__(self):
        pass

    def run(self,code):
        for xs in code:
            self.eval(xs)


    # This is our magic function. It evauates xs parameter 
    # according to its first element  and calls appropriate 
    # member function and passes the parameter to that function.
    # If xs is not a list then returns xs itself:

    def eval(self,xs):
        if isinstance(xs,list):
            return self.__getattribute__(xs[0])(xs)
        return xs


    # Our first function (or opcode) is Print. If last item 
    # is a comma it doesn't print newline:  

    def Print(self,xs):
        if len(xs)==1:
            print()
            return
        l=len(xs)-1
        for i,x in enumerate(xs[1:]):
            e=self.eval(x)
            if i<l-1:
                print(e,end="")
            else:
                if e!=",":
                    print(e)
                else:
                    print(e,end="")

# This is AST (Abstract Syntax Tree) generated by 
# parser. Consisting of recursive lists
# (No, not lisp :P )
code=[
    ["Print","Hello World!","Sky is blue"],
    ["Print",1,","],
    ["Print",2,","],
    ["Print",3],
    ["Print","a"],
    ["Print","b"],
    ["Print"],
    ["Print","c"],
]

interpreter=Interpreter()

interpreter.run(code)

Output is:

Hello World!Sky is blue
1,2,3
a
b

c

Part 2: Basic Arithmetic Functions