关于抽象语法树的简易实现 最后更新时间：2024年10月29日 ### 简介 在计算机科学中，抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法架构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真是语法中出现的每个细节。比如嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；二类似于 if-condition-then这样的条件跳转语句，可以使用带有三个分支的节点来表示。 和抽象语法树相对的是具体语法树（通常称作分析树）。一般的，在源代码的翻译和编译过程中，语法分析器创建出分析树，然后从分析树生成AST。一旦AST被创建出来，在后续的处理过程中，比如语义分析阶段，会添加一些信息。 ### 思路与流程  语法树通过循环的方式持续从队列中消耗token，通过判断token的类型来进行相关的执行。 消耗token完毕，构造成一课语法树后，通过执行器进行相应的处理。 ### 示例：  这课示例树展示了一个1+2-3的计算过程。 ### 示例代码： ```python class Token: """Token 简单的token对象 预定token只有add和number两种类型 """ def __init__(self,type:str,lexeme:str,literal:object, line:int) : self.type = type; self.lexeme = lexeme; self.literal = literal; self.line = line; def __str__ (self): return f"({self.type}, {self.lexeme}, {self.literal}, {self.line})" class TokenQueue: """ token队列 一个简易的token队列，用于构建，添加和消费token """ tokens:list[Token] = list current:int = 0 def __init__(self,tokens:list[Token]) -> None: self.tokens = tokens self.current = 0 # 判断token队列是否结束 def isAtEnd(self) -> bool: return self.peek().type == "EOF" # 取当前未消费token def peek(self) -> Token: return self.tokens[self.current] # 取当前已消费或正在消费token def previous(self) -> Token: return self.tokens[self.current-1] # 消费token def advence(self) -> Token: if not self.isAtEnd(): self.current+=1 return self.previous() # 判断当前未消费token是否符合需求token类型 def match(self,*types) -> bool: for type in types: if self.check(type): self.advence() return True return False # 断当前未消费token是否符合需求token类型 def check(self,type:str)->bool: if self.isAtEnd(): return False return self.peek().type == type # 消费符合token类型的队列 def consume(self,type:str): if self.peek().type == type: self.advence() return True return False class Express: """一个简易的表达式 用于解析和处理树的结果 """ def __init__(self):... def accept(self):... class Literal(Express): """字面量表达式 """ def __init__(self, value): self.value:Token = value def __str__(self) -> str: return f"(literal, {self.value})" def accept(self): print(f"(literal, {self.value})") return self.value class Binary(Express): """二元表达式 """ def __init__(self, left,operator,right): self.left:Express = left self.operator:Token = operator self.right:Express = right def accept(self): print(f"(Binary, [{self.operator.lexeme}] ,left {self.left}, right {self.right})") # 这里直接实现了执行器的工作 if self.operator.lexeme == "add": data = self.left.accept() + self.right.accept() elif self.operator.lexeme == "mul": data = self.left.accept() - self.right.accept() return data class Parser: """解析器 用于解析token，通过表达式构造一棵语法树 """ def __init__(self, token_queue:TokenQueue): self.token_queue:TokenQueue = token_queue def parse(self): try: return self.expression() except Exception: raise Exception("错误操作！") def expression(self): return self.add() def add(self): experss = self.literal() while self.token_queue.match("add","mul"): # 这里通过循环，连续不断地判断连续计算。同时起到消费token的作用 operator:Token = self.token_queue.previous() right = self.literal() experss = Binary(experss,operator,right) return experss def literal(self): if self.token_queue.match("Number"): return Literal(self.token_queue.previous().literal) else: raise Exception("错误！请输入正确的字面量！（1-9）") if __name__ == "__main__": """ 构造token和token队列 """ a1 = Token("Number",1,1,0) add = Token("add","add","add",0) a2 = Token("Number",2,2,0) mul = Token("mul","mul","mul",0) a3 = Token("Number",4,4,0) eof = Token("EOF","EOF","EOF",0) token_list = [a1,add,a2,mul,a3,eof] # 打印token for token in token_list: print(token) token_queue = TokenQueue(token_list) """ 构造语法树 """ parser = Parser(token_queue) expression = parser.parse() """ 执行语法树 """ data = expression.accept() print(data) ``` 执行结果： ```shell (Number, 1, 1, 0) (add, add, add, 0) (Number, 2, 2, 0) (mul, mul, mul, 0) (Number, 4, 4, 0) (EOF, EOF, EOF, 0) (Binary, [mul] ,left <__main__.Binary object at 0x0000017AF90A1DE0>, right (literal, 4)) (Binary, [add] ,left (literal, 1), right (literal, 2)) (literal, 1) (literal, 2) (literal, 4) -1 ```
Comments | NOTHING