LL1文法的判别教学内容.docx
- 文档编号:16299603
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:28
- 大小:125.22KB
LL1文法的判别教学内容.docx
《LL1文法的判别教学内容.docx》由会员分享,可在线阅读,更多相关《LL1文法的判别教学内容.docx(28页珍藏版)》请在冰点文库上搜索。
LL1文法的判别教学内容
虽然调查显示我们的创意计划有很大的发展空间,但是各种如“漂亮女生”和“碧芝”等连锁饰品店在不久的将来将对我们的创意小屋会产生很大的威胁。
“碧芝”最吸引人的是那些小巧的珠子、亮片等,都是平日里不常见的。
店长梁小姐介绍,店内的饰珠有威尼斯印第安的玻璃珠、秘鲁的陶珠、奥利的施华洛世奇水晶、法国的仿金片、日本的梦幻珠等,五彩缤纷,流光异彩。
按照饰珠的质地可分为玻璃、骨质、角质、陶制、水晶、仿金、木制等种类,其造型更是千姿百态:
珠型、圆柱型、动物造型、多边形、图腾形象等,美不胜收。
全部都是进口的,从几毛钱一个到几十元一个的珠子,做一个成品饰物大约需要几十元,当然,还要决定于你的心意。
“碧芝”提倡自己制作:
端个特制的盘子到柜台前,按自己的构思选取喜爱的饰珠和配件,再把它们串成成品。
这里的饰珠和配件的价格随质地而各有同,所用的线绳价格从几元到一二十元不等,如果让店员帮忙串制,还要收取10%~20%的手工费。
1、荣晓华、孙喜林《消费者行为学》东北财经大学出版社2003年2月
7、你喜欢哪一类型的DIY手工艺制品?
据统计,上海国民经济持续快速增长。
03全年就实现国内生产总值(GDP)6250.81亿元,按可比价格计算,比上年增长11.8%。
第三产业的增速受非典影响而有所减缓,全年实现增加值3027.11亿元,增长8%,增幅比上年下降2个百分点。
可是创业不是一朝一夕的事,在创业过程中会遇到很多令人难以想象的疑难杂症,对我们这些80年代出生的温室小花朵来说,更是难上加难。
大学生个性化消费增多是一种趋势。
当前社会、经济飞速发展,各种新的消费品不断增多,流行文化时尚飞速变化,处于校园与社会两者之间的大学生肯定会受影响。
目前在大学校园,电脑、手机、CD、MP3、录音笔被称为大学生的“五件武器”。
除了实用,这也是一种表明自己生活优越的炫耀性的东西。
现下很大一部分大学生中的“负债消费”表现的典型的超前享乐和及时行乐——其消费项目多半是用于奢侈浪费的非必要生活消耗。
如举办生日宴会、打网球、保龄球、上舞厅跳舞、进夜总会唱“卡拉OK”等。
“负债消费”使很多学生耽于物欲,发展严重者轻则引起经济纠纷,动武斗殴,影响同窗友谊,重则引发犯罪事件,于社会治安不利。
3、你是否购买过DIY手工艺制品?
(4)创新能力薄弱
(四)大学生对手工艺制品消费的要求实验四:
LL
(1)文法的判别
一、实验名称
LL
(1)文法的判别
二、实验目的
(1)能导出空串的非终结符算法
(2)实现首符集,后跟符集和可选集算法
(3)输出要指出是否为LL
(1)文法,
三、实验原理
①将数组X[]中对应每一非终结符的标记置初值为"未定"。
②扫描文法中的产生式。
(a)删除所有右部含有终结符的产生式,若这使得以某一非终结符为左部的所有产生式都被删除,则将数组中对应该非终结符的标记值改为"否",说明该非终结符不能推出ε。
(b)若某一非终结符的某一产生式右部为ε,则将数组中对应该非终结符的标志置为"是",并从文法中删除该非终结符的所有产生式。
例中对应非终结符A、B的标志改为"是"。
③扫描产生式右部的每一符号。
(a)若所扫描到的非终结符号在数组中对应的标志是"是",则删去该非终结符,若这使产生式右部为空,则对产生式左部的非终结符在数组中对应的标志改"是",并删除该非终结符为左部的所有产生式。
(b)若所扫描到的非终结符号在数组中对应的标志是"否",则删去该产生式,若这使产生式左部非终结符的有关产生式都被删去,则把在数组中该非终结符对应的标志改成"否"。
④重复③,直到扫描完一遍文法的产生式,数组中非终结符对应的特征再没有改变为止。
由②中(a)、(b)得知例中对应非终结符D的标志改为"否",对应非终结符A、B的标志改为"是"。
经过上述②中(a)、(b)两步后文法中的产生式只剩下:
S→AB和C→AD,也就是只剩下右部全是非终结符串的产生式。
再由③中的(a)步扫描到产生式S→AB时,在数组中A、B对应的标志都为"是",删去后S的右部变为空,所以S对应标志置为"是"。
最后由③中的(b)扫描到产生式C→AD时,其中,A对应的标志为"是",D对应的标志是"否",删去该产生式后,再无左部为C的产生式,所以C的对应标志改为"否"
四、实验小结
通过本次实验,熟悉了LL
(1)文法,掌握了LL
(1)文法的判定方法,具体实践了FIRST集、FOLLOW集、SELECT集的计算,加深了对LL
(1)文法的理解。
此外,将理论用于实践,亲身体会到了怎样求FIRST集等。
如何理解转化的过程是相当重要,以及如何去创建程序去实现这一转化过程。
这样的编程对于我来说是相当困难的,这次的程序并非自己编写的。
但是我会一步步去理解该程序的每步含义,争取就算自己不会编写代码,但至少做到实现过程、步骤。
通过实验进一步理解编译原理这门课程,知道这么可是多么难学,知道和理解了该理论在计算机中是怎样执行的,对该理论在实践中的应用有深刻的理解。
在这次课程设计中,我们组就是按照实验指导的思想来完成,加强培养实践动手能力和程序开发能力。
五、附录
#include
#include
intcount=0;/*分解的产生式的个数*/
intnumber;/*所有终结符和非终结符的总数*/
charstart;/*开始符号*/
chartermin[50];/*终结符号*/
charnon_ter[50];/*非终结符号*/
charv[50];/*所有符号*/
charleft[50];/*左部*/
charright[50][50];/*右部*/
charfirst[50][50],follow[50][50];/*各产生式右部的FIRST和左部的FOLLOW集合*/
charfirst1[50][50];/*所有单个符号的FIRST集合*/
charselect[50][50];/*各单个产生式的SELECT集合*/
charf[50],F[50];/*记录各符号的FIRST和FOLLOW是否已求过*/
charempty[20];/*记录可直接推出^的符号*/
charTEMP[50];/*求FOLLOW时存放某一符号串的FIRST集合*/
intvalidity=1;/*表示输入文法是否有效*/
intll=1;/*表示输入文法是否为LL
(1)文法*/
intM[20][20];/*分析表*/
charchoose;/*用户输入时使用*/
charempt[20];/*求_emp()时使用*/
charfo[20];/*求FOLLOW集合时使用*/
intin(charc,char*p){
inti;
if(strlen(p)==0)
return(0);
for(i=0;;i++)
{if(p[i]==c)
return
(1);/*若在,返回1*/if(i==strlen(p))
return(0);/*若不在,返回0*/}
}//判断一个字符是否在指定字符串中
charc()
{
charc='A';
while(in(c,non_ter)==1)
c++;
return(c);
}//得到一个不是非终结符的符号
voidrecur(char*point)//分解含有左递归的产生式
{/*完整的产生式在point[]中*/
intj,m=0,n=3,k;
chartemp[20],ch;
ch=c();/*得到一个非终结符*/
k=strlen(non_ter);
non_ter[k]=ch;
non_ter[k+1]='\0';
for(j=0;j<=strlen(point)-1;j++)
{if(point[n]==point[0])
{/*如果‘|’后的首符号和左部相同*/
for(j=n+1;j<=strlen(point)-1;j++)
{while(point[j]!
='|'&&point[j]!
='\0)
temp[m++]=point[j++];
left[count]=ch;
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
m=0;
count++;
if(point[j]=='|')
{n=j+1;
break;}}}
else{/*如果‘|’后的首符号和左部不同*/
left[count]=ch;
right[count][0]='^';
right[count][1]='\0';
count++;
for(j=n;j<=strlen(point)-1;j++)
{if(point[j]!
='|')
temp[m++]=point[j];
else
{left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
//printf("count=%d",count);
m=0;
count++;}}
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
count++;
m=0;}}}
voidnon_re(char*point)//分解不含有左递归的产生式
{intm=0,j;
chartemp[20];
for(j=3;j<=strlen(point)-1;j++)
{if(point[j]!
='|')
temp[m++]=point[j];
else
{left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]='\0';
m=0;
count++;
}}left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]='\0';
count++;
m=0;}
chargrammer(char*t,char*n,char*left,charright[50][50])//读入一个文法
{charvn[50],vt[50];
chars;
charp[50][50];
inti,j,k;
printf("请输入文法的非终结符号串:
");
scanf("%s",vn);
getchar();
i=strlen(vn);
memcpy(n,vn,i);
n[i]='\0';
printf("请输入文法的终结符号串:
");
scanf("%s",vt);
getchar();
i=strlen(vt);
memcpy(t,vt,i);
t[i]='\0';
printf("请输入文法的开始符号:
");
scanf("%c",&s);
getchar();
printf("请输入文法产生式的条数:
");
scanf("%d",&i);
getchar();
for(j=1;j<=i;j++)
{printf("请输入文法的第%d条(共%d条)产生式:
",j,i);
scanf("%s",p[j-1]);
getchar();
}for(j=0;j<=i-1;j++)
if(p[j][1]!
='-'||p[j][2]!
='>')
{printf("\ninputerror!
");
validity=0;
return('\0');
}/*检测输入错误*/
for(k=0;k<=i-1;k++)
{/*分解输入的各产生式*/
if(p[k][3]==p[k][0])
recur(p[k]);
else
non_re(p[k]);}
return(s);
}voidmerge(char*d,char*s,inttype)//将单个符号或符号串并入另一符号串
{/*d是目标符号串,s是源串,type=1,源串中的‘^’一并并入目串;
type=2,源串中的‘^’不并入目串*/
inti,j;
for(i=0;i<=strlen(s)-1;i++)
{if(type==2&&s[i]=='^')
;else
{for(j=0;;j++)
{if(j break;if(j==strlen(d)) {d[j]=s[i]; d[j+1]='\0'; break;}}}}}voidemp(charc)//求所有能直接推出^的符号 {/*即求所有由‘^’推出的符号*/ chartemp[10]; inti; for(i=0;i<=count-1;i++) {if(right[i][0]==c&&strlen(right[i])==1) {temp[0]=left[i]; temp[1]='\0'; merge(empty,temp,1); emp(left[i]);}}} int_emp(charc)//求某一符号能否推出 {/*若能推出,返回1;否则,返回0*/ inti,j,k,result=1,mark=0; chartemp[20]; temp[0]=c; temp[1]='\0'; merge(empt,temp,1); if(in(c,empty)==1) return (1); for(i=0;;i++) {if(i==count) return(0); if(left[i]==c)/*找一个左部为c的产生式*/ {j=strlen(right[i]);/*j为右部的长度*/ if(j==1&&in(right[i][0],empty)==1) return (1); elseif(j==1&&in(right[i][0],termin)==1) return(0); else {for(k=0;k<=j-1;k++) if(in(right[i][k],empt)==1) mark=1; if(mark==1) continue; else{ for(k=0;k<=j-1;k++) {result*=_emp(right[i][k]); temp[0]=right[i][k]; temp[1]='\0'; merge(empt,temp,1);}}} if(result==0&&i continue; elseif(result==1&&i return (1);}} }intjudge()//判断读入的文法是否正确 {inti,j; for(i=0;i<=count-1;i++) {if(in(left[i],non_ter)==0) {/*若左部不在非终结符中,报错*/ printf("\nerror1! "); validity=0; return(0); }for(j=0;j<=strlen(right[i])-1;j++){if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]! ='^') {/*若右部某一符号不在非终结符、终结符中且不为,报错*/printf("\nerror2! ");validity=0;return(0);}}}return (1); }voidfirst2(inti)//求单个符号的FIRST {/*i为符号在所有输入符号中的序号*/ charc,temp[20];intj,k,m;charch='^';c=v[i];emp(ch); if(in(c,termin)==1)/*若为终结符*/{first1[i][0]=c; first1[i][1]='\0'; }elseif(in(c,non_ter)==1)/*若为非终结符*/ {for(j=0;j<=count-1;j++) {if(left[j]==c){if(in(right[j][0],termin)==1||right[j][0]=='^') {temp[0]=right[j][0]; temp[1]='\0'; merge(first1[i],temp,1); }elseif(in(right[j][0],non_ter)==1) {if(right[j][0]==c) continue; for(k=0;;k++) if(v[k]==right[j][0]) break; if(f[k]=='0') {first2(k); f[k]='1';} merge(first1[i],first1[k],2);for(k=0;k<=strlen(right[j])-1;k++) { empt[0]='\0'; if(_emp(right[j][k])==1&&k {for(m=0;;m++) if(v[m]==right[j][k+1]) break; if(f[m]=='0') {first2(m);f[m]='1'; }merge(first1[i],first1[m],2); } elseif(_emp(right[j][k])==1&&k==strlen(right[j])-1) { temp[0]='^'; temp[1]='\0'; merge(first1[i],temp,1); } else break; } } } } } f[i]='1'; }voidFIRST(inti,char*p)//求各产生式右部的FIRST { intlength; intj,k,m; chartemp[20]; length=strlen(p); if(length==1)/*如果右部为单个符号*/ {if(p[0]=='^') {if(i>=0) {first[i][0]='^'; first[i][1]='\0'; }else { TEMP[0]='^'; TEMP[1]='\0'; } } else { for(j=0;;j++) if(v[j]==p[0]) break; if(i>=0) { memcpy(first[i],first1[j],strlen(first1[j])); first[i][strlen(first1[j])]='\0'; } else { memcpy(TEMP,first1[j],strlen(first1[j])); TEMP[strlen(first1[j])]='\0'; } } } else/*如果右部为符号串*/ { for(j=0;;j++) if(v[j]==p[0]) break; if(i>=0) merge(first[i],first1[j],2); else merge(TEMP,first1[j],2); for(k=0;k<=length-1;k++) { empt[0]='\0'; if(_emp(p[k])==1&&k { for(m=0;;m++) if(v[m]==right[i][k+1]) break; if(i>=0) merge(first[i],first1[m],2); else merge(TEMP,first1[m],2); } elseif(_emp(p[k])==1&&k==length-1) { temp[0]='^'; temp[1]='\0'; if(i>=0) merge(first[i],temp,1); else merge(TEMP,temp,1); } elseif(_emp(p[k])==0) break; } } } voidFOLLOW(inti)//求各产生式左部的FOLLOW { intj,k,m,n,result=1; charc,temp[20]; c=non_ter[i];/*c为待求的非终结符*/ temp[0]=c; temp[1]='\0'; merge(fo,temp,1); if(c==start) {/*若为开始符号*/ temp[0]='#'; temp[1]='\0'; merge(follow[i],temp,1); } for(j=0;j<=count-1;j++) { if(in(c,right[j])==1)/*找一个右部含有c的产生式*/ { for(k=0;;k++) if(right[j][k]==c) break;/*k为c在该产生式右部的序号*/ for(m=0;;m++) if(v[m]==left[j]) break;/*m为产生式左部非终结符在所有符号中的序号*/ if(k==strlen(right[j])-1) {/*如果c在产生式右部的最后*/ if(in(v[m],fo)==1) { merge(follow[i],follow[m],1); continue; } if(F[m]=='0') { FOLLOW(m); F[m]='1'; } merge(follow[i],follow[m],1); } else {/*如果c不在产生式右部的最后*/ for(n=k+1;n<=strlen(right[j])-1;n++) { empt[0]='\0'; result*=_emp(right[j][n]); } if(result==1) {/*如果右部c后面的符号串能推出^*/ if(in(v[m],fo)==1) {/*避免循环递归*/ merge(follow[i],follow[m],1); continue; } if(F[m]=='0') { FOLLOW(m); F[m]='1'; } merg
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LL1 文法 判别 教学内容