Simple Expressions: Code

import parser, tokenizer

def evaluate(ast):
    if ast["tag"] == "number":
        return ast["value"]
    elif ast["tag"] == "+":
        return evaluate(ast["left"]) + evaluate(ast["right"])
    elif ast["tag"] == "-":
        return evaluate(ast["left"]) - evaluate(ast["right"])
    elif ast["tag"] == "unary-":
        return -evaluate(ast["operand"])
    elif ast["tag"] == "*":
        return evaluate(ast["left"]) * evaluate(ast["right"])
    elif ast["tag"] == "/":
        return evaluate(ast["left"]) / evaluate(ast["right"])
    else:
        raise ValueError(f"Unknown AST node: {ast}")

def test_evaluate():
    print("test evaluate()")
    ast = {"tag": "number", "value": 3}
    assert evaluate(ast) == 3
    ast = {
        "tag": "+",
        "left": {"tag": "number", "value": 3},
        "right": {"tag": "number", "value": 4},
    }
    assert evaluate(ast) == 7
    ast = {
        "tag": "*",
        "left": {
            "tag": "+",
            "left": {"tag": "number", "value": 3},
            "right": {"tag": "number", "value": 4},
        },
        "right": {"tag": "number", "value": 5},
    }
    assert evaluate(ast) == 35
    tokens = tokenizer.tokenize("3*(4+5)")
    ast, tokens = parser.parse_expression(tokens)
    assert evaluate(ast) == 27
    tokens = tokenizer.tokenize("-1.5+2")
    ast, tokens = parser.parse_expression(tokens)
    assert evaluate(ast) == 0.5
    tokens = tokenizer.tokenize("3*-2")
    ast, tokens = parser.parse_expression(tokens)
    assert evaluate(ast) == -6

if __name__ == "__main__":
    test_evaluate()
    print("done.")

// Unary minus applies to 1.5; multiplication comes before addition.
-1.5+3*2 // The result is 4.5.

# parser.py

from tokenizer import tokenize
from pprint import pprint

# EBNF

#   expression ::= term { ("+" | "-") term }
#   term ::= unary { ("*" | "/") unary }
#   unary ::= "-" unary | factor
#   factor ::= <number> | "(" expression ")"


def parse_factor(tokens):
    """factor ::= <number>"""
    token = tokens[0]
    if token["tag"] == "number":
        node = {"tag": "number", "value": token["value"]}
        return node, tokens[1:]
    if token["tag"] == "(":
        node, tokens = parse_expression(tokens[1:])
        if tokens[0]["tag"] != ")":
            raise SyntaxError(f"Expected ')', got {tokens[0]}")
        return node, tokens[1:]
    raise SyntaxError(f"Expected expression, got {tokens[0]}")


def test_parse_factor():
    """factor ::= <number>"""
    print("test parse_factor()")
    tokens = tokenize("3")
    ast, tokens = parse_factor(tokens)
    assert ast == {"tag": "number", "value": 3}
    assert tokens == [{"tag": None, "line": 1, "column": 2}]
    tokens = tokenize("(3+4)")
    ast, tokens = parse_factor(tokens)
    assert ast == {'tag': '+', 'left': {'tag': 'number', 'value': 3}, 'right': {'tag': 'number', 'value': 4}} 
    assert tokens == [{'tag': None, 'line': 1, 'column': 6}]



def parse_unary(tokens):
    """unary ::= "-" unary | factor"""
    if tokens[0]["tag"] == "-":
        operand, tokens = parse_unary(tokens[1:])
        return {"tag": "unary-", "operand": operand}, tokens
    return parse_factor(tokens)


def test_parse_unary():
    """unary ::= "-" unary | factor"""
    print("test parse_unary()")
    tokens = tokenize("-3")
    ast, tokens = parse_unary(tokens)
    assert ast == {"tag": "unary-", "operand": {"tag": "number", "value": 3}}
    assert tokens == [{"tag": None, "line": 1, "column": 3}]
    tokens = tokenize("--3")
    ast, tokens = parse_unary(tokens)
    assert ast == {
        "tag": "unary-",
        "operand": {"tag": "unary-", "operand": {"tag": "number", "value": 3}},
    }
    assert tokens == [{"tag": None, "line": 1, "column": 4}]
    tokens = tokenize("-(3+4)")
    ast, tokens = parse_unary(tokens)
    assert ast == {
        "tag": "unary-",
        "operand": {
            "tag": "+",
            "left": {"tag": "number", "value": 3},
            "right": {"tag": "number", "value": 4},
        },
    }
    assert tokens == [{"tag": None, "line": 1, "column": 7}]


