2022年递归下降分析程序的实现合肥工业大学编译原理课程设计报告 .pdf

课 程 设 计 报 告设计题目17. 递归下降分析程序的实现设计要求对文法 G: EE+T|T TT*F|F F（E）|i 构造出 G的递归下降分析程序。 程序显示输出匹配过程 （即自上而下生成语法分析树的步骤，输出各匹配产生式序号即可）。设计思路（1）分析a) E=E+T=E+T*F=E+T*(E) 即有 E=E+T*(E)存在左递归。用直接改写法消除左递归，得到如下：E TE E +TE | -TE| T FT T *FT | /FT| F (E) | i b) 对于以上改进的方法。可得：对于 E:FIRST( E )=FIRST(+TE) FIRST(-TE )=+，- ， 对于 T:FIRST( T )=FIRST(*FT )FIRST(/FT ) = * ， ， 而且：FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST(E) FIRST(i)= (，i 由此得出各非终结符的FOLLOW 集合如下：FOLLOW( E )= ) ，#名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - FOLLOW(E )= FOLLOW(E)= ) ，#FOLLOW( T )= FIRST(E )FOLLOW(E )=+ ，- ，)，#FOLLOW( T ) = FOLLOW( T ) =+ ，- ，)，#FOLLOW( F )=FIRST(T ) FOLLOW(T )=* ， ，+，- ，)，#由以上 FOLLOW 集可以我们可以得出SELECT 集如下：对 E SELECT（ETE ）=FIRST(TE)=FIRST(T)= ( ，i 对 ESELECT（E +TE ）= + SELECT（E -TE ）= - SELECT（E ）= ，)，#对 T SELECT（TFT ）=( ，i对 TSELECT（T *FT ）= * SELECT（T FT）= SELECT（T ）= ，+，- ，)，#对 F SELECT（F(E) ）= ( SELECT（Fi）= i SELECT(E +TE )SELECT （E -TE ）SELECT （E ）=SELECT(T *FT) SELECT（TFT）SELECT （T ）=SELECT（F(E) ）SELECT （Fi）= 由上可知，有相同左部产生式的SELECT 集合的交集为空，所以文法是LL（1）文法。因此，转化后的文法可以用递归下降分析法作语法分析。（2）设计这里采用递归下降分析法形象描述递归子程序。程序中将要用到的几个重要数据如下：一个全局变量 ch，存放由文件输入得到的字符。一个函数宏 READ(ch)，实现读取文件中的字符。五个子函数： P(E)、P(E)、P(T)、P(T)、P(F)。课程设计源程序/* 文件描述：递归下降语法分析器。分析如下方法：* E-E+T | E-T | T* T-T*F | T/F |F名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - * F-(E) | i * * 输入：每行含一个表达式的文本文件。* 输出：分析成功或不成功信息。* 创建人：赵有斌*/#include#include#define READ(ch) ch=getc(fp) /*宏：READ(ch)*/charch; /*声明为全局变量 */int right=0; FILE *fp;structstruCHchar ch;struct struCH *next;struCH,*temp,*head,*shift;/*head指向字符线性链表的头结点*/*shift 指向动态建成的结点 (游标 )*/void main(intargc,char *argv)void E (); /* P(E) */void E1(); /* P(E)*/void T (); /* P(T) */void T1(); /* P(T)*/void F (); /* P(F) */interrnum=0,k=0,m=0,countchar=0,rownum;intcharerr=0;/*开关控制量 */名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - /*以只读方式打开文件 */if(fp=fopen(argv1,r)=NULL) printf(ntCan not open file %s,or not exist it!n,argv1);exit(0); /*文件不存在 or 打不开时，正常退出程序*/else printf(ntSuccess open file: %sn,argv1); /*成功打开文件 */*遍历整个文件检测是否有非法字符*/*如果用 while(!feof(fp) 语言，将会多出一个字符*所以这里采用以下方法遍历整个文件检测其否有非法字符*/ /*1 计算文件中字符数量 */while(!feof(fp) READ(ch); /*这里读取字符只是让文件指针往前移*/countchar+; /*统计文件中的字符数 (包括换行符及文件结束符)*/rewind(fp); /*将 fp 文件指针重新指向文件头处，以备后面对文件的操作 */if(countchar=0) /*空文件 */printf(t%s is a blank file!n,argv1); exit(0); /*正常退出本程序 */ /*2 开始遍历文件 */while(k(countchar-1) ch=getc(fp); if(!(ch=(|ch=)|ch=i|ch=+|ch=-|ch=*|ch=/|ch=#|ch=n) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - charerr=1;errnum+; /*charerror 出错标记， errnum 统计出错个数 */k+; rewind(fp); /*将 fp 文件指针重新指向文件头处， 以备后面的建链表操作*/if(charerr=1 /*文件中有非法字符 */printf(nt%dUnindentify characters in file %s n,errnum,argv1);exit(0); /*正常退出本程序 */*非空且无非法字符，则进行识别操作*/for(rownum=1;mnext=NULL;head=shift;/*读取一行形成线性链表 */READ(ch);putchar(ch);m+;while(ch!=n&mch=ch;temp-next=NULL;shift-next=temp;shift=shift-next;READ(ch);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - if(m!=(countchar-1) putchar(ch); /*不输出最后一次读取的文件结束符*/m+;head=head-next; /*消去第一个空头结点 ,并使 head指向非空线性链表头*/shift=head; /*shift 指向头结点，以便后面识别操作*/putchar(n);E(); /*开始识别一行 */ if(shift-ch=#&right) /* 正确提示 :文件名 Line 行号 :right expression!*/printf(%s Line %d:t right expression!n,argv1,rownum);else /*错误提示 :文件名 Line 行号 :error expression!*/printf(%s Line %d:t error expression!n,argv1,rownum); putchar(n);printf(Completed!n);fclose(fp); /*关闭文件 */exit(0); /*正常结束程序 */*以下函数分别对应于子模块程序*/ void E() T();E1();void E1() if(shift-ch=+|shift-ch=-) shift=shift-next;T();名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - E1();else if(shift-ch=#|shift-ch=)return;elseright=0;void T(void) F();T1();void T1(void) if(shift-ch=*|shift-ch=/) shift=shift-next;F();T1();else if(shift-ch!=#&shift-ch!=)&shift-ch!=+&shift-ch!=-)right=0; /* 如果不是 #or)or+or+or-则出错 */void F(void) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - if(shift-ch=i)shift=shift-next;elseif(shift-ch=() shift=shift-next;E();if(shift-ch=)shift=shift-next;elseright=0;elseright=0;运行结果记录名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 程序结果分析通过测试所给数据， 测试结果均与预期结果一致， 验证了程序的可行性， 较好的解决了递归下降分析程序的问题。课程设计总结这次的课程设计让我对编译原理这门课程解决实际的问题有了一个新的认识：解决一个问题首先要对其所属的结构进行一个分析，然后再运用自己所学的文法类型进行编程求解。例如所给文法：E=E+T =E+T*F =E+T*(E) 即有 E=E+T*(E)存在左递归，因此必须消除左递归，可以采取提取公因子的方法消除左递归。通过这次课程设计， 我掌握了自上而下语法分析法的特点。掌握了递归下降语法分析的基本原理和方法。运用递归下降分析法完成了本试验的语法分析构造，并且成功的分析出每种正确的句子和错误的句子。函数的构造是根据文法分析的递归过程， 所编写每个函数的功能， 以文法的右部为函数名， 对应的左部为相应分析过程。 此分析法简单， 直观，易构造分析程序， 但是不适于文法过于复杂的，不易检查出错误。 在课程设计的过程中， 遇到了一些问题， 都是粗心大意而造成，并非是对文法分析和编程的熟悉问题，说明了我再以后的试验中应该更细心的编写程序的每一步， 对于本次课程设计所出现的马虎，应该牢记， 以后不再犯同样的错误。通过这次课程设计，也让自己更加的了解递归下降语法分析器。总之，通过这次课程设计使自己受益良多，我相信别的同学也得到的不少！最后非常感谢各位老师为我们辛勤的付出以及给与我们编译原理学习方面的帮助。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -