编译原理实验报告
实验名称 由正规文法构造正规式
实验时间 2013年6月5日星期三
院系 计算机
安徽大学
Author: idiot10
1. 试验目的
输入：任意的正规文法。
输出：相应的正规式。
2. 实验原理
3型文法（正则文法，线性文法）
如果对于某文法G ，P 中的每个规则具有下列形式：
U :: = T 或 U :: = WT
其中T ∈V T ；U,W ∈V N ，则称该文法G 为左线性文法。
如果对于某文法G ，P 中的每个规则具有下列形式：
U :: = T 或 U :: = TW
其中T ∈V T ；U, W∈V N ，则称该文法G 为右线性文法。
左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG 。
按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。
3型文法所确定的语言为3型语言L 3，3型语言可由确定的有限状态自动机来识别。
程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文法描述如下：
::=//
显然，该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法——正则表达式。正则表达式又称为正则式，每个正则表达式描述的集合称为正则集。
之所以采用正则表达式来描述，主要基于以下几点原因：
（1） 词法规则简单，无需上下文无关文法那样严格的表示法，用正则式
表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更为容易；
（2） 从正则式构造高效识别程序比上下文无关文法更容易；
（3） 可以从某个正则式自动地构造识别程序，它可以识别用该正则式表
示的字符串集合中的字符串，从而减轻后面要介绍的词法分析时的工作量。
（4） 可用于其他各种信息流的处理，例如，已经应用于某些模式识别问
题、文献目录检索系统以及正文编辑程序等。
正则表达式和正则集
设有字母表∑。∑上的正则表达式和它所表示的正则集递归地定义如下：
（1） ε和Φ都是∑上的正则表达式，它们所表示的正则集分别为{ε}和
Φ，其中ε是空串，Φ是空集；
（2） 任意的a ∈∑是正则表达式，它所表示的正则集是{a}；
（3） 如果e 1和e 2是∑上的任意的正则表达式，且分别表示的正则集为L
（e 1）和L （e 2），则：
∙ e 1/e2也是正则表达式，表示的正则集为L （e 1 / e2）＝L （e 1）∪L （e 2）。 ∙ e 1 e 2也是正则表达式，表示的正则集为L （e 1 e2）＝L （e 1）L （e 2）。
***∙ （e 1）也是正则表达式，表示的正则集为L （（e 1））＝L （e 1）。
定义中（1）和（2）定义了原子正则表达式，而（3）则表明字母表∑上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。
正则表达式的性质
如果两个正则表达式e 1和e 2表示的正则集相同，即值相等，则称它们是等价的。记为e 1＝e 2。
正则表达式与正则文法的关系
一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号Φ外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于 ::= 0/1/2/…/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/…/9所定义的字符串集合是相同的。正则集Φ，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。
3.. 实验内容
由正规（则）文法构造正规（则）式
4. 实验心得
通过实验明确了正规文法构造正规式的方法，对正规式及正规文法有了进一步的认识欲了解
5. 实验代码与结果
测试数据1：
A->xB
A->y
B->xB
B->yA
#
测试数据2
S->aA
S->a
A->aA
A->dA
A->a
A->d
#
测试数据3
S->aA
S->cB
S->a
A->aB
A->bB
A->b
B->cB
B->bA
B->c
#
源码：
#include
#include
using namespace std;
string ss[30]={"",""};
string dww[15]={"",""};
string snt="";
string dst[8]={"",""};
string donesnt="";
int num=0;
int dstl=0;
int dwl=0;
void setdst()
{
for(int i=0;i
dst[i]="";
dstl=0;
}
void getsnt()
{
for(int i=0;i
{
if(snt.find(ss[i].at(0))==-1)
snt+=ss[i].at(0);
}
}
string dispose1(string temp1)
{
string df="";
for(int i=0;i
{
int k=(int)temp1.at(i);
string ft=ss[k].substr(3);
if(i==0)
df+=ft;
else
{
df+='|';
df+=ft;
}
ss[k]="";
}
return df;
}
string dispose3(string temp3)
{
string df="";
for(int i=0;i
{
int k=(int)temp3.at(i);
string temp=ss[k].substr(3);
string sttr=temp.substr(0,temp.size()-1); if(i==0)
df+=sttr;
else
{
df+='|';
df+=sttr;
}
ss[k]="";
}
return df;
}
void erass()
{
for(int i=0;i
{
if(ss[i]=="")
{
for(int j=i+1;j
if(ss[j]!="")
break;
}
ss[i]=ss[j];
ss[j]="";
}
if(i==num)
{
ss[num]="";
break;
}
}
}
void handle(string cs,string ssnot)
{
char cc=cs.at(0);
string temp1="";
string temp2="";
string temp3="";
int i=0;
bool flagg=false;
while(!flagg)
{
flagg=true;
for(i=0;i
{
for(int j=0;j
if(ss[i].find(donesnt.at(j))!=-1)
flagg=false; bool flag=false; string sk=ss[i]; for(int k=0;k
{ temp2+=i; dst[dstl]=ss[i]; dstl++; ss[i]=""; flag=true; j=ssnot.size(); } } if(!flag) temp1+=i; } } } i=temp1.size(); num-=i; i=temp2.size(); num-=i; i=temp3.size(); num-=i; i=0; string dis1str=""; string dis2str=""; string temm=""; if(num>0) { dis1str="("; dis1str+=dispose1(temp1); dis1str+=")"; } else { if(temp3.size()==0) dis1str=dispose1(temp1); else { dis1str="("; dis1str+=dispose1(temp1); dis1str+=")"; } }
temm+=dispose3(temp3); if(temp3.size()==0)
dis2str="";
else
{
if(temm.size()==1)
dis2str=temm; else
{
dis2str="(";
dis2str+=temm; dis2str+=")";
}
dis2str+="*";
}
if(dis1str=="()")
dis1str="";
dis2str+=dis1str;
string arrow="->";
arrow+=dis2str;
dww[dwl]+=cs;
dww[dwl]+=arrow;
dwl++;
for(i=0;i
{
dww[dwl]=dst[i];
dwl++;
}
erass();
}
int main()
{
cout
for(;i
{
string tem="";
cin>>tem;
if(tem=="#")
break;
ss[i]=tem;
}
} num=i; getsnt(); for(i=snt.size()-1;i>=0;i--) { string ssnot=snt.substr(0,i); string cs=""; cs+=snt.at(i); handle(cs,ssnot); donesnt+=cs; } cout
编译原理实验报告
实验名称 由正规文法构造正规式
实验时间 2013年6月5日星期三
院系 计算机
安徽大学
Author: idiot10
1. 试验目的
输入：任意的正规文法。
输出：相应的正规式。
2. 实验原理
3型文法（正则文法，线性文法）
如果对于某文法G ，P 中的每个规则具有下列形式：
U :: = T 或 U :: = WT
其中T ∈V T ；U,W ∈V N ，则称该文法G 为左线性文法。
如果对于某文法G ，P 中的每个规则具有下列形式：
U :: = T 或 U :: = TW
其中T ∈V T ；U, W∈V N ，则称该文法G 为右线性文法。
左线性文法和右线性文法通称为3型文法或正则文法，有时又称为有穷状态文法，简写为RG 。
按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个终结符号加上单个非终结符号。
3型文法所确定的语言为3型语言L 3，3型语言可由确定的有限状态自动机来识别。
程序设计语言的单词可由正则文法产生，例如，标识符的定义可由正则文法描述如下：
::=//
显然，该文法描述了以字母开头的字母数字串的集合。现在要引入另一种适合于描述单词的表示法——正则表达式。正则表达式又称为正则式，每个正则表达式描述的集合称为正则集。
之所以采用正则表达式来描述，主要基于以下几点原因：
（1） 词法规则简单，无需上下文无关文法那样严格的表示法，用正则式
表示法来理解被定义的符号集合比理解由重写规则集合定义的语言更为容易；
（2） 从正则式构造高效识别程序比上下文无关文法更容易；
（3） 可以从某个正则式自动地构造识别程序，它可以识别用该正则式表
示的字符串集合中的字符串，从而减轻后面要介绍的词法分析时的工作量。
（4） 可用于其他各种信息流的处理，例如，已经应用于某些模式识别问
题、文献目录检索系统以及正文编辑程序等。
正则表达式和正则集
设有字母表∑。∑上的正则表达式和它所表示的正则集递归地定义如下：
（1） ε和Φ都是∑上的正则表达式，它们所表示的正则集分别为{ε}和
Φ，其中ε是空串，Φ是空集；
（2） 任意的a ∈∑是正则表达式，它所表示的正则集是{a}；
（3） 如果e 1和e 2是∑上的任意的正则表达式，且分别表示的正则集为L
（e 1）和L （e 2），则：
∙ e 1/e2也是正则表达式，表示的正则集为L （e 1 / e2）＝L （e 1）∪L （e 2）。 ∙ e 1 e 2也是正则表达式，表示的正则集为L （e 1 e2）＝L （e 1）L （e 2）。
***∙ （e 1）也是正则表达式，表示的正则集为L （（e 1））＝L （e 1）。
定义中（1）和（2）定义了原子正则表达式，而（3）则表明字母表∑上的正则表达式可由原子正则表达式或较简单的正则表达式通过联合、连接与闭包运算构成一般的正则表达式。
正则表达式的性质
如果两个正则表达式e 1和e 2表示的正则集相同，即值相等，则称它们是等价的。记为e 1＝e 2。
正则表达式与正则文法的关系
一个正则表达式的值是正则集，它是正则语言的另一种表示法。不难看出，除了符号Φ外，一个正则表达式的含义类似于正则文法的一个非终结符号规则右部的含义。例如，对于 ::= 0/1/2/…/9，由非终结符数字所产生的字符串集合与正则表达式0/1/2/…/9所定义的字符串集合是相同的。正则集Φ，它对应一个不包含任何句子的语言，引进的目的主要是为了理论上的完备性。
3.. 实验内容
由正规（则）文法构造正规（则）式
4. 实验心得
通过实验明确了正规文法构造正规式的方法，对正规式及正规文法有了进一步的认识欲了解
5. 实验代码与结果
测试数据1：
A->xB
A->y
B->xB
B->yA
#
测试数据2
S->aA
S->a
A->aA
A->dA
A->a
A->d
#
测试数据3
S->aA
S->cB
S->a
A->aB
A->bB
A->b
B->cB
B->bA
B->c
#
源码：
#include
#include
using namespace std;
string ss[30]={"",""};
string dww[15]={"",""};
string snt="";
string dst[8]={"",""};
string donesnt="";
int num=0;
int dstl=0;
int dwl=0;
void setdst()
{
for(int i=0;i
dst[i]="";
dstl=0;
}
void getsnt()
{
for(int i=0;i
{
if(snt.find(ss[i].at(0))==-1)
snt+=ss[i].at(0);
}
}
string dispose1(string temp1)
{
string df="";
for(int i=0;i
{
int k=(int)temp1.at(i);
string ft=ss[k].substr(3);
if(i==0)
df+=ft;
else
{
df+='|';
df+=ft;
}
ss[k]="";
}
return df;
}
string dispose3(string temp3)
{
string df="";
for(int i=0;i
{
int k=(int)temp3.at(i);
string temp=ss[k].substr(3);
string sttr=temp.substr(0,temp.size()-1); if(i==0)
df+=sttr;
else
{
df+='|';
df+=sttr;
}
ss[k]="";
}
return df;
}
void erass()
{
for(int i=0;i
{
if(ss[i]=="")
{
for(int j=i+1;j
if(ss[j]!="")
break;
}
ss[i]=ss[j];
ss[j]="";
}
if(i==num)
{
ss[num]="";
break;
}
}
}
void handle(string cs,string ssnot)
{
char cc=cs.at(0);
string temp1="";
string temp2="";
string temp3="";
int i=0;
bool flagg=false;
while(!flagg)
{
flagg=true;
for(i=0;i
{
for(int j=0;j
if(ss[i].find(donesnt.at(j))!=-1)
flagg=false; bool flag=false; string sk=ss[i]; for(int k=0;k
{ temp2+=i; dst[dstl]=ss[i]; dstl++; ss[i]=""; flag=true; j=ssnot.size(); } } if(!flag) temp1+=i; } } } i=temp1.size(); num-=i; i=temp2.size(); num-=i; i=temp3.size(); num-=i; i=0; string dis1str=""; string dis2str=""; string temm=""; if(num>0) { dis1str="("; dis1str+=dispose1(temp1); dis1str+=")"; } else { if(temp3.size()==0) dis1str=dispose1(temp1); else { dis1str="("; dis1str+=dispose1(temp1); dis1str+=")"; } }
temm+=dispose3(temp3); if(temp3.size()==0)
dis2str="";
else
{
if(temm.size()==1)
dis2str=temm; else
{
dis2str="(";
dis2str+=temm; dis2str+=")";
}
dis2str+="*";
}
if(dis1str=="()")
dis1str="";
dis2str+=dis1str;
string arrow="->";
arrow+=dis2str;
dww[dwl]+=cs;
dww[dwl]+=arrow;
dwl++;
for(i=0;i
{
dww[dwl]=dst[i];
dwl++;
}
erass();
}
int main()
{
cout
for(;i
{
string tem="";
cin>>tem;
if(tem=="#")
break;
ss[i]=tem;
}
} num=i; getsnt(); for(i=snt.size()-1;i>=0;i--) { string ssnot=snt.substr(0,i); string cs=""; cs+=snt.at(i); handle(cs,ssnot); donesnt+=cs; } cout