动手制作一个计算器

Table of Contents

说到制作一个计算器，我首先想到的是：对字符进行安全检查然后直接eval() 好吧，这种做法是可行的，但是有点作弊了。使用eval()，我们忽略了许多细节问题(况且有些语言没有eval()，拍桌)

下面来从一个深层次的角度来分析这个问题一个计算器需要接收一个算术表达式式然后输出结果，我们假定换行符 \n 作为算式的终结符。然后我们需要从这个算式中去区分出数字和运算符。数字包括整数和小数，所以我们需要对小数点进行处理。运算符之间还存在着优先级关系。

所以为了提取这些有意义的的字符序列，我们对输入字符流进行扫描，进行模式匹配。专业一点，我们将字符流分割成词法单元(token)，这整个的步骤称为词法分析。词法单元通常由类型和值组成，

<token_kind, token_value>

可以用下面的结构体来表示

typedef struct {
    TokenKind kind;
    double value;
} Token;

对一个计算器而言，token 的种类应具有数字，运算符，括号，和终结符这几种。至于负号，我们复用了减号运算符

typedef enum {
    UNKNOWN_TOKEN,
    NUMBER_TOKEN,
    ADD_OPERATOR_TOKEN,
    SUB_OPERATOR_TOKEN,
    MUL_OPERATOR_TOKEN,
    DIV_OPERATOR_TOKEN,
    LEFT_PAREN_TOKEN,
    RIGHT_PAREN_TOKEN,
    END_TOKEN
} TokenKind;

比如 3+2 这个算式，我们返回

<NUMBER_TOKEN, 3>
<ADD_OPERATOR, NULL>
<NUMBER_TOKEN, 2>
<END_TOKEN, NULL>

有了以上的准备后，我们便可以对字符流进行解析了，定义一个 next()函数来返回 token 对于运算符 + - * / 和 () 我们直接返回其 token，对于数字的匹配稍微有点麻烦，因为它是由多个字符组成的。这里采用设置状态标志的方法解决。

typedef enum {
    INITIAL_STATUS,
    IN_INT_PART_STATUS,
    DOT_STATUS,
    IN_FRAC_PART_STATUS
} LexerStatus;

初始的状态为 INITIAL_STATUS。当遇到 [0-9]时，我们便将状态更改为 IN_INT_PART_STATUS ，当遇到小数点时，更改为 DOT_STATUS ，再遇到[0-9]时更改为 IN_FRAC_PART_STATUS。在 IN_INT_PART_STATUS 或 IN_FRAC_PART_STATUS 状态下，如果再无数字或小数点出现，则返回。 一时语塞，表达不太严谨，看代码好了:)

void next()
{
    // position of token_value
    int pos = 0;
    LexerStatus status = INITIAL_STATUS;
    char current_char;

    // default token kind
    token.kind = UNKNOWN_TOKEN;
    while (*buffer != '\0') {
        current_char = *buffer;

        // match number end
        if ((status == IN_INT_PART_STATUS || status == IN_FRAC_PART_STATUS)
            && !isdigit(current_char) && current_char != '.') {
            token.kind = NUMBER_TOKEN;
            sscanf(token_value, "%lf", &token.value);
            return;
        }

        // skip
        if (isspace(current_char)) {
            if (current_char == '\n') {
                token.kind = END_TOKEN;
                return;
            }
            buffer++;
            continue;
        }

        token_value[pos++] = *buffer++;
        token_value[pos] = '\0';

        if (current_char == '+') {
            token.kind = ADD_OPERATOR_TOKEN;
            return;
        } else if (current_char == '-') {
            token.kind = SUB_OPERATOR_TOKEN;
            return;
        } else if (current_char == '*') {
            token.kind = MUL_OPERATOR_TOKEN;
            return;
        } else if (current_char == '/') {
            token.kind = DIV_OPERATOR_TOKEN;
            return;
        } else if (current_char == '(') {
            token.kind = LEFT_PAREN_TOKEN;
            return;
        } else if (current_char == ')') {
            token.kind = RIGHT_PAREN_TOKEN;
            return;
        } else if (isdigit(current_char)) {
            if (status == INITIAL_STATUS) {
                status = IN_INT_PART_STATUS;
            } else if (status == DOT_STATUS) {
                status = IN_FRAC_PART_STATUS;
            }
        } else if (current_char == '.') {
            if (status == IN_INT_PART_STATUS) {
                status = DOT_STATUS;
            } else {
                fprintf(stderr, "syntax error\n");
                exit(1);
            }
        }
    }
}

剩下的我们便要进行语法分析了先考虑一下算术表达式的运算符结合性和优先级

左结合: + -
左结合: * /

结合性便不用考虑了，因为都相同。优先级的话，我们创建两个非终结符号 expression 和 term 来对应这两个优先级层次，并使用另一个非终结符号 factor 来表示表达式中的基本单元: 数字和带括号的表达式构建好的BNF范式如下

expression
    : term
    | expression ADD term
    | expression SUB term
    ;

term
    : factor
    | term MUL factor
    | term DIV factor
    ;

factor
    : NUM
    | LP expression RP
    | MINUS factor
    ;

但是如果采用这样的语法规则，我们会陷入左递归的陷阱中

expression
    | expression ADD term

比如上面，我们不断的向下分析 expression ，会进入无限循环

所以我们要采用一点小技巧对现有规则进行转换形如

A
    | Aα
    | Aβ
    | γ
    ;

的规则可转换为

A
    | γR
    ;

R
    | αR
    | βR
    | ε
    ;

套用上面的技巧，令

A = expression
α = + term
β = - term
γ = term

转换后可得

expression
    | term rest

rest
    | + term
    | - term
    | ε

剩下规则的转换便不详细写了

依照上面的语法规则可写出以下代码

double parse_factor()
{

    double value = 0.0;
    int minus_flag = 0;

    next();

    // if token is minus, get next token
    if (token.kind == SUB_OPERATOR_TOKEN) {
        minus_flag = 1;
        next();
    }

    if (token.kind == NUMBER_TOKEN) {
        value = token.value;
    } else if (token.kind == LEFT_PAREN_TOKEN) {
        // ( expr )
        value = parse_expression();
        if (token.kind != RIGHT_PAREN_TOKEN) {
            fprintf(stderr, "missing ')'\n");
            exit(1);
        }
    }

    if (minus_flag) {
        value = -value;
    }

    next();

    return value;
}

double parse_term()
{
    double v1;
    double v2;
    int operator;

    v1 = parse_factor();
    for (;;) {

        if (token.kind != MUL_OPERATOR_TOKEN
            && token.kind != DIV_OPERATOR_TOKEN) {
            break;
        }
        operator = token.kind;
        v2 = parse_factor();
        if (operator == MUL_OPERATOR_TOKEN) {
            v1 *= v2;
        } else if (operator == DIV_OPERATOR_TOKEN) {
            v1 /= v2;
        }
    }
    return v1;
}

double parse_expression()
{
    double v1;
    double v2;
    int operator;

    v1 = parse_term();
    for (;;) {

        if (token.kind != ADD_OPERATOR_TOKEN
            && token.kind != SUB_OPERATOR_TOKEN) {
            break;
        }
        operator = token.kind;
        v2 = parse_term();
        if (operator == ADD_OPERATOR_TOKEN) {
            v1 += v2;
        } else if (operator == SUB_OPERATOR_TOKEN) {
            v1 -= v2;
        }
    }
    return v1;
}

好了，一个计算器便完成了完整代码见 GitHub

Reference
#

BNF 范式左递归编译原理编程语言实现模式

Reference#

Reference
#