合肥工业大学 编译原理实验 LL(1)分析法

package translateTest; import java.awt.Font; import java.awt.GridBagConstraints; import java.awt.GridBagLayout; import java.awt.Panel; import java.awt.TextField; import java.util.Stack; public class LLcore { String showbasic = ""; public String creatVN(String []grammar) { //提取非终结符 String vn=new String(); for(int i=0;i<grammar.length;i++) { char [] midch=grammar[i].toCharArray(); //取文法中每条语句的第一个字符放入非终结符中 if(vn.indexOf(String.valueOf(midch[0]))==-1) { StringBuffer addvn=new StringBuffer(vn); //为字符串vn添加字符串缓冲区 addvn.insert(addvn.length(), midch[0]); vn=addvn.toString(); } } return vn; } public String creatVT(String[] grammar, String vn) { //提取终结符 String vt = ""; vt += "#"; for(int i=0;i<grammar.length;i++) { String simplifygrammar = grammar[i].replaceAll("->", ""); simplifygrammar = simplifygrammar.replaceAll("3", ""); char []midch = simplifygrammar.toCharArray(); for(int j =0;j<midch.length;j++) { if(vn.indexOf(String.valueOf(midch[j]))==-1&&vt.indexOf(String.valueOf(midch[j]))==-1){ StringBuffer addvn = new StringBuffer(vt); addvn.insert(addvn.length(), midch[j]); vt = addvn.toString(); } } } return vt; } public String[][] creatChart(String[] grammar,String vn, String vt){// 构造预测分析表 String [][] chart=new String[vn.length()+1][vt.length()+1]; char [] cvn=vn.toCharArray(); char [] cvt=vt.toCharArray(); for(int row=1;row<=vn.length();row++) { chart[row][0]=String.valueOf(cvn[row-1]); //表中第0列放非终结符 } for(int col=1;col<=vt.length();col++) { chart[0][col]=String.valueOf(cvt[col-1]); //表中第0行放终结符 } for(int j=1;j<=vt.length();j++) { char [] thevt=chart[0][j].toCharArray(); //看某一终结符 for(int i=1;i<=vn.length();i++) { char []thevn=chart[i][0].toCharArray(); if(first(thevn[0],vn,vt,grammar).indexOf(chart[0][j])!=-1) //若该终结符在非终结符的first集里 { int count_containvn=0; String [] containvn=new String[3]; for(int k=0;k<10;k++) //找该非终结符为某产生式左边的语句 { char [] ch=grammar[k].toCharArray(); if(ch[0]==thevn[0]) { containvn[count_containvn]=grammar[k]; //把以该非终结符为某产生式左边的语句放入一个字符串数组中 count_containvn++; } } if(count_containvn==1) //当只有一句以该非终结符为某产生式左边的语句时 { chart[i][j]=containvn[0]; } else //当不只一句以该非终结符为某产生式左边的语句时 { boolean find=false; int beginwithvn=0; int l=0; while(!find&&l<count_containvn) { char [] containvn1=containvn[l].toCharArray(); for(int n=2;n<containvn1.length;n++) { if(containvn1[n]=='>'&&containvn1[n-1]=='-') { if(containvn1[n+1]==thevt[0]) //找到以终结符为产生式右边的开始 { find=true; chart[i][j]=containvn[l]; } else { if(vn.indexOf(containvn1[n+1])!=-1) //产生式右边以非终结符开始 { beginwithvn=l; } } } } l++; } if(!find) { chart[i][j]=containvn[beginwithvn]; } } } } } for(int numvn=1;numvn<=vn.length();numvn++) { char [] thevns=chart[numvn][0].toCharArray(); if(first(thevns[0],vn,vt,grammar).indexOf(String.valueOf('3'))!=-1) //当3属于某非终结符的first集时 { for(int numvt=1;numvt<=vt.length();numvt++) { if(follow(thevns[0],vn,vt,grammar).indexOf(String.valueOf(chart[0][numvt]))!=-1) //且当某终结符属于该非终结符的follow集时 { for(int g=0;g<10;g++) { char [] chs=grammar[g].toCharArray(); if(grammar[g].indexOf(String.valueOf('3'))!=-1&&chs[0]==thevns[0]) { chart[numvn][numvt]=grammar[g]; // break; } } } } } } return chart; } public int addchar(char []a, char[]b) { //求两集合的交集 int lengtha = 0; int lengthb = 0; int position = 0; for(lengtha=0; lengtha<= a.length;lengtha++) { if(a[lengtha]=='\0') { break; } } for(lengthb=0;lengthb<=b.length;lengthb++) { if(b[lengthb]=='\0') { break; } } boolean in = false; for(int i=0;i<lengthb;i++) { in = false; for(int j= 0;j<lengtha;j++) { if(a[j]==b[i]) { in = true; break; } } if(!in) { a[lengtha+position] = b[i]; position++; } } return position; } public String follow(char thevn, String vn, String vt, String[] grammar) { char []midfollow = new char[grammar.length]; char []result = new char[grammar.length]; result[0] = '#'; int counter = 1; for(int i= 0;i<grammar.length;i++) { int begin = grammar[i].indexOf("->"); //找到产生式右部的开始部分 int foundvn = grammar[i].indexOf(String.valueOf(thevn), begin); if(foundvn!=-1) { //在产生式右部找到此非终结符 midfollow = grammar[i].toCharArray(); if(foundvn+1<midfollow.length&&vn.indexOf(String.valueOf(midfollow[foundvn+1]))==-1) {//该非终结符后接终结符 result[counter] = midfollow[foundvn+1]; //终结符直接加入 counter++; } if(grammar[i].endsWith(String.valueOf(thevn))) { //A->..B 后接空 if(midfollow[0]!=thevn) { String add = follow(midfollow[0], vn, vt, grammar); addchar(result, add.toCharArray()); //把follow(A)加入follow(B) } } //A->..B.. 后接非终结符 if(midfollow[midfollow.length-2]==thevn&&vn.indexOf(String.valueOf(midfollow[midfollow.length-1]))!=-1) { String add = first(midfollow[midfollow.length-1], vn,vt,grammar);//求后接非终结符的first集 char []addc = add.trim().toCharArray(); for(int j=0;j<addc.length;j++) { //将first集-'3' 加入当前follow中 if(addc[j]!='3') { if(String.valueOf(result).indexOf(String.valueOf(addc[j]))==-1) { result[counter] = addc[j]; counter++; } } } for(int n=0;n<grammar.length;n++) { //若有A->..B..且B后接的非终结符first集含有'3'，将follow(a)加入 if(grammar[n].startsWith(String.valueOf(midfollow[midfollow.length-1]))&&grammar[n].indexOf("->3")!=-1) { //A-CBD,且D->3 add = follow(midfollow[0],vn,vt,grammar); counter += addchar(result, add.toCharArray()); //将follow(A)加入follow(B) } } } } } //System.out.println(String.valueOf(result)+"2"); return String.valueOf(result); } public String first(char thevn, String vn, String vt, String[] grammar) {//求first集 int counter = 0; char []midfirst = new char[grammar.length]; char []result = new char[grammar.length]; if(vt.indexOf(thevn)!=-1) { //若为终结符 return String.valueOf(thevn); } else { //若为非终结符 for(int i = 0;i<grammar.length;i++) { midfirst = grammar[i].toCharArray(); if(thevn == midfirst[0]) { //找到该非终结符的文法 int d = 1; if(midfirst[d]=='-'&&midfirst[d+1]=='>') { if(vn.indexOf(midfirst[d+2])!=-1) { //第一个字符为非终结符 String mids = first(midfirst[d+2],vn,vt,grammar); counter += addchar(result,mids.toCharArray()); int index = 4; while(mids.indexOf('3')!=-1&&midfirst[index]!='\0') {//若含有空串，将后续的非终结符的first集加入 mids = first(midfirst[index],vn,vt,grammar); counter += addchar(result,mids.toCharArray()); index++; } } else{ //第一个字符为空串或者终结符 result[counter] = midfirst[d+2]; counter++; continue; } } } } //System.out.println(String.