编译原理学习笔记（二）

发表于 更新于 分类于

之前借助工具写了一个简单的计算器，现在尝试不借助工具，手动实现词法分析器和语法分析器，并添加括号与负号

词法分析器

词法分析器写起来很简单，写一个循环依次匹配字符，处理每一种记号。

记号

用来存放记号的Token结构体。之前说了，记号有三个属性：类型，数值，原始字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//
// Created by Apeng on 2020/2/11.
//

#ifndef CALC_PRO_TOKEN_HPP
#define CALC_PRO_TOKEN_HPP

#include <string>

enum TokenKind {
    BAD,
    NUMBER,
    ADD,
    SUB,
    MUL,
    DIV,
    CR
};

struct Token {
    TokenKind type;
    double value;
    std::string str;
};

#endif //CALC_PRO_TOKEN_HPP

词法分析

匹配实数的时候稍微复杂一点的，我将他分为整数小数指数三部分匹配，并要考虑不同情况的合法性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//
// Created by Apeng on 2020/2/11.
//

#ifndef CALC_PRO_LEXER_HPP
#define CALC_PRO_LEXER_HPP

#include "token.hpp"
#include <vector>

class Lexer {
public:
    static std::vector<Token> parse_line(std::string &str);
};

std::vector<Token> Lexer::parse_line(std::string &str) {
    std::vector<Token> tokens;
    int idx = 0;
    while(idx < str.length()) {
        if (str[idx] == ' ' or str[idx] == '\t') {
            idx++;
            continue;
        }
        if (str[idx] == '\n') {
            Token token;
            token.type = CR;
            token.str = std::string("\n");
            tokens.push_back(token);
            idx++;
            continue;
        }
        if (str[idx] == '+') {
            Token token;
            token.type = ADD;
            token.str = std::string("+");
            tokens.push_back(token);
            idx++;
            continue;
        }
        if (str[idx] == '-') {
            Token token;
            token.type = SUB;
            token.str = std::string("-");
            tokens.push_back(token);
            idx++;
            continue;
        }
        if (str[idx] == '*') {
            Token token;
            token.type = MUL;
            token.str = std::string("*");
            tokens.push_back(token);
            idx++;
            continue;
        }
        if (str[idx] == '/') {
            Token token;
            token.type = DIV;
            token.str = std::string("/");
            tokens.push_back(token);
            idx++;
            continue;
        }
        if (isdigit(str[idx])) {
            Token token;
            token.type = NUMBER;
            if (str[idx] == '0') { // integer part start at zero
                token.str += "0";
                idx++;
            }
            else {
                for(; isdigit(str[idx]); idx++) { // not zero
                    token.str += str[idx];
                }
            }
            if (str[idx] == '.') { // has decimal part
                token.str += '.';
                idx++;
                for(; isdigit(str[idx]); idx++) {
                    token.str += str[idx];
                }
            }
            if (str[idx] == 'e' || str[idx] == 'E') { // has exponent part
                token.str += str[idx];
                idx++;
                if (str[idx] == '+' || str[idx] == '-') {
                    token.str += str[idx];
                    idx++;
                }
                if (!isdigit(str[idx])) {
                    throw "syntax error!";
                }
                for(; isdigit(str[idx]); idx++) {
                    token.str += str[idx];
                }
            }
            token.value = strtod(token.str.c_str(), nullptr);
            tokens.push_back(token);
        }
        else
            throw std::logic_error("wrong token.");
    }
    return tokens;
}


#endif //CALC_PRO_LEXER_HPP

词法分析器

接下来制作词法分析器。我们采用递归下降分析的方法编写语法分析器。

简单来讲，从最大的line开始，逐级向下递归分析每一部分。比如line由expression和CR组成，expression则由若干个term和ADD/SUB组成。解析expression时，先解析出一个term，然后循环解析后面的term。

同理解析每一个term。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//
// Created by Apeng on 2020/2/13.
//

#ifndef CALC_PRO_PARSER_HPP
#define CALC_PRO_PARSER_HPP

#include <utility>
#include <vector>
#include <cassert>
#include "token.hpp"

class Parser {
    std::vector<Token> tokens;
public:
    Parser() = default;
    explicit Parser(std::vector<Token> tokens): tokens(std::move(tokens)) {}
    double parse();

private:
    double parse_line();
    double parse_expression();
    double parse_term();
    double parse_primary_expression();

};


double Parser::parse() {
    double value = parse_line();
    return value;
}

double Parser::parse_line() {
    double value;
    value = parse_expression();
    return value;
}

double Parser::parse_expression() {
    double left = parse_term();
    for (;;) {
        Token token = tokens.front();
        if (token.type != ADD && token.type != SUB)
            break;
        tokens.erase(tokens.begin());
        double right = parse_term();
        if (token.type == ADD)
            left += right;
        else if (token.type == SUB)
            left -= right;
    }
    return left;
}

double Parser::parse_term() {
    double left = parse_primary_expression();
    for (;;) {
        Token token = tokens.front();
        if (token.type != MUL && token.type != DIV)
            break;
        tokens.erase(tokens.begin());
        double right = parse_primary_expression();
        if (token.type == MUL)
            left *= right;
        else if (token.type == DIV)
            left /= right;
    }
    return left;
}

double Parser::parse_primary_expression() {
    Token token = tokens.front();
    tokens.erase(tokens.begin());
    if (token.type == NUMBER) {
        return token.value;
    }
    throw std::logic_error("syntax error.");
}


#endif //CALC_PRO_PARSER_HPP

整个写完之后对递归向下分析的思路就清晰了很多。如果要加括号功能，只需要分析，括号包裹的内容应为一个expression，括号整体是一个primary_expression，所以修改一下就可以轻松实现括号功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
double Parser::parse_primary_expression() {
    Token token = tokens.front();
    tokens.erase(tokens.begin());
    if (token.type == NUMBER) {
        return token.value;
    }
    else if (token.type == LP) {
        double value = parse_expression();
        Token token1 = tokens.front();
        if (token1.type == RP) {
            tokens.erase(tokens.begin());
            return value;
        }
        throw std::logic_error("Syntax error. Mismatched parentheses");
    }
    throw std::logic_error("Syntax error.");
}