递归下降语法分析程序设计

1、编译方法实验报告实验名称：简单的语法分析程序设计实验要求1. 功能：对简单的赋值语句进行语法分析随机输入赋值语句，输出所输入的赋值语句与相应的四元式2. 采用递归下降分析程序完成（自上而下的分析）3. 确定各个子程序的功能并画出流程图4. 文法如下：5. 编码、调试通过采用标准输入输出方式。输入输出的样例如下：【样例输入】x:=a+b*c/d-(e+f)【样例输出】 (说明，语句和四元式之间用5 个空格隔开 )T1:=b*c(*,b,c,T1)T2:=T1/d(/,T1,d,T2)T3:=a+T2(+,a,T2,T3)T4:=e+f(+,e,f,T4)T5:=T3-T4(-,T3,T4,T5)

2、x:=T5(:=,T5,-,x)【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。6.设计 3-5 个赋值语句测试实例 ，检验程序能否输出正确的四元式；当输入错误的句子时，检验程序能够给出语法错误的相应提示信息。7. 报告内容包括：递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，3-5 个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。目录1.语法分析递归下降分析算法.51.1背景知识.51.2消除左递归 .62.详细设计及流程图 .62.1函数 void V( )/ V - a|b|c|d|e.|z .62.2函数

3、 void A( )/A - V:=E .72.3函数 void E()/E - TE .72.4函数 void T( )/ T - FT .82.5函数 void E1( )/E- +TE|-TE|null .82.6函数 void T1()/T- *FT|/FT|null .93.测试用例及截图.103.1测试用例1 及截图.103.2测试用例2 及截图.113.3测试用例3 及截图.12代码清单 .121.语法分析递归下降分析算法1.1 背景知识无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。无左递归：既没有直接左递归，也没有间接左递归。无回溯：对于任一非终结符号U 的产生式

4、右部x1|x2| |xn，其对应的字的首终结符号两两不相交。如果一个文法不含回路，也不含以为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以为右部的产生式） 。文法的左递归消除算法：1、将文法G 的所有非终结符排序为U1 ,U2 , ,Un;2、 For(i=1 ； i+ ； i n)for j 1 to-1i把产生式 Ui Uj 替换成 Ui 1|2| ；|m其中： Uj 1| 2 | 消除|Uim 产生式中的直接左递归；3.化简改写之后的文法，删除多余产生式。文法的直接左递归消除公式：直接左递归形式：U Ux|y ；其中： x， y（ V N

5、V T） * ， y 不以 U 打头。直接左递归的消除：U yU ?U? xU?| 直接左递归的一般形式：U Ux 1|Ux 2| |Uxm|y1 |y2 | |yn；其中： xi i 都,y不以 U 打头。一般形式直接左递归的消除:Uy1U ?| y2U? | | ynU?U ?x1U?| x2U ?| | mxU?|回溯的消除的前提是文法不得含有左递归，可提左因子来消除回溯。1.2 消除左递归根据实验中给出的文法，进行消除左递归及回溯，得到下列的式子A - V:=EE - TEE- +TE|-TE|nullT - FTT- *FT|/FT|nullF - V|(E)V - a|b|c|d|

