语法分析器实验报告可运行.docx

语法分析器实验报告可运行.docx

《语法分析器实验报告可运行.docx》由会员分享，可在线阅读，更多相关《语法分析器实验报告可运行.docx（32页珍藏版）》请在冰点文库上搜索。

语法分析器实验报告可运行

xx大学

XX系

实验报告

XX至XX学年第X学期

课程名称

编译原理

学号

XXX

学生姓名

XXX

年级

XXX级

专业

XXX

教学班号

XXX

实验地点

XXX

实验时间

XXXX

主讲教师

XXX

辅导教师

实验

（二）

实验名称

语法分析

软件环境

Windowsxp

VC++

硬件环境

P4

实验目的

一、实验目的：

 根据某一文法编制调试LL

（1）分析程序，以便对任意输入的符号串进行分析。

本次实验的目的主要是加深对预测分析LL

（1）分析法的理解。

二实验要求:

1.LL

（1）分析法的前提:

改造文法:

消除二义性,消除左递归,提取左因子.

2.设计出模块结构,测试数据,初步编制好程序

3.程序要求:

生成LL

（1）分析表:

程序输入输出示例:

对文法用LL

（1）分析法对任意输入的符号串进行分析,输出的格式如下:

（1）LL

（1）分析程序，编制人：

姓名，学号，班级

（2）输入以#结束的符号串（包括+—*/（）i#）：

在此位置输入符号串

（3）输出过程如下：

步骤

分析栈

剩余输入串

所用产生式

1

E

i+i*i#

E→TG

（4）输入符号串为非法符号串（或者为合法符号串）

4.模块结构:

（1）定义部分：

定义常量、变量、数据结构。

（2）初始化：

设立LL

（1）分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；

（3）控制部分：

从键盘输入一个表达式符号串；

（4）利用LL

（1）分析算法进行表达式处理：

根据LL

（1）分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。

实验内容（应包括实验题目、实验要求、实验任务等）

功能描述:

LL

（1）分析法是一种不带回溯的非递归的自上而下的分析法.其基本思想是根据输入串的当前输入符号来唯一确定选用某条规则来进行推倒,当这个输入符号与推倒的第一个符号相同时再取输入串的下一个符号,继续确定下一个推倒应选的规则,如此下去,直到推倒出被分析的输入串为止.

LL

（1）分析法实验设计思想及算法:

实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）

程序流程图:

实验过程记录：

实验过程中对文法修改后且输入相同的符号串后所形成的分析表是一样的，这是一处错误，另外输入某个符号串后进行无休止运行，以上两种错误通过上网查询以及和同学交流得以解决。

实验总结：

LL

（1）分析器又称预测分析法，是一种不带回溯的非递归自上而下分析法，

一个LL

（1）分析器由一张LL

（1）分析表、一个先进后出分析栈和一个控制程序组成。

附录（可包括源程序清单或其它说明）

源程序：

#include

#include

#include

#include

#include

#definePro_MidSym_Max2

#definePro_RightSym_Max10

#defineUnTInfo_Fir_Max10

#defineUnTInfo_Fol_Max10

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

typedefstructProNode{//产生式结构

charleftSym;//产生式左边的符号

charmidSym[Pro_MidSym_Max];//产生式推导符号

charrightSym[Pro_RightSym_Max];//产生式右边的符号，不超过十个

intlength;//产生式长度

}ProNode;

typedefstructUnTInfo{//每个非终结符的信息结构，包括first和follow集合

charfirst[UnTInfo_Fir_Max];

charfollow[UnTInfo_Fol_Max];

}UnTInfo;

typedefstruct{//构造顺序栈,存储符号

char*base;

char*top;

intstacksize;

}SqStack;

