编译技术实验指导书06最新1.docx
《编译技术实验指导书06最新1.docx》由会员分享，可在线阅读，更多相关《编译技术实验指导书06最新1.docx（52页珍藏版）》请在冰点文库上搜索。
编译技术实验指导书06最新1
编译技术实验指导书
计算机科学与工程学院
前言
《编译技术》是计算机科学与技术、软件工程等专业的一门理论性较强的专业课，旨在培养大学生的计算机专业素质和基本编译程序设计的能力。
通过实验教学，使学生加深对所学知识的理解，掌握编译程序构造原理和实现技术。
它的目的和任务是：
让学生掌握编译程序的基本原理和实现技术，提高学生对程序设计语言的理解，让学生了解将高级程序设计语言源程序翻译成计算机能处理的目标代码语言的整个过程，培养学生的编译程序设计的能力。
编译程序的设计包括词法分析程序的设计、语法分析程序的设计、语义分析程序的设计和中间代码生成程序的设计等。
本实验指导书是金成植编著的《编译程序构造原理和实现技术》的配套教材。
编者根据计算机课程实践性强等特点，编写了本实验教程，帮助学生有计划地系统地上机实践。
根据教学内容和教学目标，实验指导书设计了八次实验，实验学时16学时，每个实验2学时。
学生应按照实验指导书的要求，完成指定的实验任务，并及时提交实验报告。
要求学生在每次实验之前做好预习，实验后按要求写出实验报告。
在每次实验过程中教师要考核学生每次实验的完成情况。
一、为保证实验效果学生应做到：
1、遵守实验室的规章制度，爱护教学设备。
2、学生必须按时上机下机。
3、禁止做与实验无关的内容，禁止利用实验学时玩计算机游戏；
4、每次实验前学生应做好预习，实验后按时提交实验报告。
二、实验报告的要求：
1、明确实验的目的及要求；
2、记录下相应编译阶段的程序设计的思想、程序代码及运行的结果；
3、说明实验中出现的问题和解决过程；
4、写出实验的体会和实验过程中没解决的问题。
由于编者水平有限，书中难免有错，敬请大家批评指正。
辽宁科技大学计算机学院科学系
２００9年2月
目录
实验一词法分析器的手工构造………………………………….…….…….....3
实验二词法分析器的自动生成…………………………………….………….10
实验三递归下降语法分析程序设计……………………………….…………18
实验四LL
（1）语法分析程序设计……………………………….……..………22
实验五LR语法分析器程序设计……………………….………..………..27
实验六说明语句的语法制导翻译..…………………………….…….…….….32
实验七中间代码生成程序设计.……………………………….…….……..….35
实验八微小编译器的设计………………………………….….……………37
实验一词法分析器的手工构造
实验类型：
验证性
实验要求：
必修
一、实验目的：
通过本次实验，使学生掌握词法分析的构造原理及实现技术，会编写简单程序设计语言的词法分析器。
二、实验要求：
1、通过词法分析基本原理和基本技术的学习，参照给定的词法分析程序样例，验证一个简单语言的词法分析程序，加深对词法分析基本原理和基本技术的理解。
2、从文件读入源程序，经预处理后进行词法分析，输出为单词串，即由（词法信息，语义信息）所组成的二元组序列；有一定检查词法错误的能力。
2、提交实验报告，报告内容包括：
目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
3、上机时间：
2学时。
三、实验原理
1、 词法分析器的功能和输出格式
词法分析器的功能是输入源程序，输出单词的Token序列。
词法分析器的单词符号可表示成的二元式（单词种别码，单词符号的属性值）。
本实验中，基本字、符号词采用一词一类的方式，标识符、常数采用的是一类一个类码的方式。
2、 单词的BNF表示
<标识符
-><字母
<字母数字串
<字母数字串
-><字母
<字母数字串|<数字
<字母数字串|<下划线
<字母数字串|ε
<无符号整数
->
<数字
<数字串
<数字串
->
<数字
<数字串
|ε
<运算符
->+|*|++|=
界符
->,|；|（|）|#
3、状态转换图
识别标识符的状态转换图
识别实常数和整常数的状态转换图
四、实验内容
请参照给定的C词法分析程序的样例，编写下列给定的源程序的VC++词法分析程序，屏幕显示结果。
begin
integerr;
r=r+10;
end
五、词法分析器的手工构造样例程序
#include
#include
#include
#include
#include
constshortWORDLEN=20;
structcode_val{
charcode;
charval[WORDLEN];
};
//预处理函数原型
voidpro_process（char*）;
//扫描函数原型
code_valscanner（char*）;
//拼接函数原型
voidconcat（char[],char）;
//查保留字表函数
charreserve（char[]）;
//主函数
voidmain（）
{
charbuf[4048]={'\0'};//扫描缓冲区
//预处理
pro_process（buf）;
//显示buf
cout<//单词识别
ofstreamcoutf（"Lex_r.txt",ios:
:
out）;
code_valt;//临时变量
do{
t=scanner（buf）;//调用一次扫描器获得一个单词二元式
cout<coutf<}while（t.code!
='#'）;
cout<<"Endoflexicalanalysis!
"<getch（）;
}
//扫描函数，每调用一次，返回一个单词的二元式。
structcode_valscanner（char*buf）
{
staticinti=0;//buf指针
structcode_valt={'\0',"NUL"};//临时变量
chartoken[WORDLEN]="";//用于拼接单词
//去除前导空格
while（buf[i]==''）i++;
//开始识别单词
//标识符或基本字
if（buf[i]>='a'&&buf[i]<='z'）{
while（buf[i]>='a'&&buf[i]<='z'||buf[i]>='0'&&buf[i]<='9'）
concat（token,buf[i++]）;
t.code=reserve（token）;//查保留字表
if（t.code=='i'）strcpy（t.val,token）;//是标识符
returnt;//返回标识符或基本字的二元式
}
//整常数或实常数
if（buf[i]>='0'&&buf[i]<='9'）{
while（buf[i]>='0'&&buf[i]<='9'）
concat（token,buf[i++]）;
if（buf[i]=='.'）{//实常数123.
concat（token,buf[i++]）;
while（buf[i]>='0'&&buf[i]<='9'）//123.4
concat（token,buf[i++]）;
t.code='y';
}
else//整常数
t.code='x';
strcpy（t.val,token）;
returnt;//返回当前单词整常数（123）或实常数（123.或123.4）的二元式
}
//实常数
if（buf[i]=='.'）{
concat（token,buf[i++]）;
if（buf[i]>='0'&&buf[i]<='9'）{
while（buf[i]>='0'&&buf[i]<='9'）
concat（token,buf[i++]）;
t.code='y';
strcpy（t.val,token）;
returnt;//返回当前单词实常数（.123）的二元式
}
else{//单个.错误词形
cout<<"Errorword>"<exit（0）;
}
}
//其余单词
switch（buf[i]）{
case',':
t.code=',';
break;
case';':
t.code=';';
break;
case'（':
t.code='（';
break;
case'）':
t.code='）';
break;
case'=':
t.code='=';
break;
case'+':
if（buf[++i]=='+'）
t.code='$';
else{
t.code='+';
i--;
}
break;
case'*':
t.code='*';
break;
case'#':
t.code='#';
break;
default:
//错误字符
cout<<"Errorchar>"<exit（0）;
}//endofswitch
i++;//指向下个单词
returnt;//返回当前单词的二元式
}
//拼接函数，原token="BEG",buf[i++]='I',调用后token="BEGI"。
voidconcat（chartoken[],charc）
{
for（inti=0;token[i];i++）;
token[i]=c;
token[++i]='\0';
}
charreserve（chartoken[]）
{
constchar*table[]={"begin","end","integer","real"};
constcharcode[]={"{}ac"};
for（inti=0;i<（int）strlen（code）;i++）
if（strcmp（token,table[i]）==0）returncode[i];
return'i';//标识符的单词种别为'i'
}
//预处理函数
voidpro_process（char*buf）
{
ifstreamcinf（"source.txt",ios:
:
in）;
inti=0;charold_c='\0',cur_c;//计数器，前一个字符，当前字符。
boolin_comment=false;//状态标志，false表示当前字符未处于注释中。
while（cinf.read（&cur_c,sizeof（char）））{//从文件读一个字符
switch（in_comment）{
casefalse:
if（old_c=='/'&&cur_c=='*'）{//进入注释
i--;//去除已存入扫描缓冲区的字符'/'
in_comment=true;
}
else{
if（old_c=='\\'&&cur_c=='\n'）//去除续行符'\'，包括后续换行符。
i--;//去除已存入扫描缓冲区的字符'\'
else{
if（cur_c>='A'&&cur_c<='Z'）cur_c+=32;//大写变小写
if（cur_c=='\t'||cur_c=='\n'）cur_c='';//空格
buf[i++]=cur_c;
}
}
break;
casetrue:
if（old_c=='*'&&cur_c=='/'）//离开注释
in_comment=false;
}//endofswitch
old_c=cur_c;//保留前一个字符
}//endofwhile
buf[i]='#';
}
实验二词法分析器的自动生成
实验类型：
验证性
实验要求：
必修
一、实验目的
通过本次实验，使学生掌握利用状态转换矩阵实现状态迁移，从而实现词法分析器的自动生成，完成对一个简单程序的单词的识别。
二、实验要求
1、构造描述每个单词的正规式，根据正规式Pi构造最终形成识别全部单词的NFAM。
对NFAM确定化构造DFAM'。
利用DFAM'识别一个简单程序设计语言的单词，屏幕输出单词的二元组序列。
2、提交实验报告，报告内容如下：
目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
3、上机时间：
2学时。
三、实验原理
1、自动生成过程概述
①构造描述每个单词的正规式Pi（1≤i≤N）。
②根据正规式Pi构造NFAMi（1≤i≤N），假定初态均为0。
在构造NFAMi的同时，逐步并且最终形成识别全部单词的NFAM。
③NFAM确定化
④重新标记，构造DFAM'。
2、实例（模型语言的词法）
①模型语言字符集
{'a'..'z'，'0'..'9'，'+'，'='，'*'，','，';'，'（'，'）'，'#'}
②模型语言单词集
基本字：
begin、end、integer、real
标识符：
以字母开始的数字字母串
无符号整常数：
数字串
运算符：
+、*、++、=
界符：
、;、（、）、#
③单词编码
基本字：
begin（'{',"NUL"}、end（'}',"NUL"）、integer（'a',"NUL"）、real（'c',"NUL"）
标识符：
（'i',字符串）
无符号整常数：
（'x',字符串）
运算符:
=（'=',"NUL"）、+（'+',"NUL"）、*（'*',"NUL"）、++（'$',"NUL"）
界符：
（',',"NUL"）、;（';',"NUL"）、（（'（',"NUL"）、）（'）',"NUL"）、#（'#',"NUL"）
3、实例解
①构造正规式
（令α=a|b|c|d|……|z，β=0|1|2|3|4|5|6|7|8|9）
标识符：
α（α|β）*
无符号整常数：
ββ*
运算符：
单词本身（例'='的正规式为'='，"++"的正规式为"++"）
界符：
单词本身（例';'的正规式为';'）
基本字通常是由字母构成，符合标识符规则，将基本字作为一种特殊标识。
②构造NFAM
③NFAM确定化
I
Iα
Iβ
I=
I+
I*
I,
I;
I（
I）
I#
{0}
{1,12,13}
{2,14,15}
{3}
{4,5}
{6}
{7}
{8}
{9}
{10}
{11}
{1,12,13}
{12,13}
{12,13}
{2,14,15}
{14,15}
{3}
{4,5}
{16}
{6}
{7}
{8}
{9}
{10}
{11}
{12,13}
{12,13}
{12,13}
{14,15}
{14,15}
{16}
④重新标记，构造DFAM'
状态/字符
α
β
=
+
*
;
（
）
#
0
1
2
3
4
5
6
7
8
9
10
1
11
11
2
12
3
4
13
5
6
7
8
9
10
11
11
11
12
12
13
四、实验内容
参照给定算法，构造一个识别简单程序设计语言单词的DFA。
五、扫描器控制程序的实现算法
#include
#include
#include
#include
#include
constshortWORDLEN=20;
structcode_val{
charcode;charval[WORDLEN];
};
//单词编码表
constchar*table[]={"begin","end","integer","real","=","+","++","*",",",";","（","）","#"};
constcharcode[]="{}ac=+$*,;（）#";
//DFA列字符
constcharCOL_CHAR[]="a0=+*,;（）#";
//状态转换矩阵（DFA）
constintDFA[][11]={//strlen（"a0=+*,;（）#"）=11
{1,2,3,4,5,6,7,8,9,10,0},
{11,11},
{0,12},
{0},
{0,0,0,13},
{0},
{0},
{0},
{0},
{0},
{0},
{11,11},
{0,12},
{0}
};
//预处理函数原型
voidpro_process（char*）;
//扫描函数原型
code_valscanner（char*）;
//主函数
voidmain（）
{
charbuf[4048]={'\0'};//扫描缓冲区
//预处理
pro_process（buf）;
//显示buf
cout<//单词识别
ofstreamcoutf（"Lex_r.txt",ios:
:
out）;
code_valt;//临时变量
do{
t=scanner（buf）;//调用一次扫描器获得一个单词二元式
cout<coutf<}while（t.code!
='#'）;
cout<<"Endoflexicalanalysis!
"<getch（）;
}
intcol（char）;//转换函数
voidconcat（char[],char）;//拼接函数原型
charsearch_table（char[]）;//查单词二元式编码表函数
structcode_valscanner（char*buf）//扫描函数，每调用一次，返回一个单词的二元式。
{
staticinti=0;//buf指针
structcode_valt={'\0',"NUL"};//临时变量
chartoken[WORDLEN]="";//用于拼接单词
//去除前导空格
while（buf[i]==''）i++;
//开始识别单词
intcur_state=0;
while（DFA[cur_state][col（buf[i]）]）{//存在后继状态
concat（token,buf[i]）;//拼接
cur_state=DFA[cur_state][col（buf[i]）];//进入下一状态
if（buf[++i]=='\0'）break;//指向下一字符，判缓冲区内字符是否处理完。
}
//判断当前状态是否是终态，若为非终态报错，终止程序运行。
在本例中不存在此情况，故略。
t.code=search_table（token）;//查单词二元式编码表
if（t.code=='?
'）{
if（token[0]>='a'&&token[0]<='z'）
t.code='i';
else
t.code='x';
strcpy（t.val,token）;
}
returnt;//返回当前单词的二元式
}
//转换函数
intcol（charc）
{
if（c>='a'&&c<='z'）c='a';
if（c>='0'&&c<='9'）c='0';
//constcharCOL_CHAR[]="a0=+*,;（）#";
for（inti=0;i<=（int）strlen（COL_CHAR）;i++）
if（c==COL_CHAR[i]）returni;
cout<<"Errorchar>"<}
//拼接函数，原token="BEG",buf[i++]='I',调用后token="BEGI"。
voidconcat（
升级会员 