编译原理-递归下降分析法

puffmoff 2018-02-03 原文

题：对下列文法，用递归下降分析法对任意输入的符号串进行分析：

（1）E->TG

（2）G->+TG|—TG

（3）G->ε，

（4）T->FS

（5）S->*FS|/FS

（6）S->ε

（7）F->(E)

（8）F->i

答：文法太多，可先合并。

（1）E->FSG

（2）G->+TG|—TG|ε

（3）S->*FS|/FS|ε

（4）F->(E)|i

结合1，4

（1）E->ESG|iSG

（2）G->+TG|—TG|ε

（3）S->*FS|/FS|ε

（4）F->(E)|i

消除左递归

（1）E->iSGE1

（2）E1->SGE1|ε

（3）G->+TG|—TG|ε

（4）S->*FS|/FS|ε

（5）F->(E)|i

好吧，其实上面的化简有些地方并无必要，不过我的代码是按照最后的文法写的。

package compile;

public class com {
    public static String str="i+i*i";   //待测试语句
    static int seri=0;                  //记录当前读到的序号
    public static void main(String[] args) {
        int t=E();                      //文法
        
        if(t==1) {
            System.out.println(str+" compiled successfully");
        }
        else {
            System.out.println(str+" compiled failed");
        }
    }
    static char getchar() {                       
        if(seri<str.length()) {
            System.out.println(seri+" "+str.charAt(seri));
            return str.charAt(seri++);
        }            
        return ' ';        
        };
    static int E() {
        char ch=getchar();
        if(ch!='i') {
            return  0;
        }return S()*G()*E1();
    }
    static int S() {
        char ch=getchar();
        if(ch=='+'|ch=='-') {
            seri--;return 1;
        }else if(ch=='*'|ch=='/') {
            return F()*S();
        }else if(ch=='i') {
            return 0;
        }
        return 1;        
    }
    static int F() {
        char ch=getchar();
        if(ch=='i') return 1;
        return E();
    }
    static int G() {
        char ch=getchar();
        if(ch=='*'|ch=='/') {
            seri--;return 1;
        }else if(ch=='+'|ch=='-') {
            return F()*S()*G();
        }else if(ch=='i') {
            return 0;
        }
        return 1;            
    }
    static int E1() {
        char ch=getchar();
        if(ch=='i') return 0;
        if(ch==' ') return 1;
        return S()*G()*E1();        
    }    
}