1.理论传授

源程序输入与词法分析程序输出的基本方法；正则文法及其状态转换图的基本概念，正则表达式及有限自动机的基本概念；正规文法构造相应的状态转换图的基本方法；正则表达式构造有限自动机的基本方法及不确定有限自动机确定化的基本方法；词法分析程序的设计与编写。

2.目标任务

给出补充后描述 C 语言子集单词符号的正则文法，设计并实现其词法分析程序。

[设计说明]

（1）可将该语言设计成大小写不敏感，也可设计成大小写敏感，用户定义的标识符最长不超过32个字符；
（2）字母为a-z，A-Z，数字为0-9；
（3）可以对上述文法进行扩充和改造；（4）“/……/”和“//”(一行内)为程序的注释部分。

[设计要求]

（1）给出各单词符号的类别编码；
（2）词法分析程序应能发现输入串中的错误；
（3）词法分析作为单独一遍编写，词法分析结果为二元式序列组成的中间文件；（4）设计两个测试用例（尽可能完备），并给出测试结果。3.任务分析重点解决正则文法到状态转换图的转化问题，词法分析程序的实现。

实验完成：

修改后的正则文法：
<标识符>->字母|<标识符>字母|<标识符>数字
<无符号整数>->数字|<无符号整数>数字
<单字符分界符>->；|，|（|）|{|}|!
<双字符分界符>-><大于>=|<大于>>|<小于>=|<小于><|<小于>>|<感叹号>=|<等于>=|<斜竖>|<加号>|<减号>|<乘号>|<斜竖>=|<与>&| <或>’|’
<小于>-><
<大于>->>
<等于>->=
<斜竖>->/
<感叹号>->!
<加号>->+
<减号>->-
<乘号>->*
<与>->&
<或>->|

因为在新添加的双字符分界符中，有++，–这样的符号，所以把加减乘符号从单字符分界符中单分出来，这样可以避免绘制状态转换图的时候出现一个输入对应多个状态结果的NFA情况。

程序功能描述：

可以对给定路径的TXT文件实现C语言词法分析，可以将一个C语言程序分为关键字，标识符，运算符，无符号整数，浮点数，分隔符，注释。

程序结构描述：

1.编写词法分析程序思路

一开始，我的计划是仿照之前选做作业中的无符号数识别，通过正则文法绘制一个简单的状态转换图，接下来通过一个Switch-case结构，判断每一个输入的格式并分析是否合法。
但是，当我简单绘制了一个修改好的状态转换图之后，我发现本文法的状态太多，如果使用Switch-case格式的话，会导致整体程序过于冗长，并且因为有一些输入后状态的判断是要结合前后输入的，这样一来就会导致需要回退，所以经过综合考量之后，我决定放弃这种编码方式。
而且按照单字符分界和双字符分界进行划分是需要频繁的结合前后输入的，所以为了便于后续的整理，我将所有的分界符分成了运算符和分隔符。
最后我选择使用的编码思路是：使用string类型的变量result存储文件流一个个输出出来的符号，并且每输入一个就进行一轮判断，如果被认定为是标识符或者数字或者分隔符之类的，就可以清空result，并把判定的结果存进string类型的数组中resultArray中，进行后续的输入。最后将所有resultArray中的结果统一进行输出。

2.词法分析程序具体函数功能实现

首先，是对于关键字的说明：

我定义了一个关键字数组，其中包含有int，char，double，string等二十余个编程常用的关键字，用数组模式进行保存

接下来进行简单的函数分析和说明：
isKey函数：遍历关键字数组和此时的result字符串，判断此时读入的输入部分是不是关键字。
isOperator：判断此时的指针所指的输入符号是不是运算符号
isSeparator：判断此时的指针所指的输入符号是不是分割符号

最后是具体实现词法分析的主函数部分：
首先通过文件流，读取需要分析的文件。
接下来进行如下循环：
1.如果此时指针指向的输入符号是字母（可以用C++中自带的isalpha函数判断），文件指针后移一位，字母进入result字符串中
1.1进行后续判断：此时的result是不是关键字，如果是，清空result输出结果，
1.2如果不是关键字，并且后续依旧是字母或数字，那么就重复上述操作，通过循环将输入符号进入result，期间一直进行iskey判断，这里对于循环的次数进行限制，因为标识符不能够超过32位。
1.3 如果后续的输入符号是运算符号或者分隔符号，那么标识符的读取结束。进行iskey判定，是则输出关键字，反之输出标识符
1.4输入符号不满足上述规则的，输出error

