从RegExp开始搓一个简单的解释器

Fri Dec 01 2023

# 从RegExp开始搓一个简单的脚本语言

## Ez Regular Expression

来点简单的正则语法（ 可能也不会很简单，因为已经开始预查了（ 一些基本的语法就直接跳过（

### 预查

如果要匹配一个Matrix，但是不想匹配一个Matrix2，这个时候，就可以用预查来完成（

可以用向前预查Lookahead assertion，写成Matrix(?!2)，来匹配所有Matrix且下一个字符不是2的字串，肯定预查为Matrix(?=2)

有的时候，想匹配一个Number，但是不想匹配一个INumber，这个时候，也可以用预查来完成（

以上面的例子写regex，用向后预查Lookbehind assertion，可以写成(?<!I)Number,这会匹配所有Number且前一个字符不为I的字串

当然这是否定预查，也可以使用肯定预查(?<=I)Number，这会匹配所有Number且前一个字符为I的字串，注意，匹配到的字串不包括I

## 开搓！

### 创建venv

对的，用python搓一个，为什么用python呢，因为我懒。

python3 -m venv venv
. ./venv/bin/activate
pip install regex matplotlib

regex是解释器的核心之一，正则写的好，解释器就完成了一部分（ matplotlib是课程要求（因为要求是做一个能用来绘图的语言，所以直接用matplotlib

### 字面量的匹配

先定义一些字面量的类型，直接写成正则：

pattern_literal_string = re.compile(r'^\s*"([^"]*)"\s*')
pattern_literal_integer = re.compile(r"^\s*(\d+)(?![\d\.A-z])\s*")
pattern_literal_float = re.compile(r"^\s*(\d+\.\d*|\d*\.\d+)(?![\d\.A-z])\s*")
pattern_literal_boolean = re.compile(r"^\s*(true|false)(?![A-z\d_])\s*")
pattern_literal_null = re.compile(r"^\s*(null)(?![A-z0-9_])\s*")
pattern_literal_range = re.compile(r"\s*(\d+)\.\.(\d+)\s*")

要注意这里的正则限定了开头，但是没有限定末尾，所以一定要写好匹配的边界，不然可能会漏掉内容或者匹配到了额外的内容。然后就是写一个函数，来处理这些字面量：

def from_literal(token: str):
    if m := pattern_literal_string.match(token):
        return Var("string", m.group(1), const=True), m.end()
    elif m := pattern_literal_integer.match(token):
        return Var("integer", int(m.group(1)), const=True), m.end()
    elif m := pattern_literal_float.match(token):
        return Var("float", float(m.group(1)), const=True), m.end()
    elif m := pattern_literal_boolean.match(token):
        return Var("bool", m.group(1) == "true", const=True), m.end()
    elif m := pattern_literal_null.match(token):
        return Var("object", None, const=True), m.end()
    elif m := pattern_literal_range.match(token):
        return Var("range", (int(m.group(1)), int(m.group(2))), const=True), m.end()
    else:
        return None

这里会涉及到一个Var类型，定义如下：

class Var:
    runtime_type_bindings = {
    "string":"string",
    "int":"integer",
    "float":"float",
    "bool":"bool",
    "tuple":"tuple",
    "NoneType":"null"
}
    def asVar(val):
        if isinstance(val,Var):
            return val
        elif (typename := type(val).__name__) in Var.runtime_type_bindings:
            return Var(Var.runtime_type_bindings[typename],val)
        else:
            raise Exception(f"unknown type: {typename}")
    def unwrap(var:'Var'):
            if not isinstance(var,Var):
                return var
            if var.type == "tuple":
                return [Var.unwrap(i) for i in var.value]
            else:
                return var.value 
    def __init__(self,type,value,name=None,const=False) -> None:
        self.type = type
        self.value = value
        self.name = name
        self.const = const
    def __repr__(self) -> str:
        return f"[{"const" if self.const else "var"} {self.type}::{self.name if self.name else ""}]({self.value})"
    def __str__(self) -> str:
        return self.__repr__()
    def set(self,val):
        if self.const:
            raise Exception("const filed is immutable")
        if self.type == None:
            self.type = val.type
            self.value = val.value
            return
        if val.type != self.type:
            raise Exception(f"variable type mismatch: {self.type} != {val.type}")
        self.value = val.value
    def __eq__(self, __value: object) -> bool:
        if isinstance(__value,Var):
            return self.type == __value.value and self.value == __value.value
        return False
    def __call__(self, args: 'Var',ctx:list[dict]):
        if self.type != "function":
            raise Exception("not a function")
        args = Var.unwrap(args)
        retVal = self.value(ctx, args if isinstance(args,list) else [args])
        return Var.asVar(retVal)