def parse_term(tokens):
    """term ::= unary { ("*" | "/") unary }"""
    left, tokens = parse_unary(tokens)
    while tokens[0]["tag"] in ["*", "/"]:
        op = tokens[0]["tag"]
        right, tokens = parse_unary(tokens[1:])
        left = {"tag": op, "left": left, "right": right}
    return left, tokens


def test_parse_term():
    """term ::= unary { ("*" | "/") unary }"""
    print("test parse_term()")
    tokens = tokenize("3")
    ast, tokens = parse_term(tokens)
    assert ast == {"tag": "number", "value": 3}
    assert tokens == [{"tag": None, "line": 1, "column": 2}]
    tokens = tokenize("3*4")
    ast, tokens = parse_term(tokens)
    assert ast == {
        "left": {"tag": "number", "value": 3},
        "right": {"tag": "number", "value": 4},
        "tag": "*",
    }
    assert tokens == [{"column": 4, "line": 1, "tag": None}]
    tokens = tokenize("3/4")
    ast, tokens = parse_term(tokens)
    assert ast == {
        "left": {"tag": "number", "value": 3},
        "right": {"tag": "number", "value": 4},
        "tag": "/",
    }
    assert tokens == [{"column": 4, "line": 1, "tag": None}]
    tokens = tokenize("3/4*5")
    ast, tokens = parse_term(tokens)
    assert ast == {
        "left": {
            "left": {"tag": "number", "value": 3},
            "right": {"tag": "number", "value": 4},
            "tag": "/",
        },
        "right": {"tag": "number", "value": 5},
        "tag": "*",
    }
    assert tokens == [{"column": 6, "line": 1, "tag": None}]
    tokens = tokenize("3*-2")
    ast, tokens = parse_term(tokens)
    assert ast == {
        "left": {"tag": "number", "value": 3},
        "right": {"tag": "unary-", "operand": {"tag": "number", "value": 2}},
        "tag": "*",
    }
    assert tokens == [{"column": 5, "line": 1, "tag": None}]


def parse_expression(tokens):
    """expression ::= term { ("+" | "-") term }"""
    left, tokens = parse_term(tokens)
    while tokens[0]["tag"] in ["+", "-"]:
        op = tokens[0]["tag"]
        right, tokens = parse_term(tokens[1:])
        left = {"tag": op, "left": left, "right": right}
    return left, tokens


def test_parse_expression():
    """expression ::= term { ("+" | "-") term }"""
    print("test parse_expression()")
    tokens = tokenize("3")
    ast, tokens = parse_expression(tokens)
    assert ast == {"tag": "number", "value": 3}
    assert tokens == [{"tag": None, "line": 1, "column": 2}]
    tokens = tokenize("3*4+5-6")
    ast, tokens = parse_expression(tokens)
    assert ast == {
        "left": {
            "left": {
                "left": {"tag": "number", "value": 3},
                "right": {"tag": "number", "value": 4},
                "tag": "*",
            },
            "right": {"tag": "number", "value": 5},
            "tag": "+",
        },
        "right": {"tag": "number", "value": 6},
        "tag": "-",
    }
    assert tokens == [{"column": 8, "line": 1, "tag": None}]
    tokens = tokenize("-1.5+2")
    ast, tokens = parse_expression(tokens)
    assert ast == {
        "left": {"tag": "unary-", "operand": {"tag": "number", "value": 1.5}},
        "right": {"tag": "number", "value": 2},
        "tag": "+",
    }
    assert tokens == [{"column": 7, "line": 1, "tag": None}]

def parse(tokens):
    ast, tokens = parse_expression(tokens)
    if tokens[0]["tag"] is not None:
        raise SyntaxError(f"Unexpected token: {tokens[0]}")
    return ast

if __name__ == "__main__":
    test_parse_factor()
    test_parse_unary()
    test_parse_term()
    test_parse_expression()
    print("done.")

import sys

from tokenizer import tokenize
from parser import parse
from evaluator import evaluate

if __name__ == "__main__":  
    if len(sys.argv) != 2:
        print("Usage: python runner.py <expression>")
        sys.exit(1)
    expression = sys.argv[1]
    if expression.endswith(".v") or expression.endswith(".t"):
        with open(expression, "r") as f:
            expression = f.read().strip()
    tokens = tokenize(expression)
    ast = parse(tokens)
    result = evaluate(ast)
    print(result)

import re
from pprint import pprint

patterns = [
    (r"\s+", "whitespace"),
    (r"//[^\r\n]*", "comment"),
    (r"\d*\.\d+|\d+\.\d*|\d+", "number"),
    (r"\+", "+"),
    (r"\-", "-"),
    (r"\/", "/"),
    (r"\*", "*"),
    (r"\(", "("),
    (r"\)", ")"),
    (r".", "error"),
]

