C语言词法分析程序

发表于 | 分类于
字数统计 2,920 | 阅读时长 13

C语言词法分析程序

词法分析原理：

词法分析是作为相对独立的阶段来完成的（对源程序或中间结果从头到尾扫描一次，并作相应的加工处理，生成新的中间结果或目标程序）。在词法分析过程中，编译程序是通过操作系统从外部介质中读取源程序文件中的各个字符的。同时，为正确地识别单词，有时还需进行超前搜索和回退字符等操作。因此，为了提高读盘效率和便于扫描器进行工作，通常可采用缓冲输入的方案，即在内存中设置一个适当大小的输入缓冲区，让操作系统直接将磁盘上的源程序字符串分批送入此缓冲区中，供扫描器进行处理。

词法分析程序的一般设计方案是：

  1. 程序设计语言词法规则⇒正规文法⇒ FA；
    或：词法规则⇒正规表达式⇒ FA；

  2. NFA确定化⇒ DFA；

  3. DFA最简化；

  4. 确定单词符号输出形式；

  5. 化简后的DFA＋单词符号输出形式⇒构造词法分析程序。

从设计方案可知，要构造词法分析程序，必须掌握以下三个知识点：文法.
正规表达式和FA。

文法与语言的形式定义如下：

一个形式文法 G 是下述元素构成的一个元组(VN ，VT ，P，S )。其中：

  1. VT —非空有限的终结符号集，即 Σ；

终结符：一个语言不可再分的基本符号。

  1. VN—非空有限的非终结符号集；

非终结符：也称语法变量，用来代表语法范畴。一个非终结符代表一个一定的语法概念，是一个类（集合）记号，而不是一个体记号。

  1. S —开始符号/识别符号，S∈ VN ；

  2. P —产生式规则集（或叫规则或生成式或重写规则）；

产生式：形如α → β或α ::=
β的表达式，其中α为左部，β为右部。α∈(VT∪VN)+且至少含一个VN；β∈(VT∪VN)*。

  1. VT∪VN =Ф。

仅由字母表A={ai=1，2，…，k}上的正规式α所组成的语言称为正规集，记为L(α
)。正规集的形式化描述式称为正规式。

字母表Σ上的正规表达式和正规集递归定义如下：

  1. Σ 中的a是正规表达式，其正规集为{a}；

  2. 空串ε是Σ上的正规表达式，其正规集为{ε}；

  3. 空集Φ是Σ上的正规表达式，其正规集为Φ ；

  4. 如果e1和e2是Σ上的正规表达式，它们所表示的正规集分别为L(e1)与L(e2) ，则：

e1|e2也是Σ上的正规表达式，其正规集为L(e1|e2)=L(e1) ∪L(e2)。

e1e2也是Σ上的正规表达式，其正规集为L(e1e2)=L(e1) L(e2)。

(e1)* 也是Σ上的正规表达式，其正规集为L((e1)* )=L(e1)*。

而确定有限自动机(DFA)理论定义DFA M=（Q ，Σ ，t ，q0 ，F）。其中：

  1. Q —有穷非空状态集；

  2. Σ —有穷输入字母表；

  3. t — 映射Q × Σ → Q(单值映射，下态确定)；

  4. q0 —q0∈Q,称为开始状态(唯一)；

  5. F —非空终止状态集；

非确定有限自动机(NFA M) 定义与DFA M的比较可知：
NFA可有多个初态，并可能含ε弧或字符串弧；在NFA中，t是多值的，即t（s,
a）无法唯一地确定下一状态。

对于FA，最重要的是给出其映射。可以由状态转换表，状态转换图或者直接给出。

  1. 直接给出：t(q ,a)=q’；

  2. 状态转换表：状态为表列，字母为表行；

3.
状态转换图：是由一组矢线连接的有限个结点所组成的有向图。每一结点均代表在识别或分析过程中扫描器所处的状态。它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示。下面是标识符的状态图：

（正规式与有限自动机的等价性）定义：对任何两个有限的自动机M1和M2，若有L(M1)=L(M2)，则称M1与M2等价。

可通过子集法或造表法求解NFA的等价DFA（NFA的确定化方法）。

