词法分析设计
实验目的通过本实验的编程实践，了解词法分析的任务，掌握词法分析程序设计的原理和构造方 法，对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。
实验内容
用C++语言实现对C++语言子集的源程序进行词法分析。通过输入源程序从左到右对字 符串进行扫描和分解， 依次输出各个单词的内部编码及单词符号自身值； 若遇到错误则显示
“ Error ”，然后跳过错误部分继续显示 ；同时进行标识符登记符号表的管理。
实验原理
本次实验采用 NFA->DFA->DFA0的过程：
对待分析的简单的词法（关键词 /id/num/运算符/空白符等）先分别建立自己的 FA,然
后将他们用三产生式连接起来并设置一个唯一的开始符，终结符不合并。
待分析的简单的词法
（1 ）关键字：
"asm","auto","bool","break","case","catch","char","class","co nst","co nst_cast"
（2）界符（查表）
";",",","（","）","[","]","{","}"
（3）运算符
"*" "/" "%" " + "I!I!
"*" "/" "%" " + "
I!
I!
I!
""A" "|" " + + " " " " + 一" " 一" "*一" "/一" "% 一" "&一"
"A=" "|="
relop :
（3 J? inrLuni>J “LidlL金、辑*
（3 J? inrLuni>
J “Lidl
L
金、
辑*?I lelup EQ）
rckp LTk
（4）其他单词是标识符（ID）和整型常数（SUM,通过正规式定义。
id/keywords:
l?lier ur ditfii
l?lier ur ditfii
digit:
空格有空白、制表符和换行符组成。空格一般用来分隔 ID、SUM运算符、界符和关
键字，词法分析阶段通常被忽略。
空白、制表符和换行符
相关自动机描述
DFA:
》rt*如柿忙曾” 7
沪址卅片/缈 $：疋r吟，
!"丿
B K*** (吗"他 豎秽如I必作?> ) 豹比如l疋第&D d鹫如
Uf r+=) 叩弋 0p j--J
P 址仙TJ >比虹巾iff, r J
步letmt『甲,/3 ) 卩代如d冷』/ ) F 戌曲呵申] ?此阪5打￡包 ) 疋如I叩JQ i?如 frt? n j
j)址如H [ f
DFA0
L
■'t
流程图
5
du
核心数据结构描述
(1)生成的token序列由name type、attr 保存。
struct token{
stri ng n ame;
stri ng type;
int attr;
}；
(2)本文的大多数数据结构都用
map来保存，优点是查找方便，大大提高时间复杂度。
map<stri ng.
int
> Keywords; //
保存关键字
map<stri ng,
int
> Sep;
//
保存界符
map<stri ng,
int
> Relop;
//
保存比较运算符
map<stri ng,
int
> Op;
//
保存其他运算符
map<stri ng,
int
>id;
//
保存输入字符串中的id
map<stri ng,
int
>n um;
//
保存数字
vectorvtoken>Token; // 保存token序列，大小未知，所以采用 vector保存
核心算法描述
(1) void addToken(string s, int type)s 为找到的字符串，type 为可能类型。
将分析出来的token()序列添加到Token序列表中。如果是类型为 1，查看关键词表，
若找到，其类型为关键词并将其以类型为关键词存储到 Token表中；若未找到，则查找 id
表，若找到，说明该id已经出现过，否则添加新的 id到id表中，将该i字符串以类型为 id添加到Token表中。如果类型为2,在界符表中查找，如果找到以类型为界符存储到 Token
表中，同理其他几种类型。可能类型为 1--5，如果出现其他类型表示是词法分析器中发现
额错误，将错误信息记录下来。
void addToken(string s, int type)
{
switch (type){
case 1:
l_i t=Keywords.fi nd(s);
if (l_it!=Keywords.end()){
token t={s, "keywords" ,l」t->second};
Toke n.push_back(t);
}else {
l」t=id.fi nd(s);
if (l_it==id.end())
{
id[s]=idNum;
token t={s, "id" ,idNum++};
Toke n.push_back(t);
} else {
token t={s, "id" ,l」t->second};
Toke n.push_back(t);
}
break;
case 2:
l_it=Sep.fi nd(s);
if (l_it!=Sep.end()){
token t={s, "separatrix" ,l_it->second};
Toke n.push_back(t);
}
break;
case 3:
l」t=Op.fi nd(s);
if (l_it!=Op.end()){
token t={s, "op" ,l_it->second};
Toke n.push_back(t);
}
break;
case 4:
l_it=Relop.fi nd(s);
if (l_it匸Relop.end()){
token t={s, "relop" ,l」t->second};
Toke n.push_back(t);
}
break;
case 5:
l」t=n um.fi nd(s);
if (l_it==num.end())
{
n um[s]=nNum;
toke n t={s, "n um", nN um++};
Toke n.push_back(t);
}else {
token t={s, "num",l_it->second};
Toke n.push_back(t);
}
break;
default : //error
token t={s, "id" ,-1};
Toke n.push_back(t);
break;
}
}
(2) void lexical。 词法分析器，按字符读入文法并对其进行处理。
从状态0开始处理，如果是空白符则一直在状态 0,如果第一个字符为字母，继续往后寻找，直至不
是字母或是数字结束；若第一个字符为数字，将其拼凑成一个数字，数字可以有小数点等，详细见状
态转换图，注意以数字开头容易岀现一种例如 3a类型的错误，所以以数字开头的一定要往下多找
如果后面紧跟着字母则报错。addToken()添加到 Token 表
如果后面紧跟着字母则报错。
addToken()添加到 Token 表
void lexical()
{
fstream ln( "E:\l n.txt" );
char ch,tempch;
int state=0;
string s= "" ,key="";
while (!ln.eof())
{
switch (state){
case 0: 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;
case 1: ch=ln .get();
if (ch== '=' ||ch== '>' ) state=2;
else if (ch=='<‘ ) state=4;
else state=5;
break;
case 2:
s+=ch;
addToke n( s,4);
state=0;
break;
case 4: s+=ch;
addToke n(s,3);
state=0;
break;
case 5: //*
addToke n( s,4);
In. seekg(-1,ios::cur); state=0;
break;
case 6: ch=ln .get();
if (ch== '=' ) state=7;
else state=8;
break;
case 7:
s+=ch;
addToke n( s,4);
state=0;
break;
case 8: //*
addToke n(s,3);
ln. seekg(-1,ios::cur); state=0;
break;
case 9: ch=ln .get();
if (ch== '=' ) state=10;
else if (ch=='>' ) state=11;
else state=12;
break;
case 10:
s+=ch;
addToke n( s,4);
state=0;
break;
case 11:
s+=ch;
addToke n(s,3);
state=0;
break;
case 12: //*
state=0; addToke n( s,4);
ln. seekg(-1,ios::cur); break;
case 13: ch=ln. get();
if (isDigit(ch)||isLetter(ch)) s+=ch;
else state=14;
break;
case 14: //*
state=0;
addToke n( s,1);
ln. seekg(-1,ios::cur); break;
case 15: ch=ln. get();
if (isDigit(ch)) s+=ch;
else if (ch=='.')
{
s+=ch;
state=16;
} else state=18; break;
case 16: ch=ln. get();
s+=ch;
if (isDigit(ch)) state=17;
else state=50; //error
break;
case 17: ch=ln. get();
if (isDigit(ch)){
s+=ch;
state=17;
} else state=18;
break;
case 18: //*
if (isLetter(ch))
{
s+=ch;
state=50;
} else {
addToke n( s,5);
ln. seekg(-1,ios::cur);
state=0;
}
break;
case 20: ch=ln. get();
if (ch==tempch||ch== '=' ) state=21;
else state=23;
break;
case 21:
s+=ch;
addToke n(s,3);
state=0;
break;
case 23:
addToke n(s,3);
In. seekg(-1,ios::cur);
state=0;
break;
case 44: ch=ln. get();
if (ch== '=' ) state=45;
else state=46;
break;
case 45:
s+=ch;
addToke n(s,3);
break;
case 46:
addToke n(s,3);
ln. seekg(-1,ios::cur);
break;
case 47:
addToke n(s,2);
state=0;
break;
case 48:
addToke n(s,3);
state=0;
break;
case 49:
addToke n( s,4);
state=0;
break;
case 50: //error
while ((ch=ln.get())!=EOF){
if (isSep(ch)!=-1||ch==13||ch==10||ch==32||ch==9) break;
else s+=ch;
}
addToke n( s,6); //error
ln. seekg(-1,ios::cur);
state=0;
break;
default :
break;
}
7.测试用例
待测字符串：
void fun()
{
int a=2,b=3,3a;
a++;b--;
a+=b;
b*=a;
int c=a+4;
int d=b*5;
}
产生结果在out.txt 中（注意，无论输入输出文件都要保存在 E盘根目录下）
tolten sequence:
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
?亠
sepsratri y
1
Sa
Error
pepsraTri/
0
id
1
卄
叩
11
sep^ratrix
0
id
2
——
□p
12
* a
scpcxatriz id
0
1
+=
op
13
b
id
2
*
sepsratriy
0
h
id
2
op
15
a
id
1
s^Dsr^tri y
0
In-t
keywords
27
c
id
3
—
05>
6
a
id
1
+
op
4
num
J
separatrix
iti\
keywurds
27
d
id
4
* CT 0
B EUJD 3
kmyvrands :
am
ariitc
b沁
break
c^.?e
st ch
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
ini inc
26
int
2T
1 DUg
28
mutable
29
niinesrace
30
n沖
31
opera! or
32
separalrli 0
separalrlz 叩
private protectel rublic register reint reti_trii slujrt signed nizecF static etatic_eagt struct switch teril>late this throw true try
lyptri J tyi.ensne uni ai unsigned ueine vli' tual void volati1e while
3 4 5 6 7 8 9 o 1 2 4 5 6 7 s o u 1 2 3 4 5 & 7 8 9 -u
3 3 3 3 3 3 3 目 a 召勺 4 ￡ 4 ^-5655555555^
/=
stfaratrix:
(
)
relop：
7 s E 1 3 2 q
2 1 s 1 u 1 3 114 11
id; a b
fun
nun：
2
3
4
5
出现的问题与解决方案
本实验的难点就是进行有效地进行状态如转换，先对每一个简单部分，如空白符、 id、
digit等画出自动机状态，然后由 NFA->DFA添加一个唯一的初始状态， 巳产生式连接。再
将DFA中等价的状态合并最后变成 DFA0这样便大大简化了代码量，也使得逻辑思维更加
清晰。
自我体会
将理论运用到 实际，不仅可以帮我们更好地复习理论知识， 还可以让我们发发掘到一些更深刻层面上的东
西。通过本次实验，我深入了解了词法分析的过程，对 NFA,DFA,DFAO之间的转换也更能更
加熟练地运用。这次实验还有许多需要加强的地方， 比如还可以对id的类型进行明确分类，
是函数还是变量，是什么类型的，返回类型是什么等等。之后有机会的 话，我一定会更加深入的研究，将这个实验更加完善。