造个轮子用Python写个编程语言函数与基本数据结构实现-每日运维

前言

okey,经过一段时间的努力，接下来要实现的是函数。当然还有对应的基本数据结构，那么之后的话，我们的工作就开始进一步转换了。

那么在这块我们要实现的有：

函数的定义

String类型的实现

列表类型的实现

实话实话，这个的实现是相当简陋的。不过作为一个小模型，应该是够用了，后面可以尝试打磨一下这个细节，比如这个变量的管理，函数的管理等等。

那么这块先看到我们的实现效果：
在这里插入图片描述

okey,我们开始吧。

语法表述

okey,现在的话，想要实现这个的话，我们需要先来看到我们的这个语法表述，前面我们一直在强调AST，因为这个玩意决定了，我们要如何愉快玩耍。

那么现在的话，我们来看到这个描述：

expr	    : KEYWORD:VAR IDENTIFIER EQ expr
		    : comp-expr ((KEYWORD:AND|KEYWORD:OR) comp-expr)*

comp-expr	: NOT comp-expr
			: arith-expr ((EE|LT|GT|LTE|GTE) arith-expr)*

arith-expr	: term ((PLUS|MINUS) term)*

term		: factor ((MUL|DIV) factor)*

factor		: (PLUS|MINUS) factor
			: power

power		: call (POW factor)*

call		: atom (LPAREN (expr (COMMA expr)*)? RPAREN)?

atom 		: INT|FLOAT|STRING|IDENTIFIER
			: LPAREN expr RPAREN
			: if-expr
			: for-expr
			: while-expr
			: func-def

if-expr		: KEYWORD:IF expr KEYWORD:THEN expr
			                (KEYWORD:ELIF expr KEYWORD:THEN expr)*
			                (KEYWORD:ELSE expr)?

for-expr	: KEYWORD:FOR IDENTIFIER EQ expr KEYWORD:TO expr
							(KEYWORD:STEP expr)? KEYWORD:THEN expr

while-expr	: KEYWORD:WHILE expr KEYWORD:THEN expr

func-def	: KEYWORD:FUN IDENTIFIER?
							LPAREN (IDENTIFIER (COMMA IDENTIFIER)*)? RPAREN
							ARROW expr

前面的都是老朋友，我们主要看到这个call,和func-def.
这两个家伙就是我们这个函数部分的操作。
这个和我们的变量实现一样，其实分两个部分，一个是函数本身的定义
例如Python的函数定义：

def add(a,b):

然后的话，是我们对函数的调用

add(a,b)

这里的话，其实是一样的。

所以的话，定义了这两个东西。

之后的话，我们来看到完整的描述：

expr：表示一个表达式。它可以是一个变量赋值表达式（以关键字 'VAR' 开头），或者是一个比较表达式 comp-expr，多个比较表达式之间可以使用逻辑运算符 'AND' 和 'OR' 进行连接。

comp-expr：表示一个比较表达式。它可以是一个逻辑非表达式（以关键字 'NOT' 开头），或者是一个算术表达式 arith-expr，多个算术表达式之间可以使用比较运算符进行比较。

arith-expr：表示一个算术表达式。它由一个项 term 开始，后面可以跟随多个加减运算符和项。

term：表示一个项。它由一个因子 factor 开始，后面可以跟随多个乘除运算符和因子。

factor：表示一个因子。它可以是正负号与另一个因子相乘的结果，或者是一个幂运算表达式 power。

power：表示一个幂运算表达式。它由一个函数调用 call 开始，后面可以跟随多个幂运算操作。

call：表示一个函数调用。它由一个原子表达式 atom 开始，后面可以跟随一对括号和多个参数表达式。

atom：表示一个原子表达式。它可以是整数、浮点数、字符串或标识符，也可以是一个被括号包裹的表达式，或者是一个 if 表达式、for 循环表达式、while 循环表达式或函数定义表达式。

if-expr：表示一个 if 表达式。它以关键字 'IF' 开头，后面跟随条件表达式、关键字 'THEN' 和对应的表达式。之后可以有零个或多个关键字 'ELIF'、条件表达式和关键字 'THEN' 和对应的表达式。最后可以有一个可选的关键字
'ELSE' 和对应的表达式。