这个Var其实就是一个wrapper，用来在运行时进行一些简单的类型检查（虽然写到后面直接开摆了），和引用在scope里面的Var对象，并修改所绑定的值

### 标识符和关键词和运算符

syntax_reserved_keywords = ["for", "in", "if", "else", "while", "break", "continue", "return"]
 
pattern_identifier = re.compile(r"^\s*([a-zA-Z_][a-zA-Z0-9_]*)\s*")
pattern_brance_open = re.compile(r"^\s*\(\s*")
pattern_brance_close = re.compile(r"^\s*\)\s*")
pattern_operators = re.compile(r"\s*([+\-\*/%=]|==|is)\s*")
pattern_comma = re.compile(r"^\s*,\s*")
pattern_keywords = re.compile(rf"^\s*({'|'.join(syntax_reserved_keywords)})\s*")

这里写了好几个关键词，但是其实只用到了for和in

以及写一下各个运算符所对于的函数：

def op_add(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value + b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value + b.value)
 
 
def op_sub(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value - b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value - b.value)
 
 
def op_mul(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value * b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value * b.value)
 
 
def op_div(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value / b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value / b.value)
 
 
def op_mod(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value % b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value % b.value)
 
 
def op_assign(operands, ctx):
    lval, rval = operands
    lval.set(rval)
    ctx[-1][lval.name] = lval
    return lval
 
 
def op_equal(operands, ctx):
    lval, rval = operands
    return Var("bool", lval == rval)
 
 
def op_is(operands, ctx):
    lval, rval = operands
    if lval.type == None:
        return op_assign(operands, ctx)
    else:
        return op_equal(operands, ctx)
 
 
operators_map = {
    "+": op_add,
    "-": op_sub,
    "*": op_mul,
    "/": op_div,
    "%": op_mod,
    "=": op_assign,
    "==": op_equal,
    "is": op_is,
}

### 开始解析表达式

def from_expression(expr: str):
    if pattern_comment.match(expr):
        return None
    if not (m := pattern_expression.match(expr)):
        return None
    expr = m.group(1)
    ops = []
    while len(expr):
        if brance_close := pattern_brance_close.match(expr):
            ops.append("brance_close")
            expr = expr[brance_close.end() :]
        elif brance_open := pattern_brance_open.match(expr):
            ops.append("brance_open")
            expr = expr[brance_open.end() :]
        elif keyword := pattern_keywords.match(expr):
            ops.append(("keyword", keyword.group(1)))
            expr = expr[keyword.end() :]
        elif operator := pattern_operators.match(expr):
            ops.append(("operator", operator.group(1)))
            expr = expr[operator.end() :]
        elif comma := pattern_comma.match(expr):
            ops.append("join")
            expr = expr[comma.end() :]
        elif identifier := pattern_identifier.match(expr):
            ops.append(("identifier", identifier.group(1)))
            expr = expr[identifier.end() :]
        elif literal := from_literal(expr):
            value, l = literal
            ops.append(("literal", value))
            expr = expr[l:]
        else:
            raise SyntaxError("invalid token: " + expr)
    stacks = []
    current = optree = []
    for op in ops:
        if op == "brance_open":
            current.append(new := [])
            stacks.append(current)
            current = new
        elif op == "brance_close":
            if len(current) > 1:
                new = []
                grouping = False
                for x in current:
                    if x == "join":
                        grouping = True
                    elif grouping:
                        if new[-1][0] == "group":
                            new[-1][1].append(x)
                        else:
                            new[-1] = ("group", [new[-1], x])
                    else:
                        new.append(x)
                current.clear()
                current.extend(new)
            current = stacks.pop()
            if len(current) > 1 and current[-2][0] == "identifier":
                current[-2] = ("call", current[-2], current[-1])
                current.pop()
        else:
            current.append(op)
        
    def parse(opt: list):
        if not opt:
            return None
        if isinstance(opt, tuple):
            if opt[0] == "call":
                return ("call", opt[1], parse(opt[2]))
            elif opt[0] == "group":
                return ("group",[parse(item) for item in opt[1]])
            return opt
        if not isinstance(opt, list):
            raise Exception(f"invalid opt: {opt}")
        if len(opt) == 1:
            return parse(opt[0])
        for i, o in enumerate(opt):
            if isinstance(o, list):
                opt[i] = parse(o)
        def match(*pattern: str):
            for op, p in zip(opt, pattern):
                if p == "**":
                    continue
                if not isinstance(op, tuple):
                    return False
                matched = False
                for p_ in p.split("|"):
              
        raise Exception(f"invalid expression")
 
    result = parse(optree)
    ptree(result)
    return result

