编译原理学习

学习记录

0x00: 关于编译原理

程序员的三大浪漫之一，二进制选手必修课。所以毅然决然开坑了，开始看网易云课堂的mooc，也看了Coursera上的Compilers课程，感觉后者更好一点，就是看起来很费力。书的话还没找到合适的，倒是有几本参考：

  • 龙书
  • 虎书
  • 图解编译原理
  • 自制编译器

但是个人并不是很清楚如何选择，我的方法是看书+看mooc，然后写代码实践，本来这就是一门理论+实践的课程。

0x01:

过程
  1. 词法分析（program text 分割成 words 或者 tokens）
  2. 解析（语法树）
  3. 语法分析（理解“含义”）
  4. 中间优化（little bit like editing，作文的润色？为了运行的更快、使用更少的内存等）
  5. 代码生成 （assembly code）

0x02: 简单的词法分析器

1. 定义：

词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等
(1) 关键字 是由程序语言定义的具有固定意义的标识符。例如，Pascal 中的begin，end，if，while都是保留字。这些字通常不用作一般标识符。
(2) 标识符 用来表示各种名字，如变量名，数组名，过程名等等。
(3) 常数 常数的类型一般有整型、实型、布尔型、文字型等。
(4) 运算符 如+、-、*、/等等。
(5) 界符 如逗号、分号、括号、等等。

2. 输出：

词法分析器所输出单词符号常常表示成如下的二元式：

(单词种别，单词符号的属性值)

单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。界符一般用一符一种的方法。对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。

3. 示例：

比如如下的代码段：

1
if (a>b) print a

经词法分析器处理后，它将被转为如下的单词符号序列：

1
2
3
4
5
6
7
8
  <keywords,if>
<symbol,(>
<symbol,>>
<symbol,)>
<whitespace, >
<keywords,print>
<whitespace, >
<whitespace,\n>
4. 我的实现

很简单，逐个字符扫描的方式，选择条件结构来解析输入，并归类生成对应的二元式。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


#define SYN_SYMBOL    0x000
#define SYN_KEYWORDS  0x100
#define SYN_NUMBERS   0x101
#define SYN_WHITESPS  0x111


#define MAX_CLASS     0x100

char *keywords[6] = {"if","else","do","while","then","print"};

struct CLASS{
    int syn;
    char str[6];
    int sum;
};

struct CLASS* CLASS_ARRARY[MAX_CLASS];


void save(char *token){
    struct CLASS* cla = (struct CLASS*)malloc(sizeof(struct CLASS));
    cla->syn = SYN_SYMBOL;
    strncpy(cla->str,token,strlen(token)<6?strlen(token):6);
    for(int i = 0;i<MAX_CLASS;i++){
        if(CLASS_ARRARY[i] == NULL){
            CLASS_ARRARY[i] = cla;
            break;
        }
    }
}

