简介
在计算机科学中，抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法架构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真是语法中出现的每个细节。比如嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；二类似于 if-condition-then这样的条件跳转语句，可以使用带有三个分支的节点来表示。 和抽象语法树相对的是具体语法树（通常称作分析树）。一般的，在源代码的翻译和编译过程中，语法分析器创建出分析树，然后从分析树生成AST。一旦AST被创建出来，在后续的处理过程中，比如语义分析阶段，会添加一些信息。
思路与流程
语法树通过循环的方式持续从队列中消耗token，通过判断token的类型来进行相关的执行。
消耗token完毕，构造成一课语法树后，通过执行器进行相应的处理。
示例：
这课示例树展示了一个1+2-3的计算过程。
示例代码：
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)执行结果：
(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