LL1语法分析,first集,follow集,分析表Java实现.doc

import java.awt.*;import java.awt.event.*;import javax.swing.*;import javax.swing.table.DefaultTableModel;import java.sql.*;import java.util.Vector;public class LL1 extends JFrame implements ActionListener /* * */private static final long serialVersionUID = 1L;JTextField tf1;JTextField tf2;JLabel l;JButton b0;JPanel p1, p2, p3;JTextArea t1, t2, t3;JButton b1, b2, b3;JLabel l0, l1, l2, l3, l4;JTable table;Statement sta;Connection conn;ResultSet rs;DefaultTableModel dtm;String Vn = null;Vector P = null;int firstComplete = null;/ 存储已判断过first的数据char first = null;/ 存储最后first结果int followComplete = null;/ 存储已判断过follow的数据char follow = null;/ 存储最后follow结果char select = null;/ 存储最后select结果int LL = 0;/ 标记是否为LL（1）String vt_tou = null;/ 储存VtObject shuju = null;/ 存储表达式数据char yn_null = null;/ 存储能否推出空LL1() setLocation(100, 0);setSize(700, 780);tf1 = new JTextField(13);tf2 = new JTextField(13);l = new JLabel();l0 = new JLabel(输入字符串：);l1 = new JLabel(输入的文法为： );l2 = new JLabel( );l3 = new JLabel(分析的结果： );l4 = new JLabel(预测分析表： );/ p1=new JPanel();p2 = new JPanel();p3 = new JPanel();t1 = new JTextArea(24, 20);t2 = new JTextArea(1, 30);t3 = new JTextArea(24, 40);b0 = new JButton(确定(S为开始);b1 = new JButton( 判断文法 );b2 = new JButton(输入);b3 = new JButton(清空);table = new JTable();JScrollPane jp1 = new JScrollPane(t1);JScrollPane jp2 = new JScrollPane(t2);JScrollPane jp3 = new JScrollPane(t3);p2.add(tf1);p2.add(l);p2.add(tf2);p2.add(b0);p2.add(b1);p2.add(l0);p2.add(l2);p2.add(jp2);p2.add(b2);p2.add(b3);p2.add(l1);p2.add(l3);p2.add(jp1);p2.add(jp3);p3.add(l4);p3.add(new JScrollPane(table);add(p2, Center);add(p3, South);b0.addActionListener(this);b1.addActionListener(this);b2.addActionListener(this);b3.addActionListener(this);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);table.setPreferredScrollableViewportSize(new Dimension(660, 200);setVisible(true); /界面设计 public void actionPerformed(ActionEvent e) if (e.getSource() = b0) String a = tf1.getText();String b = tf2.getText();t1.append(a + + b + n);if (e.getSource() = b1) t3.setText();int Vnnum = 0, k;Vn = new String100;P = new Vector();String s = t1.getText().split(n);for (int i = 0; i s.length; i+) if (s.length 2) t3.setText(文法输入有误，请重新输入);/ 判断长度是否符合return;if (si.charAt(0) = A& si.charAt(1) = ) for (k = 0; k = Vnnum) VnVnnum = si.substring(0, 1);/ 存入Vn数据Vnnum+;P.add(si); else t3.setText(文法输入有误，请重新输入);return;yn_null = new char100;first = new charVnnum100;int flag = 0;String firstVn = null;firstComplete = new intVnnum;for (int i = 0; Vni != null; i+) / 依次求 FIRST*flag = 0;firstVn = new String20;if (flag = add_First(firsti, Vni, firstVn, flag) = -1)return;firstCompletei = 1;t3.append(first集： + n); / 显示FIRST*for (int i = 0; Vni != null; i+) t3.append(first( + Vni + )= );for (int j = 0; firstij != 0; j+) t3.append(firstij + , );t3.append( + n);follow = new charVnnum100;String followVn = null;followComplete = new intVnnum;for (int i = 0; Vni != null; i+) / 求FOLLOW*flag = 0;followVn = new String20;if(i=0)else if (flag = tianjiaFollow(followi, Vni, followVn, flag) = -1)return;followCompletei = 1;t3.append(follow集： + n); / 显示FOLLOW*for (int i = 0; Vni != null; i+) t3.append(follow( + Vni + )= );for (int j = 0; followij != 0; j+) t3.append(followij + , );t3.append( + n);select = new charP.size()100;for (int i = 0; i P.size(); i+) / 求SELECT*flag = 0;tianjiaSelect(selecti, (String) P.elementAt(i), flag);t3.append(select集： + n); / 显示SELECT*for (int i = 0; i P.size(); i+) t3.append(select( + (String) P.elementAt(i) + )= );for (int j = 0; selectij != 0; j+) t3.append(selectij + , );t3.append( + n);for (int i = 0; Vni != null; i+)/ 判断select交集是否为空int biaozhi = 0;char save = new char100;for (int j = 0; j P.size(); j+) String t = (String) P.elementAt(j);if (t.substring(0, 1).equals(Vni) for (k = 0; selectjk != 0; k+) if (puanduanChar(save, selectjk) savebiaozhi = selectjk;biaozhi+; else/ 当有交集时，不为LL（1）文法t3.append(不是LL（1）文法！ + n);return;char Vt = new char100;int biaozhi = 0;for (int i = 0; i P.size(); i+) String t = (String) P.elementAt(i);for (int j = 2; j Z | t.charAt(j) A) if (puanduanChar(Vt, t.charAt(j) Vtbiaozhi = t.charAt(j);biaozhi+;if (puanduanChar(Vt, #)/ 若可推出空集，则将#加入Vt。Vtbiaozhi = #;biaozhi+;vt_tou = new Stringbiaozhi + 1;/ 根据select和表达式生成预测分析表shuju = new StringVnnumbiaozhi + 1;String f = ;vt_tou0 = f;for (int i = 0; i biaozhi; i+) vt_toui + 1 = String.valueOf(Vti);for (int i = 0; i Vnnum; i+) shujui0 = Vni;for (int i = 0; i P.size(); i+) String t = (String) P.elementAt(i);int j;for (j = 0; j Vn.length; j+) if (Vnj.equals(t.substring(0, 1) break;for (k = 0; selectik != 0; k+) int y = puanduanXulie(Vt, selectik);shujujy + 1 = t.substring(1);dtm = new DefaultTableModel(shuju, vt_tou);/ 显示预测分析表table.setModel(dtm);LL = 1;if (e.getSource() = b3)/ 清空列表tf1.setText();tf2.setText();t1.setText();t2.setText();t3.setText();Vn = null;P = null;firstComplete = null;first = null;followComplete = null;follow = null;select = null;dtm = new DefaultTableModel();table.setModel(dtm);if (e.getSource() = b2)/ 输入字符串并预测分析t3.setText();if (LL = 1) String s = t2.getText();for (int i = 0; i = 0; i-) zifufzifu = s.charAt(i);fzifu+;int buzhou = 2;char n = new char65;/ 存储要显示的内容t3.append(步骤 分析栈 剩余输入串 所用产生式或匹配+ n);n0 = 1;n15 = #;n14 = S;int u = 29;for (int i = fzifu - 1; i = 0; i-)nu = zifui;u+;while (!(fenxiffenxi - 1 = # & zifufzifu - 1 = #)/ 剩余输入串不为#则分析int i, j;char t = zifufzifu - 1;char k = fenxiffenxi - 1;if (t = k)/ 产生式匹配n49 = k;n50 = 匹;n51 = 配;t3.append(String.copyValueOf(n) + n);n = new char65;fzifu-;ffenxi-;if (buzhou = 0; y-)/ 处理分析栈，出栈nu = fenxiy;u+;u = 29;for (int y = fzifu - 1; y = 0; y-)/ 处理剩余字符串，消除一个字符nu = zifuy;u+;buzhou+;continue;for (i = 0; Vni != null; i+)/ 搜寻所用产生式的左部if (Vni.equals(String.valueOf(k)break;for (j = 0; j = vt_tou.length)/ 全部产生式都不能符合则报错t3.append(String.copyValueOf(n);t3.append(n + 该串不是该文法的句型 + n);return;Object result1 = shujuij;if (result1 = null) t3.append(String.copyValueOf(n);t3.append(n + 该串不是该文法的句型 + n);return; else/ 找到所用产生式n49 = Vni.charAt(0);u = 50;String result = (String) result1;for (int y = 0; y 0; i-)/ 将分析栈内非终结符换为右边表达式if (result.charAt(i) != #)fenxiffenxi = result.charAt(i);ffenxi+;if (buzhou = 0; y-) nu = fenxiy;u+;u = 29;for (int y = fzifu - 1; y = 0; y-) nu = zifuy;u+;buzhou+;n = new char65;n0 = 1;n14 = #;n29 = #;n49 = 分;n50 = 析;n51 = 成;n52 = 功;t3.append(String.copyValueOf(n);t3.append(n + 该串是此文法的句型 + n);return; else t3.setText(请先依次输入LL（1）文法，并点击 文法判断 按钮 + n);return;private int add_First(char a, String b, String firstVn, int flag) / 计算FIRST*（递归）if (puanduanString(firstVn, b.charAt(0) addString(firstVn, b); else return flag;for (int i = 0; i P.size(); i+) String t = (String) P.elementAt(i);for (int k = 2; k Z | t.charAt(k) A)/ 表达式右端第i个不是非终结符if (flag = 0 | puanduanChar(a, t.charAt(k) if (t.charAt(k) = #)/ #时直接加入firstif (k + 1 = t.length() aflag = t.charAt(k);flag+;int flag1 = 0;for (int j = 0; yn_nullj != 0; j+)/ 所求非终结符进入yn_null*if (yn_nullj = b.charAt(0)/ 判断能否推出空flag1 = 1;break;if (flag1 = 0) int j;for (j = 0; yn_nullj != 0; j+) yn_nullj = b.charAt(0);continue; else/ 终结符直接加入first*aflag = t.charAt(k);flag+;break;break; else/ 非终结符if (!puanduanString(Vn, t.charAt(k) int p = firstComplete(t.charAt(k);/ 当该非终结符的first已经求出if (p != -1) flag = addElementFirst(a, p, flag);/ 直接加入所求first else if (flag = add_First(a,String.valueOf(t.charAt(k), firstVn, flag) = -1)return -1;int flag1 = 0;for (int j = 0; yn_nullj != 0; j+)/ 当非终结符的first有空if (yn_nullj = t.charAt(k) flag1 = 1;break;if (flag1 = 1)/ 当非终结符的first能推出空if (k + 1 = t.length() & puanduanChar(a, #)/ 之后无符号，且所求first无#aflag = #;/ first中加入#flag+;continue;/ 判断下一个字符 else break; else/ 错误t3.setText(文法输入有误 + n);return -1;return flag;private int tianjiaFollow(char a, String b, String followVn, int flag) / 计算FOLLOW*（递归）if (puanduanString(followVn, b.charAt(0) addString(followVn, b); else return flag;if (b.equals(A)/ 把$存入初始符号的follow集中aflag = $;flag+;for (int i = 0; i P.size(); i+) String t = (String) P.elementAt(i);for (int j = 2; j t.length(); j+) if (t.charAt(j) = b.charAt(0) & j + 1 Z | t.charAt(j + 1) A)/ 所求为终结符if (flag = 0 | puanduanChar(a, t.charAt(2)/ 自身aflag = t.charAt(j + 1);flag+;else/ 所求为非终结符int k;for (k = 0; Vnk != null; k+) if (Vnk.equals(String.valueOf(t.charAt(j + 1) break;/ 找寻下一个非终结符的Vn位置flag = addElementFirst(a, k, flag);/ 把下一个非终结符first加入所求follow集for (k = j + 1; k Z | t.charAt(j + 1) = t.length()/ 下一个非终结符可推出空，把表达式左边非终结符的follow集加入所求follow集int p = followComplete(t.charAt(0);if (p != -1) flag = addElementFollow(a, p, flag); else if (flag = tianjiaFollow(a,String.valueOf(t.charAt(0), followVn,flag) = -1)return -1; else/ 错误t3.setText(文法输入有误,请重新输入 + n);return -1;if (t.charAt(j) = b.charAt(0) & j + 1 = t.length()/ 下一个字符为空，把表达式左边非终结符的follow集加入所求follow集int p = followComplete(t.charAt(0);if (p != -1) flag = addElementFollow(a, p, flag); else if (flag = tianjiaFollow(a,String.valueOf(t.charAt(0), followVn, flag) = -1)return -1;return flag;private void tianjiaSelect(char a, String b, int flag) / 计算SELECT*int i = 2;int biaozhi = 0;while (i Z | b.charAt(i) = A & b.charAt(i) = Z& i + 1 = A & b.charAt(i) = b.length()/ 是非终结符且没有下一个字符int j;for (j = 0; Vni != null; j+) if (Vnj.equals(String.valueOf(b.charAt(i) break;for (int k = 0; firstjk != 0; k+) if (puanduanChar(a, firstjk) if (firstjk = #) biaozhi = 1;/ 表达式右侧能推出空，标记 else aflag = firstjk;/ 不能推出空，直接将first集加入select集flag+;if (biaozhi = 1)/ 表达式右侧能推出空for (j = 0; Vni != null; j+) if (Vnj.equals(b.substring(0, 1)break;for (int k = 0; followjk != 0; k+) if (puanduanChar(a, followjk) aflag = followjk;/ 将表达式左侧的非终结符的follow加入selectflag+;break; else biaozhi = 0;break;/ 返回b在Vt的位置private int puanduanXulie(char Vt, char b) int i;for (i = 0; Vti != 0; i+) if (Vti = b)break;return i;/ 判断b是否在a中，在返回false，不在返回trueprivate boolean puanduanChar(char a, char b) for (int i = 0; ai != 0; i+) if (ai = b)return false;return true;/ 判断b是否在a中，在返回false，不在返回trueprivate boolean puanduanString(String a, char b) for (int i = 0; ai != null; i+) if (ai.equals(String.value