#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完整展开之后就执行了。