2.如果此时指针指向的输入符号是数字，文件指针后移一位，数字进入result字符串中
2.1 如果此时后续还是数字，那么就继续读进result中
2.2 如果此时后续是分隔符或者是运算符，那么此时无符号整数读入已经完成，清空result，把结果存进resultArray中。
2.3 如果此时后续是小数点，那么继续执行2.1和2.2规则，不再对小数点进行判定，避免多个小数点的情况，最后输出的时候判定结果为浮点数。
2.4不满足上述规则的，输出error

3.如果此时指针指向的输入符号是运算符，文件指针后移一位，符号进入result字符串中
3.1对于双字符的符号进行判断，首先看result中存储的符号，再看此时文件指针指向的符号，进行if-else判断。
3.2 对于注释格式/，进行循环输入，直到读入/结束。
3.3 对于所有不满足上述组合的符号，输出error

4.如果此时指针指向的输入符号是分隔符，文件指针后移一位，符号进入result字符串中
最后，将resultArray中的词法分析结果输出，并存入test文件中。

具体代码内容如下：

#include 
#include 
#include 
#include 
#define LENGTH 32
using namespace std;

//判断当前字符串是否为关键字
bool isKey(string s){
    //关键字数组
    string keyArray[] = {"int","char","string","void","bool","float","double","float","true","false","return",
                        "if","else","while","for","default","do","public","static","switch","case","include"};
    //与当前字符串一一对比
    for(int i=0;i<sizeof(keyArray);i++){
        if(s==keyArray[i]){
            return true;
        }
        if("include"==keyArray[i]){
        	break;
		}
    }
    return false;
}

//判断当前字符是否是运算符
bool isOperator(char ch){
    if('+'==ch || '-'==ch || '*'==ch || '/'==ch || '='==ch || '<'==ch || '>'==ch || '!'==ch|| '&'==ch|| '|'==ch)
        return true;
    else
        return false;
}

//判断当前字符是否是分隔符
bool isSeparator(char ch){
    if(','==ch || ';'==ch || '{'==ch || '}'==ch || '('==ch || ')'==ch|| '：'==ch)
        return true;
    else
        return false;
}