NFA的确定化方法算法（造表法）：

  1. 画一张具有n+1列的矩阵表P，n =NFA中出现的符号的个数。各应列的名字分别为I，Ia，Ib，IC，…，其中，a，b，c…是NFA中出的所有字符。

    1. 令I = ε－CLOSURE（S0）。S0：NFA的初态集。ε－CLOSURE(S0) = S0∪Sε
      Sε= {s| 从S0的某一状态出发经过任意条ε弧可达s}

    2. 把I填入乘P的I列

    3. 计算Ia，Ib，IC，…，并填入相应的列。Ia = ε－CLOSURE(Ja) Ja = {s | 从I的某一状态出发经过一条a弧可到s}

  2. 若J∈{ Ia，Ib，IC，…}未在I列出现，则令I =
    J。并重复3~5直列所有的J均在I列中出现过。

    1. 把P中的各子集作为状态，并重新命名。

    2. 确定终态和初态：

初态：I列的第一个元素。 终态：含有原NFA任一终态的子集。

  1. 画出相应的DFA

正规文法到有穷自动机的转变步骤：

  1. VT ⇒ Σ；

  2. VN ⇒ Q,其中S⇒q0；

  3. A中增加新状态Z作为终态；

  4. U →aV ⇒ t(U，a)=V；

     a∈VT或 a=ε，V∈VN 。

  5. U →a (a∈VT) ⇒ t(U,a)=Z。

正规表达式到有穷自动机的转变，对于任意的一个正则表达式e，从开始，按照变换规则，逐步扩弧. 扩结，直到转换图上所有的弧上都是∑中的单个符号为止。对于引入的每一个新状态，应该赋予一个独有的名字。其变换规则如下：

对于一个语言来说，如何对其单词进行分类和编码并没有一个原则性的规定，而主要取决于处理上的方便。通常按照语法分析的需要设置，用整数表示。

代码

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
public class Analysis {
	String sourceFile;  //源文件名
	String sentence;  //程序语句
	
	String word="";   //分析得到的字符串
	String keyWord[] = { "if", "int", "for", "while", "do", "return", "break", "continue" };// 语句控制关键字
	String id[]=new String[100];
	int idLength=0;//记录标志符表中存放的标志符的个数
	
	String num[]=new String[100];
	int numLength=0;//记录常数表中存放的常数的个数
	
	int line=0;//当前读到的行数
	
	//判断是否为数字字符
	public boolean isDigit(char ch){
		if((ch>='0')&&(ch<='9'))
			return true;
		else
			return false;
	}
	
	//判断是否为字母字符
	public boolean isLetter(char ch){
		if(((ch>='A')&&(ch<='Z'))||((ch>='a')&&(ch<='z')))
			return true;
		else
			return false;
	}
	
	//判断是否为关键字
	public void isKeyword(String str){
		int i=0;
		for(;i<keyWord.length;i++){
			if(str.equals(keyWord[i]))        //是关键字
			{
				System.out.println("(关键字："+str+")");
				i=keyWord.length;//结束循环，i等于keyWord.length+1
			}
		}//结束循环,i等于keyWord.length
		
		
		if(i==keyWord.length){//普通标志符
			int j=0;
			for(;j<idLength;j++){//在标志符表中查找是否有该标志符
				if(str.equals(id[j]))//标志符表中已经有该标志符
				{
					System.out.println("(标识符："+str+")");//输出该标志符在标志符表中的位置
					j=idLength;//结束循环，j等于idLength+1
				}
			}
			if(j==idLength){//标志符表中没有该标志符，将该标志符存入标志符表中，并返回其在符号表中的位置
				idLength++;//标志符新增一个
				id[idLength-1]=str;//将新标志符存放到标志符表中，索引从0开始
				System.out.println("(标识符："+str+")");
			}
		}
	}
	
	//是否为数字
	public void isNumber(String str){
		int i=0;
		for(;i<numLength;i++){
			if(str.equals(num[i])){
				System.out.println("(常量："+str+")");
				i=numLength;
			}
		}
		if(i==numLength){
			numLength++;
			num[numLength-1]=str;
			System.out.println("(常量："+str+")");
		}
	}
	
