AMI_Calculator

是支持自定义函数的简单计算器，是编译原理小练习。欢迎使用。

1 功能

1.1 包含

本项目为 header only, 在 C++中包含src/AMI_Calcu.hpp即可

本库的所有内容均在命名空间AmiCal下。

1.2 主要接口

接口	功能
etolf(const std::string&)	将_expr中的表达式计算为双精度实数
etoi(const std::string&)	将_expr中的表达式计算为 32 位整数
etof(const std::string&)	将_expr中的表达式计算为单精度实数
get_error_code(const std::string&)	返回发生的首个错误之错误码或 0
insert_function(const std::string&, double(*f)(const std::vector<double>&))	插入一个自定义函数，一次运行有效
insert_macro(const std::string&, const std::string&)	插入一个自定义宏，一次运行有效

1.3 表达式

1.3.1 常数

以下是可被接受的常数值类型：

1. 十进制数串，形如123, 114514
2. 十进制数串.十进制数串，形如123.456, 0.123
3. .十进制数串，形如.123

1.3.2 算符

以下是可被接受的运算符类型：

+, -, *, /, \, %, (, ), ,

(下述的优先级，数字越大表示越先被计算)

1. +运算符是左结合的，返回左右值的算术和。优先级为 1。
2. -运算符是左结合的，返回左右值的算术差值。优先级为 1。
   表示取相反数的-是右结合的，但只要不是在首位使用它，均需要用括号标注。
   比如，程序处理-1+3可以得出正确的结果，但是处理-1--3会报出语法错误，须写为-1-(-3)才可以得出正确结果
3. *运算符是左结合的，返回左右值的算术积。优先级为 2。
4. /运算符是左结合的，返回左右值的算术商，自动取浮点数。优先级为 2。
5. \运算符是左结合的，返回左右值的算术商，向下取整。优先级为 2。
6. %运算符是左结合的，返回左右值的除余数。优先级为 2。
7. (, )用于标示计算优先级，也用于标示参数列表
8. ,用于分隔参数，左结合，优先级低于任何其他算符。

1.3.3 函数

AMI_Calculator函数定义为形如ID(Para1, Para2, ..)的形式，参数支持任意多个。

1.3.3.1 预定义函数

AMI_Calculator提供以下预定函数

函数	语法	功能	示例
sin	sin(double)	返回参数的弧度-正弦值	sin(3)
cos	cos(double)	返回参数的弧度-余弦值	cos(2)
tan	tan(double)	返回参数的弧度-正切值	tan(2)
sinh	sinh(double)	返回参数的双曲正弦值	sinh(3)
cosh	cosh(double)	返回参数的双曲余弦值	cosh(2)
sum	sum(double, ...)	返回参数序列的和	sum(1,2,3,4.5)
pow/power	pow(double, double)	返回第一参数的第二参数次幂	pow(2,2)
exp	exp()	返回自然对数之底数值	exp()
exp	exp(double)	返回 e 的参数次方	exp(2)
ln	ln(double)	返回参数的自然对数	ln(exp())
pi	pi()	返回圆周率之值	pi()

预定义函数在调用时会执行语义检查，如参数个数与定义不匹配，会返回一个警告或者错误。

1.3.3.2 自定义函数

你可以使用接口insert_function(str, function)来将一个std::string与一个double(*)(const vector<double>&)绑定起来。在绑定之后，AMI_Calculator即可识别你的自定义函数。

若自定义函数的std::string与现有函数产生冲突，以最后一次覆盖为准。

自定义函数不会自动执行语义检查，应在函数体内自行实现。

1.3.4 宏

AMI_Calculator宏定义为两个#之间的字符串。宏在预处理阶段展开为固定的字符串，后交由后端计算。

1.3.4.1 预定义宏

AMI_Calculator提供以下预定宏

宏	展开结果
e	(2.718281828)
pi	(3.141592654)

1.3.4.2 自定义宏

你可以使用接口insert_macro(macro, value)来将一个std::string与一个std::string绑定起来。在绑定之后，AMI_Calculator即可识别你的宏。macro中的宏不需要加#。

若自定义宏的std::string与现有宏产生冲突，以最后一次覆盖为准。

1.4 错误处理

AMI_Calculator具有简单的错误处理能力。

1.4.1 错误信息

1. Ami000 - Complete, 返回码0。正确完成全部计算过程。只会在get_error_code过程中出现。
2. Ami001 - Lexical error, 错误码1, 词法错误。说明你的串中存在着不符合词法规范的词法单元。在发生此错误之时，AMI_Calculator会指出错误串开始的位置和词法单元的词法值。
3. Ami002 - Syntax error, 错误码2, 语法错误。说明你的串虽然词法正确，但其中存在着不符合语法规范的词法单元组合。在发生此错误之时，AMI_Calculator会指出错误词法单元开始的位置和词法单元的词法值。
4. Ami003 - Math error, 错误码3, 运算过程中错误。很大可能是因为为一个函数传入了错误个数的参数。
5. Ami0031 - Semantic warning, 语义警告。你为一个函数传入了过多的参数，程序会删掉参数列表末尾的超出规定个数的参数，但程序仍可以运行。
6. Ami0032 - Semantic error, 错误码3, 语义错误。你为一个函数传入了过少的参数。
7. Ami004 - Preprocesser error: undefined macro, 错误码4, 预处理器错误: 未定义宏。你输入了一个未定义的宏。
8. Ami005 - Preprocesser error: unclosed macro, 错误码5, 预处理器错误: 非闭合的宏符号。你输入了奇数个$符号。
9. Ami100 - Inner error, 错误码100, 这个错误的引发者不是你。看到这个请将你的输入写入issue中。