int main( )
{
    //定义字符变量，保存从源程序中读取的单个字符
    char ch;
    //定义字符串，保存从源程序中连续读取的字符串
    string result;
    //存放每个获取的单词的值
    string resultArray[999];
    //记录获取单词的个数
    int resultNum=0;

    //代码存放的文件名
    string file = "input1.txt";

    ifstream infile;
    //将文件流对象与文件连接起来
    infile.open(file.data());
    //若失败,则输出错误消息,并终止程序运行
    assert(infile.is_open());

    //txt文本中读取空格符与换行符
    //infile >> noskipws;
    //读取文本中的一个字符
    infile>>ch;

    while (!infile.eof())
    {
        //ch是英文字母
        if(isalpha(ch)){
            result.append(1,ch);
            infile>>ch;
            //判断是否为关键字
            if(isKey(result)){
                resultArray[resultNum++]="(关键字,\""+result+"\")";
                result="";
            }
            //读入首字符为字母，继续读入字母、数字，组成标识符或者关键字
            while(isalpha(ch) || isdigit(ch)){
                result.append(1,ch);
                infile>>ch;
                if(isKey(result)){
	                resultArray[resultNum++]="(关键字,\""+result+"\")";
	                result="";						
                }
                if(result.length()==LENGTH){
                	break;
				}
            }
            //读入操作符或者分割符，正确保存标识符或者关键字
            if(isSeparator(ch) || isOperator(ch)){
                if(isKey(result)){
                    resultArray[resultNum++]="(关键字,\""+result+"\")";
                    result="";
                    continue;
                }
                else{
                    resultArray[resultNum++]="(1,\""+result+"\")";
                    result="";
                    continue;
                }

            }
            //读入不是字母、数字、运算符、标识符，继续读入直到遇到运算符或者分隔符
            else{
                result.append(1,ch);
                infile>>ch;
                while(!isSeparator(ch) && !isOperator(ch)){
                    result.append(1,ch);
                    infile>>ch;
                }
                resultArray[resultNum++]="(Error，标识符中有违规符号,\""+result+"\")";
                result="";
                continue;
            }
        }
        //读入数字
        else if(isdigit(ch)){
            result.append(1,ch);
            infile>>ch;
            //继续读入数字，组成常数
            while(isdigit(ch)){
                result.append(1,ch);
                infile>>ch;
            }
            //遇到操作符或者运算符，正常终止
            if(isOperator(ch) || isSeparator(ch)){
                resultArray[resultNum++]="(无符号整数,\""+result+"\")";
                result="";
                continue;
            }
            //也可以读小数
			else if('.'==ch){
            	result.append(1,ch);
            	infile>>ch;	
            	int num=0;
				while(isdigit(ch)){
					num++;
					result.append(1,ch);
            		infile>>ch;
				}
				if(num==0){
					resultArray[resultNum++]="(Error，小数点后没有数字,\""+result+"\")";
	                result="";
	                continue;
				}
	            if(isOperator(ch) || isSeparator(ch)){
	                resultArray[resultNum++]="(浮点数,\""+result+"\")";
	                result="";
	                continue;
	            }
				else{
	                result.append(1,ch);
	                infile>>ch;
	                while(!isSeparator(ch) && !isOperator(ch)&& !infile.eof()) {
	                    result.append(1,ch);
	                    infile>>ch;
	                }
	                resultArray[resultNum++]="(Error，浮点数后有未知符号,\""+result+"\")";
	                result="";
	                continue;
	            }			
			} 
            //读入其他错误字符
            else{
                result.append(1,ch);
                infile>>ch;
                while(!isSeparator(ch) && !isOperator(ch)&& !infile.eof()) {
                    result.append(1,ch);
                    infile>>ch;
                }
                resultArray[resultNum++]="(Error，整数后有错误符号,\""+result+"\")";
                result="";
                continue;
            }
        }
        //遇到运算符
        else if(isOperator(ch)){
            result.append(1,ch);
            infile>>ch;
            //判断是否存在<=、>=、!=、==、+=、-=、*=
            if("<"==result || ">"==result || "!"==result|| "="==result ||"+"==result ||"-"==result ||"*"==result){
                if('='==ch){
                    result.append(1,ch);
                    infile>>ch;
                }
            }
            if("+"==result){
            	if('+'==ch){
            		result.append(1,ch);
                    infile>>ch;
				}
			}
            if("-"==result){
            	if('-'==ch){
            		result.append(1,ch);
                    infile>>ch;
				}
			}
			if(">"==result){
            	if('>'==ch){
            		result.append(1,ch);
                    infile>>ch;
				}
			}
			if("<"==result){
            	if('<'==ch||'>'==ch){
            		result.append(1,ch);
                    infile>>ch;
				}
			}
			if("&"==result){
            	if('&'==ch){
            		result.append(1,ch);
                    infile>>ch;
				}
				else{
					resultArray[resultNum++]="(Error：逻辑与运算符号错误：\""+result+"\")";
                	result="";
				}
			}
			if("|"==result){
            	if('|'==ch){
            		result.append(1,ch);
                    infile>>ch;
				}
				else{
					resultArray[resultNum++]="(Error：逻辑或运算符号错误：\""+result+"\")";
                	result="";
				}
			}
            if("/"==result){
            	if('*'==ch){
            		result.append(1,ch);
                    infile>>ch;
            		while(1){
            			//这里一定要把文件指针往后移动两位，不然的话/*/形式的也会被无认为是注释（虽然应该不会有人这么写） 
            			result.append(1,ch);
                    	infile>>ch;
                    	char ch2 = result.at(result.length()-1);
                    	if('*'==ch2 && '/'==ch){
                    		result.append(1,ch);
                    		infile>>ch;
                    		resultArray[resultNum++]="(可以跨行的注释内容：\""+result+"\")";
                			result="";
                    		break;
						}
					}
					continue;
				}
				else if('='==ch){
					result.append(1,ch);
                    infile>>ch;
				}
			}
            //下一个读入符为字母、数字、分隔符，即正确
            if(isalpha(ch) || isdigit(ch) || isSeparator(ch)){
                resultArray[resultNum++]="(运算符,\""+result+"\")";
                result="";
                continue;
            }
            else{
                //将错误输入符一起读入，直到正确
                while(!isSeparator(ch) && !isalpha(ch) && !isdigit(ch) && !infile.eof()){
                    result.append(1,ch);
                    infile>>ch;
                }
                resultArray[resultNum++]="(Error,\""+result+"\")";
                result="";
                continue;
            }
        }
        //读取到分隔符
        else if(isSeparator(ch)){
            result.append(1,ch);
            resultArray[resultNum++]="(分隔符,\""+result+"\")";
            result="";
            infile>>ch;
        }
        //读取到未定义输入
        else{
            //出错处理
            result.append(1,ch);
            resultArray[resultNum++]="(Error，遇到了未定义输入（非字母数字，运算符，分隔符），且不在注释中,\""+result+"\")";
            result="";
            infile>>ch;

        }
    }
    //关闭文件输入流
    infile.close();

    //以 （单词类编码，值） 输出结果
    for(int i=0;i<resultNum;i++){
        cout<<resultArray[i]<<endl;
    }

    ofstream ofs;						//定义流对象
    ofs.open("text.txt",ios::out);		//以写的方式打开文件
    for(int i=0;i<resultNum;i++){
        ofs<<resultArray[i]<<endl;
    }
    ofs.close();

	
   	return 0;
}

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

