编译原理LL1文法

主要思路及其算法

1、判断各非汇总结符是否可以推出空

   （1）将各非终结符出示状态置为“未知”

   （2）按顺序扫描各产生式右部。分为下面几种情况：

        a、若遇到符号“ε”，检查左部非终结符状态，若不是“空”，将其置为“空”，继续扫描下一产生式；

        b、若遇到终结符，检查左部非终结符状态，若为“未知”，将其置为“非空”，继续扫描下一产生式；

        c、若遇到非终结符，检查该非终结符状态，若为“未知”，则跳过当前产生式，扫描下一产生式；若为“非空”，检查左部非终结符状态，若为“未知”，将其置为“非空”，继续扫描下一产生式；

若为“空”，继续扫描本产生式的下一符号；

        d、若遇到“\0”，检查左部非终结符状态，若不是“空”，将其置为“空”，继续扫描下一产生式；

        e、若上述a,b,c,d过程引起了非终结符状态的改变，则跳到(2)处继续循环，否则跳出循环，判断结束。

2、求非终结符的first集

扫描以要求first集的非终结符为左部的各产生式的右部，分为下面几种情况：

     A、若遇到终结符，将该终结符加入左部非终结符的first集，继续扫描下一产生式；

     B、若遇到符号“ε”，将“ε”加入左部非终结符的first集，继续扫描下一产生式；

      C、若遇到非终结符，将该非终结符的  first集— {ε}加入左部非终结符的first集，然后检查该非终结符是否可以推出空，若可以为空，则扫描本产生式的下一符号；若不为空，则继续扫描下一产生式；

     D、若遇到“\0”，将“ε”加入左部非终结符的first集，继续扫描下一产生式；

3、求某一非终结符的FOLLOW集

   （1）在产生式右部找到该非终结符，扫面它后面的符号，分为下面几种情况：

   A、若是终结符，则将该终结符加入该非终结符的folow集；

   B、若是非终结符，将该非终结符的  first集— {ε}加入该非终结符的folow集，然后检查该非终结符是否可以推出空，若可以为空，则扫描本产生式的下一符号；

   C、若是“\0”，则将该产生式的左部非终结符的follow集加入它的follow集。

   （2）在产生式的右部继续查找该非终结符，若找到，转（1）步。

4、求某产生式的select集

   扫描产生式的右部，分为下面几种情况：

(1) 若是终结符，则将该终结符加入该产生式的select集；

(2) 若是“ε”，将左部非终结符的follow集加入该产生式的select集；

(3) 若是非终结符，将该非终结符的 first集— {ε}加入该产生式的select集，然后检查该非终结符是否可以推出空，若可以为空，则扫描本产生式的下一符号；

(4) 若是“\0”，则将该产生式的左部非终结符的follow集加入该产生式的select集。

代码：

package byyl;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.nio.charset.Charset;
import java.util.*;


public class LL1 {

    public static int find(char v) {
        /*if(v=='a'||v=='b'||v=='c'||v=='d'){
            return 1;
        }
        else{
            return 0;
        }*/
        if(v=='+'||v=='*'||v=='('||v==')'||v=='i'){
            return 1;
        }
        else{
            return 0;
        }
    }
    public static String shutdown(){
        //return "abc#";
        return "i+*()#";
    }
    public static void start() {
        System.out.println("LL(1)语法分析演示程序-----------------------------李欣");
        System.out.println("  1.输入LL(1)文法\n");
        System.out.println("  2.显示输入的LL(1)文法\n");
        System.out.println("  3.判定非终结符是否为空\n");
        System.out.println("  4.输出非终结符的First集\n");
        System.out.println("  5.输出非终结符的Follow集\n");
        System.out.println("  6.输出产生式的Sellect集\n\t");
        System.out.println("  7.分析过程演示\n\t");
        System.out.println("    请输入你想要做的操作:");
    }
    
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        Scanner in = new Scanner(System.in);
        start();
        int choose=0;
        String o = in.nextLine();
        choose=Integer.parseInt(o);
        while(choose!=1) {
            System.out.println("输入错误请重新输入：");
            o = in.nextLine();
            choose=Integer.parseInt(o);
        }
    
