Note: This article is available in Chinese only. 本文暂无英文版本。
View original
实验一 设计实现简单语言的词法分析器#
1、实验目的
通过该实验,熟练应用编译原理关于词法分析的基本理论和方法；学会用C/C++高级程序设计语言设计一个词法分析器；加深对编译原理理论的分析理解，提高实际操作和解决具体问题的能力。
2、实验条件
计算机上安装C/C++编译处理软件。
3、实验内容及要求
对下述单词表定义的语言设计编制一个词法分析器。单词符号及种别表和词法分析器功能及基本要求如下：
（1）单词符号及种别表
| 单词符号 | 种别编码 | 单词值 |
| main | 1 | |
| int | 2 | |
| float | 3 | |
| double | 4 | |
| char | 5 | |
| if | 6 | |
| else | 7 | |
| do | 8 | |
| while | 9 | |
| l(l|d)* | 10 | 内部字符串 |
| ( +|-|ε ) dd*(.dd* | ε)( e ( +|-|ε ) dd*|ε) | 20 | 二进制数值表示 |
| = | 21 | |
| + | 22 | |
| - | 23 | |
| * | 24 | |
| / | 25 | |
| ( | 26 | |
| ) | 27 | |
| { | 28 | |
| } | 29 | |
| , | 30 | |
| ; | 31 | |
| > | 32 | |
| >= | 33 | |
| < | 34 | |
| <= | 35 | |
| == | 36 | |
| != | 37 | |
| # | 0 |
处理用户提交的符合上述词法的源代码序列，进行词法分析，并输出单词二元组。
4、主要参考步骤
(1)画出识别上述语言单词的状态转换图
(2)用C/C++语言编写词法分析程序（应考虑能被语法分析程序调用）
(3)预处理，去除注释、多余空格、Tab字符、回车换行符等
(4)设计若干用例，上机测试并通过所设计实现的词法分析器
1. +++-123.456e-127*+45.99e+200++abc+-cnt++49
2. (+123.456+-456.789e-120)*m2+(a++456)*-c123
3. ++4+1.4
4. a+-149+49.7e+127+m123
5. x=a++1.27e+18
6. --20+-124.987e+127+-xyz
begin if(x>=-1.27e-18) xyz=(x1+y1)* -124.987e+127
7. --20+-124. e+111-137++569.246e+(123+ivar);
x=1;if(x>1) y=1234; x=(123+abc); (本例应有出错信息)
5、思考
数字的正负号与运算符加减如何处理，识别数字的DFA怎样和运算符加减等融合在一起，进而指导词法分析器的程序编写。
6、实验报告提交格式
(1) 总体设计思想
(2) 详细算法设计
(3) 流程框图
(4) 函数相关说明
(5) 输入与输出（包括出错处理）
(6) 程序运行结果（屏幕截图）
(7) 词法分析器使用说明
(8) 心得与体会
(9) 源程序清单
——————————————————————————————————————————————————————————————————————————————
主要时间卡在了double转二进制上…
有的人说需要转，有的人说不需要orz
我能想到的办法。。大概就是要高精度＋手动实现itof?
一点也不美啊。。。求好看的方法orz
1/* ***********************************************
2Author :111qqz
3Created Time :2016年12月09日 星期五 10时39分52秒
4
5 ************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-200;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int MAX = 2E4+5;
32map<string,int>mp;
33char code[MAX];
34/*
35 * ascii code:
36 * sapce ->32
37 * n ->10
38 * tab->9
39 */
40char token[100];
41int Reallen = 0 ;
42int codelen = 0;
43//table size:26
44char table[][10]={"main","int","float","double","char","if","else","do","while"};
45bool comment = false;
46int row;
47void killchar(char *code)
48{
49 int len = strlen(code);
50 //cout<<"len:"<<len<<endl;
51 for ( int i = 0 ;i < len ; i++)
52 {
53 // if (code[i]==32||code[i]==10||code[i]==9) continue;
54 if (i<len-1)
55 {
56 if (code[i]=='/'&&code[i+1]=='*')
57 {
58 // cout<<"xgxgxg"<<endl;
59 comment = true;
60 i+=2;
61 continue;
62 }
63 if (code[i]=='*'&&code[i+1]=='/')
64 {
65 comment = false;
66 i+=2;
67 continue;
68 }
69 }
70 if (comment) continue;
71 code[Reallen++] = code[i];
72 }
73}
74bool letter(char ch)
75{
76 if (ch>='A'&&ch<='Z') return true;
77 if (ch>='a'&&ch<='z') return true;
78 return false;
79}
80bool digit(char ch)
81{
82 if (ch>='0'&&ch<='9') return true;
83 return false;
84}
85int state;
86int sum = 0 ; //记录数值
87int sign; //0,1,-1,分别表示没有符号，正号，符号。
88int pos = 0 ;
89int dblcmp(double d)
90{
91 return d<-eps?-1:d>eps;
92}
93bool Real;
94int Rlen; //digit的实数部分长度
95double Rsum;
96int esum; //e后面的数
97int Esum;//用科学计数法表示的最后的答案
98bool sci;
99int sci_sign; //科学计数法部分的符号
100bool Signed ;//符号是否出现过.
101bool lstdig = false; //判断上一位是否为数字
102bool okDigit()
103{
104 if (digit(code[pos])) return true;
105 if (code[pos]=='e'||code[pos]=='E')
106 {
107 sci_sign = 0 ;
108 return true;
109 }
110 if (sci&&(code[pos]=='+'||code[pos]=='-'))
111 {
112 if (Signed) return false;
113 if (code[pos]=='+') sci_sign = 1;
114 else sci_sign = -1;
115 pos++;
116 Signed = true;
117 return true;
118 }
119 return false;
120}
121void solveInt()
122{
123 while (okDigit())
124 {
125 if (code[pos]=='e'||code[pos]=='E')
126 {
127 if (sci) //出现一个以上的e报error
128 {
129 state = -1;
130 return ;
131 }
132 sci = true;
133 pos++;
134 continue;
135 }
136 if (sci)
137 {
138 if (code[pos]>='0'&&code[pos]<='9')
139 esum = esum * 10 + code[pos]-'0';
140 else
141 {
142 state = -1;
143 return;
144 }
145 }
146 else
147 {
148 Rsum = Rsum * 10 + code[pos]-'0';
149 }
150 pos++;
151 }
152 if (sci&&esum==0) //出现了e,e后面却为空
153 {
154 state = -1;
155 return;
156 }
157 if (sci)
158 {
159 if (sci_sign==0||sci_sign==1)
160 {
161 for ( int i = 1 ;i <= esum ; i++) Rsum *= 10;
162 }
163 else
164 {
165 for ( int i = 1 ; i<= esum ; i++) Rsum = Rsum * 0.1;
166 }
167 }
168}
169void solveReal()
170{
171 if (code[pos]=='.') Real = true,pos++;
172 if (!Real)
173 {
174 pos--;
175 return;
176 }
177 if (code[pos]=='e')
178 {
179 state = -1;
180 pos-
181 return;
182 }
183 Rlen = 0 ;
184 while (okDigit())
185 {
186 if (code[pos]=='e'||code[pos]=='E')
187 {
188 if (sci)
189 {
190 state = -1;
191 return;
192 }
193 sci = true;
194 pos++;
195 continue;
196 }
197 if (sci)
198 {
199 if (code[pos]<'0'||code[pos]>'9')
200 {
201 state = -1;
202 return;
203 }
204 int val = code[pos]-'0';
205 esum = esum * 10 + val;
206 }
207 else
208 {
209 Rsum = Rsum * 10 + code[pos]-'0';
210 Rlen++;
211 }
212 pos++;
213 }
214 pos--;
215 Rsum = Rsum *pow(10.0,-Rlen*1.0);
216 if (sci&&esum==0)
217 {
218 state = -1;
219 return;
220 }
221 if (sci)
222 {
223 if (sci_sign==0||sci_sign==1)
224 {
225 for ( int i = 1 ; i <= esum ; i++) Rsum = Rsum * 10;
226 }else
227 {
228 for ( int i = 1 ; i <= esum ; i++) Rsum = Rsum * 0.1;
229 }
230 }
231}
232void SolveDigit()
233{
234 lstdig = true;
235 Signed = false;
236 sum = 0 ;
237 state = 20;
238 Real = false;
239 Rsum = 0;
240 sci = false;
241 Esum = 0 ;
242 Rlen = 0;
243 esum = 0;
244 solveInt();
245 solveReal();
246}
247void Err()
248{
249 printf("Err! in row %d\n",row);
250}
251void scaner()
252{
253 int cur = 0;
254 // while (isspace(code[pos])) pos++;
255 while (code[pos]==' '||code[pos]=='\t') pos++; //空格
256 ms(token,0);
257 if (letter(code[pos]))
258 {
259 lstdig = false;
260 state = 10;
261 cur = 0 ;
262 while (letter(code[pos])||digit(code[pos]))
263 {
264 token[cur++] = code[pos];
265 pos++;
266 }
267 // token[cur]='\n';// !!!
268 // cout<<"cur:"<<cur<<endl;
269 // for ( int i = 0 ; i < cur ; i++) printf("%c",token[i]);
270 // cout<<"token:"<<token<<endl;
271 pos--;
272 cur--;
273 for ( int i = 0 ; i < 9 ; i++)
274 {
275 if (strcmp(token,table[i])==0)
276 {
277 state = i + 1;
278 break;
279 }
280 }
281 }
282 else if (digit(code[pos]))
283 {
284 sign = 0 ;
285 lstdig = true;
286 SolveDigit();
287
288 ++pos;
289 return ; //for lstdig
290 }else if (code[pos]=='\n') state = -2;
291 else if (code[pos]=='#') state = 0;
292 else switch (code[pos])
293 {
294 case '=': state = 21;pos++;
295 if (code[pos]=='=')
296 {
297 state = 36;
298 }else pos--;
299 break;
300 case '>':state = 32; pos++;
301 if (code[pos]=='=')
302 {
303 state = 33;
304 }else pos--;
305 break;
306 case '<':state = 34; pos++;
307 if (code[pos]=='=')
308 {
309 state = 35;
310 }else pos--;
311 break;
312 case '!': pos++;
313 if (code[pos]=='=')
314 {
315 state =37;
316 }else pos--;
317 break;
318 case '+':state = 22;pos++;
319 // cout<<"pos:"<<pos<<"code[pos]:"<<code[pos]<<"lstdig:"<<lstdig<<endl;
320 if(!lstdig&&digit(code[pos]))
321 {
322 // cout<<"lstdig:"<<lstdig<<"pos:"<<pos<<endl;
323 SolveDigit();
324 sign = 1;
325 }
326 else lstdig = false,pos--;
327 pos++;
328 return;
329 case '-':state = 23;pos++;
330 if(!lstdig&&digit(code[pos]))
331 {
332 SolveDigit();sign = -1;
333 }
334 else lstdig = false, pos--;
335 pos++;
336 return;
337 case '*':state = 24; break;
338 case '/':state = 25; break;
339 case '(':state = 26; break;
340 case ')':state = 27; break;
341 case '{':state = 28; break;
342 case '}':state = 29; break;
343 case ',':state = 30; break;
344 case ';':state = 31; break;
345 }
346 ++pos;
347 lstdig = false;
348 // cout<<"posss:"<<pos<<" "<<code[pos]<<endl;
349}
350void init()
351{
352 mp["main"] = 1;
353 mp["int"] = 2;
354 mp["float"] = 3;
355 mp["double"] = 4;
356 mp["char"] = 5;
357 mp["if"] = 6;
358 mp["else"] = 7;
359 mp["do"] = 8 ;
360 mp["while"] = 9;
361}
362void pr()
363{
364 int len = strlen(code);
365 for ( int i = 0 ; i < len ; i++)
366 {
367 cout<<code[i];
368 }
369}
370char *Table[20]={"=","+","-","*","/","(",")","{","}",",",";",">",">=","<","<=","==","!="};
371int main()
372{
373#ifndef ONLINE_JUDGE
374 freopen("s2.txt","r",stdin);
375#endif
376 init();
377 row = 1;
378 while (1)
379 {
380 char ch;
381 cin.get(ch);
382 code[codelen++] = ch;
383 if (ch=='#') break;
384 }
385 // pr(code);
386 code[codelen]='\n';
387 killchar(code);
388 // cout<<code<<endl;
389 codelen = Reallen;
390 // cout<<"codelen:"<<codelen<<endl;
391 // pr();
392 pos = 0;
393 while (1)
394 {
395 scaner();
396// cout<<"lstdig:"<<lstdig<<endl;
397 if (state==0) break;
398 if (state==-2)
399 {
400 row++;
401 cout<<endl;
402 }else if (state>=1&&state<=9)
403 {
404 char *tmp = table[state-1];
405 int id = mp[string(tmp)];
406 cout<<"("<<id<<", )"<<endl;
407 }else if (state>=21&&state<=37)
408 {
409 cout<<"("<<state<<",'"<<Table[state-21]<<"')"<<endl;
410 }else if (state==10)
411 {
412 cout<<"(10,"<<token<<")"<<endl;
413 }else if (state==20)
414 {
415 cout<<"(20,";
416 if (sign==1) putchar('+');
417 else if (sign==-1) putchar('-');
418 cout<<Rsum;
419 cout<<")"<<endl;
420 }else
421 {
422 Err();
423 pos++;
424 }
425 }
426#ifndef ONLINE_JUDGE
427#endif
428 return 0;
429}