ll1.java

编译原理LL1文法的实验

/*
 * 创建日期 2005-12-18
 *
 * TODO 要更改此生成的文件的模板，请转至
 * 窗口 － 首选项 － Java － 代码样式 － 代码模板
 */

/**
 * @author 段成 软件工程0301
 * 
 * TODO 要更改此生成的类型注释的模板，请转至 窗口 － 首选项 － Java － 代码样式 － 代码模板
 */

public class LL1 {
    
	int count =0;//拆分后文法规则数
    
	char start; //文法开始符
	
    String termin = new String();//
    String nonter = new String(); 
    String v = new String();
	
    char left[] = new char[20];/*产生式左部*/
    String right[] = new String[20]; /* 产生式右部 */
	String first[] = new String[20]; /* 产生式右部的FIRST */
    String follow[] = new String[20];/*产生式左部的FOLLOW集合*/
    String first1[] = new String[20]; /*某符号的FIRST集合 */

	String select[]=new String[20]; /* 各个产生式的SELECT集合 */
    char f[] = new char[20];
    char F[] = new char[20]; /* 各符号的FIRST和FOLLOW是否已求过 */
    
    String empty = new String(); /* 可直接推出@的符号 */
	String TEMP = new String(); /* 求FOLLOW时存放某一符号串的FIRST集合 */

	boolean LL1 = true; /* 表示输入文法是否有效 */
    int ll = 1; /* 表示输入文法是否为LL(1)文法 */
    String M[][]=new String[20][20]; /* 分析表 */
  
    String empt = new String(); /* 求empty_able()时使用 */
    String followMark = new String(); /* 求FOLLOW集合时使用 */

    
  void split(String point) { /* 此方法的功能将含“|”的产生式，拆分为单个产生式 */
	    String temp = new String();
        char point1[] = point.toCharArray();
	     for (int j = 3; j < point.length(); j++) {
			if (point1[j] != '|')
				temp += point1[j];
			 
			else {
				left[count] = point1[0];
                right[count] = temp;
				temp = "";
			    count++;}
		}
		left[count] = point1[0];
		right[count] = temp;
		count++;
		}
boolean belong(char c, String p) {/*此方法功能是看字符c是否属于串p*/ 
	   int i;
    if (p.length() == 0)
			return false;
		for (i = 0;; i++) {
			if (i < p.length() && p.charAt(i) == c)
				return true; /* 若在，返回true */
			if (i == p.length())
				return false; /* 若不在，返回false */
		}
	}

void first_v(int i) { /* i为符号在输入符号v中的序号 */
		//此方法的功能求单个符号的first集，结果存在first1[i]中
	    String temp = new String();
	    int j, k, m;
        char c = v.charAt(i);
		char ch ='@';
		ToEmpty(ch);
        first1[i] = new String();
		if (belong(c, termin)) /* 终结符的情况 */
		{ 
			first1[i] +=c;
         } else if (belong(c, nonter)) /* 非终结符 */
		{
			for ( j = 0; j <= count - 1; j++) {
				if (left[j] == c) {
					if (belong(right[j].charAt(0), termin)|| right[j].charAt(0) == '@') {
						temp = "";
						temp += right[j].charAt(0);
						first1[i] = merge(first1[i], temp, 1);
					} 
					
					else if (belong(right[j].charAt(0), nonter)) {
					   if (right[j].charAt(0) == c)
							continue;
						for (k = 0;; k++)
							if (v.charAt(k) == right[j].charAt(0))
								break;
                       if (f[k] == '0') {
					    f[k] = '1';
                       	first_v(k);
		}
                      first1[i] = merge(first1[i], first1[k], 2);
						 
                      
                      for (k = 0; k < right[j].length(); k++) {
							if (empty_able(right[j].charAt(k)) == 1
		                                     && k < right[j].length() - 1) {
								for (m = 0;; m++)
									if (v.charAt(m) == right[j].charAt(k + 1))
										break;
								if (f[m] == '0') {
									f[m] = '1';
									first_v(m);
									
								}
							  first1[i] = merge(first1[i], first1[m],2);
								
							} else if (empty_able(right[j].charAt(k)) == 1
									&& k == right[j].length() - 1) {
								temp = "";
								temp += '@';
								first1[i] = merge(first1[i], temp, 1);
							} else
								break;
						}
					}
				}
			}
		}
		f[i] = '1';
	}

