编译原理SELECT()集合的求法

编译原理习题⼀、填空题: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集合，我们知道了当前状态下输入一个记号该如何选中产生式的候选式。

编译原理实验⼆：LL（1）语法分析器⼀、实验要求 1. 提取左公因⼦或消除左递归（实现了消除左递归） 2. 递归求First集和Follow集 其它的只要按照课本上的步骤顺序写下来就好（但是代码量超多...），下⾯我贴出实验的⼀些关键代码和算法思想。

⼆、基于预测分析表法的语法分析 2.1 代码结构 2.1.1 Grammar类 功能：主要⽤来处理输⼊的⽂法，包括将⽂法中的终结符和⾮终结符分别存储，检测直接左递归和左公因⼦，消除直接左递归，获得所有⾮终结符的First集，Follow集以及产⽣式的Select集。

#ifndef GRAMMAR_H#define GRAMMAR_H#include <string>#include <cstring>#include <iostream>#include <vector>#include <set>#include <iomanip>#include <algorithm>using namespace std;const int maxn = 110;//产⽣式结构体struct EXP{char left; //左部string right; //右部};class Grammar{public:Grammar(); //构造函数bool isNotTer(char x); //判断是否是终结符int getTer(char x); //获取终结符下标int getNonTer(char x); //获取⾮终结符下标void getFirst(char x); //获取某个⾮终结符的First集void getFollow(char x); //获取某个⾮终结符的Follow集void getSelect(char x); //获取产⽣式的Select集void input(); //输⼊⽂法void scanExp(); //扫描输⼊的产⽣式，检测是否有左递归和左公因⼦void remove(); //消除左递归void solve(); //处理⽂法，获得所有First集，Follow集以及Select集void display(); //打印First集,Follow集,Select集void debug(); //⽤于debug的函数~Grammar(); //析构函数protected:int cnt; //产⽣式数⽬EXP exp[maxn]; //产⽣式集合set<char> First[maxn]; //First集set<char> Follow[maxn]; //Follow集set<char> Select[maxn]; //select集vector<char> ter_copy; //去掉$的终结符vector<char> ter; //终结符vector<char> not_ter; //⾮终结符};#endif 2.1.2 AnalyzTable类 功能：得到预测分析表，判断输⼊的⽂法是否是LL(1)⽂法，⽤预测分析表法判断输⼊的符号串是否符合刚才输⼊的⽂法，并打印出分析过程。

江南大学网络教育第一阶段练习题考试科目:《编译原理》第章至第章（总分100分）__________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一单选题 (共4题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。

)1. 若一个文法是递归的，则它所产生的语言的句子是（）。

（5 分）A. 无穷多个B. 有穷多个C. 可枚举的D. 个数是常量2. 文法G[A]：A→ε A→aB B→Ab B→a是（）。

（5 分）A. 0型文法B. 1型文法C. 2型文法D. 3型文法3. 词法分析器的输入是（）。

（5 分）A. 单词符号串B. 源程序C. 语法单位D. 目标程序4. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（）。

（5 分）A. 句子B. 句型C. 单词D. 产生式二填空题 (共2题，总分值10分 )5. 编译程序的功能可以分解为词法分析、语法分析、_____语义分析_____、中间代码生成、中间代码优化、目标代码生成。

（5 分）6. 微小语言Micro的单词有下面的几种：标识符、_____整常数_____、实常数、保留字、_____符号词______、换行符。

（5 分）三简答题 (共2题，总分值20分 )7.给出与正规式R＝1(0|1)*101等价的NFA。

（10 分）答：8. 写出下面程序经词法分析后的TOKEN表示。

begin var X:real;var J:integer;read(J);J:=J+(J*20);X:=J-1;Write(2*J+X)End（10 分）答：四综合计算题 (共2题，总分值50分 )9. 已知文法G(S) S→a| (T) T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的归约规则和句柄。

（25 分）答：10. 已知文法 G[E] 为：E→T|E+T|E-T T→F|T*F|T/F F→（E）|i①该文法的开始符号（识别符号）是什么？②请给出该文法的终结符号集合 Vt 和非终结符号集合 Vn 。

