《2022年编译原理C语言LL代码 .pdf》由会员分享，可在线阅读，更多相关《2022年编译原理C语言LL代码 .pdf（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、/*/ #include #include #include /*/ int count =0; /* 分解的产生式的个数 */ int number ; /* 所有终结符和非终结符的总数*/ char start ; /* 开始符号 */ char termin 50; /* 终结符号 */ char non_ter 50; /* 非终结符号 */ char v50; /* 所有符号 */ char left 50; /* 左部*/ char right 5050; /* 右部*/ char first 5050, follow 5050; /* 各产生式右部的 FIRST和左部的FOLLO
2、W 集合*/ char first1 5050; /* 所有单个符号的 FIRST集合*/ char select 5050; /* 各单个产生式的 SELECT 集合*/ char f50, F50; /* 记录各符号的 FIRST和FOLLOW 是否已求过 */ char empty 20; /* 记录可直接推出 的符号 */ char TEMP50; /* 求FOLLOW 时存放某一符号串的 FIRST集合*/ int validity =1; /* 表示输入文法是否有效 */ int ll=1; /* 表示输入文法是否为 LL(1)文法*/ int M 2020; /* 分析表 */
3、char choose ; /* 用户输入时使用 */ char empt 20; /* 求_emp() 时使用 */ char fo 20; /* 求FOLLOW 集合时使用 */ /* 判断一个字符是否在指定字符串中名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 26 页 - - - - - - - - - */ int in(char c,char *p) int i; if(strlen (p)=0) return (0); for (i=0; i+) if(pi
4、= c) return (1); /* 若在，返回 */ if(i= strlen (p) return (0); /* 若不在，返回 */ /* 得到一个不是非终结符的符号*/ char c() char c=A ; while (in(c,non_ter )=1) c+; return (c); /* 分解含有左递归的产生式*/ void recur (char *point ) /* 完整的产生式在 point 中*/ int j,m=0, n=3, k; char temp 20, ch; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -
5、 - - - - 名师精心整理 - - - - - - - 第 2 页，共 26 页 - - - - - - - - - ch= c(); /* 得到一个非终结符 */ k=strlen (non_ter ); non_ter k= ch; non_ter k+1= 0 ; for (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 += po
6、int 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 +; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -
7、- - - - - 第 3 页，共 26 页 - - - - - - - - - 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 ,
8、m ); right count m= ch; right count m+1= 0 ; count +; m=0; /* 分解不含有左递归的产生式*/ void non_re (char *point ) int m=0, j; char temp 20; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 26 页 - - - - - - - - - for (j=3; j= strlen (point )-1;j+) if(point j!= |) temp m+= p
9、oint j; else left count = point 0; memcpy (right count ,temp ,m ); right count m= 0 ; m=0; count +; left count = point 0; memcpy (right count ,temp ,m); right count m = 0 ; count +; m=0; /* 读入一个文法*/ char grammer (char *t,char *n,char *left ,char right 5050) char vn50, vt50; char s; char p5050; int i
10、,j,k; printf (n 请输入文法的非终结符号串：); scanf (%s ,vn); getchar (); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 26 页 - - - - - - - - - i=strlen (vn); memcpy (n,vn,i); ni= 0 ; printf (请输入文法的终结符号串：); scanf (%s ,vt); getchar (); i=strlen (vt); memcpy (t,vt,i); ti= 0 ;
11、printf (请输入文法的开始符号： ); 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 ) printf (ninput error!); validity =0; return (0 ); /* 检测输入错误 */ for (k=0; k= i-1;k+) /* 分解输入的各产
12、生式 */ if(pk3= pk0) recur (pk); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 26 页 - - - - - - - - - else non_re (pk); return (s); /* 将单个符号或符号串并入另一符号串*/ void merge (char *d,char *s,int type ) /*d 是目标符号串， s是源串， type ，源串中的 一并并入目串；type ，源串中的 不并入目串 */ int i,j; for
13、(i=0; i= strlen (s)-1;i+) if(type =2&si= ) ; else for (j=0;j+) if(jstrlen (d)& si= dj) break ; if(j= strlen (d) dj= si; dj+1= 0 ; break ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 26 页 - - - - - - - - - /* 求所有能直接推出 的符号*/ void emp (char c) /* 即求所有由 推出的符号 */
14、 char temp 10; int i; for (i=0; i= count -1;i+) if(right i0= c& strlen (right i)=1) temp 0= left i; temp 1= 0 ; merge (empty ,temp ,1); emp (left i); /* 求某一符号能否推出 */ int _emp (char c) /* 若能推出，返回；否则，返回*/ int i,j,k,result =1, mark =0; char temp 20; temp 0= c; temp 1= 0 ; merge (empt ,temp ,1); if(in(c
15、,empty )=1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 26 页 - - - - - - - - - return (1); for (i=0; i+) if(i= count ) return (0); if(left i= c) /* 找一个左部为 c的产生式 */ j=strlen (right i); /*j 为右部的长度 */ if(j=1&in(right i0, empty )=1) return (1); elseif (j=1&in(ri
16、ght i0, termin )=1) return (0); else for (k=0; k= j-1; k+) if(in(right ik,empt )=1) mark =1; if(mark =1) continue ; else for (k=0; k= j-1;k+) result *= _emp (right ik); temp 0= right ik; temp 1= 0 ; merge (empt ,temp ,1); if(result =0&icount ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
17、 名师精心整理 - - - - - - - 第 9 页，共 26 页 - - - - - - - - - continue ; elseif (result =1&icount ) return (1); /* 判断读入的文法是否正确*/ int judge () int i,j; for (i=0; i= count -1;i+) if(in(left i,non_ter )=0) /* 若左部不在非终结符中，报错*/ printf (nerror1!); validity =0; return (0); for (j=0; j= strlen (right i)-1; j+) if(in(
18、right ij,non_ter )=0&in (right ij,termin )=0&right ij!= ) /* 若右部某一符号不在非终结符、终结符中且不为 ，报错*/ printf (nerror2!); validity =0; return (0); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 26 页 - - - - - - - - - return (1); /* 求单个符号的 FIRST */ void first2 (int i) /*i 为符
19、号在所有输入符号中的序号*/ char c,temp 20; int j,k,m; c=vi; char ch= ; emp (ch); if(in(c,termin )=1) /* 若为终结符 */ first1 i0= c; first1 i1= 0 ; elseif (in(c,non_ter )=1) /* 若为非终结符 */ for (j=0; j= count -1; j+) if(left j= c) if(in(right j0, termin )=1| right j0= ) temp 0= right j0; temp 1= 0 ; merge (first1 i,temp
20、 ,1); elseif (in(right j0, non_ter )=1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 26 页 - - - - - - - - - if(right j0= c) continue ; for (k=0; k+) if(vk= right j0) break ; if(fk= 0 ) first2 (k); fk= 1 ; merge (first1 i,first1 k,2); for (k=0; k= strlen (rig
21、ht j)-1; k+) empt 0= 0 ; if(_emp (right jk)=1&k=0) first i0= ; first i1= 0 ; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 26 页 - - - - - - - - - TEMP0= ; TEMP1= 0 ; else for (j=0;j+) if(vj= p0) break ; if(i=0) memcpy (first i,first1 j,strlen (first1 j);
22、 first istrlen (first1 j)= 0 ; else memcpy (TEMP,first1 j,strlen (first1 j); TEMPstrlen (first1 j)= 0 ; else/* 如果右部为符号串 */ for (j=0; j+) if(vj= p0) break ; if(i=0) merge (first i,first1 j,2); else merge (TEMP,first1 j,2); for (k=0; k= length -1;k+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
23、- - - 名师精心整理 - - - - - - - 第 14 页，共 26 页 - - - - - - - - - empt 0= 0 ; if(_emp (pk)=1&k=0) merge (first i,first1 m,2); else merge (TEMP,first1 m,2); elseif (_emp (pk)=1&k= length -1) temp 0= ; temp 1= 0 ; if(i=0) merge (first i,temp ,1); else merge (TEMP,temp ,1); elseif (_emp (pk)=0) break ; /* 求各产
24、生式左部的 FOLLOW */ void FOLLOW (int i) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 26 页 - - - - - - - - - int j,k,m,n,result =1; char c,temp 20; c=non_ter i; /*c 为待求的非终结符 */ temp 0= c; temp 1= 0 ; merge (fo ,temp ,1); if(c= start ) /* 若为开始符号 */ temp 0= # ; tem
25、p 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 jk= c) break ; /*k 为c在该产生式右部的序号 */ for (m =0;m+) if(vm= left j) break ; /*m 为产生式左部非终结符在所有符号中的序号*/ if(k= strlen (right j)-1) /* 如果c在产生式右部的最后 */ if(in(vm ,fo )=1) merge (follow i
26、,follow m,1); continue ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 26 页 - - - - - - - - - if(Fm= 0 ) FOLLOW (m); Fm= 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 jn); i
27、f(result =1) /* 如果右部 c后面的符号串能推出 */ if(in(vm,fo)=1) /* 避免循环递归 */ merge (follow i,follow m,1); continue ; if(Fm= 0 ) FOLLOW (m); Fm= 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 ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
28、- - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 26 页 - - - - - - - - - FIRST(-1, temp ); merge (follow i,TEMP,2); Fi= 1 ; /* 判断读入文法是否为一个LL(1)文法*/ int ll1() int i,j,length ,result =1; char temp 50; for (j=0; j=49; j+) /* 初始化 */ first j0= 0 ; follow j0= 0 ; first1 j0= 0 ; select j0= 0 ; TEMPj= 0 ; temp
29、j= 0 ; fj= 0 ; Fj= 0 ; for (j=0; j= strlen (v)-1;j+) first2 (j); /* 求单个符号的 FIRST集合*/ printf (nfirst1:); for (j=0; j= strlen (v)-1;j+) printf (%c:%s ,vj,first1 j); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 26 页 - - - - - - - - - printf (nempty:%s,empty );
30、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,right i); /* 求FIRST*/ printf (n ); for (j=0; j= strlen (non_ter )-1;j+) /* 求FOLLOW*/ if(foj=0) fo 0= 0 ; FOLLOW (j); printf (nfirst:); for (i=0; i= count -1;i+) printf (%s ,first i); printf (nfo
31、llow:); for (i=0; i= strlen (non_ter )-1;i+) printf (%s ,follow i); for (i=0; i= count -1;i+) /* 求每一产生式的 SELECT集合*/ memcpy (select i,first i,strlen (first i); select istrlen (first i)= 0 ; for (j=0; j= strlen (right i)-1; j+) result *= _emp (right ij); if(strlen (right i)=1&right i0= ) result =1; if
32、(result =1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 26 页 - - - - - - - - - for (j=0;j+) if(vj= left i) break ; merge (select i,follow j,1); printf (nselect:); for (i=0; i= count -1;i+) printf (%s ,select i); memcpy (temp ,select 0, strlen (select 0); te
33、mp strlen (select 0)= 0 ; for (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 )length + strlen (select i) return (0); else temp 0= 0 ; memcpy (temp ,select i,strlen (select i); temp strlen (select i)= 0 ; return (1)
34、; /* 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 26 页 - - - - - - - - - 构造分析表 M */ void MM () int i,j,k,m; for (i=0; i=19; i+) for (j=0; j=19; j+) M ij=-1; i=strlen (termin ); termin i= # ; /* 将#加入终结符数组 */ termin i+1= 0 ; for (i=0; i= count -1;i+) for (m=0;
35、 m+) if(non_ter m= left i) break ; /*m 为产生式左部非终结符的序号*/ for (j=0; j=0; n-) Sp+= right mn; Sq+strlen (right m)= 0 ; printf (nS:%s 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
36、(); while (choose = y) menu (); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 26 页 - - - - - - - - - /* 主函数*/ void main () int i,j; start = grammer (termin ,non_ter ,left ,right ); /* 读入一个文法*/ printf (count=%d,count ); printf (nstart:%c,start ); strcpy (v,non
37、_ter ); strcat (v,termin ); printf (nv:%s ,v); printf (nnon_ter:%s,non_ter ); printf (ntermin:%s,termin ); printf (nright:); for (i=0; i= count -1;i+) printf (%s ,right i); printf (nleft:); for (i=0; i= count -1;i+) printf (%c ,left i); if(validity =1) validity =judge (); printf (nvalidity=%d,validi
38、ty ); if(validity =1) printf (n 文法有效 ); ll= ll1(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 26 页 - - - - - - - - - printf (nll=%d,ll); if(ll=0) printf (n 该文法不是一个 LL1文法！ ); else MM (); printf (n ); for (i=0; i=19; i+) for (j=0; j=0) printf (M%d%d=%d ,i,j,M ij); printf (n ); menu (); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 26 页 - - - - - - - - -