for-expr：表示一个 for 循环表达式。它以关键字 'FOR' 开头，后面跟随循环变量、赋值运算符、起始值、关键字 'TO'、结束值，然后可以是可选的关键字 'STEP' 和步长值，最后是关键字 'THEN' 和对应的表达式。

while-expr：表示一个 while 循环表达式。它以关键字 'WHILE' 开头，后面跟随条件表达式，然后是关键字 'THEN' 和对应的表达式。

func-def：表示一个函数定义表达式。它以关键字 'FUN' 开头，后面可以是可选的标识符作为函数名称，然后是一对括号和多个参数标识符。最后是箭头符号和对应的表达式。

这样的话，就定义好了这个家伙。

解析器修改

okey,现在的话，开始来正式进入代码的编写部分。首先的话，毫无疑问的是，我们要做的是分为两个大部分，首先是对token词法解析的修改，然后是我们语法解析器的修改。当然这块的话我们就一起说了。

词法解析

首先，我们还是老规矩，去定义：


TT_INT = "整数"
TT_FLOAT = "浮点数"
TT_STRING = '字符串'
TT_PLUS = "加号"
TT_DIV = "除号"
TT_MINUS = "减号"
TT_LPAREN = "左括号"
TT_RPAREN = "右括号"
TT_POW	= '次幂'
TT_MUL = "乘"
TT_EOF = 'EOF'
TT_IDENTIFIER = '设变量'
TT_KEYWORD = '关键字'
TT_EQ = '赋值'
TT_EE = '等于'
TT_NE = '不等于'
TT_LT = '小于'
TT_GT = '大于'
TT_LTE = '小于等于'
TT_GTE = '大于等于'
TT_LSQUARE = '[括号'
TT_RSQUARE = ']括号'
TT_COMMA = '，号'
TT_ARROW = '-> 符号'

KEYWORDS = [
  'var',
  'and',
  'or',
  'not',
  'if',
  'elif',
  'else',
  'for',
  'to',
  'step',
  'while',
  'fun',
  'then'
]

可以看到，这个就是我们目前定义的关键字，还有对应的Token类型。

在解析器这里的话，我们要重新新增修改的代码不多，因为关键字匹配我们先前就是写好的，现在要做的只是匹配这个[]括号，主要是为了，处理这个列表变量。

当然还有这个：
在这里插入图片描述
这个家伙的话，可以去获取到我们的这个字符串，出现“ 这个符号的时候，我们就需要进行特殊处理了。

  def make_string(self):
        string = ''
        pos_start = self.pos.copy()
        escape_character = False
        self.advance()

        escape_characters = {
            'n': 'n',
            't': 't'
        }

        while self.current_char != None and (self.current_char != '"' or escape_character):
            if escape_character:
                string += escape_characters.get(self.current_char, self.current_char)
            else:
                if self.current_char == '\':
                    escape_character = True
                else:
                    string += self.current_char
            self.advance()
            escape_character = False

        self.advance()
        return Token(TT_STRING, string, pos_start, self.pos)

函数节点

那么同样的，我们要加入这个函数节点。
这里的话，我们有两个：

FuncDefNode 类表示函数定义的节点。它具有以下属性：

var_name_tok：函数名称的记号（Token）。
arg_name_toks：参数名称的记号列表。
body_node：函数体的节点。
pos_start：节点在源代码中的起始位置。如果存在函数名记号，
则起始位置为该记号的起始位置；如果不存在函数名记号但存在参数名记号，
则起始位置为第一个参数名记号的起始位置；否则起始位置为函数体节点的起始位置。
pos_end：节点在源代码中的结束位置，等于函数体节点的结束位置。

CallNode 类表示函数调用的节点。它具有以下属性：

node_to_call：被调用的函数节点。
arg_nodes：参数节点列表。
pos_start：节点在源代码中的起始位置，等于被调用函数节点的起始位置。
pos_end：节点在源代码中的结束位置。如果存在参数节点，
则结束位置为最后一个参数节点的结束位置；否则结束位置为被调用函数节点的结束位置。