实验结果：

使用的输入文件：
main(){
	int  a2,b;
	a2 == 10**4;
	b = a + 20;
%
	int 3ab;
	if(a<=3){
		a=5.4343#;
	}
}
/*yfjo
fwjoer*/
1
2
3
4
5
6
7
8
9
10
11
12
13

得到结果为：

使用的测试输入文件2为：

int isprime(int);
main()
{
    int i,c=0;
    for(i=2;i<=100;i++)
    {
        if(isprime(i))
        {
            printf("%4d",i);
            c++;
            if(c%10==0)printf("\n");
        }
    }
    printf("\n");
}
int isprime(int n)
{
    int i;
    for(i=2;i<=sqrt(n);i++)
        if(n%i==0)return 0;
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

测试样例2得到的结果为：
(关键字,“int”)
(标识符,“isprime”)
(分隔符,“(”)
(关键字,“int”)
(标识符,“”)
(分隔符,“)”)
(分隔符,“;”)
(标识符,“main”)
(分隔符,“(”)
(分隔符,“)”)
(分隔符,“{”)
(关键字,“int”)
(标识符,“i”)
(分隔符,“,”)
(标识符,“c”)
(运算符,“=”)
(无符号整数,“0”)
(分隔符,“;”)
(关键字,“for”)
(标识符,“”)
(分隔符,“(”)
(标识符,“i”)
(运算符,“=”)
(无符号整数,“2”)
(分隔符,“;”)
(标识符,“i”)
(运算符,“<=”)
(无符号整数,“100”)
(分隔符,“;”)
(标识符,“i”)
(运算符,“++”)
(分隔符,“)”)
(分隔符,“{”)
(关键字,“if”)
(标识符,“”)
(分隔符,“(”)
(标识符,“isprime”)
(分隔符,“(”)
(标识符,“i”)
(分隔符,“)”)
(分隔符,“)”)
(分隔符,“{”)
(标识符,“printf”)
(分隔符,“(”)
(Error，遇到了未定义输入（非字母数字，运算符，分隔符），且不在注释中,“”“)
(Error，遇到了未定义输入（非字母数字，运算符，分隔符），且不在注释中,”%“)
(Error，整数后有错误符号,“4d””)
(分隔符,“,”)
(标识符,“i”)
(分隔符,“)”)
(分隔符,“;”)
(标识符,“c”)
(运算符,“++”)
(分隔符,“;”)
(关键字,“if”)
(标识符,“”)
(分隔符,“(”)
(Error，标识符中有违规符号,“c%10”)
(运算符,“" )
(无符号整数,“0”)
(分隔符,“)”)
(标识符,“printf”)
(分隔符,“(”)
(Error，遇到了未定义输入（非字母数字，运算符，分隔符），且不在注释中,“”“)
(Error，遇到了未定义输入（非字母数字，运算符，分隔符），且不在注释中,”“)
(Error，标识符中有违规符号,“n””)
(分隔符,“)”)
(分隔符,“;”)
(分隔符,“}”)
(分隔符,“}”)
(标识符,“printf”)
(分隔符,“(”)
(Error，遇到了未定义输入（非字母数字，运算符，分隔符），且不在注释中,“”“)
(Error，遇到了未定义输入（非字母数字，运算符，分隔符），且不在注释中,”“)
(Error，标识符中有违规符号,“n””)
(分隔符,“)”)
(分隔符,“;”)
(分隔符,“}”)
(关键字,“int”)
(标识符,“isprime”)
(分隔符,“(”)
(关键字,“int”)
(标识符,“n”)
(分隔符,“)”)
(分隔符,“{”)
(关键字,“int”)
(标识符,“i”)
(分隔符,“;”)
(关键字,“for”)
(标识符,“”)
(分隔符,“(”)
(标识符,“i”)
(运算符,“=”)
(无符号整数,“2”)
(分隔符,“;”)
(标识符,“i”)
(运算符,“<=”)
(标识符,“sqrt”)
(分隔符,“(”)
(标识符,“n”)
(分隔符,“)”)
(分隔符,“;”)
(标识符,“i”)
(运算符,“++”)
(分隔符,“)”)
(关键字,“if”)
(标识符,“”)
(分隔符,“(”)
(Error，标识符中有违规符号,“n%i”)
(运算符,"”)
(无符号整数,“0”)
(分隔符,“)”)
(关键字,“return”)
(标识符,“0”)
(分隔符,“;”)
(关键字,“return”)
(标识符,“1”)
(分隔符,“;”)
(分隔符,“}”)