1.4.2 错误返回值

一旦触发上述任何错误，所有计算接口的返回值都将统一为：

接口	错误返回值
etolf	NaN
etof	NaN
etoi	0

2 实现

2.1 过程

整个计算过程是工厂式链式过程。

2.1.1 预处理

预处理器检查整个串，将串中所有的控制字符转为空格，同时检查所有输入串中的宏，将其展开为合适的形式或报错。

预处理器由三个简单的函数构成，在Pre_p中定义。

2.1.2 词法分析

词法分析使用确定有限状态自动机完成。

在正常的计算程序中，基于对语法分析稳定性的考虑，词法分析会预先执行一遍来排查词法错误，如无词法错误，即复位词法分析器，与语法分析协同执行词法分析。

2.1.3 语法分析

语法分析基于 LL(1)文法，使用递归下降预测分析方法执行。

产生式中的终结符号大部分被表现为语法树属性，少部分直接被舍弃。语法树中的节点全是非终结符。

返回一颗语法树。

2.1.4 语法树剪枝

去除文法中空产生式导致的nullptr子指针，以防在遍历时产生段错误。

由于空产生式只推导至非终结符号的最右侧，所以只需调用std::vector的pop_back方法即可。

2.1.5 语法树求值

使用继承属性求值。求值的实际过程已经写入了语法树节点的类方法中。这一步尤其烧脑，我都不知道自己是怎么写出来的。

语义分析会在此部分协同进行。

2.2 规约

2.1.1 词法规约

词法共有 11 类词法单元。

词法单元有：

终结符号	意义	规则(自然语言)
id	标识符	不以数字开头的字母/数字/下划线组成的非空串
num	整形数	C 风格整形数
float	浮点数	不支持对数描述的 C 风格浮点数
operator	运算符	在运算符表里的单个符号
error	词法错误	所有失配串

2.1.1.1 正则表达式

2.1.1.2 DFA

由于这个正则实在是太简单，无需通过 NFA 即可脑补出 DFA

2.1.2 语法规约

AMI_Calculator使用 LL(1)预测分析，故语法经过消左递归和消回溯处理。

2.1.2.1 终结符号集合

文法共有 11 类终结符号，部分对应 4 种词法单元。

终结符号有：

终结符号	意义	对应的词法单元
function	函数签名	(在符号表中的) id
digit	数字	num | float
ε	空串	---
+	加号	operator && tokentype == '+'
-	负号	operator && tokentype == '-'
***	乘号	operator && tokentype == '*'
/	除号	operator && tokentype == '/'
\	整除	operator && tokentype == '\\'
%	求余	operator && tokentype == '%'
(	左括号	operator && tokentype == '('
)	右括号	operator && tokentype == ')'
,	分隔符	operator && tokentype == ','

2.1.2.2 产生式

文法经过 LL(1)处理后，共有 8 种非终结符号。

非终结符号有：

终结符号	意义
Root	最高级表达式，开始符号
RootRight	Root消左递归形成的右部重复部分
Expr	加减法因子
ExprRight	Expr消左递归形成的右部重复部分
Factor	乘除法因子
Element	乘除法因子中不可再分的部分
Para	参数包
Para'	Para消左递归形成的右部重复部分

所有非终结符号的产生式如下：

$$Root\rArr Expr · RootRight\ | \boldsymbol{-} Expr · RootRight$$ $$RootRight\rArr \boldsymbol{+} Expr · RootRight\ | \boldsymbol{-} Expr · RootRight\ |\boldsymbol{\epsilon}$$

$$Expr\rArr Factor · ExprRight$$ $$ExprRight\rArr \boldsymbol{*} Factor · ExprRight\ | \boldsymbol{/} Factor · RootRight\ $$ $$ExprRight\rArr \boldsymbol{\setminus} Factor · RootRight\ | \boldsymbol{%} Factor · RootRight\ |\boldsymbol{\epsilon}$$

$$Factor\rArr Element\ | \boldsymbol{function(}para\boldsymbol{)}$$

$$Element\rArr \boldsymbol{(}root\boldsymbol{)} | \boldsymbol{digit}$$

$$Para\rArr Root · Para' | \boldsymbol{\epsilon}$$ $$Para'\rArr \boldsymbol{,}Root · Para' | \boldsymbol{\epsilon}$$

上述文法不含左递归，单产生式各个选项的FIRST集合不相交，且具有ε产生式的非终结符号的FIRST与FOLLOW集合不相交，因此适用 LL(1)预测分析技术。

2.1.2.3 FIRST

2.1.2.4 FOLLOW

3 其他

3.1 错误提交

如发生错误码为100的错误提示、运算结果错误、由本库引发的 C++内部异常或段错误，请将你的输入或操作序列和错误细节写入 issue。

不胜感激！

3.2 作者

3.3 开源协议

本库使用 MIT 协议开源。协议已附加到库的根目录。

4 更新日志

2020.01.10 为函数词法扩增了数字和_，但数字不能占首个位置

2020.01.10 修改了rootright_node节点的综合属性计算逻辑，修正了-1-1+2求出为-4的问题

2020.01.09 库构建完毕