词法分析器的原理解释及代码实现

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
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
// Lexical_Analysis.cpp : 定义控制台应用程序的入口点。
//
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "iostream"
using namespace std;
//词法分析程序
//首先定义种别码
/*
第一类：标识符   letter(letter | digit)*  无穷集
第二类：常数    (digit)+  无穷集
第三类：保留字(32)
auto       break    case     char        const      continue
default    do       double   else        enum       extern
float      for      goto     if          int        long
register   return   short    signed      sizeof     static
struct     switch   typedef  union       unsigned   void
volatile    while

第四类：界符  ‘/*’、‘//’、 () { } [ ] " "  '
第五类：运算符 <、<=、>、>=、=、+、-、*、/、^、

对所有可数符号进行编码：
<$,0>
<auto,1>
...
<while,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>
"[","]","{","}"
<常数99  ,数值>
<标识符100 ，标识符指针>


*/

/****************************************************************************************/
//全局变量，保留字表
static char reserveWord[32][20] = {
    "auto", "break", "case", "char", "const", "continue",
    "default", "do", "double", "else", "enum", "extern",
    "float", "for", "goto", "if", "int", "long",
    "register", "return", "short", "signed", "sizeof", "static",
    "struct", "switch", "typedef", "union", "unsigned", "void",
    "volatile", "while"
};
//界符运算符表,根据需要可以自行增加
static char operatorOrDelimiter[36][10] = {
    "+", "-", "*", "/", "<", "<=", ">", ">=", "=", "==",
    "!=", ";", "(", ")", "^", ",", """, "'", "#", "&",
    "&&", "|", "||", "%", "~", "<<", ">>", "[", "]", "{",
    "}", "\", ".", "?", ":", "!"
};

static  char IDentifierTbl[1000][50] = { "" };//标识符表
/****************************************************************************************/

/********查找保留字*****************/
int searchReserve(char reserveWord[][20], char s[])
{
    for (int i = 0; i < 32; i++)
    {
        if (strcmp(reserveWord[i], s) == 0)
        {//若成功查找，则返回种别码
            return i + 1;//返回种别码
        }
    }
    return -1;//否则返回-1，代表查找不成功，即为标识符
}
/********查找保留字*****************/

/*********************判断是否为字母********************/
bool IsLetter(char letter)
{//注意C语言允许下划线也为标识符的一部分可以放在首部或其他地方
    if (letter >= 'a'&&letter <= 'z' || letter >= 'A'&&letter <= 'Z'|| letter=='_')
    {
        return true;
    }
    else
    {
        return false;
    }
}
/*********************判断是否为字母********************/


/*****************判断是否为数字************************/
bool IsDigit(char digit)
{
    if (digit >= '0'&&digit <= '9')
    {
        return true;
    }
    else
    {
        return false;
    }
}
/*****************判断是否为数字************************/


/********************编译预处理，取出无用的字符和注释**********************/
void filterResource(char r[], int pProject)
{
    char tempString[10000];
    int count = 0;
    for (int i = 0; i <= pProject; i++)
    {
        if (r[i] == '/'&&r[i + 1] == '/')
        {//若为单行注释“//”,则去除注释后面的东西，直至遇到回车换行
            while (r[i] != 'n')
            {
                i++;//向后扫描
            }
        }
        if (r[i] == '/'&&r[i + 1] == '*')
        {//若为多行注释“/* 。。。*/”则去除该内容
            i += 2;
            while (r[i] != '*' || r[i + 1] != '/')
            {
                i++;//继续扫描
                if (r[i] == '$')
                {
                    printf("注释出错，没有找到 */，程序结束！！！n");
                    exit(0);
                }
            }
            i += 2;//跨过“*/”
        }
        if (r[i] != 'n'&&r[i] != 't'&&r[i] != 'v'&&r[i] != 'r')
        {//若出现无用字符，则过滤；否则加载
            tempString[count++] = r[i];
        }
    }
    tempString[count] = '';
    strcpy(r, tempString);//产生净化之后的源程序
}
/********************编译预处理，取出无用的字符和注释**********************/


/****************************分析子程序，算法核心***********************/
void Scanner(int &syn, char resourceProject[], char token[], int &pProject)
{//根据DFA的状态转换图设计
    int i, count = 0;//count用来做token[]的指示器，收集有用字符
    char ch;//作为判断使用
    ch = resourceProject[pProject];
    while (ch == ' ')
    {//过滤空格，防止程序因识别不了空格而结束
        pProject++;
        ch = resourceProject[pProject];
    }
    for (i = 0; i<20; i++)
    {//每次收集前先清零
        token[i] = '';
    }
    if (IsLetter(resourceProject[pProject]))
    {//开头为字母
        token[count++] = resourceProject[pProject];//收集
        pProject++;//下移
        while (IsLetter(resourceProject[pProject]) || IsDigit(resourceProject[pProject]))
        {//后跟字母或数字
            token[count++] = resourceProject[pProject];//收集
            pProject++;//下移
        }//多读了一个字符既是下次将要开始的指针位置
        token[count] = '';
        syn = searchReserve(reserveWord, token);//查表找到种别码
        if (syn == -1)
        {//若不是保留字则是标识符
            syn = 100;//标识符种别码
        }
        return;
    }
    else if (IsDigit(resourceProject[pProject]))
    {//首字符为数字
        while (IsDigit(resourceProject[pProject]))
        {//后跟数字
            token[count++] = resourceProject[pProject];//收集
            pProject++;
        }//多读了一个字符既是下次将要开始的指针位置
        token[count] = '';
        syn = 99;//常数种别码
    }
    else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == ';' || ch == '(' || ch == ')' || ch == '^'
        || ch == ',' || ch == '"' || ch == ''' || ch == '~' || ch == '#' || ch == '%' || ch == '['
        || ch == ']' || ch == '{' || ch == '}' || ch == '\' || ch == '.' || ch == '?' || ch == ':')
    {//若为运算符或者界符，查表得到结果
        token[0] = resourceProject[pProject];
        token[1] = '';//形成单字符串
        for (i = 0; i<36; i++)
        {//查运算符界符表
            if (strcmp(token, operatorOrDelimiter[i]) == 0)
            {
                syn = 33 + i;//获得种别码，使用了一点技巧，使之呈线性映射
                break;//查到即推出
            }
        }
        pProject++;//指针下移，为下一扫描做准备
        return;
    }
    else  if (resourceProject[pProject] == '<')
    {//<,<=,<<
        pProject++;//后移，超前搜索
        if (resourceProject[pProject] == '=')
        {
            syn = 38;
        }
        else if (resourceProject[pProject] == '<')
        {//左移
            pProject--;
            syn = 58;
        }
        else
        {
            pProject--;
            syn = 37;
        }
        pProject++;//指针下移
        return;
    }
    else  if (resourceProject[pProject] == '>')
    {//>,>=,>>
        pProject++;
        if (resourceProject[pProject] == '=')
        {
            syn = 40;
        }
        else if (resourceProject[pProject] == '>')
        {
            syn = 59;
        }
        else
        {
            pProject--;
            syn = 39;
        }
        pProject++;
        return;
    }
    else  if (resourceProject[pProject] == '=')
    {//=.==
        pProject++;
        if (resourceProject[pProject] == '=')
        {
            syn = 42;
        }
        else
        {
            pProject--;
            syn = 41;
        }
        pProject++;
        return;
    }
    else  if (resourceProject[pProject] == '!')
    {//!,!=
        pProject++;
        if (resourceProject[pProject] == '=')
        {
            syn = 43;
        }
        else
        {
            syn = 68;
            pProject--;
        }
        pProject++;
        return;
    }
    else  if (resourceProject[pProject] == '&')
    {//&,&&
        pProject++;
        if (resourceProject[pProject] == '&')
        {
            syn = 53;
        }
        else
        {
            pProject--;
            syn = 52;
        }
        pProject++;
        return;
    }
    else  if (resourceProject[pProject] == '|')
    {//|,||
        pProject++;
        if (resourceProject[pProject] == '|')
        {
            syn = 55;
        }
        else
        {
            pProject--;
            syn = 54;
        }
        pProject++;
        return;
    }
    else  if (resourceProject[pProject] == '$')
    {//结束符
        syn = 0;//种别码为0
    }
    else
    {//不能被以上词法分析识别，则出错。
        printf("error：there is no exist %c n", ch);
        exit(0);
    }
}


int main()
{
    //打开一个文件，读取其中的源程序
    char resourceProject[10000];
    char token[20] = { 0 };
    int syn = -1, i;//初始化
    int pProject = 0;//源程序指针
    FILE *fp, *fp1;
    if ((fp = fopen("F:\zyr_rc.txt", "r")) == NULL)
    {//打开源程序
        cout << "can't open this file";
        exit(0);
    }
    resourceProject[pProject] = fgetc(fp);
    while (resourceProject[pProject] != '$')
    {//将源程序读入resourceProject[]数组
        pProject++;
        resourceProject[pProject] = fgetc(fp);
    }
    resourceProject[++pProject] = '';
    fclose(fp);
    cout << endl << "源程序为:" << endl;
    cout << resourceProject << endl;
    //对源程序进行过滤
    filterResource(resourceProject, pProject);
    cout << endl << "过滤之后的程序:" << endl;
    cout << resourceProject << endl;
    pProject = 0;//从头开始读

    if ((fp1 = fopen("F:\zyr_compile.txt", "w+")) == NULL)
    {//打开源程序
        cout << "can't open this file";
        exit(0);
    }
    while (syn != 0)
    {
        //启动扫描
        Scanner(syn, resourceProject, token, pProject);
        if (syn == 100)
        {//标识符
            for (i = 0; i<1000; i++)
            {//插入标识符表中
                if (strcmp(IDentifierTbl[i], token) == 0)
                {//已在表中
                    break;
                }
                if (strcmp(IDentifierTbl[i], "") == 0)
                {//查找空间
                    strcpy(IDentifierTbl[i], token);
                    break;
                }
            }
            printf("(标识符  ,%s)n", token);
            fprintf(fp1, "(标识符   ,%s)n", token);
        }
        else if (syn >= 1 && syn <= 32)
        {//保留字
            printf("(%s   ,  --)n", reserveWord[syn - 1]);
            fprintf(fp1, "(%s   ,  --)n", reserveWord[syn - 1]);
        }
        else if (syn == 99)
        {//const 常数
            printf("(常数   ,   %s)n", token);
            fprintf(fp1, "(常数   ,   %s)n", token);
        }
        else if (syn >= 33 && syn <= 68)
        {
            printf("(%s   ,   --)n", operatorOrDelimiter[syn - 33]);
            fprintf(fp1, "(%s   ,   --)n", operatorOrDelimiter[syn - 33]);
        }
    }
    for (i = 0; i<100; i++)
    {//插入标识符表中
        printf("第%d个标识符：  %sn", i + 1, IDentifierTbl[i]);
        fprintf(fp1, "第%d个标识符：  %sn", i + 1, IDentifierTbl[i]);
    }
    fclose(fp1);
    return 0;
}