编译原理实验指导及报告书.doc

《编译原理》实验指导及报告书

《编译原理》实验指导及报告书

/ 学年 第 学期

姓 名：______________
学 号：______________
班 级：______________
指导教师：______________

计算机科学及工程学院
2016

编译原理 实验初步
一、实验目的
1、熟练掌握使用CODEBLOCK进行C程序编程，提高阅读程序及调试程序的能力。
2、掌握堆栈及队列的应用。
3、掌握C语言中对字符串处理的常见函数及方法。
4、熟悉编程规范，养成对重要的程序段进行必要的注释说明。
二、实验内容及步骤
1、下面的程序是对一个简单的算术表达式进行计算求值，并输出表达式的值及该表达式的后缀形式。该程序在求值及转换后缀形式时使用了2个堆栈和1个队列。请认真阅读程序和调试，并将程序补充完整。
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define ERROR 0
#define OK 1
#define STACK_INT_SIZE 10 /*存储空间初始分配量*/
#define Queue_Size 20
typedef int ElemType; /*定义元素的类型*/

typedef struct{
char Qdata[Queue_Size];
int front,rear;
}SeqQueue;

typedef struct{
ElemType *base;
ElemType *top;
int stacksize; /*当前已分配的存储空间*/
}SqStack;

SqStack OPTR, OPND;
SeqQueue SeQ;

char PreTab[7][7]={{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','x'},
{'>','>','>','>','x','>','>'},
{'<','<','<','<','<','x','='}
}; // 该矩阵中，X字符表示不存在优先关系，在分析过程查找到这个值，表示表达式有错。

char *OpretorS="+-*/()#"; // 运算符集
char *Express="3*(7-2)-6*2"; // 初始化的表达式
// 注意本程序只分析1位整数的表达式的运算，所以输入的表达式要注意！！
// 能力强的同学自己进行扩展：增加词法分析过程进行拼数。

int InitStack(SqStack *S); /*构造空栈*/
int push(SqStack *S,ElemType *e); /*入栈*/
int Pop(SqStack *S); /*出栈*/

void initQueue(SeqQueue *Q){/*队列初始化*/
Q->front=0;
Q->rear=0;
}
int EnterQueue(SeqQueue *Q,char c){ /*入队*/
if (Q->rear==Queue_Size)
{ printf("\n队列满，无法入队！\n");return ERROR; }
Q->Qdata[Q->rear]=c;
Q->rear++;
return OK;
}
int OutQueue(SeqQueue *Q,char *e){ /*出队*/
if(Q->front==Q->rear)
{ printf("\n队列空，无法出队！\n");return ERROR; }
*e=Q->Qdata[Q->front++];
return OK;
}
int InitStack(SqStack *S){
S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base;
S->stacksize=STACK_INT_SIZE;
return OK;
}/*InitStack*/
int Push(SqStack *S,ElemType e){
if ((S->top-S->base)>STACK_INT_SIZE) return 0;
*S->top=e;
S->top++;
return OK;
}
int Pop(SqStack *S){
int e;
if (S->top==S->base ) return 0;
S->top--;
e=*S->top;
return *S->top;
}

//判定c是否运算符，若是运算符则返回该运算符在运算符集中的位置，这样就能扫描优先//关系表，确定相邻运算符之间的优先级
int IsOps(char c){
int i=0;
char *p;

p=OpretorS;
while( i<7 )
{if (*p++==c) break;
i++;
}
return i;
}

char Precede(char c1,char c2){ //返回c1及c2运算符的优先关系
int i,j;
i=IsOps(c1);
j=IsOps(c2);
if ( PreTab[i][j]=='x' ) return 0;
return PreTab[i][j];
}
int Operate(int a,char TheOp,int b){ //进行TheOp计算
switch ( TheOp ){
case '+': return a+b;
case '-': return a-b ;
case '*': return a*b ;
case '/': return a/b ;
}
return 0;
}

int main(){

char *ScanChar;
char c1,c;
char TheOp;
int b,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") ;
return ERROR ;
}
}
}
printf("\n算术表达式：%s --->后缀表达式为：",Express);
while(SeQ.rear- SeQ.front!=0 ) // 将队列输出即为表达式的后缀形式
{ OutQueue(&SeQ,&c);printf("%c",c);}
printf("\n其结果为：%d",Pop (& OPND )); // 输出表达式的值
return 0;
}
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字节的缓冲区：char buffer[1024]，每次从文件读取1K个字符（一般较小的源文件就读1次）进行处理，直至文件结束。
注意：打开文件的方式应该是“只读”方式。如：
int fd,size;
char buffer[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<n;i++){ }
同样“=”个数不一定等于赋值语句的个数，例如：
if(i= =n)
for(i=0;i<n;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、（实验准备）给出正确的有穷自动机DFA 10分
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 | e
K→dML | e
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，注意堆栈的初始化，当进行推导时，产生式右部入栈的顺序为产生式的逆序。
⑷ 注意 e 产生式的推导实质为直接将栈顶的非终结符出栈。
程序代码清单：

运行结果：（至少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分
七、教师评语

36 / 36