编译原理课程设计——算符优先分析法研究——附源程序

1、目 录1 课程设计的目的和要求21.1 课程设计的目的21.2 课程设计的要求22 系统描述22.1 自底向上分析方法的描述:22.2 算符优先文法的描述：23）输入符号串，进行移进-规约分析。33 概要设计33.1 设计思路33.2 系统功能结构43.3 技术路线或实现方法53.4 开发环境54 详细设计54.1 模块划分54.2主要算法的流程图74.3 数据分析与定义84.4 系统界面设计85 测试方法和测试结果95.1 测试用例195.2 测试用例2105.3测试用例3115.4 测试用例4126 结论和展望13结论13展望13学习编译技术课程的体会和对本门课程的评价137 参考文献13

2、8 源代码141 课程设计的目的和要求1.1 课程设计的目的本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。1.2 课程设计的要求1、文法使用产生式来定义；2、用大写字母和小写字母分别表示非终结符和终结符；产生式使用->；3、文法中的空字符串统一使用表示；4、分别给出每一个非终结符的FIRSTVT集和LASTVT集；5、画出算符优先关系表6、判定给定的文法是否是算符优先文法；7、给定符号串判定是否是文法中的句子，分析过程用分析表格的方式打印出来。2 系统描述本次实验使用window

3、s vista操作系统下visual C+6.0平台，使用C语言，利用读文件方式将待分析的文法读入到程序中，通过定义数组和结构体作为具有一定意义或关系的表或栈，存放FIRSTVT、LASTVT、算符优先关系表的元素。系统能够对由文件读入的文法进行分析，构造出FIRSTVT表和LASTVT表以及算符优先关系表。可以根据构造的优先关系表对输入的任意符号串进行分析，判断是否为本文法的句子，若是则打印规约过程。结果显示到DOS界面上。2.1 自底向上分析方法的描述:对输入的符号串自左向右进行扫描，并将输入符逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时（该句柄对应某个产生式的右部），就

4、用该产生式的左部非终结符代替相应右部的文法符号串，这一过程称为规约。重复这一过程，直到栈中只剩下文法的开始符则分析成功。2.2 算符优先文法的描述：只规定算符之间的优先关系，也就是说只考虑终结符之间的优先关系。由于算富有先分析不考虑非终结符之间的优先关系，在规约过程中只要找到最左素短语就可以规约。如给定一个文法GS：S->#E#E->E+TE->TT->T*FT->FF->P/FF->PP->(E)P->i利用算符优先文法分析过程处理如下：1）计算给定文法中任意两个终结符对(a,b)之间的优先关系，首先计算两个集合FIRSTVT(B)=b|

5、B->b或B->CbLASTVT(B)=a|B->a或B->aC表2-1FIRSTVT集和LASTVT集 SETFPFIRSTVT#+*/i(*/i(/i(i(LASTVT#+*/i)*/i)/i)i)2）计算三种优先关系，求出算符优先关系表：表2-2算符优先关系表+*/i()#+*/I()#3）输入符号串，进行移进-规约分析。3 概要设计3.1 设计思路1）首先在源程序相同的目录下创建一个txt文档，并在文档中输入待分析的文法。然后定义一个输入流文件，调用这个流文件中的open函数打开该txt文件，再定义一个二维数组通过循环接收读入的产生式。2）接着开始构造FIRST

6、VT、LASTVT、算符优先关系表。在构造表的时候首先定义了两个重要的结构体。一个结构体作为存放具有一定关系的一对非终结符和终结符，另一个结构体作为存放上述元素的栈，包括栈顶指针、栈底指针、栈的长度。既然定义了栈，就存在对栈的初始化、栈是否为空的判断、入栈、出栈操作，利用循环和指针的操作来定义这些函数，以完成元素的进栈和弹出。定义了这两个结构体，就可以用来构造FIRSTVT、LASTVT、算符优先关系表。在构造FIRSTVT表时，通过循环找出每条产生式中的非终结符的FIRSTVT集，并把该非终结符和终结符压栈，设置标志位，标志一对非终结符和终结符具有对应关系。LASTVT表的构造则是将求FIR

