0%

编译原理学习笔记(二)

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

词法分析器

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

记号

用来存放记号的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
//
// 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
//
// 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开始,逐级向下递归分析每一部分。比如lineexpressionCR组成,expression则由若干个termADD/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
//
// 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.");
}