代码地址:https://github.com/MakDon/toy\_calculator
效果如下:

实现的功能为读入一个字符串格式的算式,然后输出数字格式的结果。

计算器主要包括如下几个部分:

  1. 词法分析器
  2. 语法分析器
  3. 伪指令生成器
  4. 伪VM

词法分析器

词法分析器对输入的文本进行分析,输出为一串token。如输入为

“1 + 2 + 3 + 5 + 7”

则输出为:

<class ‘list’>:
[[‘NUMBER’, ‘1’], [‘+’, ‘+’], [‘NUMBER’, ‘2’], [‘+’, ‘+’],
[‘NUMBER’, ‘3’], [‘+’,’+’], [‘NUMBER’, ‘5’], [‘+’, ‘+’], [‘NUMBER’, ‘7’]]

此处实现的基本思路是,使用正则对字符串从头进行匹配,若匹配到结果,则截取为一个token,然后继续匹配;若一直匹配不到结果,则认为输入的串存在词法错误。使用的正则分别如下:

{
“NUMBER”: r”([0-9]+\.)?[0-9]+”,# 数字
“+”: r”\+”,# 加号
“-“: r”-“,# 减号
“*“: r”\*“,# 乘号
“/“: r”/“,# 除号
“LBRA”: r”\(“,# 左括号
“RBRA”: r”\)”,# 右括号
“SEPARATOR”: r”( \n)”# 分隔符,此处使用空格与换行
}

  语法分析器: 语法分析,是把词法分析器生成的token串,转换为抽象语法树(Abstract Syntax Tree,AST)。上节的token串生成的AST如下: 在此计算器中,我选择的是自顶向下的生成方式。四则运算语法如下:

Expr -> Term ExprTail
ExprTail -> + Term ExprTail
- Term ExprTail
null

Term -> Factor TermTail
TermTail -> * Factor TermTail
/ Factor TermTail
null

Factor -> (Expr)
num

reference:https://zhuanlan.zhihu.com/p/24035780

其中各个符号的含义与消除左递归的推导过程详见《编译原理》。

伪指令生成

上一节的语法分析器中,生成得到了AST。这一步的作用,则是把上一节得到的树,转化为顺序的指令序列。此处使用了递归的深度遍历的方法,此处生成的每条指令包括如下两个部分:

  1. 操作:操作可以为入栈,或者是运算(加减乘除)。
  2. 操作数:可选,当操作为入栈时,操作数是被入栈的数值。当操作为运算时为None。

上一节的AST可以生成如下指令:

[(PUSH,1), (PUSH,2), (+,None), (PUSH,3), (+,None), (PUSH,5), (+,None), (PUSH,7), (+,None)]

 

伪VM

伪VM的作用,为自行上一节生成的伪指令,最后返回结算的结果。伪VM维护一个栈,用于数值计算。获得指令序列后,开始顺序执行指令。当指令的操作为入栈时,把指令的操作数push入栈顶。当指令为运算时,pop出栈顶的两个数字,进行指令的运算,然后把运算结果push回栈顶。在指令序列执行完后,伪VM的栈内应有且只有一个数值,为计算结果。 在伪VM执行完指令后,就得到结果了,计算的全过程也就此结束了。