typedefstructQNode{//构造单链队列，存储输入符号串

chardata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct{

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针

}LinkQueue;

intproNum;//产生式个数

charUnTerminate[15];//非终结符表

charTerminate[15];//终结符表

charProNull[20];//记录能产生空字符的非终结符

ProNodesheet[15][15];//分析表

charselect[15][15];//select集合，以便于构造分析表

LinkQueueRemain;//剩余符号串

voidInitUnTInfo（UnTInfounTInfo[],intunTInfoNum）;

//初始化函数，对每个非终结符的信息结构进行初始化

voidInitProNode（ProNodeproNode[],intproNum）;

//初始化函数，对每个非终结符的产生式结构进行初始化

voidInitStack（SqStack&s）;//初始化栈

voidInitQueue（LinkQueue&q）;//初始化队列

voidEnQueue（LinkQueue&q,charc）;//在队尾插入新的元素

voidExit（）;//栈溢出处理函数

voidError（）;//出错处理

voidPush（SqStack&s,charc）;//入栈

charPop（SqStack&s）;//出栈

voidInitSheet（ProNode**sheet,intm,intn）;//初始化分析表函数

boolReadPro（ProNodeproNode[],charfileName[]）;//从文件读取产生式函数

voidPrintPro（ProNodeproNode[],intproNum）;//显示产生式

voidSetUnTerminate（charUnTerminate[],ProNodeproNode[],intproNum）;//设置非终结符表

voidSetTerminate（charUnTerminate[],ProNodeproNode[],intproNum）;//设置终结符表

intGetNumofUT（charUnTerminate[]）;//获得非终结符个数

intGetNumofT（charTerminate[]）;//获得终结符个数

intGetUTLoaction（charUnTerminate[],charc）;//获得非终结符在非终结符表中的位置

intGetTLocaction（charUnTerminate[],charc）;//获得终结符在终结符表中的位置

voidFirst（ProNodeproNode[],UnTInfounTInfo[]）;//计算各非终结符的First集

voidFollow（ProNodeproNode[],UnTInfounTInfo[]）;//计算各非终结符的Follow集

voidAddChar（charchArray[],charc）;//将非终结符的所有first值加入First集

voidAddCharToChar（charchArray[],charotherArray[]）;//将非终结符的所有first集加入First集

voidAddFollow（charfollow[],charc）;//将非终结符的所有follow值加入Follow集

boolIsNull（charc）;//非终结符能否产生空字符

boolIsTerminate（charc）;//判断是否为终结符号

voidSetSheet（ProNodeproNode[],UnTInfounTInfo[]）;//设置分析表

voidSetSelect（ProNodeproNode[],UnTInfounTInfo[]）;//设置Select集合

voidInputSym（）;//输入字符串函数

voidScan（）;//分析扫描的主控程序

charGetSym（LinkQueue&q）;//获取下一字符

voidPrintSym（SqStack&s）;//显示符号栈符号

voidPrintRemain（LinkQueue&q）;//显示剩余符号串

voidPrintSheet（introw,intcol）;//显示所使用产生式

voidSuccess（）;//分析成功

voidmain（）{

charfileName[10];

cout<<"编制人：

涂君兰，20042003，三班"<

cout<<"请输入放有产生式的文件（如：

pro.txt）:

"<

cin>>fileName;

ProNodeproNode[20];

InitProNode（proNode,20）;

if（ReadPro（proNode,fileName））{

/*输出文法产生式*/

cout<<"该文法产生式为：

"<

PrintPro（proNode,proNum）;

/*设置非终结符表和终结符表*/

SetUnTerminate（UnTerminate,proNode,proNum）;

SetTerminate（Terminate,proNode,proNum）;

/*输出First集*/

intNumofUT=GetNumofUT（UnTerminate）;

intNumofT=GetNumofT（Terminate）;

UnTInfounTinfo[20];

InitUnTInfo（unTinfo,20）;

/*输出First集*/

First（proNode,unTinfo）;

/*输出Follow集*/

Follow（proNode,unTinfo）;

/*设置select*/

SetSelect（proNode,unTinfo）;

/*输出sheet*/

cout<

"<

SetSheet（proNode,unTinfo）;

cout<<"\t";

for（intjj=0;jj

cout<

cout<

for（intmm=0;mm

cout<

for（intmn=0;mn

PrintSheet（mm,mn）;

cout<<"\t";

}

cout<

}

InputSym（）;//输入字符串

Scan（）;//主控程序

}

else

Error（）;

}

voidInitProNode（ProNodeproNode[],intproNum）{

//初始化函数，对每个非终结符的产生式结构进行初始化

for（inti=0;i

proNode[i].leftSym='\0';

memset（proNode[i].midSym,0,Pro_MidSym_Max）;

memset（proNode[i].rightSym,0,Pro_RightSym_Max）;

proNode[i].length=0;

}

}

voidInitUnTInfo（UnTInfounTInfo[],intunTInfoNum）{

//初始化函数，对每个非终结符的信息结构进行初始化

for（inti=0;i

intfirLength=strlen（unTInfo[i].first）;

intfolLength=strlen（unTInfo[i].follow）;

memset（unTInfo[i].first,0,UnTInfo_Fir_Max）;

//将非终结符号的Frist集合初始化为空串

memset（unTInfo[i].follow,0,UnTInfo_Fol_Max）;

//将非终结符号的follow集合初始化为空串

}

}

voidInitStack（SqStack&s）{//初始化栈

s.base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;

if（!

s.base）Exit（）;

s.top=s.base;

s.stacksize=STACK_INIT_SIZE;

}

voidPush（SqStack&s,charc）{//入栈

if（s.top-s.base>=s.stacksize）{//栈满，追加存储空间

s.base=（char*）realloc（s.base,（s.stacksize+STACKINCREMENT）*sizeof（char））;

if（!

s.base）Exit（）;//存储分配失败

s.top=s.base+s.stacksize;

s.stacksize+=STACKINCREMENT;

}

*（s.top）=c;

s.top=s.top+1;

}

