实验三递归下降法的语法分析器.doc

《实验三递归下降法的语法分析器.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、魏陈强23020092204168实验3递归下降法的语法分析器一、实验目的学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。二、实验内容用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录A.1，p394）program→blockblock→{stmts}stmts→stmtstmts

2、estmt→id=expr;

3、if(bool)stmt

4、if(

5、bool)stmtelsestmt

6、while(bool)stmt

7、dostmtwhile(bool);

8、break;

9、blockbool→expr

10、expr<=expr

11、expr>expr

12、expr>=expr

13、exprexpr→expr+term

14、expr-term

15、termterm→term*factor

16、term/factor

17、factorfactor→(expr)

18、id

19、num三、实验要求１．个人完成，提交实验报告。２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。测试

20、程序片断：{i=2;while(i<=100){sum=sum+i;i=i+2;}}对应的推导过程为：programÞblockÞ{stmts}Þ{stmtstmts}Þ{id=expr;stmts}Þ{id=num;stmts}Þ{id=num;stmtstmts}Þ{id=num;while(bool)stmtstmts}Þ{id=num;while(expr<=expr)stmtstmts}Þ{id=num;while(id<=expr)stmtstmts}Þ{id=num;while(id<=num)stmtst

21、mts}Þ{id=num;while(id<=num)blockstmts}Þ{id=num;while(id<=num){stmts}stmts}Þ．．．．．．．四、实验思路之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable[100][20]，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable[0]=”id”，finaltable[1]=”=”，finaltable[2]=”num”。并且，为了以后能够方便使用switch()

22、case语句，另外再定义一个一维整型数组finaltableint[100]，用于存放一个数字和finaltable[100][20]中的字符串对应。这里，我们定义if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800，<=17，<==16，>=15，>==14，+=13，&&=12，

23、

24、=11，}=10，{=9，；=8；)=7，(=6，==5，===4，!==3，/=2，id=1，keyword=0，num=99，*=18，-=19。然后

25、依据语法分析的正则表达式，参照实验一类似中缀改后缀的写法以及课本40页的伪代码编写。相比词法分析器，词法分析的时候，是以单个字符为一个单位，而语法分析，我们以字符串为单位，这些字符串即finaltable[100][20]中的字符串。编写的过程中涉及几个问题，1、如何把每一步的迭代都显示出来？对于这个问题，可以在每个非终结符函数的开头输出对应的迭代即可。2、在应用文法的时候，应该首先消除左递归，这是至关重要的，该实验我们只要消除expr()和term()的左递归即可。3、if语句二义性处理。对于这个问题，我们只要再往后看

26、一个字符串，看其是否是else，如果是，则匹配if(bool)stmtelsestmt，否则匹配if(bool)stmt。4、对于空选择，如何处理？一开始的时候，我选择暂时忽略。五、实验代码#include#include#include/*if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800，<=17，<==16，>=15，>==14，+=13，&&=12，

27、

28、=11，}=10，{

29、=9，；=8；)=7，(=6，==5，===4，!==3，/=2，id=1，keyword=0，num=99，*=18，-=19*/char*keyword[8]={"if","for","else","while","do","float","int","break"};charkeywordtable[20][2