c語言學(xué)習(xí)中地語法分析器

1、H/* 分解的產(chǎn)生式的個(gè)數(shù) */* 所有終結(jié)符和非終結(jié)符的總數(shù) */ /* 開始符號(hào) */* 終結(jié)符號(hào) */* 非終結(jié)符號(hào) */* 所有符號(hào) */*左部 */*右部 */#include<stdlib.h> #include<stdio.h> #include<string.h> /*/ int count=0; int number; char start;char termin50; char non_ter50; char v50; char left50; char right5050;char first5050,follow5050; char

2、first15050; char select5050; char f50,F50; char empty20; char TEMP50; int validity=1; int ll=1; int M2020; char choose; char empt20; char fo20;/*各產(chǎn)生式右部的 FIRST 和左部的 FOLLOW 集合 */ /*所有單個(gè)符號(hào)的 FIRST 集合 */*各單個(gè)產(chǎn)生式的 SELECT 集合 */* 記錄各符號(hào)的 FIRST 和 FOLLOW 是否已求過 */* 記錄可直接推出 的符號(hào) */*求 FOLLOW 時(shí)存放某一符號(hào)串的 FIRST 集合*/* 表

3、示輸入文法是否有效 */* 表示輸入文法是否為/* 分析表 */* 用戶輸入時(shí)使用/*求_emp()時(shí)使用LL(1) 文法 */*/*/* 求 FOLLOW 集合時(shí)使用 */*判斷一個(gè)字符是否在指定字符串中*/ int in(char c,char *p)int i;if(strlen(p)=0) return(0);for(i=0;i+)if(pi=c)/* 若在，返回 1*/* 若不在，返回 0*/return(1);if(i=strlen(p)return(0);/*得到一個(gè)不是非終結(jié)符的符號(hào)*/char c()char c='A'while(in(c,non_ter)=

4、1)c+;return(c);/*分解含有左遞歸的產(chǎn)生式*/ void recur(char *point)/* 完整的產(chǎn)生式在 point 中 */int j,m=0,n=3,k; char temp20,ch; ch=c();/* 得到一個(gè)非終結(jié)符 */k=strlen(non_ter);non_terk=ch; non_terk+1='0'for(j=0;j<=strlen(point)-1;j+) if(pointn=point0)/* 如果 '|'后的首符號(hào)和左部相同 */for(j=n+1;j<=strlen(point)-1;j+)wh

5、ile(pointj!='|'&&pointj!='0') tempm+=pointj+; leftcount=ch;memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0' m=0; count+; if(pointj='|') n=j+1; break; /*如果 '|'后的首符號(hào)和左部不同 */ else leftcount=ch; rightcount0=''rightcount1='0'coun

6、t+;for(j=n;j<=strlen(point)-1;j+)if(pointj!='|')tempm+=pointj;elseleftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'printf(" count=%d ",count);m=0;count+;leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0' co

7、unt+; m=0;/*分解不含有左遞歸的產(chǎn)生式*/ void non_re(char *point) int m=0,j;char temp20; for(j=3;j<=strlen(point)-1;j+) if(pointj!='|')tempm+=pointj;elseleftcount=point0;memcpy(rightcount,temp,m);rightcountm='0'm=0;count+;leftcount=point0;memcpy(rightcount,temp,m);rightcountm='0'count+;

8、m=0;/*讀入一個(gè)文法*/char grammer(char *t,char *n,char *left,char right5050)char vn50,vt50;char s;char p5050;int i,j,k;printf(" 請(qǐng)輸入文法的非終結(jié)符號(hào)串： scanf("%s",vn);getchar(); i=strlen(vn); memcpy(n,vn,i);ni='0'printf(" 請(qǐng)輸入文法的終結(jié)符號(hào)串： scanf("%s",vt);getchar(); i=strlen(vt); memc

9、py(t,vt,i);ti='0'printf(" 請(qǐng)輸入文法的開始符號(hào)：scanf("%c",&s); getchar();printf(" 請(qǐng)輸入文法產(chǎn)生式的條數(shù)： scanf("%d",&i);getchar(); for(j=1;j<=i;j+)printf(" 請(qǐng)輸入文法的第 %d 條(共 %d 條)產(chǎn)生式： ",j,i); scanf("%s",pj-1);getchar();");");");");for

10、(j=0;j<=i-1;j+)if(pj1!='-'|pj2!='>') printf("ninput error!");validity=0; return('0');/* 檢測輸入錯(cuò)誤 */* 分解輸入的各產(chǎn)生式 */ for(k=0;k<=i-1;k+) if(pk3=pk0) recur(pk);elsenon_re(pk); return(s);/*將單個(gè)符號(hào)或符號(hào)串并入另一符號(hào)串*/void merge(char *d,char *s,int type)/*d是目標(biāo)符號(hào)串，s是源串，type= 1

11、,源串中的 '并并入目串;type= 2,源串中的 '不并入目串*/int i,j; for(i=0;i<=strlen(s)-1;i+) if(type=2&&si='')elsefor(j=0;j+)if(j<strlen(d)&&si=dj) break;if(j=strlen(d)dj=si; dj+1='0' break;/*求所有能直接推出 的符號(hào)*/void emp(char c)char temp10; int i;for(i=0;i<=count-1;i+) if(righti0

12、=c&&strlen(righti)=1) /*即求所有由 ' '推出的符號(hào) */temp0=lefti;temp1='0' merge(empty,temp,1); emp(lefti);/* 求某一符號(hào)能否推出 ' ' */int _emp(char c) /* 若能推出，返回 1；否則，返回 0*/ int i,j,k,result=1,mark=0;char temp20;temp0=c;temp1='0'merge(empt,temp,1);if(in(c,empty)=1)return(1);for(i

13、=0;i+)if(i=count)if(lefti=c)return(0);/*找一個(gè)左部為 c 的產(chǎn)生式 */j=strlen(righti);if(j=1&&in(righti0,empty)=1) return(1);else if(j=1&&in(righti0,termin)=1) return(0);else/*j 為右部的長度 */for(k=0;k<=j-1;k+)if(in(rightik,empt)=1)mark=1; if(mark=1) continue; elsefor(k=0;k<=j-1;k+)result*=_emp(

14、rightik); temp0=rightik; temp1='0' merge(empt,temp,1);if(result=0&&i<count)continue;else if(result=1&&i<count)return(1);/*判斷讀入的文法是否正確*/ int judge()int i,j;for(i=0;i<=count-1;i+)if(in(lefti,non_ter)=0) /* 若左部不在非終結(jié)符中，報(bào)錯(cuò) */printf("nerror1!");validity=0;return(

15、0);for(j=0;j<=strlen(righti)-1;j+)if(in(rightij,non_ter)=0&&in(rightij,termin)=0&&rightij!='') /*若右部某一符號(hào)不在非終結(jié)符、終結(jié)符中且不為' '，報(bào)錯(cuò) */printf("nerror2!");validity=0;return(0); return(1);/* 求單個(gè)符號(hào)的 FIRST */void first2(int i)char c,temp20; int j,k,m; c=vi;char ch=&#

16、39;' emp(ch); if(in(c,termin)=1)first1i0=c; first1i1='0' else if(in(c,non_ter)=1) for(j=0;j<=count-1;j+) /*i 為符號(hào)在所有輸入符號(hào)中的序號(hào) */* 若為終結(jié)符 */* 若為非終結(jié)符 */if(leftj=c)if(in(rightj0,termin)=1|rightj0='')temp0=rightj0;temp1='0' merge(first1i,temp,1);else if(in(rightj0,non_ter)=1)

17、 if(rightj0=c) continue;for(k=0;k+)if(vk=rightj0)break;if(fk='0') first2(k);fk='1' merge(first1i,first1k,2);for(k=0;k<=strlen(rightj)-1;k+) empt0='0' if(_emp(rightjk)=1&&k<strlen(rightj)-1) for(m=0;m+)if(vm=rightjk+1) break;if(fm='0')first2(m);fm='1&

18、#39;merge(first1i,first1m,2);else if(_emp(rightjk)=1&&k=strlen(rightj)-1) temp0=''temp1='0'merge(first1i,temp,1);else break;fi='1'/*求各產(chǎn)生式右部的 FIRST */ void FIRST(int i,char *p)int length;int j,k,m;/* 如果右部為單個(gè)符號(hào) */char temp20; length=strlen(p); if(length=1)if(p0='

19、9;)if(i>=0)firsti0='' firsti1='0'elseTEMP0=''TEMP1='0'elsefor(j=0;j+)if(vj=p0) break;if(i>=0) memcpy(firsti,first1j,strlen(first1j); firstistrlen(first1j)='0'elsememcpy(TEMP,first1j,strlen(first1j); TEMPstrlen(first1j)='0'/* 如果右部為符號(hào)串 */elsefor(j=

20、0;j+)if(vj=p0) break;if(i>=0)merge(firsti,first1j,2);elsemerge(TEMP,first1j,2);for(k=0;k<=length-1;k+)empt0='0'if(_emp(pk)=1&&k<length-1)for(m=0;m+)if(vm=rightik+1)break;if(i>=0)merge(firsti,first1m,2);elsemerge(TEMP,first1m,2);else if(_emp(pk)=1&&k=length-1)temp0

21、=''temp1='0'if(i>=0)merge(firsti,temp,1);elsemerge(TEMP,temp,1);else if(_emp(pk)=0)break;/*求各產(chǎn)生式左部的 FOLLOW*/void FOLLOW(int i)int j,k,m,n,result=1; char c,temp20; c=non_teri; temp0=c; temp1='0' merge(fo,temp,1); if(c=start)temp0='#' temp1='0'merge(followi,t

22、emp,1); /*c 為待求的非終結(jié)符 */* 若為開始符號(hào) */for(j=0;j<=count-1;j+)if(in(c,rightj)=1)for(k=0;k+)if(rightjk=c)/*找一個(gè)右部含有 c 的產(chǎn)生式 */break; /*k 為 c 在該產(chǎn)生式右部的序號(hào) */ for(m=0;m+)if(vm=leftj)break; /*m 為產(chǎn)生式左部非終結(jié)符在所有符號(hào)中的序號(hào)*/if(k=strlen(rightj)-1) /* 如果 c 在產(chǎn)生式右部的最后 */ if(in(vm,fo)=1) merge(followi,followm,1); continue;i

23、f(Fm='0')FOLLOW(m);Fm='1'merge(followi,followm,1);else /* 如果 c 不在產(chǎn)生式右部的最后 */ for(n=k+1;n<=strlen(rightj)-1;n+)empt0='0' result*=_emp(rightjn); if(result=1)/*如果右部c后面的符號(hào)串能推出A*/if(in(vm,fo)=1) /* 避免循環(huán)遞歸 */ merge(followi,followm,1); continue;if(Fm='0')FOLLOW(m);Fm='

24、;1'merge(followi,followm,1);for(n=k+1;n<=strlen(rightj)-1;n+)tempn-k-1=rightjn;tempstrlen(rightj)-k-1='0'FIRST(-1,temp);merge(followi,TEMP,2);Fi='1'/*判斷讀入文法是否為一個(gè) LL(1) 文法 */ int ll1() /*初始化 */int i,j,length,result=1; char temp50; for(j=0;j<=49;j+) firstj0='0'followj

25、0='0' first1j0='0' selectj0='0' TEMPj='0' tempj='0' fj='0' Fj='0'/*求單個(gè)符號(hào)的 FIRST 集合 */ first 集 :"); for(j=0;j<=strlen(v)-1;j+) first2(j);printf("n 各非終結(jié)符導(dǎo)出的 for(j=0;j<=strlen(v)-1;j+) printf("%c:%s ",vj,first1j);printf(&

26、quot;n 能導(dǎo)空的非終結(jié)符集合 :%s",empty); / printf("n_emp:"); /for(j=0;j<=strlen(v)-1;j+)/ printf("%d ",_emp(vj); for(i=0;i<=count-1;i+)/* 求 FIRST*/FIRST(i,righti); for(j=0;j<=strlen(non_ter)-1;j+)/* 求 FOLLOW*/ if(foj=0) fo0='0'FOLLOW(j);/printf("nfirst:");/f

27、or(i=0;i<=count-1;i+)/ printf("%s ",firsti); printf("nfollow 集合 :");for(i=0;i<=strlen(non_ter)-1;i+) printf("%s ",followi); for(i=0;i<=count-1;i+) /*求每一產(chǎn)生式的 SELECT 集合 */ memcpy(selecti,firsti,strlen(firsti); selectistrlen(firsti)='0'for(j=0;j<=strlen

28、(righti)-1;j+) result*=_emp(rightij);if(strlen(righti)=1&&righti0='')result=1; if(result=1) for(j=0;j+)if(vj=lefti)break;merge(selecti,followj,1); printf("nselect 集合順序是 :");for(i=0;i<=count-1;i+) printf("%s ",selecti);memcpy(temp,select0,strlen(select0); tempst

29、rlen(select0)='0'for(i=1;i<=count-1;i+) /*判斷輸入文法是否為 LL(1) 文法 */ length=strlen(temp);if(lefti=lefti-1) merge(temp,selecti,1); if(strlen(temp)<length+strlen(selecti)return(0);elsetemp0='0' memcpy(temp,selecti,strlen(selecti);tempstrlen(selecti)='0' return(1);/*構(gòu)造分析表 M */

30、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='#'/* 將 #加入終結(jié)符數(shù)組 */termini+1='0'for(i=0;i<=count-1;i+)for(m=0;m+)if(non_term=lefti)break; /*m 為產(chǎn)生式左部非終結(jié)符的序號(hào) */ for(j=0;j<=strlen(selecti)-1;j+)if(in(selectij,termin)=1)for(k=0;k+)if(ter

31、mink=selectij)break; /*k 為產(chǎn)生式右部終結(jié)符的序號(hào) */ Mmk=i;/*判斷符號(hào)串是否是該文法的句型*/ void syntax() int i,j,k,m,n,p,q;char ch; char S50,str50;printf(" 請(qǐng)輸入該文法的句型： "); scanf("%s",str); getchar();i=strlen(str); stri='#' stri+1='0'S0='#'S1=start;S2='0'j=0;ch=strj;while(1)

32、if(in(Sstrlen(S)-1,termin)=1) if(Sstrlen(S)-1!=ch)printf（" 該符號(hào)串不是文法的句型！ "）; return;else if(Sstrlen(S)-1='#')printf（" 該符號(hào)串是文法的句型 ."）; return; elseSstrlen(S)-1='0'j+; ch=strj;elsefor(i=0;i+) if(non_teri=Sstrlen(S)-1) break;for(k=0;k+)if(termink=ch)break;if(k=strlen(

33、termin)printf(" 詞法錯(cuò)誤！ ");return;if(Mik=-1)printf(" 語法錯(cuò)誤！ ");return; elsem=Mik;if(rightm0='')Sstrlen(S)-1='0'elsep=strlen(S)-1; q=p; for(n=strlen(rightm)-1;n>=0;n-) Sp+=rightmn;Sq+strlen(rightm)='0'printf("S:%s str:",S);for(p=j;p<=strlen(str