### 表达式求值

def eval_expr(expr, ctx):
    if not expr or not (type := expr[0]):
        return None
    if len(expr) == 1:
        return eval_expr(expr[0],ctx)
    # debug("\n==========context============")
    # for scope in ctx:
    #     for val in scope.values():
    #         debug(val)
    # debug("=========expression==========\n", expr, "\n==========output=============")
    if type == "literal":
        return expr[1]
    elif type == "identifier":
        for scope in reversed(ctx):
            if expr[1] in scope:
                return scope[expr[1]]
        return Var(None, None, expr[1])
    elif type == "group":
        val = Var("tuple",[eval_expr(i, ctx) for i in expr[1]],const=True)
        # debug("eval group", expr[1],val)
        return val
    elif type == "func":
        F,A = expr[1:]
        args = [eval_expr(i, ctx) for i in A]
        return F(args, ctx)
    elif type == "call":
        F, A = expr[1:]
        func, args = eval_expr(F, ctx), eval_expr(A,ctx)
        # debug("eval call",func,args)
        return func(args, ctx)
    elif type == "for":
        I, A, B = expr[1:]
        iterVar = Var("integer", 0, name=I[1])
        range_begin, range_end = A[1].value
        ctx[-1][iterVar.name] = iterVar
        for i in range(range_begin, range_end):
            iterVar.value = i
            eval_expr(B, ctx)
    else:
        raise Exception(f"invalid expression: {expr}")

写两个方便debug的函数

# region debug utils
def debug(*args,**kwargs):
 print("debug::",*args,**kwargs)
 
def ptree(subtree,depth=0,split="--"):
 if depth == 0:
     print("")
     print(subtree)
     print("==========parse tree==========")
 for i in subtree:
     if isinstance(i,list):
         ptree(i,depth+1)
     elif isinstance(i,tuple):
         print(f"[{depth}]:|"+split*depth,[x if not isinstance(x,list) else "<list>" for x in i])
         for x in i:
             if isinstance(x,list):
                 ptree(x,depth+1)
     else:
         print(f"[{depth}]:|"+split*depth,i)
## endregion

### 测试功能

from syntax import *
from math import atan2, sin, cos, sqrt, tan
from matplotlib import pyplot as plt
 
points = []
 
ctx = [{}]
 
 
@func_import(ctx, "print")
def myprint(*a, ctx=None):
    print("***myprint***", *a)
 
 
@func_import(ctx, "sin")
def mysin(args, ctx=None):
    return sin(args[0])
 
 
@func_import(ctx, "cos")
def mycos(args, ctx=None):
    return cos(args[0])
 
 
@func_import(ctx, "tan")
def mytan(args, ctx=None):
    return tan(args[0])
 
 