7、STVT的过程翻转过来，可以仅仅将函数中的参数稍作修改就能够完成。3）构造算符优先关系表。算符优先关系表是一个二维数组，用来存放任意两个终结符之间的优先关系。首先构造表头，通过扫描所有产生式将终结符不重复的存放在一个一维数组中并置为优先关系表的行和列，并将优先关系表其他内容全部初始化为空。接着遍历所有产生式，找出任意两个终结符之间存在的关系（可以没有关系），并判断任意两终结符是否至多存在一种优先关系，如发现优先关系表不为空，则证明该文法不是算符优先文法，否则，将相应的关系填入到相应的行列对应的单元中。4）输入串分析过程的设计。首先将大于、小于、等于和无关系分别定义成一种类型的数据表示，通过查询

8、符号栈栈顶以及当前符号之间的优先关系来判断移进和规约的操作。3.2 系统功能结构图3-1 系统功能结构图函数功能：Main()函数：调用主函数，运行程序；FirstVt()函数：构造FIRSTVT表；LastVt()函数：构造LASTVT表；OpPrioTable()函数：构造算符优先关系表；InputAnalyse()函数：分析输入串是否为文法中的句子，并给出规约过程。3.3 技术路线或实现方法算符优先分析法的具体过程如下：1、首先先输入文件的路径，在readfile(char sencol)函数中，将需要分析的文法通过输入流文件打开函数open()复制到senrowcol中。2、然后利用F

9、irstVt( )构造产生式senrowcol的FirstVt表。先找出形如A->a（a为第一个终结符）的产生式，把（A,a）压入Operator栈中。从Operator栈顶抛出项（A，a），填入first表相应位置。在找出形如B->A的产生式，把（B,a）压入Operator栈中。循环直到Operator栈为空，此时FirstVt表构造完毕。3、然后把产生式右部翻转，调用FirstVt函数求出LastVt表。4、接着调用OpPriotable（）构造算符优先关系表opTable。先把产生式中所有终结符填入opTable表第一行和第一列，然后利用产生式和FirstVt表LastVt

10、表分别找出满足=关系、<关系、>关系的算符填表。若相应位已有关系，说明两个终结符之间至少有两种优先关系，该文法不是算符优先文法。5、最后调用InputAnalyse（）对输入串进行分析。初始化分析栈S，依次判断当前输入符a和分析栈中离栈顶最近的终结符S j 的关系，若S j < a ，则a移近，若S j > a ，则往前找到第一个S j >a，将S j -1到栈顶S k 规约，若S j = a ，如果S j =#，则接受，如果S j ！=#，则移进。直到接受或者出错，算符优先分析结束。3.4 开发环境实验使用windows vista操作系统下的Microsoft

11、 Visual C+ 6.0平台，用C语言完成。4 详细设计4.1 模块划分实验分为五个模块，分别是：1、文件的导入：readfile（sen）；2、FirstVt、LastVt集的构造：FirstVt（sen,first,sen_len,frist_len）；LastVt（sen,last，sen_len,frist_len）；3、 算符优先关系表OpPriotable的构造：OpPriotable（sen,first,last,opTable,sen_len,first_len,&opTable_len）；4、算符优先分析过程的实现：InputAnalyse（opTablecol,

12、stringcol,opTable_len）；5、主函数：main（）。4.2 主要算法的流程图图4-1 算符优先分析法程序流程图4.3 数据分析与定义1、文法（产生式）：文法使用产生式来定义char senrowcol：用二维数组表示产生式；int sen_len：产生式的个数；2、FIRSTVT集：char firstrowcol：用二维数组构造FIRSTVT表int first_len: Firstvt表的行数;3、LASTVT集：char lastrowcol：用二维数组构造LASTVT表；int frist_len：LASTVT表的行数；4、算符优先关系表：char opTabler