void scaner(char *userinput){

    char temp;
    int idx = 0;
    char token[6] = {0};

    do{
        temp = userinput[idx++];
        if((temp >= 'a' && temp <= 'z' ) || (temp >= 'A' && temp <= 'Z')){
            //key words
            int m = 0;
            int n = idx;
            while((temp >= 'a' && temp <= 'z' ) || (temp >= 'A' && temp <= 'Z') || (temp >= '0' && temp <= '9')){
                token[m++] = temp;
                temp = userinput[n++];
            }
            //key word scan done
            token[m++] = '\0';
            for(int i = 0;i<6;i++){
                if(!strcmp(token,keywords[i])){
                    //find it
                    struct CLASS* cla = (struct CLASS*)malloc(sizeof(struct CLASS));
                    cla->syn = SYN_KEYWORDS;
                    strncpy(cla->str,token,6);
                    for(int i = 0;i<MAX_CLASS;i++){
                        if(CLASS_ARRARY[i] == NULL){
                            CLASS_ARRARY[i]= cla;
                            break;
                        }
                    }
                    break;
                }
            }
        }else if(temp >= '0' && temp <= '9'){
            //numbers
            int m = 0;
            int n = idx;
            int sum = 0;
            while((temp >= '0' && temp <= '9')){
                sum=sum*10 + temp - '0';
                temp = userinput[n++];
            }
            struct CLASS* cla = (struct CLASS*)malloc(sizeof(struct CLASS));
            cla->syn = SYN_NUMBERS;
            cla->sum = sum;
            for(int i = 0;i<MAX_CLASS;i++){
                if(CLASS_ARRARY[i] == NULL){
                    CLASS_ARRARY[i] = cla;
                    idx = n;
                    break;
                }
            }
        }else {
            //other chars
            switch(temp){
                case '>':{
                    token[0] = temp;
                    char tmp = userinput[idx];
                    if(tmp == '='){
                        token[1] = tmp;
                        idx ++;
                    }
                    save(token);
                }
                    break;
                case '<':{
                    token[0] = temp;
                    char tmp = userinput[idx];
                    if(tmp == '=') {
                        token[1] = tmp;
                        idx++;
                    }
                    save(token);

                }
                    break;
                case '=':{
                    token[0] = temp;
                    char tmp = userinput[idx];
                    if(tmp == '=') {
                        token[1] = tmp;
                        idx++;
                    }
                    save(token);

                }
                    break;
                case ';':
                    token[0] = ';';
                    save(token);
                    break;
                case '!':{
                    token[0] = temp;
                    char tmp = userinput[idx+1];
                    if(tmp == '=')
                        token[1] = tmp;
                    save(token);
                }
                    break;
                case '+':
                    token[0] = temp;
                    save(token);
                    break;
                case '-':
                    token[0] = temp;
                    save(token);
                    break;
                case '*':
                    token[0] = temp;
                    save(token);
                    break;
                case '/':
                    token[0] = temp;
                    save(token);
                    break;
                case '\\':
                    token[0] = temp;
                    save(token);
                    break;
                case '(':
                    token[0] = temp;
                    save(token);
                    break;
                case ')':
                    token[0] = temp;
                    save(token);
                    break;
                case '\n':{
                    struct CLASS* cla = (struct CLASS*)malloc(sizeof(struct CLASS));
                    cla->syn = SYN_WHITESPS;
                    strncpy(cla->str,"\\n",2);
                    for(int i = 0;i<MAX_CLASS;i++){
                        if(CLASS_ARRARY[i] == NULL){
                            CLASS_ARRARY[i] = cla;
                            break;
                        }
                    }
                }
                    break;
                case '\t':{
                    struct CLASS* cla = (struct CLASS*)malloc(sizeof(struct CLASS));
                    cla->syn = SYN_WHITESPS;
                    strncpy(cla->str,"\\t",2);
                    for(int i = 0;i<MAX_CLASS;i++){
                        if(CLASS_ARRARY[i] == NULL){
                            CLASS_ARRARY[i] = cla;
                            break;
                        }
                    }
                }
                    break;
                case ' ':{
                    struct CLASS* cla = (struct CLASS*)malloc(sizeof(struct CLASS));
                    cla->syn = SYN_WHITESPS;
                    strncpy(cla->str," ",2);
                    for(int i = 0;i<MAX_CLASS;i++){
                        if(CLASS_ARRARY[i] == NULL){
                            CLASS_ARRARY[i] = cla;
                            break;
                        }
                    }
                }
                    break;
                case '#':
                    //end
                    break;
                default:
                    printf("unknown:%c\n",temp);
                    break;
            }
        }
    }while(temp != '#');
}


int main() {
    char userinput[100] = {0};
    int flag = 0;
    char temp;
    printf("Plz input your string:");
    do{
        temp = getchar();
        userinput[flag++] = temp;
    }while(temp != '#');

    scaner(userinput);

    for(int i=0;i<MAX_CLASS;i++){
        if(CLASS_ARRARY[i]){
            switch(CLASS_ARRARY[i]->syn){
                case SYN_NUMBERS:
                    printf("<numbers,%d>\n",CLASS_ARRARY[i]->sum);
                    break;
                case SYN_KEYWORDS:
                    printf("<keywords,%s>\n",CLASS_ARRARY[i]->str);
                    break;
                case SYN_WHITESPS:
                    printf("<whitespace,%s>\n",CLASS_ARRARY[i]->str);
                    break;
                case SYN_SYMBOL:
                    printf("<symbol,%s>\n",CLASS_ARRARY[i]->str);
                    break;
            }
        }else{
            break;
        }
    }

    printf("Done.\n");

    return 0;
}

5. 效果
1
2
3
4
5
6
7
8
9
10
11
Plz input your string:if(a>b) print a
#
<keywords,if>
<symbol,(>
<symbol,>>
<symbol,)>
<whitespace, >
<keywords,print>
<whitespace, >
<whitespace,\n>
Done.
6. 更好的实现

使用正则表达式，待补充。

0x03: 待学习内容

  1. 词法分析（利用正则的词法分析器）
  2. 语法分析
  3. 中间优化
  4. 代码生成

开了个坑，慢慢填吧。

0x04: 参考内容

词法分析器的实现