那些年老虎的_温柔
范文一：预测分析法
《编译原理》课程实验报告
实验名称：预测分析法
姓名：许晓民学号：地点：实验楼教师：韩丽院系：计算机与通信工程学院专业：计算机科学与技术
11-01
时间：2014/5/18
一．实验目的
加深对词法分析器的工作过程的理解：加强对词法分析方法的掌握：能够采用一种编程语言实现简单的词法分析程序：能够用自己编写的分析程序对简单的程序段进行词法分析
二．实验内容
#include int main(int argc, char* argv[]) { char syn[15]; //语法栈 int top; //栈顶指针 char lookahead; //当前单词 char exp[50]; //表达式区 int m =0; //表达式指针 char s[4][5]={"d","+","*","("}; //表中有空白的符号 char string[3]={'E','T','F'}; //表中有同步记号的的非终结符 int ll1[7][6]={ {1,0,0,1,9,9}, //LL(1)分析表,9表示同步记号, 第6行是#，第7行是） {0,2,0,0,3,3}, {4,9,0,4,9,9}, {0,6,5,0,6,6}, {8,9,9,7,9,9}, {12,12,12,12,12,10}, {13,13,13,13,11,13}}; int i,j; //表行和列 int code; //表项 printf("请输入合法字符串:\n"); scanf("%s",exp); top=1; lookahead=exp[m++]; syn[0]='#'; syn[1]='E'; printf("\n"); printf("\n"); printf("预测分析表 如下：\n"); printf("\n"); printf("\n"); printf("\ti\t *\t +\t (\t )\t #\n"); printf(" E\tE->TE'\t\t\tE->TE'\n"); printf(" E'\t\t\tE'->+TE'\t E'->ε\n"); printf(" T\tT->FT'\t\t\tT->FT'\t\n"); printf(" T'\t\tT'->*FT'\t\t T'->ε\t\n"); printf(" F\tF->d\t\t\tF->(E)\n\n"); printf("调用规则顺序：\n"); while(1) { switch(syn[top]) //行 { case 'E':i=0;break; case 'e':i=1;break; case 'T':i=2;break; case 't':i=3;break; case 'F':i=4;break; case '#':i=5;break; case ')':i=6;break; } switch(lookahead) //列 { case 'd':j=0;break; case '+':j=1;break; case '*':j=2;break; case '(':j=3;break; case ')':j=4;break; case '#':j=5;break; } code=ll1[i][j]; if(code==10) { printf("语法分析结束\n"); // break; } else { switch(code) { case 0: { // printf("出错，用户多输入了%s,跳过%s\n",s[j],s[j]); if(j==0) {//lookahead=exp[m++]; lookahead=exp[m++];} else lookahead=exp[m++]; break; } case 1:{printf("E →TE ′\n");syn[top]='e';syn[top+1]='T';top++;break;} case 2:{printf("E′ → +TE`\n");syn[top+1]='T';top++;lookahead=exp[m++];break;} case 3:{printf("E′ →ε\n");syn[top]='\0';top--;break;} case 4:{printf("T → FT ′\n");syn[top]='t';syn[top+1]='F';top++;break;} case 5:{printf("T′ → * FT′ \n");syn[top+1]='F';top++;lookahead=exp[m++];break;} case 6:{printf("T′ →ε\n");syn[top]='\0';top--;break;} case 7:{printf("F → (E)\n");syn[top]=')';syn[top+1]='E';top++;lookahead=exp[m++];break;} case 8:{printf("F → d\n");syn[top]='\0';top--;lookahead=exp[m++];lookahead=exp[m++];break;} case 9:{printf("弹栈，弹出非终结符%c，用户少输入了一个d\n",string[i/2]);syn[top]='\0';top--;break;} case 11:{syn[top]='\0';top--;lookahead=exp[m++];break;} case 13:{printf("弹栈，弹出终结符 ) ，用户少输入了一个右括号\n");syn[top]='\0';top--;break;} } } } return 0; } 三．实验步骤 1：定义目标语言的可用符号表和构词规则； 2：依次读入源程序符号，对源程序进行单词切分和识别，知道源程序结束： 3：对正确的单词，按照它的种别以（特征码，值）的形式保存在符号表中； 4：对不正确的单词，做出错误处理。 调试程序的结果： 四．总结与回顾 通过这次实验，让我了解到如何设计，编制并调试词法分析器程序，加深对词法分析原理的理解；了解了构造词法分析程序的手工方式的相关原理，根据识别语言单词的状态转换图，，使用某种高级语言（C++）直接编写此法分析程序。另外，也让我重新了解了高级语言的相关内容，并加深了理解。 #include #include #include char str[100]; //存储待分析的句 子 const char T[ ] = const char NT[ ] = const char *a[]={ }; /*指向产生式右部符号串 */ const char *p[] = { /*0. S→ a */ /*1. S → ^ */ /*2. S→ (T) */ /*3. T→ SW */ /*4. W → ,SW */ }; //设 M[i][j]=x,通过 p[M[i][j]]=p[x]获取右部符号串。 const int M[][6] = { /* a ^ ( ) , $ */ /*S*/ { 0, 1, 2, -1, -1, -1 }, /*T*/ { 3, 3, 3, -1, -1, -1 }, /*W*/ { -1, -1,-1, 5, 4, -1 } }; void init()//输入待分析的句子 { printf( scanf( } int lin(char c);//非终结符转换为行 号 int col(char c);//终结转换为列号 bool isNT(char c);//isNT判断是否 是非终结符 bool isT(char c);//isT判断是否是终 结符。 void main(void) { int i,j=0; int flag=1,flag2=0; char A; //设置指示句子的当 前字符 char stack[20]= {'$','S'}; //栈 赋初值 int top = 1 ; //设置栈顶指针 char X = ' ' ; //存储栈顶字符 init(); A=str[0]; printf( 串 \t所用规则 \n while ( 1 ) { printf( //输出当前执行步数 for ( i = 0 ; i <= top="" ;="" i++="" )="" 输出当前栈的内容="" (出栈前=""> { printf( } printf( for ( i = flag-1 ; str[i]!='#' ; i++ ) { printf( } if(flag2==1) { printf( } //出栈 X = stack[top--] ; if (X=='$')//是结束符 { if (X==A)//是结束符 { printf( } else printf( break; } else if (isT(X))//是终结符 { A=str[flag++]; } else if (isNT(X))//是否是非 终结符 { flag2=1; //逆序入栈 for( i = strlen( p[ M[ lin(X) ][col(A)] ] ) - 1; i >= 0; i--) { stack[++top] = *(p[M[lin(X)][col(A)]] + i ) ; } } else { printf( exit(0); } } } int lin(char c) { for(int i = 0; i < (int)strlen(nt);="" i="" ++=""> { if (c == NT[i]) { return i ; } } printf( } int col(char c) { for (int i=0; i<(int)strlen(t); i="" ++=""> { if (c == T[i]) return i; } printf( } bool isNT(char c) //是否是非终结 符 { for (int i = 0; i < (int)strlen(nt);="" i="" ++=""> { if (c==NT[i]) return true; } return false; } bool isT(char c) //是否是终结符 (不包括 '$') { for (int i = 0; i < (int)strlen(t)="" -="" 1;="" i="" ++=""> { if (c == T[i]) { return true; } } return false; } 一、分析 语法分析部分我们我们采用LL （１）方法实现，采用LL （１）方法实现语法发分析要求文法满足以下要求： 一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当有右部能=*=>ε时则与其左部非终结符的后跟符号集合也有关，此外在产生式中不存在左递归，无回溯。它的基本思想是从左到右扫描源程序，同时从识别符号开始生成句子的最左推导，并只向前查看一个输入符号，便能唯一确定应选择的规则。 下面将确切地定义满足确定的自顶向下分析条件的文法即LL(1)文法及LL(1)文法的判别并介绍如何对非LL(1)文法进行等价变换问题，也就是消除一个文法中的左递归和左公共因子。 注意： 一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。 LL(1) 文法的定义（5种定义）： 一个文法符号串的开始符号集合定义如下： 定义1. 设G=(VT，VN ，S ，P) 是上下文无关文法, α是任意的文法符号串 ,FIRST(α) 是从α推导出的串的开始符号的终结符集合。。。。 FIRST(α)={a|α=*=>aβ,a ∈VT ，α, β∈V*}若α=*=>ε, 则规定ε∈FIRST(α) ． 当一个文法中相同左部非终结符的右部存在能=*=>ε的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素。为此，我们定义一个文法非终结符的后跟符号的集合如下： 定义2. 设 G=(VT，VN ，S ，P) 是上下文无关 文法，A ∈VN ，S 是开始符号 FOLLOW(A)=｛a|S=*=>μA β, 且a ∈VT ，a ∈FIRST(β), μ∈VT* ,β∈V+｝ 若S=*=>μA β, 且βε, 则#∈FOLLOW(A)。也可定义为：FOLLOW(A)={a|S=*=> …Aa …,a ∈VT} 若有S=*=> …A ，则规定#∈FOLLOW(A) 这里我们用'#'作为输入串的结束符，或称为句子括号，如：#输入串#。 定义3. 给定上下文无关文法的产生式A →α, A ∈VN, α∈V*, 若α==>ε, 则SELECT(A→α)=FIRST(α) 如果α=*=>ε，则SELECT(A→α)=FIRST(αε) ∪FOLLOW(A)。FIRST(αε) 表示FIRST(α) 的非{ε}元素。 更进一步可以看出能够使用自顶向下分析技术必须使文法满足如下条件，我们称满足条件的文法为LL(1)文法，其定义为： 定义4. 一个上下文无关文法是LL(1)文法的充分必要条件是： 对每个非终结符A 的两个不同产生式，A →α, A →β, 满足SELECT(A→α) ∩SELECT(A→β)=空, 其中α，β不同时能ε. 定义5. LL （1）文法也可定义为: 一个文法G 是LL （1）的，当且仅当对于G 的每一个非终结符A 的任何两个不同产生式 A →α|β，下面的条件成立： (1)FIRST（α）∩FIRST(β)= 空, 也就是α和β推导不出以某个相同的终结符a 为首的 符号串；它们不应该都能推出空字ε． (2)假若β=>ε那么，FIRST （α) ∩ FOLLOW （A ）＝ 空也就是，若β=>ε则α所能推出的串的首符号不应在FOLLOW(A)中。 二、算法 该程序可分为如下几步： （1）读入文法 （2）判断正误 （3）若无误，判断是否为LL(1)文法 （4）若是，构造分析表； 根据下面LL(1)文法，对输入串w: (i+i)*(i+i)+i*i进行LL(1)分析, 1、先手工建立LL(1)分析表； 2LL(1)文法G 为： E →TE ’ E ’→+TE’|ε T →FT ’ T ’→*FT’|ε F →(E)|id 分析算法： 输入：串w 和文法G 的分析表M 。 输出：如果W 属于L （G ），则输出W 的最左推导，否则报告错误。 方法：开始时，#S在分析栈中，其中S 是文法的开始符号，在栈顶；令指针ip 指向W#的第一个符号；repeat 让X 等于栈顶符号，a 为ip 所指向的符号； if X 是终结符号或# then If X=a then 把X 从栈顶弹出并使ip 指向下一个输入符号 else error() else /*X 是非终结符号*/ if M[x,a]=Xày1y2…yk then begin 从栈中弹出X ；把yk,yk-1, …,y1压入栈，y1在栈顶； 输出产生式X ày1y2…yk ；end else error() until X=# /*栈空*/ 语法分析的流程算法 三、设计目的： （1）理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现。 （2）掌握预测分析程序如何使用分析表和栈联合控制实现LL(1)分析。 四、实现环境和要求 选择实习环境为486以上CPU,4M 内存,TURBO C2.0语言. 实现程序见附录. 具体的实现要求： （1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并终止； （2）输入已知文法，由程序自动生成它的LL(1)分析表； （3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。 附录 /***************************************************** 预测分析程序（语法分析程序），分析对象为C 语言源程序文件。 该分析程序有18部分组成： 《1》首先定义各种需要用到的常量和变量； 《2》判断一个字符是否在指定字符串中； 《3》得到一个不是非终结符的符号； 《4》分解含有左递归的产生式； 《5》分解不含有左递归的产生式； 《6》读入一个文法； 《7》将单个符号或符号串并入另一符号串； 《8》求所有能直接推出^的符号； 《9》求某一符号能否推出‘ ^ ’； 《10》判断读入的文法是否正确； 《11》求单个符号的FIRST ； 《12》求各产生式右部的FIRST ； 《13》求各产生式左部的FOLLOW ； 《14》判断读入文法是否为一个LL(1)文法； 《15》构造分析表M ； 《16》总控算法； 《17》一个用户调用函数； 《18》主函数； 程序如下： #include #include #include 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) { } /******************************************* 得到一个不是非终结符的符号 ********************************************/ char c() { } /******************************************* 分解含有左递归的产生式 ********************************************/ void recur(char *point) { /*完整的产生式在point[]中*/ int j,m=0,n=3,k; char temp[20],ch; ch=c(); /*得到一个非终结符*/ k=strlen(non_ter); non_ter[k]=ch; non_ter[k+1]='\0'; for(j=0;j<=strlen(point)-1;j++)> char c='A'; c++; while(in(c,non_ter)==1) return(c); int i; if(strlen(p)==0) { } return(0); if(p[i]==c) return(1); /*若在，返回1*/ if(i==strlen(p)) return(0); /*若不在，返回0*/ for(i=0;;i++) { /*如果‘|’后的首符号和左部相同*/ } 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;" for(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;="" count++;="" left[count]="point[0];" memcpy(right[count],temp,m);="" right[count][m]="ch;" right[count][m+1]='\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++;="" }="" }="" m=""> left[count]=point[0]; memcpy(right[count],temp,m); right[count][m]='\0'; count++; } /******************************************* 读入一个文法 ********************************************/ 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("\n请输入文法的非终结符号串："); getchar(); m=0; scanf("%s",vn); i=strlen(vn); memcpy(n,vn,i); n[i]='\0'; printf("请输入文法的终结符号串："); getchar(); scanf("%s",vt); i=strlen(vt); memcpy(t,vt,i); t[i]='\0'; scanf("%c",&s); getchar(); printf("请输入文法产生式的条数："); getchar(); { } if(p[j][1]!='-'||p[j][2]!='>') { printf("\ninput error!"); return('\0'); validity=0; printf("请输入文法的第%d条（共%d条）产生式：",j,i); scanf("%s",p[j-1]); printf("请输入文法的开始符号："); scanf("%d",&i); for(j=1;j<=i;j++) getchar();="" for(j=""><> } /*检测输入错误*/ for(k=0;k<> { /*分解输入的各产生式*/ if(p[k][3]==p[k][0]) recur(p[k]); } /******************************************* 将单个符号或符号串并入另一符号串 ********************************************/ void merge(char *d,char *s,int type) { /*d是目标符号串，s 是源串，type ＝1，源串中的‘ ^ ’一并并入目串； type ＝2，源串中的‘ ^ ’不并入目串*/ for(i=0;i<=strlen(s)-1;i++)> int i,j; } return(s); else non_re(p[k]); if(type==2&&s[i]=='^') } /******************************************* 求所有能直接推出^的符号 ********************************************/ void emp(char c) { /*即求所有由‘ ^ ’推出的符号*/ } /******************************************* 求某一符号能否推出‘ ^ ’ ********************************************/ int _emp(char c) { /*若能推出，返回1；否则，返回0*/ int i,j,k,result=1,mark=0; char temp[20]; temp[0]=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]);="" }="" else="" {="" }="" for(j="0;;j++)" {=""> temp[1]='\0'; merge(empt,temp,1); if(in(c,empty)==1) { if(i==count) if(left[i]==c) /*找一个左部为c 的产生式*/ { if(j==1&&in(right[i][0],empty)==1) return(1); else if(j==1&&in(right[i][0],termin)==1) else { return(0); return(1); for(i=0;;i++) return(0); j=strlen(right[i]); /*j为右部的长度*/ for(k=0;k<> if(in(right[i][k],empt)==1) } /******************************************* 判断读入的文法是否正确 ********************************************/ int judge() } } } continue; return(1); 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);="" mark="1;" if(mark="=1)" continue;="" {="" if(result=""> int i,j; } /******************************************* 求单个符号的FIRST ********************************************/ void first2(int i) { /*i为符号在所有输入符号中的序号*/ char c,temp[20]; int j,k,m; c=v[i]; char ch='^'; emp(ch); if(in(c,termin)==1) /*若为终结符*/ for(i=0;i<=count-1;i++) {="" }="" return(1);="" if(in(left[i],non_ter)="=0)" {="" 若左部不在非终结符中，报错*/="" }="" for(j=""><=strlen(right[i])-1;j++) {="" }="" if(in(right[i][j],non_ter)="=0&&in(right[i][j],termin)==0&&right[i][j]!='^')" {="" 若右部某一符号不在非终结符、终结符中且不为‘="" ^="" ’，报错*/="" }="" printf("\nerror2!");="" validity="0;" return(0);="" printf("\nerror1!");="" validity="0;"> { 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]=""> if(in(right[j][0],termin)==1||right[j][0]=='^') } temp[1]='\0'; } else if(in(right[j][0],non_ter)==1) { } if(right[j][0]==c) { } merge(first1[i],first1[k],2); { } empt[0]='\0'; if(_emp(right[j][k])==1&&k } /******************************************* 求各产生式右部的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]=='^') } else { for(j=0;;j++) { 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'; if(v[j]==p[0]) break; if(i>=0) first[i][0]='^'; first[i][1]='\0'; } else { } TEMP[0]='^'; TEMP[1]='\0'; } f[i]='1'; { { if(i>=0) } } /******************************************* 求各产生式左部的FOLLOW ********************************************/ void FOLLOW(int i) { int j,k,m,n,result=1; else /*如果右部为符号串*/ { } for(j=0;;j++) if(v[j]==p[0]) break; if(i>=0) else { } empt[0]='\0'; if(_emp(p[k])==1&&k c=non_ter[i]; /*c为待求的非终结符*/ temp[0]=c; temp[1]='\0'; merge(fo,temp,1); if(c==start) { /*若为开始符号*/ } { if(in(c,right[j])==1) /*找一个右部含有c 的产生式*/ { for(k=0;;k++) if(right[j][k]==c) break; /*k为c 在该产生式右部的序号*/ temp[0]='#'; temp[1]='\0'; merge(follow[i],temp,1); for(j=0;j<=count-1;j++) for(m="0;;m++)" if(v[m]="=left[j])" break;="" m为产生式左部非终结符在所有符号中的序号*/="" if(k="=strlen(right[j])-1)" {="" 如果c="" 在产生式右部的最后*/="" }="" else="" {="" 如果c="" 不在产生式右部的最后*/="" for(n=""><=strlen(right[j])-1;n++) {="" }="" if(result="=1)" {="" 如果右部c=""> empt[0]='\0'; result*=_emp(right[j][n]); if(in(v[m],fo)==1) { merge(follow[i],follow[m],1); continue; } if(F[m]=='0') { } merge(follow[i],follow[m],1); FOLLOW(m); F[m]='1'; if(in(v[m],fo)==1) } /******************************************* 判断读入文法是否为一个LL(1)文法 ********************************************/ int ll1() { int i,j,length,result=1; char temp[50]; for(j=0;j<=49;j++) {="" }="" for(j=""><=strlen(v)-1;j++) first2(j);="" 求单个符号的first="" 集合*/=""> /*初始化*/ first[j][0]='\0'; first1[j][0]='\0'; select[j][0]='\0'; TEMP[j]='\0'; temp[j]='\0'; f[j]='0'; F[j]='0'; } F[i]='1'; } } } for(n=k+1;n<=strlen(right[j])-1;n++) temp[strlen(right[j])-k-1]='\0' ;="" first(-1,temp);="" merge(follow[i],temp,2);="" {="" 避免循环递归*/="" }="" if(f[m]="='0')" {="" follow(m);="" f[m]='1' ;="" }="" merge(follow[i],follow[m],1);="" continue;="" merge(follow[i],follow[m],1);="" temp[n-k-1]="right[j][n];" follow[j][0]='\0'> printf("%c:%s ",v[j],first1[j]); printf("\nempty:%s",empty); printf("\n:::\n_emp:"); for(j=0;j<=strlen(v)-1;j++) for(i=""><=count-1;i++) first(i,right[i]);="" 求first*/="" printf("\n");="" for(j=""><=strlen(non_ter)-1;j++) if(fo[j]="=0)" {="" }="" fo[0]='\0' ;="" follow(j);="" printf("%d="" ",_emp(v[j]));="" {="" 求follow*/="" }="" printf("\nfirst:");="" for(i=""><=count-1;i++) printf("%s="" ",first[i]);="" printf("\nfollow:");="" printf("%s="" ",follow[i]);="" for(i=""><=count-1;i++) {="" 求每一产生式的select="" 集合*/="" for(i=""><=strlen(non_ter)-1;i++)> select[i][strlen(first[i])]='\0'; } 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(j=0;j<=strlen(right[i])-1;j++) {="" }="" result*="_emp(right[i][j]);" result="1;" for(j="0;;j++)" if(v[j]="=left[i])" break;="" if(strlen(right[i])="=1&&right[i][0]=='^')" if(result="=1)"> } /******************************************* 构造分析表M ********************************************/ void MM() { int i,j,k,m; for(i=0;i<=19;i++) for(j=""><=19;j++) m[i][j]="-1;" {="" 判断输入文法是否为ll(1)文法*/="" }="" return(1);="" if(left[i]="=left[i-1])" {="" }="" else="" {="" }="" temp[0]='\0' ;="" temp[strlen(select[i])]='\0' ;="" memcpy(temp,select[i],strlen(select[i]));="" merge(temp,select[i],1);=""> i=strlen(termin); termin[i]='#'; /*将#加入终结符数组*/ termin[i+1]='\0'; for(i=0;i<=count-1;i++) {="" {="" if(in(select[i][j],termin)="=1)" {="" for(k="0;;k++)" if(termin[k]="=select[i][j])" break;="" k为产生式右部终结符的序号*/="" if(non_ter[m]="=left[i])" break;="" m为产生式左部非终结符的序号*/="" for(m="0;;m++)" for(j=""><=strlen(select[i])-1;j++) m[m][k]=""> } /******************************************* 总控算法 ********************************************/ void syntax() { int i,j,k,m,n,p,q; char S[50],str[50]; 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]; { if(in(S[strlen(S)-1],termin)==1) { { } else if(S[strlen(S)-1]=='#') { printf("\n该符号串不是文法的句型！"); char ch; printf("请输入该文法的句型："); } } while(1) if(S[strlen(S)-1]!=ch) return; printf("\n该符号串是文法的句型."); return; } else { } j++; ch=str[j]; S[strlen(S)-1]='\0'; else { { } if(M[i][k]==-1) { } else { printf("\n语法错误！"); return; if(non_ter[i]==S[strlen(S)-1]) if(termin[k]==ch) { } printf("\n词法错误！"); return; break; if(k==strlen(termin)) break; for(i=0;;i++) for(k=0;;k++) m=M[i][k]; if(right[m][0]=='^') } /******************************************* } } for(p=j;p<=strlen(str)-1;p++) printf("%c",str[p]);="" printf("="" ");="" }="" else="" {="" p="strlen(S)-1;" q="p;" for(n="strlen(right[m])-1;n">=0;n--) S[q+strlen(right[m])]='\0'; } S[strlen(S)-1]='\0'; S[p++]=right[m][n]; printf("\nS:%s str:",S); 一个用户调用函数 ********************************************/ void menu() { } /******************************************* 主函数 ********************************************/ void main() { int i,j; start=grammer(termin,non_ter,left,right); /*读入一个文法*/ printf("\nstart:%c",start); strcpy(v,non_ter); strcat(v,termin); printf("\nv:%s",v); printf("\nnon_ter:%s",non_ter); printf("\nright:"); for(i=0;i<=count-1;i++) printf("%s="" ",right[i]);="" for(i=""><=count-1;i++) printf("%c="" ",left[i]);="" syntax();="" printf("\n是否继续？(y="" or="" n):");="" scanf("%c",&choose);="" getchar();="" while(choose="='y')" {="" }="" menu();="" printf("count="%d",count);" printf("\ntermin:%s",termin);="" printf("\nleft:");="" if(validity="=1)" validity="judge();" printf("\nvalidity="%d",validity);" if(validity="=1)" {="" ll="ll1();" printf("\nll="%d",ll);" if(ll=""> 21 printf("\n文法有效"); 编译原理实验报告 } } else { MM(); for(i=0;i<=19;i++) for(j=""><=19;j++) if(m[i][j]="">=0) printf("M[%d][%d]=%d ",i,j,M[i][j]); printf("\n该文法不是一个LL1文法！"); printf("\n"); printf("\n"); menu(); } 5. 执行结果 （1）输入一个文法 （2）输入一个符号串 编译原理实验报告 22 （3）再次输入一个符号串，然后退出程序 编译原理实验报告 23 CMA P1 中文课程 线性回归分析法 主讲老师：Kroos ? 计算简单回归方程的回归结果（高低点法） ? 理解回归方程以及与回归方程相关的量度指标； ? 理解回归分析在什么情况下是一种合适的预测工具； 线性回归 是利用数理统计中的回归分析，来确定两种或两种以上变数间相互依赖的定量关系的一种统计分析方法之一，通过大量历史数据进行分析得到的回归分析方程，通过对未来各种可能性的预测得到未来的价值，分为： 简单线性回归（Y=a+bX）； 多元线性回归（Y=a+b1X1+b2X2+b3X3+……）； Y=7.5X+570 ? 相关系数 R 范围 -1~1，代表了两个变量之间的相关程度，相关性越强，相关系数的绝对数越大 ? 完全正相关 R=1 (成本与直接人工） ? 完全负相关 R=-1（事故与安全培训次数） ? 完全不相关 R=0 （头发长短与收入水平） ? 决定系数 R2 衡量回归模式的吻合度，衡量在因变量的总变化中，有多少比例是可以由自变量来解释的 范围0~1 ? T 值 ? 标准差 SE R= 0.99861 R2= 0.99724 三个使用前提： ? 在相关范围内有效 ? 假定过去的关系在未来也是有效的 ? 其他条件不变假设 一公司已经收集了过去24 个月的数据以确定是否存在一因变量，可以用来估计送货费用。正在考虑的3 个可能的因变量是送货数量、送货里程和送货重量。应用来确定这些因变量是否能为送货成本提供有效估计的定量技术是： A. 弹性预算法 B. 线性规划法 C. 线性回归 D. 可变成本法 答案：C Dawson 制造公司开发了如下的多元回归等式，利用多年的数据，并用该等式估计其产品的本： 成本= FC + a*L + b*M 其中， FC = 固定成本 L = 每小时工资率 M = 每磅材料成本 下列哪项变动对验证该模型的结果无效影响最大？ A. 工厂间接费用显著减少，工厂间接费用是固定成本的一部分 B. 重新谈判工会合同，要求更高的工资率 C. 由于从国外购买材料，材料成本显著下降 D. 劳动力生产率显著变动 答案：D 为了用广告费用的函数分析销售，Smith 公司的销售经理开发了简单回归模型。该模型如下所示，它是根据观察32 个月销售和广告费用的结果得出的， 相关系数为0.90 S = 10,000 美元+ 2.50A 美元S = 销售收入 A = 广告费用 如果Smith 公司某月的广告费用为1,000 美元，销售收入的相关点估计为： A. 2,500 美元 B. 11,250 美元 C. 12,250 美元 D. 12,500 美元 答案：D 让我们一起为明天拼搏…… 感谢您选择高顿网校. 本章结束！ 课 程 设 计 书 目 录 一、设计内容·····························································1 二、目的与基本要求·······················································1 三、语法分析器的功能·····················································1 四、算法分析····················································1 4.1相关理论介绍········································1 4.2设计原理····················································2 4.3构造LL(1)分析表·································3 4.4利用分析表进行预测分析的步骤······························5 4.5···································6 五、流程框图·················································6 六、函数相关说明··············································8 七、参考程序清单·············································8 八、程序运行结果···········································17 九、使用方法·················································19 十、····················································20 ···························································20 课 程 设 计 书 语 法 分 析 器 —预测分析法 一、设计内容 用预测分析法（即LL （1）分析法）构造文法G[E]： E → E + T | T T → T * F | F F → ( E ) | i | x | y 的预测分析程序（即语法分析器）。 二、目的与基本要求 1析的条件。 2、学会用C/C++LL （1）分析法的语法分析器； 3 4.1相关理论介绍 语法分析是编译过程的核心部分。语法分析的任务就是识别词法分析程序输出的单词序列是否为给定方法的正确句子，并确定其语法结构。尽管目前已提出很多语法分析方法，但总体上语法分析的方法可分为两大类：自顶向下的分析方法和自底向上的分析方法。 课 程 设 计 书 自底向上的分析方法就是归约的方法，即从待分析符号串出发，从底向上构造语法树，若能够造至树根（能够归约到方法开始符号），则表示该符号串是方法的句子。 自顶向下的分析法其实就是推导的方法，也就是从方法的开始符号出发，试图向下构造待分析符号串的语法树，若语法的叶结点可以构成该符号串（能够推导出该符号串），则表示这个符号串是方法的句子。自顶向下的分析方法又分为：带回溯的自顶向下分析方法和确定的自顶向下分析方法。一个文法如果要能进行确定的自顶向下分析，必须满足什么条件呢？ 由可选集的定义可知，规则A →x 的可选集SELECT （A →x 推导出的下一个终结符号的集合。因此利用SELECT 据当前输入的符号有目的的选择产生式。 U →X i ）(i=1,2,3,?,n ) ，求可选集。这样，U ，待输入符号为a, 且a ∈SELECT （U →X i 一定能推导出等输入符号a 。 a ?SELECT （U (,n,i ≠j ) 。 一个非终结符A A x 1 |x2|?|xn ,满足SELECT （A →x i ）?SELECT(A→x j )=φ?，即同一个非终结符各规则的SELECT 集两两不相交。 LL （1）分析法等, 下面详细介绍预测，的相关理论，分析表构造，预测分析过程。 4.2设计原理 所谓LL （1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL （1）分析的程序又称为LL （1）分析程序或LL （1）分析器。 我们知道一个文法要能进行LL （1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST 和 课 程 设 计 书 FOLLOW 集合，然后根据FIRST 和FOLLOW 集合构造LL （1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL （1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C++语言来编写，其逻辑结构图如下： 的 4.3 构造LL(1)分析表 考查文法G[E]： E →E+T | T T →T*F | F F →( E ) | i | x | y 课 程 设 计 书 我们容易看出此文法没有左公因子也没有二义性，但却存在两个直接左递归，这里我们利用引入新非终结符的方法来消除它使方法满足要求，即： 对形如：U →Ux|y的产生式（其中x,y ∈V + ，y 不以U 开头），引入一个新的非终结符U ’后，可以等价地改写成为： U →yU ’ U ’→x U’|ε 显然改写后，U 和U ’都不是左递归的非终结符。因此文法G ［E 归后可等价地写成： E →TP P→+TP | ε T→FQ Q→*FQ | ε F →( E ) | i | x | y 在构造LL(1)FIRST 和FOLLOW ①FIRST 集合的构造算法： （1）若X ∈V T ，则FIRST （（2）若X ∈V N X a 加入到FIRST(X)中；若X →ε也是一条产生式，则把ε（3）若X →Y V N ，则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若Y 1Y 2k Y 1，?，Y i-1都是非终结符，而且，对于任何j ，1≤j ≤j ε（即Y 1?Y i-1*?ε），则把FIRST(Yj ) 中的所有非ε-FIRST(Yj ) 均含有ε，j=1,2,?，k ，则把ε加到FIRST 不再增大为止。 S ，置#于FOLLOW(S)中； （2）若→αB β是一个产生式，则把FIRST(β)| {ε}加至FOLLOW(B)中； （3）若A →αB 是一个产生式，或A →αB β是一个产生式而β?ε（即ε∈FIRST(β) ），则把FOLLOW(A)加至FOLLOW(B)中。 连续使用上面的规则，直至每个集合FOLLOW 不再增大为止。 根据以上描述的算法，可以构造文法G ［E ］的FIRST 和FOLLOW 集合如下： FIRST(E) = {( , i，x ，y } FOLLOW(E) = { ) , # } 课 程 设 计 书 FIRST(P) = { + ,ε} FIRST(T) = { ( , i，x ，y } FIRST(Q) = { * , ε} FIRST(F) = { ( , i，x ，y } FOLLOW(P) = { ) , # } FOLLOW(T) = { + , ) , # } FOLLOW(Q) = { + , ) , # } FOLLOW(F) = { * , + , ) , # } 现在来构造G ［E ］的LL （1）预测分析表。预测分析表M[A, a]是如下形式的一个矩阵。A 为非终结符，a 是终结符或‘#’。矩阵元素 M[A, a]中存放这一条关于A 的产 课 程 设 计 书 4.5预测分析程序的总控程序的算法描述 实现LL(1)的一种有效方法是使用一张分析表和一个栈进行联合控制。如果前面已经设计好了分析表和栈的话，那么现在就开始具体实现这个LL(1)LL(1)分析程序的算法的描述如下： BEGIN 首先把‘#’然后把文法开始符号推进STACK 分析栈； 把第一个输入符号读进a ； FLAG = TURE; WHILE FLAG DO BEGIN 把STACK IF X∈V T THEN a ELSE ‘ →X 1X 2??X k } THEN 把X k-1X 1，一一推进STACK 栈 若1X k = ε，不推进什么进栈 */ 分析成功 */ 五、流程框图 课 程 设 计 书 课 程 设 计 书 六、函数相关说明 分析栈可以采取许多的存储方法来设计，在这里采用的顺序栈。这里定义了一个类Stack ，将所有对栈的操作封装在Stack 类中，作为它的成员函数。 根据预测分析器模型，LL(1)分析器的实现关键在于分析栈和分析表是采用何种数据结构来实现。分析表是一个矩阵，当我们要调用分析表来分析时，就根据栈顶的非终结符和当前输入的终结符来决定执行哪种过程。具体设计思想如下： //声明：每个Event 执行一个特定的进栈处理，Error 将抛出错误 void Event1(); void Event2(); void Event3(); void Event4(); void Event5(); void Event6(); void Event7(); void Error(); typedef void (*Action)(); // }; #if !defined(AFX_STACK_H__AA8994AF_8B3A_477C_A4CC_6F18499CA9BE__INCLUDED_) #define AFX_STACK_H__AA8994AF_8B3A_477C_A4CC_6F18499CA9BE__INCLUDED_ #if _MSC_VER > 1000 #pragma once 课 程 设 计 书 #endif // _MSC_VER > 1000 class Stack { public: Stack(); ~Stack(); void push(char token); char pop(); bool isEmpty(); private: char *_stack; int _top; int _bottom; }; #endif // D_) // stack // Construction/Destruction Stack::Stack() { _stack=new char [InitStackSize]; _top=_bottom=-1; 课 程 设 计 书 } Stack::~Stack() { _top=_bottom=-1; delete _stack; } // Attributes void Stack::push(char token) { if(_top>=InitStackSize-1) { exit(1); } _top++; _stack[_top]=token; } { { } } bool Stack::isEmpty() { if(_top==_bottom) return true; else 课 程 设 计 书 return false; } // 分析表的构造 #include "Stack.h" #include using namespace std; const int NonterminalNum=5; //非终结符个数 const int TerminalNum=7; //终结符个数 char nonterminal[]={'E', 'P', 'T', 'Q','F'}; // 定义终结符 Stack stack; // 事件描述与LL （1）分析表 void Event1(); void Event2(); void Event3(); void Event4(); void Event5(); void Event6(); {Event4, Error, Error, Event4, Error, Error}, {Error, Event3, Event5, Error, Event3, Event3}, {Event6, Error, Error, Event7, Error, Error} }; // 定义事件 课 程 设 计 书 void Event1() { stack.push('P'); stack.push('T'); }; void Event2() { stack.push('P'); stack.push('T'); stack.push('+'); }; void Event3() { }; void Event4() { stack.push('Q'); }; { void Event6() { stack.push('i'); stack.push('x'); stack.push('y'); }; 课 程 设 计 书 void Event7() { stack.push(')'); stack.push('E'); stack.push('('); }; // 出错处理 void Error() { cerr<<"---------------------分析失败 exit(1);=""> // 判断 Token bool isVt(char ch) { { // 字符串入 Stack 分析栈 void pushTogether(char nonterminal, char terminal) { switch(nonterminal) { 课 程 设 计 书 case 'E': switch(terminal) { case 'i': ParseTable[4][0](); break; case 'x': ParseTable[4][1](); break; case 'y': ParseTable[4][2](); break; case '+': ParseTable[4][3](); break; case '*': ParseTable[4][4](); break; case '(': ParseTable[4][5](); break; case ')': ParseTable[4][6](); break; case '#': ParseTable[4][7](); break; default: break; } break; case 'P': switch(terminal) { case 'i': case 'x': case 'y': switch(terminal) { case 'i': ParseTable[4][0](); break; case 'x': ParseTable[4][1](); break; case 'y': ParseTable[4][2](); break; case '+': ParseTable[4][3](); break; case '*': ParseTable[4][4](); break; 课 程 设 计 书 case '(': case ')': case '#': default: } break; ParseTable[4][5](); break; ParseTable[4][6](); break; ParseTable[4][7](); break; break; case 'Q': switch(terminal) { case 'i': ParseTable[4][0](); break; case 'x': ParseTable[4][1](); break; case 'y': ParseTable[4][2](); break; case '+': case '*': case '(': case ')': case '#': default: break; } break; case 'F': { ParseTable[4][2](); break; ParseTable[4][3](); break; ParseTable[4][4](); break; ParseTable[4][5](); break; case ')': ParseTable[4][6](); break; case '#': ParseTable[4][7](); break; default: break; } break; default: 课 程 设 计 书 Error(); break; } } // LL（1）分析程序 #include using namespace std; void LL1Parse() { stack.push('#'); stack.push('E'); char a; cout<<"请输入一字符串以# a="getchar();" bool="" flag="true;" while(flag)=""> { //match Error(); { if(X==a) //parse successfully flag=false; else Error(); } else //reverse, push into stack 课 程 设 计 书 pushTogether(X, a); } if(stack.isEmpty()) cout<> // 主程序 #include cout<<"\t\t文结构结构如下:\n";><<"\t\t\t> cout<<"\t\t\t p→+tp｜ε\n";=""><<"\t\t\t> cout<<"\t\t\t> cout<<"\t\t\t f→(e)｜i="" ｜=""> i+i*i#, 显示“分析成功”。 课 程 设 计 书 显示“分析失败！”。运行结果如下： 课 程 设 计 书 九、使用方法 程序在VC++6.0下调试通过。打开VC6.0执行“文件”—>“新建”, 编辑上面的源程序，完成后单击“保存”（aa.cpp ），再单击菜单栏的“编译”—>“编译 aa.cpp”或按Ctrl+F7；“编译”—>“构件 aa.exe”或按F7；“编译”—>“执行 aa.exe”或按Ctrl+F5。 当然你也可以找aa.cpp 文件所在目录的“debug 目录”aa.exe, 拷贝到别的目录下面再在DOS 下来执行它。这里我把它拷到“然后执行“Win+R”，输入“CMD ”进入DOS, 接着执行“cd\”C:\录，再执行aa 回车。如下图： 课 程 设 计 书 十、课程设计心得 本次课程设计完成了语法分析器-预测分析法（即LL （1）分析法）的算法分析到实现的全部过程，结果满足设计要求，验证无误。在整整一个星期的日子里同时做两个课程设计，可以说是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课刻，掌握得不够牢固等等。 经努力过。 ［1. 重庆大学出版社，2005年8月。 ［2语言程序设计. 清华大学出版社，2005年月1月。 《编译原理》课程设计—预测分析法LL （1） 第21页范文二：预测分析法代码
范文三：实验3预测分析法
范文四：24.预测技术-线性回归分析法
范文五：编译原理 预测分析法实验
