编译原理课程设计(共34页)

1、精选优质文档-倾情为你奉上编译原理课程设计 自顶向下语法分析器学 院（系）： 计算机科学与技术学院 学 生 姓 名： xxxxxxxxx 学 号： xxxxxxxxx 班 级： 电计1102 大连理工大学 Dalian University of Technology专心-专注-专业 目 录1 系统概论语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示：图1 语法分析器在编译程序中的地位语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是

2、否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产

3、生式谋求匹配输入串的过程。实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。2 需求分析以前，人们对语法的分析都建立在人工的基础上，人工分析虽然能够做到侧类旁推，但终究人力有限，再精密的分析都会出现或多或少的错误。为减少因人为产生的错误，并加快语法的分析，故设计了这个自顶向下的语法分析器。人们只要运行程序，输入几个简单的命令或语法，就能求出人们所需要的各种结果。虽然程序设计有一定的局限性，但在这个局限中

4、却能如人们的要求对语法进行分析，从而在一定程度上帮助人们更好的完成工作。3 系统设计自顶向下的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶自顶向下的分析程序有两类：回溯分析程序（backtracking parser）和预测分析程序（predictive parser）。预测分析程序试图利用一个或多个先行记号来预测出输入串中的下一个构造，而回溯分析程序则试着分析其他可能的输入，当一种可能失败时就要求输入中备份任意数量的字符。虽然回溯分析程序比预测分析程序强大许多，但它们都非常慢，一般都在指数的数量

5、级上，所以对于实际的编译器并不合适。递归下降程序分析和LL(1)分析一般地都要求计算先行集合，它们分别称作First集合和Follow集合。由于无需显式地构造出这些集合就可以构造出简单的自顶向下的分析程序。1、LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a )SELECT(A:=b)=Ø。这样，当前非终结符A面临输入符a时，如果aSELECT(A：=a)，则可以选择产生式A:=a去准确匹配。如本程序中举

6、例说明的a.txt的文法就是一个LL（1）文法： S:=aBc|bABA:=aAb|bB:=b|02、文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AÞA，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。3、直接左递归若文法中的某一产生式形如AA，V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：AA| （,V*，且不以A开头）对A引入一个新的非终结符A，把上式改写为：A A AA| 4、间接左

7、递归若文法中存在某一非终结符A，使得AÞA至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。 【方法二】直接改写文法：设有文法G10S： SA| AS 因为SÞAÞS，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将式代入式，即可得到与原文法等价的文法（可以证明）： SS| 式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：SSSS|4 系统实现 系统流程图5 使用说明5.1 程序运行平台Visual C+ 6.0Windows XP SP25.2 程序中所

8、有定义的函数class Syntax_analysis public: char stotax3020; /存放文法规则 char soudocu1000; /用于存放打开的文件内容 int sto_tax; /存放产生式总数 char firstchars30; /某个串的first集(可能有重复) int first_num; /first集长度 char followchars1000; /存放某个非终结符的follow集(如果有(间接)右递归,可能有较大重复) int follow_num; /follow集长度 int follownumkey; /用于判断右递归或间接右递归 cha

9、r followkey; char selectchars3030; /存放每条产生式的select集 char colec030; /存入所有能推导出0的非终结符 int colec0num; /能推导出0的非终结符个数 char capital; /第一个未被使用的大写字母 char preanatab13013020;/存放预测分析表,分别为非终结符(将字母转化为数字)、终结符(将字母转化为数字)、产生式 char _stotax3020; /临时的stotax备份 int _sto_tax; /临时的_sto_tax备份 char startchar; /开始文法符号 char key

10、lr; char save1000; /保存结果到外存储器 char lie20; int li; char hang20; int han; int ll_key; int input_key;Syntax_analysis()void openfile() /打开文件void getin() /对读取出来的文件内容,推导式分解并保存在stotax数组中void disp() /显示方法推导式void get_in() /输入推导式,并保存stotax数组中void save_file(char p) /保存到外存储器void Delpare() /消除左递归void findcapital

