编译器-词法分析

要求：单词符号及种别表

1.    总体设计思想

         首先将指定语言的所有出现的单词（可以是一类也可以是特定的）构造其正规式，然后根据正规式构造NFA，最后将NFA确定化为DFA，词DFA即为遇到此类单词时的状态转换图也就是程序的流程分支图，每一种单词的状态转换图又是整个词法分析程序的分支，组合到一块几可以画出整个分析程序的状态转换图。

2.    详细算法设计

下面给出关键单词的NFA：

科学技术法： ( +|-|ε )dd*(.dd* | ε)( e ( +|-|ε ) dd*|ε)

标示符：l(l|d)*

下面给出程序的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1ch=getch();//从源码缓冲区去一个字符

2

3while(isBlank(ch))

4

5{

6

7         ch=getch();//从源码缓冲区去一个字符

8

9}

10

11switch(ch)

12

13{

14

15         根据ch的类型按照状态图流程进行判断；

16

17         return type;

18

19}

20

3.    流程框图

4.    函数相关说明

1
2
3
4
5
6
7
8
9
10
11
12
1scaner(constchar codeBuffer[],int&startPosition,char token[])：扫描指定缓冲区的字符串，识别出从startPosition开始的该语言的单词，codeBuffer为字符串缓冲区指针，startPosition为识别的起始位置，token为识别出的单词存放数组指针。

2

3isBlank(constchar ch)：判断ch是否为空白字符，包括制表符，空格，换行符。

4

5isLetter(constchar ch)：判断ch是否为字母。

6

7isDigi(constchar ch)：判断ch是否为数字

8

9getTypeCode(constchar token[])：如果识别出的是字符串就查表给出字符串的类型码

10

11judgeEe(char ch,constcharcodeBuffer[],int&startPosition,char token[],int&m)：如果为科学计数法的形式，找出E/e后面的部分

12

5.    输入与输出

输入：以#号结束所给文法的源程序字符串

输出：二元组（returnCode,token或sum）构成的序列

例如：输入：abc+123#

         输出：(10,’abc’)

                            (13,’+’)

            (11,123)

出错处理：

如果出现不符合该语言的构造都要提示错误

例如：123e+就不符合该语言构造规则，为错误语言

6.    程序运行结果

程序源码：

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
425
426
427
428
429
430
1/********************************************************

2*文件名：Morphology.h词法分析器相关函数的声明

3*功能:实现词法分析功能

4*时间：2013.9.28

5*作者:KDF5000

6*/

7#include "common.h"

8#pragma once

9class Morphology

10{

11public:

12  Morphology(void);

13  ~Morphology(void);

14

15  //char *keyWordTable[KEYWORD_NUMBER];

16  //扫描代码缓冲区,函数返回字符串的代码，字符串或者数字保存在token数组中

17  int scaner(const char codeBuffer[],int &startPosition,char token[]); 

18  bool isBlank(const char ch);//判断是否为空格等字符

19  

20  static bool isLetter(const char ch);  //判断输入字符是否为字母

21  static bool isDigi(const char ch);    //判断输入字符是否为数字

22  int getTypeCode(const char token[]);  //获取字符串对应的code

23  bool judgeEe(char ch,const char codeBuffer[],int &startPosition,char token[],int &m);//遇到E/e时进行后面的判断

24  void setPreIsOp(bool isPreOP);   //前一个字符串是否为运算符

25private:

26  bool preIsOp;   //前一个字符串是否为运算符

27};

28

29/*******************************************************

30*Morphology.cpp文件，主要函数的实现

31********************************************************/

32#include "Morphology.h"

33#include <string.h>

34//关键字表

35#ifndef KEYWORDTABLE

36#define KEYWORDTABLE    

37char *keyWordTable[KEYWORD_NUMBER] = {"begin","if","then","while","do","end"};

38#endif

39

40Morphology::Morphology(void)

41{

42   preIsOp = true;

43}

44

45

46Morphology::~Morphology(void)

47{

48}

49

50void Morphology::setPreIsOp(bool isPreOp)

51{

52  preIsOp = true;

53}

54int Morphology::scaner(const char codeBuffer[],int &startPosition,char token[])

