编译方法实验报告
姓 名 李亚方 学 号
20080931
班 级 软一0801 指 导 教 师 高健
实 验 名 称 扫描器设计
开 设 学 期 20 10 -20 11 第二学 期
实 验 时 间 第 16 周
评 定 成 绩
评定人签 字
评 定 日 期
东北大学软件学院
2011年1月
实验目的
(1) 熟悉并实现一个扫描器（词法分析程序）；
(2) 掌握如何设计扫描器的有限自动机（识别器）；
(3) 熟悉翻译、生成 Token 的算法（翻译器）；
(4) 了解扫描器、识别器、翻译器三者之间的关系；
(5) 掌握有限自动机及词法分析器原理；
(6) 加深对课堂讲授内容的理解，了解编译程序的基本结构；
(7) 学习并掌握编译程序的相关实现技术：如设计扫描器的自动机、设计翻译及生成 Token
的算法；
(8) 熟悉算术表达式的语法分析与中间代码生成原理。
实验内容
(1) 设计扫描器的有限自动机（识别器）；
(2) 设计翻译、生成 Token 的算法（翻译器）；
(3) 编写代码并上机调试运行通过。
·输入——源程序文件或源程序字符串；
·输出——相应的 Token 序列；
关键字表和界符表；
符号表和常数表；
实验原理及基本步骤
（1）词法分析程序又称扫描器，任务有两个：
a.识别单词——从用户的源程序中把单词分离出来;
b.翻译单词——把单词转换成机内表示，便于后续处理。
即： 单词 Token
（2）有限自动机的状态转换图：
扫描器
e
d d d
+|- -1/+/-
+ ① d ② . ③ d ④ e ⑤ ⑥ d ⑦
d -
-1/+/-
l/d -1/+/-
-1
l ⑧ -
-1
b ⑨ b ⑩ -
-1
-
-1
-
其中：d 为数字，l 为字母，b 为界符，-1 代表其它符号（如在状态 8 处遇到了非字母或数
字的其它符号，会变换到状态 12）。
（3）状态转换矩阵：
d · E|e +|- l b -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(2) 关键字表和界符表
Program ;
Begin :
End (
Var )
While ,
2 8 9 15
2 3 5 11 11
4
4 5 11 11
7 6
7
7 11 11
8 8 12
10 14
15 13
12
11
13
1
4
15
Do :=
Repeat +
Until -
For *
To /
If >
Then >=
Else ==
<
<=
数据结构设计
① 状态转换矩阵：int aut[10][7]={ 2, 0, 0, 0, 8, 9, 15,
2, 3, 5,11, 0, 0, 11,
4, 0, 0, 0, 0, 0, 0,
4, 0, 5,11, 0, 0, 11,
7, 0, 0, 6, 0, 0, 0,
7, 0, 0, 0, 0, 0, 0,
7, 0, 0,11, 0, 0, 11,
8, 0, 0, 0, 8, 0, 12,
0, 0, 0, 0, 0, 10, 14,
0, 0, 0, 0, 0, 0, 13};
② 关键字表：
char keywords[30][12]={“program”,”begin”,”end”,”var”,”while”,”do”,
”repeat”,”until”,”for”,”to”,”if”,”then”,”else”, “;”, ”:”, ”(“, ”)”, ”,”,
”:=”, ”+”, ”-“, ”*”, ”/”,
”>”, ”>=”, ”==”, “<”, “<=”};
③ 符号表：char ID[50][12]; //表中存有源程序中的标识符
④ 常数表：float C[20];
⑤ 其它变量： struct token
{ int code;
int value}; //Token 结构
struct token tok[100]; //Token 数组
int s; //当前状态
int n,p,m,e,t; //尾数值，指数值，小数位数，指数符号，类型
float num; //常数值
char w[50]; //源程序缓冲区
int i; //源程序指针,当前字符为 w[i]
char strTOKEN[12]; //当前已经识别出的单词
(4) 语义动作：
·q
1
：n=m=p=t=0; e=1; num=0; 其它变量初始化；
·q
2
：n=10*n+(w[i]);
·q
3
：t=1;
·q
4
：n=10*n+( w[i]); m++;
·q
5
：t=1;
·q
6
：if ‘-‘ then e=-1;
·q
7
：p=10*p+(w[i]);
·q
8
：将 w[i]中的符号拼接到 strTOKEN 的尾部；
·q
9
：将 w[i]中的符号拼接到 strTOKEN 的尾部；
·q
10
：将 w[i]中的符号拼接到 strTOKEN 的尾部；
//标识符的编码为 1，值为其在常数表中的位置；常数的编码为 2，值为其在符号表中的
位置；关键字和界符的编码为其在关键字表中的位置，值为 0。
·q
11
：num=n*10
e*p-m
; //计算常数值
t[i].code=2; t[i].value=InsertConst(num); //生成常数 Token
·q
12
：code=Reserve(strTOKEN); //查关键字表
if code then { t[i].code=code; t[i].value=0; } //生成关键字 Token
else {t[i].code=1; t[i].value=InsertID(strTOKEN); }
//生成标识符 Token
·q
13
：code=Reserve(strTOKEN); //查界符表
if code then { t[i].code=code; t[i].value=0; } //生成界符 Token
else {
strTOKEN[strlen(strTOKEN)-1]=’\0’; //单界符
源程序缓冲区指针减 1；
code=Reserve(strTOKEN); //查界符表
t[i].code=code; t[i].value=0; //生成界符 Token
}
·q
14
：code=Reserve(strTOKEN); //查界符表
t[i].code=code; t[i].value=0; //生成界符 Token
·q
15
：stop.
(5) 查状态变换表
int find(int s,char ch) //s 是当前状态，ch 是当前字符，返回值是转换后状态
{
查状态转换矩阵 aut[10][7]；
返回新状态；
}
(6) 主程序流程：
初始化；
打开用户源程序文件；
while （文件未结束{ 读入一行到 w[i]，i=0;
do //处理一行，每次处理一个单词
{ 滤空格，直到第一个非空的 w[i]；
i--；
s=1; //处理一个单词开始
while （s!=0） //拼单词并生成相应 Token