@func_import(ctx, "draw")
def mydraw(args, ctx=None):
    x, y = args
    offset_x, offset_y = ctx("origin")
    scale_x, scale_y = ctx("scale")
    rot = ctx("rot")
    x, y = x * scale_x, y * scale_y
    r = sqrt(x * x + y * y)
    theta = atan2(y, x) + rot
    x = r * cos(theta) + offset_x
    y = r * sin(theta) + offset_y
    points.append((x, y))
 
 
@func_import(ctx, "plot")
def myplot(args, ctx=None):
    plt.scatter(*zip(*points))
    plt.show()
 
 
for statement in """
1+1+1+1+1+1+1+1+1+1+1+1
origin is (1, 1); 设置原点的偏移量
rot is 0.5; -- 设置旋转角度
scale is (0.1, 12); 设置横坐标和纵坐标的比例
print("origin is", origin, ", rot is", rot, ", scale is", scale); 输出当前设置的参数
for T in 0..1000 draw(T,((sin((T*0.01))+1)+(cos((T*0.01))*cos((T*0.01))))); 从0到1000，每次增加1
plot()
""".splitlines():
    # debug("statement:", statement)
    result = eval_expr(from_expression(statement), ctx)
    # debug("result:",result)

it works

## 具体代码分析

摸了

## 改进方向

  1. 加入流程控制
  2. 优化运算符的解析，支持更复杂的表达式

# 实验报告版（大部分内容相同，只是为了模板改了改）

## 1. 总体任务

题目：为函数绘图语言编写一个解释器，解释器接受用绘图语言编写的源程序，经语法和语义分析之后，将源程序所规定的图形显示在显示屏（或窗口）中。 目的：通过自己动手编写解释器，掌握语言翻译特别是语言识别的基本方法

  1. 会使用正则表达式设计简单的语法
  2. 会用递归下降子程序编写编译器或解释器
  3. 会写报告

## 2. 函数绘图语言简介

### 2.1 运算符

  1. +, -, *, /, %: 基本算数运算
  2. =: 赋值运算
  3. ==: 判断相等
  4. is: 当lval未定义类型时，将rval的赋给lval; 当lval已定义类型时，判断lval与rval是否相等

### 2.2 基本类型

#### 2.2.1 字面量类型
  1. string: 字符串类型，运行时内部类型为str e.g. "some string"
  2. integer: 整数类型，运行时内部类型为int e.g. 114
  3. float: 浮点数类型，运行时内部类型为float e.g. 114.514
  4. bool: boolean类型，运行时内部类型为bool e.g. true or false
  5. range: range类型，运行时内部类型为tuple[int, int] e.g. 0..1919 从0到1919（不包含）的整数序列
    1. 作为for表达式的范围参数时会进行自动推导成generator，a..b会被推导为range(a,b)
#### 2.2.2 内部类型
  1. tuple: 元组，用于函数调用参数和定义复杂结构，由，表达式生成（在作为函数参数的时候，嵌套的元组会被自动压平成一维列表）
  2. function: 函数，目前只支持使用@func_import导入python函数，暂不支持自定义函数

### 2.3 基本语法

  1. 注释：;
  2. 标识符：/[A-z_][A-z0-9_]*/
  3. 定义变量：<varname> = <value> or <varname> is <value>
  4. 基本运算符：<lval> <op> <rval>
  5. 元组定义：<tuple> = (<value1>, <value2>, ...)
  6. 函数调用：<funcname>(<arg1>, <arg2>, ...)
  7. for循环：for <loop_var> in <iterable> <expression>

### 2.4 变量

  1. 变量具有作用域，在搜索时从当前上下文向上搜索
  2. 变量可以由字面量或运行时导入产生，这个时候的变量是immutable，不可以修改值
  3. 变量可以由赋值运算符产生，这个时候的变量可以修改值

### 2.5 内置函数

解释器后端是python，可以使用@func_importdecorator在特定上下文中导入python函数

  1. print: 打印 print("scale is", scale)
  2. draw: 添加点 draw(1, 1)
    1. draw函数会使用当前上下文中的origin, scale, rot三个变量
  3. plot: 绘图 plot()
  4. sin: 正弦函数 sin(1)
  5. cos: 余弦函数 cos(1)
  6. tan: 正切函数 tan(1)