55{

56  //将token数组清空

57  memset(token,0,sizeof(token));

58  int m = 0; //token的指针

59  char preCh;

60  char ch = codeBuffer[startPosition++];

61  //确保第一个字符不是空格，制表符，换行等符号

62  while(isBlank(ch))

63  {

64      ch = codeBuffer[startPosition++];

65  }

66  

67  //判断第一个字符的类型，根据状态转换图确定字符串

68  //若第一个字符是字母

69  if(isLetter(ch))

70  {

71      //根据状态图确定字符串

72      while(isLetter(ch) || isDigi(ch) )

73      {

74          token[m++] = ch;

75          ch = codeBuffer[startPosition++];

76      }

77      token[m] = '\0';//在token字符串末尾添加结束符

78      //将不是字母或者数字的字符放回缓冲区

79      startPosition--;

80

81      //判断取得的字符串的类型码

82      int stringCode = getTypeCode(token);

83      preIsOp = false;

84      return stringCode;

85  }

86  //如果为‘+’,'-'号或者是数字

87  else if(ch=='+' || ch == '-'|| isDigi(ch))

88  {

89      

90      if(isDigi(ch))

91      {

92          preIsOp=true;

93      }

94      else

95      {

96          preCh = ch;

97          token[m++]= ch;

98          ch = codeBuffer[startPosition++];

99      }

100

101     if(isDigi(ch)&&preIsOp==true)

102     {

103         while(isDigi(ch))

104         {

105             token[m++] = ch;

106             ch = codeBuffer[startPosition++];

107         }

108         //如果是E/e

109         if(ch == 'E' || ch == 'e')

110         {

111             if(!judgeEe(ch,codeBuffer,startPosition,token,m))

112             {

113                 preIsOp = false;

114                 startPosition--;

115                 return ERROR;

116             }

117             preIsOp = false;

118             startPosition--;

119             return DIGIT;

120         }

121         //如果是’.’

122         if(ch == '.')

123         {

124             //如果后面不是数字,则将'.'放回缓冲区

125             token[m++] = ch;

126             ch = codeBuffer[startPosition++];

127             //如果E/e后面不是数字，则将E重新放回缓冲区

128             if(!isDigi(ch))

129             {

130                 startPosition--;

131                 token[m] = '\0';

132                 //返回数字类型碼

133                 preIsOp = false;

134                 return ERROR;

135             }

136             //如果是数字

137             while(isDigi(ch))

138             {

139                 token[m++] = ch;

140                 ch = codeBuffer[startPosition++];

141             }

142             //

143             if(ch == 'E' || ch == 'e')

144             {

145                 if(!judgeEe(ch,codeBuffer,startPosition,token,m))

146                 {

147                     preIsOp = false;

148                     startPosition--;

149                     return ERROR;

150                 }

151             }

152             token[m] = '\0';

153             startPosition--;

154             preIsOp = false;

155             return DIGIT;

156         }

157         token[m] = '\0';

158         startPosition--;

159         preIsOp = false;

160         return DIGIT;

161     }

162     else

163     {

164         if(preCh=='+')

165         {

166             token[m] = '\0';

167             startPosition--;

168             preIsOp=true;

169             return PLUS;                

170         }

171         else

172         {

173             token[m] = '\0';

174             startPosition--;

175             preIsOp=true;

176             return SUB;

177         }

178

179     }

180 }

181 //*

182 else if(ch == '*')

183 {

184     token[m++] = '*';

185     token[m] = '\0';

186     preIsOp=true;

187     return STAR;

188 }

189 //'/'

190 else if(ch == '/')

191 {

192     bool endNode= false;

193     char nextCh;

194     token[m++] = '/';

195     ch = codeBuffer[startPosition++];

196     if(ch=='*')

197     {

198         token[m++]= ch;

199         while(!endNode)

200         {

201             ch = codeBuffer[startPosition++];

202             if(ch=='#')

203             {

204                 startPosition--;

205                 return ERROR;

206             }

207             nextCh = codeBuffer[startPosition];

208             if(ch=='*' && nextCh=='/')

209             {

210                 token[m++]= ch;

211                 token[m++]= nextCh;

212                 startPosition++;

213                 endNode = true;

214             }

215             else

216             {

217                 token[m++]= ch;

218             }

219         }

220         //startPosition--;

221         token[m] = '\0';

222         return NOTE;

223     }

224     else

225     {

226         startPosition--;

227         token[m] = '\0';

228         preIsOp=true;

229         return SLASH;

230     }

231     

232 }

233 else if(ch == '=')

234 {

235     token[m++] = '=';

236     token[m] = '\0';

237     preIsOp = true;

238     return EQUAL;

239 }

240 //':' ,':='

241 else if(ch == ':')

242 {

243     token[m++] = ch;

244     ch = codeBuffer[startPosition++];

245     if(ch == '=')

246     {

247         token[m++] = ch;

248         token[m] = '\0';

249         return MAOHAO_DENGHAO;

250     }

251     startPosition--;

252     token[m] = '\0';

253     return MAOHAO;

254 }

255 //'<', '<>,'<='

256 else if(ch == '<')

257 {

258     token[m++] = ch;

259     ch = codeBuffer[startPosition++];

260     if(ch == '>')

261     {

262         token[m++] = ch ;

263         token[m] = '\0';

264         return SMALL_BIGGER;

265     }

266     if(ch == '=')

267     {

268         token[m++] = ch ;

269         token[m] = '\0';

270         return SMALLER_EQUAL;

271     }

272     startPosition--;

273     token[m] = '\0';

274     return SMALLER;

275 }

276 // '>'

277 else if(ch == '>')

278 {

279     token[m++] = ch;

280     ch = codeBuffer[startPosition++];

281     if(ch == '=')

282     {

283         token[m++] = ch ;

284         token[m] = '\0';

285         return BIGGER_EQUAL;

286     }

287     startPosition--;

288     token[m] = '\0';

289     return BIGGER;

290 }

291 // ';'

292 else if(ch == ';')

293 {

294     token[m++] = ch;

295     token[m] = '\0';

296     return FENHAO;

297 }

298 else if(ch == '(')

299 {

300     token[m++] = ch;

301     token[m] = '\0';

302     preIsOp=true;

303     return KUOHAO_L;

304 }

305 else if(ch == ')')

306 {

307     token[m++] = ch;

308     token[m] = '\0';

309     preIsOp=false;

310     return KUOHAO_R;

311 }

312 //如果为结束字符#

313 else if(ch =='#')

314 {

315     token[m++] = '#';

316     token[m] = '\0';

317     return END_JINGHAO;

318 }

319 token[m++] = ch;

320 token[m] = '\0';

321 return ERROR;

322}

