@[TOC]
前言
先前，我们实现了一个基本的词法分析器。那么现在的话，我们要在这个基础上面，实现一个解析器，那么实现效果的话，是这样的：
注意此时此刻，我们还啥都没有，目前我们还没有自己的变量等等，我们目前还是只是对数学运算进行处理并且只是对+-*/进行简单处理。当然这里的话，对比上次做的是做出了一点改动，当然这都不是重点，因为在这里都会进行说明。
语法树
由于，我们在这里的话，我们要做一个解析器，因此的话，我们毫无疑问的是，我们需要去构建一个简单的语法树。那么在这里的话，先前，我们是实现了一个简单的词法解析器，也就是我们把这些东西都解析为了Token。
，当然为了适应这部分的代码，我们对先前的代码进行了一点改动。至于是哪里改动了，这里会进行说明（由于代码不难超过文章的60%，所以这里无法贴出全部代码，后期做好了，再给仓库地址吧~
那么在这里的话，我们看到了刚刚的效果，所以的话，我们这里的话其实还是只是实现了一个简单的运算表达式的语法解析。
也就是其实，我们今天实现的效果是这样的，假设用户在终端输入：
在我们的代码里面将构造出这个：
换一句话说，我们今天实现的效果，其实就是中缀表达式用一颗树来表示。只是这个树，在我们这里叫做语法树。目前我们只是解析这个，后面我们再解析变量等等，这样的话，我们就可以非常愉快地实现这个小语言了。
所以在这块我们先引入几个东西。
节点
在这里的话，我们要做的是把刚刚的这个转化为一颗语法树，也就是（目前）输入的合法的数学表达式。所以的话，为了能够去构建这棵树，我们定义了如下节点：
"""
定义节点：
NumberNode：表示数字节点，用于存储数字的令牌（token）信息。
BinOpNode：表示二元操作符节点。其中：
left_node（左节点），
op_tok（操作符令牌），
right_node（右节点）
UnaryOpNode：表示一元操作符节点。
op_tok（操作符令牌）
node（子节点）
"""
class NumberNode:
def __init__(self, tok):
self.tok = tok
def __repr__(self):
return f'{self.tok}'
class BinOpNode:
def __init__(self, left_node, op_tok, right_node):
self.left_node = left_node
self.op_tok = op_tok
self.right_node = right_node
def __repr__(self):
return f'({self.left_node}, {self.op_tok}, {self.right_node})'
class UnaryOpNode:
def __init__(self, op_tok, node):
self.op_tok = op_tok
self.node = node
def __repr__(self):
return f'({self.op_tok}, {self.node})'
语法描述
接下来，我们把我们提到的这个节点和我的刚刚的节点进行对应，进行查抽象，
并且他们的代码关系大致是这样的：
于是得到语法描述
expr（表达式）
：由一个项（term）后面跟随零个或多个类似于加法（PLUS）或减法（MINUS）操作符的项组成。term（项）
：由一个因子（factor）后面跟随零个或多个类似于乘法（MUL）或除法（DIV）操作符的因子组成。factor（因子）
> ：可以是整数（INT）或浮点数（FLOAT）
> ：是一个加法（PLUS）或减法（MINUS）操作符后面跟随一个因子
> ：或者是括号内的一个表达式（expr）。
异常处理
okey,在开始我们的具体核心实现之前的话，我们还是来看到我们对异常的处理吧。
InvalidSyntaxError
那么在这里我们首当其冲的就是我们的这个语法错误的报错。
class InvalidSyntaxError(HlangError):
def __init__(self, pos_start, pos_end, details=''):
super().__init__(pos_start, pos_end, 'Invalid Syntax：语法错误', details)
也是我们在学习过程当中，遇到的第一个错误。
那么在这里的话，对比上次的代码，在这里我对Error父类也进行了改动：
class HlangError:
def __init__(self, pos_start, pos_end, error_name, details):
"""
:param pos_start: 错误开始未知
:param pos_end: 错误结束未知
:param error_name: 错位类型
:param details: 细节
"""
self.pos_start = pos_start
self.pos_end = pos_end
self.error_name = error_name
self.details = details
def as_string(self):
red_code = " 33[91m"
reset_code = " 33[0m"
result = f'{self.error_name}: {self.details}n'
result += f'File {self.pos_start.fn}, line {self.pos_start.ln + 1}'
result += 'nn' + string_with_arrows(self.pos_start.ftxt, self.pos_start, self.pos_end)
return red_code+result+reset_code
错误内容定位
那么在这里的话，我之所以做这个改动，主要是因为，我们要实现这个显示错误的内容提示，那么这个时候的话，当出现异常的时候，之所以，可以这样，还有一个原因是，我们对这个类Position也进行了修改，这个家伙，现在会记录当前的文本了：
class Position:
def __init__(self, idx, ln, col, fn, ftxt):
self.idx = idx
self.ln = ln
self.col = col
self.fn = fn
self.ftxt = ftxt
def advance(self, current_char=None):
self.idx += 1
self.col += 1
if current_char == 'n':
self.ln += 1
self.col = 0
return self
def copy(self):
return Position(self.idx, self.ln, self.col, self.fn, self.ftxt)
这样做的好处是能够进行快速定位显示错误。
之后的话，为了显示出错误：
这里有一个专门用来显示错误的方法：
def string_with_arrows(text, pos_start, pos_end):
result = ''
# 计算索引位置
idx_start = max(text.rfind('n', 0, pos_start.idx), 0)
idx_end = text.find('n', idx_start + 1)
if idx_end < 0:
idx_end = len(text)
# 生成每一行
line_count = pos_end.ln - pos_start.ln + 1
for i in range(line_count):
# 计算行的列数
line = text[idx_start:idx_end]
col_start = pos_start.col if i == 0 else 0
col_end = pos_end.col if i == line_count - 1 else len(line) - 1
# 添加到结果中
result += line + 'n'
result += ' ' * col_start + '^' * (col_end - col_start)
# 重新计算索引位置
idx_start = idx_end
idx_end = text.find('n', idx_start + 1)
if idx_end < 0:
idx_end = len(text)
return result.replace('t', '')
解析实现
那么在这里之后的话，就是我们解析的实现了。
那么首先在这里的话，我们对这个节点在进行一个简单的封装：
class ParseResult:
def __init__(self):
self.error = None
self.node = None
def register(self, res):
if isinstance(res, ParseResult):
if res.error: self.error = res.error
return res.node
return res
def success(self, node):
self.node = node
return self
def failure(self, error):
self.error = error
return self
这样做的目的只要是为了，能够去记录一下异常。记录一下这个报错，不记录不行。
它的核心其实就是这几个方法：
那么在这里的话主要有两个比较核心的代码：
bin_op函数
因为我们这里要构造的就是一棵树，所以i的话，我们要递归处理，我们要去合并左右子树。所以这个函数的作用就是去生成当前的语法解析树。
def bin_op(self, func, ops):
res = ParseResult()
#构造左边的解析树
left = res.register(func())
if res.error: return res
while self.current_tok.type in ops:
#如果，当前的token，是token，令牌是这个符合要求的运算符
#那么拿到下一个token,然后看看能不能构造左边的解析树
#记住我们这里是中缀表达式，从左到右的
op_tok = self.current_tok
res.register(self.advance())
right = res.register(func())
if res.error: return res
#此时我们把左右合并，组装成新的树，但是如果没有，
# 那么左子树就是当前的树，不用构造，没有新的层级
left = BinOpNode(left, op_tok, right)
return res.success(left)
factory函数
之后是这个函数，这个函数的唯一作用其实就是构造当前的节点。这里的话有一点要说明的是，那就是我们先解析的token是封装好的，然后我们是按照从左到右进行拿到的，我们读取的时候也是按照顺序读取的，因此这个就意味着在我们进行解析的时候，针对这个数学表达式，其实就是按照中缀的顺序来进行处理 的。
def factor(self):
res = ParseResult()
tok = self.current_tok
if tok.type in (TT_PLUS, TT_MINUS):
#如果是运算符号，那么它是一元操作符，找到下一个数字
res.register(self.advance())
factor = res.register(self.factor())
if res.error: return res
#返回到右子树
return res.success(UnaryOpNode(tok, factor))
elif tok.type in (TT_INT, TT_FLOAT):
#如果是一个数字，那么直接返回节点
res.register(self.advance())
return res.success(NumberNode(tok))
#如果是(，那么说明这个玩意又是一个表达式
elif tok.type == TT_LPAREN:
res.register(self.advance())
expr = res.register(self.expr())
if res.error: return res
if self.current_tok.type == TT_RPAREN:
res.register(self.advance())
return res.success(expr)
else:
return res.failure(InvalidSyntaxError(
self.current_tok.pos_start, self.current_tok.pos_end,
"应该是： ')'"
))
return res.failure(InvalidSyntaxError(
tok.pos_start, tok.pos_end,
"应为：整型或浮点型"
))
模拟流程
如果你熟悉递归的话，那么这个案例，你就不需要看了。怎么去想这个递归的话，给点提示就是，按照不同的类型，去构建不同的节点。然后递归只要关系当前的函数的作用即可。具体的，递归思想可以看到我总结的7W蓝桥杯算法的部分。里面关于递归的写法是我总结了的，按照那个套路写，leetcode分分钟秒杀大部分中档题目，hard 题目那就需要点技巧了。
假设要解析的表达式是`(5+3)*2`,那么我们这个解析器的流程是这样的： 目标是这个： * / + 2 / 5 3 1. 表达式：`(5+3)*2` 2. 调用 `expr()` 方法开始解析表达式。 3. 在 `bin_op()` 方法内部，调用 `term()` 方法解析左操作数。 - 调用 `term()` 方法开始解析项。 - 在 `bin_op()` 方法内部，调用 `factor()` 方法解析左操作数。 - 获取数字 `5` 的令牌，并创建一个 NumberNode 对象表示该数字。 - 返回左操作数的解析结果。 4. 循环检查当前令牌，发现下一个令牌是 `+` 号。 5. 调用 `bin_op()` 方法解析加法运算符。 - 调用 `term()` 方法作为参数传递给 `bin_op()` 方法，解析右操作数。 - 调用 `term()` 方法开始解析项。 - 在 `bin_op()` 方法内部，调用 `factor()` 方法解析右操作数。 - 获取数字 `3` 的令牌，并创建一个 NumberNode 对象表示该数字。 - 返回右操作数的解析结果。 - 创建一个 BinOpNode 对象，表示加法运算，左操作数为前面解析得到的 NumberNode 对象，右操作数为刚刚解析得到的数字 `3` 的 NumberNode 对象。 6. 返回加法运算的结果，即 BinOpNode 对象。 7. 循环检查当前令牌，发现下一个令牌是 `*` 号。 8. 调用 `bin_op()` 方法解析乘法运算符。 - 调用 `term()` 方法作为参数传递给 `bin_op()` 方法，解析右操作数。 - 获取数字 `2` 的令牌，并创建一个 NumberNode 对象表示该数字。 - 创建一个 BinOpNode 对象，表示乘法运算，左操作数为前面解析得到的 BinOpNode 对象，右操作数为刚刚解析得到的数字 `2` 的 NumberNode 对象。 9. 返回乘法运算的结果，即 BinOpNode 对象。 10. 返回表达式的解析结果，即最终得到的抽象语法树的根节点。
总结
okey,溜了，还是很有意思的东东。
