# 词法分析

词法分析是整个编译器结构中最简单的一个阶段，所以放轻松，咱们往下看。

那么，词法分析是什么呢？
我们知道，程序开发者编写的源代码，也就是编译器最初能够接收到的输入，即连续的字符序列。

词法分析存在的意义，就是提前将源代码切分成能被后续编译程序直接使用的单词序列。

  • 如源代码中的变量标识，关键字，字符串字面量，数值字面量等…

我们上一节课所展示的算术表达式， 3 + 2 ，也是先将其分成 3 + 2 三个节点，才能用于构成抽象语法树。

词法分析器产出的单词序列，我们将其称为 Token 。

# 输入四则运算表达式，产出 Token

我们既然需要将四则运算表达式转成 Token ，也就需要知道其单词序列的规则，当然，关于这一点，我们早已烂熟于心了。
以下是我通过正则表达式描述的 Token 匹配规则 (以我们将要开发的词法分析器为准)。

TokenType Regex
Eof \0
Number \d+
OpAdd +
OpSub -
OpMul *
OpDiv /
SepLParen (
SepRParen )

此处笔者忽略了运算符在正则表达式中需要转义的情况，做一个参考即可。

# Lexer

Lexer，即词法分析器。
接下来我们编写代码实现 Lexer。

# Token

\ToyLang\lexer\token.h 
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
#ifndef LEXER_TOKEN_H_
#define LEXER_TOKEN_H_

#include <string>

namespace toylang {

// token类型常量
enum class TokenType {
	kNil = 0,

	kEof,
	kNumber,

	kOpAdd,    // +
	kOpSub,    // -
	kOpMul,    // *
	kOpDiv,    // /

	kSepLPar,  // (
	kSepRPar,  // )
};

// 描述token的结构体
struct Token {
	bool Is(TokenType t_type) const noexcept;

	int line;		// 行号
	TokenType type;		// token类型
	std::string str;	// 保存必要的信息
};

} // namespace lexer

#endif // LEXER_TOKEN_H_
\ToyLang\lexer\token.cpp 
1
2
3
4
5
6
7
8
9
#include "token.h"

namespace lexer {

bool Token::Is(TokenType t_type) const noexcept {
    return t_type == type;
}

} // namespace lexer

token 这部分十分简单，不赘述了。

# Lexer

\ToyLang\lexer\lexer.h 
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
#ifndef LEXER_LEXER_H_
#define LEXER_LEXER_H_

#include <string>
#include <exception>

#include <lexer/token.h>

namespace lexer {

// 词法分析时发生的异常
class LexerException : public std::exception {
public:
	LexerException(const char* t_msg);
};

// 词法分析器类
class Lexer {
public:
	Lexer(const char* t_src);
	~Lexer() noexcept;

private:
	char NextChar() noexcept;
	void SkipChar(int count) noexcept;

public:
	Token LookAHead();
	Token NextToken();
	Token MatchToken(TokenType type);

private:
	std::string m_src;
	size_t m_idx;
	Token m_save;
	int m_line;
};

} // namespace lexer

#endif // LEXER_LEXER_H_
\ToyLang\lexer\lexer.cpp 
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
109
110
#include "lexer.h"

namespace toylang {

LexerException::LexerException(const char* t_msg) : std::exception(t_msg) {

}


Lexer::Lexer(const char* t_src) : m_src{ t_src }, m_line{ 0 }, m_idx{ 0 }, m_save{ 0, TokenType::kNil } {
        
}

Lexer::~Lexer() noexcept {

}

// 获取下一字符
char Lexer::NextChar() noexcept {
    if (m_idx < m_src.size()) {
        return m_src[m_idx++];
    }
    return 0;
}

// 跳过指定字符数
void Lexer::SkipChar(int count) noexcept {
    m_idx += count;
}

// 前瞻下一Token
Token Lexer::LookAHead() {
    if (m_save.type == TokenType::kNil) {        // 如果没有前瞻过
        m_save = NextToken();       // 获取
    }
    return m_save;
}

// 获取下一Token
Token Lexer::NextToken() {
    Token token;
    if (!m_save.Is(TokenType::kNil)) {        // 如果有前瞻保存的token
        // 返回前瞻的结果
        token = m_save;
        m_save.type = TokenType::kNil;
        return token;
    }

    char c;

    // 跳过空格
    while ((c = NextChar()) && c == ' ');

    token.line = m_line;

    if (c == 0) {
        token.type = TokenType::kEof;
        return token;
    }

    // 根据字符返回对应类型的Token
    switch (c) {
    case '+':
        token.type = TokenType::kOpAdd;
        return token;
    case '-':
        token.type = TokenType::kOpSub;
        return token;
    case '*':
        token.type = TokenType::kOpMul;
        return token;
    case '/':
        token.type = TokenType::kOpDiv;
        return token;
    case '(':
        token.type = TokenType::kSepLParen;
        return token;
    case ')':
        token.type = TokenType::kSepRParen;
        return token;
    }

    if (c >= '0' || c <= '9') {
        token.type = TokenType::kNumber;
        token.str.push_back(c);
        while (c = NextChar()) {
            if (c >= '0' && c <= '9') {
                token.str.push_back(c);
            }
            else {
                SkipChar(-1);
                break;
            }
        }
        return token;
    }
        
    throw LexerException("cannot parse token");
}

// 匹配下一Token
Token Lexer::MatchToken(TokenType type) {
    auto token = NextToken();
    if (token.Is(type)) {
        return token;
    }
    throw LexerException("cannot match token");
}

} // namespace lexer

我们封装了一个词法分析器类；
Lexer::LookAHead 前瞻一个 Token。
Lexer::NextToken 是关键成员函数，用于扫描字符序列，匹配一个完整的 Token 并返回，如果前瞻过则返回前瞻的结果。
Lexer::MatchToken 要求下一 token 为指定类型，否则会抛出异常。

# 测试成果

接下来，我们编写测试代码，用于测试新鲜出炉的词法分析器。
用于测试的表达式是： 1 + 33 - 0 * (33 / 999) - 123

\entry.cpp 
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
#include "lexer/lexer.h"

int main() {
    using namespace toylang;

    Lexer lexer{ "1 + 33 - 0 * (33 / 999) - 123" };

    do {
        auto token = lexer.NextToken();
        if (token.Is(TokenType::kEof)) {
            break;
        }

        switch (token.type) {
        case TokenType::kNumber:{
            printf("%s\n", token.str.c_str()); break;
        }
        case TokenType::kOpAdd: {
            printf("+\n"); break;
        }
        case TokenType::kOpDiv: {
            printf("/\n"); break;
        }
        case TokenType::kOpMul: {
            printf("*\n"); break;
        }
        case TokenType::kOpSub: {
            printf("-\n"); break;
        }
        case TokenType::kSepLParen: {
            printf("(\n"); break;
        }
        case TokenType::kSepRParen: {
            printf(")\n"); break;
        }
        }
    } while (true);
}

打印结果 
1
2
3
4
5
6
7
8
9
10
11
12
13
1
+
33
-
0
*
(
33
/
999
)
-
123