### 2.6 绘图函数

绘图函数涉及三个全局变量：

  1. origin: 原点偏移量 origin is (1, 1)
  2. rot: 旋转角度 rot is 0.5
  3. scale: 横纵坐标比例 scale is (0.1, 12)

draw函数接受x，y两个参数，在调用时，会对坐标进行变换操作，然后将变换后的坐标添加到散点列表中，坐标变换公式如下：

x, y = x * scale_x, y * scale_y
r = sqrt(x * x + y * y)
theta = atan2(y, x) + rot
x = r * cos(theta) + offset_x
y = r * sin(theta) + offset_y

plot函数调用时，会将散点列表使用matplotlib绘制出来，并显示窗口，阻塞当前线程

## 3. 函数绘图程序举例

origin is (1, 1); 设置原点的偏移量
rot is 0.5; -- 设置旋转角度
scale is (0.1, 12); 设置横坐标和纵坐标的比例
print("origin is", origin, ", rot is", rot, ", scale is", scale); 输出当前设置的参数
for T in 0..1000 draw(T,((sin((T*0.01))+1)+(cos((T*0.01))*cos((T*0.01))))); 从0到1000，每次增加1
plot(); 绘图

## 4. 开发环境及配置

  1. Operating System: Fedora Workstation 39
  2. Python version：3.12.0
  3. IDE: Visual Studio Code (Language server: Pylance)

使用的Python包：

  1. regex: python内置的正则表达式包
  2. matplotlib: 绘图包

## 5. 基本原理与解决思路

解释器运行逻辑：

  1. 初始化解释器上下文，加载内置函数
  2. 读入所有源代码文件，按\n拆分成多个statements，逐行分析
  3. 使用正则表达式循环匹配当前行，生成指令序列
    1. 记未分析的字符串为expr，初始化指令序列ops为空
    2. 使用正则表达式匹配expr，如果匹配成功，将匹配到的内容加入ops，并将expr被匹配到的部分截断
    3. 循环直至expr为空或者无法匹配，抛出异常，终止解释器
  4. 根据指令序列生成指令图
    1. 初始化栈stacks为空，当前帧为current，指令图optree指向current，即图的根节点
    2. 遍历指令序列ops
      1. 如果当前指令为brance_open，将current压入栈stacks，创建新的帧new，将new加入current，并将current置为new
      2. 如果当前指令为brance_close，将current中的join操作进行解析，生成group指令，弹出stacks栈顶，并将current置为弹出的栈顶元素，初步处理函数调用
      3. 如果当前指令不是brance_open或brance_close或join，将当前指令加入current
  5. 从指令图递归生成表达式
    1. 如果当前节点为group，递归生成子表达式，将子节点加入group的子表达式参数列表
    2. 如果当前节点为call，递归生成子表达式，将子节点加入call的子表达式参数列表
    3. 如果当前节点为原子表达式，直接返回
    4. 如果当前表达式为运算符表达式，递归生成左右子表达式，将左右子表达式加入运算符表达式的参数列表
    5. 如果当前表达式为for循环表达式，递归生成循环变量、迭代器、循环体，将循环变量、迭代器、循环体加入for循环表达式的参数列表
    6. 如果当前表达式无法匹配，抛出异常，终止解释器
  6. 在当前上下文中求值表达式
    1. 如果当前表达式为字面量，返回字面量的运行时引用
    2. 如果当前表达式为标识符，从当前上下文向上搜索，返回第一个匹配的变量
    3. 如果当前表达式为元组，递归求值子表达式，返回元组
    4. 如果当前表达式为函数调用，递归求值子表达式，返回函数调用结果
    5. 如果当前表达式为for循环，递归求值循环变量、迭代器、循环体，对每次循环修改当前ctx中绑定的迭代变量，并对循环体表达式求值，返回空
    6. 如果当前表达式无法匹配，抛出异常，终止解释器

