计科1304班廖成0902130408编译原理实验报告.doc

计科1304班_廖成_0902130408_编译原理实验报告

CENTRAL SOUTH UNIVERSITY

编译原理课程
实验报告

姓 名： 廖 成

学 号： 0902130408

专业班级： 计算机科学及技术1304班

指导老师： 张修如

实验一 计算FIRSTVT集

一、实验目的

进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC 。

二、实验内容

设计一个由正规文法生成FIRSTVT集的算法动态模拟，实现以下功能：
1．输入一个文法G；
2．输出由文法G构造FIRSTVT集的算法；
3．输出FIRSTVT集。

三、实验要求

1．思想的正确性，采用合适的数据存储结构等；
2．程序实现的正确性，程序整体结构合理、编程风格规范等；
3．程序功能的完善程度，包括功能的基本实现、基本完善、完全实现；
4．工作认真、独立完成实验。

四、实验步骤

1． 问题理解和分析：充分地分析和理解问题本身，弄清要求做什么；
2． 确定解决问题的方法：主要是找到解决问题的主要思路，该怎么做；
3．详细设计和编码：确定算法的主要流程，再进行编程；
4．程序调试和运行：掌握程序调试和排错的基本方法，增加编程的感觉和解决问题的成就感；
五、程序设计

5.1基本算法：

构造集合FIRSTVT(P)的算法，按FIRSTVT(P)的定义，可以用如下两条归则来构造：
(1)若有产生式P→a…或→Qa…，则a∈FIRSTVT(P)
(2)若a∈FIRSTV且有产生式P→Q…，则a∈FIRSTVT(P)构造算法：
建立一个二维布尔数组F[P,a]，使得F[P,a]为真的条件适当且仅当a∈FIRSTVT(P)；再用一个栈STACK，把所有初值为真的数组元素F[P,a]的符号对(P,a)全都放到栈中；算法如下：
(1)将布尔矩阵各元素置假；栈置空；
(2)按照归则(1)查看产生式，对于P→a…或P→Qa..，置相应F[P,a]为真，符号对(P,a)入栈；
(3)按规则(2)，对栈施加如下操作：弹出栈定符号对记作(Q,a)，查看所有产生式是否有形如P→Q…产生式，若有，且a∈FIRSTVT(P)，则将F[P,a]置为真，并把(P,a)入栈；
(4)重复(3)，直到栈空为止。

5.2定义数据结构：

在程序中，用两个字符数组vn[M]和vt[N]分别用来存储所有的非终结字符集及终结字符集。为了记录非终结符的FIRSTVT集，为此建立一个布尔数组F[M][N]，记录非终结符的FIRSTVT集。
比如，F[i][j]=true表示vt[j]属于FIRSTVT(vn[i])，值为false表示相应的终结符不属于非终结符的FIRSTVT集。
为了简便起见，程序中又构造了一个两维布尔数组first[M][M N]来表示推导关系。数组第一维的M个字符代表非终结符；数组第二维的前M个字符代表非终结符，后N个字符代表终结符。
以first数组为例，fist[i][M j]代表非终结符vn[i]=P及非终结符vt[j]=a有推导关系P →a…；fist[i][j]代表非终结符vn[i]=P及非终结符vt[j]=Q有推导关系或P→Qa..。
相关的数据结构定义如下：
char vn[M],vt[N]; //非终结字符及终结字符数组
bool first[M][M N],last[M][M N]; //以布尔数组形式定义推导关系
char vn[M],vt[N]; //非终结字符及终结字符数组
int stp; //堆栈栈顶指针
符号栈的数据结构：
struct relation int vn; int vt; //结构体用来说明终结符vt及非终结符vn之间的关系，若关系存在说明vt属于FIRSTVT(vn)

六、关键代码

