///**共有三個類，主類為LL.java,讀取TXT檔案中的文法 類ReadInfo.java, 擷取First集,Follow集，Select集，ll分析表，語句分析的類GetFFS.java讀取的文法必須是A->qB|cT而不是A->qB和A->cT這種形式
//第一個ll.java*************************LL.java********************************************/
* author:Ack訾
* Date：3/11/2012
* Attention:Please Input a Grammer that doesn't contain recursion,otherwise it will be endless loop;
* (ha ha!I don't how to solve this question)
*/
package com.algorithm;
import java.awt.BorderLayout;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.JTextField;
public class LL extends JFrame implements ActionListener{
/**
*
*/
private static final long serialVersionUID = 1L;
JFrame jf=new JFrame();
JPanel displayPanel,controlPanel,resultPanel;
JTextField filePath;
JTextField sentence;
JTextArea jta2;
int height =Toolkit.getDefaultToolkit().getScreenSize().height;
int width=Toolkit.getDefaultToolkit().getScreenSize().width;
LL(){
jf.setSize(700,500);
jf.setLocation((width-700)/2,(height-500)/2);
JPanel displayPanel=new JPanel();
JPanel controlPanel=new JPanel();
JPanel resultPanel=new JPanel();
JButton analyze_Gramar =new JButton("分析此文法");
analyze_Gramar .addActionListener(this);
JButton save=new JButton("儲存");
save.addActionListener(this);
JLabel tip=new JLabel("請輸入可用檔案路徑：");
JLabel sentence_Label=new JLabel("請輸入語句：");
JButton analyze_Sentence =new JButton("分析語句");
analyze_Sentence.addActionListener(this);
//1
filePath=new JTextField(20);
filePath.addActionListener(this);
jta2=new JTextArea(20,62);
JScrollPane jsp =new JScrollPane(jta2);
//2
sentence=new JTextField(20);
sentence.addActionListener(this);
resultPanel.add(jsp);
controlPanel.add(tip);
controlPanel.add(filePath);
controlPanel.add(analyze_Gramar);
controlPanel.add(save);
displayPanel.add(sentence_Label);
displayPanel.add(sentence);
displayPanel.add(analyze_Sentence);
jf.add(displayPanel,BorderLayout.CENTER);
jf.add(controlPanel, BorderLayout.NORTH);
jf.add(resultPanel,BorderLayout.SOUTH);
jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
jf.setResizable(false);
jf.setVisible(true);
}
public static void main(String[] args) {
new LL();
}
public void actionPerformed(ActionEvent e) {
if(e.getActionCommand()=="分析此文法"){
String f=filePath.getText();
ReadInfo ri=new ReadInfo();
String[][] ll = null;
try {
ll = ri.gettext(f);
} catch (IOException e1) {
e1.printStackTrace();
}
GetFFS g=new GetFFS(ll);
//①讀取的文法放在ll[][]二維數組中，可根據下面的注釋語句進行列印
jta2.append("文法G"+"["+ll[0][0]+"]"+":"); jta2.append("\n");
for(int i=0;i<ll[0].length;i++){
jta2.append(ll[0][i]);
jta2.append("->");
jta2.append(ll[1][i]);
jta2.append("\n");
}
jta2.append("\n");
//②終結符放在NT[]中（not terminate）可通過下面注釋語句進行列印
String[]NT = g.getNT();
jta2.append(" 非終結符集：");jta2.append("{");
for(int i=0;i<NT.length;i++){
if(NT.length-1==i)
jta2.append(NT[i]);
else
jta2.append(NT[i]+",");
}
jta2.append("}");jta2.append("\n");
//③終結符放在T[]中（teminate） 可通過下面注釋語句進行列印
String[]T = g.getT();
jta2.append(" 終結符集：");jta2.append("{");
for(int i=0;i<T.length;i++){
if(T.length-1 ==i)
jta2.append(T[i]);
else
jta2.append(T[i]+",");
}
jta2.append("}");
jta2.append("\n");
//④注意文法的First集放在First[][]二維數組中 可通過下面注釋語句進行列印
jta2.append("\n");
String[][] First=g.getFirst();
jta2.append("FIRST集："); jta2.append("\n");
for(int i=0;i<First[0].length;i++){
jta2.append("First"+"("+First[0][i]+")"+"=");
jta2.append("{");
char[] ch=First[1][i].toCharArray();
for(int j=0;j<ch.length;j++){
if(ch.length-1 ==j)
jta2.append(String.valueOf(ch[j]));
else jta2.append(ch[j]+",");
}
jta2.append("}");
jta2.append("\n");
//jta2.appendln("{"+First[1][i]+"}");
}
jta2.append("\n");
//⑤Follow集
String[][] Follow=null;
try{ Follow=g.getFollow();}catch (Exception es) {
jta2.append("此文法存在遞歸！");
}
jta2.append("FOLLOw集："); jta2.append("\n");
for(int i=0;i<Follow[0].length;i++){
jta2.append("Follow"+"("+Follow[0][i]+")"+"=");
jta2.append("{");
char[] ch=Follow[1][i].toCharArray();
for(int j=0;j<ch.length;j++){
if(ch.length-1 ==j)
jta2.append(String.valueOf(ch[j]));
else jta2.append(ch[j]+",");
}
jta2.append("}"); jta2.append("\n");
//jta2.appendln(First[1][i]);
}
//⑥求select集
jta2.append("\n");
String[][] Select=g.getSelect();
String[][] Selectbefore=g.getSelectbefore();
jta2.append("Select集：");
jta2.append("\n");
for(int i=0;i<Select[0].length;i++){
jta2.append("Select"+"("+ Select[0][i]+"->"+Selectbefore[1][i]+")"+"=");
jta2.append("{");
char[] ch=Select[1][i].toCharArray();
for(int j=0;j<ch.length;j++){
if(ch.length-1 ==j)
jta2.append(String.valueOf(ch[j]));
else jta2.append(ch[j]+",");
}
jta2.append("}");jta2.append("\n");
}
jta2.append("\n");
// jta2.appendln(Select[1][1]);
//将select的結果存在Analyze[3][Select[0].lenth]
String[][] Analyze=new String[3][Select[0].length];
//jta2.appendln(Analyze[1].length);
for(int i=0;i<Analyze[0].length;i++){
Analyze[0][i]=Select[0][i];
Analyze[1][i]=Selectbefore[1][i];
Analyze[2][i]=Select[1][i];
}
jta2.append("\n");
boolean isLL1=true;
for(int i=0;i<Analyze[0].length-1;i++){
if(Analyze[0][i].equals(Analyze[0][i+1])){
char []ch=Analyze[2][i].toCharArray();
for(int j=0;j<ch.length;j++){
if(Analyze[2][i+1].contains(String.valueOf(ch[j]))){
jta2.append("∵");
jta2.append("Select"+"("+Analyze[0][i]+"->"+Analyze[1][i]+")"+"∩"
+"Select"+"("+Analyze[0][i]+"->"+Analyze[1][i+1]+")"+"≠"+"¤");
jta2.append("∴");
isLL1=false;
}
}
}
}
//判斷是否是LL(1)文法
if(isLL1==false){
jta2.append("\n");
jta2.append("文法G"+"["+ll[0][0]+"]"+":"+"不是LL(1)文法！");}
//求select集合得出的終結符号
ArrayList<String> T_list=new ArrayList<String>();
for(int i=0;i<Analyze[0].length;i++){
char[] ch=Analyze[2][i].toCharArray();
for(int j=0;j<ch.length;j++){
String temp=String.valueOf(ch[j]);
if(!T_list.contains(temp))
T_list.add(temp);
}
}
//求select集合得出的終結符号,放在select_T[]中
String[] select_T=new String[T_list.size()];
for(int i=0;i<T_list.size();i++){
select_T[i]=String.valueOf(T_list.get(i));
//jta2.appendln(select_T[i]);
}
jta2.append("\n");jta2.append("\n");
//⑦求分析表it
if(isLL1==true){
jta2.append("文法G"+"["+ll[0][0]+"]"+":"+"是LL(1)文法！");
jta2.append("\n");
jta2.append("LL(1)分析表:"); jta2.append("\n");
jta2.append("-----------------------------------------------------------" +
"-----------------------------------------------------------------------------------------------------------");
jta2.append("\n");
jta2.append("\t\t"+" "+" ");
for(int i=0;i<select_T.length;i++){
jta2.append(select_T[i]+"\t");
jta2.append(" "+" ");
//jta2.append("\n");
}
jta2.append("\t ");
jta2.append("\n");
jta2.append("-----------------------------------------------------------" +
"-----------------------------------------------------------------------------------------------------------");
// jta2.append("\n");
for(int i=0;i<NT.length;i++){
jta2.append("\n");
jta2.append("\t ");
jta2.append(NT[i]);
for(int j=0;j<select_T.length;j++){
boolean isE=false;
for(int k=0;k<Analyze[1].length;k++){
if(Analyze[2][k].contains(select_T[j])&&Analyze[0][k].equals(NT[i])){
isE=true;
jta2.append("\t ");
jta2.append("->"+Analyze[1][k]);//+"("+select_T[j]+")");
}
}
if(isE==false){jta2.append(" \t ");}
}
jta2.append("\n");
jta2.append("-----------------------------------------------------------" +
"-----------------------------------------------------------------------------------------------------------");
}
}
jta2.append("\n");
}
jta2.append("\n");
if(e.getActionCommand()=="分析語句"){
ReadInfo ri=new ReadInfo();
String[][] ll=null;
try {
ll = ri.gettext(filePath.getText());
} catch (IOException e1) {
e1.printStackTrace();
}
GetFFS g=new GetFFS(ll);
String[][] Select=g.getSelect();
String[][] Selectbefore=g.getSelectbefore();
String[][] Analyze=new String[3][Select[0].length];
//System.out.println(Analyze[1].length);
for(int i=0;i<Analyze[0].length;i++){
Analyze[0][i]=Select[0][i];
Analyze[1][i]=Selectbefore[1][i];
Analyze[2][i]=Select[1][i];
//System.out.println(Analyze[2][i]);
}
ArrayList<String> T_list=new ArrayList<String>();
for(int i=0;i<Analyze[0].length;i++){
char[] ch=Analyze[2][i].toCharArray();
for(int j=0;j<ch.length;j++){
String temp=String.valueOf(ch[j]);
if(!T_list.contains(temp))
T_list.add(temp);
}
}
String string=sentence.getText();
jta2.append("輸入的句子是：");
jta2.append(string);
jta2.append("\n");
char[] ch=string.toCharArray();
//s用于存放讀入的語句
ArrayList<String> s=new ArrayList<String>();
//stack用于存放分析棧
ArrayList<String> stack=new ArrayList<String>();
stack.add("#");
for(int i=0;i<ch.length;i++){
s.add(String.valueOf(ch[i]));
}
stack.add(Analyze[0][0]);
ArrayList<String> sentence_result=new ArrayList<String>();
for(int i=0;i<ch.length;i++){
// do{
String s_result=new String();
s_result=s_result.concat(stack+"\t"+s+"\t");
//int i=0;
// jta2.append("("+z+")");jta2.append("\t");jta2.append(String.valueOf(stack));jta2.append("\t");jta2.append(String.valueOf(s));jta2.append("\t");
for(int j=0;j<Analyze[0].length;j++){
if((!string.contains(String.valueOf(stack.get(stack.size()-1))))&&Analyze[0][j].equals(stack.get(stack.size()-1))&&Analyze[2][j].contains(String.valueOf(s.get(0))))
{
//jta2.append(Analyze[0][j]+"->"+Analyze[1][j]);jta2.append("\t");jta2.append("\n");
s_result=s_result.concat(Analyze[0][j]+"->"+Analyze[1][j]);
sentence_result.add(s_result);
s_result="";
stack.remove(Analyze[0][j]);
StringBuffer sb=new StringBuffer(Analyze[1][j]);
String st=(sb.reverse()).toString();
char[] tempchar=st.toCharArray();
for(int k=0;k<st.length();k++){
if(tempchar[k]!='ε')
stack.add(String.valueOf(tempchar[k]));
}
s_result=s_result.concat(stack+"\t"+s+"\t");
}
}
// System.out.print(1);System.out.print("\t");System.out.print(stack);System.out.print("\t");System.out.print(s);System.out.print("\t");
if(s.get(0).equals(stack.get(stack.size()-1))){
if(stack.get(stack.size()-1)!="#"){
// jta2.append(s.get(0)+"比對"); jta2.append("\t");jta2.append("\n");
s_result=s_result.concat(s.get(0)+"比對");
sentence_result.add(s_result);
}
else{ //jta2.append("Accept");
sentence_result.add(s_result+"Accept!");}
}
else{
// sentence_result.add("Failed!");
//jta2.append("\n");
//jta2.append(string+"\t"+"不是"+"文法G"+"["+ll[0][0]+"]"+"的句子");jta2.append("\n");
sentence_result.add(s_result+"Failed!");
//s_result="";
s_result=string+"不是"+"文法G"+"["+ll[0][0]+"]"+"的句子";
sentence_result.add(s_result);
break;}
s.remove(s.get(0));
stack.remove(stack.get(stack.size()-1));
}
for(int i=0;i<sentence_result.size();i++){
jta2.append("("+(i+1)+")");
jta2.append("\t");
jta2.append((String) sentence_result.get(i));jta2.append("\n");
}
}
if(e.getActionCommand()=="儲存"){
String Stext=jta2.getText();
File file =new File("G:\\大三實驗課\\編譯原理\\實驗2\\result.txt");
file.delete();
try {
PrintWriter out
= new PrintWriter(new BufferedWriter(new FileWriter("G:\\大三實驗課\\編譯原理\\實驗2\\result.txt")));
out.write(Stext);
out.flush();
out.close();
} catch (IOException e1) {
e1.printStackTrace();
}
}
}
}
//***************************************第二個GetFFS.java類
package com.algorithm;
import java.util.ArrayList;
//求first，follow，sellect
class GetFFS{
public String [][]str;
static String Tstring="";
static String TstringFollow="";
static String Tstringselect="";
GetFFS(String[][] ll){
str=ll;
}
//擷取非終結符放到NT數組中
String[] getNT(){
//String [][] Follow=getFollow();
String[] NT=new String[str[0].length];
for(int i=0;i<str[0].length;i++){
NT[i]=str[0][i];
}
return NT;
}
//擷取終結符 放到T數組中
String[] getT(){
String[] NT1 = getNT();
String temp=new String();
for(int i=0;i<str[1].length;i++){
temp=temp+str[1][i];
}
for(int i=0;i<NT1.length;i++){
temp=temp.replaceAll(NT1[i],"");
}
temp=temp.replaceAll("\\|","");
temp=temp.replaceAll("\\'","");
//System.out.println(temp);
char[] ch=new char[temp.length()];
ch=temp.toCharArray();
String resultString = new String();
for(int i=0;i<ch.length;i++){
if(!resultString.contains(String.valueOf(ch[i])))
resultString=resultString.concat(String.valueOf(ch[i]));
}
//System.out.println(resultString);
String[] T=new String[resultString.length()];
for(int i=0;i<resultString.length();i++){
T[i]=(String)String.valueOf(resultString.charAt(i));
//System.out.println(T[i]);
}
return T;
}
//求first這裡我們隻考慮非終結符為大寫字母的情況
String[][] getFirst(){
String[][] First = new String[2][str[0].length];
for(int i=0;i<str[0].length;i++){
First[0][i]=str[0][i];
try{
getF(str[0][i],str[1][i]);}
catch (Exception e) {
System.out.print("捕獲異常：文法不是ll1文法！或其他問題:存在遞歸");
}
First[1][i]=Tstring;
Tstring="";
}
return First;
}
//遞歸算法求first
String getF(String str1,String str2){
String temp="";
//for(int i=0;i<str[0].length;i++){System.out.print(str[0][i]);}
if(str2.contains("|")){
String[] strtemp;
strtemp=str2.split("\\|");
for(int i=0;i<strtemp.length;i++){
getF(str1,strtemp[i]);
}
}
else{
if('A'<=str2.charAt(0)&&str2.charAt(0)<='Z'){
for(int i=0;i<str[0].length;i++){
//System.out.print(str[0][i]);
if(str[0][i].equals(String.valueOf(str2.charAt(0)))){
if(!str1.equals(String.valueOf(str2.charAt(0))))
getF(str[0][i],str[1][i]);
}
}
}
else{
temp=String.valueOf(str2.charAt(0));
if(!Tstring.contains(temp))
Tstring=Tstring.concat(String.valueOf(str2.charAt(0)));
}
}
return temp;
}
//求follow集
String[][] getFollow(){
String[][] Follow= new String[2][str[0].length];
//public String [][]str;
String temp;
for(int i=0;i<str[0].length;i++){
Follow[0][i]=str[0][i];
getFo(str[0][i]);
//getFo(str[0][0])="#";
Follow[1][i]=TstringFollow;
TstringFollow="";
}
for(int i=0;i<Follow[0].length;i++){
StringBuffer sb=new StringBuffer(Follow[1][i]);
for(int j=0;j<sb.length();j++){
if(sb.charAt(j)=='ε'||sb.charAt(j)=='\''){
sb.deleteCharAt(j);
temp=sb.toString();
Follow[1][i]=temp;
}
}
}
return Follow;
}
//遞歸求follow
String getFo(String str3){
//public String [][]str;
String [][] First=getFirst();
String temp="";
//假如受str1存在str[][]中的str[1][i]中，
//若存在則判斷是否有str[1][i]中的str1是否有字尾,
//①若不存在則follow(str1)則尋找str[1][i]所對應的str[0][i]
//②存在則follow(str1)=first(str1)
if(str3.equals(str[0][0])){
if(!TstringFollow.contains("#"))
TstringFollow=TstringFollow.concat("#");}
for(int i=0;i<str[0].length;i++){
if(str[1][i].contains(str3)){
char[]ch=str[1][i].toCharArray();
for(int j=0;j<ch.length;j++){
if(str3.equals(String.valueOf(ch[j]))){
//j+1沒有超出ch.length的時候
//字尾為|時if(j+1==ch.length||ch[j+1]=='|')
if(j+1<ch.length){
//字尾為非終結符ch[j+1]=='|'||j+1==ch.length
if('A'<=ch[j+1]&&ch[j+1]<='Z'){
//求first(ch[j+1])
for(int k=0;k<First[0].length;k++){
//for(int l=0;l<Follow[0].)
// if(){}
if(First[0][k].equals(String.valueOf(ch[j+1]))){
String temp1=String.valueOf((First[1][k]));
if(!TstringFollow.contains(temp1))
TstringFollow=TstringFollow.concat(First[1][k]);
}
}
}
//字尾為終結符号時加入follow（str1）
else if(ch[j+1]=='|'){
if(!str[0][i].equals(String.valueOf(ch[j])))
getFo(String.valueOf(str[0][i]));
}
else{
String temp2=String.valueOf((ch[j+1]));
if(!TstringFollow.contains(temp2))
TstringFollow=TstringFollow.concat(String.valueOf((ch[j+1])));}
}
else{
//求follow(str[0][i])
if(!str[0][i].equals(String.valueOf(ch[j])))
getFo(String.valueOf(str[0][i]));
}
}
//j+1 超過ch.length時候
/*else{
//求follow(str[0][i])
getFo(String.valueOf(str[0][i]));
}*/
}
}
}
/*else{
//System.out.print("哎！大哥！又出錯了！");
}*/
return temp;
}
//求select集合
String[][] getSelect(){
String [][] First=getFirst();
String [][] Follow=getFollow();
ArrayList<String> selectNT=new ArrayList<String>();
ArrayList<String> selectRight=new ArrayList<String>();
//public String [][]str;
//System.out.println(n);
String[] s;
for(int i=0;i<str[0].length;i++){
if(str[1][i].contains("|")){
s=str[1][i].split("\\|");
//selectNT.add(str[0][i]);
//selectNT.add(str[0][i]);
for(int j=0;j<s.length;j++)
{selectRight.add(s[j]);
selectNT.add(str[0][i]);}
}
else{
selectNT.add(str[0][i]);
selectRight.add(str[1][i]);
}
}
String[][] selectbefore= new String[2][selectNT.size()];
String[][] select= new String[2][selectNT.size()];
for(int i=0;i<selectNT.size();i++){
selectbefore[0][i]=(String) selectNT.get(i);
selectbefore[1][i]=(String) selectRight.get(i);
select[0][i]=(String) selectNT.get(i);
//System.out.println(selectbefore[0][i]);
}
for(int z=0;z<selectbefore[0].length;z++){
if(selectbefore[1][z].charAt(0)=='ε'){
String temp=selectbefore[0][z];
for(int e=0;e<Follow[0].length;e++){
if(Follow[0][e].equals(temp))select[1][z]=Follow[1][e];
}
}
else if(!('A'<=selectbefore[1][z].charAt(0)&&selectbefore[1][z].charAt(0)<='Z')){
select[1][z]=String.valueOf(selectbefore[1][z].charAt(0));
}
else{
String temp=String.valueOf(selectbefore[1][z].charAt(0));
for(int e=0;e<First[0].length;e++){
if(Follow[0][e].equals(temp))select[1][z]=First[1][e];
}
}
}
return select;
}
//此方法是求Selectbefore[][]用來存不含“|”的文法
String[][] getSelectbefore(){
ArrayList<String> selectNT=new ArrayList<String>();
ArrayList<String> selectRight=new ArrayList<String>();
//public String [][]str;
//System.out.println(n);
String[] s;
for(int i=0;i<str[0].length;i++){
if(str[1][i].contains("|")){
s=str[1][i].split("\\|");
//selectNT.add(str[0][i]);
for(int j=0;j<s.length;j++)
{selectRight.add(s[j]);
selectNT.add(str[0][i]);}
}
else{
selectNT.add(str[0][i]);
selectRight.add(str[1][i]);
}
}
String[][] selectbefore= new String[2][selectNT.size()];
String[][] select= new String[2][selectNT.size()];
for(int i=0;i<selectNT.size();i++){
selectbefore[0][i]=(String) selectNT.get(i);
selectbefore[1][i]=(String) selectRight.get(i);
select[0][i]=(String) selectNT.get(i);
//System.out.println(selectbefore[1][i]);
}
return selectbefore;}}
package com.algorithm;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
class ReadInfo{
//讀取input.txt檔案中的内容
String[][] gettext(String str) throws IOException{
FileReader fr=new FileReader(str);
BufferedReader br=new BufferedReader(fr);
String temp;
ArrayList<String> list =new ArrayList<String>();
while((temp=br.readLine())!=null){
list.add(temp);
}
br.close();
String arr[]=new String[list.size()];
String arrNT[]=new String[list.size()];//非終結符數組
String arrT[]=new String[list.size()];//終結符号數組
for(int i=0;i<list.size();i++){
arr[i]=(String) list.get(i);
//System.out.println(arr[i]);
}
for(int i=0;i<arr.length;i++){
String[] temp1;
temp1=arr[i].split("->");
arrNT[i]=temp1[0];
arrT[i]=temp1[1];
}
String[][] ll=new String[2][list.size()];
for(int i=0;i<list.size();i++){
ll[0][i]=arrNT[i];
ll[1][i]=arrT[i];
}
return ll;
}
}
![Remove Duplicates系列筆記[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)