11、() /查找未被使用的大写字母,把第一个未被使用的大写字母保存在capital中void First_Collection(char p) /求字符串p的first集,把结果保存在数组firstchars30中void Follow_Collection(char p) /求字符p的follow集,把结果保存在数组followchars中void Select_Collection() /求每条产生式的select集,存放在数组selectchars3030中void Estab_preanatab() /创建预测分析表void dispselect() /显示选择void base_()vo

12、id disp_table() /打印预测分析表void Analyse_course() /分析过程void deduce0_colec() /将所有能推导出0的非终符放在数组colec030中void dispfirst() /显示First集void dispfollow()5.3 文档说明文档文法句子a.txtLL(1)文法baabbb#、baaabbbb#.b.txt直接左递归abbbbb(可以任意多少个b)c.txt间接左递归abbbbb(可以任意多少个b)d.txtLL(1)文法maebn#.5.4 调试分析程序运行说明：适应的文法类型：1、一切LL(1)文法2、含有直接左递归但

13、可以转化为LL(1)文法的文法3、含有间接左递归但可以转化为LL(1)文法的文法说明：1、文法表达方式例如：S:=Aa|Bb，其中空串用数字0代替，每输入一个表达式换行写下一表达式2、文法输入结束后，换行再按#结束3、需要输入命令来执行所需要的功能命令说明：Cmd命令功能open从外存储器打开某文法input从键盘输入文法lltab查看预测分析表select查看每条产生式的SELECT集first求所输串的FIRST集follow求所输非终结符的FOLLOW集ll对某个输入句子进行分析exit退出程序程序运行主界面：（1）open：打开文件打开附带文档a.txta.txt文档中的文法为LL(1

14、)文法：S:=aBc|bABA:=aAb|bB:=b|0（2）input：输入文法输入文法过程中“”应用“0”代替使用每输入一条新文法需重新另起一行文法输入结束后换行以“”结束输入文法后若要保存文件，请按“y”键，并按提示输入备份文件的路径和名称。若没有输入备份路径，文法则保存在默认路径（程序所在文件夹）中；若不进行保存，则键入除“y”键外的任意键退出当前命令。打开a.bck.txt文档，可以看到文法：（3）lltab：预测分析表打开文件a.txt，对文档中语法进行分析：（4）select：查看每条产生式的SELECT集打开文件a.txt，求文档中语法的SELECT集（5）first：求所输串

15、的FIRST集打开文件a.txt，求文档中语法的FIRST集若需要继续求FIRST集，则按“y”键继续；若想退出当前命令，则键入除“y”键外的任意键退出当前命令。（6）follow：求所输非终结符的FOLLOW集打开文件a.txt，求文档中语法的FOLLOW集若需要继续求FOLLOW集，则按“y”键继续；若想退出当前命令，则键入除“y”键外的任意键退出当前命令。（7）ll：对某个输入句子进行分析打开文件a.txt，输入要分析的字符串进行分析（8）exit：推出程序 输入exit命令退出6 课程设计总结在三周的课程设计中，我设计了一个自顶向下的语法分析器。由于涉及大量的编译原理知识，且编程过程复

16、杂，代码量大，完成的功能并不是很多，而且也不是很完善，设计过程难免出现或多或少的错误。由于时间有限，无法对程序进行很好的测试，只发现其中的一些小错误并加以改进和完善，对其他未发现的BUG，只能尽量避免其出现。倘若有足够多的时间，我相信我可以做出需求分析中要求的功能，使其满足人民的要求，减少人工操作，减少运算时间，避免由于人工计算出现的错误，最终加快人们对语法的分析，减少人们的工作量。虽然三周的课程设计时间短，但却使我受益匪浅，通过这次课程设计我把课本中的理论转化成实际运用，从中加深了理论认识，为以后的后续学习奠定基础；并且在编程过程的资料查找和程序编制中掌握了编程的一些基本思路和构想，为以后的

