当前位置：文档库 › 递归下降语法分析程序设计

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

编译方法实验报告

令狐采学

实验名称：简单的语法分析程序设计

实验要求

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:=T3T4 (,T3,T4,T5)

x:=T5 (:=,T5,,x)

【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。

6.设计35个赋值语句测试实例，检验程序能否输出正确的四

元式；当输入错误的句子时，检验程序能够给出语法错误的相应提示信息。

7.报告内容包括：

递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，35个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。

1.语法分析递归下降分析算法5

1.1背景知识5

1.2消除左递归6

2.详细设计及流程图6

2.1 函数void V( ) // V > a|b|c|d|e...|z6

2.2 函数void A( ) // A > V:=E7

2.3 函数void E() //E > TE'7

2.4函数void T( ) // T > FT'8

2.5函数void E1( ) //E'> +TE'|TE'|null8

2.6函数void T1() // T'> *FT'|/FT'|null9

3.测试用例及截图9

3.1测试用例1及截图9

3.2测试用例2及截图10

3.3测试用例3及截图11

代码清单11

1.语法分析递归下降分析算法

1.1背景知识

无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。

无左递归：既没有直接左递归，也没有间接左递归。

无回溯：对于任一非终结符号U的产生式右部x1|x2|…|xn，其对应的字的首终结符号两两不相交。

如果一个文法不含回路，也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。

文法的左递归消除算法：

1、将文法G的所有非终结符排序为U1 ,U2 ,… ,Un;

2、For(i=1；i++；i≥n)

{

for j→1 to i1

把产生式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:=E

E > TE'

E'> +TE'|TE'|null

T > FT'

T'> *FT'|/FT'|null

F > V|(E)

V > a|b|c|d|e...|z

2.详细设计及流程图

根据消除左递归后的文法，可以编写相应的函数。

2.1 函数void V( ) // V > a|b|c|d|e...|z

void V() // 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("Operand Errors!\n"); //运算对象错误

SIGN=1;

exit(0);

}

2.2函数void A() // A > V:=E

void A() // A > V:=E函数主要用来实现赋值的操作，流程图如图1所示。

图1 A( ) 函数流程图

2.3函数void E() //E > TE'

函数E（）里面主要递归调用函数T( )和E'( )。当没有出现语法错误时就可正常的运行。函数比较简单，代码如下：

{

if(SIGN==0)

{

T();

E1();

}

2.4函数void T() // T > FT'

函数T()里面主要递归调用函数F ( )和T''( )。当没有出现语法错误时就可正常的运行。函数比较简单，代码如下：if(SIGN==0)

{

F();

T1();

}

2.5函数void E1( )//E'> +TE'|TE'|null

函数void E1() //E'> +TE'|TE'|null，主要用来实现加减法的语义分析。流程图如图2所示。

图2 E1 ( ) 函数流程图2.6函数void T1() // T'> *FT'|/FT'|null

函数void T1() // 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

void A(); // A > V:=E

void E(); // E > TE'

void T(); // T > FT'

void E1(); // E'> +TE'|TE'|null

void T1(); // T'> *FT'|/FT'|null

void F(); // F > V|(E)

void V(); // V > a|b|c|d|e...|z

char s[50],n='1'; //s[50]用于存放输入的赋值表达式char Table[50][3]; //产生中间代码所需的符号表

int SIGN,sym; //sym为s[50]中当前读入符号的下标int list_n=0; //符号表的下标

/*消除左递归及回溯

A > V:=E

E > TE'

E'> +TE'|TE'|null

T > FT'

T'> *FT'|/FT'|null

F > V|(E)

V > a|b|c|d|e...|z

int main()

{

SIGN = 0; //SIGN用于指示赋值表达式是否出现错误

sym=0;

scanf("%s",&s);

if( s[0] == '\0') //没有输入的情况直接退出

return 0;

A();

if(s[sym]!='\0'&&SIGN==0)

{

printf("ERROR!\n");

exit(0);

}

return 0;

}

void A() // A > V:=E

{

V();

if(s[sym]==':'&&s[sym+1]=='=') //判断赋值号是否有拼写错误

{

sym+=2;

E();

printf("%s:=%s",Table[list_n2],Table[list_n1]);

printf(" (:=,%s,,%s)\n",Table[list_n1],Table[list_n2]);

}

else

{

printf("The assignment Symbol spelling mistakes!\n"); //

赋值号拼写错误

SIGN=1;

exit(0);

}

void V() // 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("Operand Errors!\n"); //运算对象错误

SIGN=1;

exit(0);

}

void E() //E > TE'

{

if(SIGN==0)

{

T();

E1();

}

void T() // T > FT'

{

if(SIGN==0)

{

F();

T1();

}

void E1() //E'> +TE'|TE'|null

{

int p;

if(SIGN==0)

{

if(s[sym] == '+'||s[sym]=='')

{

p=sym; //用p记录出现'+'或''时sym 的值

sym++;

T();

char ch[3];

ch[0] = 'T';

ch[1] = n;

ch[2] = '\0';

if(s[p] == '+')

{

printf("%s:=%s+%s",ch,Table[list_n2],Table[list_n1]); //输出三地址代码

printf(" (+,%s,%s,%s)\n", Table[list_n2],Table[list_n1],ch); //输出四元式

}

else

{

printf("%s:=%s%s",ch,Table[list_n2],Table[list_n1]);

//输出三地址代码

printf(" (,%s,%s,%s)\n", Table[list_n2],Table[list_n1],ch); //输出四元式

}

strcpy(Table[list_n2],ch); //将当前结果归结式放在符号表中

list_n;

n++;

E1();

}

void T1() // T'> *FT'|/FT'|null

{

int p;

if(SIGN==0)

{

if(s[sym] == '*'||s[sym]=='/')

{

p=sym;

sym++;

F();

char ch[3];

ch[0] = 'T';

ch[1] = n;

ch[2] = '\0';

if(s[p] == '*')

{

printf("%s:=%s*%s",ch,Table[list_n2],Table[list_n1]); //输出三地址代码

printf(" (*,%s,%s,%s)\n",