class FuncDefNode:
  def __init__(self, var_name_tok, arg_name_toks, body_node):
    self.var_name_tok = var_name_tok
    self.arg_name_toks = arg_name_toks
    self.body_node = body_node

    if self.var_name_tok:
      self.pos_start = self.var_name_tok.pos_start
    elif len(self.arg_name_toks) > 0:
      self.pos_start = self.arg_name_toks[0].pos_start
    else:
      self.pos_start = self.body_node.pos_start

    self.pos_end = self.body_node.pos_end

class CallNode:
  def __init__(self, node_to_call, arg_nodes):
    self.node_to_call = node_to_call
    self.arg_nodes = arg_nodes

    self.pos_start = self.node_to_call.pos_start

    if len(self.arg_nodes) > 0:
      self.pos_end = self.arg_nodes[len(self.arg_nodes) - 1].pos_end
    else:
      self.pos_end = self.node_to_call.pos_en

函数节点解析

定义号函数节点之后的话，我们要做就是构建函数节点了，那么对于这个节点的处理，其实和我们的这个for循环，while 还有这个if的其实是类似的。
在这里插入图片描述

我们直接上代码吧，然后在注释里面说明：

    def func_def(self):
        res = ParseResult()
        # 当前节处理是函数节点，检查有没有fun关键字
        if not self.current_tok.matches(TT_KEYWORD, 'fun'):
            return res.failure(InvalidSyntaxError(
                self.current_tok.pos_start, self.current_tok.pos_end,
                f"Expected 'fun'"
            ))
	
        res.register_advancement()
        self.advance()
		
		# 处理函数的形式变量，也就是参数
		# 问：为什么可以检查到下一个节点
		# 答，算过了（狗头） 好吧是adanven这个函数，它会滑动，
		# 这里面的话register其实是递归调用了，所以，前面结束之后，拿到的一定
		# 就是符合语法规范的下一个token
        if self.current_tok.type == TT_IDENTIFIER:
            var_name_tok = self.current_tok
            res.register_advancement()
            self.advance()
            #检查左括号
            if self.current_tok.type != TT_LPAREN:
                return res.failure(InvalidSyntaxError(
                    self.current_tok.pos_start, self.current_tok.pos_end,
                    f"Expected '('"
                ))
        #没有参数
        else:
            var_name_tok = None
            if self.current_tok.type != TT_LPAREN:
                return res.failure(InvalidSyntaxError(
                    self.current_tok.pos_start, self.current_tok.pos_end,
                    f"Expected identifier or '('"
                ))

        res.register_advancement()
        self.advance()
        arg_name_toks = []
		# 处理参数
        if self.current_tok.type == TT_IDENTIFIER:
            arg_name_toks.append(self.current_tok)
            res.register_advancement()
            self.advance()
			#下一个参数逗号隔开
            while self.current_tok.type == TT_COMMA:
                res.register_advancement()
                self.advance()

                if self.current_tok.type != TT_IDENTIFIER:
                    return res.failure(InvalidSyntaxError(
                        self.current_tok.pos_start, self.current_tok.pos_end,
                        f"Expected identifier"
                    ))

                arg_name_toks.append(self.current_tok)
                res.register_advancement()
                self.advance()

            if self.current_tok.type != TT_RPAREN:
                return res.failure(InvalidSyntaxError(
                    self.current_tok.pos_start, self.current_tok.pos_end,
                    f"Expected ',' or ')'"
                ))
        # 没有参数了
        else:
            if self.current_tok.type != TT_RPAREN:
                return res.failure(InvalidSyntaxError(
                    self.current_tok.pos_start, self.current_tok.pos_end,
                    f"Expected identifier or ')'"
                ))

        res.register_advancement()
        self.advance()
	
        if self.current_tok.type != TT_ARROW:
            return res.failure(InvalidSyntaxError(
                self.current_tok.pos_start, self.current_tok.pos_end,
                f"Expected '->'"
            ))

        res.register_advancement()
        self.advance()
        node_to_return = res.register(self.expr())
        if res.error: return res
		# 完成参数节点定义，得到函数名，参数名（变量名）
        return res.success(FuncDefNode(
            var_name_tok,
            arg_name_toks,
            node_to_return
        ))