13、owcol：用二维数组表示算符优先关系表；int opTable_len：算符优先关系表的行数和列数；5、算符优先分析表char stringcol：用一维数组记录输入串；char SSIZE：用一维数组表示分析栈 ；char a：当前输入字符；6、其他数据结构：typedef structchar nonterm; /非终结符char term; /终结符StackElement;FIRSTVT表或LASTVT表中一个表项（A,a）；7、typedef struct StackElement *top;StackElement *bottom;int stacksize;stack;以形如表

14、项（A,a）为元素的栈，在构造FirstVt集的过程中用到；4.4 系统界面设计本实验没有考虑界面设计，将结果直接打印输出在DOS界面下。5 测试方法和测试结果5.1 测试用例1测试目的：使用算符优先分析法对一个算符文法中的句子进行分析。读入一个算符优先文法进行分析，给出文件路径D:coursesC_source_file成品算符优先文法1.txt。结果如下：图5-1 测试用例1运行截图1输入一个字符串，使得该字符串是该文法的一个句子。则输入字符串i+i*i/(i+i)#时运行结果为：图5-2 测试用例1运行截图25.2 测试用例2测试目的：使用算符优先分析法，分析一个字符串不是该文法的句子，

15、并输出出错信息。输入一个字符串，使得该字符串不是文法的句子。图5-3 测试用例2运行截图5.3 测试用例3测试目的：读入一个文法，判断该文法不是算符优先文法。读入一个非算符优先文法进行分析，给出文件路径：D:coursesC_source_file成品非算符优先文法1.txt。运行结果如下：图5-4 测试用例3运行截图5.4 测试用例4测试目的：输入一个非算符文法，判断该文法不是算符文法。读入一个非算符文法，给出路径：D:coursesC_source_file成品非算符文法.txt。运行结果如下：图5-5 测试用例4运行截图6 结论和展望结论本次实验我们基本完成了实验题目的要求。求出了一个文

16、法中每一个非终结符的FIRSTVT集和LASTVT集，画出算符优先关系表，并判定出给定的文法是否是算符优先文法。当给定一个符号串时，能够判定是否是文法中的句子，并能够将分析过程打印出来。通过算符优先分析方法，可以对任意一个文法进行自底向上的分析。同时，算符优先分析法也存在不足之处，由于忽略文法中的非终结符，会将本不属于文法的句子正确规约，从而引起错误。展望本次实验完成了题目的要求，准确把握了将文法通过读文件形式、手动输入分析字符串的题目要求，并在满足要求的基础上进行了创新，添加了对算符文法的判断功能。实验中，小组成员的分工与合作充分体现了软件工程的思想。需求分析理解准确，小组成员任务明确，统一

17、函数头、参数，各自完成分内工作，整合工作快速、高效。同时，实验中还存在很多不足。调试程序中的错误占用了大部分时间，以至于没有考虑使用界面展示结果。虽然使用C+开发工具，但实质上还是在使用C编代码。在今后的实践中还需注意。学习编译技术课程的体会和对本门课程的评价在上编译课的时候，小组成员都觉得自己对算符优先文法已经掌握了，但等真正用程序去实现时，才发现有很多细节我当时没有注意到。也正以为没有注意到这些细节，导致成员们编程时会出现各种错误，大部分都是在循环时下标或者循环次数的控制上出错。在进行到一定阶段后发现犯的低级错误越来越少了，对算符优先文法也愈发的吃透了，编程水平也有了进一步的提高。编译原理

18、如果要深入研究，那会是一门非常深奥的学问，对于现阶段只有60多学时的本科生来说，只能涉及到它一些最基本的原理，和最宏观的方法，要想微观的去研究，还需要在以后的时间里去钻研。在这次实验中，小组成员也只是用高级语言模拟了编译的一个小方法，在完成实验的过程中，小组成员对编译原理有了进一步的了解，更提高了动手编程能力，是一次经验和知识的积累。7 参考文献 1 张素琴编译原理（第2版）M. 北京：清华大学出版社，2005.6，102-121.2 陈维兴C+面向对象程序设计教程M. 北京：清华大学出版社，2004.8，258-272.8 源代码#include<iostream.h>#incl