        String []t = new String [50];    //字符串形式存入 
        int []s= new int [26];     //  存放左部起始符 
        int i=0;
        int top;    
        int n;
        int count=0;  // 
        char []mov = new char[50];
        System.out.println("请输入个数");
        o = in.nextLine();
        n = Integer.parseInt(o);
        
        
        for(i=0;i<26;i++){
            s[i]=5;
        }
        System.out.println("请输入文法");
        i = 0;
        while(i<n){
            char ch;
            t[i] = in.nextLine();
            ch = t[i].charAt(0);
            if(s[ch-'A']==5) {
                s[ch-'A']=-1; //-1表示未知
                mov[count]=ch;
                count++;
            }
            i++;
        }
        
        /***********************************************************************************************/
    //    System.out.println();
    //    System.out.println("判断是为空:");
        int len;
        int j;
        top = n;
        for(i=0;i<top;i++){
            len = t[i].length();        
            for(j=3;j<len;j++){
                if(t[i].charAt(j)=='\0'){
                    s[t[i].charAt(0)-'A']=0;
                    break;
                }
                if(s[t[i].charAt(0)-'A']==0){        
                    break;
                } 
        /*a*/    if(t[i].charAt(j)=='@'){
                    s[t[i].charAt-'A']=0;    //遇到符号ε表示空 
                    break;
                }
        /*b*/    if(find(t[i].charAt(j))==1){    //遇到终结符，检查左部非终结符状态
                    if(s[t[i].charAt(0)-'A']==-1){
                        s[t[i].charAt(0)-'A']=1;
                        break;    
                    }     
                        
                } 
                
        /*c*/    if(find(t[i].charAt(j))==0){  //遇到非终结符，检查该非终结符状态
                    if(s[t[i].charAt(j)-'A']==-1){//若为"未知"，则跳过当前产生式，扫描下一产生式                    
                        String vc = new String();
                        vc=t[i];
                        t[top]=vc;
                        top++;
                        break;
                    }     
                    if(s[t[i].charAt(j)-'A']==1){    //若为"非空"，检查左部非终结符状态，
                        if(s[t[i].charAt(0)-'A']==-1){
                            s[t[i].charAt(0)-'A']=1;                    //若为"未知"，将其置为"非空"，继续扫描下一产生式；
                        }    
                        break;        
                    } 
                    if(s[t[i].charAt(j)-'A']==0){//若为"空"，继续扫描本产生式的下一符号；
                            if(j+1==t[i].length()){
                                s[t[i].charAt(0)-'A']=0;
                                break;
                            }
                    }         
                }
            }
        } 
        /*for(i=0;i<26;i++){
            if(s[i]==1){
                char ch = (char) (i+'A');
                System.out.println( ch+"为非空");
            }
            if(s[i]==0){
                char ch = (char) (i+'A');
                System.out.println( ch+"为空");
            }
        }*/
        
        
        /****************************************************************************************/
        //System.out.println();
        //System.out.println("First集：");
        Set []first = new HashSet[26];
        top = n;
        int []flag = new int [26];
        for(i=0;i<26;i++) {
            flag[i]=0;
        }
        for(i=0;i<top;i++) {
            char ch = t[i].charAt(0);
            if(flag[ch-'A']==0) {
                flag[ch-'A']=1;
                first[ch-'A'] = new HashSet();
            }
            for(j=3;j<=t[i].length();j++) {
                if(j==t[i].length()){              //若遇到“\0”，将“ε”加入左部非终结符的first集，继续扫描下一产生式；
                    first[(int)ch-'A'].add('@');
                    break;
                }
                if(find(t[i].charAt(j))==1) {        //若遇到终结符，将该终结符加入左部非终结符的first集，继续扫描下一产生式；
                    
                    first[(int)ch-'A'].add(t[i].charAt(j));
                    break;
                }
                if(t[i].charAt(j)=='@') {            //若遇到符号“ε”，将“ε”加入左部非终结符的first集，继续扫描下一产生式；
                    
                    first[(int)ch-'A'].add('@');
                    break;
                }
                if(find(t[i].charAt(j))==0) {        //若遇到非终结符，将该非终结符的  first集— {ε} 加入左部非终结符的first集
                    if(top<2*n) {
                        String vc = new String();
                        vc=t[i];
                        t[top]=vc;
                        top++;
                    }
                    if(first[(int)t[i].charAt(j)-'A']!=null) {    
                        Iterator<Character> it  = first[(int)t[i].charAt(j)-'A'].iterator();        //利用迭代器遍历
                        while(it.hasNext()) {
                            char chr = it.next();
                            if(chr!='@')
                            first[(int)ch-'A'].add(chr);
                        }
                    }
                    if(s[t[i].charAt(j)-'A']==0) {    //然后检查该非终结符是否可以推出空，若可以为空，则扫描本产生式的下一符号；
                        continue;
                    }
                    else {                            //若不为空，则继续扫描下一产生式；
                        break;
                    }
                }
            }
        }
        /*for(i=0;i<26;i++) {
            if(s[i]!=5) {
                System.out.println((char)(i+'A')+"的first集"+first[i].toString());
            }
        }*/
        /*******************************************************************************************************************************/
        //System.out.println();
        //System.out.println("Follow集：");
        Set []follow = new HashSet[26];
        top = n;
        for(i=0;i<26;i++) {
            flag[i]=0;
        }
        int l;
        for(i=0;i<count*n;i++) {                
            char ch = mov[i%count];    //ch为当前要检测的字符
        //    System.out.println("当前检测字符为"+ch);
            if(flag[ch-'A']==0) {
                flag[ch-'A']=1;                        //分配空间
                follow[ch-'A'] = new HashSet();
            }
            follow[mov[0]-'A'].add('#');
            for(j=0;j<top;j++) {                    //五个式子
            //    System.out.println("               当前是第"+j+"个式子");
                for(l=3;l<t[j].length();l++) {            //每个式子从头到尾
                    if(t[j].charAt(l)==ch) {
            //            System.out.println("                         第"+j+"个式子的第"+(l-2)+"个字符匹配成功");
                        int q;
                        for(q=l+1;q<=t[j].length();q++) {            
                            if(q==t[j].length()) {    //若是“\0”，则将该产生式的左部非终结符的follow集加入它的follow集。
            //                    System.out.println("                            进入1");
                                if(follow[(int)t[j].charAt(0)-'A']!=null) {
                                    Iterator<Character> it  = follow[(int)t[j].charAt(0)-'A'].iterator();        //利用迭代器遍历
                                    while(it.hasNext()) {
                                        char chr = it.next();
                                        if(chr!='@')
                                        follow[(int)ch-'A'].add(chr);
                                    }
             //                        System.out.println("                                    "+ch+"的follow集合为"+follow[(int)ch-'A']);
                                }
                                break;
                            }
                            if(find(t[j].charAt(q))==1) {            //若是终结符，则将该终结符加入该非终结符的follow集；
                //                System.out.println("                              进入2");
                                follow[ch-'A'].add(t[j].charAt(q));
                                break;
                            }
                            if(find(t[j].charAt(q))==0) {            //若是非终结符，将该非终结符的  first集— {ε} 加入该非终结符的follow集，
                //                System.out.println("                               进入3");
                                Iterator<Character> it  = first[(int)t[j].charAt(q)-'A'].iterator();        //利用迭代器遍历
                //                System.out.println("                                                                  "+t[j].charAt(q));
                                while(it.hasNext()) {
                                    char chr = it.next();
                                    if(chr!='@')
                                    follow[(int)ch-'A'].add(chr);
                                }
                //                System.out.println("                                 "+ch+"的follow集合为"+follow[(int)ch-'A']);
                                if(s[t[j].charAt(q)-'A']==0) {        //然后检查该非终结符是否可以推出空，若可以为空，则扫描本产生式的下一符号；
                //                    System.out.println("                                 进入3.5");
                                    continue;
                                }
                            }
                        }
                    }
                }
            }
        }
        /*for(i=0;i<26;i++) {
            if(s[i]!=5) {
                System.out.println((char)(i+'A')+"的follow集"+follow[i].toString());
            }
        }*/
    /***********************************************************************************************************************************************************************/
        //System.out.println();
        //System.out.println("Select集：");
        Set []select = new HashSet[n];
        top = n;
        for(i=0;i<n;i++) {
            select[i] = new HashSet();
        }
        for(i=0;i<n;i++) {
            for(l=3;l<=t[i].length();l++) {
                if(l==t[i].length()) {
                    Iterator<Character> it  = follow[(int)t[i].charAt(0)-'A'].iterator();        //利用迭代器遍历
                    while(it.hasNext()) {
                        char chr = it.next();
                        select[i].add(chr);
                    }
                    break;
                }
                if(find(t[i].charAt(l))==1) {        //若是终结符，则将该终结符加入该产生式的select集；
                    select[i].add(t[i].charAt(l));
                    break;
                }
                if(t[i].charAt(l)=='@') {            //若是“ε”，将左部非终结符的follow集加入该产生式的select集
                    Iterator<Character> it  = follow[(int)t[i].charAt(0)-'A'].iterator();        //利用迭代器遍历
                    while(it.hasNext()) {
                        char chr = it.next();
                        select[i].add(chr);
                    }
                    break;
                }
                if(find(t[i].charAt(l))==0) {        //若是非终结符，将该非终结符的  first集— {ε} 加入该产生式的select集
                    Iterator<Character> it  = first[(int)t[i].charAt(l)-'A'].iterator();        //利用迭代器遍历
                    while(it.hasNext()) {
                        char chr = it.next();
                        if(chr!='@')
                        select[i].add(chr);
                    }
                    if(s[t[i].charAt(l)-'A']==0) {    //然后检查该非终结符是否可以推出空，若可以为空，则扫描本产生式的下一符号
                        continue;
                    }
                    else {
                        break;
                    }
                }
            }
        }
        /*for(i=0;i<n;i++) {
            System.out.println(t[i]+"的select集为"+select[i].toString());
        }*/
        /*********************************************************************************************************************/
        //System.out.println();
        //System.out.println("判断是否为LL(1)文法：");
        int judge=0;
        for(i=0;i<n;i++) {
            for(j=i+1;j<n;j++) {
                if(t[i].charAt(0)==t[j].charAt(0)) {
                    Set<Character> result = new HashSet<Character>();
                    result.clear();
                    result.addAll(select[i]);
                    result.retainAll(select[j]);
                    if(result.size()!=0) {
                        judge=1;
                        break;
                    }
                }
            }
            /*if(judge==1) {
                System.out.println("该文法不是LL(1)文法");
                break;
            }
            else {
                System.out.println("该文法是LL(1)文法");
            }*/
        }
        /*********************************************************************************************************************/
        //System.out.println();
        //System.out.println("构建的预测分析表：");
        int [][]graph=new int [26][20];
        for(i=0;i<26;i++) {
            for(j=0;j<20;j++) {
                graph[i][j]=1024;
            }
        }
        String end = shutdown();
        for(i=0;i<n;i++) {
            for(j=0;j<end.length();j++) {
                if(select[i].contains(end.charAt(j))) {
                    graph[t[i].charAt(0)-'A'][j]=i;
                }
            }
        }
        /*for(i=0;i<end.length();i++) {
            System.out.print("    "+end.charAt(i)+"    ");
        }
        System.out.println();
        for(i=0;i<count;i++) {
            System.out.print(mov[i]);
            for(j=0;j<end.length();j++) {
                if(graph[mov[i]-'A'][j]!=1024) {
                    System.out.print("   "+t[graph[mov[i]-'A'][j]]);
                }
                else {
                    System.out.print("   "+"error");
                }
            }
            System.out.println();
        }*/
        /*************************************************************************************************************************************/
        /*************************************************************************************************************************************/
        while(true){
            start();
            o = in.nextLine();
            choose=Integer.parseInt(o);
            while(choose>7) {
                System.out.println("输入错误请重新输入：");
                o = in.nextLine();
                choose=Integer.parseInt(o);
            }
            if(choose==2) {
                                        for(i=0;i<n;i++) {
                                            System.out.println(t[i]);
                                        }
            }
            if(choose==3) {
                                        for(i=0;i<26;i++){
                                            if(s[i]==1){
                                                char ch = (char) (i+'A');
                                                System.out.println( ch+"为非空");
                                            }
                                            if(s[i]==0){
                                                char ch = (char) (i+'A');
                                                System.out.println( ch+"为空");
                                            }
                                        }
            }
            if(choose==4) {
                                        for(i=0;i<26;i++) {
                                            if(s[i]!=5) {
                                                System.out.println((char)(i+'A')+"的first集"+first[i].toString());
                                            }
                                        }
            }
            if(choose==5) {
                                        for(i=0;i<26;i++) {
                                            if(s[i]!=5) {
                                                System.out.println((char)(i+'A')+"的follow集"+follow[i].toString());
                                            }
                                        }
                                        
            }
            if(choose==6) {
                                        for(i=0;i<n;i++) {
                                            System.out.println(t[i]+"的select集为"+select[i].toString());
                                        }

                                        System.out.println();
                                        if(judge==1) {
                                            System.out.println("该文法不是LL(1)文法");
                                        }
                                        else {
                                            System.out.println("该文法是LL(1)文法");
                                        }
                                        System.out.println();
                                        
                                        for(i=0;i<end.length();i++) {
                                            System.out.print("    "+end.charAt(i)+"    ");
                                        }
                                        System.out.println();
                                        for(i=0;i<count;i++) {
                                            System.out.print(mov[i]);
                                            for(j=0;j<end.length();j++) {
                                                if(graph[mov[i]-'A'][j]!=1024) {
                                                    System.out.print("   "+t[graph[mov[i]-'A'][j]]);
                                                }
                                                else {
                                                    System.out.print("   "+"error");
                                                }
                                            }
                                            System.out.println();
                                        }
            }
            if(choose==7) {
                if(judge==1) {
                    System.out.println("该文法不是LL(1)文法!!不能进行LL(1)分析！！！");
                }
                else {
                    String str = new String();
                    System.out.println("请输入要分析的符号串(以#号结尾):");
                    str=in.nextLine();
                    Stack vc = new Stack();
                    vc.push('#');
                    vc.push(t[0].charAt(0));
                    System.out.println("步骤    "+"分析栈                                                         "+"剩余串                                                         "+"产生式或匹配");
                    //
                    i=0;
                    l=0;
                    int c=0;
                    String copy=new String();
                    copy=str;
                    StringBuffer way = new StringBuffer();
                    way.append(t[0].charAt(0));
                    while((char)vc.peek()!='#'||str.charAt(i)!='#') {
                        System.out.print(l+"   "+vc.toString()+"                   "+str+"                   ");
                        if((char)vc.peek()==str.charAt(i)) {
                            System.out.println(str.charAt(i)+"匹配");
                            vc.pop();
                            str=str.substring(1);
                            c++;
                        }
                        else if(find((char)vc.peek())==0) {
                            j = graph[(char)vc.peek()-'A'][end.indexOf(str.charAt(i))];
                            if(j==1024) {
                                System.out.println("分析出错！！！！！！停止分析");
                            //    System.out.println((char)vc.peek()+" "+str.charAt(i)+" "+i);
                                break;
                            }
                            else {
                                System.out.println(t[j]);
                                vc.pop();
                                if(t[j].charAt(3)!='@') {
                                    for(int k=t[j].length()-1;k>=3;k--) {
                                        vc.push(t[j].charAt(k));
                                    }
                                }
                                //
                                way.append(" => ");
                                way.append(copy.substring(0,c));
                                int z;
                                for(z=vc.size()-1;z>0;z--) {
                                    way.append(vc.get(z));
                                }
                            }
                        }
                        else {
                            System.out.println("分析出错！！！！！！");
                            break;
                        }
                    }
                    if((char)vc.peek()=='#'&&str.charAt(i)=='#') {
                        System.out.println(l+"   "+vc.toString()+"                   "+str+"                   "+"接受");
                        System.out.println("最右推导"+way);
                    }
                }
            }
        }
    }
}