#include
#include
#define N 10
#define M 10
using namespace std; //用于存储FIRSTVT集
char FIRSTVT0[N],FIRSTVT1[N],FIRSTVT2[N],FIRSTVT3[N],FIRSTVT4[N]; //接受输入
char INPUT[N][M];//存储FIRSTVT集
void setFIRSTVT(char X,int T)
void FIRSTVT(char X,int S)
void main()
inti,j;
printf("请输入文法(按两次回车结束):");
for(i=0;i<N;i++)
{
for(j=0;j<M,j++)
{
scanf("%c",&INPUT[i][j]);
if(INPUT[i][j]=='') break;
if(INPUT[i][0]=='') break;
}
} //保存FIRSTVT集
for(i=0;INPUT[i][0]!='';i++)
{
FIRSTVT(INPUT[i][0],i);
}
printf("FIRSTVT SET:");
for(i=0;INPUT[i][0]!='';i++)
{}
switch(i)
{
case 0:
{
printf("FIRSTVT(");
printf("%",INPUT[0][0]);
printf(")=");
for(j=0;FIRSTVT0[j]!='0';j++)
{
printf("%c",FIRSTVT0[j]);
if(FIRSTVT0[j 1]!='0')
printf("");
}
printf(",");
break;
}
case 1:
{
printf("FIRSTVT(");
printf("%c",INPUT[1][0]);
printf(")=");
for(j=0;FIRSTVT1[j]!='0';j++)
{
printf("%c",FIRSTVT1[j]);
if(FIRSTVT1[j 1]!='0')
printf(",");
}
printf("");
break;
}
case 2:
{
printf("FIRSTVT(");
printf("%c",INPUT[2][0]);
printf(")=");
for(j=0;FIRSTVT2[j]!='0';j++)
{
printf("%c",FIRSTVT2[j]);
if(FIRSTVT2[j 1]!='0')
printf(",");
}
printf("");
break;
}
case 3:
{
printf("FIRSTVT(");
printf("%c",INPUT[3][0]);
printf(")=");
for(j=0;FIRSTVT3[j]!='0';j++)
{
printf("%c",FIRSTVT3[j]);
if(FIRSTVT3[j 1]!='0')
printf(",");
}
printf("");
break;
}
case 4:
{
printf("FIRSTVT(");
printf("%c",INPUT[4][0]); printf(")=");
for(j=0;FIRSTVT4[j]!='0';j++)
{
printf("%c",FIRSTVT4[j]);
if(FIRSTVT4[j 1]!='0')
printf(",");
}
printf("");
break;
}
default :break;
printf("");
system("pause");

实验二 自上而下语法分析

一、 实验目的

加深对语法分析器工作过程的理解；加强对预测分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。

二、 实验内容

在实验1的基础上，用自上而下语法分析分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。

三、 实验要求：

1. 对语法规则有明确的定义；
2. 编写的分析程序能够对实验一的结果进行正确的语法分析；
3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；
4. 实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。

四、 实验步骤

1. 定义目标语言的语法规则；
2. 求解预测分析方法需要的符号集和分析表；
3. 依次读入实验一的分析结果，根据预测分析的方法进行语法分析，直到源程序结束；
4. 对遇到的语法错误做出错误处理。

五、 设计思路和实现过程

本实验是使用LL（1）方法实现的语法分析器，我是用的是MFC实现的设计思路分为以下几步：
1、 先读入输入串，判断输入串有没有语法错误，如有语法错误，提示第几个语法错误，退出；
2、 将“或”语句拆开，如果有左递归，消除左递归；
3、 判断可以产生空字符的非终结符，将其储存在一个数组中；
4、 计算非终结符的first集，follow集；
5、 计算select集；
6、 创建预测分析表；
7、 对照预测分析表对句子进行分析，输出每一步的操作。

六、 错误处理

1、 如果未输入文法，则提示输入文法；
2、 如果文法有错误，既不是以类似于“S->”开头的，则提示错误发生在第几行；
3、 如果文法不是LL（1）文法，程序会予以提示；
4、 如果句子不是以“#”结尾的，或者句子中含有大写字母的，予以提示；
5、 计算follow集时，如果follownumkey大于某个值，则可认定求follow集陷入死循环，即有右递归或间接右递归，此时跳出去，终止死循环。

七、 关键代码

void CGrammaanalysisDlg::OnChange()
{
int n=0;
UpdateData();

int i, nLineCount = m_gramma1.GetLineCount();//m_gramma是及edit控件关联的变量

CString strText;

// Dump every line of text of the edit control.

for (i=0; i < nLineCount; i++) //检测每一句文法输入是否正确
{
// length of line i:
int len = m_gramma1.LineLength(m_gramma1.LineIndex(i));
m_gramma1.GetLine(i, strText.GetBuffer(len), len);
strText.ReleaseBuffer(len);
if(strText.IsEmpty())
break;
if(!getin(i,strText))//整理
return;
// MessageBox(strText);//输出得到的每行数据
}
m_gramma.Empty();
Delpare(); //消除左递归
deduce0_colec(); //将所有能推导出0的非终符放在数组colec0[30]中
Select_Collection(); //创建select集
Estab_preanatab(); //创建预测分析表
key=1;

}

bool CGrammaanalysisDlg::getin(int i,CString strLine)//整理
{
char line_no = i+'0';

if (!isupper(strLine[0])||strLine[1]!='-'||strLine[2]!='>')
{
CString error="The Syntax on line "+(CString)line_no+" is wrong! please check and enter again:\n";
MessageBox(error);
return false;
}
else
{
int m=0;
for(int j=0;j<strLine.GetLength();j++)
{
if(strLine[j]!='|')
{
stotax[sto_tax][m++]=strLine[j];
continue;
}
else
{
stotax[sto_tax][m]='\0';
sto_tax++;
stotax[sto_tax][0]=stotax[sto_tax-1][0];
stotax[sto_tax][1]=stotax[sto_tax-1][1];
stotax[sto_tax][2]=stotax[sto_tax-1][2];
m=3;
continue;
}
}
stotax[sto_tax][m]='\0';
sto_tax++;
i=0;
startchar=stotax[0][0];
return TRUE;

}

}

void CGrammaanalysisDlg::Delpare() //消除左递归
{

ll_key=0;
keylr=0;
for(int i=0;i<sto_tax;i++)
strcpy(_stotax[i],stotax[i]);
_sto_tax=sto_tax;
int key;
char p[30];
char key_c;
for( i=0;i<_sto_tax;i++)
{

key_c=_stotax[i][0];
if(_stotax[i][0]==_stotax[i][3])
{
findcapital();
for(int j=0;j<_sto_tax;j++)
{
if(_stotax[j][0]==key_c)
{
keylr=1;
if(_stotax[j][3]==_stotax[j][0])
{
strcpy(&_stotax[j][3],&_stotax[j][4]);
_stotax[j][strlen(_stotax[j])]=capital;
_stotax[j][0]=capital;
_stotax[j][strlen(_stotax[j])+1]='\0';
_stotax[_sto_tax][0]=capital;
_stotax[_sto_tax][1]=':';
_stotax[_sto_tax][2]='=';
_stotax[_sto_tax][3]='0';
_stotax[_sto_tax][4]='\0';
_sto_tax++;
}
else if(_stotax[j][3]!='0')
{
int d;
d=strlen(_stotax[j]);
_stotax[j][d]=capital;
_stotax[j][d+1]='\0';
}
}
}
}
}
char keyc[30];
for( i=0;i<_sto_tax;i++)
{
key=0;
strcpy(keyc,_stotax[i]);
if(isupper(_stotax[i][3]))
{
for(int j=0;j<=_sto_tax;j++)
{
if(keyc[0]!=_stotax[j][0])
if(_stotax[j][0]==keyc[3])
{
if(key==0)
{
strcpy(p,&_stotax[i][4]);
strcpy(&_stotax[i][3],&_stotax[j][3]);
strcpy(&_stotax[i][strlen(_stotax[i])],p);
key=1;
}
else
{
_stotax[_sto_tax][0]=_stotax[i][0];
_stotax[_sto_tax][1]=':';
_stotax[_sto_tax][2]='=';
strcpy(&_stotax[_sto_tax][3],&_stotax[j][3]);
strcpy(&_stotax[_sto_tax][strlen(_stotax[_sto_tax])],p);
_sto_tax++;
}

}
}
}
for( int n=0;n<_sto_tax;n++)
{
key_c=_stotax[n][0];
if(_stotax[i][0]==_stotax[i][3])
{
keylr=1;
findcapital();
for(int j=0;j<_sto_tax;j++)
{
if(_stotax[j][0]==key_c)
{
if(_stotax[j][3]==_stotax[j][0])
{
strcpy(&_stotax[j][3],&_stotax[j][4]);
_stotax[j][strlen(_stotax[j])]=capital;
_stotax[j][0]=capital;
_stotax[j][strlen(_stotax[j])+1]='\0';
_stotax[_sto_tax][0]=capital;
_stotax[_sto_tax][1]=':';
_stotax[_sto_tax][2]='=';
_stotax[_sto_tax][3]='0';
_stotax[_sto_tax][4]='\0';
_sto_tax++;
}
else if(_stotax[j][3]!='0')
{
int d;
d=strlen(_stotax[j]);
_stotax[j][d]=capital;
_stotax[j][d+1]='\0';
}
}
}
}
}

}
if(keylr==1)
{
MessageBox("该文法有直接或间接左递归，消除左递归后的文法为：\n");

for( i=0;i<_sto_tax;i++)
{
strcpy(stotax[i],_stotax[i]);
}
sto_tax=_sto_tax;
}

for( i=0;i<_sto_tax;i++)
{
m_gramma+=_stotax[i];
m_gramma.Delete(m_gramma.GetLength());
m_gramma+="\r\n";
//m_gramma[m_gramma.GetLength()-1]="\r\n";
}
m_gramma+='\0';
UpdateData(false);
}

void CGrammaanalysisDlg::First_Collection(char p[]) //求字符串p的first集，把结果保存在数组firstchars[30]中
{
if(islower(p[0]))
firstchars[first_num++]=p[0];
else if(isupper(p[0]))
{
for(int i=0;i<sto_tax;i++)
if(stotax[i][0]==p[0])
if(islower(stotax[i][3]))
firstchars[first_num++]=stotax[i][3];
for( i=0;i<strlen(p);i++)
{
if(isupper(p[i]))
{
char *q;
for(int n=0;n<sto_tax;n++)
if(p[i]==stotax[n][0])
{
q=&stotax[n][3];
First_Collection(q);
}
int key=0;
for(int j=0;j<colec0num;j++)
if(colec0[j]==p[i])
{
key=1;
break;
}
if(key==0)
break;
}
else if(islower(p[i]))
{
firstchars[first_num++]=p[i];
break;
}
}
}
}

void CGrammaanalysisDlg::Follow_Collection(char p) //求字符p的follow集，把结果保存在数组followchars中
{
if(p==stotax[0][0])
followchars[follow_num++]='#';
for(int i=0;i<sto_tax;i++)
{
for(int j=3;j<strlen(stotax[i]);j++)
if(p==stotax[i][j])
{
if(islower(stotax[i][j+1]))
{
followchars[follow_num++]=stotax[i][j+1];
break;
}
else if(stotax[i][j+1]=='\0')
{
if(follownumkey>=30) //如果follownumkey大于某个值，则可认定求follow集陷入死循环，即有右递归或间接右递归，此时跳出去，终止死循环
{
follownumkey=0;
break;
}
follownumkey++;
Follow_Collection(stotax[i][0]);
break;
}
else if(isupper(stotax[i][j+1]))
{

char *q;
q=&stotax[i][j+1];
first_num=0;
First_Collection(q);
for(int m=0;m<first_num;m++)
followchars[follow_num++]=firstchars[m];
int key1=0;
for(int n=j+1;n<strlen(stotax[i]);n++)
{
int key2=0;
for(int r=0;r<colec0num;r++)
if(stotax[i][n]==colec0[r])
key2=1;
if(key2==0)
{
key1=1;
break;
}
}
if(key1==0)
{
if(follownumkey>=30) //如果follownumkey大于某个值，则可认定求follow集陷入死循环，即有右递归或间接右递归，此时跳出去，终止死循环
{
follownumkey=0;
break;
}
follownumkey++;
Follow_Collection(stotax[i][0]);

}
break;
}
}
}
}

void CGrammaanalysisDlg::Select_Collection() //求每条产生式的select集，存放在数组selectchars[30][30]中
{
for(int i=0;i<sto_tax;i++)
{
int select_num=0;
int key1=0;
int key2=0;
for(int j=3;j<strlen(stotax[i]);j++)
{
for(int m=0;m<colec0num;m++)
if(colec0[m]==stotax[i][j])
key1=1;
if(key1==0)
{
key2=1;
break;
}
}
if(stotax[i][3]=='0') //产生式右边为0，则把follow集加入select集中
{
follownumkey=0;
follow_num=0;
Follow_Collection(stotax[i][0]);
for(int r=0;r<follow_num;r++)
{
int key5=0;
for(int v=0;v<select_num;v++)
if(followchars[r]==selectchars[i][v])
key5=1;
if(key5==0)
selectchars[i][select_num++]=followchars[r];
}
selectchars[i][select_num]='\0';
break;
}

if(key2==0) //表示产生式右边能推出0，则把first集和follow集加入select集中
{
first_num=0;
First_Collection(&stotax[i][3]);
for(int q=0;q<first_num;q++)
{
int key3=0;
for(int s=0;s<select_num;s++)
if(firstchars[q]==selectchars[i][s])
key3=1;
if(key3==0)
selectchars[i][select_num++]=firstchars[q];
}
follownumkey=0;
follow_num=0;
Follow_Collection(stotax[i][0]);
for(int p=0;p<follow_num;p++)
{
int key4=0;
for(int t=0;t<select_num;t++)
if(followchars[p]==selectchars[i][t])
key4=1;
if(key4==0)
selectchars[i][select_num++]=followchars[p];
}
selectchars[i][select_num]='\0';
}
else //表示产生式右边不能推出0，则把first集加入select集中
{
first_num=0;
First_Collection(&stotax[i][3]);
for(int q=0;q<first_num;q++)
{
int key3=0;
for(int s=0;s<select_num;s++)
if(firstchars[q]==selectchars[i][s])
key3=1;
if(key3==0)
selectchars[i][select_num++]=firstchars[q];
}
selectchars[i][select_num]='\0';
}

}

}

bool CWord_analysisDlg::IsDigit(){

if (ch>='0' && ch<='9')
return true;
else
return false;

}

void CGrammaanalysisDlg::Estab_preanatab() //创建预测分析表
{
int i,j;
//如果分析表中有一项有两个产生式，
//则可确认该文法为非LL(1)文法，也不能改写为LL(1)文法，不能进行确定的自顶向下分析
for(i=0;i<130;i++)
for(j=0;j<130;j++)
for(int m=0;m<20;m++)
preanatab[i][j][m]='$'; //初始化分析表，以便重复建立
for(i=0;i<sto_tax;i++)
{
for(j=0;j<strlen(selectchars[i]);j++)
{
int p=int(stotax[i][0]);
int q=int(selectchars[i][j]);
if(preanatab[p][q][0]=='$')
strcpy(preanatab[p][q],stotax[i]);
else
{
MessageBox("该文法为非LL(1)文法，也不能改写为LL(1)文法，不能进行确定的自顶向下分析!\n");
ll_key=1;
goto notll1;
}

}
}
notll1:
{
}
}

void CGrammaanalysisDlg::Analyse_course() //分析过程
{

char inputchars[100]; //存放要分析的字符
int inpoint; //输入串指针
char anastack[100]; //分析栈
int anapoint; // 分析栈指针
int i=1;

anastack[0]='#';
anastack[1]=startchar;
anastack[2]='\0';
anapoint=1;

inpoint=0;
i=0;

while(m_setence[i]!='#')
{

if(isupper(m_setence[i]))
{
printf("输入的字符串不能有大写字母:\n");
return;
}
inputchars[inpoint++]=m_setence[i];
i++;
}

inputchars[inpoint++]='#';
inputchars[inpoint]='\0';
inpoint=0;

m_analysis.DeleteAllItems();

i=1;
while(!(anastack[anapoint]=='#' && inputchars[inpoint]=='#'))
{
if(anastack[anapoint]!=inputchars[i