编译原理实验——递归下降分析法（回溯）

1、实验目的与内容

采用递归下降分析法&＃xff0c;根据下列文法内容编写程序&＃xff1a;

E → TE’
E’ → ATE’|ε
T → FT’
T’ → MFT’ |ε
F → (E) | i
A → &＃43; | -
M → * | /


输入&＃xff1a;一个表达式&＃xff0c;例如”i*i&＃43;i-i“。

输出&＃xff1a;该表达式的分析&＃xff0c;例如&＃xff08;打印是倒着的&＃xff09;&＃xff1a;

2、程序总体设计思路和框架

无回溯递归下降分析要先手动求出select集&＃xff0c;为了避免手动求解的麻烦&＃xff08;主要是懒&＃xff09;&＃xff0c;采用有回溯递归下降分析的方法。

根据产生式编写函数&＃xff0c;一个产生式对应一条函数。有多个候选式的情况下&＃xff0c;默认产生式选择第一条候选式&＃xff0c;如果推出错误&＃xff0c;回溯时选择下一条候选式。

函数退出递归的条件以及回溯的状态重置&＃xff0c;这是主要的难点。

3、主要的数据结构和流程描述

为了打印出上图所示的结果&＃xff0c;每一条使用一个信息节点&＃xff08;info_node)来表示。

struct info_node //保存分析步骤的信息
{//int steps_number;//分析步骤号string grammer; //用到的语法string hv_ana; //已经分析过的字符串char bi_ana; //正在分析的字符string rem_str; //剩余的字符串info_node(/*int steps_number,*/ string grammer, string hv_ana, char bi_ana, string rem_str){//this->steps_number &＃61; steps_number;this->grammer &＃61; grammer;this->hv_ana &＃61; hv_ana;this->bi_ana &＃61; bi_ana;this->rem_str &＃61; rem_str;}
};


没进行一次推导&＃xff0c;就产生一个node&＃xff0c;存放推导使用的文法&＃xff0c;已分析的串&＃xff0c;正在分析的字符以及未分析的串。

4、测试结果与说明

一个正确的测试例子如1&＃xff0c;下面显示一个错误的测试例子&＃xff1a;

输入&＃xff1a;i*

输出&＃xff1a;

5、实验收获与反思

加强了写回溯算法的能力。

附录

代码地址