实验三中间的代码优化
某些编译程序在中间代码或目标代码生产之后要对其进行优化，所谓优化就是对代码进行等价的变换。而变换后的代码运行结果与变换前的代码运行结果相同。而运行速度加快或占用内存空间减少。中间的代码优化就是对中间代码进行等价的变换。
基本块的有向图DAG（Directed Acyclic Graph)
有向图中任何一条通路都不是环路，则称该有向图为无环路有向图，简称为DAG。
一、实验题目：
中间代码的局部优化
二、实验目的：
掌握局部优化方法、提高机器的运行速度
三、实验内容：
1 、构造基本块内的优化DAG
假设：（1）ni 为已知结点号，n为新结点号；
（2）访问各结点信息时，按结点号逆序排序
2、完成对下例三类表达式的优化
（1）常值表达式的优化
（2）公共表达式的优化
（3）无用赋值的优化
3、输出根据优化的DAG重组四元式
四、设计概要：
首先要实现表达式中间代码生成，采用递归下降子程序法实现。
E→T{ω0 “push(SYN,w)”T“QUAT” }
T→F{ω1”push(SYN,w)”F“QUAT”}
F→i“push(SEM,entry(w))”|(E)
其中：·push(SYN,w)---当前单词w入符号栈SYN；
·push(SEM,entry(w))--- 当前i在符号表中的入口值压入语义栈SEM；·QUAT---生成四元式函数
①T:=newtemp;
②QT[j]=(SYN[k],SEM[s-1],SEM[s],T);j++;
③ pop(SYN,_);pop(SEM,_);pop(SEM,_); push(SEM,T);
在对中间代码进行局部优化
五、程序代码及运行结果：
1.表达式中间代码生成
#include
#include
using namespace std;
char str[50];
char sem[50];
char syn[50];
char ch;
int i=0;
int j=0;
int n=0;
int p=1;
void push_sem(char w)
{
sem[j++]=w;
}
void push_syn(char w)
{
syn[n++]=w;
}
void Gen()
{
char s[2][2];
char w;
w=sem[--j];
if(w>='1'&&w<='9')
{
s[0][1]=w;
s[0][0]=sem[--j];
}
else
{
s[0][0]=w;
s[0][1]=' ';
}
w=sem[--j];
if(w>='1'&&w<='9')
{
s[1][1]=w;
s[1][0]=sem[--j];
}
else
{
s[1][0]=w;
s[1][1]=' ';
}
cout<<"("< push_sem('t'); push_sem(p+47); } int F() { int m; int E(); if(ch=='(') { ch=str[i++]; m=E(); if(ch==')') ch=str[i++]; else { //cout<<"表达式error!"< return 0; } } else { if((ch>='a'&&ch<='z')||(ch>='1'&&ch<='9')) { push_sem(ch); ch=str[i++]; } else { //cout<<"表达式error!"< return 0; } } return 1; } int T() { int k,m,l; k=F(); if(k==0){return 0;} while(1) { //push_syn(ch); if(ch=='*') { push_syn(ch); ch=str[i++]; m=F(); if(m==0){return 0;} Gen(); } else if(ch=='/') { push_syn(ch); ch=str[i++]; l=F(); if(l==0){return 0;} Gen(); } else break; } return 1; } int E() { int k,m,l; k=T(); if(k==0){return 0;} while(1) { //push_syn(ch); if(ch=='+') { push_syn(ch); ch=str[i++]; m=T(); if(m==0){return 0;} Gen(); } else if(ch=='-') { push_syn(ch); ch=str[i++]; l=T(); if(l==0){return 0;} Gen(); } else break; } return 1; } int main() { int k,q=0; char w1,w2,w; char s[1][2]; cout<<"输入表达式(以'#'结束):"; cin>>str; w1=str[i++]; w2=str[i++]; if(w2!='=') {i=i-2;q=1;} ch=str[i++]; k=E(); if(q==0) { w=sem[--j]; if(w>='1'&&w<='9') { s[0][1]=w; s[0][0]=sem[--j]; } else { s[0][0]=w; s[0][1]=' '; } cout<<"("< } if(k==0) cout<<"error!"< else { if(ch=='#') cout<<"OK!"< else cout<<"error!"< } return 0; } 运行结果： 2.代码优化：（采用递归下降子程序法判断表达式是否合法，方法如上） #include #include #include using namespace std; int i=1; int j=0,n=0; int p; int m=1; int Ti=0; char prog[100]; char ch; char syn[20],sem[50][3]; void SEM(void) { int i,j; for(i=0;i<50;i++) for(j=0;j<3;j++) sem[i][j]='\0'; } struct quat//四元式结构 { char result[8]; char ag1[8]; char op; char ag2[8]; }quad[25],newquad[15]; struct Ni//节点结构 { int pre[2]; char op; char bz[25][8]; }N[25]; void newN(void) { int l,j; i++; for(j=0;j<25;j++) { for(l=0;l<8;l++) { N[i-1].bz[j][l]='\0'; } } for(j=0;j<2;j++) N[i-1].pre[j]=0; N[i-1].op='\0'; } void dagt(void); void newquat(void); void fuzhi(void); //递归语法分析生成中间代码 void E(void); void T(void); void F(void); void pop0(char sz[]); void push0(char sz[],char x); void pop1(char sz[50][3]); void push1(char sz[50][3],char x[3]); void quat1(void); void quat0(char w); void print1(void); void print2(void); char *newT(void) { char *p; char m[8]; p=(char *)malloc(8); Ti++; itoa(Ti,m,10); strcpy(p+1,m); p[0]='t'; return(p); } void main() { p=0; syn[0]='#'; SEM(); sem[0][0]='#'; cout<<"请输入表达式："< do { cin.get(ch); if(ch != '\n') prog[p++]=ch; }while(ch!='#'); p=0; ch=prog[p++]; while(ch!='#') { fuzhi(); } print1(); dagt(); newquat(); print2(); } void fuzhi(void) { char temp[3]; temp[0]='\0'; temp[1]='\0'; temp[2]='\0'; if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')) { temp[0]=ch; push1(sem,temp); ch=prog[p++]; if(ch=='=') { push0(syn,ch); ch=prog[p++]; E(); if(m==0) { cout<<"错误1!"< system("pause"); ///// return; } if(ch==';') { ch=prog[p++]; quat1(); } else { cout<<"错误2!"< system("pause"); return; } } else { cout<<"错误3!"< system("pause"); return; } } else { cout<<"错误4!"< printf("%d",ch); system("pause"); return; } } //E、T、F是递归下降子程序的语法分析 void E(void) { char w; T(); while(ch=='+'||ch=='-') { push0(syn,ch); w=syn[strlen(syn)-1]; ch=prog[p++]; T(); quat0(w); } } void T(void) { char w; F(); while(ch=='*'||ch=='/') { push0(syn,ch); w=syn[strlen(syn)-1]; ch=prog[p++]; F(); quat0(w); } } void F(void) { char temp[3]; temp[0]='\0'; temp[1]='\0'; temp[2]='\0'; if(ch=='(') { ch=prog[p++]; E(); if(ch==')') { ch=prog[p++]; } else m=0; } else if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')||(ch<='9'&&ch>='0')) { temp[0]=ch; push1(sem,temp); ch=prog[p++]; } else m=0; } void push0(char sz[],char x) { int top; top=strlen(sz); sz[top]=x; top++; sz[top+1]='\0'; } void pop0(char sz[]) { int top; top=strlen(sz)-1; sz[top]='\0'; } void push1(char sz[50][3],char x[3]) { int top=1; while(sz[top][0]) top++; strcpy(sz[top],x); top++; sz[top+1][0]='\0'; } void pop1(char sz[50][3]) { int top=1; while(sz[top][0]) top++; top--; sz[top][0]='\0'; sz[top][1]='\0'; sz[top][2]='\0'; } void quat0(char w) { int top=1,i; char *p; while(sem[top][0]) top++; strcpy(quad[j].ag1,sem[top-2]); strcpy(quad[j].ag2,sem[top-1]); quad[j].op=w; p=newT(); for(i=0;i<8;i++) quad[j].result[i]=p[i]; pop1(sem); top--; pop1(sem); top--; for(i=0;i<3;i++) sem[top][i]=quad[j].result[i]; sem[top][2]='\0'; j++; } void quat1(void) { char ag2[8]; int top,i; top=1; while(sem[top][0]) top++; ag2[0]='_'; for(i=1;i<8;i++) ag2[i]='\0'; strcpy(quad[j].ag1,sem[top-1]); strcpy(quad[j].ag2,ag2); quad[j].op='='; strcpy(quad[j].result,sem[top-2]); pop0(syn); pop1(sem); pop1(sem); j++; } void print1(void) { int i; cout<<"原来的四元组："< for(i=0;i cout<<(i+1)<<"、("< } void dagt(void) { int m,n,top,l,tag=0,tag1=0,tag2=0; char temp; for(m=0;m { tag=0; for(n=i;n>0;n--) for(l=0;l<25;l++) { if(strcmp(quad[m].ag1,N[n-1].bz[l])==0) { tag=n; break; } } if(tag!=0) { tag1=tag-1; if('0' goto N3; else goto N3; } else { if('0' { if(quad[m].ag2[0]!='_') { if('0' { quad[m].ag1[0]=quad[m].ag1[0]-'0'; quad[m].ag2[0]=quad[m].ag2[0]-'0'; switch(quad[m].op) { case '+':temp=quad[m].ag1[0]+quad[m].ag2[0];break; case '-':temp=quad[m].ag1[0]-quad[m].ag2[0];break; case '*':temp=quad[m].ag1[0]*quad[m].ag2[0];break; case '/':temp=quad[m].ag1[0]/quad[m].ag2[0];break; default:break; } tag=0; for(n=i;n>0;n--) for(l=0;l<25;l++) { if(strcmp(quad[m].result,N[n-1].bz[l])==0) { tag=n; break; } } if(tag!=0) continue; else { newN(); N[i-1].bz[0][0]=temp+'0' ; strcpy(N[i-1].bz[1],quad[m].result); continue; } } else { newN(); tag1=i-1; strcpy(N[i-1].bz[0],quad[m].ag1); goto N2; } } else goto N1; } else N1: { newN(); strcpy(N[i-1].bz[0],quad[m].ag1); tag1=i-1; N3: if(quad[m].ag2[0]=='_') { tag=0; for(n=i;n>0;n--) for(l=0;l<25;l++) { if(strcmp(quad[m].result,N[n-1].bz[l])==0) { tag=n; top=l; break; } } if(tag!=0) { for(l=top+1;l<25;l++) { strcpy(N[tag-1].bz[l-1],N[tag-1].bz[l]); } goto N5; } else { N5: if(N[i-1].bz[0][1]) { if(quad[m].result[1]) { top=0; while(N[tag1].bz[top][0]) top++; strcpy(N[tag1].bz[top],quad[m].result); continue; } else { temp=N[i-1].bz[0][1]; strcpy(N[i-1].bz[0],quad[m].result); top=0; while(N[tag1].bz[top][0]) top++; N[i-1].bz[top][0]='t'; N[i-1].bz[top][1]=temp; continue; } } else { top=0; while(N[tag1].bz[top][0]) top++; strcpy(N[tag1].bz[top],quad[m].result); continue; } } } else N2: { tag=0; for(n=i;n>0;n--) for(l=0;l<25;l++) { if(strcmp(quad[m].ag2,N[n-1].bz[l])==0) { tag=n; break; } } if(tag!=0) { tag2=tag-1; tag=0; for(n=i;n>0;n--) if((N[n-1].pre[0]==tag1)&&(N[n-1].pre[1]==tag2)) { tag=n; break; } if(tag!=0) { if(N[tag-1].op==quad[m].op) { if(!N[tag-1].bz[0][1]) { top=1; while(N[tag-1].bz[top][0]) top++; strcpy(N[tag-1].bz[top],quad[m].result); } else if(!quad[m].result[1]) { temp=N[tag-1].bz[0][1]; strcpy(N[tag-1].bz[0],quad[m].result); top=1; while(N[tag-1].bz[top][0]) top++; N[tag].bz[top][0]='t'; N[tag].bz[top][1]=temp; } else { top=1; while(N[tag-1].bz[top][0]) top++; strcpy(N[tag-1].bz[top],quad[m].result); } continue; } else { newN(); N[i-1].op=quad[m].op; strcpy(N[i-1].bz[0],quad[m].result); N[i-1].pre[0]=tag1; N[i-1].pre[1]=tag2; } continue; } else { newN(); N[i-1].op=quad[m].op; strcpy(N[i-1].bz[0],quad[m].result); N[i-1].pre[0]=tag1; N[i-1].pre[1]=tag2; continue; } } else { newN(); strcpy(N[i-1].bz[0],quad[m].ag2); tag2=i-1; tag=0; for(n=i;n>0;n--) for(l=0;l<25;l++) if(strcmp(quad[m].result,N[n-1].bz[l])==0) { tag=n; top=l; break; } if(tag==0) { newN(); strcpy(N[i-1].bz[0],quad[m].result); N[i-1].op=quad[m].op; N[i-1].pre[0]=tag1; N[i-1].pre[1]=tag2; continue; } else { for(l=top+1;l<25;l++) { strcpy(N[tag-1].bz[l-1],N[tag-1].bz[l]); } newN(); strcpy(N[i-1].bz[0],quad[m].result); N[i-1].op=quad[m].op; N[i-1].pre[0]=tag1; N[i-1].pre[1]=tag2; } } } } } } } void newquat(void) { int l,top; for(l=1;l { if(N[l].pre[1]==0&&N[l].pre[0]==0) { if(!N[l].bz[0][1]) { if(('0' continue; else { for(top=1;N[l].bz[top][1];top++) { if(!N[l].bz[top][0]) { strcpy(newquad[n].ag1,N[l].bz[0]); newquad[n].ag2[0]='_'; newquad[n].op='='; strcpy(newquad[n].result,N[l].bz[top]); n++; } } } } else continue; } else if(N[l].pre[1]!=0||N[l].pre[0]!=0) { strcpy(newquad[n].ag1,N[N[l].pre[0]].bz[0]); strcpy(newquad[n].ag2,N[N[l].pre[1]].bz[0]); newquad[n].op=N[l].op; strcpy(newquad[n].result,N[l].bz[0]); n++; if(!N[l].bz[0][1]) { for(top=1;N[l].bz[top][0];top++) { if(!N[l].bz[top][1]) { strcpy(newquad[n].ag1,N[l].bz[0]); newquad[n].ag2[0]='_'; newquad[n].op='='; strcpy(newquad[n].result,N[l].bz[top]); n++; } } } } } } void print2(void) { int i; cout<<"优化后的代码:"< for(i=0;i cout<<(i+1)<<"、("< 编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。 语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V 编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。 实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则 编译原理复习题 一、是非题 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 3．每个文法都能改写为 LL(1) 文法。 (×) 4．算符优先关系表不一定存在对应的优先函数。 (√) 5．LR分析方法是自顶向下语法分析方法。 (×) 6．“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(× ) 7．一个句型的句柄一定是文法某产生式的右部。 (√) 8．仅考虑一个基本块，不能确定一个赋值是否真是无用的。 (√ ) 9．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 (× ) 10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×) 11．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(× ) 12．递归下降分析法是自顶向下分析方法。(√ ) 13．产生式是用于定义词法成分的一种书写规则。 (×) 14．在 SLR(1)分析法的名称中，S的含义是简单的。(√) 15．综合属性是用于“自上而下”传递信息。(× ) 16．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(×) 17．程序语言的语言处理程序是一种应用软件。 (×) 18．解释程序适用于 COBOL 和 FORTRAN 语言。 (×) 19．一个 LL(l)文法一定是无二义的。 (√) 20．正规文法产生的语言都可以用上下文无关文法来描述。 (√) 21．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 (×) 22．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 (√) 22．逆波兰法表示的表达式亦称后缀式。 (√ ) 23．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 (√ ) 24．数组元素的地址计算与数组的存储方式有关。(√) 25．算符优先关系表不一定存在对应的优先函数。 (×) 26．编译程序是对高级语言程序的解释执行。(× ) 27．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 28．一个算符优先文法可能不存在算符优先函数与之对应。 (√ ) 29．语法分析时必须先消除文法中的左递归。 (×) 30．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (√) 31．逆波兰表示法表示表达式时无须使用括号。 (√ ) 32．静态数组的存储空间可以在编译时确定。 (√) 33．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (√) 34．两个正规集相等的必要条件是他们对应的正规式等价。 (√) 35．一个语义子程序描述了一个文法所对应的翻译工作。 (×) 36．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×) 37．确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 38．词法分析作为单独的一遍来处理较好。 (× ) 39．构造LR分析器的任务就是产生LR分析表。 (√) 40．规范归约和规范推导是互逆的两个过程。 (√) 41．同心集的合并有可能产生新的“移进”/“归约”冲突。 (× ) 42．LR分析技术无法适用二义文法。 (× ) [实验任务] 完成以下正则文法所描述的Pascal语言子集单词符号的词法分析程序。 <标识符>→字母︱<标识符>字母︱<标识符>数字 <无符号整数>→数字︱<无符号整数>数字 <单字符分界符> →+ ︱－︱* ︱; ︱(︱) <双字符分界符>→<大于>=︱<小于>=︱<小于>>︱<冒号>=︱<斜竖>* <小于>→< <等于>→= <大于>→> <冒号> →: <斜竖> →/ 该语言的保留字：begin end if then else for do while and or not 说明：1 该语言大小写不敏感。 2 字母为a-z A-Z，数字为0-9。 3可以对上述文法进行扩充和改造。 4 ‘/*……*/’为程序的注释部分。 [设计要求] 1、给出各单词符号的类别编码。 2、词法分析程序应能发现输入串中的错误。 3、词法分析作为单独一遍编写，词法分析结果为二元式序列组成的中间文件。 4、设计两个测试用例（尽可能完备），并给出测试结果。 demo.cpp #include 第十章代码优化 某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。 本章重点：局部优化基本块的DAG表示 第一节优化技术简介 为了说明问题，我们来看下面这个例子，源程序是： P :=0 For I :=1 to 20 do P :=P+A[I]*B[I]; 经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。那么，对于这个中间代码段，可进行如下这些优化。 1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。所以，（6）的运算是多余的。我们可以把（6）变换成：T4 :=T1。这种优化称为删除多余运算或称为删除公共子表达式。 2、代码外提减少循环中代码总数的一个重要办法是代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。经过删除多余运算和代码外提后，代码变成图10-1-2。 第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？ 答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。 第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？ 答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。 答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 （1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答： （1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab 实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表 /*PL/0编译程序（C语言版） *编译和运行环境： *Visual C++6.0 *WinXP/7 *使用方法： *运行后输入PL/0源程序文件名 *回答是否将虚拟机代码写入文件 *回答是否将符号表写入文件 *执行成功会产生四个文件（词法分析结果.txt符号表.txt虚拟代码.txt源程序和地址.txt） */ #include 编译原理上机实验试题 一、实验目的 通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术， 如何针对确定的有限状态自动机进行编程序；熟悉和 掌握程序设计语言的语法分析程序的设计原理、熟悉 和掌握算符优先分析方法。 二、实验要求 本实验要求：①要求能熟练使用程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）； ③要编写出完成相应任务的程序并在计算机上准确 地运行；④实验结束后要写出上机实验报告。 三、实验题目 针对下面文法G(S)： S→v = E E→E+E│E-E│E*E│E/E│（E）│v │i 其中，v为标识符，i为整型或实型数。要求完成 ①使用自动机技术实现一个词法分析程序； ②使用算符优先分析方法实现其语法分析程序，在 语法分析过程中同时完成常量表达式的计算。 1、题目（见“编译原理---实验题目.doc，“实验题目”中的第一项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理： (1)单词分类：标识符，保留字，常数，运算符，分隔符等等 (2)单词类型编码 (3)自动机 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。 1、题目（见“编译原理---实验题目.doc，“实验题目”中的第二项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理：构造出算法优先关系表 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。 Scanner: #include 5. 目标代码生成 本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C 源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIM Simulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。 选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。 需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。 5.1 实验内容 5.1.1 实验要求 为了完成实验四，我们建议你首先下载并安装SPIM Simulator用于对生成的目标代码进行检查和调试，SPIM Simulator的官方下载地址为：https://www.doczj.com/doc/6914594825.html,/~larus/spim.html。这是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍有关SPIM Simulator的使用方法。 你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。因此，以下几个方面不属于检查范围： 1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的 正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。 2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使 用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即MIPS32汇编代码）能运行正确。 《编译原理》习题答案： 第一次： P14 2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？ 答：被翻译的程序称为源程序； 翻译出来的程序称为目标程序或目标代码； 将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序； 把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序； 解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行； 编译程序是将高级语言写的源程序翻译成目标语言的程序。 关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。 P14 3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。 P14 4、语法分析和语义分析有什么不同？试举例说明。 答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量 x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。 P15 5、编译程序分遍由哪些因素决定？ 答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。 补充： 1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？ 答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。 补充： 2、赋值语句： A：= 5 * C的语法和语义指的是什么？ 答：语法分析将检查该语句是否符合赋值语句规则，语义是指将 5 * C 的结果赋值为 A 。 《编译原理》模拟题（补） 一．单项选择题 1.（）是两类程序语言处理程序。 A. 高级语言程序和低级语言程序 B. 解释程序和编译程序 C. 编译程序和操作系统 D. 系统程序和应用程序 2. 编译程序前三个阶段完成的工作是（）。 A. 词法分析、语法分析和代码优化 B. 代码生成、代码优化和词法分析 C. 词法分析、语法分析、语义分析和中间代码生成 D. 词法分析、语法分析和代码优化 3. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组（）。 A. 字符串 B. 产生式 C. 非开始符号 D. 文法 4. 词法分析器的输出结果是（）。 A. 单词的种别编码 B. 单词在符号表中的位置 C. 单词的种别编码和自身值 D. 单词自身值 5. 一个句型中称为句柄的是该句型的最左（）。 A. 非终结符号 B. 短语 C. 句子 D. 直接短语 6. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。 A. 自左向右 B. 自顶向下 C. 自底向上 D. 自右向左 7. 在通常的语法分析方法中，（）特别适用于表达式的分析。 A. 算符优先分析法 B. LR分析法 C. 递归下降分析法 D. LL（1）分析法 8. 优化可生成_____的目标代码。 A. 运行时间较短 B. 占用存储空间较小 C. 运行时间短但占用内存空间大 D. 运行时间短且占用存储空间小 9.（）是两类程序语言处理程序。 A. 系统程序和应用程序 B.编译程序和操作系统 C. 解释程序和编译程序 D.高级语言程序和低级语言程序 10. 经过编译所得到的目标程序是（）。 A. 四元式序列 B. 间接三元式序列 实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: "; 一.实验目的 1．深入理解算符优先分析法 2．掌握FirstVt和LastVt集合的求法有算符优先关系表的求法 3．掌握利用算符优先分析法完成中缀表达式到逆波兰式的转化 二.实验内容及要求 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 程序输入/输出示例： 输出的格式如下： (1) (2)输入一以#结束的中缀表达式(包括+—*/（）数字#) (3) (4)逆波兰式 备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔； 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照； 三.实验过程 1、逆波兰式定义 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。 2、产生逆波兰式的前提 中缀算术表达式 3、逆波兰式生成的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算 第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 编译原理实验报告 ******************************************************************************* ******************************************************************************* PL0语言功能简单、结构清晰、可读性强，而又具备了一般高级程序设计语言的必须部分，因而PL0语言的编译程序能充分体现一个高级语言编译程序实现的基本方法和技术。PL/0语言文法的EBNF表示如下： <程序>::=<分程序>. <分程序> ::=[<常量说明>][<变量说明>][<过程说明>]<语句> <常量说明> ::=CONST<常量定义>{，<常量定义>}; <常量定义> ::=<标识符>=<无符号整数> <无符号整数> ::= <数字>{<数字>} <变量说明> ::=VAR <标识符>{, <标识符>}; <标识符> ::=<字母>{<字母>|<数字>} <过程说明> ::=<过程首部><分程序>{; <过程说明> }; <过程首部> ::=PROCEDURE <标识符>; <语句> ::=<赋值语句>|<条件语句>|<当循环语句>|<过程调用语句> |<复合语句>|<读语句><写语句>|<空> <赋值语句> ::=<标识符>:=<表达式> <复合语句> ::=BEGIN <语句> {;<语句> }END <条件语句> ::= <表达式> <关系运算符> <表达式> |ODD<表达式> <表达式> ::= [+|-]<项>{<加法运算符> <项>} <项> ::= <因子>{<乘法运算符> <因子>} <因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’ <加法运算符> ::= +|- <乘法运算符> ::= *|/ <关系运算符> ::= =|#|<|<=|>|>= <条件语句> ::= IF <条件> THEN <语句> <过程调用语句> ::= CALL 标识符 <当循环语句> ::= WHILE <条件> DO <语句> <读语句> ::= READ‘(’<标识符>{,<标识符>}‘)’ <写语句> ::= WRITE‘(’<表达式>{,<表达式>}‘)’ <字母> ::= a|b|…|X|Y|Z <数字> ::= 0|1|…|8|9 【预处理】 对于一个pl0文法首先应该进行一定的预处理，提取左公因式，消除左递归（直接或间接），接着就可以根据所得的文法进行编写代码。 【实验一】词法分析 【实验目的】给出PL/0文法规，要求编写PL/0语言的词法分析程序。 【实验容】已给PL/0语言文法，输出单词（关键字、专用符号以及其它标记）。 编译原理复习题 一、填空题： 1、编译方式与解释方式的根本区别在于（是否生成目标代码）。 2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。 3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。 4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。 5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。 6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。 7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。 8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。 9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。 10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。 11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。 14、在编译程序中安排中间代码生成的目的是（便于代码优化）和（便于目标程序的移植）。 15、表达式-a+b*(-c+d)的逆波兰表示为（a-bc-d+*+ ）。 16、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为（aabcde/↑*f/+:= ）。 18、文法符号的属性有（继承属性）和（综合属性）两种。 19、一个文法符号的继承属性是通过语法树中它的（兄弟结点与父）结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。 第一章引论 1.编译过程的阶段 由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 2.编译程序的概念 3.编译程序的结构 例：（B）不是编译程序的组成部分。 A. 词法分析器； B. 设备管理程序 C. 语法分析程序； D. 代码生成程序 4.遍的概念 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 5.编译程序与解释程序的区别 例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D）。 A. 单用户与多用户的差别 B. 对用户程序的差错能力 C. 机器执行效率 D. 是否生成目标代码 第三章文法和语言 文法的概念 字母表、符号串和集合的概念及运算 例：(ab|b)*c 与下面的那些串匹配？（ACD） A. ababbc； B. abab； C. c； D. babc； E. aaabc 例：ab*c*(a|b)c 与后面的那些串匹配？（BC） A.acbbc B.abbcac C.abc D.acc 例：(a|b)a+(ba)*与后面的那些串匹配? （ADE）A.ba B.bba C.ababa D.aa E.baa 文法的定义（四元组表示） 文法G定义为四元组（V N，V T，P，S） V N：非终结符集 V T：终结符集 P：产生式（规则）集合 S：开始符号（或识别符号） 例：给定文法，A::= bA | cc，下面哪些符号串可由其推导出（①② ⑤）。 ①cc ②b*cc ③b*cbcc ④bccbcc ⑤bbbcc 什么是推导 例：已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 试给出下述表达式的推导：i*i+i 推导过程：E->E+T ->T+T ->T*F+T ->F*F+T ->i*F+T ->i*i+T ->i*i+F ->i*i+i ●句型、句子的概念 例：假设G一个文法，S是文法的开始符 号，如果S=>*x，则称x是句型。 例：对于文法G，仅含终结符号的句型称 为句子。 ●语言的形式定义 例：设r=(a|b|c)(x|y|z)，则L(r)中元素为 9个。 例：文法G产生式为S→AB，A→aAb|ε， B→cBd|cd，则B∈L(G)。 A. ababcd； B. ccdd； C. ab； D. aabb ●等价文法 例：如果两个文法描述了同一个语言，则这两个文法是等价文法。 ●文法的类型 0型：左边至少有一个非终结符 1型：右边长度>=左边长度 2型：左边有且仅有一个非终结符 3型：形如：A->aB,A->a 各类型文法都是逐级包含关系， 例：文法S→abC|c，bC→d是几型文法？0 型 例：文法S→abC，bC→ad是几型文法？1 型 例：文法G[A]：A→ε，A→aB，B→Ab，B→a 是几型文法？2型 例：文法S→a|bC，C→d是几型文法？ 3 《编译原理》实验报告 实验3 递归下降分析器的设计 学号班级计科1001班 时间：2012/4/15 地点:文波 同组人：无 指导教师：朱少林 实验目的 使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。 实验容 a.运用所学知识，编程实现递归下降语法分析程序。使用递归下降分析算法分析表达式 是否符合下文法： exp →exp addop term | term Addop →+ | - term→term mulop factor | factor mulop →* | / factor →(exp) | id | number 其中number可以是多位的十进制数字串（整数即可），因此这里还需要一个小的词法分析器来得到id 和number的值。 b.从数据文件中读出符号串，输出表达式并给出其正误评判。 实验数据文件中应该有多个表达式，可能有正确的也应该有错误的表达式；表达式有形式简 单的也应该有复杂的。每个表达式写在一行，以回车结束。 实验环境 软件：VC++6.0 实验前准备 1、方案设计： ①准备模拟数据：本实验中使用“work..cpp” ②程序思想： 为了使用递归向下的分析，为每个非终结符根据其产生式写一个分析程序，由于写入读出的操作频繁。所以程序中还有一个match(char t)函数，该函数是将字符写入文件打印输出同时从文件中读取下一个字符，而由于id和number可能是多个字符构成，故写了number()和id（）来分析数字和标识符，它们的功能仅仅是把整个number或id完整的读取出来并写入文件，打印输出。 由于分析的文件中可能出现非法字符，而一旦发现非法字符就无需再接着分析，所以在每次读取一个字符时调用islegal函数判断是否是合法字符，并返回0或1. 在main()函数中，while((lookahead=='\n'||lookahead==' ')&&lookahead!=EOF) fscanf(resource,"%c",&lookahead); 是为了忽略分析文件中的换行或空格，之后进入分析阶段，根据返回值判断是否是合法的表达式。在该程序中只有发现了非法字符才会返回0，否则就返回1，而对于合法的表达式，递归程序最后分析的字符就是换行符，不合法的表达式在未分析到换行符就会停止分析，所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。编译原理知识点汇总
编译原理实验指导
编译原理复习题(经典)
编译原理实验代码
编译原理 第十章 代码优化
(完整版)编译原理课后习题答案
实验1-3 《编译原理》词法分析程序设计方案
编译原理(PL0编译程序源代码)
编译原理实验题目及报告要求
编译原理第三版附带的实验源码
编译原理实验：目标代码的生成
编译原理习题答案
编译原理模拟题
编译原理实验 中间代码生成
(编译原理)逆波兰式算法的源代码
编译原理课后习题答案+清华大学出版社第二版
编译原理实验 (词法语法分析报告 附源代码
编译原理试题及答案3
编译原理复习(有答案)
编译原理实验-递归下降分析资料报告器地设计(含源代码和运行结果)
相关主题
文本预览