## 6. 关键类及主要方法

### 字面量的匹配

先定义一些字面量的类型，直接写成正则：

pattern_literal_string = re.compile(r'^\s*"([^"]*)"\s*')
pattern_literal_integer = re.compile(r"^\s*(\d+)(?![\d\.A-z])\s*")
pattern_literal_float = re.compile(r"^\s*(\d+\.\d*|\d*\.\d+)(?![\d\.A-z])\s*")
pattern_literal_boolean = re.compile(r"^\s*(true|false)(?![A-z\d_])\s*")
pattern_literal_null = re.compile(r"^\s*(null)(?![A-z0-9_])\s*")
pattern_literal_range = re.compile(r"\s*(\d+)\.\.(\d+)\s*")

要注意这里的正则限定了开头，但是没有限定末尾，所以一定要写好匹配的边界，不然可能会漏掉内容或者匹配到了额外的内容。然后就是写一个函数，来处理这些字面量：

def from_literal(token: str):
    if m := pattern_literal_string.match(token):
        return Var("string", m.group(1), const=True), m.end()
    elif m := pattern_literal_integer.match(token):
        return Var("integer", int(m.group(1)), const=True), m.end()
    elif m := pattern_literal_float.match(token):
        return Var("float", float(m.group(1)), const=True), m.end()
    elif m := pattern_literal_boolean.match(token):
        return Var("bool", m.group(1) == "true", const=True), m.end()
    elif m := pattern_literal_null.match(token):
        return Var("object", None, const=True), m.end()
    elif m := pattern_literal_range.match(token):
        return Var("range", (int(m.group(1)), int(m.group(2))), const=True), m.end()
    else:
        return None

这里会涉及到一个Var类型，定义如下：

class Var:
    runtime_type_bindings = {
    "string":"string",
    "int":"integer",
    "float":"float",
    "bool":"bool",
    "tuple":"tuple",
    "NoneType":"null"
}
    def asVar(val):
        if isinstance(val,Var):
            return val
        elif (typename := type(val).__name__) in Var.runtime_type_bindings:
            return Var(Var.runtime_type_bindings[typename],val)
        else:
            raise Exception(f"unknown type: {typename}")
    def unwrap(var:'Var'):
            if not isinstance(var,Var):
                return var
            if var.type == "tuple":
                return [Var.unwrap(i) for i in var.value]
            else:
                return var.value 
    def __init__(self,type,value,name=None,const=False) -> None:
        self.type = type
        self.value = value
        self.name = name
        self.const = const
    def __repr__(self) -> str:
        return f"[{"const" if self.const else "var"} {self.type}::{self.name if self.name else ""}]({self.value})"
    def __str__(self) -> str:
        return self.__repr__()
    def set(self,val):
        if self.const:
            raise Exception("const filed is immutable")
        if self.type == None:
            self.type = val.type
            self.value = val.value
            return
        if val.type != self.type:
            raise Exception(f"variable type mismatch: {self.type} != {val.type}")
        self.value = val.value
    def __eq__(self, __value: object) -> bool:
        if isinstance(__value,Var):
            return self.type == __value.value and self.value == __value.value
        return False
    def __call__(self, args: 'Var',ctx:list[dict]):
        if self.type != "function":
            raise Exception("not a function")
        args = Var.unwrap(args)
        retVal = self.value(ctx, args if isinstance(args,list) else [args])
        return Var.asVar(retVal)

这个Var其实就是一个wrapper，用来在运行时进行一些简单的类型检查（虽然写到后面直接开摆了），和引用在scope里面的Var对象，并修改所绑定的值

### 标识符和关键词和运算符

syntax_reserved_keywords = ["for", "in", "if", "else", "while", "break", "continue", "return"]
 
pattern_identifier = re.compile(r"^\s*([a-zA-Z_][a-zA-Z0-9_]*)\s*")
pattern_brance_open = re.compile(r"^\s*\(\s*")
pattern_brance_close = re.compile(r"^\s*\)\s*")
pattern_operators = re.compile(r"\s*([+\-\*/%=]|==|is)\s*")
pattern_comma = re.compile(r"^\s*,\s*")
pattern_keywords = re.compile(rf"^\s*({'|'.join(syntax_reserved_keywords)})\s*")