同样的，我们来看到call的实现。

    def call(self):
        res = ParseResult()
        atom = res.register(self.atom())
        if res.error: return res
		"""
		函数是可以有括号把里面的东西括起来的，就像这样：
		fun show()-> ( var b=3 )
		"""
        if self.current_tok.type == TT_LPAREN:
            res.register_advancement()
            self.advance()
            arg_nodes = []

            if self.current_tok.type == TT_RPAREN:
                res.register_advancement()
                self.advance()
            else:
                arg_nodes.append(res.register(self.expr()))
                if res.error:
                    return res.failure(InvalidSyntaxError(
                        self.current_tok.pos_start, self.current_tok.pos_end,
                        "Expected ')', 'var', 'if', 'for', 'while', 'fun', int, float, identifier, '+', '-', '(', '[' or 'not'"
                    ))

                while self.current_tok.type == TT_COMMA:
                    res.register_advancement()
                    self.advance()

                    arg_nodes.append(res.register(self.expr()))
                    if res.error: return res

                if self.current_tok.type != TT_RPAREN:
                    return res.failure(InvalidSyntaxError(
                        self.current_tok.pos_start, self.current_tok.pos_end,
                        f"Expected ',' or ')'"
                    ))

                res.register_advancement()
                self.advance()
             # 当前面的都执行完毕之后的话，我们的这个Call节点就ok了。
            return res.success(CallNode(atom, arg_nodes))
        return res.success(atom)

他们着两个的关系其实就是这样的：
在这里插入图片描述

List的解析实现

ok, 这里别忘了，我们还实现了我们的数据结构，String和List，所以这里的话，我们还要对这个两个家伙处理。不过这块的话，对于String的话其实没有什么特殊的，只需要解释的时候进行处理，但是对于List的话，因为这个家伙是有语法规则的，因此还需要单独处理。

 def list_expr(self):
        res = ParseResult()
        element_nodes = []
        pos_start = self.current_tok.pos_start.copy()

        if self.current_tok.type != TT_LSQUARE:
            return res.failure(InvalidSyntaxError(
                self.current_tok.pos_start, self.current_tok.pos_end,
                f"Expected '['"
            ))

        res.register_advancement()
        self.advance()

        if self.current_tok.type == TT_RSQUARE:
            res.register_advancement()
            self.advance()
        else:
            element_nodes.append(res.register(self.expr()))
            if res.error:
                return res.failure(InvalidSyntaxError(
                    self.current_tok.pos_start, self.current_tok.pos_end,
                    "Expected ']', 'var', 'if', 'for', 'while', 'fun', int, float, identifier, '+', '-', '(', '[' or 'not'"
                ))

            while self.current_tok.type == TT_COMMA:
                res.register_advancement()
                self.advance()

                element_nodes.append(res.register(self.expr()))
                if res.error: return res

            if self.current_tok.type != TT_RSQUARE:
                return res.failure(InvalidSyntaxError(
                    self.current_tok.pos_start, self.current_tok.pos_end,
                    f"Expected ',' or ']'"
                ))

            res.register_advancement()
            self.advance()

        return res.success(ListNode(
            element_nodes,
            pos_start,
            self.current_tok.pos_end.copy()
        ))

这里的话，我特意把注释删掉了，按照我们前面的套路，我想应该是可以把这个看明白的。

解释器

之后是我们的解释器。

节点

同样的在我们的解释器里面也有节点，这个节点，前面忘记说了，先前的话我只要Number这个节点，主要是因为当时我们只有这个对数学的基本运算，没有啥高级的操作，因此一个就够了，这个玩意就是用来存储运算结果的。

同样的，现在的话，操作复杂了，因此我们要做的事情就多了，所以的话，在这里我们有这些玩意：

（代码就不贴了，后面直接看到项目即可）

在这里：

Value类是所有其他类的基类，它定义了一些通用的方法和属性，例如set_pos()用于设置对象在源代码中的位置，set_context()用于设置对象的上下文环境。还有一些操作符方法，如added_to()、subbed_by()等，用于处理对象之间的加减乘除等操作。

String类继承自Value类，代表字符串类型的值。它重载了added_to()方法和multed_by()方法，实现了字符串的拼接和重复操作。is_true()方法判断字符串是否为真（即非空）。copy()方法用于创建String对象的副本。

