递归下降分析算法

《递归下降分析算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、(二)编译原理部分一、课程设计目的在进行了专业基础课和《编译原理》课程的基础上，设计一个实际的程序语言的编译系统旨在加深对程序语言结构和机器处理方式的理解，初步掌握高级语言到机器指令的转换的基本方法，提高进行工程设计的基本技能及分析、解决实际问题的能力，为毕业设计和以后的工程实践打下良好的基础。二、课程实习任务构造文法的递归下降分析三、设计思路和算法描述1.基本原理递归下降法是语法分析中最易懂的一种方法。它的主要原理是，对每个非终极符按其产生式结构构造相应语法分析子程序，其中终极符产生匹配命令，而非终极符则产生过程调用

2、命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。其中子程序的结构与产生式结构几乎是一致的。2.文法要求递归下降法要满足的条件：假设A的全部产生式为A1

3、a2

4、……

5、an，则必须满足如下条件才能保证可以唯一的选择合适的产生式predict(A->aj)Apredict(A->aj)=(P/当iHj.3.实现原理假设文法屮有如下的产生式AT%

6、卩2I...I仇，则应按如下方法编写语法分析子程序procedureA()beginiftokensPredict(A->pi)then0(pi)e

7、lseiftokenePredict(A^p2)then0(p2)else讦tokenePredict(A->卩“then8(血)elseerror()end四、实验步骤1.求SNL文法中每个产生式Predict集合Predict(A->P)=First(P),当EgFirst(卩)=(First(p)-{e})UFollow(A),当ewFirst(p)根据Predict集合的定义求SNL的文法中每个产生式的Predict集合，判断是否满足递归下降法分析条件，若不满足用消除左递归和消除公共前缀等文法等价变化算法对文法

8、进行变换，使其满足递归下降法的要求。五、程序设计publicclassMain{staticStringstr;//整个字符串staticintptr,//游标len,〃字符串长度step;//步骤staticbooleanright;staticbooleanAdvance(){//前进一个字符if(ptr

9、(step+"t"+str・charAt(ptr)+"t"+s++str.substring(ptr));}staticvoidE(){pri(〃E->TG〃)；TO;GO;}staticvoidG(){if(str・charAt(ptr)='+'){pri(〃G->+TG〃)；if(!Advance()){return;}TO;GO;}elseif(str.charAt(ptr)二二'){pri(〃G->-TG〃)；辻(！Advance。){return;}TO;G();}else{pri(〃G->e“)；}}s

10、taticvoidT(){pri(〃T->FS〃)；F();S();}staticvoidS(){if(str.charAt(ptr)二二'*'){pri(〃S->*FS〃)；辻（！Advance。）｛return;F();SO;}elseif(str.charAt(ptr)=='/'){pri(〃S->/FS〃);if(!Advance()){return;}F();SO;}else{pri(〃S->£”)；}}staticvoidF(){if(str.charAt(ptr)='('){priCF—>(E)〃)；if

11、(!Advance()){return;}E();if(str・charAt(ptr)二二')'){if(!Advance()){return;}else{Error();}}elseif(str.charAt(ptr)=='i'){pri("F-〉i");if(!Advance()){return;}}else{Error();}}staticvoidError(){right二false;prirError!，z);if(!Advance()){return;}}publicstaticvoidmain(Strin

12、g[]args)Scannersc=newScanner(System,in);str=newString(sc.next());ptr二step=0;right二true;len=str・length();System,out.printin步骤t当前t产生式t输入串“);E();if(right&&ptr==len-1)