第五章自顶向下语法分析方法1．对文法G[S]S→a|∧|(T)T→T,S|S(1)给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。

(2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。

(3)经改写后的文法是否是LL(1)的？给出它的预测分析表。

(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。

解：(1) (a,(a,a))的最左推导为S→(T)→(T,S)→(S,S)→(a,(T))→(a,(T,S))→(a,(S,a))→(a,(a,a))(((a,a),∧,(a)),a)的最左推导为S→(T)→(T,S)→(S,a)→((T),a)→((T,S),a)→((T,S,S),a)→((S,∧,(T)),a)→(((T),∧,(S)),a) →(((T,S),∧,(a)),a)→(((S,a),∧,(a)),a)→(((a,a),∧,(a)),a)(2)由于有T→T,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/[S]:S→a|∧|(T)T→SUU→，SU|ε分析子程序的构造方法对满足条件的文法按如下方法构造相应的语法分析子程序。

(1) 对于每个非终结号U，编写一个相应的子程序P(U)；(2) 对于规则U::=x1|x2|..|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：IF CH IN FIRST(x1) THEN P(x1)ELSE IF CH IN FIRST(x2) THEN P(x2)ELSE ......IF CH IN FIRST(xn) THEN P(xn)ELSE ERROR其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序；P(xj)为相应的子程序。

(3) 对于符号串x=y1y2...yn;p(x)的含义为：BEGINP(y1);P(y2);...P(yn);END如果yi是非终结符，则P(yi)代表调用处理yi的子程序；如果yi是终结符，则P(yi)为形如下述语句的一段子程序IF CH=yi THEN READ(CH) ELSE ERROR即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中，否则表明出错。

习题11-1 说明解释程序和编译程序的区别。

答：通常，翻译程序可分为解释程序、汇编程序和编译程序。

所谓解释程序是一种将源程序按动态顺序逐句进行分析解释编译，边解释边执行、不产生目标程序的一种翻译程序。

这种翻译程序结构简单、占用内存较少，易于在执行过程中对源程序进行修改，但工作效率低，只适合一些规模较小的语言，如解释BASIC等。

而编译程序（也称编译器）是源语言为某种高级语言，目标语言为相应于某一计算机的汇编语言或机器语言的一种翻译程序。

这种编译程序将源程序翻译成执行时可完全独立于源程序的经优化的目标语言代码，因而运行效率高。

更为重要的是，它使工作于高级语言环境下的程序设计人员，不必考虑与机器有关的繁琐细节，却能完成机器语言所能完成的绝大多数工作。

在解释方式下，并不生成目标代码，而是直接执行源程序本身。

这是编译方式与解释方式的根本区别。

1-2 简述高级语言程序按编译方式的执行过程。

答：高级语言程序按编译方式的执行过程一般可分为两个阶段：编译阶段和运行阶段。

其中，编译阶段完成由源程序到目标程序的翻译，若目标程序是汇编语言程序，还需再通过汇编程序进一步翻译成机器语言程序。

而运行阶段的任务是在目标计算机上执行编译阶段所得到的目标程序。

但目标程序往往不能由计算机直接执行，一般还应有运行系统进行配合，这个运行系统包括链接程序和由这样一些子程序组成的系统库，如标准函数计算子程序、数组动态存储子程序等。

由链接程序将目标程序和系统库连接在一起，最终形成一个可执行程序，在计算机上直接执行。

1-3 什么是编译系统？答：通常将编译程序、链接程序、系统库、源程序编辑程序等软件组成的系统称为编译系统。

1-4 编译过程通常有哪几个阶段？简述各阶段的主要任务。

答：程序设计语言的编译过程一般可以分为词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成5个阶段。

词法分析是编译过程的第一个阶段。

该阶段的主要任务是从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位——单词，并指出其属性。

一、判断对错：（对√；错；每小问2分共24分）<1>算符优先分析法是一种规范归约分析法。

（）<2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈V N，则称Gs为算符文法。

（√）<3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。

（）<4>若两个正规式所表示的正规集相同，则认为二者是等价的。

（√）<5>LR分析法是一种规范归约分析法。

（√）<6>一个LR(0)项目集I={B →α.bβ, P →aA.},则说I中含有“移进—归约”冲突。

（√）<7>SLR(1)文法是无二义性文法。

（√）<8>消除左递归后的文法一定是LL(1)文法。

（）<9>对任何编译程序而言，代码优化是必不可少的。

（）<10>编译程序与具体的机器无关。

（）<11>在自动机的概念中，终态与非终态是可区别的。

（√）<12>逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（√）1. 一个语言有文法是不惟一的。

（√）2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。

（√）3. 紧跟在条件转移语句后面的语句是基本块的入口语句。

（√）4. 算符优先分析法是一种规范归约分析法。

（）5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。

（√）6. LR(0)文法、SLR(1)文法都是无二义性文法。

（√）7．K、∑分别表示有限状态集和有穷字母表, DFA M的转换函数f 是一个从K ⨯∑到K的单值映射。

（√）8. 对任何编译程序而言，代码优化是必不可少的。

（）9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。

（√）10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。

（）11. 一个LR(0)项目集为：I={A→α.bβ, D→β.},则说I中含有“移进--归约”冲突。

一、填空题（每空2分，共20分）1．编译程序首先要识别出源程序中每个单词,然后再分析每个句子并翻译其意义.2．编译器常用的语法分析方法有自底向上和自顶向下两种。

3．通常把编译过程分为分析前端与综合后端两大阶段。

词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合.4．程序设计语言的发展带来了日渐多变的运行时存储管理方案,主要分为两大类，即静态存储分配方案和动态存储分配方案。

5．对编译程序而言，输入数据是源程序，输出结果是目标程序.1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译.2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。

4．一个LL（1）分析程序需要用到一张分析表和符号栈。

5．后缀式abc-/所代表的表达式是a/（b—c）。

二、单项选择题（每小题2分，共20分）1．词法分析器的输出结果是__C。

A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和自身值D．单词自身值2．正规式M 1 和M 2 等价是指__C_。

A．M1和M2的状态数相等 B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_C____.A．xyx B．（xyx）* C．xnyxn（n≥0）D．x*yx*4．如果文法G是无二义的，则它的任何句子α_A____.A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。

A．源程序B．目标语言C．编译方法D．以上三项都是6．四元式之间的联系是通过__B___实现的。

1、试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。

2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。

3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。

4、已知文法G(S)及相应翻译方案S→aAb {print “1”}S→a {print “2”}A→AS {print “3”}A→c {print “4”}输入acab, 输出是什么？5、已知文法G(S)S→bAaA→(B | aB→A a)写出句子b(aa)b的规范归约过程。

6、已知文法G[S]S→S*aF | aF | *aFF→+aF | +a消除文法左递归。

1、设文法G(S):S→^ | a | (T)T→T,S | S⑴ 消除左递归；⑵ 构造相应的FIRST和FOLLOW集合；⑶ 构造预测分析表2.语句 if E then S(1) 改写文法，使之适合语法制导翻译；(2) 写出改写后产生式的语义动作。

4.设某语言的for语句的形式为for i:＝E(1) to E(2) do S其语义解释为i:＝E(1)LIMIT:＝E(2)again: if i＜＝LIMIT thenBeginS;i:＝i＋1goto againEnd;（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。

7.已知文法G(S)S→a | ^ | (T)T→T,S | S(1) 给出句子(a,(a,a))的最左推导；(2) 给出句型((T,S),a)的短语, 直接短语，句柄。

8.对于 C 语言do S while E语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。

9.已知文法G(S)S→aAcBeA→Ab| bB→d(1)给出句子abbcde的最左推导及画出语法树；(2)给出句型aAbcde的短语、素短语。

10.设文法G(S):S→(T) | aS | aT→T,S | S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。