《编译原理》实验指导及报告书新资料.docx
《《编译原理》实验指导及报告书新资料.docx》由会员分享，可在线阅读，更多相关《《编译原理》实验指导及报告书新资料.docx（20页珍藏版）》请在冰点文库上搜索。
《编译原理》实验指导及报告书新资料
《编译原理》实验指导及报告书
/学年第学期
姓名：
______________
学号：
______________
班级：
______________
指导教师：
______________
计算机科学与工程学院
2016
编译原理实验初步
一、实验目的
1、熟练掌握使用CODEBLOCK进行C程序编程，提高阅读程序与调试程序的能力。
2、掌握堆栈与队列的应用。
3、掌握C语言中对字符串处理的常见函数与方法。
4、熟悉编程规范，养成对重要的程序段进行必要的注释说明。
二、实验内容与步骤
1、下面的程序是对一个简单的算术表达式进行计算求值，并输出表达式的值与该表达式的后缀形式。
该程序在求值与转换后缀形式时使用了2个堆栈和1个队列。
请认真阅读程序和调试，并将程序补充完整。
#include
#include
#include
#defineERROR0
#defineOK1
#defineSTACK_INT_SIZE10/*存储空间初始分配量*/
#defineQueue_Size20
typedefintElemType;/*定义元素的类型*/
typedefstruct{
charQdata[Queue_Size];
intfront,rear;
}SeqQueue;
typedefstruct{
ElemType*base;
ElemType*top;
intstacksize;/*当前已分配的存储空间*/
}SqStack;
SqStackOPTR,OPND;
SeqQueueSeQ;
charPreTab[7][7]={{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','x'},
{'>','>','>','>','x','>','>'},
{'<','<','<','<','<','x','='}
};//该矩阵中，X字符表示不存在优先关系，在分析过程查找到这个值，表示表达式有错。
char*OpretorS="+-*/（）#";//运算符集
char*Express="3*（7-2）-6*2";//初始化的表达式
//注意本程序只分析1位整数的表达式的运算，所以输入的表达式要注意！
！
//能力强的同学自己进行扩展：
增加词法分析过程进行拼数。
intInitStack（SqStack*S）;/*构造空栈*/
intpush（SqStack*S,ElemType*e）;/*入栈*/
intPop（SqStack*S）;/*出栈*/
voidinitQueue（SeqQueue*Q）{/*队列初始化*/
Q->front=0;
Q->rear=0;
}
intEnterQueue（SeqQueue*Q,charc）{/*入队*/
if（Q->rear==Queue_Size）
{printf（"\n队列满，无法入队！
\n"）;returnERROR;}
Q->Qdata[Q->rear]=c;
Q->rear++;
returnOK;
}
intOutQueue（SeqQueue*Q,char*e）{/*出队*/
if（Q->front==Q->rear）
{printf（"\n队列空，无法出队！
\n"）;returnERROR;}
*e=Q->Qdata[Q->front++];
returnOK;
}
intInitStack（SqStack*S）{
S->base=（ElemType*）malloc（STACK_INT_SIZE*sizeof（ElemType））;
if（!
S->base）returnERROR;
S->top=S->base;
S->stacksize=STACK_INT_SIZE;
returnOK;
}/*InitStack*/
intPush（SqStack*S,ElemTypee）{
if（（S->top-S->base）>STACK_INT_SIZE）return0;
*S->top=e;
S->top++;
returnOK;
}
intPop（SqStack*S）{
inte;
if（S->top==S->base）return0;
S->top--;
e=*S->top;
return*S->top;
}
//判定c是否运算符，若是运算符则返回该运算符在运算符集中的位置，这样就能扫描优先//关系表，确定相邻运算符之间的优先级
intIsOps（charc）{
inti=0;
char*p;
p=OpretorS;
while（i<7）
{if（*p++==c）break;
i++;
}
returni;
}
charPrecede（charc1,charc2）{//返回c1与c2运算符的优先关系
inti,j;
i=IsOps（c1）;
j=IsOps（c2）;
if（PreTab[i][j]=='x'）return0;
returnPreTab[i][j];
}
intOperate（inta,charTheOp,intb）{//进行TheOp计算
switch（TheOp）{
case'+':
returna+b;
case'-':
returna-b;
case'*':
returna*b;
case'/':
returna/b;
}
return0;
}
intmain（）{
char*ScanChar;
charc1,c;
charTheOp;
intb,a,digit;
InitStack（&OPTR）;
Push（&OPTR,'#'）;
InitStack（&OPND）;
initQueue（&SeQ）;
ScanChar=Express;
c=*ScanChar;
while（c!
='#'||*OPTR.top!
='#'）
{if（c==0）c='#';
if（IsOps（c）>=7）//判定是否是运算符，若IsOps的值>=7，则c是操作数
{digit=c-'0';//将字符转换成相应的数值
Push（&OPND,digit）;//操作数入栈
EnterQueue（&SeQ,c）;//操作数入队
c=*++ScanChar;
}
else
{c1=*（OPTR.top-1）;
switch（Precede（c1,c））//调用哪个函数
{case'<':
Push（&OPTR,c）;
c=*++ScanChar;
break;
case'=':
//脱括号
TheOp=Pop（&OPTR）;
if（c!
=0&&c!
='#'）
c=*++ScanChar;
break;
case'>':
TheOp=Pop（&OPTR）;//参与计算的运算符出栈
EnterQueue（&SeQ,TheOp）;//参与运算的运算符入队
b=Pop（&OPND）;
a=Pop（&OPND）;
Push（&OPND,Operate（a,TheOp,b））;
break;
default:
printf（"\n算术表达式错误！
\n"）;
returnERROR;
}
}
}
printf（"\n算术表达式：
%s--->后缀表达式为：
",Express）;
while（SeQ.rear-SeQ.front!
=0）//将队列输出即为表达式的后缀形式
{OutQueue（&SeQ,&c）;printf（"%c",c）;}
printf（"\n其结果为：
%d",Pop（&OPND））;//输出表达式的值
return0;
}
2、修改上面的程序：
要求通过键盘输入表达式，运行程序并纪录运行过程和结果，至少处理3个不同的表达式。
第一次运行：
第二次运行：
第三次运行：
三、实验小结与体会
四、实验评分和标准
1、（程序功能）程序调通并能实现基本的功能50分
2、（实验态度）事先准备充分，上机调试认真，程序功能完整20分
3、（实验报告）实验分析和总结报告认真30分
五、教师评语
补充试验
（1）
一、试验要求：
修改试验初步中的源程序，使其能实现2位以上的整数的四则运算。
二、说明与提示
1、主要是增加实现拼数的功能。
为实现拼数，可应用堆栈NumStack来存储当前的数字，若当前的字符不是数字，则弹出NumStack栈中的所有数字进行拼数。
如1、2、3依次入栈，则弹出栈进行拼数：
3×1＋2×10＋1×10×10＝123。
2、参考代码：
if（IsOps（c）>=7）//判定是否是运算符，若IsOps的值>=7，则c是操作数
{digit=c-'0';//将字符转换成相应的数值
Push（&NumStack,digit）;//数字入栈
EnterQueue（&SeQ,n）;//数字入队
c=*++;
}
else{
if（NumStack非空）{
弹出NumStack中所有数字，进行拼数得到整数n;
Push（&OPND,n）;//操作数n入栈
}
c1=*（OPTR.top-1）;
……
}
三、调试与运行过程
要求至少3个以上的测试数据（必须含有错误表达式的测试数据）
补充试验
（2）
一、试验要求：
编写一程序，实现对一个C语言源程序进行相关统计：
1、源程序共有多少行（包含注释行）lines。
2、编译预处理命令有几条。
（行首为“＃”字符为编译预处理命令）commands。
3、忽略注释行。
（行首为“//”，或包含在“/*”与“*/”之间的字符串）rems。
4、共有多少条语句；统计赋值语句、for语句、while语句（包括do……while语句）的个数。
分别对应全局变量statements、asings；fors；whiles
二、说明与提示
注意：
必须确保读取的源程序语法是正确的。
1、为了提高读文件的效率，可设置1K字节的缓冲区：
charbuffer[1024]，每次从文件读取1K个字符（一般较小的源文件就读1次）进行处理，直至文件结束。
注意：
打开文件的方式应该是“只读”方式。
如：
intfd,size;
charbuffer[1024];
fd=open（“e:
/temp/my.c”,O_RDONLY）;//必须先准备好文件e:
/temp/my.c
size=read（fd,buffer,sizeof（buffer））;//size为从文件中实际读取的字节数
当然也可以用其它相关的文件操作函数，如fopen，更详细的例子请参阅C程序手册。
2、Tab字符的ASCII值为0x09；换行回车的ASCII值为0x0D、0x0A；空格ASCII值为0x20。
这些字符作为单词的分隔符。
3、以“;”结束的为语句，包括说明定义语句。
统计“;”个数不一定等于语句的个数，例如：
for（i=0;i同样“=”个数不一定等于赋值语句的个数，例如：
if（i==n）
for（i=0;i例如：
当取得当前单词是for，就可调用自定义函数Isfor来判定和处理：
for其后必定是“（”字符，并将P指针移动到“）”字符的下个字符。
4、整个统计过程要求仅扫描1遍程序，这样就要求设置1个扫描指针p，指向buffer字符串的当前待处理的位置，从左至右扫描。
三、调试与运行过程
要求至少要对2个源程序进行统计。
提示：
耐心点，不难。
可以逐步实现各个统计功能，最后进行整合。
实验一词法分析
一、实验目的
1、掌握词法分析的基本概念。
2、用DFA实现词法分析。
二、实验内容与步骤
正则表达式如下：
Signednat=（+|-）?
nat
nat=[0—9]
1、请查阅描述正则表达式相关的资料，并描述下列符号的含义：
（）
？
[]
+
2、请描述上述正则表达式的含义，并画出与其对应的有穷自动机。
含义：
对应的有穷自动机如下所示：
2、用代码实现该有穷自动机DFA。
要求：
①从键盘输入一个字符串，判别是否符合上述正则表达式规则，并给出正确与错误的信息；
②程序要求可以重复处理多个输入，直到输入结束符为止；
③调试并运行该程序，给出运行实例与结果；
注1：
可用自己喜欢的实现方式。
注2：
建议采用状态转换表，这样涉及的面多一些。
注3：
优秀的同学可采用两种以上的方法实现。
程序代码清单：
（若程序代码太长，可自行添加页面）
运行结果：
（至少5个不同测试数据，必须包含能得出正确和错误信息的数据）
三、实验小结与体会
要求：
从实验准备、操作、运行结果和遇到问题、参考书查阅、解决办法等方面小结。
四、实验评分和标准
1、（实验准备）给出正确的有穷自动机DFA10分
2、（程序功能）程序调通并能实现基本的功能50分
3、（实验态度）事先准备充分，上机调试认真，程序功能完整20分
4、（实验报告）实验分析和总结报告认真20分
五、教师评语
实验二语法分析——递归下降分析法
一、实验目的
1、掌握语法分析的基本概念和思路
2、详细了解递归子程序法的分析处理
二、实验内容
给出如下文法G[Z]：
Z→aAcB∣Bd
A→AaB∣c
B→bBc∣b
1、求产生式右部各侯选式的FIRST（）集合；
2、修改文法，消除左递归和回溯；
3、对修改后的文法，用递归子程序法构造语法分析程序。
①、从键盘输入一个由a、b、c组成的字符串，判别是否符合上述文法定义的语法，给出正确与错误信息；
②、程序要求能重复输入，直到输入结束符为止；
程序代码清单：
运行结果：
（至少6个不同测试数据，必须包含能得出正确和错误信息的数据）
三、实验小结与体会
要求：
从实验准备、操作、运行结果和遇到问题、参考书查阅、解决办法等方面小结。
四、评分标准
1、（实验准备）给出正确的消除左递归和回溯的文法10分
2、（程序功能）程序调通并能实现基本的功能50分
3、（实验态度）事先准备充分，上机调试认真，程序功能完整20分
4、（实验报告）实验分析和总结报告认真20分
五、教师评语
实验三语法分析
（2）－预测分析法
一、实验目的
1、掌握LL
（1）文法的预测分析表的构造方法
2、编写基于预测分析法的语法分析器。
二、实验内容
1、判定如下文法G[S]是否是LL
（1）文法：
S→MH|a
H→LSo|
K→dML|
L→eHf
M→K|bLM
2、上述G[S]文法若是LL
（1）文法，则构造LL
（1）分析表
3、参考教材图5.11预测分析程序流程图，编写出基于预测分析方法的语法分析器。
要求对输出每步推导的过程（如教材P95表5.4所示的分析过程）。
提示：
⑴产生式可存储在数组中，如：
Char*Rules[2]={“S->MH”，“H->LSo”}
⑵预测分析表用二维数组M存储，每行表示某个非终结符，每列表示某个终结符，M数组中的值仅存储产生式在数组Rules的序号即可。
为确定非终结符与终结符在数组M的序号，可定义分别包含非终结符与终结符的字符集，如：
Char*VN=“SHKLM”；
Char*VT=“aodefb＃”//特别注意不能忘记＃，它作为分析的结束标志
⑶分析过程使用堆栈Stack，注意堆栈的初始化，当进行推导时，产生式右部入栈的顺序为产生式的逆序。
⑷注意产生式的推导实质为直接将栈顶的非终结符出栈。
程序代码清单：
运行结果：
（至少2个不同测试数据，必须包含能得出正确和错误信息的数据）
三、实验小结与体会
要求：
从实验准备、操作、运行结果和遇到问题、参考书查阅、解决办法等方面小结。
四、评分标准
1、进行LL
（1）文法判定，构造出LL
（1）分析表10分
2、（程序功能）程序调通并能实现基本的功能50分
3、（实验态度）事先准备充分，上机调试认真，程序功能完整20分
4、（实验报告）实验分析和总结报告认真20分
五、教师评语
实验四TINY语言的词法分析实现
一、实验目的
通过对样本语言TINY语言词法分析程序的设计和实现，使学生能进一步理解和掌握词法分析的原理和实现方法。
二、预习与准备
1、TINY语言语法定义的完整BNF描述如下：
2、TINY语言的单词和单词类别如下：
保留字
特殊符号
其他
If
Then
Else
End
Repeat
Until
Read
write
+
-
*
/
=
<
（
）
;
:
=
数
（一个或更多的数字）
标识符
（一个或更多的字母）
从表中可知，TINY的单词为3个典型类型：
保留字，特殊符号和“其他”单词。
其他单词为“数”和“标识符”，数由一个或更多的数字组成，标识符由一个或更多的字母构成。
除了单词之外，TINY语言还遵循如下的词法惯例：
注释应放在花括号{}内，且不可嵌套；代码应是自由格式；空白格由空格、制表符和换行符组成；最长子串原则后须接识别单词。
TINY语言的详细介绍请同学自己查阅相关资料。
三、实验内容
为样本语言TINY编写一个扫描器（词法分析程序）。
1、画出TINY语言的确定性有穷自动机（DFA）。
2、根据DFA，用C语言编写一个程序，程序的功能为：
（1）读入TINY语言编写的源程序；
（2）对源程序进行分析，识别出一个一个的单词；
（3）打印出所有单词及单词类型。
源程序清单：
3、调试并运行：
①TINY语言编写的源程序清单：
②运行及结果
四、提示（建议采用状态转换表实现）
1、它的DFA经修改后如下：
2、TINY语言的状态转换表
输入字符
1
2
3
4
5
6
7
8
9
状态
编号
空白格
数
字
字
符
{
}
：
=
单个特
殊字符
其它
字符
接受状态
START
0
0
2
3
1
5
4
5
5
5
no
INCOMMENT
1
1
1
1
1
1
1
1
1
[5]
no
INNUM
2
[5]
2
[5]
[5]
[5]
[5]
[5]
[5]
[5]
no
INID
3
[5]
[5]
3
[5]
[5]
[5]
[5]
[5]
[5]
no
INASSIGN
4
[5]
[5]
[5]
[5]
[5]
[5]
[5]
[5]
[5]
no
DONE
5
yes
注1：
词法分析只考虑单词的构造，不考虑语法。
注2：
该状态表采用3个数组存放。
注3：
相关数组如下：
T数组
Advence数组
Accept数组
五、实验小结与体会
要求：
从实验准备、操作、运行结果和遇到问题、参考书查阅、解决办法等方面小结。
六、评分标准
1、（实验准备）给出正确的确定性有穷自动机（DFA）。
10分
2、（程序功能）程序调通并能实现基本功能。
50分
3、（实验态度）事先准备充分，上机调试认真，程序功能完善。
20分
4、（实验报告）实验分析和总结报告认真。
20分
七、教师评语
升级会员 