323//判断是否为空格，制表符，换行等字符

324bool Morphology::isBlank(const char ch)

325{

326 if(ch==' '|| ch=='\n'|| ch=='\t')

327 {

328     return true;

329 }

330 else

331 {

332     return false;

333 }

334}

335//判断字符是否为字母

336bool Morphology::isLetter(const char ch)

337{

338 if((ch >= 'A' && ch <= 'Z') || ((ch >= 'a' && ch <= 'z')) )

339 {

340     return true;

341 }

342 else

343 {

344     return false;

345 }

346}

347//判断字符是否为数字

348bool Morphology::isDigi(const char ch)

349{

350 if(ch>='0' && ch<='9')

351 {

352     return true;

353 }

354 else

355 {

356     return false;

357 }

358}

359//获取制定字符串的类型码，病作为含函数值返回

360int Morphology::getTypeCode(const char token[])

361{

362 for(int n=0;n<KEYWORD_NUMBER;n++)

363 {

364     if(strcmp(token,keyWordTable[n])==0)

365     {

366         return (n+1);

367     }

368 }

369 return IDENTIFIER;

370}

371

372//遇到E/e时进行后面的判断

373bool Morphology::judgeEe(char ch,const char codeBuffer[],int &startPosition,char token[],int &m)

374{

375 token[m++] = ch;

376 ch = codeBuffer[startPosition++];

377 //如果E/e后面不是数字，则将E重新放回缓冲区

378 if(ch == '+' || ch == '-')

379 {

380     token[m++] = ch;

381     ch = codeBuffer[startPosition++];

382     if(!isDigi(ch))

383     {

384         token[m] = '\0';

385         //返回数字类型碼

386         return false;

387     }

388 }

389 else

390 {

391     if(!isDigi(ch))

392     {

393         token[--m] = '\0';

394         //返回数字类型碼

395         return false;

396     }

397 }

398 //进入科学计数法E后面的文法

399 while(isDigi(ch))

400 {

401     token[m++] = ch;

402     ch = codeBuffer[startPosition++];

403 }

404 if(ch=='.')

405 {

406     token[m++] = ch;

407     ch = codeBuffer[startPosition++];

408     if(!isDigi(ch))

409     {

410         token[m] = '\0';

411         return false;

412     }

413     else

414     {

415         while(isDigi(ch))

416         {

417             token[m++] = ch;

418             ch = codeBuffer[startPosition++];

419         }

420         token[m] = '\0';

421         return true;

422     }

423 }

424 else

425 {

426     return true;

427 }

428}

429

430