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

/编译方法实验报告实验名称：简单的语法分析程序设计实验要求功能：对简单的赋值语句进行语法分析随机输入赋值语句.输出所输入的赋值语句与相应的四元式采用递归下降分析程序完成〔自上而下的分析确定各个子程序的功能并画出流程图文法如下：编码、调试通过采用标准输入输出方式。输入输出的样例如下：[样例输入]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>x:=T5

<:=,T5,-,x>

[样例说明]程序除能够正确输出四元式外.当输入的表达式错误时.还应能检测出语法错误.给出相应错误提示。设计3-5个赋值语句测试实例.检验程序能否输出正确的四元式；当输入错误的句子时.检验程序能够给出语法错误的相应提示信息。报告内容包括：递归程序的调用过程.各子程序的流程图和总控流程图.详细设计.3-5个测试用例的程序运行截图及相关说明.有详细注释的程序代码清单等。目录1.语法分析递归下降分析算法51.1背景知识51.2消除左递归62.详细设计及流程图62.1函数voidV<>//V->a|b|c|d|e...|z62.2函数voidA<>//A->V:=E72.3函数voidE<>//E->TE'72.4函数voidT<>//T->FT'82.5函数voidE1<>//E'->+TE'|-TE'|null82.6函数voidT1<>//T'->*FT'|/FT'|null93.测试用例及截图93.1测试用例1及截图93.2测试用例2及截图103.3测试用例3及截图11代码清单111.语法分析递归下降分析算法1.1背景知识无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。无左递归：既没有直接左递归.也没有间接左递归。无回溯：对于任一非终结符号U的产生式右部x1|x2|…|xn.其对应的字的首终结符号两两不相交。如果一个文法不含回路.也不含以ε为右部的产生式.那么可以通过执行消除文法左递归的算法消除文法的一切左递归〔改写后的文法可能含有以ε为右部的产生式。文法的左递归消除算法：1、将文法G的所有非终结符排序为U1,U2,…,Un;2、For<i=1；i++；i≥n>{forj→1toi-1把产生式Ui→Ujα替换成Ui→β1α|β2α|…|βmα； 其中：Uj→β1|β2|…|βm消除Ui产生式中的直接左递归；}3.化简改写之后的文法.删除多余产生式。文法的直接左递归消除公式： 直接左递归形式：U→Ux|y；其中：x.y∈〔VN∪VT*.y不以U打头。直接左递归的消除：U→yU‟U‟→xU‟|ε直接左递归的一般形式：U→Ux1|Ux2|…|Uxm|y1|y2|…|yn；其中：xi≠ε,yi都不以U打头。一般形式直接左递归的消除:U→y1U‟|y2U‟|…|ynU‟U‟→x1U‟|x2U‟|…|xmU‟|ε回溯的消除的前提是文法不得含有左递归.可提左因子来消除回溯。1.2消除左递归根据实验中给出的文法.进行消除左递归及回溯.得到下列的式子A->V:=EE->TE'E'->+TE'|-TE'|nullT->FT'T'->*FT'|/FT'|nullF->V|<E>V->a|b|c|d|e...|z2.详细设计及流程图根据消除左递归后的文法.可以编写相应的函数。2.1函数voidV<>//V->a|b|c|d|e...|z voidV<>//V->a|b|c|d|e...|z函数设计主要用来识别小写字母的.如果是小写字母的话.放入字符表.不是的话.输出语法错误。函数比较简单.代码如下： if<islower<s[sym]>> { Table[list_n][0]=s[sym];//把读取的小写字母存入符号表.便于分析是生成中间代码 Table[list_n][1]='\0'; list_n++; sym++; } else { printf<"OperandErrors!\n">;//运算对象错误 SIGN=1; exit<0>; }2.2函数voidA<>//A->V:=E voidA<>//A->V:=E函数主要用来实现赋值的操作.流程图如图1所示。图1A<>函数流程图2.3函数voidE<>//E->TE'函数E〔里面主要递归调用函数T<>和E'<>。当没有出现语法错误时就可正常的运行。函数比较简单.代码如下：{ if<SIGN==0> { T<>; E1<>; }}2.4函数voidT<>//T->FT'函数T<>里面主要递归调用函数F<>和T''<>。当没有出现语法错误时就可正常的运行。函数比较简单.代码如下： if<SIGN==0> { F<>; T1<>; }2.5函数voidE1<>//E'->+TE'|-TE'|null函数voidE1<>//E'->+TE'|-TE'|null.主要用来实现加减法的语义分析。流程图如图2所示。图2E1<>函数流程图2.6函数voidT1<>//T'->*FT'|/FT'|null函数voidT1<>//T'->*FT'|/FT'|null.主要用来实现乘除法的语义分析。流程图如图3所示。图3T1<>函数流程图3.测试用例及截图3.1测试用例1及截图用例1为实验要求上的的用例。测试结果图4所示。图4测试用例1及结果截图3.2测试用例2及截图用例2为出现大写字母.出现报错。测试结果图5所示。图5测试用例2及结果截图3.3测试用例3及截图用例3为随意编写用例。测试结果图6所示。图6测试用例3及结果截图代码清单#include<stdio.h>#include<stdlib.h>#include<string.h>#include<ctype.h>voidA<>;//A->V:=EvoidE<>;//E->TE'voidT<>;//T->FT'voidE1<>;//E'->+TE'|-TE'|nullvoidT1<>;//T'->*FT'|/FT'|nullvoidF<>;//F->V|<E>voidV<>;//V->a|b|c|d|e...|zchars[50],n='1';//s[50]用于存放输入的赋值表达式charTable[50][3];//产生中间代码所需的符号表intSIGN,sym;//sym为s[50]中当前读入符号的下标intlist_n=0;//符号表的下标/*消除左递归及回溯A->V:=EE->TE'E'->+TE'|-TE'|nullT->FT'T'->*FT'|/FT'|nullF->V|<E>V->a|b|c|d|e...|z*/intmain<>{ SIGN=0;//SIGN用于指示赋值表达式是否出现错误 sym=0; scanf<"%s",&s>; if<s[0]=='\0'>//没有输入的情况直接退出 return0; A<>; if<s[sym]!='\0'&&SIGN==0> { printf<"ERROR!\n">; exit<0>; } return0;}voidA<>//A->V:=E{ V<>; if<s[sym]==':'&&s[sym+1]=='='>//判断赋值号是否有拼写错误 { sym+=2; E<>; printf<"%s:=%s",Table[list_n-2],Table[list_n-1]>; printf<"<:=,%s,-,%s>\n",Table[list_n-1],Table[list_n-2]>; } else { printf<"TheassignmentSymbolspellingmistakes!\n">;//赋值号拼写错误 SIGN=1; exit<0>; }}voidV<>//V->a|b|c|d|e...|z{ if<islower<s[sym]>> { Table[list_n][0]=s[sym];//把读取的小写字母存入符号表.便于分析是生成中间代码 Table[list_n][1]='\0'; list_n++; sym++; } else { printf<"OperandErrors!\n">;//运算对象错误 SIGN=1; exit<0>; }}voidE<>//E->TE'{ if<SIGN==0> { T<>; E1<>; }}voidT<>//T->FT'{ if<SIGN==0> { F<>; T1<>; }}voidE1<>//E'->+TE'|-TE'|null{ intp; if<SIGN==0> { if<s[sym]=='+'||s[sym]=='-'> { p=sym;//用p记录出现'+'或'-'时sym的值 sym++; T<>; charch[3]; ch[0]='T'; ch[1]=n;ch[2]='\0';if<s[p]=='+'>{printf<"%s:=%s+%s",ch,Table[list_n-2],Table[list_n-1]>;//输出三地址代码 printf<"<+,%s,%s,%s>\n",Table[list_n-2],Table[list_n-1],ch>;//输出四元式 } else { printf<"%s:=%s-%s",ch,Table[list_n-2],Table[list_n-1]>;//输出三地址代码 printf<"<-,%s,%s,%s>\n",Table[list_n-2],Table[list_n-1],ch>;//输出四元式 } strcpy<Table[list_n-2],ch>;//将当前结果归结式放在符号表中 list_n--; n++; E1<>;} }}voidT1<>//T'->*FT'|/FT'|null{intp; if<SIGN==0> { if<s[sym]=='*'||s[sym]=='/'> { p=sym;sym++; F<>; charch[3]; ch[0]='T';ch[1]=n; ch[2]='\0'; if<s[p]=='*'>{ printf<"%s:=%s*%s",ch,Table[list_n-2],Tabl