19、ude<stdlib.h>#include <fstream.h>#define row 50#define col 50#define SIZE 50/两个重要结构体的定义/FIRSTVT表或LASTVT表中一个表项（A,a）结构体的初始化typedef structchar nonterm; /非终结符char term; /终结符StackElement;/存放（A,a）的栈的初始化typedef struct StackElement *top;StackElement *bottom;int stacksize;stack;/初始化（A,a）栈void Ini

20、tStack(stack &S) S.bottom = new StackElementSIZE; if(!S.bottom) cout<<"存储空间分配失败！"<<endl; S.top = S.bottom; S.stacksize = SIZE;/判断（A,a）栈是否为空bool ifEmpty(stack S)if(S.top=S.bottom) return true; /如果栈为空，则返回trueelse return false; /否则不为空，返回false/插入栈顶（A,a）元素void Insert(stack &

21、S,StackElement e)if(S.top-S.bottom>=S.stacksize)cout<<"栈已满，无法插入！"<<endl;elseS.top->nonterm=e.nonterm;S.top->term=e.term;S.top+;/弹出栈顶（A,a）元素StackElement Pop(stack &S)StackElement e;e.nonterm = '0'e.term = '0'if(S.top=S.bottom)cout<<"栈为空，无法

22、进行删除操作！"<<endl; return e;elseS.top-; e.nonterm=S.top->nonterm;e.term=S.top->term;return e;/终结符与非终结符的判断函数（布尔类型）bool TerminalJud(char c)if(c>='A'&&c<='Z')return false; /非终结符返回falseelse return true; /终结符返回true/判断非终结符在first表中是否已存在bool ItemJud(char firstcol,

23、int frist_len,char C)for(int i=0;i<frist_len;i+)if(firsti0=C) return true; /如果first表中已存在此非终结符，则返回true return false;/读文件函数int readfile(char sencol)char addr50;cout<<"请输入要读文件的地址（用表示）："<<endl;cin>>addr;ifstream fin;fin.open(addr,ios:in);if(!fin)cout<<"Cannot op

24、en file!n"<<endl;for(int i=0;!fin.eof();i+)fin>>seni;cout<<seni<<endl;return i;/FIRSTVT表和LASTVT表中表项（非终结符）的初始化void ItemInit(char sencol,char firstcol,char lastcol,int sen_len,int &frist_len)int i;frist_len=1;first00=sen00;last00=sen00;for(i=1;i<sen_len;i+)if(Termin

25、alJud(seni0)=false && ItemJud(first,frist_len,seni0)=false) /k是当前first和last表的长度firstfrist_len0=seni0;lastfrist_len0=seni0;frist_len+;void FirstVt(char sencol,char firstcol,int sen_len,int frist_len) / frist_len 是 first 表的行数 sen_len是产生式的个数StackElement DFS,recordSIZE;stack Operator; /创建存放（A，a）

26、的栈InitStack(Operator); int i,j,r=0;for(i=0;i<sen_len;i+) /第一次扫描，将能直接得出的first（A，a）放进栈中for(j=3;senij!='0'j+)if(TerminalJud(senij)=true) /遇到的第一个终结符压入int exist=0;DFS.nonterm=seni0;DFS.term=senij;for(int i1=0;i<r;i+)if(recordi1.nonterm=seni0&&recordi1.term=senij)exist=1;break;record

