递归下降计算器.doc

递归下降计算器
全文5页1405字 叙述详尽
一、 实验题目
1、 重写程序清单4-1的递归下降计算器，使其根据3.3.2节的声明返回一个语法树。
2、 写出一个以语法树作为参数的函数，它得到上面的代码生成的语法树，并由移动树返回计算的值。
二、 分析算法
此次实验要求采用递归下降的方法产生输入串的语法树，并用移动树来计算最终的值。因此我采用VC++软件开发平台来完成，主要考虑到生成语法树需要采用结构体来表示每个结点，而在c++中我们可以用类来完好的封装一个结点类，使程序更加直观。封装好结点类后，我们就可以用其提供的接口进行语法树的构造了。然后可以对书上的程序进行改造，在书上程序中计算的地方，我们就用构造语法树的代码来替代。最终形成语法树。在计算最终结果的代码中，我采用后序遍历语法树的方法来计算最终结果。
三、 算法思路
1、 采用的数据结构：
typedef enum { add,minus,mulop,none } OpKind; //枚举操作类型
streeNode类用来存储语法树中的结点。
2、 采用的方法：
A） 实现构建语法树：用streeNode表示语法树的结点，对书上的程序进行改造，在书上程序中计算的地方，我们就用构造语法树的代码来替代。最终形成语法树。
B） 计算最终结果：后序遍历语法树即可。
六、 实验体会
通过这次实验，加深了我对编译器设计中递归下降方法和构造语法树的了解。在此次实验中，采用C＋＋封装结点类使程序更直观，在设计过程中，碰到了如何区分叶子结点和分支结点的问题，其实可以采用建立两个类分别表示叶子结点和分支结点的方法来区分，然而这会影响程序设计的复杂性和可读性。所以最后我就采取统一一个类表示两种结点的方法来完成设计。其实，这个实验并不难，算法也很简单，只要自己去做，就能完成它。