6、e.|z2.详细设计及流程图根据消除左递归后的文法，可以编写相应的函数。2.1函数 void V( )/ V - a|b|c|d|e.|zvoid V() / V - a|b|c|d|e.|z 函数设计主要用来识别小写字母的，如果是小写字母的话，放入字符表，不是的话，输出语法错误。函数比较简单，代码如下：if(islower(ssym)Tablelist_n0 = ssym;/把读取的小写字母存入符号表，便于分析是生成中间代码Tablelist_n1 = 0;list_n+;sym+;elseprintf(Operand Errors!n);/运算对象错误SIGN=1;exit(0);2.2函

7、数 void A( )/A - V:=Evoid A()/A - V:=E函数主要用来实现赋值的操作，流程图如图1 所示。开始V( )ssym=:&ssym+1=YNsym+=2;E( );输出表达式输出错误结束图 1A( )函数流程图2.3函数 void E()/E - TE函数 E（）里面主要递归调用函数T( ) 和 E( ) 。当没有出现语法错误时就可正常的运行。函数比较简单，代码如下：if(SIGN=0)T();E1();2.4 函数 void T( )/ T - FT函数 T( ) 里面主要递归调用函数F ( )和 T( ) 。当没有出现语法错误时就可正常的运行。函数比较简单，代码如

8、下：if(SIGN=0)F();T1();2.5 函数 void E1( )/E- +TE|-TE|null函数 void E1() /E- +TE|-TE|null ，主要用来实现加减法的语义分析。流程图如图2所示。开始SIGN=0ssym = +|ssym=-Yp=sym;sym+T()N输出三地址式和四元表达式NE1()结束图 2 E1() 函数流程图2.6 函数 void T1()/T- *FT|/FT|null函数 void T1()/ T- *FT|/FT|null ，主要用来实现乘除法的语义分析。流程图如图3所示。开始SIGN=0ssym = *|ssym=/Yp=sym;sym

9、+F()N输出三地址式和四元表达式T1()N结束图 3 T1() 函数流程图3.测试用例及截图3.1 测试用例1 及截图用例 1 为实验要求上的的用例。测试结果图4 所示。图 4测试用例1 及结果截图3.2 测试用例2 及截图用例 2 为出现大写字母，出现报错。测试结果图5 所示。图 5测试用例2 及结果截图3.3 测试用例3 及截图用例 3 为随意编写用例。测试结果图6 所示。图 6测试用例3 及结果截图代码清单#include#include#include#include void A();/A - V:=Evoid E();/E - TEvoid T();/T - FTvoid E1(

10、); /E- +TE|-TE|nullvoid T1(); /T- *FT|/FT|nullvoid F();/F - V|(E)void V();/V - a|b|c|d|e.|zchar s50,n=1;/s50 用于存放输入的赋值表达式char Table503; int SIGN,sym;/产生中间代码所需的符号表/sym 为 s50中当前读入符号的下标int list_n=0;/符号表的下标/* 消除左递归及回溯A - V:=EE - TEE- +TE|-TE|nullT - FTT- *FT|/FT|nullF - V|(E)V - a|b|c|d|e.|z*/int main()

11、SIGN = 0;/SIGN 用于指示赋值表达式是否出现错误sym=0;scanf(%s,&s);if( s0 = 0)/没有输入的情况直接退出return 0;A();if(ssym!=0&SIGN=0)printf(ERROR!n);exit(0);return 0;void A()/A - V:=EV();if(ssym=:&ssym+1=) /判断赋值号是否有拼写错误sym+=2;E();printf(%s:=%s,Tablelist_n-2,Tablelist_n-1);printf(:=,%s,-,%s)n,Tablelist_n-1,Tablelist_n-2);elseprin

12、tf(The assignment Symbol spelling mistakes!n); /赋值号拼写错误SIGN=1;exit(0);void V()/ V - a|b|c|d|e.|zif(islower(ssym)Tablelist_n0 = ssym;/把读取的小写字母存入符号表，便于分析是生成中间代码Tablelist_n1 = 0;list_n+;sym+;elseprintf(Operand Errors!n);SIGN=1;exit(0);/运算对象错误void E()/E - TEif(SIGN=0)T();E1();void T()/ T - FTif(SIGN=0)F

13、();T1();void E1()/E- +TE|-TE|nullint p;if(SIGN=0)if(ssym = +|ssym=-)p=sym;/ 用p 记录出现+或 -时sym 的值sym+;T();char ch3;ch0 = T;ch1 = n;ch2 = 0;if(sp = +)printf(%s:=%s+%s,ch,Tablelist_n-2,Tablelist_n-1);/输出三地址代码printf(+,%s,%s,%s)n,Tablelist_n-2,Tablelist_n-1,ch);/输出四元式elseprintf(%s:=%s-%s,ch,Tablelist_n-2,T

14、ablelist_n-1);/ 输出三地址代码printf(-,%s,%s,%s)n,Tablelist_n-2,Tablelist_n-1,ch);/输出四元式strcpy(Tablelist_n-2,ch); /将当前结果归结式放在符号表中 list_n-;n+;E1();void T1()/T- *FT|/FT|nullint p;if(SIGN=0)if(ssym = *|ssym=/)p=sym;sym+;F();char ch3;ch0 = T;ch1 = n;ch2 = 0;if(sp = *)printf(%s:=%s*%s,ch,Tablelist_n-2,Tablelist_n-1);/ 输出三地址代码printf(*,%s,%s,%s)n,Tablelist_n-2,Tablelist_n-1,ch);/输出四元式elseprintf(%s:=%s/%s,ch,Tablelist_n-2,Tablelist_n-1);/输出三地址代码printf(/,%s,%s,%s)n,Tablelist_n-2,Tablelist_n-1,ch);/输出四元