编译原理词法分析语法分析实验报告

1、本文档如对你有帮助，请帮忙下载支持！编译原理实验报告LL（1） 文法分析1.设计要求（1）对输入文法，它能判断是否为 LL（1） 文法，若是，则转（ 2）；否则报错并 终止；（2）输入已知文法，由程序自动生成它的 LL（1） 分析表；（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。2.分析该程序可分为如下几步：1）读入文法2）判断正误3）若无误，判断是否为 LL（1） 文法4）若是，构造分析表；5）由总控算法判断输入符号串是否为该文法的句型。#include<string.h>int count=0;/* 分解的产生式的个数 */int number;/* 所有终结符

2、和非终结符的总数 */char start;/* 开始符号 */char termin50;/* 终结符号 */char non_ter50;/* 非终结符号 */char v50;char left50;char right5050;/* 所有符号 */ /* 左部 */ /*右部 */char first5050,follow5050;/*各产生式右部的 FIRST 和左部的 FOLLOW 集合*/本文档如对你有帮助，请帮忙下载支持！char first15050; char select5050;char f50,F50;/*所有单个符号的 FIRST 集合 */*各单个产生式的 SEL

3、ECT 集合*/* 记录各符号的 FIRST 和 FOLLOW 是否已求过 */char empty20; char TEMP50; int validity=1;/*记录可直接推出 的符号 */*求 FOLLOW 时存放某一符号串的 FIRST 集合 */ /* 表示输入文法是否有效 */int ll=1;int M2020; char choose; char empt20; char fo20;/*表示输入文法是否为 LL(1) 文法*/ /* 分析表 */* 用户输入时使用 */* 求 _emp()时使用 */*求 FOLLOW 集合时使用 */判断一个字符是否在指定字符串中int i

4、n(char c,char *p)int i;if(strlen(p)=0)return(0);for(i=0;i+)if(pi=c)return(1);/* 若在，返回 1*/if(i=strlen(p)return(0);/* 若不在，返回 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 temp20,ch;本文档如对你有帮助，

5、请帮忙下载支持！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!='|'&&pointj!='0')tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);

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

7、tcountm=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 m=0,j;char temp20;for(j=3;j<=strlen(point)-1;j+)if(poin

8、tj!='|')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,char right5050) char vn50,vt50;char s;本文档如对你有帮助，请帮忙下载支持！char

9、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(" 请输入文法的开始符号： ");scanf("%c",&am

10、p;s);getchar();printf(" 请输入文法产生式的条数： ");scanf("%d",&i);getchar();for(j=1;j<=i;j+)",j,i);printf("请输入文法的第 %d条(共 %d条)产生式： scanf("%s",pj-1);getchar();for(j=0;j<=i-1;j+)if(pj1!='-'|pj2!='>') printf("ninput error!");validity=0;

11、return('0');/* 检测输入错误 */for(k=0;k<=i-1;k+) /* 分解输入的各产生式 */ if(pk3=pk0) recur(pk);elsenon_re(pk);return(s);/*将单个符号或符号串并入另一符号串本文档如对你有帮助，请帮忙下载支持！void merge(char *d,char *s,int type) '一并并入目串； /*d 是目标符号串， s 是源串， type 1，源串中的 type 2，源串中的 '不并入目串 */int i,j;for(i=0;i<=strlen(s)-1;i+)if(t

12、ype=2&&si='')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)/* 即求所有由 '推出的符号 */char temp10;int i;for(i=0;i<=count-1;i+)if(righti0=c&&strlen(righti)=1)temp0=lefti;temp1='0'merge(emp

13、ty,temp,1);emp(lefti);求某一符号能否推出本文档如对你有帮助，请帮忙下载支持！*/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 为右部的长度 */ if(j=1&a

14、mp;&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<count)continu

15、e;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,term

16、in)=0&&rightij!='') '，报错 */* 若右部某一符号不在非终结符、终结符中且不为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=''emp(ch);if(in(c,termin)=1)/* 若为终结符 */first1i0=c;first1i1='0'

