实验3预测分析法模板

1、实验三一、分析语法分析部分我们我们采用 LL ( 1)方法实现，采用 LL ( 1)方法实现语法发分析要 求文法满足以下要求：一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号 集合有关，当有右部能=*= 时则与其左部非终结符的后跟符号集合也有关，此外在产生 式中不存在左递归， 无回溯。它的基本思想是从左到右扫描源程序，同时从识别符号开始生成句子的最左推导，并只向前查看一个输入符号，便能唯一确定应选择的规则。下面将确切地定义满足确定的自顶向下分析条件的文法即LL(1)文法及LL(1)文法的判别并介绍如何对非LL(1)文法进行等价变换问题，也就是消除一个文法中的左递归和左

2、公共 因子。注意：一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。 然而，某些含有左递归和左公共因子的文法在通过等价 变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是 LL(1)文法的必要条件。LL(1)文法的定义(5种定义)：一个文法符号串的开始符号集合定义如下：定义1.设G=(VT , VN , S, P)是上下文无关文法，a是任意的文法符号串,FIRST( a )是从a推导出的串的开始符号的终结符集合。= ，则规定 FIRST( a ).的情况则必须知道该

3、非终结符的 为此，我们定义一个文法非终结FIRST( a )=a| a =*=a 3 ,a VT , a ,3 V*若 a当一个文法中相同左部非终结符的右部存在能=后跟符号的集合中是否含有其它右部开始符号集合的元素。 符的后跟符号的集合如下：定义2.设G=(VT , VN , S, P)是上下文无关 文法，A VN , S是开始符号FOLLOW(A)= a|S=*= 卩 A 3 且 a VT , a FIRST( 3 ),卩 若S=*=卩A 3，且3 ,则# FOLLOW(A) o也可定义为：Aa ,a VT若有S=*=A，则规定# FOLLOW(A)这里我们用#作为输入串的结束符，或称为句子

4、括号，如：定义3.给定上下文无关文法的产生式A T aSELECT(A T a )=FIRST( a )如果 a =*= ，贝U SELECT(A t a )=FIRST( a ) U FOLLOW(A) FIRST( a )的非 元素。更进一步可以看出能够使用自顶向下分析技术必须使文法满足如下条件， 件的文法为LL(1)文法，其定义为：定义4. 一个上下文无关文法是 LL(1)文法的充分必要条件是： 对每个非终结符A的两个不同产生式，SELECT(A T 3 )=空，其中a , 3不同时能 .定义5. LL (1)文法也可定义为：一个文法G是LL (1)的，当且仅当对于式AT a |3，下面

5、的条件成立：(1)FIRST ( a)n FIRST( 3 )=空,也就是= VT* , 3 V+ FOLLOW(A)=a|S=*=#输入串#O,A VN, a V*,若 a= ,则O FIRST( a )表示我们称满足条SELECT(A Ta ) AG的每一个非终结符 A的任何两个不同产生a和3推导不出以某个相同的终结符a为首的符号串；它们不应该都能推出空字 .假若B = 那么，FIRST ( a )n FOLLOW (A)=空也就是，若3 = 则a所能 推出的串的首符号不应在 FOLLOW(A)中。二、算法该程序可分为如下几步：(1) 读入文法(2) 判断正误(3) 若无误，判断是否为LL

6、(1)文法(4) 若是，构造分析表；根据下面1、先手工建立LL(1)分析表；2、分析输入串，判断是否是语法上正确的句子，并输出整个分析过程。LL(1)文法G为：EETTFLL(1)文法，对输入串W： (i+i)*(i+i)+i*i 进行LL(1)分析，要求如下F判断句型1F是LL(1)文法?结束报错7 TE7+TE |7 FT7 *FT |7 (E)|id编译原理实验报告3分析算法： 输入：串W和文法G的分析表M。输出：如果 W属于L ( G),则输出W的最左推导，否则报告错误。方法：开始时，#S在分析栈中，其中S是文法的开始符号，在栈顶；令指针 ip指向W#的第一个符号；rep eat让X等

7、于栈顶符号，a为ip所指向的符号；if X 是终结符号或# thenIf X=a then把X从栈顶弹出并使ip指向下一个输入符号else error()else /*X是非终结符号*/cy1y2 yk the n beginX ;把yk,yk-1,y1压入栈，y1在栈顶;X cy1y2 yk ； endif Mx,a=X从栈中弹出输出产生式else error() un til X=#/*栈空*/三、设计目的：(1) 理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析 表的构造及分析过程的实现。LL(1)分析。(2) 掌握预测分析程序如何使用分析表和栈联