charPop（SqStack&s）{//出栈

if（s.top==s.base）returnNULL;

s.top=s.top-1;

chartmpChar=*（s.top）;

returntmpChar;

}

voidInitQueue（LinkQueue&q）{//初始化队列

q.front=q.rear=（QueuePtr）malloc（sizeof（QNode））;

if（!

q.front）Exit（）;//存储分配失败

q.front->next=NULL;

}

voidEnQueue（LinkQueue&q,charc）{//在队尾插入新的元素

QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;

if（!

p）Exit（）;//存储分配失败

p->data=c;

p->next=NULL;

q.rear->next=p;

q.rear=p;

}

voidExit（）{//溢出处理

cout<<"溢出！

"<

}

voidError（）{//出错处理

cout<<"分析出错！

"<

}

voidInitSheet（ProNode**sheet,intm,intn）{

//初始化分析表函数,以便将无定义的表格定义为error

for（inti=0;i

for（intj=0;j

sheet[i][j].leftSym='\0';//用0标记无定义的表格

}

}

boolReadPro（ProNodeproNode[],charfileName[]）{

FILE*pFile;

if（（pFile=fopen（fileName,"r"））==NULL）{

cout<<"打开文件出错！

"<

returnfalse;

}

chartmpChar;

inttmpIndex=0;

fscanf（pFile,"%c",&tmpChar）;

while（tmpChar!

='#'）{//求出产生式的个数

if（tmpChar==';'）

tmpIndex++;

fscanf（pFile,"%c",&tmpChar）;

}

proNum=tmpIndex;

rewind（pFile）;

for（inti=0;i

//同时可将非终结符置于非终结符号表

fscanf（pFile,"%c%c%c",&proNode[i].leftSym,&proNode[i].midSym[0],\

&proNode[i].midSym[1]）;

proNode[i].midSym[2]='\0';

fscanf（pFile,"%c",&tmpChar）;

intj=0;

while（tmpChar!

=';'）{

proNode[i].rightSym[j]=tmpChar;

fscanf（pFile,"%c",&tmpChar）;

j++;

}

proNode[i].rightSym[j]='\0';

proNode[i].length=j;

}

returntrue;

}

voidPrintPro（ProNodeproNode[],intproNum）{//显示产生式

for（inti=0;i

cout<

for（intj=0;j

cout<

cout<

}

}

voidSetUnTerminate（charUnTerminate[],ProNodeproNode[],intproNum）{

//获得非终结符，存储于非终结符表

for（inti=0;i

boolflag=true;

inttmpLength=strlen（UnTerminate）;

for（intj=0;j<=tmpLength;j++）{

if（UnTerminate[j]==proNode[i].leftSym）{//若已存在，则进入下个产生式

flag=false;

break;

}

}

if（flag）{

UnTerminate[tmpLength]=proNode[i].leftSym;//将非终结符加入到非终结符表

UnTerminate[tmpLength+1]='\0';

}

}

}

voidSetTerminate（charTerminate[],ProNodeproNode[],intproNum）{

//获得终结符，存储于终结符表

inttmpLength;

boolflag;

for（inti=0;i

for（intk=0;k

flag=true;

tmpLength=strlen（Terminate）;

if（isupper（proNode[i].rightSym[k]））//若为非终结符号，则进入下一个字符

flag=false;

elseif（proNode[i].rightSym[k]=='^'）{

inttmpLength=strlen（ProNull）;

flag=false;

ProNull[tmpLength]=proNode[i].leftSym;//记录能产生空字符的产生式

ProNull[tmpLength+1]='\0';

}

elseif（flag）

for（intj=0;j<=tmpLength;j++）{

if（Terminate[j]==proNode[i].rightSym[k]）{

//若已存在，则进入下一个字符

flag=false;

break;

}

}

if（flag）{//将终结符加入到终结符表

Terminate[tmpLength]=proNode[i].rightSym[k];

Terminate[tmpLength+1]='\0';

}

}

}

}

intGetNumofUT（charUnTerminate[]）{//获得非终结符个数

returnstrlen（UnTerminate）;

}

intGetNumofT（charTerminate[]）{//获得终结符个数

returnstrlen（Terminate）;

}

boolIsNull（charc）{//非终结符能否产生空字符

intlen=strlen（ProNull）;

for（inti=0;i

if（ProNull[i]==c）

returntrue;

}

returnfalse;

}

boolIsTerminate（charc）{//判断是否为终结符号

intnum=GetNumofT（Terminate）;

boolflag=false;

for（inti=0;i

if（Terminate[i]==c）{

flag=true;

break;

}

}

returnfl