17、程序设计奠定了基础。参考文献1、陈火旺，刘春林. 程序设计语言 编译原理(第3版）. 国防工业出版社. 2000年2、李建中，. 编译原理. 机械工业出版社. 2003年年12月.3、（美）阿佩尔，（美）金斯伯格. . 人民邮电出版社. 2005年09月.附录：重要代码#include"stdio.h"#include"string.h"#include"iostream.h"#include"ctype.h"#include"fstream.h"class Syntax_analysis pu

18、blic:char stotax3020; /存放文法规则char soudocu1000; /用于存放打开的文件内容int sto_tax; /存放产生式总数char firstchars30; /某个串的first集(可能有重复)int first_num; /first集长度char followchars1000; /存放某个非终结符的follow集(如果有(间接)右递归,可能有较大重复)int follow_num; /follow集长度int follownumkey; /用于判断右递归或间接右递归char followkey;char selectchars3030; /存放每条

19、产生式的select集char colec030; /存入所有能推导出0的非终结符int colec0num; /能推导出0的非终结符个数char capital; /第一个未被使用的大写字母char preanatab13013020; /存放预测分析表,分别为非终结符(将字母转化为数字)、终结符(将字母转化为数字)、产生式 char _stotax3020; /临时的stotax备份 int _sto_tax; /临时的_sto_tax备份char startchar; /开始文法符号char keylr;char save1000; /保存结果到外存储器char lie20;int li

20、;char hang20;int han;int ll_key;int input_key; Syntax_analysis()void openfile() /打开文件 input_key=0; int i=0; ifstream infile; char path255; cin>>path; infile.open(path); if (infile.is_open() while (infile.good() soudocui+=(char)infile.get(); infile.close(); soudocui='#' else cout<<

21、;"Error opening file" void getin() /对读取出来的文件内容,推导式分解并保存在stotax数组中int cout=0;char c;char interim50;int i=0; sto_tax=0;again:c=soudocucout+;while(c!='#')if(c!='n')/把一行内容存放在interim数组里if(c!=' ') interimi+=c; c=soudocucout+;elseif(!isupper(interim0)|interim1!=':'

22、|interim2!='=')/如果行首不是以大写字母:=这种格式,则输出错误信息printf("The Syntax is wrong! please enter again:n"); i=0;goto again;else /字符数组加结束符interimi='0'int m=0;for(int j=0;j<strlen(interim);j+)/把后选式进行分解成一个个产生式 /如A:=a|b分解成A:=a,A:=b if(interimj!='|')stotaxsto_taxm+=interimj;continu

23、e;else stotaxsto_taxm='0'sto_tax+;stotaxsto_tax0=stotaxsto_tax-10;stotaxsto_tax1=stotaxsto_tax-11;stotaxsto_tax2=stotaxsto_tax-12;m=3;continue;stotaxsto_taxm='0'sto_tax+;i=0;c=soudocucout+;startchar=stotax00;void disp() /显示方法推导式for(int i=0;i<sto_tax;i+)cout<<stotaxi<<e

24、ndl;void get_in() /输入推导式,并保存stotax数组中char c;if(input_key=0) c=getchar();input_key=1;char interim50;int i=0; sto_tax=0;again:c=getchar();while(c!='#')if(c!='n')if(c!=' ') interimi+=c; c=getchar();elseif(!isupper(interim0)|interim1!=':'|interim2!='=')printf(&quo

25、t;The Syntax is wrong! please enter again:n"); i=0;goto again;else interimi='0'int m=0;for(int j=0;j<strlen(interim);j+)if(interimj!='|')stotaxsto_taxm+=interimj;continue;else stotaxsto_taxm='0'sto_tax+;stotaxsto_tax0=stotaxsto_tax-10;stotaxsto_tax1=stotaxsto_tax-11;s

26、totaxsto_tax2=stotaxsto_tax-12;m=3;continue;stotaxsto_taxm='0'sto_tax+;i=0;c=getchar();startchar=stotax00;int sav=0;savesav='0'printf("save it? press 'y' to save or other to continuen");char command30;cin>>command;if(!strcmp(command,"y")for(int i=0;i

27、<sto_tax;i+)strcat(save,stotaxi);sav=strlen(save);savesav='n'savesav+1='0'save_file(save);char g;g=getchar();void save_file(char p) /保存到外存储器char filepath30; cout<<"Please enter the path and file name"<<endl;cin>>filepath; ofstream ofs(filepath); ofs.wri

28、te(p,strlen(p); ofs.close();void Delpare() /消除左递归ll_key=0;keylr=0;/复制推导式数组for(int i=0;i<sto_tax;i+) strcpy(_stotaxi,stotaxi);_sto_tax=sto_tax;int key;char p30;char key_c;for(i=0;i<_sto_tax;i+)/消除直接左递归key_c=_stotaxi0;if(_stotaxi0=_stotaxi3)/如果存在直接左递归,则消除/查找未被使用的大写之母 findcapital(); for(int j=0;j

29、<_sto_tax;j+)if(_stotaxj0=key_c)keylr=1;if(_stotaxj3=_stotaxj0)strcpy(&_stotaxj3,&_stotaxj4);_stotaxjstrlen(_stotaxj)=capital;_stotaxj0=capital; _stotaxjstrlen(_stotaxj)+1='0'_stotax_sto_tax0=capital;_stotax_sto_tax1=':'_stotax_sto_tax2='='_stotax_sto_tax3='0&#

30、39; _stotax_sto_tax4='0'_sto_tax+;else if(_stotaxj3!='0')int d;d=strlen(_stotaxj);_stotaxjd=capital; _stotaxjd+1='0'char keyc30;for(i=0;i<_sto_tax;i+)/消除间接左递归key=0;strcpy(keyc,_stotaxi);if(isupper(_stotaxi3)for(int j=0;j<=_sto_tax;j+) if(keyc0!=_stotaxj0)if(_stotaxj0=ke

31、yc3)if(key=0) strcpy(p,&_stotaxi4); strcpy(&_stotaxi3,&_stotaxj3); strcpy(&_stotaxistrlen(_stotaxi),p);key=1;else_stotax_sto_tax0=_stotaxi0;_stotax_sto_tax1=':'_stotax_sto_tax2='=' strcpy(&_stotax_sto_tax3,&_stotaxj3); strcpy(&_stotax_sto_taxstrlen(_stotax

32、_sto_tax),p);_sto_tax+; for(int n=0;n<_sto_tax;n+)key_c=_stotaxn0; if(_stotaxi0=_stotaxi3)keylr=1; findcapital(); for(int j=0;j<_sto_tax;j+)if(_stotaxj0=key_c)if(_stotaxj3=_stotaxj0)strcpy(&_stotaxj3,&_stotaxj4); _stotaxjstrlen(_stotaxj)=capital; _stotaxj0=capital; _stotaxjstrlen(_stot

33、axj)+1='0' _stotax_sto_tax0=capital; _stotax_sto_tax1=':' _stotax_sto_tax2='=' _stotax_sto_tax3='0' _stotax_sto_tax4='0' _sto_tax+; else if(_stotaxj3!='0')int d; d=strlen(_stotaxj); _stotaxjd=capital; _stotaxjd+1='0'if(keylr=1)printf("该文法有

34、直接或间接左递归,消除左递归后的文法为:n"); for(i=0;i<_sto_tax;i+) printf("%s",_stotaxi); printf("n"); for(i=0;i<_sto_tax;i+) strcpy(stotaxi,_stotaxi); sto_tax=_sto_tax;void findcapital() /查找未被使用的大写字母,把第一个未被使用的大写字母保存在capital中int key;for(int i=65;i<=90;i+)key=0;for(int j=0;j<_sto_ta

35、x;j+)if(_stotaxj0=char(i) key=1;if(key=0)capital=char(i);break;void First_Collection(char p) /求字符串p的first集,把结果保存在数组firstchars30中if(islower(p0) firstcharsfirst_num+=p0;else if(isupper(p0)for(int i=0;i<sto_tax;i+)if(stotaxi0=p0)if(islower(stotaxi3) firstcharsfirst_num+=stotaxi3; for(i=0;i<strlen

36、(p);i+)if(isupper(pi)char *q;for(int n=0;n<sto_tax;n+)if(pi=stotaxn0)q=&stotaxn3;First_Collection(q); int key=0; for(int j=0;j<colec0num;j+) if(colec0j=pi)key=1; break; if(key=0) break; else if(islower(pi) firstcharsfirst_num+=pi; break;void Follow_Collection(char p) /求字符p的follow集,把结果保存在数组

37、followchars中if(p=stotax00) followcharsfollow_num+='#'for(int i=0;i<sto_tax;i+)for(int j=3;j<strlen(stotaxi);j+)if(p=stotaxij)if(islower(stotaxij+1)followcharsfollow_num+=stotaxij+1; break;else if(stotaxij+1='0')if(follownumkey>=30) /如果follownumkey大于某个值,则可认定求follow集陷入死循环,即有右递

38、归或间接右递归,此时跳出去,终止死循环follownumkey=0;break; follownumkey+;Follow_Collection(stotaxi0);break;else if(isupper(stotaxij+1)char *q;q=&stotaxij+1;first_num=0;First_Collection(q);for(int m=0;m<first_num;m+) followcharsfollow_num+=firstcharsm;int key1=0;for(int n=j+1;n<strlen(stotaxi);n+)int key2=0;

39、for(int r=0;r<colec0num;r+)if(stotaxin=colec0r) key2=1; if(key2=0)key1=1;break;if(key1=0)if(follownumkey>=30) /如果follownumkey大于某个值,则可认定求follow集陷入死循环,即有右递归或间接右递归,此时跳出去,终止死循环 follownumkey=0; break; follownumkey+;Follow_Collection(stotaxi0);break;void Select_Collection() /求每条产生式的select集,存放在数组sele

40、ctchars3030中for(int i=0;i<sto_tax;i+)int select_num=0;int key1=0;int key2=0;for(int j=3;j<strlen(stotaxi);j+)for(int m=0;m<colec0num;m+)if(colec0m=stotaxij) key1=1; if(key1=0)key2=1;break;if(stotaxi3='0') /产生式右边为0,则把follow集加入select集中follownumkey=0;follow_num=0;Follow_Collection(stot

41、axi0);for(int r=0;r<follow_num;r+)int key5=0;for(int v=0;v<select_num;v+)if(followcharsr=selectcharsiv) key5=1;if(key5=0) selectcharsiselect_num+=followcharsr; selectcharsiselect_num='0'break;if(key2=0) /表示产生式右边能推出0,则把first集和follow集加入select集中first_num=0;First_Collection(&stotaxi3);

42、for(int q=0;q<first_num;q+)int key3=0;for(int s=0;s<select_num;s+)if(firstcharsq=selectcharsis) key3=1;if(key3=0) selectcharsiselect_num+=firstcharsq;follownumkey=0;follow_num=0;Follow_Collection(stotaxi0);for(int p=0;p<follow_num;p+)int key4=0;for(int t=0;t<select_num;t+)if(followcharsp

43、=selectcharsit) key4=1;if(key4=0)selectcharsiselect_num+=followcharsp; selectcharsiselect_num='0'else /表示产生式右边不能推出0,则把first集加入select集中first_num=0;First_Collection(&stotaxi3);for(int q=0;q<first_num;q+)int key3=0;for(int s=0;s<select_num;s+)if(firstcharsq=selectcharsis) key3=1;if(key3=0) selectcharsiselect_num+=firstcharsq;selectcharsiselect_num='0' void Estab_preanatab() /创建预测分析表int i,j; /如果分析表中有一项有两个产生式,则可确认该文法为非LL(1)文法,也不能改写为LL(1)文法,不能进行确定的自顶向下分析for(i=0;i<130;i+)for(j=0;j<13