编译原理实验之语法分析程序.doc

软件工程0801班 和春辰 U200818016 编译技术实验2 编译技术实验报告实验名称：语法分析程序姓名：和春辰学号：U200818016班级：软件工程0801班指导老师：胡福林2010年10月23日目录一、实验题目3二、实验目的4三、实验要求4四、实验步骤4基本设计思路4正规式5状态转换图5流程框图5算法设计6函数相关说明7输入与输出8程序运行结果8五、实验方案设计实现10六、实验程序亮点描述10七、实验程序使用说明10八、实验心得体会10九、源程序清单11一、 实验题目对下述文法和单词表定义的语言设计编制一个语法分析器。1) 单词符号及种别表单词符号种别编码单词值main1int 2float3double4char5if 6else 7do8while9l(l|d)*10内部字符串 ( +|-| ) dd*(.dd* | )( e ( +|-| ) dd*|) 20二进制数值表示=21+22- 23* 24/ 25(26)272829,30;3132=3334=35=36!=372) 语法结构定义 := +|- := *|/ :=ID|num|()num:= ( +|-| ) 数字数字*(.数字数字* | )( e ( +|-| ) 数字数字*|)ID:=字母(字母|数字)*字母:=a|b|c|z|A|B|C|Z数字:=0|1|2|9二、 实验目的1、通过该实验,熟练应用编译原理的基本理论和方法2、学会用C/C+高级程序设计语言设计一个语法分析器的技术3、加深对编译原理的分析理论的理解，培养动手实践能力三、 实验要求词法分析程序需具备语法分析的功能：处理用户提交的符合上述文法的源代码序列，进行语法分析，并给出语法是否正确的结论。例如：控制台输入d+-11.7e-17，经过语法分析后输出如下序列：success!例如：控制台输入(123.456+-456.789e-120)*m2+(a+456)*c123，经过语法分析后输出如下序列：success!例如：控制台输入(123.456+-456.789e-120)*m2+(a+456)*-c123，经过语法分析后输出如下序列：error!四、 实验步骤基本设计思路 基本字作为一类特殊的标识符来处理：识别出标识符，差基本字表，给出相应种别码。基本字表置初值：char *rwtab6=begin,if,then,while,do,end;（字符指针的数组） 识别无符号整数是将数字串转换为无符号整数。我们在getchar()的时候是把数字当做字符从外部输出读取的。将数字串345#转换为整数：(3*10+4)*10+5=345送到sum中 程序主要由2个函数组成，主函数main()和扫描子函数scanner()。扫描程序每次读取1个独立意义的单词符号，并判断单词类型。主程序做相应处理后做控制台输出。 递归下降分析法是对文法的每个非终结符编制一个递归过程（函数），按规则右部符号串的顺序编写：若为终结符，则读下一个单词符号；非终结符，调用相应的递归过程（函数）。正规式将已知正规文法变换一下：E - T +T|-TT - F*F|/FF - ID|num|(E)将其表示为正规式方程组后，试图解方程，以求此正规文法对应的正规式。但是由于计算过程中，方程变得越来越复杂，只好作罢。状态转换图正规式无法求出，状态转换图只好作罢。流程框图图表 1函数E图表 2函数T图表 3函数F算法设计词法分析程序所用的较为重要的全局变量和需调用的函数如下：1) ch字符变量，存放当前读进的源程序字符。2) token8字符数组，存放构成单词符号的字符串。3) prog80字符数组，存放所有用户输入的字符。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) double pow(double x,double y)，计算x的y次幂。14) int strcmp(char *str1,char #str2)，字符串比较。15) int isSignal; 是否带正负号(0不带，1负号，2正号）16) int repeat; 是否连续出现+,-。17) void E(); 递归下降分析程序中，为非终结符E编写的函数18) void T(); 递归下降分析程序中，为非终结符T编写的函数19) void F(); 递归下降分析程序中，为非终结符F编写的函数函数相关说明void E()T();while(syn=22)|(syn=23) /+,-scanner();T();void T()F();while(syn=24)|(syn=25) /*,/scanner();F();void F()if(syn=20)|(syn=10) /字符串，数字scanner();else if(syn=26) /(scanner();E();if(syn=27) /)scanner();else isError=1;else isError=1;输入与输出词法分析程序需具备词法分析的功能：输入：所给文法的源程序字符串。（字符串以“#”号结束）输出：success 是文法正确句子 error 不是文法正确句子例如：输入 a+b*c# 输出success.程序运行结果五、 实验方案设计实现用C语言实现。采用递归下降分析法做语法分析。六、 实验程序亮点描述巧妙整合上次实验的词法分析程序，只添加了少许代码，大概都是递归下降分析程序的逻辑主体部分。但是因为单词符号及种别表与第1次实验不完全相同，我做了相应的修改。七、 实验程序使用说明用户输入待识别字符串（并以“#”结尾，表示字符串输入结束），回车后程序自动输出语法分析结果。八、 实验心得体会这次老师给出了很复杂的待分析的字符串，运行之后总是出现各种各样的bug，调了1个晚上加1个早上，才搞定。比较严重的是，我甚至发现自己之前写的词法分析程序还有问题，那就是没能识别正负！之前没有听到老师的具体要求，所以只设置了识别浮点数（包括小数表示和指数表示形式）。在VC+6.0里边不断地改，不断地设breakpoint，不断地F5,F10,F11，看到眼花。调了时候心里默默在想，悲剧啊，这么小一个程序，也把姐搞整得这么惨。后来又发现一个问题，能够识别1+2了，但是无法识别1+2.当时判断正负号的方法是，读取当前字符的后一个字符，如果是数字，那么就判断当前字符为正负号。但是如果遇到1+2这种，+表示的是加号。所以就增加了一个repeat变量，当遇到2个+或者-时，才识别后一个字符为正负号。这样又带来一个bug，无法识别类似+1+2式子中最前面的+号，程序会误认它为正号(repeat等于0）。囧啊。暂未解决，不想调了。休养生息，改日再战。这次这个实验可把我整惨了，好像狠狠敲了我一棒。原来我的编译原理还有这么多东西没有掌握好！包括递归下降分析法的实质，包括扩充BNF表示法。好多好多，以后要加油了。九、 源程序清单#include#includeint isError;char prog80; /存放所有输入字符 char token8; /存放词组 char ch; /单个字符 int syn,p,m,n; /syn:种别编码 double sum; int count; int isSignal; /是否带正负号(0不带，1负号，2正号）int isDecimal; /是否是小数 double decimal; /小数 int isExp; /是否是指数 int index; /指数幂 int isNegative; /是否带负号 double temp; int temp2;int repeat; /是否连续出现+,- void scanner(); char *rwtab9=main,int,float,double,char,if,else,do,while;void E();void T();void F();void scanner();void main()p=0;count=0;isDecimal=0;index=0;repeat=0;printf(n please input the source string:n);doch=getchar();progp+=ch;while(ch!=#);p=0;isError=0;scanner();if(syn=20)|(syn=10)|(syn=26) E();if(ch=#)&(isError=0)printf(successn);elseprintf(errorn);void E()T();while(syn=22)|(syn=23)scanner();T();void T()F();while(syn=24)|(syn=25)scanner();F();void F()if(syn=20)|(syn=10)scanner();else if(syn=26)scanner();E();if(syn=27)scanner();else isError=1;else isError=1;void scanner() sum=0; decimal=0; m=0; for(n=0;n=a)&(ch=A)&(ch=a)&(ch=A)&(ch=0)&(chtoken ch=progp+; /读下一个字符 tokenm+=0; p-; /回退一格 syn=10; /标识符 /如果是begin,if,then,while,do,end标识符中的一个 for(n=0;n=0)&(ch=0)&(ch=0)&(ch=0)&(ch=9) /指数 index=index*10+ch-0; ch=progp+; /10的幂 /123e3代表123*10(3) /sum=sum*pow(10,index);是错误的 if(isNegative) sum=sum*pow(0.1,index); else sum=sum*pow(10,index); if(isSignal=1)sum=-sum;isSignal=0; p-; syn=20; else switch(ch) case : m=0; tokenm+=ch; ch=progp+; if(ch=) syn=33; tokenm+=ch; else syn=32; p-; break; case =: m=0; tokenm+=ch; ch=progp+; if(ch=) syn=36; tokenm+=ch; else syn=21; p-; break; case +:temp2=progp;tokenm+=ch;if(temp2=0)&(temp2=0)&(temp2=9)&(repeat=1)isSignal=1;ch=progp+; /读“-”下一个字符repeat=0;goto IsNum; /转到数字的识别if(temp2=+)|(temp2=-)&(repeat=0) /如果重复出现符号，才将后边的+，-视为正负号repeat=1; /预言会重复/ch=progp+; /读下一个字符syn=23;break; /* case *: syn=24; tokenm+=ch; break;*/case *:temp2=progp;tokenm+=ch;if(temp2=+)isSignal=2;repeat=1;else if(temp2=-)isSignal=1;repeat=1;syn=24;break; case /: syn=25; tokenm+=ch; break; /* case (: syn=26; tokenm+=ch; break;*/case (:temp2=progp;tokenm+=ch;if(temp2=+)isSignal=2;repeat=1;else if(t