实验四---LR(1)分析法.doc

实验四 LR(1)分析法
实验学时：2
实验类型：验证
实验要求：必修
一、实验目的
构造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)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
u LR分析器由三个部分组成：

u 其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
u ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行动作有四种可能：
(1)移进：
action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。
(2)归约：
action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
(3)接受acc:
当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。
(4)报错:
当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。

四、实验要求
1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。
2、如果遇到错误的表达式，应输出错误提示信息。
3、程序输入/输出实例：
输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串
输出过程如下：
步骤 状态栈 符号栈 剩余输入串 动 作
1 0 # i+i*i# 移进 

i+i*i的LR分析过程
步骤
状态栈
符号栈
输入串
动作说明
1
0
#
i+i*i#
ACTION[0,i]=S5,状态5入栈
2
05
#i
+i*i#
r6: F→i归约,GOTO(0,F)=3入栈
3
03
#F
+i*i#
r4: T→F归约,GOTO(0,T)=3入栈
4
02
#T
+i*i#
r2: E→T归约,GOTO(0,E)=1入栈
5
01
#E
+i*i#
ACTION[1,+]=S6,状态6入栈
6
016
#E+
i*i#
ACTION[6,i]=S5,状态5入栈
7
0165
#E+i
*i#
r6: F→i归约,GOTO(6,F)=3入栈
8
0163
#E+F
*i#
r4: T→F归约,GOTO(6,T)=9入栈
9
0169
#E+T
*i#
ACTION[9,*]=S7,状态7入栈
10
01697
#E+T*
i#
ACTION[7,i]=S5,状态5入栈
11
016975
#E+T*i
#
r6:F→i归约,GOTO(7,F)=10入栈
12
0169710
#E+T*F
#
r3: T→T*F归约,GOTO(6,T)=9入栈
13
0169
#E+T
#
r1:E→E+T,GOTO(0,E)1入栈
14
01
#E
#
Acc：分析成功
4、输入符号串为非法符号串(或者为合法符号串)
算术表达式文法的LR分析表
状
态
ACTION
GOTO
i
+
*
(
)
#
E
T
F
0
S5

S4

1
2
3
1

S6

acc

2

r2
S7

r2
r2

3

r4
r4

r4
r4

4
S5

S4

8
2
3
5

r6
r6

r6
r6

6
S5

S4

9
3
7
S5

S4

10
8

S6

S11

9

r1
S7

r1
r1

10

r3
r3

r3
r3

11

r5
r5

r5
r5

五、实验源程序
import 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 LR1 extends JFrame {

private static final long serialVersionUID = 1L;

//*********************************
private char []VN =new char[50]; //非终结符集
private char []VT =new char[50]; //终结符集
private String []F =new String[50]; //产生式集
private StringBuffer []FirstVN; //非终结符的First集
private int []staStack =new int[50]; //状态分析栈
private char []symStack =new char[50]; //符号分析栈
private boolean[]VNE; //非终结符与空串的关系表
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,25"
private JPanel jContentPane_testFrame = null;
private JDialog jDialog_TG = null; // @jve:decl-index=0:visual-constraint="170,520"
private JPanel jContentPane_TG = null;

public LR1() {
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(c<'A'||c>'Z'){ //如果输入的不是大写字母，给予提示
if(c<='z'&&c>='a'){
JOptionPane.showMessageDialog(LR1.this,"产生式左端非法！"+
"自动将其转换成大写字母");
jTextField.setText(jTextField.getText().toUpperCase());
}else
jTextField.setText("");
}else if(s.length()>1){
JOptionPane.showMessageDialog(LR1.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(LR1.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();
F[0]=new String("SBB");
F[1]=new String("BaB");
F[2]=new String("Bb");
for(int i=0;i<3;i++)
getElements(F[i]);
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();
F[0]=new String("EaA");
F[1]=new String("EbB");
F[2]=new String("AcA");
F[3]=new String("Ad");
F[4]=new String("BcB");
F[5]=new String("Bd");
for(int i=0;i<6;i++)
getElements(F[i]);
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_testedStringgetText().length()==0)
JOptionPane.showMessageDialog(jFrame_testFrame, "请输入待检测符号串");
else if(F[0]!=null){ //文法必须存在才可以进行以下操作
createAll();
analysisInPutString();
}else
JOptionPane.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()<1){
JOptionPane.showMessageDialog(LR1.this, "产生式左端不允许为空值！");
}else{
String s=jTextField.getText()+jTextField1.getText();
getElements(s); //提取所需信息
displayInformation();
clearTextField();
}
}
});
}
return jButton_ok;
}
private JButton getJButton_delete() {
if (jButton_delete == null) {
jButton_delete = new JButton();
//jButton_delete.setForeground(Color.red);
jButton_delete.setText("删除规则");
jButton_delete.setBounds(new Rectangle(153, 107, 90, 40));
jButton_delete.setToolTipText("删除一个产生式");
jButton_delete.addActionListener(new java.awt.event.ActionListener() {
public void actionPerformed(java.awt.event.ActionEvent e) {