patterns = [(re.compile(p), tag) for p, tag in patterns]


def tokenize(characters):
    "Tokenize a string using the patterns above"
    tokens = []
    position = 0
    line = 1
    column = 1
    current_tag = None

    while position < len(characters):
        for pattern, tag in patterns:
            match = pattern.match(characters, position)
            if match:
                current_tag = tag
                break
        assert match is not None
        value = match.group(0)

        if current_tag == "error":
            raise Exception(f"Unexpected character: {value!r}")

        if current_tag not in ("whitespace", "comment"):
            token = {"tag": current_tag, "line": line, "column": column}
            if current_tag == "number":
                if "." in value:
                    token["value"] = float(value)
                else:
                    token["value"] = int(value)
            tokens.append(token)

        # advance position and update line/column
        for ch in value:
            if ch == "\n":
                line += 1
                column = 1
            else:
                column += 1
        position = match.end()

    tokens.append({"tag": None, "line": line, "column": column})
    return tokens


def test_digits():
    print("test tokenize digits")
    t = tokenize("123")
    assert t[0]["tag"] == "number"
    assert t[0]["value"] == 123
    assert t[1]["tag"] is None
    t = tokenize("1")
    assert t[0]["tag"] == "number"
    assert t[0]["value"] == 1
    assert t[1]["tag"] is None


def test_floats():
    print("test tokenize floats")
    t = tokenize("12.5")
    assert t[0]["tag"] == "number"
    assert t[0]["value"] == 12.5
    assert t[1]["tag"] is None
    t = tokenize(".5")
    assert t[0]["tag"] == "number"
    assert t[0]["value"] == 0.5
    assert t[1]["tag"] is None
    t = tokenize("5.")
    assert t[0]["tag"] == "number"
    assert t[0]["value"] == 5.0
    assert t[1]["tag"] is None


def test_operators():
    print("test tokenize operators")
    t = tokenize("+ - * / ( )")
    tags = [token["tag"] for token in t]
    assert tags == ["+", "-", "*", "/", "(", ")", None]


def test_expressions():
    print("test tokenize expressions")
    t = tokenize("1+222*3")
    assert t[0]["tag"] == "number" and t[0]["value"] == 1
    assert t[1]["tag"] == "+"
    assert t[2]["tag"] == "number" and t[2]["value"] == 222
    assert t[3]["tag"] == "*"
    assert t[4]["tag"] == "number" and t[4]["value"] == 3
    assert t[5]["tag"] is None


def test_whitespace():
    print("test tokenize whitespace")
    t = tokenize("1 +\t2  \n*    3")
    assert t[0]["tag"] == "number" and t[0]["value"] == 1
    assert t[1]["tag"] == "+"
    assert t[2]["tag"] == "number" and t[2]["value"] == 2
    assert t[3]["tag"] == "*"
    assert t[4]["tag"] == "number" and t[4]["value"] == 3
    assert t[5]["tag"] is None


def test_comments():
    print("test tokenize comments")
    for ending in ("\n", "\r\n", "\r"):
        tokens = tokenize("8// ignored @ ; /" + ending + "/2")
        assert [token["tag"] for token in tokens] == ["number", "/", "number", None]
        assert tokens[0]["value"] == 8
        assert tokens[2]["value"] == 2
    for source in ("//", "// comment at end", "8 // trailing comment"):
        tokens = tokenize(source)
        if source.startswith("8"):
            expected_tags = ["number", None]
        else:
            expected_tags = [None]
        assert [token["tag"] for token in tokens] == expected_tags
        assert tokens[-1]["column"] == len(source) + 1
    tokens = tokenize("// first\n  8// second\r\n /2")
    assert (tokens[0]["line"], tokens[0]["column"]) == (2, 3)
    assert (tokens[1]["line"], tokens[1]["column"]) == (3, 2)
    assert [token["tag"] for token in tokenize("8/2")] == ["number", "/", "number", None]
    assert [token["tag"] for token in tokenize("/ /")] == ["/", "/", None]


def test_error():
    print("test tokenize error")
    try:
        tokenize("1@@@ +\t2  \n*    3")
    except Exception as e:
        assert str(e) == "Unexpected character: '@'"
        return
    raise Exception("Error did not happen.")


if __name__ == "__main__":
    test_digits()
    test_floats()
    test_operators()
    test_expressions()
    test_whitespace()
    test_comments()
    test_error()
    print("done.")

#!/usr/bin/env bash
exec python3 "$(dirname "$0")/runner.py" "$@"