语法分析器

目录引言...............................................................1第一章概述.....................................................21.1设计内容....................................................21.2设计要求....................................................3第二章设计的基本原理............................................32.1词法分析....................................................32.2语法分析...................................................3第三章程序设计..................................................33.1总体方案设计................................................33.2各模块设计..................................................5第四章程序测试.................................................74.1程序调试与体会.............................................74.2运行结果...................................................7第五章结论.....................................................8参考文献...........................................................9附录程序清单.................................................9引言编译原理作为计算机科学中的一门基础科学，它对我们理解高级语言编译程序是极其重要的。在编译系统中,词法分析阶段是整个编译系统的基础。而语法分析是编译过程的核心部分，它的任务是在词法分析分器识别出单词符号串的基础上，分析判定程序的语法结构是否符合语法规则。语言的语法结构使用上下无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。按照语法分析树的建立方法，可粗略将语法分析办法分成两类，一类是自上而下分析方法，另一类是自下而上分析法。自上而下的递归下降方法是最简单的分析方法，本程序采用此方法。第一章概述1.1设计内容对下述文法和单词表定义的语言设计编制一个语法分析器。1)单词符号及种别表单词符号种别编码单词值main1int2float3double4char5if6else7do8while9l(l|d)*10内部字符串(+|-|ε)dd*(.dd*|ε)(e(+|-|ε)dd*|ε)20二进制数值表示=21+22-23*24/25(26)27{28}29,30;3132=3334=35==36!=372)语法结构定义表达式::=项{+项|-项}项::=因子{*因子|/因子}因子::=ID|num|(表达式)num::=(+|-|ε)数字数字*(.数字数字*|ε)(e(+|-|ε)数字数字*|ε)ID::=字母(字母|数字)*字母::=a|b|c…|z|A|B|C…|Z数字::=0|1|2…|91.2设计要求1）通过该实验,熟练应用编译原理的基本理论和方法2）学会用C/C++高级程序设计语言设计一个语法分析器的技术3)加深对编译原理的分析理论的理解，培养动手实践能力第二章设计的基本原理.2.1词法分析语法分析器中嵌套词法分析。词法分析的任务是：从左至右逐个字符的对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。词法分析是编译的基础。词法分析器的功能是输入源程序，输出单词符号。将词法分析器作为一个独立子程序好处是，它可使整个编译程序的结构更为简洁、清晰和条理化。将词法分析器作为一个独立子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号，把它交给语法分析器。2.2语法分析器的递归下降分析法语法分析是编译过程的核心部分，它的任务是在词法分析分器识别出单词符号串的基础上，分析判定程序的语法结构是否符合语法规则。自上而下的递归下降方法是最简单的分析方法，本程序采用此方法。递归下降分析方法使程序直观易懂，便于表示左递归消去和因子提取。第三章程序设计3.1总体方案设计基本设计思路基本字作为一类特殊的标识符来处理：识别出标识符，差基本字表，给出相应种别码。基本字表置初值：char*rwtab[6]={begin,if,then,while,do,end};（字符指针的数组）识别无符号整数是将数字串转换为无符号整数。我们在getchar()的时候是把数字当做字符从外部输出读取的。将数字串345#转换为整数：(3*10+4)*10+5=345送到sum中程序主要由2个函数组成，主函数main()和扫描子函数scanner()。扫描程序每次读取1个独立意义的单词符号，并判断单词类型。主程序做相应处理后做控制台输出。递归下降分析法是对文法的每个非终结符编制一个递归过程（函数），按规则右部符号串的顺序编写：若为终结符，则读下一个单词符号；非终结符，调用相应的递归过程（函数）。正规式将已知正规文法变换一下：E-T{+T|-T}T-F{*F|/F}F-ID|num|(E)将其表示为正规式方程组后，试图解方程，以求此正规文法对应的正规式。流程框图3.2各模块设计算法设计词法分析程序所用的较为重要的全局变量和需调用的函数如下：1)ch字符变量，存放当前读进的源程序字符。2)token[8]字符数组，存放构成单词符号的字符串。3)prog[80]字符数组，存放所有用户输入的字符。4)syn整数，存放当前单词的种别码。5)sum双精度浮点型变量，存放无符号整数，或者浮点数。6)isDecimal整数，是否为浮点数。isDecimal为1，则为浮点数。7)decimal双精度浮点型变量(double)，浮点数的小数部分。8)isExp整数，是否为指数形式表示的浮点数（即是否存在符号E或者e）。isExp为1，则为指数形式。9)index整数，指数形式的幂。10)isNegative整数，是否为负数幂。isNegative为1，则为负数幂，如123E-2。11)scanner()扫描子程序。12)getchar()从控制台读取一个字符数据。13)doublepow(doublex,doubley)，计算x的y次幂。14)intstrcmp(char*str1,char#str2)，字符串比较。15)intisSignal;是否带正负号(0不带，1负号，2正号）16)intrepeat;是否连续出现+,-。17)voidE();递归下降分析程序中，为非终结符E编写的函数18)voidT();递归下降分析程序中，为非终结符T编写的函数19)voidF();递归下降分析程序中，为非终结符F编写的函数函数相关说明voidE(){T();while((syn==22)||(syn==23))//’+’,’-‘{scanner();T();}}voidT(){F();while((syn==24)||(syn==25))//’*’,’/’{scanner();F();}}voidF(){if((syn==20)||(syn==10))//字符串，数字scanner();elseif(syn==26)//’(‘{scanner();E();if(syn==27)//’)’{scanner();}elseisError=1;}elseisError=1;}第四章程序测试4.1程序调试与体会语法分析是编译过程的核心部分。本程序采用递归下降分析法做语法分析。用户输入待识别字符串（并以“#”结尾，表示字符串输入结束），回车后程序自动输出语法分析结果。4.2运行结果（截图）第五章结论通过语法分析器的程序设计，我们很好的了解语法分析的相关知识，很好的理解了语法的分析方法，自上而下、自下而上的分析方法，掌握了递归下降的方法。巧妙整合词法分析程序，只添加了少许代码，再进行修改成为递归下降分析程序的逻辑主体部分。开始运行之后总是出现各种各样的bug，调了好久，才搞定。比较严重的是，我甚至发现自己之前写的词法分析程序还有问题，那就是没能识别正负！在VC++6.0里边不断地改，不断地调试。后来又发现一个问题，能够识别1++2了，但是无法识别1+2.当时判断正负号的方法是，读取当前字符的后一个字符，如果是数字，那么就判断当前字符为正负号。但是如果遇到1+2这种，'+'表示的是加号。所以就增加了一个repeat变量，当遇到2个'+'或者'-'时，才识别后一个字符为正负号。这次课程设计我学到了很多东西，这些东西对我来说课堂上是根本学不到的。在本次课程设计中我学会了如何自学，如何将学的知识用于实践等。这些东西对我来说将一生受用。参考文献［1］陈火旺等编译原理程序设计国防工业出版社2002年［2］[美]AlfredV.Aho,RaviSethi,JeffreyD.UllmanPearsonEducationCompilers:Principles,Techniques,andTools2003年［3］Louden,K.C.冯博琴译编译原理及实践机械工业出版社2000年［4］谭浩强C++程序设计清华大学出版社2007年附录程序清单#includestdio.h#includestring.h#includemath.hintisError;charprog[80];//存放所有输入字符chartoken[8];//存放词组charch;//单个字符intsyn,p,m,n;//syn:种别编码doublesum;intcount;intisSignal;//是否带正负号(0不带，1负号，2正号）intisDecimal;//是否是小数doubledecimal;//小数intisExp;//是否是指数intindex;//指数幂intisNegative;//是否带负号doubletemp;inttemp2;intrepeat;//是否连续出现+,-voidscanner();char*rwtab[9]={main,int,float,double,char,if,else,do,while};voidE();voidT();voidF();voidscanner();voidmain(){p=0;count=0;isDecimal=0;index=0;repeat=0;printf(\npleaseinputthesourcestring:\n);do{ch=getchar();prog[p++]=ch;}while(ch!='#');p=0;isError=0;scanner();if((syn==20)||(syn==10)||(syn==26)){E();}if((ch=='#')&&(isError==0))printf(success\n);elseprintf(error\n);}voidE(){T();while((syn==22)||(syn==23)){scanner();T();}}voidT(){F();while((syn==24)||(syn==25)){scanner();F();}}voidF(){