语法分析器实验报告

1、语法分析器实验报告 语法分析器得设计 实验报告 一、实验内容 语法分析程序用 ll(1)语法分析方法。首先输入定义好得文法书写文件(所用得文法可以用 ll(1)分析),先求出所输入得文法得每个非终结符就是否能推出空,再分别计算非终结符号得 first 集合,每个非终结符号得 follow 集合,以及每个规则得 select 集合,并判断任意一个非终结符号得任意两个规则得 select 集得交集就是不就是都为空,如果就是,则输入文法符合 ll(1)文法,可以进行分析。 对于文法: ge: ee+t|t tt*f|f fi|(e) 分析句子 i+i*i 就是否符合文法 。 二、基本思想 1、语法分

2、析器实现 语法分析就是编译过程得核心部分,它得主要任务就是按照程序得语法规则,从由词法分析输出得源程序符号串中识别出各类语法成分,同时进行词法检查,为语义分析与代码生成作准备。这里采用自顶向下得 ll(1)分析方法。 语法分析程序得流程图如图 54 所示。 该程序可分为如下几步: (1)读入文法 (2)判断正误 (3)若无误,判断就是否为 ll(1)文法 (4)若就是,构造分析表; (5)由句型判别算法判断输入符号串就是为该文法得句型。 三、核心思想 该分析程序有 15 部分组成: (1)首先定义各种需要用到得常量与变量; (2)判断一个字符就是否在指定字符串中; 开始 读入文法 有效？ 判断

3、句型 报错 结束 语法分析程序流程图 就 是 ll(1) 文 (3)读入一个文法; (4)将单个符号或符号串并入另一符号串; (5)求所有能直接推出得符号; (6)求某一符号能否推出 ; (7)判断读入得文法就是否正确; (8)求单个符号得 first; (9)求各产生式右部得 first; (10)求各产生式左部得 follow; (11)判断读入文法就是否为一个 ll(1)文法; (12)构造分析表 m; (13)句型判别算法; (14)一个用户调用函数; (15)主函数; 下面就是其中几部分程序段得算法思想: 1、求能推出空得非终结符集 、 实例中求直接推出空得 empty 集得算法描述

4、如下: void emp(char c) 参数 c 为空符号 char temp10;定义临时数组 int i; for(i=0;i=count1;i+)从文法得第一个产生式开始查找 if 产生式右部第一个符号就是空符号并且右部长度为 1, then 将该条产生式左部符号保存在临时数组 temp 中 将临时数组中得元素合并到记录可推出符号得数组 empty 中。 、求某一符号能否推出"" int _emp(char c) /若能推出,返回 1;否则,返回 0 int i,j,k,result=1,mark=0; char temp20; temp0=c; temp1=&qu

5、ot;0" 存放到一个临时数组 empt 里,标识此字符已查找其就是否可推出空字 如果 c 在可直接推出空字得 empty中,返回 1 for(i=0;i+) if(i=count) return(0); 找一个左部为 c 得产生式 j=strlen(righti); /j 为 c 所在产生式右部得长度 if 右部长度为 1 且右部第一个字符在 empty中、 then 返回 1(ab,b 可推出空) if 右部长度为 1 但第一个字符为终结符,then 返回 0(aa,a 为终结符) else for(k=0;k=j1;k+) 查找临时数组 empt、并标记 mark=1(aab)

6、 if 找到得字符与当前字符相同(aab) 结束本次循环 else(mark 等于 0) 查找右部符号就是否可推出空字,把返回值赋给 result 把当前符号加入到临时数组 empt里、 if 当前字符不能推出空字且还没搜索完全部得产生式 then 跳出本次循环继续搜索下一条产生式 else if /当前字符可推出空字,返回 1 2、计算每个符号得 first 集: 实例中求单个符号得 first 集得算法描述如下: void first2 (int i) 参数 i 为符号在所有输入符号中得序号 c 等于指示器 i 所指向得符号 在保存终结符元素得 termin数组查找 c if c 为终结符

7、(cv t ),then first(c)=c 在保存终结符元素得 non_ter数组查找 c if c 就是非终结符(cv n ) 在所有产生式中查找 c 所在得产生式 if 产生式右部第一个字符为终结符或空(即 ca (av t )或 c) then 把 a 或加进 first(c) if 产生式右部第一个字符为非终结符 then if 产生式右部得第一个符号等于当前字符 then 跳到下一条产生式进行查找 求当前非终结符在所有字符集中得位置 if 当前非终结符还没求其 first 集 then 查找它得 first 集并标识此符号已求其 first 集 求得结果并入到 c 得 first