	/***************************************************************************
	 * 求所有能直接推出@的符号
	 **************************************************************************/
	void  ToEmpty(char c) { 
        // 结果存于字符串empty中
		String temp = new String();
		int i;
		for (i = 0; i <= count - 1; i++) {
			if (right[i].charAt(0) == c) {
				temp="";
				temp += left[i];
				empty =merge (empty, temp, 1);
				ToEmpty(left[i]);
			}
}
	}
	/***************************************************************************
	 * 求某一符号能否推出‘ @’
	 **************************************************************************/
	int empty_able(char c) { /* 若能推出，返回1；否则，返回0 */
	
	
		int i, j, k, result = 1, mark = 0;
		String temp = new String();
    	empt=merge(empt, temp, 1);
		if (belong(c,empty))
			return 1;
		for (i = 0;; i++) {
			if (i == count)
				return 0;
			if (left[i] == c) /* 找一个左部为c的产生式 */
			{
				j = right[i].length(); /* j为右部的长度 */
				if (j == 1 && belong(right[i].charAt(0),empty))
					return (1);
				else if (j == 1 && belong(right[i].charAt(0), termin))
					return 0;
				else {
					for (k = 0; k <= j - 1; k++)
						if (belong(right[i].charAt(k), empt))
							mark = 1;
					if (mark == 1)
						continue;
					else {
						for (k = 0; k <= j - 1; k++) {
							result *= empty_able(right[i].charAt(k));
							temp = "";
							temp += right[i].charAt(k);

						empt=merge(empt, temp, 1);
						}
					}
				}
				if (result == 0 && i < count)
					continue;
				else if (result == 1 && i < count)
					return 1;
			}
		}
	}	

	/***************************************************************************
	 * 求字符串的FIRST集
	 **************************************************************************/
void first_s(int i, String p) {
		int length;
		int j, k, m;
		String temp = new String();
		length = p.length();
		if (length == 1) /* 如果右部为单个符号 */
		{
			if (p.charAt(0) == '@') {
				if (i >= 0) {
					first[i]="";
					first[i] += '@';
				} else {
					TEMP = "";
					TEMP += '@';
				}
			} else {
				for (j = 0;; j++)
					if (v.charAt(j) == p.charAt(0))
						break;
				if (i >= 0) {
                    first[i]="";
					first[i]+=first1[j];
				
				
				} else {
					  TEMP = "";
					  TEMP+=first1[j];
				     
				}
			}
		} else /* 如果右部为符号串 */
		{
			for (j = 0;; j++)
				if (v.charAt(j) == p.charAt(0))
					break;
			if (i >= 0)
				{first[i]=new String();
				first[i]=merge(first[i], first1[j], 2);}
			else
				{
				TEMP=merge(TEMP, first1[j], 2);}
			for (k = 0; k <= length - 1; k++) {
				//empt='\0';
				if (empty_able(p.charAt(k)) == 1 && k < length - 1) {
					for (m = 0;; m++)
						if (v.charAt(m) == right[i].charAt(k + 1))
							break;
					if (i >= 0)
						first[i]=merge(first[i],first1[m],2);
					else
					TEMP=merge(TEMP, first1[m], 2);
				} else if (empty_able(p.charAt(k)) == 1 && k == length - 1) {
					temp="";
					temp+= '@';
					if (i >= 0)
						first[i] = merge(first[i], temp, 1);
					else
						TEMP = merge(TEMP, temp, 1);
				} else if (empty_able(p.charAt(k)) == 0) {
					break;
				}
			}
		}
	}

