#DoubleKill
本计算器参考The C++ Programming Language
一书中提供的基于编译器前端计数的思路,采用Java语言重新实现,并修改了一些关键特性,并使之更符合Java语言的编程规范。
本计算器的前端使用编译器技术对表达式进行分析求值。
分析部分,与The C++ Programming Language
保持一致,分为专用于识别基本元素的Lexer
和用于分析表达式整体的Parser
。
由于算术表达式中能能够出现的仅有数字、括号、运算符三类元素,Lexer
使用了相对简易的识别方法:
if (Character.isSpaceChar(curr)) {
this.pos += 1; // 略过空白
} else if (Character.isDigit(curr)) {
this.last = readNumber();
return this.last;
} else {
this.last = readToken();
return this.last;
}
除此之外的符号均被判定为不合法并抛出异常。
Lexer
的主要工作是把字符流转换成为为Parser
所用的记号流,并用以进一步识别。
在处理算术表达式,在这里是中缀表达式,此时,必须对运算符的优先级进行处理,为数字和括号、前缀+/-
、乘除、加减提供4个不同的优先级。
本计算器在处理算术表达式时使用了递归下降分析的策略,从空多项式开始先下构造完整的表达式,并通过按优先级分解产生式来控制各个算术运算的优先级。
本计算器使用的产生式如下:
expr -> term { +|- term }
term -> fact { *|/ fact }
fact -> [+|-] atom
atom -> NUMBER | ( expr )
该文法是LL(1)的,且不需回溯。
为了实现递归下降分析,还需要引入一组用于控制词法分析器的函数,包括实现在Parser
中的:
private static Token read_safe(CalcLexer lexer);
private static boolean match(CalcLexer lexer, TokenType type);
private static boolean test_2(CalcLexer lexer, TokenType type_a, TokenType type_b);
和实现在Lexer
中的锁定/解锁方法。
由于在特定节点执行算术表达式的语义动作不需要预知整体结构,因此求值代数表达式的语义动作可以在分析的过程中同步进行,因此,本计算器中的Parser
和Eval
模块就是分析器和求职器的共同实现,在每个非终结符展开完毕后即可进行求值,例如最顶层的expr
:
private static double eval_expr(CalcLexer lexer) throws Exception {
double ret = eval_term(lexer);
while (test_2(lexer, TokenType.ADD, TokenType.SUB)) {
Token tk = lexer.lex();
if (tk.getType() == TokenType.ADD)
ret += eval_term(lexer);
else
ret -= eval_term(lexer);
}
return ret;
}
其中,部分求值工作在term
完整展开之后就执行了。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。