下载文档原格式
编译原理习题⼀、填空题:1-01.编译程序的⼯作过程⼀般可以划分为词法分析,语法分析,语义分析，之间代码⽣成,代码优化等⼏个基本阶段,同时还会伴有表格处理和出错处理.1-02.若源程序是⽤⾼级语⾔编写的,⽬标程序是机器语⾔程序或汇编程序,则其翻译程序称为编译程序.1-03.编译⽅式与解释⽅式的根本区别在于是否⽣成⽬标代码.1-04.翻译程序是这样⼀种程序,它能够将⽤甲语⾔书写的程序转换成与其等价的⽤⼄语⾔书写的程序. 1-05.对编译程序⽽⾔,输⼊数据是源程序,输出结果是⽬标程序.1-06.如果编译程序⽣成的⽬标程序是机器代码程序,则源程序的执⾏分为两⼤阶段:编译阶段和运⾏阶段.如果编译程序⽣成的⽬标程序是汇编语⾔程序,则源程序的执⾏分为三个阶段:编译阶段,汇编阶段和运⾏阶段.1-07.若源程序是⽤⾼级语⾔编写的，⽬标程序是机器语⾔程序或汇编程序，则其翻译程序称为编译程序。
1-08.⼀个典型的编译程序中，不仅包括词法分析、语法分析、中间代码⽣成、代码优化、⽬标代码⽣成等五个部分，还应包括表格处理和出错处理。
其中，词法分析器⽤于识别单词。
1-09.编译⽅式与解释⽅式的根本区别为是否⽣成⽬标代码。
2-01.所谓最右推导是指：任何⼀步αβ都是对α中最右⾮终结符进⾏替换的。
2-02.⼀个上下⽂⽆关⽂法所含四个组成部分是⼀组终结符号、⼀组⾮终结符号、⼀个开始符号、⼀组产⽣式。
2-03.产⽣式是⽤于定义语法成分的⼀种书写规则。
2-04.设G[S]是给定⽂法，则由⽂法G所定义的语⾔L(G)可描述为：L(G)＝{x│S x,x∈V T*}。
2-05.设G是⼀个给定的⽂法，S是⽂法的开始符号，如果S x（其中x∈V*），则称x是⽂法的⼀个句型。
2-06.设G是⼀个给定的⽂法，S是⽂法的开始符号，如果S x(其中x∈V T*),则称x是⽂法的⼀个句⼦。
3-01.扫描器的任务是从源程序中识别出⼀个个单词符号。
4-01.语法分析最常⽤的两类⽅法是⾃上⽽下和⾃下⽽上分析法。
课程设计报告课程：编译原理课程设计学号：姓名：班级：教师：时间：2015.05.20-2015.07.02计算机学院图4 输入LL(1)文法并测试图7 测试非LL(1)文法附录：程序代码#include<stdlib.h>#include<stdio.h>#include<string.h>/*******************************************/int count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/ char start; /*开始符号*/char termin[50]; /*终结符号*/char non_ter[50]; /*非终结符号*/char v[50]; /*所有符号*/char left[50]; /*左部*/char right[50][50]; /*右部*/char first[50][50],follow[50][50]; /*各产生式右部的FIRST和左部的FOLLOW集合*/ char first1[50][50]; /*所有单个符号的FIRST集合*/char select[50][50]; /*各单个产生式的SELECT集合*/char f[50],F[50]; /*记录各符号的FIRST和FOLLOW是否已求过*/char empty[20]; /*记录可直接推出^的符号*/char TEMP[50]; /*求FOLLOW时存放某一符号串的FIRST集合*/ int validity=1; /*表示输入文法是否有效*/int ll=1; /*表示输入文法是否为LL(1)文法*/int M[20][20]; /*分析表*/char choose; /*用户输入时使用*/char empt[20]; /*求_emp()时使用*/char fo[20]; /*求FOLLOW集合时使用*//*******************************************判断一个字符是否在指定字符串中********************************************/int in(char c,char *p){int i;if(strlen(p)==0) return(0);for(i=0;;i++){if(p[i]==c) return(1); /*若在，返回1*/if(i==strlen(p)) return(0); /*若不在，返回0*/}}/*******************************************得到一个不是非终结符的符号********************************************/char c(){char c='A';while(in(c,non_ter)==1) c++;return(c);}/*******************************************分解含有左递归的产生式********************************************/void recur(char *point){ /*完整的产生式在point[]中*/int j,k,m=0,n=3;char ch,temp[20];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);/*从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;}}}/******************************************* 分解不含有左递归的产生式********************************************/ void non_re(char *point){int m=0,j;char temp[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;}/******************************************* 读入一个文法********************************************/char grammer(char *t,char *n,char *left,char right[50][50]){char vn[50],vt[50];char s;char p[50][50];int i,j,k;printf("请输入文法的非终结符号串：");scanf("%s",vn);//getchar(); /*取出缓冲区剩余的回车键，不要也可*/ i=strlen(vn);memcpy(n,vn,i);n[i]='\0';printf("\n请输入文法的终结符号串：");scanf("%s",vt);getchar();i=strlen(vt);memcpy(t,vt,i);t[i]='\0';printf("\n请输入文法的开始符号：");scanf("%c",&s);//getchar();printf("\n请输入文法产生式的条数：");scanf("%d",&i);//getchar();for(j=1;j<=i;j++){printf("\n请输入文法的第%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("\nInput error!\n");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);}/*******************************************将单个符号或符号串并入另一符号串********************************************/void merge(char *d,char *s,int type){/*d是目标串s是源串，type＝1，源串中的'^'并入目串；type＝2，源串中的'^'不并入目串*/ int i,j;for(i=0;i<=strlen(s)-1;i++){if(type==2&&s[i]=='^');else{for(j=0;;j++){if(j<strlen(d)&&s[i]==d[j]) break;if(j==strlen(d)){d[j]=s[i];d[j+1]='\0';break;}}}}}/*******************************************求所有能直接推出‘^’的符号********************************************/void emp(char c){ /*即求所有由'^'推出的符号*/char temp[10];int i;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(char c){ /*若能推出，返回1；否则，返回0*/ int i,j,k,result=1,mark=0;char temp[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);else if(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<count) continue;else if(result==1&&i<count) return(1);}}}/*******************************************判断读入的文法是否正确********************************************/int judge(){int i,j;for(i=0;i<=count-1;i++){if(in(left[i],non_ter)==0){ /*若左部不在非终结符中，报错*/printf("\nLeft error!");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("\nRight error!");validity=0;return(0);}}}return(1);}/*******************************************求单个符号的FIRST集********************************************/void first2(int i){ /*i为符号在所有输入符号中的序号*/char c,ch='^',temp[20];int j,k,m;c=v[i];emp(ch);if(in(c,termin)==1) /*若为终结符*/{first1[i][0]=c;first1[i][1]='\0';}else if(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);}else if(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<strlen(right[j])-1){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);}else if(_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';}/*******************************************求各产生式右部的FIRST集********************************************/ void FIRST(int i,char *p){int length;int j,k,m;char temp[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<length-1){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);}else if(_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);}else if(_emp(p[k])==0) break;}}}/******************************************* 求各产生式左部的FOLLOW集********************************************/ void FOLLOW(int i){int j,k,m,n,result=1;char c,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';}merge(follow[i],follow[m],1);}for(n=k+1;n<=strlen(right[j])-1;n++) temp[n-k-1]=right[j][n];temp[strlen(right[j])-k-1]='\0';FIRST(-1,temp);merge(follow[i],TEMP,2);}}}F[i]='1';}/*******************************************判断读入文法是否为一个LL(1)文法********************************************/int ll1(){int i,j,length,result=1;char temp[50];for(j=0;j<=49;j++){ /*初始化*/ first[j][0]='\0';follow[j][0]='\0';first1[j][0]='\0';select[j][0]='\0';TEMP[j]='\0';temp[j]='\0';f[j]='0';F[j]='0';}for(j=0;j<=strlen(v)-1;j++) first2(j); /*求单个符号的FIRST集合*/ printf("\nfirst1:");for(j=0;j<=strlen(v)-1;j++) printf("%c:%s ",v[j],first1[j]);printf("\nempty:%s",empty);printf("\n_emp:");for(j=0;j<=strlen(v)-1;j++) printf("%d ",_emp(v[j]));for(i=0;i<=count-1;i++) FIRST(i,right[i]); /*求FIRST集*/for(j=0;j<=strlen(non_ter)-1;j++){ /*求FOLLOW集*/ if(fo[j]==0){fo[0]='\0';FOLLOW(j);}}printf("\nfirst:");for(i=0;i<=count-1;i++) printf("%s ",first[i]);printf("\nfollow:");for(i=0;i<=strlen(non_ter)-1;i++) printf("%s ",follow[i]);for(i=0;i<=count-1;i++){ /*求每一产生式的SELECT集合*/ memcpy(select[i],first[i],strlen(first[i]));select[i][strlen(first[i])]='\0';for(j=0;j<=strlen(right[i])-1;j++)result*=_emp(right[i][j]);if(strlen(right[i])==1&&right[i][0]=='^')result=1;if(result==1){for(j=0;;j++)if(v[j]==left[i]) break;merge(select[i],follow[j],1);}}printf("\nselect:");for(i=0;i<=count-1;i++)printf("%s ",select[i]);memcpy(temp,select[0],strlen(select[0]));temp[strlen(select[0])]='\0';for(i=1;i<=count-1;i++){ /*判断输入文法是否为LL(1)文法*/ length=strlen(temp);if(left[i]==left[i-1]){merge(temp,select[i],1);if(strlen(temp)<length+strlen(select[i])) return(0);}else{temp[0]='\0';memcpy(temp,select[i],strlen(select[i]));temp[strlen(select[i])]='\0';}}return(1);}/*******************************************构造分析表M********************************************/void MM(){int i,j,k,m;for(i=0;i<=19;i++)for(j=0;j<=19;j++) M[i][j]=-1;i=strlen(termin);termin[i]='#'; /*将#加入终结符数组*/termin[i+1]='\0';for(i=0;i<=count-1;i++){for(m=0;;m++)if(non_ter[m]==left[i]) break; /*m为产生式左部非终结符的序号*/ for(j=0;j<=strlen(select[i])-1;j++){if(in(select[i][j],termin)==1){for(k=0;;k++)if(termin[k]==select[i][j]) break; /*k为产生式右部终结符的序号*/ M[m][k]=i;}}}}/*******************************************总控算法********************************************/void syntax(){int i,j,k,m,n,p,q;char ch,S[50],str[50];printf("\n请输入该文法的句型：");scanf("%s",str);getchar();i=strlen(str);str[i]='#';str[i+1]='\0';S[0]='#';S[1]=start;S[2]='\0';j=0;ch=str[j];while(1){if(in(S[strlen(S)-1],termin)==1){if(S[strlen(S)-1]!=ch){printf("\n该符号串不是文法的句型！");return;}else if(S[strlen(S)-1]=='#'){printf("\n该符号串是文法的句型.");return;}else{S[strlen(S)-1]='\0';j++;ch=str[j];}}else{for(i=0;;i++)if(non_ter[i]==S[strlen(S)-1]) break;for(k=0;;k++){if(termin[k]==ch) break;if(k==strlen(termin)){printf("\n词法错误！");return;}}if(M[i][k]==-1){printf("\n语法错误！");return;}else{m=M[i][k];if(right[m][0]=='^') S[strlen(S)-1]='\0';else{p=strlen(S)-1;q=p;for(n=strlen(right[m])-1;n>=0;n--) S[p++]=right[m][n];S[q+strlen(right[m])]='\0';}}}printf("S:%s str:",S);for(p=j;p<=strlen(str)-1;p++) printf("%c",str[p]);printf(" \n");}}/*******************************************一个用户调用函数********************************************/void menu(){syntax();printf("\n是否继续？(y or n):");scanf("%c",&choose);getchar();while(choose=='y') menu();}/*******************************************主函数********************************************/void main(){int i,j;start=grammer(termin,non_ter,left,right); /*读入一个文法*/printf("count=%d",count);printf("\nstart:%c",start);strcpy(v,non_ter);strcat(v,termin);printf("\nv:%s",v);printf("\nnon_ter:%s",non_ter);printf("\ntermin:%s",termin);printf("\nright:");for(i=0;i<=count-1;i++) printf("%s ",right[i]);printf("\nleft:");for(i=0;i<=count-1;i++) printf("%c ",left[i]);if(validity==1) validity=judge();printf("\nvalidity=%d",validity);if(validity==1){ll=ll1();printf("\nll=%d",ll);if(ll==0) printf("\n该文法不是一个LL(1)文法！");else{MM();printf("\n");for(i=0;i<=19;i++)for(j=0;j<=19;j++)if(M[i][j]>=0)printf("M[%d][%d]=%d ",i,j,M[i][j]);menu();}}}。
编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。
但要求至少要按照作业题的范围复习。
)一选择题1．编译的各阶段工作都涉及。
[A]词法分析[B]表格管理 [C]语法分析 [D]语义分析2．型文法也称为正规文法。
[A] 0 [B] 1 [C] 2 [D] 33．文法不是LL(1)的。
[A]递归 [B]右递归 [C]2型 [D]含有公共左因子的4．文法E→E+E|E*E|i的句子i*i+i*i有棵不同的语法树。
[A] 1 [B] 3 [C] 5 [D] 75．文法 S→aaS|abc 定义的语言是。
[A]{a2k bc|k>0} [B]{a k bc|k>0}[C]{a2k-1bc|k>0} [D]{a k a k bc|k>0}6．若B为非终结符，则 A→α.Bβ为。
[A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目7．同心集合并可能会产生新的冲突。
[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约8．代码优化时所依据的是。
[A]语法规则 [B]词法规则[C]等价变换规则 [D]语义规则9．表达式a-(-b)*c的逆波兰表示（@为单目减）为。
[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-*10．过程的DISPLAY表是用于存取过程的。
[A]非局部变量[B]嵌套层次 [C]返回地址 [D]入口地址二填空题1．词法分析阶段的任务式从左到右扫描字符流，从而逐个识别一个个的单词。
2．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是。
3．最右推导的逆过程称为规范归约，也称为最左归约。
4．符号表的每一项是由名字栏和两个栏目组成。
在目标代码生成阶段，符号表是的依据。
三判断题（认为正确的填“T”，错的填“F”）【】1．同心集的合并有可能产生“归约/归约”冲突。
select函数详细⽤法解析1．表头⽂件#include#include#include2．函数原型int select(int n,fd_set * readfds,fd_set * writefds,fd_set * exceptfds,struct timeval * timeout);3．函数说明select()⽤来等待⽂件描述词状态的改变。
参数n代表最⼤的⽂件描述词加1，参数readfds、writefds和exceptfds 称为描述词组，是⽤来回传该描述词的读，写或例外的状况。
底下的宏提供了处理这三种描述词组的⽅式:FD_CLR(inr fd,fd_set* set)；⽤来清除描述词组set中相关fd的位FD_ISSET(int fd,fd_set *set)；⽤来测试描述词组set中相关fd的位是否为真FD_SET（int fd,fd_set*set）；⽤来设置描述词组set中相关fd的位FD_ZERO（fd_set *set）；⽤来清除描述词组set的全部位4．结构体说明先说明两个结构体：1) struct fd_set可以理解为⼀个集合，这个集合中存放的是⽂件描述符(filedescriptor)，即⽂件句柄，这可以是我们所说的普通意义的⽂件，当然Unix下任何设备、管道、FIFO等都是⽂件形式，全部包括在内，所以毫⽆疑问⼀个socket就是⼀个⽂件，socket句柄就是⼀个⽂件描述符。
fd_set集合可以通过⼀些宏由⼈为来操作，⽐如清空集合FD_ZERO(fd_set *)；将⼀个给定的⽂件描述符加⼊集合之中FD_SET(int ,fd_set*)；将⼀个给定的⽂件描述符从集合中删除FD_CLR(int,fd_set*)；检查集合中指定的⽂件描述符是否可以读写FD_ISSET(int ,fd_set* )。
⼀会⼉举例说明。
2) struct timeval是⼀个⼤家常⽤的结构，⽤来代表时间值，有两个成员，⼀个是秒数，另⼀个是毫秒数。
编译原理-期末复习编译原理⼀、单选题1、将编译程序分为若⼲个“遍”是为了（）。
BA.提⾼程序的执⾏效率B.使程序的结构更加清晰C.利⽤有限的机器内存并提⾼机器的执⾏效率D.利⽤有限的机器内存但降低了机器的执⾏效率2、构造编译程序应掌握（）。
DA.源程序B.⽬标语⾔C.编译⽅法D.以上三项都是3、变量应当（）。
CA.持有左值B.持有右值C.既持有左值⼜持有右值D.既不持有左值也不持有右值4、编译程序绝⼤多数时间花在（）上。
DA.出错处理B.词法分析C.⽬标代码⽣成D.管理表格5、（）不可能是⽬标代码。
DA.汇编指令代码B.可重定位指令代码C.绝对指令代码D.中间代码6、编译程序是对（）。
DA.汇编程序的翻译B.⾼级语⾔程序的解释执⾏C.机器语⾔的执⾏D.⾼级语⾔的翻译7、正规式M1和M2等价是指（）。
CA.M1和M2的状态数相等B.M1和M2的有象弧条数相等C.M1和M2所识别的语⾔集相等D.M1和M2状态数和有象弧条数相等8、如果⽂法G是⽆⼆义的，则它的任何句⼦（）。
AA.最左推导和最右推导对应的语法树必定相同。
B.最左推导和最右推导对应的语法树可能相同。
C.最左推导和最右推导必定相同。
D.可能存在两个不同的最左推导，但它们对应的语法树相同。
9、⽂法G：S→S+T|TT→T*P|PP→(S)|i句型P+T+i的短语有（）BA.i，P+TB. P，P+T，i，P+T +iB.P+T + i D. P，P+T，i10、产⽣正规语⾔的⽂法为（）。
DA.0型B.1型C.2型D.3型11、⽂法G：S→b|?|(T)T→T?S|S则FIRSTVT(T)=() CA.{b，?，(}B.{b，?，)}C.{b，?，(，?}D.{b，?，)，?}12、给定⽂法：A→bA | cc，下⾯的符号串中，为该⽂法句⼦的是（）。
A①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc可选项有：A.①B.①③④⑤C.①④D.①④⑤13、采⽤⾃上⽽下分析，必须（）。
一、实验目的及要求1．把握LL(1)分析法的大体原理；2．把握LL(1)分析表的构造方式；3．用LL（1）分析法分析高级语言表达式。
4、了解LL（1）分析器的工作进程。
文法：无二义性的算术表达式的文法（1）把词法分析作为语法分析的子程序实现（5分）（2）独立的语法分析程序（4分）（3）对表达式文法排除左递归、构造LL（1）分析表（4）LL（1）分析表能够直接输入（4分），也能够用程序实现（5分）（5）给一个表达式，给出分析进程（分析栈、输入串、所用规那么）（4分）（6）生成一个棵语法树（5分）用二叉树的形式表示出来二、实验内容及原理一、实验原理（1）、LL（1）文法的概念LL(1)分析法属于确信的自顶向下分析方式。
LL(1)的含义是：第一个L说明自顶向下分析是从左向右扫描输入串，第2个L说明分析进程中将利用最左推导，1说明只需向右看一个符号即可决定如何推导，即选择哪个产生式(规那么)进行推导。
LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判定是不是为LL(1)文法,最后再进行句子分析。
需要预测分析器对所给句型进行识别。
即在LL(1)分析法中，每当在符号栈的栈顶显现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当显现终结符时，判定其与剩余输入串的第一个字符是不是匹配，若是匹配，那么继续分析，不然报错。
LL(1)分析方式要求文法知足如下条件：关于任一非终极符A的两个不同产生式A→α,A→β，都要知足下面条件：SELECT(A→α)∩SELECT(A→β)=∅（2）、预测分析表构造LL(1)分析表的作用是对当前非终极符和输入符号确信应该选择用哪个产生式进行推导。
它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。
假设用M表示LL(1)分析表，那么M可表示如下：M: VN×VT→P∪{Error}M(A, t) = A→α，当t∈select(A→α) ，不然M(A, t) = Error其中P表示所有产生式的集合。
TINY语言语法分析一、两个预测语法分析需要的知识.1.上下文无关文法及其处理上下文无关文法是描述语法的工具，如<<编译原理与实践>>中提供了TINY文法，用大写字符表示非终结符，小写字符和符号表示终结符($ 表示空)，$ 表示空集，# 表示记号结束。
BNF of the TINY**************************************************************************PROGRAM-> STMT-SEQUENCESTMT-SEQUENCE-> STMT-SEQUENCE ; STATEMENT | STATEMENT STATEMENT-> IF-STMT | REPEAT-STMT | ASSIGN-STMT| READ-STMT | WRITE-STMTIF-STMT-> if EXP then STMT-SEQUENCE end| if EXP then STMT-SEQUENCE else STMT-SEQUENCE end REPEAT-STMT-> repeat STMT-SEQUENCE until EXPASSIGN-STMT-> identifier := EXPREAD-STMT-> read identifierWRITE-STMT-> write EXPEXP-> SIMPLE-EXP COMPARISON-OP SIMPLE-EXP | SIMPLE-EXP COMPARISON-OP-> < | =SIMPLE-EXP-> SIMPLE-EXP ADDOP TERM | TERMADDOP-> + | -TERM-> TERM MULOP FACTOR | FACTORMULOP-> * | /FACTOR-> ( EXP ) | number | identifier2.对文法进行处理文法中存在二义性, 左递归和公因子对于二义性不同的文法视具体情况而论.消除左递归(龙书中的例子):A-> Aa | b消除后的产生式A-> b A’A’-> aA’ | $消除左递归的方法是:A-> Aa1 | Aa2 | … | Aa m | b 1 | b 2| … | b n(其中 b i 都不已 A 开头)使用一下产生式替换A-> b 1A’| b 2A’ | … | b n A’A’-> a1A’ | a2A’| … | a m A’ | $看上面的BNF 其中有几条产生式是属于左递归的例子:STMT-SEQUENCE-> STMT-SEQUENCE ; STATEMENT | STATEMENT SIMPLE-EXP-> SIMPLE-EXP ADDOP TERM | TERMTERM-> TERM MULOP FACTOR | FACTOR按照消除左递归的方法变换成下面的产生式STMT-SEQUENCE-> STATEMENT STMT-SEQUENCE’STMT-SEQUENCE’-> ; STATEMENT STMT-SEQUENCE’ | $SIMPLE-EXP-> TERM SIMPLE-EXP’SIMPLE-EXP’-> ADDOP TERM SIMPLE-EXP’ | $TERM-> FACTOR TERM’TERM’-> MULOP FACTOR TERM’ | $提取公因子(龙书中的例子):A-> a b 1| a b 2提取公因子后:A-> aA’A’-> b 1| b 2提取公因子的方法是:A-> a b 1 | a b 2 | … | a b n | c (c 是不以 a 开头的候选式)提取后:A-> aA’ | cA’-> b 1 | b 2| … | b n上面的BNF 中有几条公因子的例子:IF-STMT-> if EXP then STMT-SEQUENCE end| if EXP then STMT-SEQUENCE else STMT-SEQUENCE end EXP-> SIMPLE-EXP COMPARISON-OP SIMPLE-EXP | SIMPLE-EXP提取公因子后:IF-STMT-> if EXP then STMT-SEQUENCE ELSE-STMT endELSE-STMT-> else STMT-SEQUENCE | $EXP-> SIMPLE-EXP EXP’EXP’-> COMPARISON-OP SIMPLE-EXP | $所以处理后的BNF文法为BNF of the TINY**************************************************************************PROGRAM-> STMT-SEQUENCESTMT-SEQUENCE-> STATEMENT STMT-SEQUENCE'STMT-SEQUENCE'-> ; STATEMENT STMT-SEQUENCE' | $STATEMENT-> IF-STMT | REPEAT-STMT | ASSIGN-STMT |READ-STMT | WRITE-STMTIF-STMT-> if EXP then STMT-SEQUENCE ELSE-STMT endELSE-STMT-> else STMT-SEQUENCE | $REPEAT-STMT-> repeat STMT-SEQUENCE until EXPASSIGN-STMT-> identifier := EXPREAD-STMT-> read identifierWRITE-STMT-> write EXPEXP-> SIMPLE-EXP EXP'EXP'-> COMPARISON-OP SIMPLE-EXP | $COMPARISON-OP-> < | =SIMPLE-EXP-> TERM SIMPLE-EXP'SIMPLE-EXP'-> ADDOP TERM SIMPLE-EXP' | $ADDOP-> + | -TERM-> FACTOR TERM'TERM'-> MULOP FACTOR TERM' | $MULOP-> * | /FACTOR-> ( EXP ) | number | identifier3.first集合和follow集合进行语法分析时, 非终结符的产生式会包含很多候选式, 当遇到一个记号, 用哪个候选式来扩展就成了问题. 当我们知道了候选式对应的第一个终结符时就可以确定了.first集合就是文法产生式中所有的候选式的第一个终结符的集合.(参考<<现代编译程序设计>>)使用如下方法来就文法的first集合(参考龙书):(1). 如果X是终结符, first(X) = {X}(2). 如果X-> $ 是产生式, 则将{$} 加入first(X)(3). 如果X是非终结符, 且X-> Y1Y2…Y k是产生式, 则:1). 若对于某个i, 有a 属于first(Y i), 且$属于first(Y1)…first(Y i-1), 则a属于first(X)2). 若对于j = 1, 2, …, k 有 $ 属于first(Y j) 则$ 属于first(X)龙书上的例子:E-> TE’E’-> +TE’ | $T-> FT’T’-> *FT’ | $F-> (E) | id对于first(E), E是非终结符, 根据(3)的1) 当i = 1时. T前面没有符号了所以first(T)属于first(E), 同理first(F) 属于first(T). 又根据(1), first(F) = {(, id}, $ 不属于first(F), 所以first(F) = first(T) = first(E) = {(, id}.根据(1),(2), 的first(E’) = {+, $}, first(T’) = {*, $}根据求first集合的规则和TINY的BNF求出TINY的first集合为:first(PROGRAM) = first(STMT-SEQUENC) = first(STATEMENT) ={if, repeat, identifier, read, write}first(STMT-SEQUENCE') = {;, $}first(IF-STMT) = {if}first(ELSE-STMT) = {else, $}first(REPEAT-STMT) = {repeat}first(ASSIGN-STMT) = {identifier}first(READ-STMT) = {read}first(WRITE-STMT) = {write}first(EXP) = first(SIMPLE-EXP) = first(TERM) = first(FACTOR) ={(, number, identifier}first(EXP') = {<, =, $}first(COMPARISON-OP) = {<, =}first(SIMPLE-EXP') = {+, -, $}first(ADDOP) = {+, -}first(TERM') = {*, /, $}first(MULOP) = {*, /}follow集合是指产生式A的后继的终结符集合, 也就是紧跟在A后面的终结符集合. follow 集合的求法(参考龙书):(1). 如果S是开始符号, 则$属于follow(S), $是记号串的结束符号.(2). 如果存在产生式A-> aBb 则将first(b)中除了$ 以外的符号加入到follow(B)中.(3). 如果存在产生式A-> aB, 或A-> aBb且$ 属于first(b),则将follow(A)加入到follow(B)中.龙书中的例子:E-> TE’E’-> +TE’ | $T-> FT’T’-> *FT’ | $F-> (E) | id对于follow(E), 根据(1), follow(E) = {#}, 在产生式右部包含E的产生式F-> (E) | id 其中根据(2)是的{)}加入到follow(E)中, 所以follow(E) = {), #}.对于follow(E’), 观察所有右部包含E’的产生式: E-> TE’和E’-> +TE’ | $ 在每一个产生式中E’都处在右部最右端所以根据(3), 右follow(E)属于follow(E’) 所以follow(E’) = follow(E).对于follow(T), 观察所有右部包含T的产生式E-> TE’和E’-> +TE’ | $ 根据(2)first(E’)中处理$ 以外的符号都属于follow(T), 所以follow(T) = {+}, 又$ 属于first(E’) 根据(3)有follow(E) 和follow(E’) 都属于follow(T), 但是follow(E) = follow(E’)不用重复加入. 所以follow(T) = {+, ), #}同上follow(T’) = follow(T)同上follow(F) = {*, +, ), #}根据求follow集合的规则和TINY的BNFfollow(PROGRAM) = {#}follow(STMT-SEQUENCE) = {#, else, end, until}follow(STMT-SEQUENCE') = {#, else, end, until}follow(STATEMENT) = follow(IF-STMT) = follow(REPEAT-STMT) =follow(ASSIGN-STMT) = follow(READ-STMT) = follow(WRITE-STMT) ={;, #, else, end, until}follow(ELSE-STMT) = {end}follow(EXP) = {then, ), ;, #, else, end, until}follow(EXP') = follow(EXP)follow(COMPARISON-OP) = {(, number, identifier}follow(SIMPLE-EXP) = {<, =, then, ), ;, #, else, end, until}follow(SIMPLE-EXP') = follow(SIMPLE-EXP)follow(TERM) = {+, -, <, =, then, ), ;, #, else, end, until}follow(ADDOP) = {(, number, identifier}follow(TERM') = follow(TERM)follow(MULOP) = {(, number, identifier}follow(FACTOR) = {*, /, +, -, <, =, then, ), ;, #, else, end, until}4.select集合select集合是制导通过某一个记号和非终结符来选择适当的产生式候选式的集合, 是十分重要的集合.select集合的求法很简单, 主要用到了前面求的first集合和follow集合求select(A-> a)(1)如$ 不属于first(A)则select(A-> a) = first(A)(2)如$ 属于first(A) 则select(A-> a) = first(A) U follow(A)根据select集合的规则和TINY的BNFselect(PROGRAM-> STMT-SEQUENCE) = {if, repeat, identifier, read, write}select(STMT-SEQUENCE-> STATEMENT STMT-SEQUENCE') ={if, repeat, identifier, read, write}select(STMT-SEQUENCE'-> ; STATEMENT STMT-SEQUENCE') = {;}select(STMT-SEQUENCE'-> $) = {#, else, end, until}select(STATEMENT-> IF-STMT) = {if}select(STATEMENT-> REPEAT-STMT) = {repeat}select(STATEMENT-> ASSIGN-STMT) = {identifier}select(STATEMENT-> READ-STMT) = {read}select(STATEMENT-> WRITE-STMT) = {write}select(IF-STMT-> if EXP then STMT-SEQUENCE ELSE-STMT end) = {if}select(ELSE-STMT-> else STMT-SEQUENCE) = {else}select(ELSE-STMT-> $) = {end}select(REPEAT-STMT-> repeat STMT-SEQUENCE until EXP) = {repeat}select(ASSIGN-STMT-> identifier := EXP) = {identifier}select(READ-STMT-> read identifier) = {read}select(WRITE-STMT-> write EXP) = {write}select(EXP-> SIMPLE-EXP EXP') = {(, number, identifier}select(EXP'-> COMPARISON-OP SIMPLE-EXP) = {<, =}select(EXP'-> $) = {then, ), ;, #, else, end, until}select(COMPARISON-OP-> <) = {<}select(COMPARISON-OP-> =) = {=}select(SIMPLE-EXP-> TERM SIMPLE-EXP') = {(, number, identifier}select(SIMPLE-EXP'-> ADDOP TERM SIMPLE-EXP') = {+, -}select(SIMPLE-EXP'-> $) = {<, =, then, ), ;, #, else, end, until}select(ADDOP-> +) = {+}select(ADDOP-> -) = {-}select(TERM-> FACTOR TERM') = {(, number, identifier}select(TERM'-> MULOP FACTOR TERM') = {*, /}select(TERM'-> $) = {+, -, <, =, then, ), ;, #, else, end, until}select(MULOP-> *) = {*}select(MULOP-> /) = {/}select(FACTOR-> (EXP)) = {(}select(FACTOR-> number) = {number}select(FACTOR-> identifier) = {identifier}二、递归预测语法分析1. 分析程序“预测”并不准确, 因为通过上面的select集合，我们知道了当前状态下输入一个记号该如何选中产生式的候选式。
