1
《编译原理》实验报告
实验名称
TEST 语言编译系统
实验类型
设计型
指导老师
小组成员姓名
学号
小组分工
语法代码\测试\文档
语义代码\测试\实验三程序实现
词法代码
实验地点
东 7A1-16
完成时间
2020/12/25
测试用例数量
32
正确数量
28
考核细则
内容
分值
要求
得分
词法分析
3
完成实验 1，测试数据设计合理，结果正确
语法分析
5
完成实验 2，测试数据设计合理，结果正确
语义及模拟机
9
完成实验 3，测试数据设计合理，结果正确
答辩
5
思路清晰，分工合理，团队合作精神好
报告内容
8
符合实验指导书的要求，有总结、有收获
实验加分项
5
完成额外加分的功能项，结果正确
○一维数组○负操作○符号串○DFA○其他
总分
30
（5）
考核时间： 考核人：
计算机科学与技术学院
2
一、实验内容简介
实验目的：通过实验使学生对高级语言程序的编译过程及原理有较全面的了解，从理论和实践
上掌握高级程序语言的设计、翻译过程和方法。
实验要求：
(1) 熟悉编译程序的整体结构；
(2) 掌握词法分析、语法分析、语义分析的基本方法；
(3) 具有设计各种常见语言成分的目标结构的能力；
(4) 熟悉编译程序中各种主要的数据结构；
(5) 具有分析和实现编译程序的初步能力。
实验目标：
设计并实现 TEST 语言的编译系统。TEST 语言结构简单，在语法上相当于 C 的子集：
(1) 本实验的 TEST 语言程序体为：’{‘ 语句序列 ‘}’。语句包含：int 语句、if 语句、for 语句、
while 语句、do-while 语句、read 语句、write 语句、{}复合语句、表达式语句构成，其中 do-while 语
句为新增加的语句。
(2) 用于变量定义的 int 语句只支持区无符号整型，一条定义语句可以声明多个变量，如：int
i,j,k;。变量可以在使用之前定义。
(3) 表达式包含赋值表达式、布尔表达式和算术表达式。布尔表达式由对两个算术表达式的比
较组成，该比较使用<、<=、>、>=、==和!=比较算符。算术表达式可以包括整型常数、变量、（）、
+、－、*、/，此外还有一般的数学属性。
(4) 注释用“/*”和“*/”括起来，但注释不能嵌套。
(5) 支持%运算（mod）,保留字的判断采用 Hash 法。
扩充的加分功能：
（6）支持一维数组。
（7）支持负操作，如： -a; --a; b---a;。
（8）支持 write 符号串（如 write “input data”）。
（9）DFA 词法分析器。
（10）其他特殊功能。
必须完成内容：（1）-（5），实验最高 30 分。
额外加分内容：（6）-（10），根据完成情况，最高增加 5 分，即总的实验分最高 35 分。
3
二、实验设计及实现
词法规则：扫描源程序字符流，根据字母表 keywords 里面的关键字，将对应符号序列从输入字
符流中分离出来。对于完善结果的表达，我们在每次读入一个"\n"之后，会让一个变量 i++，以此来
实现行数的展示。对于提高查找的效率，我们设计了一套精妙的算法：设定一个 gethash 函数，首先
将一个占位符 null 放进字母表 keywords 数组里面，然后读进一个符号序列，用一个变量 lens 去记录
它的长度，用一个变量 allasc 去记录它的 ASCII 码，然后用((lens + 2 * ((allasc - 1) % 11)) - 4) % 10 计
算目标符号序列位置下标，将结果保存到一个变量 hashnum 中并作为返回值，再在 check 函数中将
其调用，查看目标符号序列是否与字母表中的关键字相匹配，这样就完成了一次查找。
//定义长度为 9 的哈希存储地址，null 表示占位
char *keywords[9] = { "if","int","read","for","null","while","else","write","do"};
int gethash(char token[]) { //计算各关键字的 hash 值
int lens = 0;
int allasc = 0;
for (int i = 0; token[i] != '\0'; i++){
lens += 1;
allasc += (token[i] - 'a');
}
int hashnum = 0;
hashnum= ((lens + 2 * ((allasc - 1) % 11)) - 4) % 10;
return hashnum;
}
int check(char token[]) { //判断是否为关键字
int index = gethash(token);
if (index >= 0 && index < 9) {
if (strcmp(token, keywords[index]) == 0) {
return 1;
}
else { //hash 值和关键字相等，但是不为关键字
return 0;
}
}
else { //hash 值不在关键字范围，一定部署
return 0;
}
}
计算机科学与技术学院
4
统计行数
int i=0;
ch=getc(fin);
while(ch!=EOF){
while (ch==' '||ch=='\n'||ch=='\t') {
if(ch=='\n')
i++; //行数+1
ch=getc(fin);
}
......
if(check(token)==1) //直接调用 hash 函数判断是否关键字
{
fprintf(fout,"%s\t%s\t%d\n",token,token,i); //输出保留字符号
printf("%s\t%s\t%d\n",token,token,i); //输出错误符号
}
else{
fprintf(fout,"%s\t%s\t%d\n","ID",token,i); //输出标识符符号
printf("%s\t%s\t%d\n","ID",token,i); //输出错误符号
}
} else if (isdigit(ch))//数字处理
{
token[0]=ch; j=1;
ch=getc(fin); //读下一个字符
while (isdigit(ch)) //如果是数字则组合整数；如果不是则整数组合结束
{
token[j++]=ch; //组合整数保存在 token 中
ch=getc(fin); //读下一个字符
}
token[j]='\0'; //整数组合结束
......
语法规则：根据词法规则产生出的符号序列进行语法分析，支持<int 语句>|if 语句>|<while 语句
>|<for 语句>|<read 语句>|<write 语句>|<复合语句>|<表达式语句>|<do…while 语句>，我们完成了实
验指导书上所缺的<int 语句>和<do…while 语句>部分，并完善了报错函数，使其不禁能检查出语法
错误类型，还能检查出错误发生的行数。在关于<int 语句>部分的 int_start 函数中，我们首先将目标
符号序列读入并打印出来，然后将其第一行字符与"ID"字符串作比对，如果不相等，则用 error 函数
进行报错。接着再读入一行并打印，用递归的方式来检查目标符号序列：若为","就递归；若为";"就
读入下一行，并用 statement 函数判断目标符号序列是否为"int"；否则就进行报错。在关于<do…while
语句>部分的 do_while_stat 函数中，仍是先将目标符号序列读入并打印出来，然后检查第一行的符号
是否为"{"，然后再读入一行，用 statement_list 函数进行目标符号序列检查读入符号是否为"}"，然后
再读入一行，检查是否为"while"，然后再读入一行用 expression 函数进行表达式检查，最后读入剩
下的字符串用 statement 函数进行状态检查。
5
每个非终结符号的 First 和 Follow 集合:
First(<ID>)=a|b|…|z|A|B|…|Z Follow(<ID>)=a|b|…|z|A|B|…|Z
First(<NUM>)=a|b|…|z|A|B|…|Z Follow(<NUM>)=a|b|…|z|A|B|…|Z
First(<letter>)=a|b|…|z|A|B|…|Z Follow(<letter>)=#
First(<digit>)=1|2|…|9|0 Follow(<digit>)=#
First(<singleword>)=+|-|*|/|=|（|）|{|}|%|，|；|＜|＞|! Follow(<singleword>)=#
First(<doubleword>)=＞=|＜=|！=|== Follow(<doubleword>)=#
First(<commend_first>)=/ Follow(<commend_first>)=#
First(<commend_last>)=* Follow(<commend_last>)=#
First(<program>)=int Follow(<program>)=#
First(<statement>)=int|if|while|for|read|write Follow(<statement>)=#
First(<int_stat>)=int Follow(<int_stat>)=#
First(<if_stat>)=if Follow(<if_stat>)=#
First(<while_stat>)=while Follow(<while_stat>)=#
First(<do-while_stat>)=do-while Follow(<do-while_stat>)=#
First(<for_stat>)=for Follow(<for_stat>)=#
First(<write_stat>)=write Follow(<write_stat>)=#
First(<read_stat>)=read Follow(<read_stat>)=#
First(<compound_stat>)=int|if|while|for|read|write Follow(<compound_stat>)=#
First(<expression_stat>)=ID Follow(<expression_stat>)=#
First(<expression>)=ID Follow(<expression>)=#
First(<bool_expr>)=ID Follow(<bool_expr>)=#
First(< additive_expr>)=ID Follow(< additive_expr>)=#
First(<term>)=ID Follow(<term>)=#
First(<factor>)=ID|NUM Follow(<factor>)=#
输出错误信息函数：
void error(int es,char line[10]){
iserr=1;
switch (es)
{
case 10: printf("打开文件失败!\n", Scanout); break;
case 1: printf("缺少{!\t%s\n",line); break;
case 2: printf("缺少}!\t%s\n",line); break;
