编译原理实验报告LL文法构造Word格式文档下载.docx
- 文档编号:5922216
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:27
- 大小:102.39KB
编译原理实验报告LL文法构造Word格式文档下载.docx
《编译原理实验报告LL文法构造Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《编译原理实验报告LL文法构造Word格式文档下载.docx(27页珍藏版)》请在冰点文库上搜索。
5、把实验结果写入一个新建立的文本文件。
六、测试数据
输入数据:
编辑一个文本文文件g.txt,在文件中输入如下内容:
S->
Qc|c|cab;
Q->
Rb|b;
R->
Sa|a;
正确结果:
本实验的输出结果是不唯一的,根据消除左递归是选择非终结符号的顺序不同,或选择新的非终结符号的不同,可能会得到不同的结果,下面只是可能的一个结果:
Qc|cT;
T->
@|ab;
//由于无法输出ε,用@代替
bcaU|caU|cabaU|aU;
U->
bcaU|@;
七、实验报告要求
实验报告应包括以下几个部分:
1、满足LL
(1)文法的分析条件;
转换前要求文法中不含回路(经过推导有形如P->
P之类的),也不含以ε为右部的产生式。
一个文法要能进行LL
(1)分析,那么这个文法应该满足:
无二义性,无左递归,无左公因子。
首先需要定义一些规则:
1.在程序运行前文法就必须输入进文本文件中,输入的文法只包含其中的所有产生式,并且默认其为可转换的非LL
(1)文法,即通过消除左递归和反复提取公共左因子,就转换成了LL
(1)文法。
2.输入的产生式为原实验1的结果,即一个非终结符只有一条产生式,候选之间用“|”隔开。
3.产生式与产生式之间只能以换行符或分号隔开。
4.开始符号对应的产生式必须第一个输入,即默认输入的第一个产生式的左部的大写字母是开始符号。
5.输入与输出都会保存在文本文件中文件名分别是g.txt和newg.txt,本实验测试数据时,将两个文本放在了桌面。
6.ε用@代替,输入与输出都使用@。
7.新产生的非终结符统一使用没有在非终结符集合中出现的大写字母。
8.规定产生式最多只有20个。
2、构造LL
(1)文法的算法;
算法:
1)从文本文件g.txt中读入文法,存入结构体中。
将第一个读到的大写字母记为开始符号S,将读到的包括开始符号在内的所有大写字母判定为非终结符,并将第一次出现的存入文法的非终结符集合中,终结符小写字母也一样。
将以换行符或分号隔开的字符串判断为一条产生式存入文法中。
实现函数是scanP()。
2)对文法中的产生式消除左递归。
实现函数是remove_left_recursion()。
3)对文法中的产生式反复提取公共左因子。
实现函数是remove_left_gene()。
4)向newg.txt中输出文法的所有产生式。
3、消除左递归文法和提取左因子算法实现方法;
消除左递归文法(包括其中用到其它的子函数):
/*字符串分割函数,将产生式右部的候选返回,识别‘|’,从pos位开始分割*/
stringstrsplit(stringstrTok,intpos){
stringstr;
size_tposition;
position=strTok.find("
|"
pos);
if(position!
=string:
:
npos){//找到了‘|’
str=strTok.substr(pos,position-pos);
}
else{//没找到
str=strTok.substr(pos,strTok.size()-pos);
returnstr;
}
/*获得一个文法中尚未定义的非终结符,即特定的大写字母*/
charGetWord(char*p){
charch,word[]={'
A'
'
B'
C'
D'
E'
F'
G'
H'
I'
J'
K'
L'
M'
N'
O'
P'
Q'
'
R'
S'
T'
U'
V'
W'
X'
Y'
Z'
};
intw,x;
for(w=0;
w<
26;
w++){
ch=word[w];
for(x=0;
x<
m;
x++){
if(ch==p[x]){
break;
}
}
if(x==m)break;
returnch;
/*判断非终结符是否已存在*/
boolcheckWord(charch,stringVn){
inti;
boolflag=true;
for(i=0;
i<
Vn.size();
i++){
if(ch==Vn[i])
flag=false;
returnflag;
/*化简无用产生式*/
voidsimplify(structgrammar*gp){
//存储从开始符号可以到达的非终结符的序列
intsVn[20];
//标记在哪个产生式
sVn[0]=0;
str.insert(0,1,gp->
Vn[0]);
//初始化设置开始符号
boolflag[20];
flag[0]=false;
//标记哪个产生式需要删除
charch;
inti,j,k,l,o;
str.size();
for(j=3;
j<
gp->
P[sVn[i]].size();
j++){
for(k=0;
k<
k++){
if(gp->
P[sVn[i]][j]<
'
||gp->
P[sVn[i]][j]>
)break;
//不是非终结符无需判断
P[sVn[i]][j]==gp->
Vn[k]){//判断从开始符号可以到达的非终结符在Vn的哪个位置
flag[k]=false;
if(checkWord(gp->
Vn[k],str)){//将在str中没有的有用非终结符插入str
inte=str.size();
sVn[e]=k;
str.insert(str.size(),1,gp->
Vn[k]);
}
break;
}
for(l=0;
l<
l++){//删除无用的产生式和相应的非终结符
charch;
if(flag[l]){
gp->
Vn[l]='
;
for(o=l+1;
o<
o++){
ch=gp->
Vn[o-1];
gp->
Vn[o-1]=gp->
Vn[o];
Vn[o]=ch;
P[o-1].clear();
P[o-1].s>
P[o]);
m--;
voidremove_left_recursion(structgrammar*gp){//子函数,消除文法左递归
inti,j,num_i,num_j,ipos,jpos;
charch_i,ch_j;
for(i=1;
m+1;
i++){
boolrepeat=true;
//标记相对于本轮循环上轮过程产生式是否有过变化,有则需要重新分割得到候选
num_i=0,ipos=3;
stringstr_i[20],restr_i[20],ex="
a"
ch_i=gp->
Vn[i-1];
//获取当前要被处理的非终结符,即Pi
//分割产生式,得到右部的所有候选
while(ipos!
=gp->
P[i-1].size()+1){
str_i[num_i]=strsplit(gp->
P[i-1],ipos);
restr_i[num_i]=str_i[num_i];
ipos=ipos+str_i[num_i].size()+1;
num_i++;
for(j=1;
=i-1;
if(!
repeat){
num_i=0,ipos=3;
ch_i=gp->
//重新获取当前要被处理的非终结符,即Pi
//分割产生式,得到右部的所有候选
while(ipos!
str_i[num_i]=strsplit(gp->
restr_i[num_i]=str_i[num_i];
ipos=ipos+str_i[num_i].size()+1;
num_i++;
repeat=true;
stringstr_j[20];
intl;
jpos=3;
num_j=0;
ch_j=gp->
Vn[j-1];
//获取当前要替换的非终结符,即Pj
//分割产生式,得到右部的所有候选
while(jpos!
P[j-1].size()+1){
str_j[num_j]=strsplit(gp->
P[j-1],jpos);
jpos=jpos+str_j[num_j].size()+1;
num_j++;
for(l=0;
num_i;
l++){//逐个判断Pi的候选中是否含有Pj,有则进行替换
stringchange;
ex[0]=ch_j;
size_tpos=restr_i[l].find(ex);
if(pos==string:
npos){continue;
}//无需替换
elseif(pos==0){//Pj在该候选的第一个字符
repeat=false;
//
strings=str_i[l].substr(1,str_i[l].size()-1);
//得到候选中除Pj外的剩余部分
str_i[l].s);
//清空字符串
intlink=0;
while
(1){//将Pj的所有候选与Pi中匹配的候选的剩余部分连接,中间还添加“|”
if(link==num_j)break;
str_j[link]+=s;
if(link==num_j-1)str_i[l]+=str_j[link];
elsestr_i[l]=str_i[l]+str_j[link]+"
link++;
elseif(pos==str_i[l].size()-1){//Pj在该候选的最后一个字符
strings=str_i[l].substr(0,str_i[l].size()-1);
while
(1){
str_j[link]=s+str_j[link];
else{//Pj在该候选的中间
strings1=str_i[l].substr(0,pos-1);
//得到该候选中Pj前的字符串
strings2=str_i[l].substr(pos+1,str_i[l].size()-pos-1);
//得到该候选中Pj后的字符串
str_j[link]=s1+str_j[link]+s2;
stringstri="
->
"
stri.insert(0,1,ch_i);
intindex=0;
while
(1){//将替换后的Pi的所有候选进行重组并存进文法中
if(index==num_i)break;
if(index==num_i-1)stri=stri+str_i[index];
elsestri=stri+str_i[index]+"
index++;
P[i-1]=stri;
//消除直接左递归
stringsplitstr[30],resplitstr[30];
ints=0,ps=3,h=0;
while
(1){//分割替换后的产生式
splitstr[s]=strsplit(gp->
P[i-1],ps);
resplitstr[s]=splitstr[s];
ps=ps+splitstr[s].size()+1;
if(ps==gp->
P[i-1].size()+1)break;
s++;
stringPi="
Pichange="
Pi=ch_i+Pi;
intlink=0,flag=-1;
boolflagpos[30];
charnewWord;
for(;
link<
=s;
link++){//遍历所有候选,校验其中是否有左递归
size_tposi;
posi=resplitstr[link].find(ch_i);
if(posi==0){//存在直接左递归
flag++;
//对候选标记左递归
if(flag==0){//处理出现左递归的第一个候选
newWord=GetWord(gp->
Vn);
//获取一个新的非终结符
gp->
Vn[m]=newWord;
Pichange=newWord+Pichange;
m++;
splitstr[link]=splitstr[link].substr
(1)+newWord;
flagpos[link]=false;
P[m-1]=Pichange+splitstr[link]+"
if(flag>
0){
P[m-1]=gp->
P[m-1]+splitstr[link]+"
//对消除了直接左递归的候选进行重组成为产生式并存入文法
if(flag>
-1){
P[i-1]="
P[i-1].insert(0,1,ch_i);
for(;
h<
h++){
if(flagpos[h]){
splitstr[h]+=newWord;
P[i-1]=gp->
P[i-1]+splitstr[h]+"
P[m-1]+="
@"
P[i-1].erase(gp->
P[i-1].size()-1,1);
simplify(gp);
//化简无用的产生式
提取左因子(包括辅助函数):
//对字符串数组排序
voidstr_sort(string*str,intnum){
inti,j;
num;
for(j=i+1;
if(str[i]>
str[j])
str[i].s[j]);
/*子函数,提取左因子*/
voidremove_left_gene(structgrammar*gp){
intrule_a,i,j,k,l,matchnum,oldmatchnum,resize,size;
charch,newWord;
for(rule_a=0;
rule_a<
rule_a++){//遍历所有产生式
intbre=-1;
//标记已对产生式进行过左因子的提取
intoldpo=0;
intnum=0,ps=3;
stringstr[30],restr[30];
//前者用于判断,需要保持原样,后者用于对有公共左因子的候选进行提取,可变
while(ps!
P[rule_a].size()+1){//分割替换后的产生式
str[num]=strsplit(gp->
P[rule_a],ps);
restr[num]=str[num];
ps=ps+str[num].size()+1;
num++;
str_sort(str,num);
//对所有候选按ASCII码进行排序,以便于简化对公共左因子的判断,只需先对前面候选判断
str_sort(restr,num);
intca_i;
stringPa="
Pa.insert(0,1,gp->
Vn[rule_a]);
for(ca_i=0;
ca_i<
ca_i++){//对排序后的候选进行重组并存入文法
if(ca_i==num-1)
Pa+=str[ca_i];
else
Pa+=str[ca_i]+"
gp->
P[rule_a]=Pa;
intipo=0;
//辅助免除对已判断过有左因子的候选的遍历
for(i=0;
i++,i+=ipo){//遍历候选
ipo=0;
size=0;
resize=0;
oldmatchnum=0;
inti_s=str[i].size();
for(j=0;
i_s;
j++){//对候选的逐个字符遍历
matchnum=0;
//标记除了本身,有几个候选有公共左因子
ch=str[i][j];
intkf=num;
for(k=i+1;
num
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 实验 报告 LL 文法 构造