代码地址:https://github.com/MakDon/toy_calculator 效果如下:实现的功能为读入一个字符串格式的算式,然后输出数字格式的结果。
计算器主要包括如下几个部分:
- 词法分析器
- 语法分析器
- 伪指令生成器
- 伪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。这一步的作用,则是把上一节得到的树,转化为顺序的指令序列。此处使用了递归的深度遍历的方法,此处生成的每条指令包括如下两个部分:
- 操作:操作可以为入栈,或者是运算(加减乘除)。
- 操作数:可选,当操作为入栈时,操作数是被入栈的数值。当操作为运算时为None。
上一节的AST可以生成如下指令:
[(PUSH,1), (PUSH,2), (+,None), (PUSH,3), (+,None), (PUSH,5), (+,None), (PUSH,7), (+,None)]
伪VM
伪VM的作用,为自行上一节生成的伪指令,最后返回结算的结果。伪VM维护一个栈,用于数值计算。获得指令序列后,开始顺序执行指令。当指令的操作为入栈时,把指令的操作数push入栈顶。当指令为运算时,pop出栈顶的两个数字,进行指令的运算,然后把运算结果push回栈顶。在指令序列执行完后,伪VM的栈内应有且只有一个数值,为计算结果。
在伪VM执行完指令后,就得到结果了,计算的全过程也就此结束了。