这里写了好几个关键词，但是其实只用到了for和in，其他关键字保留备用

以及写一下各个运算符所对于的函数：

def op_add(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value + b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value + b.value)
 
 
def op_sub(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value - b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value - b.value)
 
 
def op_mul(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value * b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value * b.value)
 
 
def op_div(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value / b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value / b.value)
 
 
def op_mod(operands, ctx):
    a, b = operands
    assert isinstance(a, Var) and isinstance(b, Var)
    if a.type == "integer" and b.type == "integer":
        return Var("integer", a.value % b.value)
    elif a.type == "float" or b.type == "float":
        return Var("float", a.value % b.value)
 
 
def op_assign(operands, ctx):
    lval, rval = operands
    lval.set(rval)
    ctx[-1][lval.name] = lval
    return lval
 
 
def op_equal(operands, ctx):
    lval, rval = operands
    return Var("bool", lval == rval)
 
 
def op_is(operands, ctx):
    lval, rval = operands
    if lval.type == None:
        return op_assign(operands, ctx)
    else:
        return op_equal(operands, ctx)
 
 
operators_map = {
    "+": op_add,
    "-": op_sub,
    "*": op_mul,
    "/": op_div,
    "%": op_mod,
    "=": op_assign,
    "==": op_equal,
    "is": op_is,
}

### 开始解析表达式

此处对应章节5中的3. 4. 5. 三部分

def from_expression(expr: str):
    if pattern_comment.match(expr):
        return None
    if not (m := pattern_expression.match(expr)):
        return None
    expr = m.group(1)
    ops = []
    while len(expr):
        if brance_close := pattern_brance_close.match(expr):
            ops.append("brance_close")
            expr = expr[brance_close.end() :]
        elif brance_open := pattern_brance_open.match(expr):
            ops.append("brance_open")
            expr = expr[brance_open.end() :]
        elif keyword := pattern_keywords.match(expr):
            ops.append(("keyword", keyword.group(1)))
            expr = expr[keyword.end() :]
        elif operator := pattern_operators.match(expr):
            ops.append(("operator", operator.group(1)))
            expr = expr[operator.end() :]
        elif comma := pattern_comma.match(expr):
            ops.append("join")
            expr = expr[comma.end() :]
        elif identifier := pattern_identifier.match(expr):
            ops.append(("identifier", identifier.group(1)))
            expr = expr[identifier.end() :]
        elif literal := from_literal(expr):
            value, l = literal
            ops.append(("literal", value))
            expr = expr[l:]
        else:
            raise SyntaxError("invalid token: " + expr)
    stacks = []
    current = optree = []
    for op in ops:
        if op == "brance_open":
            current.append(new := [])
            stacks.append(current)
            current = new
        elif op == "brance_close":
            if len(current) > 1:
                new = []
                grouping = False
                for x in current:
                    if x == "join":
                        grouping = True
                    elif grouping:
                        if new[-1][0] == "group":
                            new[-1][1].append(x)
                        else:
                            new[-1] = ("group", [new[-1], x])
                    else:
                        new.append(x)
                current.clear()
                current.extend(new)
            current = stacks.pop()
            if len(current) > 1 and current[-2][0] == "identifier":
                current[-2] = ("call", current[-2], current[-1])
                current.pop()
        else:
            current.append(op)
        
    def parse(opt: list):
        if not opt:
            return None
        if isinstance(opt, tuple):
            if opt[0] == "call":
                return ("call", opt[1], parse(opt[2]))
            elif opt[0] == "group":
                return ("group",[parse(item) for item in opt[1]])
            return opt
        if not isinstance(opt, list):
            raise Exception(f"invalid opt: {opt}")
        if len(opt) == 1:
            return parse(opt[0])
        for i, o in enumerate(opt):
            if isinstance(o, list):
                opt[i] = parse(o)
        def match(*pattern: str):
            for op, p in zip(opt, pattern):
                if p == "**":
                    continue
                if not isinstance(op, tuple):
                    return False
                matched = False
                for p_ in p.split("|"):
              
        raise Exception(f"invalid expression")
 
    result = parse(optree)
    ptree(result)
    return result

