南开大学
计算机科学与技术学院课程设计报告（2010 ~2011 学年度第一学期）课程名称编译原理
设计题目LL(1)分析
姓名学号
专业班级
地点教师
1.需求分析
语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示：
图1 语法分析器在编译程序中的地位
语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。
自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。
自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。
实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。
对于给定的分析文法对象，构造它的预测分析程序；并任意给一算术表达式进行分析测试，本预测分析程序能够使用分析表和栈联合控制实现LL(1)分析，本文将就编译原理中比较常用的一个表达式文法，通过递归下降语法分析法来编写分析器。文中将为您提供如何通过FIRST、FOLLOW和SELECT集合来判断LL(1)方法，然后如何用递归下降语法分析法分析LL(1)方法的基本递归流程，以及用C++语言来编程实现分析器。本程序需要首先构造文法，根据文法判断是否正确，消除左递归，判断是否为LL（1）文法，然后用户输入句型，根据句型判断是否为该文法的句型。
2.概要设计
自顶向下的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶自顶向下的分析程序有两类：回溯分析程序（backtracking parser）和预测分析程序（predictive parser）。预测分析程序试图利用一个或多个先行记号来预测出输入串中的下一个构造，而回溯分析程序则试着分析其他可能的输入，当一种可能失败时就要求输入中备份任意数量的字符。虽然回溯分析程序比预测分析程序强大许多，但它们都非常慢，一般都在指数的数量级上，所以对于实际的编译器并不合适。
递归下降程序分析和LL(1)分析一般地都要求计算先行集合，它们分别称作First集合和Follow集合。由于无需显式地构造出这些集合就可以构造出简单的自顶向下的分析程序。
2.1 LL(1)文法设计
2.1.1 LL(1)文法定义
LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a )∩SELECT(A:=b)=?。这样，当前非终结符A面临输入符a时，如果a∈SELECT(A：=a)，则可以选择产生式A:=a去准确匹配。
如本程序中举例说明的a.txt的文法就是一个LL（1）文法：
S:=aBc|bAB
A:=aAb|b
B:=b|0
2.1.2文法的左递归
当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导A?A…，则称该文法是左递归的。
左递归又可以分为直接左递归和间接左递归。
2.1.3直接左递归
若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。
消除直接左递归的方法：
设有产生式是关于非终结符A的直接左递归：A→Aα|β（α,β∈V*，且β不以A 开头）
对A引入一个新的非终结符A′，把上式改写为：
A →βA′
A′→αA′|ε
2.1.5间接左递归
若文法中存在某一非终结符A，使得A?A…至少需要两步推导，则称该文法是间接左递归的。
消除间接左递归的方法：
【方法一】采用代入法把间接左递归变成直接左递归。
【方法二】直接改写文法：设有文法G10[S]：
S→Aα|β⑴
A→Sγ⑵
因为S?Aα?Sγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）：
S→Sγα|β⑶
⑶式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：
S→βS′
S′→γαS′|ε
2.2 设计数据结构
2.2.1 FIRST、FOLLOW集合的存储
由于FIRST集合和FOLLOW集合里都是一个一个的字符，所以用字符数组来存储比较合适。
具体如下：
char FIRST[NUMVN];
char FOLLOW[NUMVN];
2.2.2 终结符集合的存储
该集合存储着文法中一个一个的终结符，为了便于某一个终结符集中的查找定位，采用字符数组来存放是做适当不过的。
具体如下：
char VTSET[NUMVT];
2.2.3 文法产生式的存储
文法的产生式都是形如A->a|b,因此比较复杂，此处，我自定义了一个结点类型。
具体如下：
Struct VNNODE
{ char v;
char firstexpress[MAX];
char rightexpress[MAX];
char *firstptr;
char *followptr;
};
其中v存放着产生式左部的非终结符；
字符数组firstptr和rightptr分别存放该终结符的两个产生式，若只有一个产
生式，则rightexpress 为“ERROR”若该非终结符有ε产生式则将ε产生式
固定的存放在rightexpress中。
字符指针firstptr、followptr分别指向该非终结符的FIRST集合和FOLLOW集
合；
MAX 为常数255；
2.2.4 文法的存储
在此考虑到一般文法的产生式不是很多，采用数组存放是比较方便的。文法的基本单位是产生式。因此数组的每一个元素为上述的VNNODE类型。
具体如下：
VNNODE Grammer[NUMVN+1];
至此，我们可以看到设计这样的存储结构，便于算法的实现，但是也存在着一些局限性。即每个非终结符的产生式的个数最多只允许两个.
2.2.5 预测分析表的存储
预测分析表可以被视为一个二维数组，它的每一行与文法的一个非终结符号相关联，而其每一列则与一个终结符号或界符‘#’相关联。而数组中的每一个元素又是一个复合结构类型，为了将数组的第一行（终结符或‘#’）和第一列（非终结符）与数组内部的产生式相协调，我将数组的每一个元素定义为字符指针。
具体如下：
char *M[NUMVN+1][NUMVT+1]；
其中NUMVN 、NUMVT分别为文法的非终结符、终结符的最大个数，在此用CONST 修饰并定义为254；
2.3 LL(1)文法的判别：
一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。
2.4 预测分析程序——张表(分析表)，一个栈：
预测分析表是一个M[A, a]形式的矩阵，a是终结符或“#” (结束符),文法E->E+T|T,T->T*F|F,F->(E)|i是LL(1)分析表，栈STACK存放文法符号，栈底先放一个“#”，每个输入串后接一个“#”，设当前栈顶符号为X，当前输入符号为a，则对应的LL(1)预测
出，让a指向下一个输入符号；若X是一个非终结符，则查表M。若M[A,a]中存在产生式，则逐出X，然后把产生式右部符号串反序入栈(若右部符号为ε，则意味不推什么东西进栈)，同时应做这个产生式相应的语义动作(目前暂且不管)。若M[A,a]中存放出错标志，则调用ERROR。
2.5 程序流程图
3.详细设计
3.1 预测分析表的构造
对G中每个文法符号X∈VT∪VN，构造 FIRST(X)。连续使用下述规则，直至每个FIRST 集合不再增大：
若X∈VT，则FIRST(X)={X}；
若X∈VN，且有产生式X→a…，则把a加入FIRST(X) ；若Xε→也是一条产生式，则把ε也加入；若X→Y…是一个产生式且Y∈VN，则把FIRST(Y)中的所有非ε元素都加入FIRST(X)中；若X→Y1Y2…Yk是一个产生式，Y1,Y2,…,Yi–1都是非终结符，而且，对任意j(1≤j ≤i–1)，FIRST(Yj)都含有ε，则把FIRST(Yi)中的所有非ε元素加入FIRST(X)中；特别是，若所有的FIRST(Yj)均含有ε，j=1, 2, …,k, 则把ε加入FIRST(X)中。构造M[A, a]对文法G的每个产生式Aα→，执行第2步和第3步；对每个终结符a∈FIRST(α)，把Aα→加入M；若∈εFIRST(α)，则对任何b∈FOLLOW(A)把Aα→加入M；所有无定义的M[A, a]标上“出错标志”。程序模块实现如下：
void Make_M()
{
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;
}
}
}
}
3.2 构造FOLLOW(A)
对G中每个非终结符A，构造FOLLOW(A)。连续使用下述规则，直至每个FOLLOW不再增大。对文法的开始符号S，置#于FOLLOW(S)中；若Aα→Bβ是一个产生式，则把FIRST(β)\{ε}加入FOLLOW(B)；若Aα→B是一个产生式，或Aα→Bβ是一个产生式而ε?β，则把FOLLOW (A)加入FOLLOW(B)。对文法(: E→TE'T→FT' E→'+TE'|ε F→(E)|i T*→'FT'|ε其first和follow集如下：
FIRST(E)={(, i} FOLLOW(E)={), #}
FIRST(E')={+, ε} FOLLOW(E')={), #}
FIRST(T)={(, i} FOLLOW(T)={+, ), #}
FIRST(T')={*, ε} FOLLOW(T')={+, ), #}
FIRST(F)={(, i} FOLLOW(F)={*, +, ), #}
程序代码模块实现如下：
void FOLLOW(int i)
{
i nt j,k,m,n,result=1;
c har c,temp[20];
c=non_ter[i]; /*c为待求的非终结符*/
t emp[0]=c;
t emp[1]='\0';
m erge(fo,temp,1);
i f(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';
}
3.3 构造First集模块设计
FIRST(α)={a|α=*=>aβ,a∈VT，α,β∈V*}若α=*=>ε,则规定ε∈FIRST(α)．当一个文法中相同左部非终结符的右部存在能=*=>ε的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素。
本程序设计代码如下：
void first2(int i)
{ /*i为符号在所有输入符号中的序号*/
char c,temp[20];
i nt j,k,m;
c har ch='^';
c=v[i];
e mp(ch);
i f(in(c,termin)==1) /*若为终结符*/
{
first1[i][0]=c;
first1[i][1]='\0';
}
e lse 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 { 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'; } 3.4 消除左递归模块设计 欲构造行之有效的自上而下分析器，必须消除回溯。为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。在本程序里的设计思路如下：void recur(char *point) { /*完整的产生式在point[]中*/ int j,m=0,n=3,k; c har temp[20],ch; c h=c(); /*得到一个非终结符*/ k=strlen(non_ter); n on_ter[k]=ch; n on_ter[k+1]='\0'; cout<<"此文法含有左递归，现在开始分改此含左递归的产生式："< f or(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; } } } 3.5 判断文法是否为LL（1）文法 一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。本程序设计过程如下：int ll1() { int i,j,length,result=1; c har temp[50]; f or(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'; } f or(j=0;j<=strlen(v)-1;j++) first2(j); /*求单个符号的FIRST集合*/ p rintf("\nfirst1:"); f or(j=0;j<=strlen(v)-1;j++) printf("%c:%s ",v[j],first1[j]); printf("\nempty:%s",empty); p rintf("\n:::\n_emp:"); f or(j=0;j<=strlen(v)-1;j++) printf("%d ",_emp(v[j])); f or(i=0;i<=count-1;i++) FIRST(i,right[i]); /*求FIRST*/ p rintf("\n"); f or(j=0;j<=strlen(non_ter)-1;j++) { /*求FOLLOW*/ if(fo[j]==0) { fo[0]='\0'; FOLLOW(j); } } p rintf("\nfirst:"); f or(i=0;i<=count-1;i++) printf("%s ",first[i]); p rintf("\nfollow:"); for(i=0;i<=strlen(non_ter)-1;i++) printf("%s ",follow[i]); f or(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); } } p rintf("\nselect:"); f or(i=0;i<=count-1;i++) printf("%s ",select[i]); m emcpy(temp,select[0],strlen(select[0])); t emp[strlen(select[0])]='\0'; f or(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) return(0); } else { temp[0]='\0'; memcpy(temp,select[i],strlen(select[i])); temp[strlen(select[i])]='\0'; } } r eturn(1); } 3.6 判断输入的句型是否为给用户所输入文法的句型 void syntax()//总控算法 { int i,j,k,m,n,p,q; int w=1; char ch; char S[50],str[50]; printf("请输入该文法的句型："); 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'; } } } if(flag==1) { cout<<"步骤"<<" "<<"符号栈"<<" "<<"输入串"< } printf("%d %s ",w,S); w++; // cout< for(p=j;p<=strlen(str)-1;p++) //cout< printf("%c",str[p]); printf(" \n"); } } 3.7 LL(1)分析中的错误处理 出现下列两种情况时，说明出错 a．栈顶的终结符与当前输入符号不匹配； b．M[A, a]为空 发现错误，要尽快从错误中恢复过来，以便分析继续下去，跳过输入串中的一些符号直至遇到“同步符号”为止，这就涉及到同步符号集的选择问题。同时形成诊断信息、报告。 4 . 程序调试 程序运行说明： 适应的文法类型： a、一切LL(1)文法 b、含有直接左递归但可以转化为LL(1)文法的文法 c、含有间接左递归但可以转化为LL(1)文法的文法 说明： a、文法表达方式 例如：S:=Aa|Bb，其中空串用数字0代替，每输入一个表达式换行写下一表达式 b、文法输入结束后，换行再按‘#’结束 c、需要输入命令来执行所需要的功能 命令说明： 程序运行主界面： （1）open：打开文件 打开附带文档a.txt a.txt文档中的文法为LL(1)文法： S:=aBc|bAB A:=aAb|b B:=b|0 （2）input：输入文法 输入文法过程中“ε”应用“0”代替使用 每输入一条新文法需重新另起一行 文法输入结束后换行以“＃”结束 输入文法后若要保存文件，请按“y”键，并按提示输入备份文件的路径和名称。若没有输入备份路径，文法则保存在默认路径（程序所在文件夹）中；若不进行保存，则键入除“y”键外的任意键退出当前命令。 打开a.bck.txt文档，可以看到文法： （3）lltab：预测分析表 打开文件a.txt，对文档中语法进行分析： （4）select：查看每条产生式的SELECT集打开文件a.txt，求文档中语法的SELECT集 （5）first：求所输串的FIRST集 打开文件a.txt，求文档中语法的FIRST集 若需要继续求FIRST集，则按“y”键继续；若想退出当前命令，则键入除“y”键外的任意键退出当前命令。 （6）follow：求所输非终结符的FOLLOW集 打开文件a.txt，求文档中语法的FOLLOW集 若需要继续求FOLLOW集，则按“y”键继续；若想退出当前命令，则键入除“y”键外的任意键退出当前命令。 （7）ll：对某个输入句子进行分析 打开文件a.txt，输入要分析的字符串进行分析 （8）exit：推出程序 输入exit命令退出 5 . 总结分析 在课程设计中，我设计了一个自顶向下的语法分析器。由于涉及大量的编译原理知识，且编程过程复杂，代码量大，完成的功能并不是很多，而且也不是很完善，设计过程难免出现或多或少的错误。由于时间有限，无法对程序进行很好的测试，只发现其中的一些小错误并加以改进和完善，对其他未发现的BUG，只能尽量避免其出现。倘若有足够多的时间，我相信我可以做出需求分析中要求的功能，使其满足人民的要求，减少人工操作，减少运算时间，避免由于人工计算出现的错误，最终加快人们对语法的分析，减少人们的工作量。 通过此次实验，基本掌握语法分析方法－－LL（1）分析法；熟悉算法的基本思想。根据实验目的、要求和分析，选择相应的数据结构，使用Ｃ语言参照算法中的流程编写词法分析的程序。整个课程设计使我更加深入了解了程序编译过程是怎么样的,编译原理是怎么样用于实践了.这些加深了我对计算机的理解,也使我在程序设计的其它方面有了长进.总的来说,这个课程设计使我学到了很多东西。 实验报告 ——（方差分析） 一、实验目的 熟练使用SPSS软件进行方差分析。学会通过方差分析分析不同水平的控制变量是否对结果产生显著影响。 二、实验内容 1、某职业病防治院对31名石棉矿工中的石棉肺患者、可疑患者及非患者进行了用力肺活量（L）测定，问三组石棉矿工的用力肺活量有无差别?（自建数据集） 石棉肺患者可疑患者非患者 1.8 2.3 2.9 1.4 2.1 3.2 1.5 2.1 2.7 2.1 2.1 2.8 1.9 2.6 2.7 1.7 2.5 3.0 1.8 2.3 3.4 1.9 2.4 3.0 1.8 2.4 3.4 1.8 3.3 2.0 3.5 SPSS计算结果： 在建立数据集时定义group1为石棉肺患者，group2为可疑患者，group3为非患者。 零假设：各水平下总体方差没有显著差异。 相伴概率为0.075，大于0.05，可以认为各个组的方差是相等的，可以进行方差检验。 从上表可以看出3个组之间的相伴概率都小于显著性水平0.05，拒绝零假设，说明3个组之间都存在显著差别。 2、某汽车经销商在不同城市进行调查汽车的销售量数据分析工作，每个城市分别处于不同的区域：东部、西部和中部，而且汽车经销商在不同城市投放不同类型的广告，调查数据放置于附件中数据文件“汽车销量调查.sav”。 （1）试分析不同区域与不同广告类型是否对汽车的销量产生显著性的影响？（2）如果考虑到不同城市人均收入具有差异度时，再思考不同区域和不同广告类型对汽车销量产生的影响差异是否改变，这说明什么问题？ SPSS计算结果： （1）此为多因素方差分析 相伴概率为0.054大于0.05，可以认为各个组总体方差相等可以进行方差检验。 《编译原理》课程设计大纲 课程编号： 课程名称：编译原理/Compiler Principles 周数/学分：1周/1学分 先修课程：高级程序设计语言、汇编语言、离散数学、数据结构 适用专业：计算机科学与技术专业、软件工程专业 开课学院，系或教研室：计算机科学与技术学院 一、课程设计的目的 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。 设计时间： 开发工具： （1） DOS环境下使用Turbo C； （2） Windows环境下使用Visual C++ 。 （3） 其它熟悉语言。 二、课程设计的内容和要求 设计题一：算术表达式的语法分析及语义分析程序设计。 1.目的 通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词 法检查和分析。 2.设计内容及要求： 算术表达式的文法： 〈无符号整数〉∷＝ 〈数字〉{〈数字〉} 〈标志符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝ [＋｜－]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝ 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝ 〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝ ＋｜－ 〈乘法运算符〉∷＝ ＊｜／ （1） 分别选择递归下降法、算符优先分析法（或简单优 先法）完成以上任务，中间代码选用逆波兰式。 （2） 分别选择LL（1）、LR法完成以上任务，中间代码选 用四元式。 （3） 写出算术表达式的符合分析方法要求的文法，给出 分析方法的思想，完成分析程序设计。 （4） 编制好分析程序后，设计若干用例，上机测试并通 过所设计的分析程序。 设计题二：简单计算器的设计 1．目的 通过设计、编制、调试一个简单计算器程序，加深对语法及语 义分析原理的理解，并实现词法分析程序对单词序列的词法检 查和分析。 2.设计内容及要求 算术表达式的文法： 《LL（1）分析器的构造》实验报告 一、实验名称 LL(1)分析器的构造 二、实验目的 设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。 三、实验内容和要求 设计并实现一个LL(1)语法分析器，实现对算术文法: G[E]:E->E+T|T T->T*F|F F->(E)|i 所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。 实验要求: 1、检测左递归，如果有则进行消除； 2、求解FIRST集和FOLLOW集； 3、构建LL(1)分析表； 4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。 四、主要仪器设备 硬件：微型计算机。 软件： Code blocks（也可以是其它集成开发环境）。 五、实验过程描述 1、程序主要框架 程序中编写了以下函数，各个函数实现的作用如下： void input_grammer(string *G);//输入文法G //将文法G预处理得到产生式集合P，非终结符、终结符集合U、u， int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GG int* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空 string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST集 string FIRST(string U,string u,string* first,string s)；//求符号串s=X1X2...Xn的FIRST集 string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表 void analyse(string **table,string U,string u,int t,string s)；//分析符号串s 2、编写的源程序 #include 非参数检验 实验报告 方差分析 学院: 参赛队员: 参赛队员: 参赛队员: 指导老师: 目录 一、实验目的 (1) 1.了解方差分析的基本内容； (1) 2.了解单因素方差分析； (1) 3.了解多因素方差分析； (1) 4.学会运用spss软件求解问题； (1) 5.加深理论与实践相结合的能力。 (1) 二、实验环境 (1) 三、实验方法 (1) 1. 单因素方差分析； (1) 2. 多因素方差分析。 (1) 四、实验过程 (1) 问题一： (1) 1.1实验过程 (1) 1.1.1输入数据，数据处理； (1) 1.1.2单因素方差分析 (1) 1.2输出结果 (3) 1.3结果分析 (3) 1.3.1描述 (3) 1.3.2方差性检验 (4) 1.3.3单因素方差分析 (4) 问题二： (4) 2.1实验步骤 (5) 2.1.1命名变量 (5) 2.1.2导入数据 (5) 2.1.3单因素方差分析 (5) 2.1.4输出结果 (7) 2.2结果分析 (7) 2.2.1描述 (7) 2.2.2方差性检验 (8) 2.2.3单因素方差分析 (8) 问题三： (8) 3.1提出假设 (8) 3.2实验步骤 (8) 3.2.1数据分组编号 (8) 3.2.2多因素方差分析 (9) 3.2.3输出结果 (13) 3.3结果分析 (14) 五、实验总结 (14) 方差分析 一、实验目的 1.了解方差分析的基本内容； 2.了解单因素方差分析； 3.了解多因素方差分析； 4.学会运用spss软件求解问题； 5.加深理论与实践相结合的能力。 二、实验环境 Spss、office 三、实验方法 1.单因素方差分析； 2.多因素方差分析。 四、实验过程 问题一： 1.1.1输入数据，数据处理； 1.1.2单因素方差分析 选择：分析→比较均值→单因素AVONA； 5.1、实验步骤： 1．建立数据文件。 定义2个变量：PWK和DCGJSL，分别表示排污口和大肠杆菌数量。 2. 选择菜单“分析→比较均值→单因素”,弹出“单因素方差分析”对话框。在对话 框左侧的变量列表中，选择变量“DCGJSL”进入“因变量”列表框，选择变量“PWK”进入“因子”列表框。 3．单击“确定”按钮，得到输出结果。 结果解读： 由以上结果可以看到，观测变量大肠杆菌数量的总离差平方和为460.438；如果仅考虑“排污口”单个因素的影响，则大肠杆菌数量总变差中，排污口可解释的变差为308.188，抽样误差引起的变差为152.250，它们的方差（平均变差）分别为102.729和12.688，相除所得的F统计量的观测值为8.097，对应的概率P值为0.003。在显著性水平α为0.05的情况下。由于概率P值小于显著性水平α，则应拒绝零假设，认为不同的排污口对大肠杆菌数量产生了显著影响，它对大肠杆菌数量的影响效应不全为0。 因此，可判断各个排污口的大肠杆菌数量是有差别的。 5.2、实验步骤： 1．建立数据文件。 定义2个变量：Branch和Turnover，分别表示分店和日营业额。将Branch的值定义为1=第一分店，2=第二分店，3=第三分店，4=第四分店，5=第五分店。 2. 选择菜单“分析→比较均值→单因素”,弹出“单因素方差分析”对话框。在对话 框左侧的变量列表中，选择变量“Turnover”进入“因变量”列表框，选择变量“Branch”进入“因子”列表框。 3．单击“确定”按钮，得到输出结果。 结果解读： 由以上结果可以看到，观测变量日营业额的总离差平方和为1187668.733；如果仅考虑“分店”单个因素的影响，则日营业额总变差中，分店可解释的变差为366120.900，抽样误差引起的变差为821547.833，它们的方差（平均变差）分别为91530.225和14937.233，相除所得的F统计量的观测值为6.128，对应的概率P值近似为0。在显著性水平α为0.05的情况下，由于概率P值小于显著性水平α，则应拒绝零假设，认为不同的分店对日营业额产生了显著影响，它对日营业额的影响效应不全为0。 因此，在α＝0.05的显著性水平下，“这五个分店的日营业额相同”这一假设不成立。 5.3、实验步骤： 1．建立数据文件。 定义3个变量：weight和method，分别表示幼苗干重（mg）和处理方式。将method 的值定义为1=HCI，2=丙酸，3=丁酸，4=对照。 2. 选择菜单“分析→比较均值→单因素”,弹出“单因素方差分析”对话框。在对话 框左侧的变量列表中，选择变量“，method”进入“因变量”列表框，选择变量“weight”进入“因子”列表框。在“两两比较”选项中选择LSD、Bonferroni 和Scheffe方法。 课程设计(论文)任务书 软件学院学院软件工程专业07-1班 一、课程设计(论文)题目LL(1)分析过程模拟 二、课程设计(论文)工作自 2010 年 6 月 22日起至 2010 年 6月 28 日止。 三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．本课程设计的目的 （1）使学生掌握LL（1）模块的基本工作原理； （2）培养学生基本掌握LL（1）分析的基本思路和方法； （3）使学生掌握LL（1）的调试； （4）培养学生分析、解决问题的能力； （5）提高学生的科技论文写作能力。 2．课程设计的任务及要求 1）基本要求： （1）分析LL（1）模块的工作原理； （2）提出程序的设计方案； （3）对所设计程序进行调试。 2）创新要求： 在基本要求达到后，可进行创新设计，如改算法效率。 3）课程设计论文编写要求 （1）要按照书稿的规格打印誊写课程设计论文 （2）论文包括目录、绪论、正文、小结、参考文献、附录等 （3）课程设计论文装订按学校的统一要求完成 4）答辩与评分标准： （1）完成原理分析：20分； （2）完成设计过程（含翻译）：40分； （3）完成调试：20分； （4）回答问题：20分。 5）参考文献： （1）张素琴，吕映芝，蒋维杜，戴桂兰.编译原理（第2版）.清华大学出版社 （2）丁振凡.《Java语言实用教程》北京邮电大学出版社 6）课程设计进度安排 内容天数地点 构思及收集资料2图书馆 编程与调试4实验室 撰写论文1图书馆、实验室 学生签名： 2009 年6 月22 日 课程设计(论文)评审意见 （1）完成原理分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）；（3）完成调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）翻译能力（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（） 评阅人：职称： 年月日 编译原理课程设计报告 课题名称： C-语言编译器设计（scanner和parser） 提交文档学生姓名： 提交文档学生学号： 同组成员名单：无 指导教师姓名：金军 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间： 2011年 6 月 17 日 1.课程设计目标 设计C-Minus编译器分为scanner和parser两个部分。scanner主要作用是对目标代码进行扫描，列出关键字，变量等内容；parser主要对语法进行分析并生成语法树。 2.分析与设计 ●实现方法：代码用C语言编译而成。其中scanner为手工实现，主要采用switch-case结构实现 状态转换；parser部分采用递归下降分析方法实现。 ●扫描器：C-的词法如下： 1、语言的关键字：i f el se i nt return void while 2、专用符号：+ - * /< <= > >= == != =; , ( ) [ ] { } /* */ 3、其他标记是变量（ID）和数字（NUM），通过下列正则表达式定义： ID = letter letter* NUM = di git digi t* letter = a|..|z|A|..|Z digi t = 0|..|9 4、空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字 5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在 标记内)上，且可以超过一行。注释不能嵌套 其DFA图如下： 分析器：以下为C-的语法规则BNF: 编译原理实验报告 实验名称：分析调试语义分析程序 TEST抽象机模拟器完整程序 保证能用！！！！！ 一、实验目的 通过分析调试TEST语言的语义分析和中间代码生成程序，加深对语法制导翻译思想的理解，掌握将语法分析所识别的语法范畴变换为中间代码的语义翻译方法。 二、实验设计 程序流程图 extern int TESTScan(FILE *fin,FILE *fout); FILE *fin,*fout; //用于指定输入输出文件的指针 int main() { char szFinName[300]; char szFoutName[300]; printf("请输入源程序文件名（包括路径）:"); scanf("%s",szFinName); printf("请输入词法分析输出文件名（包括路径）："); scanf("%s",szFoutName); if( (fin = fopen(szFinName,"r")) == NULL) { printf("\n打开词法分析输入文件出错！\n"); return 0; } if( (fout = fopen(szFoutName,"w")) == NULL) { printf("\n创建词法分析输出文件出错！\n"); return 0; } int es = TESTScan(fin,fout); fclose(fin); fclose(fout); if(es > 0) printf("词法分析有错，编译停止！共有%d个错误！\n",es); else if(es == 0) { printf("词法分析成功！\n"); int es = 0; 云南大学滇池学院 方差分析与假设检验实验报告二 学生姓名：方炜学号：20092123080 专业：软件工程 一、实验目的和要求： 1、初步了解SPSS的基本命令； 2、掌握方差分析和假设检验。 二、实验内容： 1、为比较5中品牌的合成木板的耐久性，对每个品牌取4个样本作摩擦试验测量磨损量，得以下数据： （1）它们的耐久性有无明显差异？ （2）有选择的作两品牌的比较，能得出什么结果？ 2、将土质基本相同的一块耕地分成5块，每块又分成均等的4小块。在每块地内把4个品 种的小麦分钟在4小块内，每小块的播种量相同，测得收获量如下： 考察地块和品种对小麦的收获量有无显著影响？并在必要时作进一步比较。 3、为了研究合成纤维收缩率和拉伸倍数对纤维弹性的影响进行了一些试验。收缩率取0，4， 8，12四个水平；拉伸倍数取460，520，580，640四个水平，对二者的每个组合重复作两次试验，所得数据如下： （1）收缩率，拉伸倍数及其交互作用对弹性有无显著影响？ （2）使弹性达到最大的生产条件是什么？ 三、实验结果与分析： 1、运行结果截图： 1、结果分析： （1）、Sig<0.05，耐久性有明显差异 （2）、由样本分析，品牌3分为一类；品牌1，2，5分为一类；品牌4分为一类。而品牌3和品牌4差距最大，品牌3的耐久性最差，品牌4的耐久性最好。 2、运行结果截图： 2、结果分析： （1）、地块（A组）Sig>0.05对小麦的收获量无显著影响，品种（B组）Sig<0.05对小麦的收获量有显著影响。 （2）、由图得，地块4最适合种小麦，地块1最不适合种小麦；而品种2的小麦收获量最大，品种4的小麦收获量最小。 3、运行结果截图： 编译原理程序设计报告 一个简单文法的编译器的设计与实现专业班级：计算机1406班 组长姓名：宋世波 组长学号： 20143753 指导教师：肖桐 2016年12月 设计分工 组长学号及姓名：宋世波20143753 分工：文法及数据结构设计 词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成 组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0) 部分目标代码生成 组员2学号及姓名：孙何奇20143754 分工：符号表组织 部分目标代码生成 摘要 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。 一．编译器的概述 1.编译器的概念 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。 2．编译器的种类 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语 编译原理课程设计报告 课题名称：C- Minus词法分析和语法分析设计 提交文档学生姓名：X X X 提交文档学生学号：XXXXXXXXXX 同组成员名单：X X X 指导教师姓名：X X 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2015年6月10日 1.课程设计目标 实验建立C-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。 2.分析与设计 C-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。 2.1 、扫描程序scanner部分 2.1.1系统设计思想 设计思想：根据DFA图用switch-case结构实现状态转换。 惯用词法： ①语言的关键字：else if int return void while ②专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 大写和小写字母是有区别的 ④空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM 关键字。 ⑤注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套 scanner的DFA 说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。 2.1.2程序流程图 学号20102７９8 专业软件工程姓名薛建东 实验日期２013.04.０8 教师签字成绩实验报告 【实验名称】ＬL（1）语法分析 【实验目的】 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。 【实验内容】 ◆根据某一文法编制调试LL ( 1)分析程序，以便对任意输入的符号串进行分析。 ◆构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 ◆分析法的功能是利用LＬ（１)控制程序根据显示栈栈顶内容、向前看符号以及LL(1) 分析表,对输入符号串自上而下的分析过程。 【设计思想】 （1）、LL(１)文法的定义 ＬL(1)分析法属于确定的自顶向下分析方法。LＬ（１)的含义是：第一个Ｌ表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式（规则)进行推导。 LL(1)文法的判别需要依次计算FIRＳT集、FOLＬＯW集和SELLＥＣT集,然后判断是否为LL（1)文法，最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LＬ(１)分析法中,每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符;当出现终结符时，判断其与剩余输入串的第一个字符是否匹配,如果匹配，则继续分析,否则报错。ＬＬ（1）分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式Ａ→α，A→β,都要满足下面条件:ＳELEＣＴ(Ａ→α)∩SELＥCT（Ａ→β)＝? (2）、预测分析表构造 LL（1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推 实验报告 方差分析 学院: 参赛队员: 参赛队员: 参赛队员: 指导老师: 目录 一、实验目的 (4) 1.了解方差分析的基本内容； (4) 2.了解单因素方差分析； (4) 3.了解多因素方差分析； (4) 4.学会运用spss软件求解问题； (4) 5.加深理论与实践相结合的能力。 (4) 二、实验环境 (4) 三、实验方法 (4) 1. 单因素方差分析； (4) 2. 多因素方差分析。 (4) 四、实验过程 (4) 问题一： (4) 1.1实验过程 (4) 1.1.1输入数据，数据处理； (4) 1.1.2单因素方差分析 (4) 1.2输出结果 (6) 1.3结果分析 (6) 1.3.1描述 (6) 1.3.2方差性检验 (7) 1.3.3单因素方差分析 (7) 问题二： (7) 2.1实验步骤 (8) 2.1.1命名变量 (8) 2.1.2导入数据 (8) 2.1.3单因素方差分析 (8) 2.1.4输出结果 (10) 2.2结果分析 (10) 2.2.1描述 (10) 2.2.2方差性检验 (11) 2.2.3单因素方差分析 (11) 问题三： (11) 3.1提出假设 (11) 3.2实验步骤 (11) 3.2.1数据分组编号 (11) 3.2.2多因素方差分析 (12) 3.2.3输出结果 (16) 3.3结果分析 (17) 五、实验总结 (17) 方差分析 一、实验目的 1.了解方差分析的基本内容； 2.了解单因素方差分析； 3.了解多因素方差分析； 4.学会运用spss软件求解问题； 5.加深理论与实践相结合的能力。 二、实验环境 Spss、office 三、实验方法 1. 单因素方差分析； 2. 多因素方差分析。 四、实验过程 问题一： 1.1.1输入数据，数据处理； 1.1.2单因素方差分析 选择：分析→比较均值→单因素AVONA； 编译原理课程设计报告 实验名称编译原理课程设计 班级 学号 姓名 指导教师 实验成绩 2013 年06月 一、实验目的 通过设计、编写和调试，将正规式转换为不确定的有穷自动机，再将不确定的有穷自动机转换为与之等价的确定的有穷自动机，最后再将确定有穷自动机进行简化。 通过设计、编写和调试构造LR(0)项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR(0)分析表的步骤，对文法的要求，能够从文法G出发生成LR(0)分析表，并对给定的符号串进行分析。 二、实验内容 正规式——>NFA——>DFA——>MFA 1.正规式转化为不确定的有穷自动机 （1）目的与要求 通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，使学生了解Thompson算法，掌握转换过程中的相关概念和方法，NFA的表现形式可以是表格或图形。 （2）问题描述 任意给定一个正规式r（包括连接、或、闭包运算），根据Thompson算法设计一个程序，生成与该正规式等价的NFA N。 （3）算法描述 对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 步骤1：首先构造基本符号的有穷自动机。 步骤2：其次构造连接、或和闭包运算的有穷自动机。 （4）基本要求 算法实现的基本要求是： (1) 输入一个正规式r； (2) 输出与正规式r等价的NFA。（5）测试数据 输入正规式：(a|b)*(aa|bb)(a|b)* 得到与之等价的NFA N （6）输出结果 2.不确定的有穷自动机的确定化 （1）目的与要求 通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。（2）问题描述 任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFA N变换为与之等价的DFA D。 （3）算法描述 用子集法将NFA转换成接受同样语言的DFA。 步骤一：对状态图进行改造 (1) 增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结 点引ε弧到Y结点。 (2) 对状态图进一步进行如下形式的改变 编译原理课程设计 自顶向下语法分析器 学院（系）：计算机科学与技术学院学生姓名：xxxxxxxxx 学号：xxxxxxxxx 班级：电计1102 大连理工大学 Dalian University of Technology 目录 1 系统概论 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示： 图1 语法分析器在编译程序中的地位 语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。 自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。 自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。 2 需求分析 以前，人们对语法的分析都建立在人工的基础上，人工分析虽然能够做到侧类旁推，但终究人力有限，再精密的分析都会出现或多或少的错误。为减少因人为产生的错误，并加快 2011-2012学年第二学期 《编译原理》课程设计报告 学院：计算机科学与工程学院 班级： 学生姓名：学号： 成绩： 指导教师： 时间：2012年5 月 目录 一、课程设计的目的 ---------------------------------------------------------------- - 1 - 二、课堂实验及课程设计的内容 -------------------------------------------------- - 1 - 2.1、课堂实验内容-------------------------------------------------------------- - 1 - 2.2、课程设计内容-------------------------------------------------------------- - 1 - 三、visual studio 2008 简介------------------------------------------------------- - 2 - 四、问题分析及相关原理介绍 ----------------------------------------------------- - 3 - 4.1、实验部分问题分析及相关原理介绍 ---------------------------------- - 3 - 4.1.1、词法分析功能介绍及分析------------------------------------- - 3 - 4.1.2、语法分析功能介绍及分析------------------------------------- - 3 - 4.1.3、语义分析功能介绍及分析------------------------------------- - 4 - 4.2、课程设计部分问题分析及相关原理介绍 ---------------------------- - 5 - 4.2.1、编译程序介绍 ----------------------------------------------------- - 5 - 4.2.2、对所写编译程序的源语言的描述（C语言） -------------- - 6 - 4.2.3、各部分的功能介绍及分析 -------------------------------------- - 7 - 4.3、关键算法：单词的识别-------------------------------------------------- - 8 - 4.3.1、算法思想介绍 ----------------------------------------------------- - 8 - 4.3.2、算法功能及分析 -------------------------------------------------- - 8 - 五、设计思路及关键问题的解决方法 ------------------------------------------ - 10 - 5.1、编译系统------------------------------------------------------------------ - 10 - 5.1.1、设计思路 --------------------------------------------------------- - 10 - 5.2、词法分析器总控算法--------------------------------------------------- - 12 - 5.2.1、设计思路 --------------------------------------------------------- - 12 - 5.2.2、关键问题及其解决方法 --------------------------------------- - 13 - 六、结果及测试分析-------------------------------------------------------------- - 14 - 6.1、软件运行环境及限制--------------------------------------------------- - 14 - 6.2、测试数据说明------------------------------------------------------------ - 14 - 6.3、运行结果及功能说明--------------------------------------------------- - 16 - 6.4、测试及分析说明--------------------------------------------------------- - 16 - 七、总结及心得体会 --------------------------------------------------------------- - 17 - 7.1、设计过程------------------------------------------------------------------ - 17 - 7.2、困难与收获 ------------------------------------------------------------- - 17 - 八、参考文献 ------------------------------------------------------------------------ - 18 - 编译原理： 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象。 编译原理课程设计： 《编译原理课程设计》是2007年11月浙江大学出版社出版的图书，作者是冯雁、鲁东明、李莹。 内容简介： 本书围绕着编译技术的基本原理和方法，以模拟程序设计语言SPL的编译器的设计和实现为主线，结合词法分析、语法分析、语义分析、代码生成、代码优化、错误处理等各个基本模块，对原理和实现方法进行了详细分析。该编译器可接受SPL的程序，并将其翻译成汇编语言程序，最终实现汇编语言到8086/8088机器语言的翻译。本书为编译技术等相关课程的实验提供了参考。在附件中还提供了三类不同类型和难度的实验题，可供课程实验选择。 第1章引论： 1.1本书介绍 1.2SPL语言的特点及实验安排 1.2.1SPL语言的特点 1.2.2SPL语言编译器的主要结构1.2.3实验安排 1.3平台的选择和介绍 1.3.1LEX简介 1.3.2YACC简介 第2章词法分析： 2.1词法分析器的基本框架 2.2词法分析器的基本原理 2.2.1DFA的构造和实现 2.2.2词法分析的预处理 2.2.3实现词法分析器的注意要点2.3词法分析器的实现 2.3.1SPL语言单词属性字 2.3.2SPL词法分析器的输入和输出2.3.3SPL词法分析器的分析识别第3章语法分析： 3.1语法分析的基本框架 3.1.1上下文无关文法 3.1.2语法分析过程 3.1.3语法分析过程中的数据结构3.2语法分析的基本方法 实习二语法分析－自上而下分析 一、实验目的 使用预测分析方法对输入的表达式进行分析，掌握其具体的使用并且学会去分析一个文法。 二、实验内容 1．设计表达式的语法分析器算法（使用预测分析） 2．编写一段代码并上机调试查看其运行结果 三、实验要求 使用LL（1）分析算法设计表达式的语法分析器 LL（1）文法是一个自上而下的语法分析方法，它是从文法的开始符号出发，生成句子的最左推导，从左到右扫描源程序，每次向前查看一个字符，确定当前应该选择的产生式。 实现LL（1）分析的另一种有效方法是使用一张分析表和一个栈进行联合控制。 预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前a的输入符号行事的。对于任何（X，a），总控程序每次都执行三种可能的动作之一。 1.若X＝a＝“#”，则宣布分析成功，停止分析过程 2.若X＝a≠“#”，则把X从STACK栈顶逐出，让a指向下一 个输入符号。 3.若X是一个非终结符，则查看分析表。 四、运行结果 （本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析） 五、源程序实现 /*LL(1)分析法源程序，只能在VC++中运行*/ #include 先简要分析一下语法分析的大致流程： 当有句子要进行处理时，首先要对其进行词法分析来分解出该句子中的每个符号，然后将该句子按照算符优先算法压入归约栈中，如果可以顺利归约，则说明这是一个合法的句子，否则该句子非法。 这里有一个需要考虑的地方，就是如何进行归约。由于文法已经给定，所以我们考虑设计一个文法表，文法表中的内容就是可归约串的种别码的顺序，比如v=E可以表示为9,1,13。这样的话当我们要进行一次归约时，只用按顺序存储最左素短语中符号的种别码，然后拿这个种别码序列与文法表进行匹配，就可知道当前归约需要执行哪些操作。 还有一点需要注意，就是如何对一个表达式进行求值。这里需要我们设计一个二元组的变量名表，这个变量名表可以根据变量的名称来返回变量的数据。变量名表的具体设计见详细设计部分。 由于是简化分析，所以这个程序只考虑整数的处理。 有了上面的分析，可以构造出算符优先分析算法的流程图，如下图所示。 详细设计 （1）词法分析部分 由于词法分析的内容在课程设计1中已经介绍，并且这次的状态转换图与课程设计1中的非常相似，所以这里就不过多介绍。（2）优先关系表 在程序中我们用一个二维数组priTable[][]来存储算符间的优先关系。priTable[a][b]=1表示a>b; 。priTable[a][b]=0表示a=b; 。priTable[a][b]=-1表示aspss实验报告---方差分析
编译原理课程设计
编译原理实验报告《LL(1)语法分析器构造》
方差分析实验报告
实验报告 单因素方差分析
编译原理课程设计报告_LL(1)分析过程模拟
编译原理课程设计
TEST语言 -语法分析,词法分析实验报告
方差分析与假设检验实验报告
编译原理课程设计报告(一个完整的编译器)
CMinus词法分析和语法分析设计编译器编译原理课程设计报告书
编译原理LL(1)语法分析实验报告
方差分析实验报告
(重庆理工大学计算机学院)编译原理课程设计报告
编译原理课程设计
编译原理课程设计报告
编译原理课程设计
语法分析(自上而下分析)实验报告
编译原理课程设计
相关主题
文本预览