	void FOLLOW(int i) {
		int j, k, m, n, result = 1;
		char c;
		String temp = new String();
       	c = nonter.charAt(i); /* c为待求的非终结符 */
		temp += c;
        
		followMark = merge(followMark, temp, 1);
		follow[i]=new String();
		if (c == start) {
			temp=""; /* 若为开始符号 */
			temp+='#';
			follow[i] = merge(follow[i], temp, 1);
		}
		for (j = 0; j <= count - 1; j++) {
			if (belong(c, right[j])) /* 找一个右部含有c的产生式 */
			{   
				for (k = 0;; k++)
					if (right[j].charAt(k) == c)
					break;/* k为c在该产生式右部的序号 */
				for (m = 0;; m++)
					if (v.charAt(m) == left[j])
						break; /* m为产生式左部非终结符在所有符号中的序号 */
				if (k == right[j].length() - 1) { /* 如果c在产生式右部的最后 */
					if (belong(v.charAt(m), followMark)) {
						follow[i] = merge(follow[i], follow[m], 1);
						continue;
					}
					if (F[m] == '0') {
				        FOLLOW(m);
						F[m] = '1';
						}
					follow[i] = merge(follow[i], follow[m], 1);
				} else { /* 如果c不在产生式右部的最后 */
					for (n = k + 1; n <= right[j].length() - 1; n++) {
						result *= empty_able(right[j].charAt(n));
					}
					if (result == 1) { /* 如果右部c后面的符号串能推出@*/
						if (belong(v.charAt(m), followMark)) { /* 避免循环递归 */
							follow[i]=merge(follow[i], follow[m], 1);
							continue;
						}
						if (F[m] =='0') {
							FOLLOW(m);
							F[m] = '1';
						}
					follow[i]=merge(follow[i], follow[m], 1);
					}
					  temp = "";
					for (n = k + 1; n <= right[j].length() - 1; n++)
				    temp += right[j].charAt(n);
					first_s(-1, temp);
					follow[i] = merge(follow[i],TEMP, 2);
				}
			}
		}
		F[i] = '1';
	}

String merge(String d, String s, int type) { 
	/* 此方法的功能是将源串s与d串取并集 */
		int i, j;
		for (i = 0; i <= s.length() - 1; i++) {
			if (type == 2 && s.charAt(i) == '@') ;
			else {
				for (j = 0;; j++) {
					if (j < d.length() && s.charAt(i) == d.charAt(j))
						break;
					if (j == d.length()) {
						d += s.charAt(i);
						break;
					}
				}
			}
		}

		return d;
}

void initialize(){
	for(int i=0;i<20;i++){
    	f[i]='0';
        F[i]='0'; }

for(int i=0;i<v.length();i++){
 /*求first*/
  first_v(i);
  }
   

for(int j=0;j<=nonter.length()-1;j++)
    {                               /*求FOLLOW*/
		
  	if(! belong(nonter.charAt(j),followMark)){
         followMark="";
  		 FOLLOW(j);
  		 }
  	}
 
 for(int i=0;i<=count-1;i++)
 first_s(i,right[i]);          /*求FIRST*/
 

 
 
 
for(int i=0;i<=count-1;i++)
	{      
	int re=1;                    /*求每一产生式的SELECT集合*/
     
    select[i]="";
    select[i]=merge(select[i],first[i],2);
	
  
    
	for(int j=0;j<=right[i].length()-1;j++)
			re*=empty_able(right[i].charAt(j));

	  
	
 if(right[i].length()==1&&right[i].charAt(0)=='@')
			 re=1;
		
  if(re==1)
		{	int j;
			for(j=0;;j++)
				if(v.charAt(j)==left[i]) break;
			    select[i]=merge(select[i],follow[j],2);
    }
		

	}
    }


public String SearchTable(char a,char b){
	
	  String termin1=termin+'#';
	  int i,j;
	  int mark=1;
		for (i=0;i<nonter.length();i++)
			if (nonter.charAt(i)==a) {
			break;}
		
		for (j=0;j<termin1.length();j++)
			if (termin1.charAt(j)==b) 
		{mark=0;
		break;}
		
			if (mark==1) 
		{
			return "error";
			
		}
		return (M[i][j]);
	
	}


boolean isLL1(){
	String temp;
	temp="";
	temp=merge(temp,select[0],1);
	int length;

	for(int i=1;i<count;i++){
		length=temp.length();
		
		if(left[i]==left[i-1])
		{
			temp=merge(temp,select[i],1);
			if(temp.length()<length+select[i].length())
				return false;}
					else{
		temp="";
		temp=select[i];}
		
		}
	return true;
}

}