List类也继承自Value类，代表列表类型的值。它重载了added_to()方法、subbed_by()方法、multed_by()方法和dived_by()方法，实现了列表的添加、删除、拼接和取元素操作。copy()方法用于创建List对象的副本。

Function类继承自Value类，代表函数类型的值。它包含函数的名称、函数体和参数名列表。execute()方法用于执行函数调用，将参数传递给函数，并在新的上下文环境中执行函数体。copy()方法用于创建Function对象的副本。

函数操作

我们先来看到我们的函数处理：
在我们的解释器部分有这个代码：
在这里插入图片描述
我们把这个函数相关的信息，进行组装，然后得到这个函数对象，然后通过函数对象进行操作。得到结果，或者运行函数里面的代码。
所以在这里的话，我们要重点看到这里，函数的执行代码：

可以看到，我们在这里的操作，是，我们得到了函数主体的入口节点，画图题可能是这样的：
在这里插入图片描述

我们的execute函数会拿到这个body,当然还有参数，然后我们让解释器，从这个body头节点开始执行

然后就是我们的局部参数，可以看到我们的代码在这里面：

        for i in range(len(args)):
            arg_name = self.arg_names[i]
            arg_value = args[i]
            arg_value.set_context(new_context)
            new_context.symbol_table.set(arg_name, arg_value)

我们把这个变量的值什么的都放在了函数内部的局部context里面，所以这个就是局部参数的由来，我们在这里面实现了变量的隔离。

okey,接下来我们看到这个完整代码：

    def execute(self, args):
        res = RTResult()
        interpreter = Interpreter()
        new_context = Context(self.name, self.context, self.pos_start)
        new_context.symbol_table = SymbolTable(new_context.parent.symbol_table)

        if len(args) > len(self.arg_names):
            return res.failure(RTError(
                self.pos_start, self.pos_end,
                f"{len(args) - len(self.arg_names)} too many args passed into '{self.name}'",
                self.context
            ))

        if len(args) < len(self.arg_names):
            return res.failure(RTError(
                self.pos_start, self.pos_end,
                f"{len(self.arg_names) - len(args)} too few args passed into '{self.name}'",
                self.context
            ))

        for i in range(len(args)):
            arg_name = self.arg_names[i]
            arg_value = args[i]
            arg_value.set_context(new_context)
            new_context.symbol_table.set(arg_name, arg_value)

        value = res.register(interpreter.visit(self.body_node, new_context))
        if res.error: return res
        return res.success(value)

String和List处理

接下来的话，就是String和List的处理，这里面的话没啥，直接看到代码就好了。

  def visit_StringNode(self, node, context):
        return RTResult().success(
            String(node.tok.value).set_context(context).set_pos(node.pos_start, node.pos_end)
        )

    def visit_ListNode(self, node, context):
        res = RTResult()
        elements = []

        for element_node in node.element_nodes:
            elements.append(res.register(self.visit(element_node, context)))
            if res.error: return res

        return res.success(
            List(elements).set_context(context).set_pos(node.pos_start, node.pos_end)
        )

总结

接下来的话，我们的实现就要到尾声了，当然接下来我们要处理的是这个，怎么和中文联系起来。先前我们一直做到的是中文，但是在后面，发现用中文实在是太啰嗦了，但是这个玩意的目标用户又是小学生，淦。

造个轮子用Python写个编程语言函数与基本数据结构实现

词法解析

函数节点

函数节点解析

List的解析实现

节点

函数操作

String和List处理

相关文章

发布评论取消回复

竹子爱熊猫

服务器开放端口，服务器开放端口的步骤

百度搜索：蓝易云 – docker部署jenkins修改登录会话超时时间教程

27 期 | 死锁（3）解决死锁

造个轮子用Python写个编程语言函数与基本数据结构实现

词法解析

函数节点

函数节点解析

List的解析实现

节点

函数操作

String和List处理

相关文章

发布评论 取消回复

竹子爱熊猫

服务器开放端口，服务器开放端口的步骤

百度搜索：蓝易云 – docker部署jenkins修改登录会话超时时间教程

27 期 | 死锁（3）解决死锁

发布评论取消回复