编译原理语法分析程序c╱c++

1、语法分析 (王君网络1 班)#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;/*各产生式右部的F

2、IRST 和左部的 FOLLOW 集合 */char first15050;char select5050;char f50,F50;char empty20;char TEMP50;int validity=1;int ll=1;/*所有单个符号的FIRST 集合 */* 各单个产生式的SELECT 集合 */* 记录各符号的 FIRST 和 FOLLOW 是否已求过 */*记录可直接推出人的符号*/* 求 FOLLOW 时存放某一符号串的 FIRST 集合 */* 表示输入文法是否有效*/* 表示输入文法是否为 LL(1) 文法 */int M2020; char choose; char

3、 empt20; char fo20;/* 分析表 */* 用户输入时使用 */*求_emp()时使用*/* 求 FOLLOW 集合时使用 */*判断一个字符是否在指定字符串中*/int in(char c,char *p)int i;if(strlen(p)=0)return(0);for(i=0;i+)if(pi=c)return(1);if(i=strlen(p)/*若在，返回1*/return(0);/*若不在，返回0*/*得到一个不是非终结符的符号*/ char c() char c='A'while(in(c,non_ter)=1)c+;return(c);/* 分

4、解含有左递归的产生式*/void recur(char *point)/* 完整的产生式在point 中 */int j,m=0,n=3,k;char temp20,ch;ch=c();/*得到一个非终结符*/k=strlen(non_ter);non_terk=ch;non_terk+1='0'for(j=0;j<=strlen(point)-1;j+)*/if(pointn=point0)/* 如果'|'后的首符号和左部相同for(j=n+1;j<=strlen(point)-1;j+) while(pointj!='|'&

5、;&pointj!='0') tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1='0'm=0;count+;if(pointj='|')n=j+1;break; else/* 如果'|'后的首符号和左部不同*/leftcount=ch;rightcount0=w；rightcount1='0'count+;for(j=n;j<=strlen(point)-1;j+) if(pointj!

6、='|')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'count+;m=0;/* 分解不含有左递归的产生式*/void non_re(char *point)int

7、 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+;m=0;/*读入一个文法*/ char grammer(char *t,char *n,char *left,ch

8、ar right5050) char vn50,vt50;char s;char p5050;int i,j,k;printf("n 请输入文法的非终结符号串： ");scanf("%s",vn);getchar();i=strlen(vn);memcpy(n,vn,i);ni='0'printf(" 请输入文法的终结符号串： ");scanf("%s",vt);getchar();i=strlen(vt);memcpy(t,vt,i);ti='0'printf(" 请输入

9、文法的开始符号： ");scanf("%c",&s);getchar();printf(" 请输入文法产生式的条数： ");scanf("%d",&i);getchar();for(j=1;j<=i;j+)printf(" 请输入文法的第%d 条(共 %d 条)产生式： ",j,i);scanf("%s",pj-1);getchar();for(j=0;j<=i-1;j+)if(pj1!='-'|pj2!='>') pr

10、intf("ninput error!");validity=0;return('0');/* 检测输入错误 */for(k=0;k<=i-1;k+)/* 分解输入的各产生式*/if(pk3=pk0)recur(pk);elsenon_re(pk);return(s);/*将单个符号或符号串并入另一符号串* I void merge(char *d,char *s,int type)/*d是目标符号串，s是源串，type=1,源串中的一并并入目串;type = 2,源串中的人不并入目串*/int i,j;for(i=0;i<=strlen(s)-

11、1;i+)if(type=2&&si='A');elsefor(j=0;j+)if(j<strlen(d)&&si=dj)break;if(j=strlen(d)dj=si;dj+1='0'break;/*/void emp(char c) /* 即求所有由 ' A '推出的符号*/*求所有能直接推出人的符号*char temp10;int i;for(i=0;i<=count-1;i+)if(righti0=c&&strlen(righti)=1) temp0=lefti;temp1=

12、'0'merge(empty,temp,1);emp(lefti);/* 求某一符号能否推出A '*/ 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=0;i+)if(i=count)return(0);if(lefti=c)/*找一个左部为 c 的产生式 */j=strlen(righti); /*j 为右部的长度

13、*/if(j=1&&in(righti0,empty)=1)return(1);else if(j=1&&in(righti0,termin)=1)return(0);elsefor(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(rightik);temp0=rightik;temp1='0'merge(empt,temp,1);if(result=0&&i<coun

14、t)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)/* 若左部不在非终结符中，报错*/printf("nerror1!");validity=0;return(0);for(j=0;j<=strlen(righti)-1;j+)if(in(rightij,non_ter)=0&&in(rightij,termin)=0&am

15、p;&rightij!='A')/*若右部某一符号不在非终结符、终结符中且不为人，报错*/printf("nerror2!");validity=0;return(0);return(1);/*求单个符号的 FIRST*/ void first2(int i)*/*i 为符号在所有输入符号中的序号char c,temp20;int j,k,m;c=vi;char ch='A'emp(ch);if(in(c,termin)=1)/*若为终结符*/first1i0=c;first1i1='0'else if(in(c,no

16、n_ter)=1)/*若为非终结符*/for(j=0;j<=count-1;j+)if(leftj=c)if(in(rightj0,termin)=1|rightj0='A')temp0=rightj0;temp1='0'merge(first1i,temp,1);else if(in(rightj0,non_ter)=1)if(rightj0=c)continue;for(k=0;k+)if(vk=rightj0)break;if(fk='0')first2(k);fk='1'merge(first1i,first1k,2

17、);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'merge(first1i,first1m,2);else if(_emp(rightjk)=1&&k=strlen(rightj)-1)temp0='A'temp1='0'merge(first

18、1i,temp,1);elsebreak;fi='1' /*求各产生式右部的 FIRST*/ void FIRST(int i,char *p) int length;int j,k,m;char temp20;/* 如果右部为单个符号*/length=strlen(p);if(length=1)if(P0=w)if(i>=0)firsti0='A'firsti1='0'elseTEMP0='A'TEMP1='0'elsefor(j=0;j+)if(vj=p0)break;if(i>=0)memcpy(

19、firsti,first1j,strlen(first1j);firstistrlen(first1j)='0'elsememcpy(TEMP,first1j,strlen(first1j);TEMPstrlen(first1j)='0'else/*如果右部为符号串 */for(j=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&

20、&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=w；temp1='0'if(i>=0)merge(firsti,temp,1);elsemerge(TEMP,temp,1);else if(_emp(pk)=0) break;/*求各产生式左部的 FOLLOW*/void FOLLOW(int i)int

21、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,temp,1);for(j=0;j<=count-1;j+)/*c 为待求的非终结符*/* 若为开始符号*/if(in(c,rightj)=1)for(k=0;k+)if(rightjk=c)/* 找一个右部含有c 的产生式 */break; /*k 为 c 在该产生式右部的序号*/for(m=0;m+)*

22、/if(vm=leftj)break;/*m 为产生式左部非终结符在所有符号中的序号if(k=strlen(rightj)-1)/* 如果 c 在产生式右部的最后*/if(in(vm,fo)=1)merge(followi,followm,1);continue;if(Fm='0')FOLLOW(m);Fm='1'merge(followi,followm,1);else/* 如果 c 不在产生式右部的最后*/for(n=k+1;n<=strlen(rightj)-1;n+)empt0='0'result*=_emp(rightjn);if

23、(result=1)/*如果右部C后面的符号串能推出人*/if(in(vm,fo)=1)/* 避免循环递归*/merge(followi,followm,1); continue;if(Fm='0')FOLLOW(m);Fm='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'/*判断

24、读入文法是否为一个LL(1) 文法*/int ll1()int i,j,length,result=1;char temp50;for(j=0;j<=49;j+)/* 初始化 */firstj0='0'followj0='0'first1j0='0'selectj0='0'TEMPj='0'tempj='0'fj='0'Fj='0'for(j=0;j<=strlen(v)-1;j+)first2(j);printf("nfirst1:"

25、);for(j=0;j<=strlen(v)-1;j+)/* 求单个符号的 FIRST 集合 */printf("%c:%s ",vj,first1j);printf("nempty:%s",empty);printf("n:n_emp:");for(j=0;j<=strlen(v)-1;j+)printf("%d ",_emp(vj);for(i=0;i<=count-1;i+)FIRST(i,righti);printf("n");for(j=0;j<=strlen(

26、non_ter)-1;j+)/* 求 FIRST*/* 求 FOLLOW*/if(foj=0) fo0='0'FOLLOW(j);printf("nfirst:");for(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+)/* 求每一产生式的 SELECT 集合 *

27、/memcpy(selecti,firsti,strlen(firsti);selectistrlen(firsti)='0'for(j=0;j<=strlen(righti)-1;j+)result*=_emp(rightij);if(strlen(righti)=1&&righti0='A')result=1;if(result=1)for(j=0;j+)if(vj=lefti)break;merge(selecti,followj,1);printf("nselect:");for(i=0;i<=count-

28、1;i+)printf("%s ",selecti);memcpy(temp,select0,strlen(select0);tempstrlen(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,sele

29、cti,strlen(selecti);tempstrlen(selecti)='0'return(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='#'/* 将 #加入终结符数组*/termini+1='0'for(i=0;i<=count-1;i+)for(m=0;m+)if(non_term=lefti)break; /*m 为产生式左部非终结符的序号*/for(j=0;

30、j<=strlen(selecti)-1;j+)if(in(selectij,termin)=1)for(k=0;k+)if(termink=selectij)*/break;/*k 为产生式右部终结符的序号Mmk=i;/* 总控算法*/void syntax()int i,j,k,m,n,p,q;char ch;char S50,str50;printf(" 请输入该文法的句型： ");scanf("%s",str);getchar();i=strlen(str);stri='#'stri+1='0'S0='

31、;#'S1=start;S2='0'j=0;ch=strj;while(1)if(in(Sstrlen(S)-1,termin)=1)if(Sstrlen(S)-1!=ch)printf("n 该符号串不是文法的句型！ "); return;else if(Sstrlen(S)-1='#')printf("n 该符号串是文法的句型.");return;elseSstrlen(S)-1='0'j+;ch=strj;elsefor(i=0;i+)if(non_teri=Sstrlen(S)-1) bre

32、ak;for(k=0;k+)if(termink=ch)break;if(k=strlen(termin)printf("n 词法错误！ ");return;if(Mik=-1)printf("n 语法错误！ ");return; elsem=Mik;if(rightm0=w)Sstrlen(S)-1='0' else p=strlen(S)-1;q=p;for(n=strlen(rightm)-1;n>=0;n-)Sp+=rightmn;Sq+strlen(rightm)='0'printf("nS:%s

33、 str:",S);for(p=j;p<=strlen(str)-1;p+)printf("%c",strp);printf(" ");/* 一个用户调用函数*/void menu() syntax();printf("n 是否继续？ (y or n):");scanf("%c",&choose);getchar();while(choose='y')menu();/* 主函数*void main()int i,j;/* 读入一个文法*/start=grammer(termin,non_ter,left,right);printf("count=%d",count);printf("nstart:%c",start);strcpy(v,non_ter);strcat(v,termin);printf("nv:%s",v);printf("nnon_ter:%s",non_ter); p