东南大学编译原理词法分析器实验报告.docx
《东南大学编译原理词法分析器实验报告.docx》由会员分享，可在线阅读，更多相关《东南大学编译原理词法分析器实验报告.docx（19页珍藏版）》请在冰点文库上搜索。
东南大学编译原理词法分析器实验报告
词法分析设计
1.实验目的
通过本实验的编程实践，了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。
2.实验内容
用C++语言实现对C++语言子集的源程序进行词法分析。
通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示
“Error”，然后跳过错误部分继续显示；同时进行标识符登记符号表的管理。
3.实验原理
本次实验采用NFA->DFA->DFA0的过程：
对待分析的简单的词法（关键词/id/num/运算符/空白符等）先分别建立自己的FA,然
后将他们用三产生式连接起来并设置一个唯一的开始符，终结符不合并。
待分析的简单的词法
（1）关键字：
"asm","auto","bool","break","case","catch","char","class","const","const_cast"
（2）界符（查表）
";",",","（","）","[","]","{","}"
（3）运算符
"A=""|="
relop:
（4）其他单词是标识符（ID）和整型常数（SUM,通过正规式定义。
id/keywords:
digit:
（5）空格有空白、制表符和换行符组成。
空格一般用来分隔ID、SUM运算符、界符和关
键字，词法分析阶段通常被忽略。
空白、制表符和换行符
4.相关自动机描述
DFA:
》rt*如柿忙曾”7
沪址卅片/缈$：
疋r吟，
!
"丿
BK***（吗"他豎秽如I必作?
>）豹比如l疋第&Dd鹫如
Ufr+=）叩弋0pj--J
P址仙TJ>比虹巾iff,rJ
步letmt『甲,/3）卩代如d冷』/）F戌曲呵申]?
此阪5打£包）疋如I叩JQi?
如frt?
nj
j）址如H[f
DFA0
L
■'t
流程图
5
du
5.核心数据结构描述
（1）生成的token序列由nametype、attr保存。
structtoken{
stringname;
stringtype;
intattr;
}；
（2）本文的大多数数据结构都用
map来保存，优点是查找方便，大大提高时间复杂度。
mapint
>Keywords;//
保存关键字
mapint
>Sep;
//
保存界符
mapint
>Relop;
//
保存比较运算符
mapint
>Op;
//
保存其他运算符
mapint
>id;
//
保存输入字符串中的id
mapint
>num;
//
保存数字
vectorvtoken>Token;//保存token序列，大小未知，所以采用vector保存
6.核心算法描述
（1）voidaddToken（strings,inttype）s为找到的字符串，type为可能类型。
将分析出来的token（）序列添加到Token序列表中。
如果是类型为1，查看关键词表，
若找到，其类型为关键词并将其以类型为关键词存储到Token表中；若未找到，则查找id
表，若找到，说明该id已经出现过，否则添加新的id到id表中，将该i字符串以类型为id添加到Token表中。
如果类型为2,在界符表中查找，如果找到以类型为界符存储到Token
表中，同理其他几种类型。
可能类型为1--5，如果出现其他类型表示是词法分析器中发现
额错误，将错误信息记录下来。
voidaddToken（strings,inttype）
{
switch（type）{
case1:
l_it=Keywords.find（s）;
if（l_it!
=Keywords.end（））{
tokent={s,"keywords",l」t->second};
Token.push_back（t）;
}else{
l」t=id.find（s）;
if（l_it==id.end（））
{
id[s]=idNum;
tokent={s,"id",idNum++};
Token.push_back（t）;
}else{
tokent={s,"id",l」t->second};
Token.push_back（t）;
}
break;
case2:
l_it=Sep.find（s）;
if（l_it!
=Sep.end（））{
tokent={s,"separatrix",l_it->second};
Token.push_back（t）;
}
break;
case3:
l」t=Op.find（s）;
if（l_it!
=Op.end（））{
tokent={s,"op",l_it->second};
Token.push_back（t）;
}
break;
case4:
l_it=Relop.find（s）;
if（l_it匸Relop.end（））{
tokent={s,"relop",l」t->second};
Token.push_back（t）;
}
break;
case5:
l」t=num.find（s）;
if（l_it==num.end（））
{
num[s]=nNum;
tokent={s,"num",nNum++};
Token.push_back（t）;
}else{
tokent={s,"num",l_it->second};
Token.push_back（t）;
}
break;
default:
//error
tokent={s,"id",-1};
Token.push_back（t）;
break;
}
}
（2）voidlexical。
词法分析器，按字符读入文法并对其进行处理。
从状态0开始处理，如果是空白符则一直在状态0,如果第一个字符为字母，继续往后寻找，直至不
是字母或是数字结束；若第一个字符为数字，将其拼凑成一个数字，数字可以有小数点等，详细见状
态转换图，注意以数字开头容易岀现一种例如3a类型的错误，所以以数字开头的一定要往下多找
如果后面紧跟着字母则报错。
addToken（）添加到Token表
个，看最后一个数字后面是否为空白符或界符或者其他允许岀现的符号,如上同理分析运算符等。
注意每次处理完遇到一个字符串都要将其送到中并回到状态0,继续往下处理。
voidlexical（）
{
fstreamln（"E:
\ln.txt"）;
charch,tempch;
intstate=0;
strings="",key="";
while（!
ln.eof（））
{
switch（state）{
case0:
ch=ln.get（）;
s=ch;
if（ch==13||ch==10||ch==32||ch==9）{state=0;s="";}
else
if
（ch=='<'）state=1;
else
if
（ch=='='）state=6;
else
if
（ch=='>'）state=9;
else
if
（isLetter（ch））state=13;
else
if
（isDigit（ch））state=15;
else
if
（ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='&'||ch=='|'）
{state=20;tempch=ch;}
else
if
（ch==s'）state=44;
else
if
（isSep（ch）!
=-1）state=47;
else
if
（isOp（s）!
=-1）state=48;
else
if
（isRelop（s）!
=-1）state=49;
else
state=50;
//error
break;
case1:
ch=ln.get（）;
if（ch=='='||ch=='>'）state=2;
elseif（ch=='<‘）state=4;
elsestate=5;
break;
case2:
s+=ch;
addToken（s,4）;
state=0;
break;
case4:
s+=ch;
addToken（s,3）;
state=0;
break;
case5:
//*
addToken（s,4）;
In.seekg（-1,ios:
:
cur）;state=0;
break;
case6:
ch=ln.get（）;
if（ch=='='）state=7;
elsestate=8;
break;
case7:
s+=ch;
addToken（s,4）;
state=0;
break;
case8:
//*
addToken（s,3）;
ln.seekg（-1,ios:
:
cur）;state=0;
break;
case9:
ch=ln.get（）;
if（ch=='='）state=10;
elseif（ch=='>'）state=11;
elsestate=12;
break;
case10:
s+=ch;
addToken（s,4）;
state=0;
break;
case11:
s+=ch;
addToken（s,3）;
state=0;
break;
case12:
//*
state=0;addToken（s,4）;
ln.seekg（-1,ios:
:
cur）;break;
case13:
ch=ln.get（）;
if（isDigit（ch）||isLetter（ch））s+=ch;
elsestate=14;
break;
case14:
//*
state=0;
addToken（s,1）;
ln.seekg（-1,ios:
:
cur）;break;
case15:
ch=ln.get（）;
if（isDigit（ch））s+=ch;
elseif（ch=='.'）
{
s+=ch;
state=16;
}elsestate=18;break;
case16:
ch=ln.get（）;
s+=ch;
if（isDigit（ch））state=17;
elsestate=50;//error
break;
case17:
ch=ln.get（）;
if（isDigit（ch））{
s+=ch;
state=17;
}elsestate=18;
break;
case18:
//*
if（isLetter（ch））
{
s+=ch;
state=50;
}else{
addToken（s,5）;
ln.seekg（-1,ios:
:
cur）;
state=0;
}
break;
case20:
ch=ln.get（）;
if（ch==tempch||ch=='='）state=21;
elsestate=23;
break;
case21:
s+=ch;
addToken（s,3）;
state=0;
break;
case23:
addToken（s,3）;
In.seekg（-1,ios:
:
cur）;
state=0;
break;
case44:
ch=ln.get（）;
if（ch=='='）state=45;
elsestate=46;
break;
case45:
s+=ch;
addToken（s,3）;
break;
case46:
addToken（s,3）;
ln.seekg（-1,ios:
:
cur）;
break;
case47:
addToken（s,2）;
state=0;
break;
case48:
addToken（s,3）;
state=0;
break;
case49:
addToken（s,4）;
state=0;
break;
case50:
//error
while（（ch=ln.get（））!
=EOF）{
if（isSep（ch）!
=-1||ch==13||ch==10||ch==32||ch==9）break;
elses+=ch;
}
addToken（s,6）;//error
ln.seekg（-1,ios:
:
cur）;
state=0;
break;
default:
break;
}
7.测试用例
待测字符串：
voidfun（）
{
inta=2,b=3,3a;
a++;b--;
a+=b;
b*=a;
intc=a+4;
intd=b*5;
}
产生结果在out.txt中（注意，无论输入输出文件都要保存在E盘根目录下）
toltensequence:
RE
luktii
attri
void
keywords
58
fun
id
0
<
scpci'atriz
2
）
sep^ratrii
3
（
6
ini
kc/wuL'dt
27
a
id
1
2
num
0
J
seperatrix
1
h
id
2
—
op
£
3
num
1
•亠
sepsratriy
1
Sa
Error
pepsraTri/
0
id
1
卄
叩
11
sep^ratrix
0
id
2
——
□p
12
*a
scpcxatrizid
0
1
+=
op
13
b
id
2
*
sepsratriy
0
h
id
2
op
15
a
id
1
s^Dsr^triy
0
In-t
keywords
27
c
id
3
—
05>
6
a
id
1
+
op
4
num
J
separatrix
iti\
keywurds
27
d
id
4
*CT0
BEUJD3
kmyvrands:
am
ariitc
b沁
break
c^.?
e
stch
char
class
corst
c^rtinuc
10
default
11
delete
12
dj
13
dnublr
14
d/ramic扫家
15
else
16
旳inn
n
IB
extern
19
f^lcs
20
float
21
for
魂
friend
23
goto
24
if
25
iniinc
26
int
2T
1DUg
28
mutable
29
niinesrace
30
n沖
31
opera!
or
32
separalrli0
separalrlz叩
privateprotectelrublicregisterreintreti_triislujrtsignednizecFstaticetatic_eagtstructswitchteril>latethisthrowtruetry
lyptriJtyi.ensneuniaiunsignedueinevli'tualvoidvolati1ewhile
3456789o124567sou12345&789-u
3333333目a召勺4£4^-5655555555^
/=
«
»
A
stfaratrix:
（
）
relop：
7sE132q
21s1u1311411
id;ab
fun
nun：
2
3
4
5
8.出现的问题与解决方案
本实验的难点就是进行有效地进行状态如转换，先对每一个简单部分，如空白符、id、
digit等画出自动机状态，然后由NFA->DFA添加一个唯一的初始状态，巳产生式连接。
再
将DFA中等价的状态合并最后变成DFA0这样便大大简化了代码量，也使得逻辑思维更加
清晰。
9.自我体会
将理论运用到实际，不仅可以帮我们更好地复习理论知识，还可以让我们发发掘到一些更深刻层面上的东
西。
通过本次实验，我深入了解了词法分析的过程，对NFA,DFA,DFAO之间的转换也更能更
加熟练地运用。
这次实验还有许多需要加强的地方，比如还可以对id的类型进行明确分类，
是函数还是变量，是什么类型的，返回类型是什么等等。
之后有机会的话，我一定会更加深入的研究，将这个实验更加完善。
升级会员 