# DoubleKill

**Repository Path**: eizoassik/DoubleKill

## Basic Information

- **Project Name**: DoubleKill
- **Description**: 作业用计算器
- **Primary Language**: Java
- **License**: WTFPL
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2014-12-30
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#DoubleKill

本计算器参考`The C++ Programming Language`一书中提供的基于编译器前端计数的思路，采用Java语言重新实现，并修改了一些关键特性，并使之更符合Java语言的编程规范。

本计算器的前端使用编译器技术对表达式进行分析求值。

## 分析部分
分析部分，与`The C++ Programming Language`保持一致，分为专用于识别基本元素的`Lexer`和用于分析表达式整体的`Parser`。

由于算术表达式中能能够出现的仅有数字、括号、运算符三类元素，`Lexer`使用了相对简易的识别方法：

```Java
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`中的：

```Java
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`：

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