17、;else if(in(c,non_ter)=1) /* 若为非终结符 */本文档如对你有帮助，请帮忙下载支持！for(j=0;j<=count-1;j+)if(leftj=c)if(in(rightj0,termin)=1|rightj0='')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);f

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

19、9;'temp1='0'merge(first1i,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='')if(i>=0)firsti0=''firsti1='0'elseTEMP0=''TEMP1=

20、'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' else /* 如果右部为符号串 */for(j=0;j+)if(vj=p0)break;if(i>=0)merge(firsti,first1j,2);elsem

21、erge(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);else merge(TEMP,first1m,2);else if(_emp(pk)=1&&k=length-1)temp0=''temp1='0'if(i>=0) merge(firsti,temp

22、,1);elsemerge(TEMP,temp,1);else if(_emp(pk)=0)break;本文档如对你有帮助，请帮忙下载支持！求各产生式左部的 FOLLOW*/void FOLLOW(int i)int j,k,m,n,result=1;char c,temp20;c=non_teri; /*c 为待求的非终结符 */ temp0=c;temp1='0'merge(fo,temp,1); if(c=start)/* 若为开始符号 */temp0='#'temp1='0' merge(followi,temp,1); for(j=0;

23、j<=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,followm,1); continue;if(Fm='0')FOLLOW(m); Fm='1'

24、; merge(followi,followm,1);else /*如果 c 不在产生式右部的最后 */ for(n=k+1;n<=strlen(rightj)-1;n+) 本文档如对你有帮助，请帮忙下载支持！empt0='0'result*=_emp(rightjn);if(result=1)/*如果右部 c 后面的符号串能推出 */if(in(vm,fo)=1) /* 避免循环递归 */ merge(followi,followm,1); continue;if(Fm='0')FOLLOW(m);Fm='1'merge(followi,

25、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'/*判断读入文法是否为一个 LL(1) 文法*/int ll1()int i,j,length,result=1;char temp50;for(j=0;j<=49;j+)/* 初始化 */firstj0='0'followj0='0'first1j0=&#

26、39;0'selectj0='0'TEMPj='0'tempj='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,first1j); printf("nempty:%s",empty

27、); 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); /* 求 FIRST*/ printf("n");for(j=0;j<=strlen(non_ter)-1;j+) /* 求 FOLLOW*/if(foj=0)fo0='0' FOLLOW(j); printf("nfirst:"); for(i=0;i<=

28、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 集合 */ memcpy(selecti,firsti,strlen(firsti);selectistrlen(firsti)='0' for(j=0;j<=strlen(righti)-1;j+) res

29、ult*=_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);tempstrlen(se

30、lect0)='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);/*构造分析表 M*/void MM()

31、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;j<=strlen(selecti)-1;j+)if(in(selectij,termin)=1)for(k=0;k+)本文档如对你有帮助，请帮忙下

