实验三 LR(1)分析法一、实验目的构造 LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解 LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。二、实验内容对下列文法，用 LR（1）分析法对任意输入的符号串进行分析： （1）E- E+T（2）E- E T（3）T- T*F（4）T- T/F（5）F- (E)（6）F- i三、LR （1）分析法实验设计思想及算法 (1)总控程序，也可以称为驱动程序。对所有的 LR 分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的 LR 分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。 LR 分析器由三个部分组成： 其中:SP 为栈指针，Si为状态栈，Xi 为文法符号栈。状态转换表用GOTOi，X=j 表示，规定当栈顶状态为 i，遇到当前文法符号为 X 时应转向状态 j，X 为终结符或非终结符。 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 分析过程步骤 状态栈 符号栈 输入串 动作说明1 0 # i+i*i# ACTION0,i=S5,状态 5 入栈2 05 #i +i*i# r6: F i 归约,GOTO(0,F)=3 入栈3 03 #F +i*i# r4: TF 归约,GOTO(0,T)=3 入栈4 02 #T +i*i# r2: ET 归约,GOTO(0,E)=1 入栈5 01 #E +i*i# ACTION1,+=S6,状态 6 入栈6 016 #E+ i*i# ACTION6,i=S5,状态 5 入栈7 0165 #E+i *i# r6: F i 归约,GOTO(6,F)=3 入栈8 0163 #E+F *i# r4: TF 归约,GOTO(6,T)=9 入栈9 0169 #E+T *i# ACTION9,*=S7,状态 7 入栈10 01697 #E+T* i# ACTION7,i=S5,状态 5 入栈11 016975 #E+T*i # r6:Fi 归约,GOTO(7,F)=10 入栈12 0169710 #E+T*F # r3: TT*F 归约,GOTO(6,T)=9 入栈13 0169 #E+T # r1:EE+T,GOTO(0,E)=1 入栈14 01 #E # Acc：分析成功4、输入符号串为非法符号串(或者为合法符号串)算术表达式文法的 LR 分析表ACTION GOTO状态 i + * ( ) # E T F0 S5 S4 1 2 31 S6 acc2 r2 S7 r2 r23 r4 r4 r4 r44 S5 S4 8 2 35 r6 r6 r6 r66 S5 S4 9 37 S5 S4 108 S6 S119 r1 S7 r1 r110 r3 r3 r3 r311 r5 r5 r5 r55、实验源程序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 int staStack =new int50; /状态分析栈private char symStack =new char50; /符号分析栈private booleanVNE; /非终结符与空串的关系表private int F_index =0; /产生式数组指针private int staStack_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 Vector State =new Vector(); /项目集 / jve:decl-index=0:private int Action; /Action动作数组private int Goto; /Goto动作数组private StringBuffer bridge1; /描述项目集之间的转换关系，在createLR1()中初始化private int bridge2;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 getJCont