### 表达式求值

def eval_expr(expr, ctx):
    if not expr or not (type := expr[0]):
        return None
    if len(expr) == 1:
        return eval_expr(expr[0],ctx)
    # debug("\n==========context============")
    # for scope in ctx:
    #     for val in scope.values():
    #         debug(val)
    # debug("=========expression==========\n", expr, "\n==========output=============")
    if type == "literal":
        return expr[1]
    elif type == "identifier":
        for scope in reversed(ctx):
            if expr[1] in scope:
                return scope[expr[1]]
        return Var(None, None, expr[1])
    elif type == "group":
        val = Var("tuple",[eval_expr(i, ctx) for i in expr[1]],const=True)
        # debug("eval group", expr[1],val)
        return val
    elif type == "func":
        F,A = expr[1:]
        args = [eval_expr(i, ctx) for i in A]
        return F(args, ctx)
    elif type == "call":
        F, A = expr[1:]
        func, args = eval_expr(F, ctx), eval_expr(A,ctx)
        # debug("eval call",func,args)
        return func(args, ctx)
    elif type == "for":
        I, A, B = expr[1:]
        iterVar = Var("integer", 0, name=I[1])
        range_begin, range_end = A[1].value
        ctx[-1][iterVar.name] = iterVar
        for i in range(range_begin, range_end):
            iterVar.value = i
            eval_expr(B, ctx)
    else:
        raise Exception(f"invalid expression: {expr}")

### 初始化运行时上下文和测试代码

from syntax import *
from math import atan2, sin, cos, sqrt, tan
from matplotlib import pyplot as plt
 
points = []
 
ctx = [{}]
 
 
@func_import(ctx, "print")
def myprint(*a, ctx=None):
    print("***myprint***", *a)
 
 
@func_import(ctx, "sin")
def mysin(args, ctx=None):
    return sin(args[0])
 
 
@func_import(ctx, "cos")
def mycos(args, ctx=None):
    return cos(args[0])
 
 
@func_import(ctx, "tan")
def mytan(args, ctx=None):
    return tan(args[0])
 
 
@func_import(ctx, "draw")
def mydraw(args, ctx=None):
    x, y = args
    offset_x, offset_y = ctx("origin")
    scale_x, scale_y = ctx("scale")
    rot = ctx("rot")
    x, y = x * scale_x, y * scale_y
    r = sqrt(x * x + y * y)
    theta = atan2(y, x) + rot
    x = r * cos(theta) + offset_x
    y = r * sin(theta) + offset_y
    points.append((x, y))
 
 
@func_import(ctx, "plot")
def myplot(args, ctx=None):
    plt.scatter(*zip(*points))
    plt.show()
 
 
for statement in """
1+1+1+1+1+1+1+1+1+1+1+1
origin is (1, 1); 设置原点的偏移量
rot is 0.5; -- 设置旋转角度
scale is (0.1, 12); 设置横坐标和纵坐标的比例
print("origin is", origin, ", rot is", rot, ", scale is", scale); 输出当前设置的参数
for T in 0..1000 draw(T,((sin((T*0.01))+1)+(cos((T*0.01))*cos((T*0.01))))); 从0到1000，每次增加1
plot()
""".splitlines():
    # debug("statement:", statement)
    result = eval_expr(from_expression(statement), ctx)
    # debug("result:",result)

## 7. 测试截图

主要代码已包含在上一节中，这里只展示运行结果

(自己截图)

## 8. 总体体会（遇到的问题与体会）

  1. 解释器运行过程中，尤其是进行语法分析和表达式求值的时候，会进行非常多递归操作，调试难度较大
  2. 把问题复杂化了，本次实验的语法点较少，且语法形式很单一，完全可以直接匹配特定字符串，但是为了拓展性做了很多workaround