32、载支持！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='#'S1=start;S2='0'j=0;ch=strj;while(1)if(in(S

33、strlen(S)-1,termin)=1)if(Sstrlen(S)-1!=ch)printf("n 该符号串不是文法的句型！ ");return;else if(Sstrlen(S)-1='#')printf("n 该符号串是文法的句型 ."); return;else Sstrlen(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(

34、k=strlen(termin)printf("n 词法错误！ "); return;if(Mik=-1)printf("n 语法错误！ ");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("nS:%s str:",S);for(p=j;p<=s

35、trlen(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_t

36、er,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); printf("ntermin:%s",termin); printf("nright:");for(i=0;i<=count-1;i+)printf("%

37、s ",righti); printf("nleft:"); for(i=0;i<=count-1;i+)printf("%c ",lefti);if(validity=1) validity=judge();printf("nvalidity=%d",validity);if(validity=1) printf("n 文法有效 ");ll=ll1(); printf("nll=%d",ll);if(ll=0)printf("n 该文法不是一个 LL1 文法！ &qu

38、ot;);本文档如对你有帮助，请帮忙下载支持！elseMM();printf("n");for(i=0;i<=19;i+)for(j=0;j<=19;j+)if(Mij>=0)printf("M%d%d=%d ",i,j,Mij);printf("n");menu();5.执行结果(1) 输入一个文法(2) 输入一个符号串(3) 再次输入一个符号串，然后退出程序 二词法分析 一、 问题描述识别简单语言的单词符号识别简单语言的基本字、标识符、无 符号整数、运算符和界符。1.题目 选择计算机高级程序语言之一 C 语言，运

39、用恰当的词法 分析技术线路，设计和实现其对应的词法分析器。2.要求1) . 给出一简单语言单词符号的种别编码。单词符号 种别编码begin1if2then本文档如对你有帮助，请帮忙下载支持！while4do5end6l ( l | d ) *10dd *112）. 词法分析程序的功能 . 输入是源程序字符串 ,以#'结 束。 输出是单词符号的二元组。 分析器输出结果存入到磁盘文件中，具有出错处理功能。3）. 建议和提示： 技术线路选择如下两种之一： 正则式 NFADFAmin DFA程序设计 或正则文法 NFADFAmin DFA程序设计。系统分析 词法分析器对应的正则文法表达如下：

40、S 标示符或关键字 |数字字符 |运算符 标示符或关键字 character AA character |number|（标示符或关键字要以字母开头）数字字符 number| （数字字符只能由数字组成 ）本文档如对你有帮助，请帮忙下载支持！character a|b|c |y|z|A|B|C |Y|Znumber 0|1|2|3|4|5|6|7|8|9运算符 <>|<|<=|>|>=|:|:=|+|-|*|/|=|;|(|)|n 该词法分析程序要识别的字符类别包括关键字，标示符， 数字字符，运算符，结束符 '#'。这里把关键字和标示符归为同

41、一类，识别完之后根据查标示符表得到是标示符还是关键字。 因此对于自动机 DFA 来说，有几个相应的状态， 对应识别不同 单词串。当然词法分析程序还要有过滤空格字符，注释符号， 回车换行符等一些特殊字符。 当词法分析器遇到符号 '#'的时候 就表示词法分析已经完成，程序结束。字母数字字母或数字 数字空格或回车结束空格或回车三、 系统设计 基于以上的讨论，我设计了本实验词法分析器的有限自动机的 状态图。DFA 图流程说明：本文档如对你有帮助，请帮忙下载支持！每当读入完一个字符串后，自动机回到开始状态 S，读入 下一个字符串的第一个字母。这里所说的字符串是指标示符或 者关键字或者数字

42、或者特殊符号。当读入的第一个字符是字母的时候说明这个状态机要识别 的是标示符或者字符串，后面的字符可以是字母或者数字。所 以在标示符或关键字状态的时候读入的下一个字符是字母或者 是数字的时候其状态还是会转向自己；当读入的下个字符是回 车或空格的时候表示识别完成；当读入的下个字符是特殊符号 的时候（非字母或数字）按正常思维状态应转向出错处理，不 过由于本实验是词法分析，标示符不合法应该是语义分析阶段 做的事，所以本程序没有给出出错处理。识别字符串后还应区 分这个单词是标示符还是关键字。实现过程是查关键字表，将 识别的字符串同关键字表中的每一个元素比较，若有相同则说 明识别的是关键字，否则是标示符

43、。当读入的第一个字符是数字的时候说明这个状态机要识别 的是数字。后面的字符可以是数字，表示多位数。所以在数字 状态的时候读入的下一个字符是数字的时候其状态还是会转向 自己；当读入的下个字符是回车或空格的时候表示识别完成； 当读入的下个字符非数字时候，会发生语义错误，本程序是词 法分析所以没有给出。当读入的第一个字符是特殊字符的时候说明这个状态机要 识别的是特殊字符。双目特殊字符 （ 如:=,>=等 ）后面的字符还可本文档如对你有帮助，请帮忙下载支持！以是特殊字符。所以在特殊字符状态的时候读入的下一个字符是特殊字符的时候其状态还是会转向自己；当读入的下个字符是回车或空格的时候表示识别完成；

44、当读入的下个字符非数字时候，状态机理应转向出错处理，不过本程序同样没有给出。最后程序读入符号 #'时，说明源程序读入完毕，程序结 束。四系统实现程序流程图如下所示：打开要识别的源程序文件，初调始用扫化关描子键程字序表。， 对每个字符串 输出扫描，识别所属类型。 每个单词二元组。程序结束其中 syn=0，表示读到的字符是 #'。关键字表设置代码如下：char * rwtab6= “begin ” , “if ”, “ then ”, “while“do” , “ end” ;这里只给出了六个常用的关键字，真正的编译器的话应该给出所有的关键字。扫描子程序算法：本文档如对你有帮助，请

45、帮忙下载支持！字母标示符或关键字单词缓冲数组token 置为空。跳过空格，读入第一个字符。判断第一个字符运算符 空格回车过滤掉 syn=0查关键字表 拼数 置对应的 syn 值匹配否则 置 syn=11关键字 标示符置 syn=1-6 置 syn=10程序源代码如下：#include<stdio.h>#include<string.h>tokenchar prog80, token8; /prog 存储源程序字符串， 存储单个字符char ch;FILE * fp;int syn, p, m, n ,sum ;char *rwtab6= "begin"

46、;,"if","then","while","do","end" ;void scaner();void main(int argc,char* argv)本文档如对你有帮助，请帮忙下载支持！p=0;fp=fopen("./input.txt","r"); if(!fp) printf("File open error!n"); do ch=getc(fp);progp+=ch ; while ( ch!='#');p=

47、0;fp=fopen("./output.txt","w"); if(!fp) printf("File open error!n");do scaner();switch(syn)case 11:fprintf (fp,"%2d",syn);fprintf (fp,"%8dn",sum);break; /输出数字 case -1:fprintf(fp,"inpu t errorn"); break;/ 出错case 29: break;/过滤回车default:fprint

48、f (fp,"%2d",syn);/输出保留字或者标识符fprintf (fp,"%8sn",token);本文档如对你有帮助，请帮忙下载支持！while (syn!=0);fclose(fp);void scaner() / 词法扫描子程序m=0,sum=0;for ( n=0; n<8; n+ ) tokenn=NULL; /token 置为空 ch=progp+; /读入源程序中的一个字母 while (ch=' ') ch=progp+ ; / 跳过空格 if(ch>='A'&&ch&l

49、t;='Z')|(ch>='a'&&ch<='z')while/为字 (ch>='A'&&ch<='Z')|(ch>='a'&&ch<='z')|(ch>='0'&&ch<='9') 母字符或数字字符tokenm+=ch; ch=progp+;tokenm+='0' / 插入空格p-;syn=10;/种别编码/如果 token

50、 存储for (n=0 ; n<6; n+ )if(strcmp(token, rwtabn)=0)本文档如对你有帮助，请帮忙下载支持！的是保留字，重新确定 syn 的值syn=n+1; break ;elseif (ch>='0'&&ch<='9') while (ch>='0'&&ch<='9')sum=sum*10+ch-'0' ch=progp+;p- ;syn=11; /数字的 syn 为 11elseswitch(ch)case '&

51、lt;':m=0; tokenm+=ch;ch=progp+;本文档如对你有帮助，请帮忙下载支持！if (ch='>') /字符为 <> syn=21; tokenm+=ch; else if (ch='=') /字符为 <= syn=22; tokenm+=ch;else syn=20; /字符就是 < p-;break;case '>':m=0; tokenm+=ch;ch=progp+;if (ch='=') /字符为 >= syn=24; tokenm+=ch; else

52、/字符为 > syn=23;p-;break;case ':':m=0; tokenm+=ch;ch=progp+;if (ch='=') /字符为 := syn=18; tokenm+=ch; else/ 字符为： syn=18; p-; break;本文档如对你有帮助，请帮忙下载支持！case '+': syn=13; token0=ch; break;case '-': syn=14; token0=ch; break;case '*': syn=15; token0=ch; break;case '/': syn=16; token0=ch; break;case '=': syn=25; token0=ch; break;case '': syn=26; token0=ch; break;case &