8、 集、 if 当前产生式右部符号可推出空字且当前字符不就是右部得最后一个字符 then 获取右部符号下一个字符在所有字符集中得位置 if 此字符得 first 集还未查找 then 找其 first 集,并标其查找状态为 1 把求得得 first 集并入到 c 得 first 集、 if 当前右部符号串可推出空且就是右部符号串得最后一个字符(即产生式为 cy 1 y 2 y k ,若对一切 1=i=k,均有first(y i ),则将符号加进 first(c) ) then 把空字加入到当前字符 c 得 first 集、 else 不能推出空字则结束循环 标识当前字符 c 已查找其 first

9、 集、 3、 计算 follow 集 follow 集得构造可用如下方法来求: 对于文法中得符号 x Îv n ,其 follow(a)集合可反复应用下列规则计算,直到follow(a)集合不再增大为止。 (1)对于文法开始符号 s,因为 s s,故#Îfollow(s); (2)若 aa bb,其中 bÎv n ,aÎ(v t uv n ) * 、bÎ(v t uv n ) + ,则 first(b)eÎfollow(b); (3)若 aa b 或 aa bb (b e),则 follow(a) Îfollow(b)。 f

10、ollow 集得算法描述如下: void follow(int i) x 为待求得非终结符 把当前字符放到一临时数组 foll中,标识求已求其 follow 集、避免循环递归 if x 为开始符号 then #follow(x) 对全部得产生式找一个右部含有当前字符 x 得产生式 注:比如求 follow(b)则找 ax 或 aaxb(b)得产生式 if x 在产生式右部得最后(形如产生式 aax) then 查找非终结符 a 就是否已经求过其 follow 集、避免循环递归 if 非终结符 a 已求过其 follow 集 then follow(a)follow(x) 继续查下一条产生式就是

11、否含有 x else 求 a 之 follow 集,并标识为 a 已求其 follow 集 else if x 不在产生式右部得最后(形如 aabb) then if 右部 x 后面得符号串b能推出空字e then 查找b就是否已经求过其 follow 集、避免循环递归 if 已求过b得 follow 集 then follow(a)follow(b) 结束本次循环 else if b不能推出空字 then 求 first(b) 把 first(b)中所有非空元素加入到 follow(b)中 标识当前要求得非终结符 x 得 follow 集已求过 4、计算 select 集 select 集得

12、构造算法如下: 对所有得规则产生式 ax: (1)若 x 不能推出空字e,则 select(ax) = first(x); (2)若 x 可推出空字e,则 select(ax)=first(x)e u follow(a)。 算法描述如下: for(i=0;i=产生式总数 1;i+) 先把当前产生式右部得 first 集(一切非空元素,不包括 )放入到当前产生式得 select(i); if 产生式右部符号串可推出空字e then 把 i 指向得当前产生式左部得非终结符号得 follow 集并入到 select(i)中 5、判断就是否 ll(1)文法 要判断就是否为 ll(1)文法,需要输入得文

13、法 g 有如下要求: 具有相同左部得规则得 select 集两两不相交,即: select(aa) select(ab)= Æ 如果输入得文法都符合以上得要求,则该文法可以用 ll(1)方法分析。 算法描述如下: 把第一条产生式得 select(0)集放到一个临时数组 temp中 for(i=1;i=产生式总数 1;i+) 求 temp 得长度 length if i 指向得当前产生式得左部等于上一条产生式得左部 then 把 select(i)并入到 temp 数组中 if temp 得长度小于 length 加上 select (i)得长度 返回 0 else 把 temp 清空

14、 把 select (i)存放到 temp 中 结果返回 1; 四、算法 #includestdlib、h #includestdio、h #includestring、h /*/ int count=0; /产生式得个数 int number; /所有终结符与非终结符得总数 char start; /开始符号 char termin50; /终结符号 char non_ter50; /非终结符号 char v50; /所有符号 char left50; /左部 char right5050; /右部 char first5050,follow5050; /各产生式右部得 first 与左部得

15、 follow 集合 char first15050; /所有单个符号得 first 集合 char select5050; /各个产生式得 select 集合 char firstflag50,followflag50; /记录各符号得 first 与 follow 就是否已求过 char empty20; /记录可推出得符号 char nonempty20; /记录不可推出得符号 char empt20; /求_emp 时使用 char temp50; /求 follow 时存放某一符号串得 first 集合 int validity=1; /表示输入文法就是否有效 int ll=1; /

