LL1分析在编译原理实验中是如何实现的？

本文共计5522个文字，预计阅读时间需要23分钟。

java/** * 简化实验三的内容： * * class LL1analysis extends JFrame implements ActionListener { * JLabel labelGrammarInput; * JButton buttonOpenFile; * JButton buttonCertainGrammar; * JButton buttonSaveFile; * JLabel labelWarning1; * JLabel labelWarning; * } */

// 下面是实验三的内容 ： class LL1analysis extends JFrame implements ActionListener{ JLabel labelGrammarInput ; JButton buttonOpenFile; JButton buttonCertainGrammar; JButton buttonSaveFile; JLabel labelWarning1; JLabel labelWarning2; JLabel labelWarning3; JTextArea textAreaGrammar; JButton buttonGenerateFirstSet; JButton buttonGenerateFollowSet; JLabel labelFirstSet; JLabel labelFollowSet; JTable textAreaFirstSet; JTable textAreaFollowSet; JLabel labelForecastAnalysisTable; JButton buttonGenerateForecastAnalysis; JTable textAreaForecastAnalysisTable; JLabel labelAnalysisSentence; JLabel labelWaitAnalosisSentence; JTextField textFieldWaitAnalysisSentence; JButton buttonAnalysis , buttonSingleStepShow , buttonOneChickDisplay; JLabel labelAnalysisResult ; JTextArea textAreaAnalysisResult; // 用于 实现功能的变量 grammar currentGrammar ; boolean certainGrammar = false; boolean readyAnalysis = false; // 为句型 分析添加 Stack<Character> analStack = new Stack<>(); char[] sequence; int analIndex; boolean isEnd = false; String law = "*()+"; LL1analysis(){ init(); } void init(){ labelGrammarInput = new JLabel("文法输入"); buttonOpenFile = new JButton("打开文件"); buttonOpenFile.addActionListener(this::actionPerformed); buttonSaveFile = new JButton("保存文法"); buttonSaveFile.addActionListener(this::actionPerformed); buttonCertainGrammar = new JButton("确认文法"); buttonCertainGrammar.addActionListener(this::actionPerformed); labelWarning1 = new JLabel("注意事项:请输入满足L(1)最简判别的2型文法。-行一个产生式"); labelWarning2 = new JLabel("注意事项:请输入形式如S->A的产生式，空格用_表示，空用#表示"); labelWarning3 = new JLabel("注意事项:开始符为第一个产生式的左部，非终结符用大写字母表示"); textAreaGrammar = new JTextArea(15,10); buttonGenerateFirstSet = new JButton("生成First集"); buttonGenerateFirstSet.addActionListener(this::actionPerformed); buttonGenerateFollowSet = new JButton("生成Fllow集"); buttonGenerateFollowSet.addActionListener(this::actionPerformed); labelFirstSet = new JLabel("First集"); textAreaFirstSet = new JTable(null); labelFollowSet = new JLabel("Follow集"); textAreaFollowSet = new JTable(null); labelForecastAnalysisTable = new JLabel("预测分析表"); buttonGenerateForecastAnalysis = new JButton("构造预测分析"); buttonGenerateForecastAnalysis.addActionListener(this::actionPerformed); textAreaForecastAnalysisTable = new JTable(null); labelAnalysisSentence = new JLabel("分析句子"); labelWaitAnalosisSentence = new JLabel("待分析句子"); textFieldWaitAnalysisSentence = new JTextField(15); buttonAnalysis = new JButton("分析"); buttonAnalysis.addActionListener(this::actionPerformed); buttonSingleStepShow = new JButton("单步显示"); buttonSingleStepShow.addActionListener(this::actionPerformed); buttonOneChickDisplay = new JButton("一键显示"); buttonOneChickDisplay.addActionListener(this::actionPerformed); labelAnalysisResult = new JLabel("分析结果"); textAreaAnalysisResult = new JTextArea(20,15); /* 整体 为一个一行两列的结构 第一列： 为一个两行一列的结构 第一行： 为一个五个方向的结构： 上方： 为一个五行一列的结构 第二行用一个一行三列的结构包括三个按钮 其余都只有一个标签 center 为一个textarea ；south 为一个一行两列的结构 包含两个按钮 第二行： 为一个四行一列的结构： 分别是两个标签和两个area */ setLayout(new GridLayout(1,2)); JPanel panel1 = new JPanel(); panel1.setLayout(new GridLayout(2,1)); JPanel panel1_1 = new JPanel(); panel1_1.setLayout(new BorderLayout()); JPanel panel1_1_1 = new JPanel(); panel1_1_1.setLayout(new GridLayout(5,1)); JPanel panel1_1_1_1 = new JPanel(); panel1_1_1_1.setLayout(new GridLayout(1,3)); panel1_1_1_1.add(buttonOpenFile); panel1_1_1_1.add(buttonCertainGrammar); panel1_1_1_1.add(buttonSaveFile); panel1_1_1.add(labelGrammarInput); panel1_1_1.add(panel1_1_1_1); panel1_1_1.add(labelWarning1); panel1_1_1.add(labelWarning2); panel1_1_1.add(labelWarning3); panel1_1.add(panel1_1_1 , BorderLayout.NORTH); /* JScrollPane scroller = new JScrollPane(textAreaSourcePrograme); scroller.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS); panel1.add(scroller, BorderLayout.CENTER);//向窗口添加文本编辑区 textAreaSourcePrograme.setWrapStyleWord(true);//设置单词在一行不足容纳时换行 textAreaSourcePrograme.setLineWrap(true);//设置文本编辑区自动换行默认为true,即会"自动换行" */ JScrollPane scrollPane1 = new JScrollPane(textAreaGrammar); scrollPane1.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS); panel1.add(scrollPane1, BorderLayout.CENTER);//向窗口添加文本编辑区 textAreaGrammar.setWrapStyleWord(true);//设置单词在一行不足容纳时换行 textAreaGrammar.setLineWrap(true);//设置文本编辑区自动换行默认为true,即会"自动换行" panel1_1.add(scrollPane1,BorderLayout.CENTER); JPanel panel1_1_2 = new JPanel(); panel1_1_2.setLayout(new GridLayout(1,2)); panel1_1_2.add(buttonGenerateFirstSet); panel1_1_2.add(buttonGenerateFollowSet); panel1_1.add(panel1_1_2 , BorderLayout.SOUTH); JPanel panel1_2 = new JPanel(); panel1_2.setLayout(new GridLayout(2,1)); JPanel panel1_2_1 = new JPanel(); panel1_2_1.setLayout(new BorderLayout()); panel1_2_1.add(labelFirstSet ,BorderLayout.NORTH ); JScrollPane scrollPane3 = new JScrollPane(textAreaFirstSet); scrollPane3.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS); panel1.add(scrollPane3, BorderLayout.CENTER);//向窗口添加文本编辑区 // textAreaFirstSet.setWrapStyleWord(true);//设置单词在一行不足容纳时换行 // textAreaFirstSet.setLineWrap(true);//设置文本编辑区自动换行默认为true,即会"自动换行" panel1_2_1.add(scrollPane3 , BorderLayout.CENTER); JPanel panel1_2_2 = new JPanel(); panel1_2_2.setLayout(new BorderLayout()); panel1_2_2.add(labelFollowSet ,BorderLayout.NORTH ); JScrollPane scrollPane2 = new JScrollPane(textAreaFollowSet); scrollPane2.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS); panel1.add(scrollPane2, BorderLayout.CENTER);//向窗口添加文本编辑区 // textAreaFollowSet.setWrapStyleWord(true);//设置单词在一行不足容纳时换行 // textAreaFollowSet.setLineWrap(true);//设置文本编辑区自动换行默认为true,即会"自动换行" panel1_2_2.add(scrollPane2 , BorderLayout.CENTER); panel1_2.add(panel1_2_1); panel1_2.add(panel1_2_2); panel1.add(panel1_1); panel1.add(panel1_2); this.add(panel1); /* 第二列： 为一个五个方向的结构： 上方： 用三行一列的 包含 标签 按钮 area 中间 用一个五个方向的结构 上： 一个标签 中： 两行一列 标签 fild 下： 三行一列 三个按钮 下方： 两行一列： 标签 area */ JPanel panel2 = new JPanel(); panel2.setLayout(new GridLayout(2,1)); JPanel panel2_1 = new JPanel(); panel2_1.setLayout(new BorderLayout()); JPanel panel2_1_1 = new JPanel(); panel2_1_1.setLayout(new GridLayout(1,2)); panel2_1_1.add(labelForecastAnalysisTable); panel2_1_1.add(buttonGenerateForecastAnalysis); panel2_1.add(panel2_1_1 , BorderLayout.NORTH ); JScrollPane scrollPane4 = new JScrollPane(textAreaForecastAnalysisTable); scrollPane4.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS); panel1.add(scrollPane4, BorderLayout.CENTER);//向窗口添加文本编辑区 // textAreaForecastAnalysisTable.setWrapStyleWord(true);//设置单词在一行不足容纳时换行 // textAreaForecastAnalysisTable.setLineWrap(true);//设置文本编辑区自动换行默认为true,即会"自动换行" panel2_1.add(scrollPane4 , BorderLayout.CENTER); panel2_1.add(labelAnalysisSentence , BorderLayout.SOUTH); JPanel panel2_2 = new JPanel(); panel2_2.setLayout(new BorderLayout()); // JPanel panel2_2_1 = new JPanel(); // panel2_2_1.setLayout(new GridLayout(2,1)); // panel2_2_1.add(labelAnalysisSentence ); JPanel panel2_2_2 = new JPanel(); panel2_2_2.setLayout(new BorderLayout()); panel2_2_2.add(labelWaitAnalosisSentence ,BorderLayout.WEST); panel2_2_2.add(textFieldWaitAnalysisSentence , BorderLayout.CENTER); JPanel panel2_2_3 = new JPanel(); panel2_2_3.setLayout(new GridLayout(1,3)); panel2_2_3.add(buttonAnalysis); panel2_2_3.add(buttonSingleStepShow); panel2_2_3.add(buttonOneChickDisplay); // panel2_2.add(panel2_2_1 , BorderLayout.NORTH); panel2_2.add(panel2_2_2 , BorderLayout.CENTER); panel2_2.add(panel2_2_3 , BorderLayout.SOUTH); JPanel panel2_3 = new JPanel(); panel2_3.setLayout(new BorderLayout()); panel2_3.add(labelAnalysisResult , BorderLayout.NORTH); JScrollPane scrollPane5 = new JScrollPane(textAreaAnalysisResult); scrollPane5.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS); panel1.add(scrollPane5, BorderLayout.CENTER);//向窗口添加文本编辑区 textAreaAnalysisResult.setWrapStyleWord(true);//设置单词在一行不足容纳时换行 textAreaAnalysisResult.setLineWrap(true);//设置文本编辑区自动换行默认为true,即会"自动换行" panel2_3.add(scrollPane5 , BorderLayout.CENTER); JPanel t = new JPanel(); t.setLayout(new BorderLayout()); t.add(panel2_2 , BorderLayout.NORTH); t.add(panel2_3 , BorderLayout.CENTER); panel2.add(panel2_1 ); panel2.add(t ); // panel2.add(panel2_3 ); this.add(panel2); //设置窗口在屏幕上的位置、大小和可见性 this.setLocation(100, 100); this.setSize(1000, 700); this.setVisible(true); // addWindowListener(new WindowAdapter() { // public void windowClosing(WindowEvent e) { // exitWindowChoose(); // } // }); this.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);//使用 System exit 方法退出应用程序 // 测试专用： textAreaGrammar.setText("S->AB\n" + "S->bC\n"+"C->AD\n"+"C->b\nA->#\nA->b\nD->aS\nD->c\nB->#\nB->aD"); buttonCertainGrammar.doClick(); // textAreaGrammar.setText("E->TR\n" // + "R->+TR\n" // + "R->#\n" // + "T->TY\n" // + "Y->*FY\n" // + "Y->#\n" // + "F->(E)\n" // + "F->a"); // // buttonCertainGrammar.doClick(); /* E->TR R->+TR R-># T->TY Y->*FY Y-># F->(E) F->a */ } boolean certainGrammar(){ if (currentGrammar !=null){ return currentGrammar.isL1L(); } return false; } @Override public void actionPerformed(ActionEvent e) { if (e.getSource() == buttonCertainGrammar){ initGrammar(); if (certainGrammar() ){ JOptionPane.showMessageDialog(null, "合法", "判断结果", JOptionPane.ERROR_MESSAGE); }else { JOptionPane.showMessageDialog(null, "不合法", "判断结果", JOptionPane.ERROR_MESSAGE); currentGrammar = null; } // currentGrammar.show(textAreaFirstSet); }else if(e.getSource() == buttonGenerateFirstSet){ // 生成First集 if (currentGrammar !=null){ currentGrammar.showFirstSet(textAreaFirstSet); } }else if (e.getSource() == buttonGenerateFollowSet){ if (currentGrammar !=null){ currentGrammar.showFollowSet(textAreaFollowSet); } }else if (e.getSource() == buttonGenerateForecastAnalysis){ // 显示 构造 预测分析表 if (currentGrammar !=null){ currentGrammar.showGenerateForecastTable(textAreaForecastAnalysisTable); }else { currentGrammar.generateForecastTable(); } }else if (e.getSource() == buttonAnalysis){ initAnalysis(); if (readyAnalysis == false){ textAreaAnalysisResult.append("无法启动"+ "\n"); }else { textAreaAnalysisResult.setText(""); startAnalysis(); textAreaAnalysisResult.append("准备完毕"+ "\n"); } }else if (e.getSource() == buttonOneChickDisplay) { while (isEnd == false){ oneStep(); } }else if (e.getSource() == buttonSingleStepShow){ oneStep(); }else if (e.getSource() == buttonOpenFile){ String ass = openGrammar(); if (ass !=null){ textAreaGrammar.setText(""); textAreaGrammar.append(ass); }else { textAreaGrammar.append("错误"); } }if (e.getSource() == buttonSaveFile){ save(); } } String openGrammar() { String str = null; JFileChooser fileChooser = new JFileChooser(); fileChooser.setFileSelectionMode(JFileChooser.FILES_ONLY); fileChooser.setDialogTitle("打开文件"); int result = fileChooser.showOpenDialog(this); if (result == JFileChooser.CANCEL_OPTION) { return null; } File fileName = fileChooser.getSelectedFile(); if (fileName == null || fileName.getName().equals("")) { JOptionPane.showMessageDialog(this, "不合法的文件名", "不合法的文件名", JOptionPane.ERROR_MESSAGE); } else { try { FileInputStream fis = new FileInputStream(fileName); InputStreamReader isr = new InputStreamReader(fis, "gbk");//避免中文乱码 BufferedReader bfr = new BufferedReader(isr); // FileReader fr = new FileReader(fileName); // BufferedReader bfr = new BufferedReader(fr); String ans = ""; int count = 0; if ((str = bfr.readLine()) != null) { count = 1; } while (count != 0) { // System.out.print(str); ans = ans.concat(str) + "\n"; if ((str = bfr.readLine()) != null) { count = 1; // System.out.print("\n"); } else { count = 0; } } return ans; } catch (Exception e) { } } return null; } void save( ){ String str = null; JFileChooser fileChooser = new JFileChooser(); fileChooser.setFileSelectionMode(JFileChooser.FILES_ONLY); //fileChooser.setApproveButtonText("确定"); fileChooser.setDialogTitle("保存"); int result = fileChooser.showSaveDialog(this); File saveFileName = fileChooser.getSelectedFile(); if (saveFileName == null || saveFileName.getName().equals("")) { JOptionPane.showMessageDialog(this, "不合法的文件名", "不合法的文件名", JOptionPane.ERROR_MESSAGE); } else { try { FileWriter fw = new FileWriter(saveFileName); BufferedWriter bfw = new BufferedWriter(fw); String ans = textAreaGrammar.getText(); bfw.write(ans); bfw.flush();//刷新该流的缓冲 bfw.close(); } catch (IOException ioException) { } } } void oneStep(){ // 往前分析一步 if (analIndex == sequence.length){ isEnd =true; textAreaAnalysisResult.append("分析结束 句子合法 \n"); return; } char sour = analStack.peek(); char des = sequence[analIndex]; if (sour == des){ analIndex++; analStack.pop(); textAreaAnalysisResult.append("匹配" + sour + "\n"); textAreaAnalysisResult.append("当前句子" + String.valueOf(sequence).substring(analIndex)+ "\n"); textAreaAnalysisResult.append("当前分析栈" + analStack.toString()+ "\n"); textAreaAnalysisResult.append("\n\n"); return; } Map<Character , pUnit> now = currentGrammar.forecastAnalysisTable.get(new Character(sour)); if (now == null){ textAreaAnalysisResult.append("出错"+ "是合法句子 \n"); isEnd = true; return; } pUnit ans = now.get(new Character(des)); if (ans == null){ textAreaAnalysisResult.append("出错"+ "是合法句子 \n"); isEnd = true; return; } textAreaAnalysisResult.append("匹配产生式"+ans.toString()+ "\n"); analStack.pop(); String lll = ans.des; char[] lis = lll.toCharArray(); int len = lis.length; int i = len-1; for (;i>=0 ; i--){ if (lis[i] == '#'){ break; } analStack.push(new Character(lis[i])); } textAreaAnalysisResult.append("当前句子" + String.valueOf(sequence).substring(analIndex)+ "\n"); textAreaAnalysisResult.append("当前分析栈" + analStack.toString()+ "\n"); textAreaAnalysisResult.append("\n\n"); } void initAnalysis(){ if (currentGrammar == null || currentGrammar.forecastAnalysisTable == null){ readyAnalysis = false; }else { readyAnalysis = true; } } void startAnalysis(){ // 启动 分析 String a = textFieldWaitAnalysisSentence.getText(); a = a+"#"; sequence = a.toCharArray(); analIndex = 0; analStack.clear(); analStack.push(new Character(new Character('#'))); analStack.push(new Character(currentGrammar.S)); isEnd = false; } void initGrammar(){ String text = textAreaGrammar.getText(); initGrammar(text); } void initGrammar(String text){ String[] gra = text.split("\n"); // 根据 输入的产生式 初始化 文法 // 先统计 终结符 和 非终结符 grammar ans = new grammar(); Set<Character> VN = new HashSet<>(); Set<Character> VT = new HashSet<>(); char[] all = text.toCharArray(); // 先单独抽出 S ans.S = all[0]; for (char a : all){ if (isBigLetter(a)){ VN.add(new Character(a)); } if (isSmallLetter(a)){ VT.add(new Character(a)); } } // 将集合 转换为数组 初始化 VN 和VT ans.VN = setToCharArray(VN); ans.VT = setToCharArray(VT); // System.out.println(VN); // System.out.println(VT); // 建立一个 非终结符 到下标的映射 Map<Character , Integer> indexMap = new HashMap<>(); int i=0; for (Character a : VN){ indexMap.put(a , new Integer(i++)); } // 下面 根据非终结符的数量 初始化P 然后遍历文法 添加产生式 ans.P = new ArrayList[VN.size()]; for (i=0 ; i<VN.size() ; i++){ ans.P[i] = new ArrayList<>(); } // 下面 遍历 添加 for (String now : gra){ // 每一行 是一个产生式 now= now.replaceAll(" ",""); char[] arr = now.toCharArray(); char source = arr[0]; String des = now.substring(3); pUnit x = new pUnit(String.valueOf(source) , des); ans.P[ indexMap.get(source) ].add(x); } // 初始化完成 // System.out.println("初始化结果"); // System.out.println(ans.P); currentGrammar = ans; // currentGrammar.show(); } // 判断 是大写字母 还是小写字母 boolean isBigLetter( char a){ if (a >= 'A' && a<='Z') { return true; } return false; } boolean isSmallLetter( char a ){ if (a >= 'a' && a<='z') { return true; } if (law.indexOf(String.valueOf(a)) !=-1){ return true; } return false; } public char[] setToCharArray(Set<Character> a){ char[] ans = new char[a.size()]; int inde = 0; for (Character s: a){ ans[inde++] = s; } return ans; } } // 文法类 class grammar{ char[] VN ; char[] VT; ArrayList<pUnit>[] P; // P[i] 以VN[i] 开头 static int UNKNOWN = -1; static int YES = 1; static int NO = 0; private Map<Character , Set<Character>> firstSet = null; private boolean[] isIntroductionEmpty = null; private Map<Character , Set<Character>> followSet = null; private Map<String , Set<Character>> selectSet = null; Map<Character , Map<Character , pUnit>> forecastAnalysisTable= null; char S; boolean searchFirstSet(char left , char destination) { Set<Character> des = firstSet.get(new Character(left)); if (des != null){ // System.out.println(left); // System.out.println(des); return des.contains(new Character(destination)); } return false; } boolean searchFollowtSet(char left , char destination){ Set<Character> des = followSet.get(new Character(left)); if (des != null){ return des.contains(new Character(destination)); } return false; } String searchForecasAT(char nEndChar , char currenChar){ Map<Character , pUnit> des = forecastAnalysisTable.get(new Character(nEndChar)); if (des != null){ return des.get(new Character(currenChar)).toString(); } return null; } void showGenerateForecastTable(JTable panel){ if (forecastAnalysisTable == null){ generateForecastTable(); } int len1 = VN.length; int len2 = VT.length+1; String[] anfd = new String[len2]; int i , j; anfd[0] = new String("\\"); for (i=1 ; i<len2 ; i++){ anfd[i] = String.valueOf(VT[i-1]); } TableModel model = new DefaultTableModel(anfd , len2); // TableColumnModel columnModel = new DefaultTableColumnModel(); // TableColumn tableColumn = new TableColumn(); // panel.setColumnModel(columnModel); panel.setModel(model); for (i = 0 ; i< len1 ; i++ ){ model.setValueAt(String.valueOf(VN[i]) , i , 0); for (j = 1 ; j<len2 ; j++){ model.setValueAt(String.valueOf( searchForecasAT(VN[i] , VT[j-1]) ) , i , j); } } // panel.setText(""); // Set<Character> VT = arrToSet(this.VT); // VT.add(new Character('#')); // for (char a : VN){ // System.out.print(a + ": \n"); // // Map<Character , pUnit> now = forecastAnalysisTable.get(new Character(a)); // for (char s : VT){ // if (now.containsKey(new Character(s))){ // // 包含 // System.out.print(" "+String.valueOf(s) + " "); // System.out.print( now.get(new Character(s)).toString() + "\n"); // }else { // System.out.print(" "+String.valueOf(s) + " null" + "\n"); // } // // // } // // } } boolean isL1L(){ if (selectSet == null){ getSelectSet(); } // 判断是不是 LL1 int i=0; for (ArrayList<pUnit> a : P){ // 第i个的所有产生式 int count = 0; Set<Character> sc = new HashSet<>(); for (pUnit b : a){ if (selectSet.containsKey(b.toString())){ Set<Character> now = selectSet.get(b.toString()); sc.addAll(now); count += now.size(); } } if (count != sc.size()){ return false; } i++; } return true; } void generateForecastTable(){ if (selectSet == null){ getSelectSet(); } if (forecastAnalysisTable != null){ return; } Map<Character , Map<Character , pUnit>> table = new HashMap<>(); int i=0; for (ArrayList<pUnit> a : P){ // 第i个的所有产生式 Map<Character , pUnit> k = new HashMap<>(); for (pUnit b : a){ Set<Character> no = selectSet.get(b.toString()); for(char ass : no){ k.put(new Character(ass) , b); } } table.put( new Character(VN[i]) , k ); i++; } this.forecastAnalysisTable = table; } void showFirstSet(JTable panel){ // 显示 first集 int len1 = VN.length; int len2 = VT.length+1; String[] anfd = new String[len2]; int i , j; anfd[0] = new String("\\"); for (i=1 ; i<len2 ; i++){ anfd[i] = String.valueOf(VT[i-1]); } TableModel model = new DefaultTableModel(anfd , len2); // TableColumnModel columnModel = new DefaultTableColumnModel(); // TableColumn tableColumn = new TableColumn(); // panel.setColumnModel(columnModel); panel.setModel(model); for (i = 0 ; i< len1 ; i++ ){ model.setValueAt(String.valueOf(VN[i]) , i , 0); for (j = 1 ; j<len2 ; j++){ model.setValueAt(String.valueOf( searchFirstSet(VN[i] , VT[j-1]) ) , i , j); } } // panel.setText(""); // // Map<Character , Set<Character>> ans = getFirstSet(); // System.out.print("显示 各终结符/非终结符的first集合 \n"); // System.out.print("\n"); // System.out.print(ans.toString()); // // // System.out.print("显示 各产生式的first集合 \n"); // for (ArrayList<pUnit> a : P){ // for (pUnit b : a){ // System.out.print(b.toString() + " "); // // // //// 这里展示各产生式的右部符号串的first集合 // System.out.print(getFirstSet(b).toString() + "\n"); //// System.out.println(b.toString()); // // } // } } void showFollowSet(JTable panel){ int len1 = VN.length; int len2 = VT.length+1; String[] anfd = new String[len2]; int i , j; anfd[0] = new String("\\"); for (i=1 ; i<len2 ; i++){ anfd[i] = String.valueOf(VT[i-1]); } TableModel model = new DefaultTableModel(anfd , len2); // TableColumnModel columnModel = new DefaultTableColumnModel(); // TableColumn tableColumn = new TableColumn(); // panel.setColumnModel(columnModel); panel.setModel(model); for (i = 0 ; i< len1 ; i++ ){ model.setValueAt(String.valueOf(VN[i]) , i , 0); for (j = 1 ; j<len2 ; j++){ model.setValueAt(String.valueOf( searchFollowtSet(VN[i] , VT[j-1]) ) , i , j); } } // panel.setText(""); // Map<Character , Set<Character>> an = getFollowSet(); // panel.append("显示 follow集合 \n"); // panel.append("\n"); // panel.append(an.toString()); } public grammar() { // P = new ArrayLis } void show(JTextArea panel){ panel.setText(""); for (ArrayList<pUnit> a : P){ for (pUnit b : a){ panel.append(b.toString() + " "); // 这里展示各产生式的右部符号串的first集合 panel.append(getFirstSet(b).toString() + "\n"); // System.out.println(b.toString()); } } // 显示 first集合 // 这里展示 first集合 Map<Character , Set<Character>> ans = getFirstSet(); panel.append("显示 first集合 \n"); panel.append("\n\n"); panel.append(ans.toString()); // 这里展示 follow集合 Map<Character , Set<Character>> an = getFollowSet(); panel.append("显示 follow集合 \n"); panel.append("\n\n"); panel.append(an.toString()); panel.append("\n显示 select集\n"); for (ArrayList<pUnit> a : P){ for (pUnit b : a){ panel.append(b.toString() + " "); // 这里展示各产生式的右部符号串的first集合 panel.append(getSelectSet(b).toString() + "\n"); // System.out.println(b.toString()); } } } void show(){ System.out.println(VT); System.out.println(VN); for (ArrayList<pUnit> a : P){ for (pUnit b : a){ System.out.print(b.toString() + "\n"); // System.out.println(b.toString()); } } } public grammar(char[] VN, char[] VT, ArrayList<pUnit>[] p, char s) { this.VN = VN; this.VT = VT; P = p; S = s; } void add( char source , String des ){ int x = String.valueOf(VN).charAt(source); pUnit a = new pUnit(source , des); P[x].add(a); } boolean[] getIsIntroductionEmpty(){ if (isIntroductionEmpty !=null){ return isIntroductionEmpty; } int[] ans = new int[VN.length]; boolean[] aans = new boolean[VN.length]; int i; int l = VN.length; for (i=0 ; i<l ; i++){ ans[i] = UNKNOWN; } grammar now = this.copy(); // 删除右部含有非终结符的产生式 int j; for (i=0 ; i<l ; i++){ for (j=0 ; j<now.P[i].size() ; j++){ pUnit s = now.P[i].get(j); if (s.desIsEmpty()){ ans[i]= YES; // System.out.println("fdsv"); now.P[i].clear(); // System.out.println("sd----"); } if (s.desContainEndChar(VT)){ now.P[i].remove(j); } } if (now.P[i].size() == 0 && ans[i] == UNKNOWN){ ans[i] = NO; } } // now.show(); // 重复扫描 int count = 1; while (count ==1){ count = 0; for (i=0 ; i<l ; i++){ // System.out.println(i); for (j=0 ; j<now.P[i].size() ; j++){ pUnit s = now.P[i].get(j); // System.out.println(s.toString()); // now.P[i].remove(j); // System.out.print(s.des); // System.out.println("ds"); if (s.desIsEmpty()){ ans[i] = YES; count = 1; now.P[i].clear(); break; } int z; for (z= 0 ; z<l ; z++){ if (ans[z] == YES){ s.des = s.des.replaceAll(String.valueOf(VN[z]) , ""); if (s.desIsEmpty()){ ans[i] = YES; count = 1; now.P[i].clear(); break; } } } } } } for (i = 0 ; i<l ; i++){ if (ans[i] == YES){ aans[i] = true; }else { aans[i] = false; } // System.out.println(aans[i]); } isIntroductionEmpty = aans; return aans; } grammar copy(){ grammar ans = new grammar(); ans.VN = String.valueOf(this.VN).toCharArray(); ans.VT = String.valueOf(this.VT).toCharArray(); ans.S = this.S; ans.P = new ArrayList[VN.length]; int i; int l = VN.length; for (i=0 ; i<l ; i++){ ans.P[i] = new ArrayList<>(); for (pUnit a:this.P[i] ){ ans.P[i].add(new pUnit(a)); } } // ans.show(); return ans; } // 计算 每一个文法符号的 first集 Map<Character , Set<Character>> getFirstSet() { if (firstSet !=null){ return firstSet; } boolean[] isToEmpty = getIsIntroductionEmpty(); // for (boolean a : isToEmpty){ // System.out.println(a); // } // System.out.println(VT); // System.out.println(VN); Map<Character , Integer> indexMap = new HashMap<>(); int i = 0; // for (char a :VT){ // indexMap.put(new Character(a) , i++); // } for (char a :VN){ indexMap.put(new Character(a) , i++); } Map<Character , Set<Character>> ans = new HashMap<>(); // 先统计非终结符的first集 for (char a : VT){ Set<Character> x = new HashSet<>(); x.add(new Character(a)); ans.put(new Character(a) , x); } for (char a : VN){ Set<Character> x = new HashSet<>(); ans.put(new Character(a) , x); } int count = 1; Set<Character> VNSet = arrToSet(VN); Set<Character> VTSet = arrToSet(VT); // 这里统计一个 可以推出空的集合 用于后面判断 Set<Character> toEmpty = new HashSet<>(); for (i=0 ; i< VN.length ; i++){ if (isToEmpty[i]){ toEmpty.add(new Character(VN[i])); } } int j; while (count == 1){ count = 0; // 执行第二步 若X∈VN,且有Xa…,a∈ VT,则a∈FIRST(X); 第三步 若X∈VN，X ε ,则ε∈ FIRST(X); // 遍历 产生式 X必定属于VN 看右边 是否 都是终结符 i=0; for (ArrayList<pUnit> now : P){ for (pUnit x : now){ // 当前 为第i个非终结符的产生式 Set<Character> cu = arrToSet(x.des.toCharArray()); // 是否 全为 终结符 第二步 // System.out.println(cu); // System.out.println(VT); if (VTSet.containsAll(cu) && ans.get(VN[i]).contains(new Character( x.des.charAt(0) )) == false){// 符合且未包含 // 全部包含 即全为终结符 // System.out.println(" 第二步 "); ans.get(VN[i]).add(new Character( x.des.charAt(0) )); // System.out.println(VTSet); // System.out.println(x.des.charAt(0)); count = 1; // System.out.println("sdjk"); } // 顺便判断 第三步 if ( isToEmpty[i] == true && ans.get(VN[i]).contains(new Character('#')) == false){ // 该非终结符 可以推出空 ans.get(VN[i]).add(new Character( '#')); // System.out.println("fds"); count = 1; } } i++; } // 执行 第四步和第五步 4)若X∈VN，Y1,Y2,…,Yn都∈VN，且有XY1Y2…Yn 。当Y1,Y2,…,Yi-1都 ε时，（其中1<=i<=n),则FIRST(Y1)-{ε}, FIRST(Y2)-{ε},…,FIRST(Yi-1)-{ε},FIRST(Yi)都包含在FIRST(X)中。 // 都是 非终结符 i=0; for (ArrayList<pUnit> now : P){ // 统计要添加的所有新的 元素 以判断是否 有新的添加进去 Set<Character> updateSet = new HashSet<>();// 要添加的 最后判断 是否有新的 for (pUnit x : now){ // 当前 为第i个非终结符的产生式 Set<Character> cu = arrToSet(x.des.toCharArray()); // 是否 全为 非终结符 第四步 if (VNSet.containsAll(cu)) { // 全部包含 即全为非终结符 // 判断 第四步 还是 第五步 即： -> 是否 全都可以推出空 if (toEmpty.containsAll(cu)){ // 全都可以推出空 第五步 // 更新 updateSet for (Character aa : cu){ for (Character as : ans.get(aa)){ if (as !='#'){ updateSet.add(as); } } } updateSet.add(new Character('#')); // 第五步 }else { // 非 全都可以推出空 第四步 char[] curr = x.des.toCharArray(); for (int ii = 0 ; ii < curr.length ; ii++){ if (toEmpty.contains(curr[ii])){ // 属于 0-(i-1) if (updateSet.contains(new Character('#'))){ updateSet.addAll(ans.get(curr[ii])); }else { updateSet.addAll(ans.get(curr[ii])); updateSet.remove(new Character('#')); } }else { // 属于 i updateSet.addAll(ans.get(curr[ii])); break; } } } // ok }else { // 这里就是 含有 非终结符 也有 终结符 char[] akd = x.des.toCharArray(); for ( char ds : akd){ // 非终结符 if (VNSet.contains(new Character(ds))){ if (ans.get(ds).contains('#')){ //可以退空 if (updateSet.contains('#')){ updateSet.addAll(ans.get(ds)); }else { updateSet.addAll(ans.get(ds)); updateSet.remove('#'); } continue; }else { updateSet.addAll(ans.get(ds)); break; } } if (VTSet.contains(ds)){ updateSet.add(new Character(ds)); break; } } } } // 这里遍历完 第i的个非终结符的所有产生式 判断 是否有更新 if (ans.get(new Character(VN[i])).containsAll(updateSet)){ // 包含全部 }else { count = 1; ans.get(new Character(VN[i])).addAll(updateSet); // 更新 } i++; } // System.out.println(ans.toString()); } firstSet = ans; return ans; } public Set<Character> arrToSet(char[] a){ Set<Character> ans = new HashSet<>(); for (char as : a){ ans.add(new Character(as)); } return ans; } Set<Character> getFirstSet(pUnit a){ if (firstSet == null){ getFirstSet(); } //first集未初始化 Set<Character> ans = new HashSet<>(); // Map<Character , Integer> indexMap = new HashMap<>(); int i = 0; // show(); for (char aa :VN){ indexMap.put(new Character(aa) , i++); } // System.out.println(indexMap); Set<Character> VNSet = arrToSet(VN); Set<Character> VTSet = arrToSet(VT); char[] des = a.des.toCharArray(); // System.out.println(a.toString()); if (des[0] == '#'){ ans.add(new Character('#')); return ans; } for (char aa : des){ if(VTSet.contains(aa)){ ans.add(new Character(aa)); return ans; } if (isIntroductionEmpty[ indexMap.get(aa) ] ){ ans.addAll(firstSet.get(new Character(aa))); ans.remove(new Character('#')); }else { ans.addAll(firstSet.get(new Character(aa))); ans.remove(new Character('#')); return ans; } } ans.add(new Character('#')); return ans ; } Set<Character> getFirstSet(String a){ return getFirstSet(new pUnit("2",a)); } Map<Character , Set<Character>> getFollowSet(){ if (followSet !=null){ return followSet; } if (firstSet == null){ getFirstSet(); } Map<Character , Set<Character>> ans = new HashMap<>(); // 由于要统计 每个 follow 都不在增大时 结束 所以 这里统计一个总数 int count = 0;// 所有follow 为空 int i,j; int l = VN.length; // 初始化 for( char a : VN){ ans.put(new Character(a) , new HashSet<>()); } // 设A为文法开始符号，把#加入FOLLOW(A)中，（#为句子括号） ans.get(new Character(S)).add(new Character('#')); int update = 1; Set<Character> VNSet = arrToSet(VN); Set<Character> VTSet = arrToSet(VT); while (count != update){ count = update; // 遍历 所有产生式 i=0; for (ArrayList<pUnit> now : P){ for (pUnit x : now){ String des = x.des; char[] lis = des.toCharArray(); char source = x.source.charAt(0); // 第二步 /* 2）若BαAβ是一个产生式，则把FIRST(β)的非空元素加入FOLLOW(A)中。 如果β ε，则把FOLLOW(B)也加入FOLLOW(A)： 因为当有形如Dα1Bβ1 BαAβ的产生式时，A、B、D∈VN, α1,β1,α,β∈V*,在推导过程中可能出现句型序列如 S …α1Bβ1…=>…α1αAββ1 …=> …α1αAβ1, 故FIRST(β1)∈FOLLOW(B)和FIRST(β1) ∈ FOLLOW(A),所以FOLLOW(B)FOLLOW(A) */ // 过滤掉 右侧为空的 和 全为终结符的产生式 if (des.equals("#" )|| VTSet.containsAll(arrToSet(lis)) ){ continue; } // 含有 非终结符 检测 for(i=0 ;i<lis.length ; i++){ if (VNSet.contains(lis[i])){ // 是非终结符 if (i== lis.length-1){ // 最后一个 ans.get(lis[i]).addAll( ans.get(new Character(source)) ); continue; } String sub = des.substring(i+1); Set<Character> fir = getFirstSet(sub); // ans.get(lis[i]).addAll(fir); if (fir.contains(new Character('#'))){ ans.get(lis[i]).addAll( ans.get(new Character(source)) ); }else { } } } } } update = 0; for(char aaa: VN){ update = update+ ans.get(new Character(aaa)).size(); } } this.followSet = ans; return ans; } Map<String , Set<Character>> getSelectSet() { if (selectSet != null){ return selectSet; } if (firstSet == null){ getFirstSet(); } if (followSet == null){ getFollowSet(); } Map<String, Set<Character>> ans = new HashMap<>(); for (ArrayList<pUnit> a : P) { for (pUnit b : a) { // 这里展示各产生式的右部符号串的first集合 ans.put(b.toString(), getSelectSet(b)); // System.out.println(b.toString()); } } selectSet = ans; return ans; } Set<Character> getSelectSet( pUnit a ){ // if (selectSet == null){ // getSelectSet(); // } // System.out.println(a.toString()); if (a.des == "#"){ return followSet.get(new Character(a.source.charAt(0))); } Set<Character> now = getFirstSet(a); if (now.contains(new Character('#'))){ now.remove(new Character('#')); if (this.followSet == null){ getFollowSet(); } Set<Character> as = followSet.get(new Character(a.source.charAt(0))); now.addAll(as); return now; }else { return now; } } } class pUnit { String source; String des; public pUnit() { } @Override public String toString() { return source + "->" + des; } public pUnit(String source, String des) { this.source = source; this.des = des.replaceAll("\n",""); } public pUnit(char source, String des) { this.source = String.valueOf(source); this.des = des; } public pUnit(pUnit a) { this.des = a.des; this.source = a.source; } boolean desContainEndChar(char[] VT){ for (char a : VT){ if (des.indexOf(a) !=-1){ return true; } } return false; } boolean desIsEmpty(){ if (des.equals("#") || des.equals("")){ return true; } return false; } }

这里没有添加main 函数ou 直接新建一个LL1analysis类就行了

个人作品， 如有错误，请指出； 如要转载，请注明出处。 三克油。。