simplepriority_grammeranalysis.java

这是简单优先文法分析器

package compiler;

import javax.swing.JOptionPane;

public class SimplePriority_GrammerAnalysis {

	
	public static void main(String[] args) {
		String strV_N_T=JOptionPane.showInputDialog(null,"enter a string(upper-case,lower-case leters other symbol)",
	              "输入终结符&终结符",JOptionPane.QUESTION_MESSAGE);
		int len=strV_N_T.length();
		int n=6;
		String[] WenFa=new String[n];
		for(int i=0;i<n;i++){
		    String strWenFa=JOptionPane.showInputDialog(null,"enter a wenfa（upper-case＝upper-case，lower-case leters other symbol）并且第一个输入以识别符号开头的产生式",
	              "输入文法",JOptionPane.QUESTION_MESSAGE);
		    WenFa[i]=strWenFa;
		}
		StringBuffer S=new  StringBuffer("#");
		String TR=JOptionPane.showInputDialog(null,"enter a string(end with #)",
	              "example 2.1 output",JOptionPane.QUESTION_MESSAGE);
		int [][]First=new int[len][len];
		int [][]Last=new int[len][len];
		int [][]Equals=new int[len][len];
		for(int i=0;i<n;i++){
			for(int j=0;j<len;j++){
				char ch=strV_N_T.charAt(j);
				if(WenFa[i].startsWith(String.valueOf(ch))){
					int k=strV_N_T.indexOf(WenFa[i].charAt(2));
					First[j][k]=1;
				}
				if(WenFa[i].endsWith(String.valueOf(ch))){
					int k=strV_N_T.indexOf(WenFa[i].charAt(0));
					Last[k][j]=1;
				}
		    }
			int  p,q,k=2;
			while(k<WenFa[i].length()){
				p=strV_N_T.indexOf(WenFa[i].charAt(k++));
				if(k<WenFa[i].length()){
				    q=strV_N_T.indexOf(WenFa[i].charAt(k));
				    Equals[p][q]=1;
				
			    }
			}	
	    }
		char [][]M=new char[len][len];
		M=PriorityMatrix(First,Last,Equals,len);
		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++)
				System.out.print(M[i][j]+"\t");
				 
		System.out.println();
		}
	    
	
		
		System.out.println("----------Start Analyzing------------");
		
		int i=0,j=0,s=0;
		while(j<TR.length()){
			if(S.charAt(i)=='#')   S.append(TR.charAt(j));
			else if(M[strV_N_T.indexOf(S.charAt(i))][strV_N_T.indexOf(TR.charAt(j))]==' '){
				 System.out.println("error");
				 break;
			}
			else if(M[strV_N_T.indexOf(S.charAt(i))][strV_N_T.indexOf(TR.charAt(j))]=='>'){
				 int k=i;
				 while(M[strV_N_T.indexOf(S.charAt(k-1))][strV_N_T.indexOf(TR.charAt(k))]=='>')
				 {   
					 k--;
					 continue;
				 }
				 if(M[strV_N_T.indexOf(S.charAt(k-1))][strV_N_T.indexOf(TR.charAt(k))]=='<'){
				   while(s<n){
					 String subS=WenFa[s].substring(2); 
					 if(subS.equals(S.subSequence(k, i))){
						 S.delete(k, i);
						 i=k;
						 S.append(WenFa[s].charAt(0));
					 }
					 else if(S.charAt(i)==WenFa[0].charAt(0)&&TR.charAt(j)=='#'){
						 System.out.println("OK");  
						 break;
					 }
					 else{
						 System.out.println("error"); 
						 break;
					 }
					 s++;
				   }// end of while	                              
				 }
			}//*
			else
			{
				i++;
				S.append(TR.charAt(j));
				j++;
			}
				 
		}
	}

	public static int[][]  Warshall(int[][]M){
		 int n=M.length;
		 for(int i=0;i<n;i++){
		     for(int j=0;j<n;j++){
		           if(M[j][i]==0) 
		        	      continue;
		            else{
		              for(int k=0;k<n;k++)
		        	    if(M[i][k]==0)  
		        		  continue;
		        	     else{
		        		  M[j][k] =1;
		        	     }
		            }
		     }
		}
		return M;    
	}
		
	public static char[][] PriorityMatrix(int [][]First ,int [][]Last ,int [][]Equals ,int len){
		char [][]Matrix=new char[len][len];
		int [][]Larger=new int[len][len];
		int [][]Smaller=new int[len][len];
		int[][]first=Warshall(First);
		int[][]first$=first;
		int[][]last=Warshall(Last);
		int [][]a=new int[len][len];
	
		for(int i=0;i<len;i++){
			for(int j=0;j<=i;j++){
				if(i==j)  first$[i][j]=1;     //由（first)+得到（first）*
				int temp=last[i][j];          //转置（last)+
				last[i][j]=last[j][i];
				last[j][i]=temp;
				
			}
		}
		
		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++){   
				for(int k=0;k<len;k++){
				Smaller[i][j]+=Equals[i][k]*first[k][j] ;  //求低优先矩阵 {<}
			      a[i][j]+=last[i][k]*Equals[k][j];   //求得(（last）+)T[][]*equals[][]
			    }                                         
		    }
		}
		System.out.println("smaller");
		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++)
				System.out.print(Smaller[i][j]+"\t");
				 
		System.out.println();
		}
		
		for(int i=0;i<len;i++){            //求高优先矩阵{>}
			for(int j=0;j<len;j++){ 
				for(int k=0;k<len;k++){ 
		        Larger[i][j]+=a[i][k]*first$[k][j];
			    }
			}	
		}
		System.out.println("larger");
		for(int i=0;i<len;i++){
			for(int j=0;j<len;j++)
				System.out.print(Larger[i][j]+"\t");
			System.out.println();
		}	
		for(int i=0;i<len;i++){                            
			for(int j=0;j<len;j++){
				if(Smaller[i][j]==1)  Matrix[i][j]='<';
				if(Larger[i][j]==1)  Matrix[i][j]='>';
				if(Equals[i][j]==1)  Matrix[i][j]='=';
			}
		}
		return Matrix;
		
	}
        
	
}