8、合控制实现四、实现环境和要求选择实习环境为 486以上CPU,4M内存,TURBO C2.0语言.实现程序见附录. 具体的实现要求：(1) 对输入文法，它能判断是否为LL(1)文法，若是，则转(2);否则报错并终止;(2) 输入已知文法，由程序自动生成它的LL(1)分析表；实验三for(j=0;j#includevstdio.h#includeint count=0;int number;/*分解的产生式的个数*/*所有终结符和非终结符的总数*/char start;/*开始符号*/char termin50;char non_ter50;/*终结符号*/*非终结符号*/char v50;/*

9、所有符号*/char left50;char right5050;/*左部*/*右部*/char first5050,follow5050;/*所有单个符号的FIRST集合*/*各产生式右部的 FIRST和左部的FOLLOW 集合*/char first15050;char select5050;/*各单个产生式的 SELECT集合*/char f50,F50;/*记录各符号的 FIRST和FOLLOW 是否已求过*/char emp ty20;/*记录可直接推出A的符号*/char TEMP 50;int validity=1;/*求FOLLOW时存放某一符号串的 FIRST集合*/*表示输

10、入文法是否有效*/int ll=1;/*表示输入文法是否为LL(1)文法*/int M2020;/*分析表*/char choose;/*用户输入时使用*/char emp t20;/*求_emp()时使用*/char fo20;/*求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*/*得到一个不是非终结符的符号*/ cha

11、r c()char c=A;while(in(c,non_ter)=1)c+;return(c);/*分解含有左递归的产生式*/ void recur(char *po int)/*完整的产生式在point中*/int j,m=0,n=3,k;char temp 20,ch;ch=c();/*得到一个非终结符*/k=strlen(non_ter);non_terk=ch;non_terk+1=0;if(po intn=po intO)/*如果 I后的首符号和左部相同*/for(j=n+1;jv=strlen (po int)-1;j+)while( pointj!=T&p ointj!=、O)

12、temp m+=po intj+;leftcount=ch;meme py (nghtcount,te mp, m);rightcountm=ch;rightcountm+1=0;m=0;count+;if(p ointj=T)n=j+1;break;else/*如果 r后的首符号和左部不同*/leftcount=ch;rightcountO=A;rightcount1=O;count+;for(j=n;jv=strlen (po int)-1;j+)if(po intj!=T)temp m+=p ointj;elseleftcount=p ointO;memc py (nghtcount,t

13、e mp, m);rightcountm=ch;rightcountm+1=0;p rintf( count=%d ,count);m=0;count+;leftcount=pointO;memc py (nghtcount,te mp, m); rightcountm=ch;rightcountm+1=0;实验三count+;m=0;/*分解不含有左递归的产生式*/ void non_re(char *po int)int m=0,j;char temp 20;for(j=3;jv=strlen (po int)-1;j+)if(p ointj!=T)temp m+=p ointj;else

14、leftcount=point0;memc py (nghtcount,te mp, m);rightcountm=0;m=0;count+;leftcount=point0;memc py (nghtcount,te mp, m);rightcountm=0;count+;m=0;/*读入一个文法*/ char grammer(char *t,char *n,char *left,char right5050)char vn50,vt50;char s;char p5050;int i,j,k;printf（n请输入文法的非终结符号串：）;scanf(%s,vn);getchar();i=s

15、trlen(vn);编译原理实验报告9实验三for(i=0;iv=strlen(s)-1;i+)编译原理实验报告11meme py( n,vn,i);ni=0;printf(请输入文法的终结符号串:)；scanf(%s,vt);getchar();i=strlen(vt);meme py(t,vt,i);ti=0;printf(请输入文法的开始符号:)；seanf(%e, &s);getchar();printf(请输入文法产生式的条数:)；scanf(%d,&i);getcharO;for(j=1;jv=i;j+)printf(请输入文法的第 %d条(共%d条)产生式:,j,i);scanf

16、(%s, pj-1);getcharO;for(j=0;jv=i-1;j+)if(p j1!=-ll Pj【2!=)p rintf(n input error!);validity=0;return(0);/*检测输入错误*/for(k=0;kv=i-1;k+)/*分解输入的各产生式*/if(P k3=pk0)recur( pk);elsenon_re( pk);return(s);/*将单个符号或符号串并入另一符号串*/void merge(char *d,char *s,int type)/*d是目标符号串，s是源串，type= 1, type=2,源串中的A 不并入目串源串中的A 并并入

17、目串;*/int i,j;实验三if(typ e=2&si=A)elsefor(j=0;j+)if(jstrlen(d)&si=dj)break;if(j=strlen(d)dj=si;dj+1=0;break;/*求所有能直接推出A的符号*/ void emp( char c)/*即求所有由A 推出的符号*/char temp 10;int i;for(i=0;i=count-1;i+)if(righti0=c&strlen(righti)=1)tem p 0=lefti;te mp 1=、0;merge(e mp ty,te mp ,1);emp (lefti);/*求某一符号能否推出*/

18、 int _emp( char c)/*若能推出，返回1;否则，返回0*/int i,j,k,result=1,mark=0;char temp 20;tem p 0=c;编译原理实验报告15tem p1=、0;merge(e mp t,te mp ,1);if(in(c,em pty)=1)retum(1);for(i=0;i+)if(i=count)retum(0);if(lefti=c)/*找一个左部为c的产生式*/j=strlen(righti);/*j为右部的长度*/if(j=1 &in(righti0,e mp ty)=1)retum(1);else if(j=1 &i n(rig

19、hti0,termin)=1)retum(0);elsefor(k=0;kv=j-1;k+)if(in(righ tik,em pt)=1)mark=1;if(mark=1)continue;elsefor(k=0;k=j-1;k+)result*=_em p(rightik);tem p 0=rightik;te mp 1=、0;merge(e mp t,te mp ,1);if(result=0&ivcount)continue;else if(result=1 &i vcount)return(1);/*判断读入的文法是否正确*/ int judge()int i,j;for(i=0;i

20、v=count-1;i+)if(in(lefti,non_ter)=0)/*若左部不在非终结符中，报错*/p rintf(nerror1!);validity=0;retum(0);for(j=0；jv=strlen(righti)-1;j+)retum(1);if(in(rightij,non_ter)=0&in(righ tij,termin)=0&righ ti j!=A)/*若右部某一符号不在非终结符、终结符中且不为A ,报错*/p rintf(nerror2!);validity=0;retum(0);/*求单个符号的 FIRST*/void first2(int i)/*i为符号在

21、所有输入符号中的序号*/char c,te mp 20;int j,k,m;c=vi;char ch=A;emp (ch);if(in(c,termin)=1)/*若为终结符*/first1i0=c;first1i1=0;else if(in(c,non_ter)=1)/*若为非终结符*/for(j=0;j|eaiqX L-dLue 二二 l4sEe6eLUvp-2d专宀命一亘 I4S一二二 l4sEe6g二-言壬)剁S匸(D+兰-=茎6出巨)一(+uroMLU)OJ言盒(+K L 丄-mwEueESHVKO 艾)0命 2I4S一二二 l4sEe6g(Ogg-|eaiq(-0=茎6匸丄兰壬(+

22、圭0艾)0-enuRUOO(。“出0=茎6吕一(LMM(euouo=mug)uw as忑X L-dLue 二二 l4sEe6eLUJo=m 吕斤实验三fi=1;/*求各产生式右部的 FIRST */ void FIRST(int i,char *p)int length;int j,k,m;char temp 20;length=strlen (p);编译原理实验报告21if(length=1)/*如果右部为单个符号*/if(p 0=)if(i=0)firsti0=A;firsti1=0;elseTEM P 0=A;TEMP 1=、0;elsefor(j=0;j+)if(vj=P0)break

23、;if(i=0)memc py(firs ti ,first1j,strlen(first1j);firstistrlen(first1j)=0;elsememc py(TEMP ,first1j,strlen(first1j);TEMP strlen(first1j)=、0;else/*如果右部为符号串*/for(j=0;j+)if(vj=P 0)break;merge(firsti,first1j,2);elsemerge (TEMP ,first1j,2);for(k=0;kv=length-1;k+)emp t0=0;if(_emp(p k)=1 &k=0)merge(firsti,f

24、irst1m,2);elsemerge (TEMP ,first1m,2);else if(_emp(p k)=1 &k=length-1)tem p 0=A;temp 1=、0;if(i=0)merge(firsti,tem p,1);elsemerge (TEMP ,tem p,1);else if(_e mp(p k)=0)break;/*求各产生式左部的 FOLLOW */ void FOLLOW(int i)int j,k,m,n,result=1;char c,te mp 20;c=non_teri;/*c为待求的非终结符*/tem p 0=c;temp1=0; merge(fo,

25、te mp ,1);if(c=start)/*若为开始符号*/tem p 0=#;temp 1=、0;merge(followi,te mp ,1);for(j=0;jv=count-1;j+)if(in(c,rightj)=1)/*找一个右部含有c的产生式*/for(k=0;k+)if(rightjk=c)break;/*k为c在该产生式右部的序号*/for(m=0;m+)if(vm=leftj)break;/*m为产生式左部非终结符在所有符号中的序号*/if(k=strlen(rightj)-1)c在产生式右部的最后*/*如果if(in(vm,fo)=1)merge(followi,fol

26、lowm,1);continue;if(Fm=0)FOLLOW(m);Fm=1;merge(followi,followm,1); else/*如果c不在产生式右部的最后*/for(n=k+1;n=strlen(rightj)-1;n+)emp t0=0;result*=_emp(rightj n);if(result=1)/*如果右部c后面的符号串能推出A*/实验三if(in(vm,fo)=1)/*避免循环递归*/ merge(followi,followm,1);continue;if(Fm=O)FOLLOW(m);Fm=1;merge(followi,followm,1);for(n=k

27、+1;nv=strlen(nghtj)-1;n+)tem p n-k-1=rightjn;te mp strlen(rightj)-k-1=、0;FIRST(-1,tem p);merge(followi,TE MP,2);Fi=1;/*判断读入文法是否为一个LL(1)文法*/ int ll1()int i,j,length,result=1;char temp 50;/*初始化*/*求单个符号的 FIRST集合*/for(j=0;j=49;j+)firstj0=0;followj0=0;first1j0=0;selectj0=0;TEM Pj=、0;tem pj=、0;fj=0;Fj=0;f

28、or(j=0;j=strlen(v)-1;j+)first2(j);p rintf(nfirst1:);编译原理实验报告25for(j=0;jv=strlen(v)-1;j+)p rintf(%c:%s ,vj,first1j);printf(ne mp ty:%s,e mp ty);p rintf(n:n_e mp:);for(j=0;j=strlen(v)-1;j+)printf(%d ,_em p(vj);for(i=0;i=count-1;i+)FIRST(i,righti);/* 求 FIRST*/p rintf(n);for(j=0;j=strlen(non_ter)-1;j+)/

29、* 求 FOLLOW*/if(foj=0)fo0=0;FOLLOW(j); p rintf(nfirst:);for(i=0;i=count-1;i+)printf(%s ,firsti);p rintf(nfollow:);for(i=0;i=strlen(non_ter)-1;i+)p rintf(%s ,followi);for(i=0;i=count-1;i+)/*求每一产生式的 SELECT集合*/memc py (selecti,firsti,strlen(firsti);selectistrlen(firsti)=0;for(j=0;j=strlen(righti)-1;j+)r

30、esult*=_e mp (rightij);if(strlen(righ ti)=1 &righti0=)result=1;if(result=1)for(j=0;j+)if(vj=lefti)break;merge(selecti,followj,1);p rintf(nselect:);for(i=0;i=count-1;i+)p rintf(%s ,selecti);memc py(te mp ,select0,strlen(select0);te mp strlen(select0)=0;for(i=1;i=count-1;i+)/*判断输入文法是否为LL(1)文法*/length=

31、strlen(te mp);if(lefti=lefti-1)merge(te mp ,selecti,1);if(strlen(tem p) vlength+strlen(selecti)retum(O);elsetem p 0=、0;memc py (te mp ,selecti,strlen(selecti);te mp strlen(selecti)=、0;retum(1);/*构造分析表M*/ void MM()int i,j,k,m;for(i=0;i=19;i+)for(j=0;j=19;j+)Mij=-1;i=strlen(termin);termini=#;/*将#加入终结符

32、数组*/termini+1=0;for(i=0;i=count-1;i+)for(m=0;m+)if(non_term=lefti)break;/*m为产生式左部非终结符的序号*/for(j=0;j=0;n-)Sp+=rightmn;Sq+strlen(rightm)=0;p rintf(nS:%s str:,S);for(p=j;pv=strlen(str)-1; p+)p rintf(%c,str p);prin tf();/*一个用户调用函数*/ void menu()syntax();printf(n 是否继续？ (y or n):);scanf(%c, &choose);getcha

33、rO;while(choose=y)menu();/*主函数*/ void main()/*读入一个文法*/int i,j;start=grammer(termin,non_ter,left,right);p rintf(count=%d,count);p rintf(nstart:%c,start);strc py (v,non_ter); strcat(v,termin);p rintf(nv:%s,v);p nntf(nnon_ter:%s,non_ter);printf(ntermin:%s,termin);p rintf(nright:);for(i=0;i=count-1;i+)p rintf(%s ,righti);p rintf(nleft:);for(i=0;i=0)p rintf(n);menu();5.执行结果（1）输入一个文法p rintf(M%d%d=%d ,i,j,Mij);:厂 *D:Turboc2DebuesTnt ai. exe晶莹-丸委屈miro BBS终开生ww 的盼盼产紛紛紛 文文文文文文文 请请请请请请请串:号串3) =s