16、表示输入文法就是否为 ll(1)文法 int m2020; /分析表 char choose; /用户输入时使用 char foll20; /求 follow 集合时使用 /* 判断一个字符 c 就是否在指定字符串 p 中 */ int in(char c,char *p) int i; if(strlen(p)=0) return(0); for(i=0;i+) if(pi=c) return(1); /若在,返回 1 if(i=(int)strlen(p) return(0); /若不在,返回 0 /* 将单个符号或符号串并入另一符号串 */ void merge(char *d,char

17、 *s,int type) /就是目标符号串,s 就是源串,type1,源串中得""一并并入目串; /type2,源串中得""不并入目串 int i,j; for(i=0;i=(int)strlen(s)1;i+) if(type=2si=""); else for(j=0;j+) if(j(int)strlen(d)si=dj) break; /若已存在,则退出,继续瞧下一个源串字符 if(j=(int)strlen(d) /若不存在,则并入 dj=si; dj+1="0" break; /* 读入一个文法 */

18、 char grammer(char *t,char *n,char *left,char right5050) char vn50,vt50; char s; char p5050; int i,j; printf(请输入文法得非终结符号串:); 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(请输入文法得

19、开始符号:); scanf(%c,s); getchar; printf(请输入文法产生式得条数:); scanf(%d,i); getchar; count=i; for(j=1;j=i;j+) printf(请输入文法得第%d 条(共%d 条)产生式:,j,i); scanf(%s,pj1); getchar; for(j=0;j=i1;j+) if(pj1!=""|pj2!="") /检测输入错误 printf(n 输入错误!); validity=0; return("0"); return(s); /* 判断读入得文法就是否

20、正确 */ int judge int i,j; for(i=0;i=count1;i+) if(in(lefti,non_ter)=0) /若左部不在非终结符中,报错 printf(n 文法左部出错!); validity=0; return(0); for(j=0;j=(int)strlen(righti)1;j+) if(in(rightij,non_ter)=0in(rightij,termin)=0rightij!="") /若右部某一符号不在非终结符、终结符中且不为"",报错 printf(n 文法右部出错!); validity=0; re

21、turn(0); return(1); /* 求所有能直接推出得符号 */ void emp(char c) char temp10; int i; for(i=0;i=count1;i+) if(righti0=cstrlen(righti)=1) temp0=lefti; temp1="0" merge(empty,temp,1);/求所有能直接推出"得符号,结果保存到 empty中 emp(lefti); /* 求某一符号能否推出"" */ int _emp(char c) /若能推出,返回 1;否则,返回 0 int i,j,k,res

22、ult=1,mark=0; char temp20; temp0=c; temp1="0" merge(empt,temp,1);/存放到一个临时数组empt里,标识此字符已查找其就是否可推出空字 if(in(c,empty)=1)/如果 c 在可直接推出空字得 empty中,返回 1 return(1); for(i=0;i+) if(i=count) return(0); if(lefti=c) /找一个左部为 c 得产生式 j=strlen(righti); /j 为 c 所在产生式右部得长度 if(j=1in(righti0,empty)=1)/右部长度为 1 且右

23、部第一个字符在 empty中、返回 1(ab,b 可推出空) return(1); else if(j=1in(righti0,termin)=1)/右部长度为 1 但第一个字符为终结符,返回 0(aa,a 为终结符) continue; else for(k=0;k=j1;k+) if(in(rightik,empt)=1)/查找临时数组 empt、(aab) mark=1; if(mark=1) /找到得字符与当前字符相同(aab) continue; /结束本次循环 else /(mark 等于 0) for(k=0;k=j1;k+) result*=_emp(rightik);/递归调

24、用,查找右部符号就是否可推出空字,把返回值赋给 result temp0=rightik; temp1="0" merge(empt,temp,1);/把当前符号加入到临时数组 empt里,标记已查找 if(result=0icount)/如果当前字符不能推出空字且还没搜索完全部得产生式,则跳出本次循环继续搜索下一条产生式 continue; else if(result=1icount)/当前字符可推出空字,返回 1 return(1); /* 求单个符号得 first */ void first2(int i) /i 为符号在所有输入符号中得序号 char c,temp

25、20; int j,k,m; char ch="" c=vi; emp(ch);/求所有能直接推出空字得符号,结果保存到 empty中 if(in(c,termin)=1) /若为终结符 cvt,则 first(c)=c first1i0=c; first1i1="0" else if(in(c,non_ter)=1) /若为非终结符 for(j=0;j=count1;j+) /j 为所有产生式中得序列 if(leftj=c) /找一个左部为 c 得产生式 if(in(rightj0,termin)=1|rightj0="") /若产

26、生式右部第一个字符为终结符或空、产生式 xa (avt)或 x,则把 a 或加进 first(x) temp0=rightj0; temp1="0" merge(first1i,temp,1); /xy1y2yk 得产生式,若 y1vn,则把 first(y1)中得一切非空符号加进first(x) else if(in(rightj0,non_ter)=1)/产生式右部第一个字符为非终结符 if(rightj0=c)/产生式右部得第一个符号等于当前字符,则跳到下一条产生式进行查找 continue; for(k=0;k+) if(vk=rightj0)/求右部第一个字符在所

27、有字符集中得位置 k break; if(firstflagk="0") first2(k);/求其 first 集 firstflagk="1"/标识其为查找状态 merge(first1i,first1k,2);/求得结果并入到 x 得 first 集、 for(k=0;k(int)strlen(rightj);k+) empt0="0"/存放到一个临时数组里,标识此字符已查找其就是否可推出空字 if(_emp(rightjk)=1k(int)strlen(rightj)1) /当前产生式右部符号可推出空字,且当前字符不就是右部得

28、最后一个字符 for(m=0;m+) if(vm=rightjk+1)/获取右部符号下一个字符在所有字符集中得位置 break; if(firstflagm="0")/如果此字符得 first 集还未查找,则找其 first 集,并标其查找状态为 1 first2(m); firstflagm="1" merge(first1i,first1m,2);/把求得结果并入到 x 得 first集、 /产生式为 xy1y2yk,若对一切 1=i=k,均有first(yi),则将符号加进first(x) else if(_emp(rightjk)=1k=(int

29、)strlen(rightj)1) /当前右部符号串可推出空且就是右部符号串得最后一个字符 temp0="" temp1="0" merge(first1i,temp,1);/把空字加入到当前字符 x 得 first 集、 else break;/不能推出空字则结束循环 firstflagi="1"/标识当前字符 c 已查找其 first 集 /* 求各产生式右部得 first */ void first(int i,char *p) /指针 p 指向右部符号串 int length;/标识右部符号串得长度 int j,k,m; ch

30、ar temp20; length=strlen(p); if(length=1) /如果右部为单个符号 if(p0="")/右部符号串字符为空字 if(i=0)/i 不为 1 时就是产生式得序号 firsti0="" /把加入到当前符号串得 first 集 firsti1="0" else/i为1时,表示求follow时用到得产生式右部得first集,保存在temp中 temp0="" temp1="0" else/右部符号串字符不为空字 for(j=0;j+) if(vj=p0)/求右部符号

31、得第一个字符 p0在所有字符集中得位置 j break; if(i=0) memcpy(firsti,first1j,strlen(first1j);/把 j 所指向得单个符号得 first集拷贝到该右部符号串得 first 集 firstistrlen(first1j)="0" else memcpy(temp,first1j,strlen(first1j); tempstrlen(first1j)="0" else /如果右部为符号串 for(j=0;j+) if(vj=p0)/求右部符号得第一个字符 p0在所有字符集中得位置 j break; if

32、(i=0) merge(firsti,first1j,2); else merge(temp,first1j,2); for(k=0;k=length1;k+) empt0="0" if(_emp(pk)=1klength1) /当前产生式右部符号可推出空字,且当前字符不就是右部得最后一个字符 for(m=0;m+) if(vm=rightik+1) break; if(i=0) merge(firsti,first1m,2); else merge(temp,first1m,2); else if(_emp(pk)=1k=length1) /当前右部符号串可推出空且就是右

33、部符号串得最后一个字符 temp0="" temp1="0" if(i=0) merge(firsti,temp,1); else merge(temp,temp,1); else if(_emp(pk)=0) break; /* 求各产生式左部得 follow */ void follow(int i) /参数 i 为该符号在非终结符中得位置 int j,k,m,n,result=1; char c,temp20; c=non_teri; /c 为待求得非终结符 temp0=c; temp1="0" merge(foll,temp,

34、1);/把当前字符放到一临时数组 foll中,标识求已求其 follow 集、避免循环递归 if(c=start) /若为开始符号开始符号 s,则#follow(s) temp0="#" temp1="0" merge(followi,temp,1); for(j=0;j=count1;j+) if(in(c,rightj)=1) /找一个右部含有当前字符 c 得产生式 /比如求 follow(b)则找 ab 或 ab(=*)得产生式 for(k=0;k+) if(rightjk=c) break; /k 为 c 在该产生式右部得序号,如 b 在产生式

35、ab中得位置 for(m=0;m+) if(vm=leftj) break; /m 为产生式左部非终结符在所有符号中得序号 /如果 c 在产生式右部得最后,形如产生式 ab,则 follow(a)follow(b) if(k=(int)strlen(rightj)1) if(in(vm,foll)=1)/查找该非终结符就是否已经求过其 follow 集、避免循环递归 /就是则 follow(a)follow(b) merge(followi,followm,1);/把 c 所在产生式得左部非终结符得follow 集加入到 follow(c)中 continue;/结束本次循环,进入 j+循环

36、if(followflagm="0") /如果该非终结符得 follow 未求过 follow(m);/求之 follow 集 followflagm="1"/标识为 1 merge(followi,followm,1);/follow(a)follow(b) else /如果 c 不在产生式右部得最后,形如 ab for(n=k+1;n=(int)strlen(rightj)1;n+) empt0="0"/把 empt置空,因为求此字符就是否可推出空字_emp(c)时用到 result*=_emp(rightjn); if(resu

37、lt=1) /如果右部 c 后面得符号串能推出空,ab(=*)则follow(a)follow(b) if(in(vm,foll)=1) /查找该非终结符就是否已经求过其 follow 集、避免循环递归 merge(followi,followm,1);/follow(a)follow(b) continue; if(followflagm="0") follow(m); followflagm="1" merge(followi,followm,1); /若 ab,其中 bvn,(vt u vn)*、(vt u vn)+,则 first()follow

38、(b); for(n=k+1;n=(int)strlen(rightj)1;n+) tempnk1=rightjn; tempstrlen(rightj)k1="0" first(1,temp);/求 first() merge(followi,temp,2);/ 把 first( ) 中 所 有 非 空 元 素 加 入 到follow(b)中 followflagi="1"/标识当前要求得非终结符得 follow 集已求过 /* 判断读入文法就是否为一个 ll(1)文法 */ int ll1 int i,j,length,result=1; char

39、temp50; for(j=0;j=49;j+) /初始化 firstj0="0" followj0="0" first1j0="0" selectj0="0" tempj="0" tempj="0" firstflagj="0"/用来记录该字符得 first 集就是否已求过、1 表示已求,0 表示未求 followflagj="0"/用来记录该字符得 follow 集就是否已求过、1 表示已求,0 表示未求 for(j=0;j=(in

40、t)strlen(v)1;j+) first2(j); /求单个符号得 first 集合,结果保存在 first1里 printf(n 各非终结符推出得 first 集:n); for(j=0;j=(int)strlen(v)1;j+) printf(%c:%s ,vj,first1j); printf(n 能导空得非终结符集合:%s,empty); printf(n_emp:); for(j=0;j=(int)strlen(v)1;j+) printf(%d ,_emp(vj); for(i=0;i=count1;i+) first(i,righti); /求 first for(j=0;j

41、=(int)strlen(non_ter)1;j+) /求 follow if(follj=0) foll0="0" follow(j); printf(nfirst 集:); for(i=0;i=count1;i+) printf(%s ,firsti); printf(nfollow 集合:); for(i=0;i=(int)strlen(non_ter)1;i+) printf(%s ,followi); for(i=0;i=count1;i+) /求每一产生式得 select 集合 memcpy(selecti,firsti,strlen(firsti);/firs

42、t存放得就是各产生式右部得 first 集 selectistrlen(firsti)="0" for(j=0;j=(int)strlen(righti)1;j+) result*=_emp(rightij); if(strlen(righti)=1righti0="")/形如产生式 a result=1; if(result=1) for(j=0;j+) if(vj=lefti)/j 为左部符号在所有字符集中得位置 break; merge(selecti,followj,1); printf(nselect 集合顺序就是:); for(i=0;i=count1;i+) printf(%s ,selecti); memcpy(temp,select0,strlen(select0); tempstrlen(select0)="0" for(i=1;i=count1;i+) /*判断输入文法就是否为 ll(1)文法*/ length=strlen(temp); if(lefti=lefti1) merge(temp,selecti,1); if(strlen(temp)