递归下降分析器程序(c语言版,编译原理实验)

递归下降分析器设计

1、实验目的：

2、（1）掌握自上而下语法分析的要求与特点。

3、（2）掌握递归下降语法分析的基本原理和方法。

4、（3）掌握相应数据结构的设计方法。

5、2、实验内容：

6、编程实现给定算术表达式的递归下降分析器。

7、算术表达式文法如下：

8、E-->E+T|T

9、T-->T*F|F

10、F-->(E)|i

11、3、设计说明：

12、首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。

13、4、设计分析

14、这个题目属于比较典型的递归下降语法分析。需要先将原算术表达式方法改写为LL(1)文法为：

15、E-->TE'

16、E'-->+TE'|ε

17、T-->FT'

18、T'-->*FT'|ε

19、F-->(E)|i

20、然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而实现递归下降语法分析的功能。

21、具体方法为：

22、（1）当遇到终结符a时，则编写语句

23、If(当前读到的输入符号==a)读入下一个输入符号

24、（2）当遇到非终结符A时，则编写语句调用A()。

25、（3）当遇到A-->ε规则时，则编写语句

26、If(当前读到的输入符号不属于Follow(A))error()

27、（4）当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一个候选式进行推导.

28、#include

void E();

void T();

void E1();

void T1();

void F();

char s[100];

int i, SIGN;

int main()

{

printf(\"请输入一个语句，以#号结束语句（直接输入#号推出）\\n\");

while( 1 )

{

SIGN = 0;

i=0;

scanf(\"%s\

if( s[0] == '#')

return 0;

E();

if(s[i]=='#')

printf(\"正确语句！\\n\");

printf(\"请输入一个语句，以#号结束语句\\n\");

}

return 1;

}

void E()

{

if(SIGN==0)

{

T();

E1();

}

}

void E1()

{

if(SIGN==0)

{

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

{

++i;

T();

E1();

}

else if(s[i]!='#'&&s[i]!=')')

{

printf(\"语句有误！\\n\");

SIGN=1;

}

}

}

void T()

{

if(SIGN==0)

{

F();

T1();

}

}

void T1()

{

if(SIGN==0)

{

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

{

++i;

F();

T1();

}

else if(s[i]!='#'&&s[i]!=')'&&s[i]!='+')

{

printf(\"语句有误！\\n\");

SIGN=1;

}

}

}

void F()

{

if(SIGN==0)

{

if(s[i]=='(')

{

++i;

E();

if(s[i]==')')

++i;

else if(s[i]== '#')

{

printf(\"语句有误！\\n\");

SIGN=1;

++i;

}

}

else if(s[i]=='i')

++i;

else

{

printf(\"语句有误！\\n\");

SIGN=1;

}

}

}

测试用例

（1）输入i，预期显示语句正确！

（2）输入iii，预期显示语句有误！

（3）输入a，预期显示语句有误！

（4）输入(i)，预期显示语句正确！

（5）输入(a)，预期显示语句有误！

（6）输入(i+i)，预期显示语句正确！

（7）输入(i+i，预期显示语句有误！

（8）输入((i*i)+i)*i，预期显示语句正确！

（9）输入((((i+i*i))))，预期显示语句正确！

（10）输入(i+ia，预期显示语句有误！

（11）输入i+i*i+i*a，预期显示语句有误！