27、r.nonterm=seni0;recordr.term=senij;if(exist=0)Insert(Operator,DFS);/A-aB A-aC (A,a)压栈两次?recordr.nonterm=seni0;recordr.term=senij;r+;break;int locationcol; /辅助数组，用来记录first表中放入终结符的位置for(i=0;i<frist_len;i+) locationi=1;while(!ifEmpty(Operator)int exist=0; /标志位，记录即将入栈的元素是否已经存在StackElement IDElement,D

28、Element;DElement=Pop(Operator); /弹出栈顶元素for(i=0;i<frist_len;i+)if(firsti0=DElement.nonterm)int n=locationi;firstin=DElement.term; /将终结符填入相应的first表中locationi+;break;for(j=0;j<sen_len;j+) if(senj3=DElement.nonterm) /找出能推出当前非终结符的产生式的左部 IDElement.nonterm=senj0;IDElement.term=DElement.term;/判断将要放进栈里

29、的元素曾经是否出现过，若没有，才压入栈for(int r0=0;r0<r;r0+) /r记录record数组中的元素个数if(recordr0.nonterm=IDElement.nonterm && recordr0.term=IDElement.term) exist=1;break; if(exist=0)Insert(Operator,IDElement);recordr.nonterm=IDElement.nonterm;recordr.term=IDElement.term;r+;/if/for/whilevoid LastVt(char sencol,cha

30、r lastcol,int sen_len,int frist_len) /firstvt表与lastvt表行数一样 first_len表示last 表的行数int i,j,i1,j1;char c,recordrowcol='0'for(i=0;i<sen_len;i+) for(j=0;senij!='0'j+)recordij=senij;j=j-1; for(i1=3,j1=j;i1<j1;i1+,j1-) /做翻转，就可以用求first的方法求lastc=recordii1;recordii1=recordij1;recordij1=c;/

31、forFirstVt(record,last,sen_len,frist_len);/判断非终结符在term表中是否已存在bool TermTableJud(char termcol,int term_len,char C) for(int i=0;i<term_len;i+)if(termi=C) return true; /如果first表中已存在此非终结符，则返回1 return false;/构造算符优先关系表bool OpPriotable(char sencol,char firstcol,char lastcol,char opTablecol,int sen_len,in

32、t first_len,int &opTable_len) int i,j,term_len=0;int i2,i3,opr,opc;char c1,c2,c3;char termSIZE='0'for(i=0;i<sen_len;i+) /一维数组term记录关系表中存在的所有终结符for(j=3;senij!='0'j+)if(TerminalJud(senij)=true) if(TermTableJud(term,term_len,senij)=false) /term_len记录term表的长度 termterm_len=senij; t

33、erm_len+; /得到终结符表 for(i=0;i<term_len+1;i+) /给优先关系表赋初值，都等于空for(j=0;j<term_len+1;j+)opTableij=' 'for(i=1;i<term_len+1;i+) /设置优先关系表的表头opTablei0=termi-1; opTable0i=termi-1; for(i=0;i<sen_len;i+) /找等于关系for(j=5;senij!='0'j+)if(TerminalJud(senij-2)=true&&TerminalJud(seni

34、j-1)=false&&TerminalJud(senij)=true)c1=senij-2; c2=senij; for(opr=1;opr<term_len+1;opr+) /在opTable表中找到该存入的行标oprif(opTableopr0=c1)break;for(opc=1;opc<term_len+1;opc+) /在opTable表中找到该存入的列标opcif(opTable0opc=c2)break;if(opTableopropc!=' ')cout<<"不是算符优先文法！"<<end

35、l;return false;elseopTableopropc='='/if/for(j)for(j=4;senij!='0'j+)if(TerminalJud(senij-1)=true&&TerminalJud(senij)=true)c1=senij-1;c2=senij;for(opr=1;opr<term_len+1;opr+) /在opTable表中找到该存入的行标oprif(opTableopr0=c1)break;for(opc=1;opc<term_len+1;opc+) /在opTable表中找到该存入的列标j2

36、if(opTable0opc=c2)break;if(opTableopropc!=' ')cout<<"不是算符优先文法！"<<endl;return false;elseopTableopropc='='/for(i)for(i=0;i<sen_len;i+) /找小于关系for(j=3;senij!='0'j+)if(TerminalJud(senij)=true&&TerminalJud(senij+1)=false)c1=senij; /c1记录终结符c2=senij+1

37、; /c2记录非终结符 for(opr=1;opr<term_len+1;opr+) /在opTable表中找到该存入的行标oprif(opTableopr0=c1)break;for(opc=0;opc<first_len;opc+) /找出非终结符在first表中的列标opcif(firstopc0=c2)break;for(i2=1;firstopci2!='0'i2+)c3=firstopci2;for(i3=1;i3<term_len+1;i3+)if(opTable0i3=c3)if(opTableopri3!=' ')cout&l

38、t;<"不是算符优先文法！"<<endl;return false;elseopTableopri3='<'break;/if/for(j)/for(i)for(i=0;i<sen_len;i+) /找大于关系for(j=3;senij!='0'j+)if(TerminalJud(senij)=false&&senij+1!='0'&&TerminalJud(senij+1)=true)c1=senij; /c1记录非终结符c2=senij+1; /c2记录终结符

39、for(opr=1;opr<term_len+1;opr+) /在opTable表中找到该存入的列标j1if(opTable0opr=c2)break;for(opc=0;opc<first_len;opc+) /找出非终结符在last表中的行标j2if(lastopc0=c1)break;for(i2=1;lastopci2!='0'i2+)c3=lastopci2;for(i3=1;i3<term_len+1;i3+)if(opTablei30=c3)if(opTablei3opr!=' ')cout<<"不是算符优先

40、文法！"<<endl;return false;elseopTablei3opr='>'break;/if/for(j)/for(i)opTable_len=term_len+1;return true;/判断两算符优先关系并给出类型供构造分析表int RelationshipJud(char c1,char c2,char opTablecol,int opTable_len)int i,j;for(i=1;i<opTable_len;i+)if(opTablei0=c1)break;for(j=1;j<opTable_len;j+)i

41、f(opTable0j=c2)break;if(opTableij='<')return 1;else if(opTableij='=')return 2;else if(opTableij='>') return 3;else return 4;/判断输入串是不是优先文法bool PrioGramJud(char sencol,int sen_len)int i,j;for(i=0;i<sen_len;i+)for(j=4;senij!='0'j+)if(TerminalJud(senij-1)=false&a

42、mp;&TerminalJud(senij)=false)cout<<"输入的不是算符文法!"<<endl;return false;return true;/开始分析输入串void InputAnalyse(char opTablecol,char stringcol,int opTable_len) /opTable_len是opTable表的长度char a,Q,SSIZE='0' /S是分析栈 char cho1,cho2;int i,j,relation;int k=0;Sk='#'cho2='

43、;y'cout<<"tttt分析过程如下："<<endl;cout<<"-"<<endl;/cout<<" 栈t当前字符t优先关系t移进或规约"<<endl;/cout<<"分析过程如下："<<endl;cout.width(10);cout<<"栈"cout.width(15);cout<<"当前字符"cout.width(20);cout<

44、<"剩余符号串"cout.width(15);cout<<"优先关系"cout.width(15);cout<<"移进或规约"<<endl;char* p;p=string;p+;for(i=0;stringi!='0'&&cho2='y'i+,p+)a=stringi; /读入当前字符cho1='n' /可否接受while(cho1='n') if(TerminalJud(Sk)=true)j=k; /规约使栈内

45、有非终结符 else j=k-1; relation=RelationshipJud(Sj,a,opTable,opTable_len); if(relation=3) /Sj>a/cout<<" "<<S<<"t"<<" "<<a<<"tt >tt"cout.setf(ios:left);cout.width(10);cout<<S;cout.unsetf(ios:left);cout.width(15);cout&l

46、t;<a;cout.width(20);cout<<p;cout.width(15);cout<<">"do Q=Sj; if(TerminalJud(Sj-1)=true) j=j-1; else j=j-2;while(RelationshipJud(Sj,Q,opTable,opTable_len)!=1);/cout<<" "<<Sj<<"归约"<<endl;cout.width(11);cout<<Sj;cout.width(4)

47、;cout<<"归约"<<endl;k=j+1; Sk='N'for(int l=k+1;l<SIZE;l+)Sl='0' else if(relation=1) /Sj<a cho1='y' /cout<<" "<<S<<"t"<<" "<<a<<"tt <tt 移进"<<endl; cout.setf(ios:left);cout.width(10); cout<<S;cout.unsetf(ios:left);cout.width(15);cout<<a;cout.width(20);cout<<p;cout.width(15);cout<<"<"cout.width(1