# 1. 需求分析文档
## 1.1. 功能性需求
该程序为一个文本模式计算器,需要包含如下功能:
1. 程序启动后显示一个命令提示符,该命令提示符可以通过设置环境变量BC_INDICATOR进行设置;当该环境变量为空时,命令提示符默认为“->”;
2. 程序启动后,输入文本形式的四则运算公式,回车后可以得到运算结果,例如:
```
-> 1+2-3*4/5 [Enter]
0.600000
```
其中,乘法和除法的优先级高于加法和减法,同级运算符为左结合,并且所有运算为双精度浮点运算;
3. 支持圆括号改变运算优先级,圆括号中的内容具有最高的求解优先级,例如:
```
-> (1+2-3)*4/5 [Enter]
0.000000
```
4. 支持如下数学函数sin, cos, ln, exp, sqrt, pow, fabs,例如:
```
-> cos(0.0) [Enter]
1.000000
-> sqrt(0.01) [Enter]
0.100000
```
5. 支持双精度数学常量pi和e,例如:
```
-> cos(pi) [Enter]
-1.000000
-> cos(pi/2) [Enter]
0.000000
-> ln(e) [Enter]
1.000000
```
6. 在程序中,初始默认运算精确到6位小数,可以通过“SET_PRECISION”命令指定运算精度:
```
-> pi [Enter]
3.141593
-> SET_PRECISION 2
OK.
-> pi [Enter]
3.14
```
7. 用户输入为空时,会忽略此次指令:
```
-> [Enter]
-> [Enter]
->
```
8. 通过EXIT命令可以退出计算器:
```
-> EXIT
Bye.
```
## 1.2. 非功能性需求
除了上述功能以外,需要考虑以下非功能性需求(系统健壮性、易用性):
1. 当用户输入不合法时提示:
```
-> hello [Enter]
Invalid expression.
-> (1+2 * 3 [Enter]
Invalid expression.
```
2. 算术错误时提示:
```
-> 1 / 0 [Enter]
Computation error.
-> sqrt(-1)
Computation error.
```
总之,当用户错误输入时,需要有适当的提示告知用户;不能出现程序崩溃退出的情况。
# 2. 系统设计文档
## 2.1. 总体设计
根据需求分析文档,该程序为一个文本计算器,不断接受用户输入并求值。因此程序主体为一个循环,不断接受用户输入并处理、输出,并且仅当用户输入为EXIT时,退出程序。
在每次处理用户输入时,可以进一步将功能性需求分为相对独立的两大部分:核心功能(表达式求值)和非核心功能(命令提示符、精度、退出等)。
## 2.2. 核心功能设计
核心功能包括和表达式求值相关的若干功能,包括:
1. 基本的四则运算支持,包括运算符优先级、同级运算符左结合
2. 圆括号控制运算优先级
3. 部分数学函数支持
4. 数学常量pi和e的支持
下面将分别介绍解析表达式中的词法分析和语法分析,并通过递归下降算法实现求值的整体逻辑。
### 2.2.1 词法分析
首先需要对用户的输入字符串进行词法分析,这一步将用户输入的字符串处理为可接受的tokens序列。
合法的tokens包括:
1. 运算符:'+', '-', '*', '/'(注意,其中'-'还可以表示负号)
2. 圆括号:'(', ')'
3. 数学函数:'sin', 'cos', 'ln', 'exp', 'sqrt', 'pow', 'fabs'
4. 数学常量:'pi', 'e'
5. 0-9的数位:'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
6. 浮点数常量中的小数点:'.'(例如:3.56)
7. 二元函数pow中的逗号:','(例如:pow(2, 3))
8. 表示句子终结的特殊token:'#'
词法分析模块,输入为字符串,输出为表示token的结构体数组。分析逻辑如下:
1. 从左至右扫描字符串,初始化指针指向字符串的第一个字符
2. 若当前指向的字符为空白字符,则将指针向后移动一位
3. 若剩余子串的前缀匹配任意tokens,则将其追加到结构体数组中,并且将指针后移对应位数
4. 若剩余子串的前缀与任何一个token都不匹配,词法分析退出并报告错误
5. 循环2-4,直到指针指向字符串末尾,在结构体数组中追加'#'标志,代表输入终结,然后返回结构体数组。
### 2.2.2 语法分析
根据核心功能需求,可以写出如下的文法:
```
产生式 编号
--------------------------------------------------------------------
S -> AddExp 1
AddExp -> MulExp AddExp' 2
AddExp' -> + MulExp AddExp' | - MulExp AddExp' | ε 3-5
MulExp -> AtomExp MulExp' 6
MulExp' -> * AtomExp MulExp' | / AtomExp MulExp' | ε 7-9
AtomExp -> ( AddExp ) | FuncExp | ConstValue 10-12
FuncExp -> Func1 ( AddExp ) | Func2 ( AddExp , AddExp ) 13-14
Func1 -> sin | cos | ln | exp | sqrt | fabs 15-20
Func2 -> pow 21
ConstValue -> pi | e | NumericValue | - NumericValue 22-25
NumericValue -> . Digit Digits | Digit NumericValue' 26-27
NumericValue' -> . Digits | Digit NumericValue' | ε 28-30
Digits -> Digit Digits | ε 31-32
Digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 33-42
```
其中:
1. AddExp表示加减表达式
2. MulExp表示乘除表达式
3. AtomExp表示原子表达式,例如圆括号包围的表达式、常量、函数表达式等
4. FuncExp表示函数表达式,根据需求,又可以分为:
1. 一元函数,包括sin、cos、ln、exp、sqrt、fabs
2. 二元函数,包括pow
5. ConstValue表示常量,包括两个数学常量(pi和e)以及其它浮点数常量
6. NumericValue为正浮点数常量,支持如下几种形式:
1. 不包含小数点的整数,例如:45
2. 包含整数部分和小数部分的一般浮点数,例如:3.00
3. 省略整数部分的浮点数,例如:.234
4. 省略小数部分的浮点数,例如:3.
上面的文法满足以下条件:
1. 不存在左递归;
2. 对于任意两个相同左部的产生式“A -> α | β”,当α和β都不能推导出空表达式时,两者First集的交集为空;
3. 对于任意两个相同左部的产生式“A -> α | β”,α和β至多只有一个能推导出空表达式;
4. 对于任意两个相同左部的产生式“A -> α | β”,假设α能推导出空表达式,那么满足α的First集与β的Follow集的交集为空
因此,该文法为LL(1)文法,可以进行自顶向下的语法分析。
上述文法,非终结符号的First集和Follow集如下所示:
| Non-terminal | First | Follow |
| --- | --- | --- |
| S | {(,sin,cos,ln,exp,sqrt,fabs,pow,pi,e,-,.,0,1,2,3,4,5,6,7,8,9} | {#} |
| AddExp | {(,sin,cos,ln,exp,sqrt,fabs,pow,pi,e,-,.,0,1,2,3,4,5,6,7,8,9} | {),,,#} |
| AddExp' | {+,-,ε} | {),,,#} |
| MulExp | {(,sin,cos,ln,exp,sqrt,fabs,pow,pi,e,-,.,0,1,2,3,4,5,6,7,8,9} | {+,-,),,,#} |
| MulExp' | {*,/,ε} | {+,-,),,,#} |
| AtomExp | {(,sin,cos,ln,exp,sqrt,fabs,pow,pi,e,-,.,0,1,2,3,4,5,6,7,8,9} | {*,/,+,-,),,,#} |
| FuncExp | {sin,cos,ln,exp,sqrt,fabs,pow} | {*,/,+,-,),,,#} |
| Func1 | {sin,cos,ln,exp,sqrt,fabs} | {(} |
| Func2 | {pow} | {(} |
| ConstValue | {pi,e,-,.,0,1,2,3,4,5,6,7,8,9} | {*,/,+,-,),,,#} |
| NumericValue | {.,0,1,2,3,4,5,6,7,8,9} | {*,/,+,-,),,,#} |
| NumericValue' | {.,0,1,2,3,4,5,6,7,8,9,ε} | {*,/,+,-,),,,#} |
| Digits | {0,1,2,3,4,5,6,7,8,9,ε} | {*,/,+,-,),,,#} |
| Digit | {0,1,2,3,4,5,6,7,8,9} | {.0,1,2,3,4,5,6,7,8,9,*,/,+,-,),,,#} |
构建预测分析表如下:
||S|AddExp|AddExp'|MulExp|MulExp'|AtomExp|FuncExp|Func1|Func2|ConstValue|NumericValue|NumericValue'|Digits|Digit|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|+ |-|-|3|-|9|-|-|-|-|-|-|30|32|-|
|- |1|2|4|6|9|12|-|-|-|25|-|30|32|-|
|* |-|-|-|-|7|-|-|-|-|-|-|30|32|-|
|/ |-|-|-|-|8|-|-|-|-|-|-|30|32|-|
|( |1|2|-|6|-|10|-|-|-|-|-|-|-|-|
|) |-|-|5|-|9|-|-|-|-|-|-|30|