	public void analyse(String str){
		char ch;//存放当前字符
		char ch2;//存放下一个字符
		for(int i=0;i<str.length();i++,word=""){
			ch=str.charAt(i);//从0索引
			if(ch=='\n'||ch=='\t'||ch==' ');//忽略回车、Tab、空格字符
			else if(isDigit(ch)){
				word=word+ch;
				for(int j=1;j<=str.length()-i;j++){
					int k=i+j;
					if(k==(str.length()+1)){//错误语句，没有;界符
						isNumber(word);
						j=str.length();//跳出循环
						i=i+j-1;
					}
					else{
						ch2=str.charAt(k);
						if(isDigit(ch2)||ch2=='.'){
							word=word+ch2;
						}
						else{
							isNumber(word);
							i=i+j-1;//跳过j-1个字符
							j=str.length();//跳出循环
						}
					}
				}
			}
			else if(isLetter(ch)||ch=='_'){//变量以字符或者下划线开头
				word=word+ch;
				for(int j=1;j<=str.length()-i;j++){
					int k=i+j;
					if(k==str.length()){
						isKeyword(word);
						i=i+j-1;
						j=str.length();//识别到行尾，跳出循环
					}
					else{
						ch2=str.charAt(k);
						if(isLetter(ch2)||isDigit(ch2)||ch2=='_'){//变量由字母、数字或下划线组成
							word=word+ch2;
						}
						else{
							isKeyword(word);
							i=i+j-1;//跳过j-1个字符
							j=str.length();//跳出循环，识别下一个单词
						}
					}	
				}		
			}
			else if(ch=='+'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='-'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='*'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='/'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");//除等/=
					i++;
				}
				else if(ch2=='/'){
					System.out.print("单行注释\t");
					System.out.print("注释内容为：");
					for(int m=i;m<str.length();m++){
						System.out.print(str.charAt(m));
					}
					System.out.println();
					i=str.length();//注释行//，读取下一行
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='%'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='<'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='>'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='='){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='!'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='='){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("(符号："+ch+")");
				}
			}
			else if(ch=='&'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='&'){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("非法字符&");
					System.out.println("位置："+line+"行"+i+"字符");
				}
			}
			else if(ch=='|'){
				word=word+ch;
				ch2=str.charAt(i+1);
				if(ch2=='|'){
					System.out.println("(符号： "+ch+ch2+")");
					i++;
				}
				else{
					System.out.println("非法字符|");
					System.out.println("位置："+line+"行"+i+"字符");
				}
			}
			else if(ch=='('){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch==')'){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch=='['){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch==']'){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch=='{'){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch=='}'){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch==','){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch==';'){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch=='"'){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else if(ch=='.'){
				word=word+ch;
				System.out.println("(符号："+ch+")");
			}
			else{
				System.out.println("非法字符"+ch);
				System.out.println("位置："+(line+1)+"行"+(i+1)+"字符");
			}
		}
	}
	
	
	public static void main(String args[]){
		Analysis c=new Analysis();
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入您要编译的源程序文件名");
		c.sourceFile=sc.next();//输入文件路径、名
		try{
			File f=new File(c.sourceFile);//用指定的文件名构建文件对象
			RandomAccessFile raf=new RandomAccessFile(f,"r");//创建文件随机访问
			int fileLine=0;//文件行数
			while(raf.readLine()!=null){
				fileLine++;
			}
			System.out.println("源程序共有"+fileLine+"行");
			System.out.println("源程序内容为：");
			raf.seek(0);  //从第0个字符开始读取
			for(int i=0;i<fileLine;i++){
				System.out.println(raf.readLine());
			}
			System.out.println("分析结果为：");
			raf.seek(0);
			for(int i=0;i<fileLine;i++){
				c.sentence=raf.readLine();
				System.out.println("第"+(i+1)+"行：");
				c.analyse(c.sentence);
				c.line++;
			}
		}catch (IOException e){
			System.out.println("文件未找到，请输入正确的文件路径");
		};
		}
	
}
世界再嘈杂，匠人的内心，绝对是必须是安静的、安定的。