实验三 LR1分析法 JAVA.docVIP

实验三 LR(1)分析法一、实验目的 构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验内容对下列文法，用LR（1）分析法对任意输入的符号串进行分析： （1）E- E+T（2）E- ET（3）T- T*F（4）T- T/F（5）F- (E)（6）F- i三、LR（1）分析法实验设计思想及算法 (1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。u LR分析器由三个部分组成：u 其中:SP为栈指针，Si为状态栈，Xi为文法符号栈。状态转换表用GOTOi，X=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。u ACTIONi，a规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进： actioni，a= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。(2)归约： actioni，a=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTOi,A移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc: 当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是#，则为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。四、实验要求1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。 3、程序输入/输出实例： 输入一以#结束的符号串(包括+*/（）i#)：在此位置输入符号串 输出过程如下：步骤 状态栈 符号栈 剩余输入串 动 作 1 0 # i+i*i# 移进 i+i*i的LR分析过程步骤状态栈符号栈输入串动作说明10#i+i*i#ACTION0,i=S5,状态5入栈205#i+i*i#r6: Fi归约,GOTO(0,F)=3入栈303#F+i*i#r4: TF归约,GOTO(0,T)=3入栈402#T+i*i#r2: ET归约,GOTO(0,E)=1入栈501#E+i*i#ACTION1,+=S6,状态6入栈6016#E+i*i#ACTION6,i=S5,状态5入栈70165#E+i*i#r6: Fi归约,GOTO(6,F)=3入栈80163#E+F*i#r4: TF归约,GOTO(6,T)=9入栈90169#E+T*i#ACTION9,*=S7,状态7入栈1001697#E+T*i#ACTION7,i=S5,状态5入栈11016975#E+T*i#r6:Fi归约,GOTO(7,F)=10入栈120169710#E+T*F#r3: TT*F归约,GOTO(6,T)=9入栈130169#E+T#r1:EE+T,GOTO(0,E)=1入栈1401#E#Acc：分析成功4、输入符号串为非法符号串(或者为合法符号串)算术表达式文法的LR分析表状态ACTIONGOTOi+*()#ET F0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r55、 实验源程序LR.javaimport javax.swing.*;import java.awt.Dimension;import javax.swing.JButton;import java.awt.Rectangle;import java.util.Vector;import javax.swing.JTextArea;import javax.swing.JTextField;import javax.swing.JLabel;import javax.swing.JMenuBar;import javax.swing.JMenu;import javax.swing.JMenuItem;import javax.swing.JScrollPane;import java.awt.BorderLayout;import javax.swing.JDialog;public class LR extends JFrame private static final long serialVersionUID = 1L;/*private char VN=new char50;/非终结符集private char VT=new char50;/终结符集private String F=new String50;/产生式集private StringBuffer FirstVN;/非终结符的First集private intstaStack=new int50;/状态分析栈private charsymStack=new char50;/符号分析栈private booleanVNE;/非终结符与空串的关系表private int F_index=0;/产生式数组指针private intstaStack_index=0;/状态栈指针private int symStack_index=0;/符号栈指针private int ERROR=Integer.MAX_VALUE;/出错标志private char emp=;/空串private String error=x;/分析表显示的出错标志 / jve:decl-index=0:private String acc=acc;/分析表显示的分析成功标志private VectorVector State=new VectorVector(); /项目集 / jve:decl-index=0:private int Action;/Action动作数组private intGoto;/Goto动作数组private StringBuffer bridge1;/描述项目集之间的转换关系，在createLR1()中初始化private intbridge2;private JPanel jContentPane = null;private JTextArea jTextArea4 = null;private JTextArea jTextArea3 = null;private JTextArea jTextArea2 = null;private JTextArea jTextArea_LR1States = null;private JTextArea jTextArea_LR1AnalysisTable = null;private JTextField jTextField = null;private JTextField jTextField1 = null;private JTextField jTextField_testedString = null;private JLabel jLabel = null;private JLabel jLabel1 = null;private JLabel jLabel_LR1States = null;private JLabel jLabel_inputString = null;private JButton jButton_test = null;private JButton jButton_ok = null;private JButton jButton_delete = null;private JButton jButton_clearall = null;private JButton jButton_testPanel = null;private JMenuBar jJMenuBar = null;private JMenu jMenu1 = null;private JMenuItem jMenuItem1 = null;private JMenuItem jMenuItem2 = null;private JScrollPane jScrollPane_LR1States = null;private JScrollPane jScrollPane_LR1AnalysisTable = null;private JScrollPane jScrollPane2 = null;private JScrollPane jScrollPane3 = null;private JScrollPane jScrollPane4 = null;private JPanel jPanel = null;private JPanel jPanel1 = null;private JLabel jLabel_LR1AnalysisTable = null;private JButton jButton_fresh = null;private JButton jButton_TransFunGraph = null;private JFrame jFrame_testFrame = null; / jve:decl-index=0:visual-constraint=531,25private JPanel jContentPane_testFrame = null;private JDialog jDialog_TG = null; / jve:decl-index=0:visual-constraint=170,520private JPanel jContentPane_TG = null;public LR() super();initialize();private void initialize() this.setSize(583, 483);this.setJMenuBar(getJJMenuBar();this.setContentPane(getJContentPane();this.setTitle(LR1语法分析);this.setLocation(300,250);this.setVisible(true);private JPanel getJContentPane() if (jContentPane = null) jContentPane = new JPanel();jContentPane.setLayout(null);jContentPane.add(getJPanel(), null);jContentPane.add(getJPanel1(), null);return jContentPane;private JPanel getJPanel() if (jPanel = null) jPanel = new JPanel();jPanel.setLayout(null);jPanel.setBounds(new Rectangle(0, 0, 210, 430);/jPanel.setBackground(Color.green);jPanel.add(getJScrollPane4(), null);jPanel.add(getJScrollPane3(), null);return jPanel;private JPanel getJPanel1() if (jPanel1 = null) jPanel1 = new JPanel();jPanel1.setLayout(null);/jPanel1.setBackground(Color.green);jPanel1.setBounds(new Rectangle(210, 0, 368, 430);jLabel1 = new JLabel();/jLabel1.setForeground(Color.red);jLabel1.setBounds(new Rectangle(120, 58, 23, 24);jLabel1.setText(-);jLabel = new JLabel();/jLabel.setForeground(Color.red);jLabel.setBounds(new Rectangle(16, 19, 57, 23);jLabel.setText(产生式：);jPanel1.add(jLabel, null);jPanel1.add(getJTextField(), null);jPanel1.add(jLabel1, null);jPanel1.add(getJTextField1(), null);jPanel1.add(getJButton_delete(), null);jPanel1.add(getJButton_ok(), null);jPanel1.add(getJButton_clearall(), null);jPanel1.add(getJButton_testPanel(), null);jPanel1.add(getJScrollPane2(), null);return jPanel1;private JPanel getJContentPane_testFrame() if (jContentPane_testFrame = null) jContentPane_testFrame = new JPanel();jContentPane_testFrame.setLayout(null);jContentPane_testFrame.setBackground(null);jContentPane_testFrame.add(getJScrollPane_LR1States(), null);jContentPane_testFrame.add(getJScrollPane_LR1AnalysisTable(), null);jLabel_inputString = new JLabel();jLabel_inputString.setText(请输入待测句子：);jLabel_inputString.setBounds(new Rectangle(29, 25, 108, 18);jContentPane_testFrame.add(jLabel_inputString, null);jContentPane_testFrame.add(getJTextField_testedString(), null);jContentPane_testFrame.add(getJButton_test(), null);jContentPane_testFrame.add(getJButton_fresh(), null);jContentPane_testFrame.add(getJButton_TransFunGraph(), null);jLabel_LR1States = new JLabel();jLabel_LR1States.setText(LR1项目集);jLabel_LR1States.setBounds(new Rectangle(11, 65, 65, 18);jLabel_LR1States.addMouseListener(new java.awt.event.MouseAdapter() public void mouseReleased(java.awt.event.MouseEvent e) jTextArea_LR1States.setText();/准备数据createAll();/显示项目集displayLR1States();/*public void mouseExited(java.awt.event.MouseEvent e) jLabel_LR1States.setForeground(Color.black);public void mouseEntered(java.awt.event.MouseEvent e) jLabel_LR1States.setForeground(Color.green);*/);jContentPane_testFrame.add(jLabel_LR1States, null);jLabel_LR1AnalysisTable = new JLabel();jLabel_LR1AnalysisTable.setText(LR1分析表);jLabel_LR1AnalysisTable.setBounds(new Rectangle(264, 67, 66, 18);jLabel_LR1AnalysisTable.addMouseListener(new java.awt.event.MouseAdapter() /*public void mouseExited(java.awt.event.MouseEvent e) jLabel_LR1AnalysisTable.setForeground(Color.black);public void mouseEntered(java.awt.event.MouseEvent e) jLabel_LR1AnalysisTable.setForeground(Color.green);*/public void mouseReleased(java.awt.event.MouseEvent e) jTextArea_LR1AnalysisTable.setText();createAll();displayLR1AnalysisTable(););jContentPane_testFrame.add(jLabel_LR1AnalysisTable, null);return jContentPane_testFrame;private JDialog getJDialog_TG() if (jDialog_TG = null) jDialog_TG = new JDialog();jDialog_TG.setSize(new Dimension(361, 266);/jDialog_TG.setTitle(LR1状态图);/jDialog_TG.setBackground(Color.black);jDialog_TG.setLocationRelativeTo(jFrame_testFrame);jDialog_TG.setContentPane(getJContentPane_TG();return jDialog_TG;private JPanel getJContentPane_TG() if (jContentPane_TG = null) /jContentPane_TG = new TransformGraphPanel();jContentPane_TG.setLayout(new BorderLayout();return jContentPane_TG;private JTextField getJTextField() if (jTextField = null) jTextField = new JTextField();jTextField.setBounds(new Rectangle(16, 58, 91, 22);jTextField.addKeyListener(new java.awt.event.KeyAdapter() public void keyReleased(java.awt.event.KeyEvent e) String s=jTextField.getText();char c=s.charAt(0);if(cZ)/如果输入的不是大写字母，给予提示if(c=a)JOptionPane.showMessageDialog(LR.this,产生式左端非法！+自动将其转换成大写字母);jTextField.setText(jTextField.getText().toUpperCase();elsejTextField.setText();else if(s.length()1)JOptionPane.showMessageDialog(LR.this,这里只允许写一个大写字母！);jTextField.setText(String.valueOf(s.charAt(0););return jTextField;private JTextField getJTextField1() if (jTextField1 = null) jTextField1 = new JTextField(null);jTextField1.setBounds(new Rectangle(153, 58, 193, 22);jTextField1.addKeyListener(new java.awt.event.KeyAdapter() public void keyReleased(java.awt.event.KeyEvent e) if(jTextField1.getText().length()25)JOptionPane.showMessageDialog(LR.this, 最多处理25个字符！);jTextField1.setText(jTextField1.getText().substring(0, 25););return jTextField1;private JTextField getJTextField_testedString() if (jTextField_testedString = null) jTextField_testedString = new JTextField();jTextField_testedString.setText();jTextField_testedString.setBounds(new Rectangle(139, 23, 156, 22);return jTextField_testedString;private JMenuBar getJJMenuBar() if (jJMenuBar = null) jJMenuBar = new JMenuBar();/jJMenuBar.add(getJMenu();jJMenuBar.add(getJMenu1();return jJMenuBar;private JMenu getJMenu1() if (jMenu1 = null) jMenu1 = new JMenu();jMenu1.setText(示例文法);jMenu1.add(getJMenuItem1();jMenu1.add(getJMenuItem2();return jMenu1;private JMenuItem getJMenuItem1() if (jMenuItem1 = null) jMenuItem1 = new JMenuItem();jMenuItem1.setText(示例文法1);jMenuItem1.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent e) clearAll();F0=new String(SBB);F1=new String(BaB);F2=new String(Bb);for(int i=0;i3;i+)getElements(Fi);displayInformation(););return jMenuItem1;private JMenuItem getJMenuItem2() if (jMenuItem2 = null) jMenuItem2 = new JMenuItem();jMenuItem2.setText(示例文法2);jMenuItem2.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent e) clearAll();F0=new String(EaA);F1=new String(EbB);F2=new String(AcA);F3=new String(Ad);F4=new String(BcB);F5=new String(Bd);for(int i=0;i6;i+)getElements(Fi);displayInformation(););return jMenuItem2;private JButton getJButton_test() if (jButton_test = null) jButton_test = new JButton();jButton_test.setText(测试);jButton_test.setBounds(new Rectangle(324, 21, 61, 40);jButton_test.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent e) if(jTextField_testedString.getText().isEmpty()JOptionPane.showMessageDialog(jFrame_testFrame, 请输入待检测符号串);else if(F0!=null)/文法必须存在才可以进行以下操作createAll();analysisInPutString();elseJOptionPane.showMessageDialog(jFrame_testFrame, 请先载入文法！););return jButton_test;private JButton getJButton_ok() if (jButton_ok = null) jButton_ok = new JButton();/jButton_ok.setForeground(Color.red);jButton_ok.setText(确定添加);jButton_ok.setBounds(new Rectangle(16, 107, 90, 40);jButton_ok.setToolTipText(添加一个产生式);jButton_ok.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent e) if(jTextField.getText().length()0&isLegalStringToInt(s)int i=Integer.parseInt(s);if(iF_index-1)JOptionPane.showMessageDialog(LR.this, 不存在此标号的产生式！);elsedelete_a_f(i);displayInformation(););return jButton_delete;private JButton getJButton_clearall() if (jButton_clearall = null) jButton_clearall = new JButton();/jButton_clearall.setForeground(Color.red);jButton_clearall.setText(清空所有);jButton_clearall.setBounds(new Rectangle(16, 150, 90, 40);jButton_clearall.setToolTipText(删除所有的产生式);jButton_clearall.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent e) clearAll(););return jButton_clearall;private JButton getJButton_testPanel() if (jButton_testPanel = null) jButton_testPanel = new JButton();/jButton_testPanel.setForeground(Color.red);jButton_testPanel.setBounds(new Rectangle(153, 150, 90, 40);jButton_testPanel.setText(测试面板);jButton_testPanel.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent e) if(F0!=null)/检测文法是否载入getJFrame_testFrame();if(jFrame_testFrame!=null)jFrame_testFrame.setVisible(true);elseJOptionPane.showMessageDialog(LR.this, 请先载入文法！););return jButton_testPanel;private JButton getJButton_fresh() if (jButton_fresh = null) jButton_fresh = new JButton();jButton_fresh.setText(显示项目集和分析表);jButton_fresh.setBounds(new Rectangle(413, 21, 97, 40);jButton_fresh.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent e) jTextArea_LR1States.setText();jTextArea_LR1AnalysisTable.setText();createAll();displayLR1States();displayLR1AnalysisTable(););return jButton_fresh;private JButton getJButton_TransFunGraph() if (jButton_TransFunGraph = null) jButton_TransFunGraph = new JButton();/jButton_TransFunGraph.setText(状态转换图);/jButton_TransFunGraph.setBounds(new Rectangle(533, 21, 107, 27);jButton_TransFunGraph.addActionListener(new java.awt.event.ActionListener() public void actionPerformed(java.awt.event.ActionEvent e) createAll();if(jDialog_TG=null)getJDialog_TG();jDialog_TG.setVisible(true);elsejDialog_TG.setVisible(true););return jButton_TransFunGraph;private JTextArea getJTextArea4() if (jTextArea4 = null) jTextArea4 = new JTextArea();jTextArea4.setEditable(false);/禁止从文本区改写，以保证文法产生式的输入与修改是同一个接口jTextArea4.setText(非终结符：);/即只能从文本域输入jTextArea4.setLineWrap(true);/自动折行/jTextArea4.setBackground(Color.white);return jTextArea4;private JTextArea getJTextArea3() if (jTextArea3 = null) jTextArea3 = new JTextArea();jTextArea3.setE