实验三 LR1分析法 JAVA.docx
《实验三 LR1分析法 JAVA.docx》由会员分享，可在线阅读，更多相关《实验三 LR1分析法 JAVA.docx（40页珍藏版）》请在冰点文库上搜索。
实验三 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）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
uLR分析器由三个部分组成：
u其中:
SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。
状态转换表用
GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
uACTION[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
5、实验源程序
LR.java
importjavax.swing.*;importjava.awt.Dimension;importjavax.swing.JButton;importjava.awt.Rectangle;importjava.util.Vector;
importjavax.swing.JTextArea;importjavax.swing.JTextField;importjavax.swing.JLabel;importjavax.swing.JMenuBar;importjavax.swing.JMenu;importjavax.swing.JMenuItem;importjavax.swing.JScrollPane;importjava.awt.BorderLayout;
importjavax.swing.JDialog;
publicclassLRextendsJFrame{
privatestaticfinallongserialVersionUID=1L;
//*********************************
privatechar[]VN =newchar[50]; //非终结符集privatechar[]VT =newchar[50]; //终结符集privateString[]F =newString[50];//产生式集
privateStringBuffer[]FirstVN; //非终结符的First集privateint []staStack =newint[50]; //状态分析栈privatechar[]symStack =newchar[50]; //符号分析栈
privateboolean[]VNE; //非终结符与空串的关系
表
privateint F_index =0; //产生式数组指针
privateint staStack_index=0; //状态栈指针
privateint symStack_index=0; //符号栈指针privateint ERROR =Integer.MAX_VALUE;//出错标志privatechar emp ='ε'; //空串
privateStringerror ="x"; //分析表显示的出错标志
// @jve:
decl-index=0:
privateStringacc ="acc"; //分析表显示的分析成功标志
privateVector> State =newVector>（）; //项目集 // @jve:
decl-index=0:
privateint [][]Action; //Action动作数组
privateint [][]Goto; //Goto动作数组
privateStringBuffer []bridge1; //描述项目集之间的转换
关系，在createLR1（）中初始化
privateint [][]bridge2;
privateJPaneljContentPane=null;privateJTextAreajTextArea4=null;privateJTextAreajTextArea3=null;privateJTextAreajTextArea2=null;
privateJTextAreajTextArea_LR1States=null;privateJTextAreajTextArea_LR1AnalysisTable=null;privateJTextFieldjTextField=null;
privateJTextFieldjTextField1=null;
privateJTextFieldjTextField_testedString=null;privateJLabeljLabel=null;
privateJLabeljLabel1=null;
privateJLabeljLabel_LR1States=null;privateJLabeljLabel_inputString=null;privateJButtonjButton_test=null;privateJButtonjButton_ok=null;privateJButtonjButton_delete=null;privateJButtonjButton_clearall=null;privateJButtonjButton_testPanel=null;privateJMenuBarjJMenuBar=null;privateJMenujMenu1=null;
privateJMenuItemjMenuItem1=null;privateJMenuItemjMenuItem2=null;
privateJScrollPanejScrollPane_LR1States=null;privateJScrollPanejScrollPane_LR1AnalysisTable=null;privateJScrollPanejScrollPane2=null;
privateJScrollPanejScrollPane3=null;privateJScrollPanejScrollPane4=null;privateJPaneljPanel=null;
privateJPaneljPanel1=null;
privateJLabeljLabel_LR1AnalysisTable=null;privateJButtonjButton_fresh=null;
privateJButtonjButton_TransFunGraph=null;
private JFrame jFrame_testFrame = null; // @jve:
decl-index=0:
visual-constraint="531,25"
privateJPaneljContentPane_testFrame=null;
private JDialog jDialog_TG = null; // @jve:
decl-index=0:
visual-constraint="170,520"
privateJPaneljContentPane_TG=null;
publicLR（）{
super（）;
initialize（）;
}
privatevoidinitialize（）{this.setSize（583,483）;this.setJMenuBar（getJJMenuBar（））;this.setContentPane（getJContentPane（））;
this.setTitle（"LR1语法分析"）;
this.setLocation（300,250）;this.setVisible（true）;
}
privateJPanelgetJContentPane（）{
if（jContentPane==null）{jContentPane=newJPanel（）;jContentPane.setLayout（null）;jContentPane.add（getJPanel（）,null）;
jContentPane.add（getJPanel1（）,null）;
}
returnjContentPane;
}
privateJPanelgetJPanel（）{
if（jPanel==null）{jPanel=newJPanel（）;jPanel.setLayout（null）;
jPanel.setBounds（newRectangle（0,0,210,430））;
//jPanel.setBackground（Color.green）;jPanel.add（getJScrollPane4（）,null）;jPanel.add（getJScrollPane3（）,null）;
}
returnjPanel;
}
privateJPanelgetJPanel1（）{
if（jPanel1==null）{jPanel1=newJPanel（）;jPanel1.setLayout（null）;
//jPanel1.setBackground（Color.green）;jPanel1.setBounds（newRectangle（210,0,368,430））;jLabel1=newJLabel（）;
//jLabel1.setForeground（Color.red）;jLabel1.setBounds（newRectangle（120,58,23,24））;jLabel1.setText（"-->"）;
jLabel=newJLabel（）;
//jLabel.setForeground（Color.red）;jLabel.setBounds（newRectangle（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）;
}
returnjPanel1;
}
privateJPanelgetJContentPane_testFrame（）{
if（jContentPane_testFrame==null）{jContentPane_testFrame=newJPanel（）;jContentPane_testFrame.setLayout（null）;jContentPane_testFrame.setBackground（null）;jContentPane_testFrame.add（getJScrollPane_LR1States（）,
null）;
jContentPane_testFrame.add（getJScrollPane_LR1AnalysisTable（）,
null）;
18））;
null）;
null）;
18））;
jLabel_inputString=newJLabel（）;
jLabel_inputString.setText（"请输入待测句子：
"）;jLabel_inputString.setBounds（newRectangle（29,25,108,
jContentPane_testFrame.add（jLabel_inputString,null）;jContentPane_testFrame.add（getJTextField_testedString（）,
jContentPane_testFrame.add（getJButton_test（）,null）;jContentPane_testFrame.add（getJButton_fresh（）,null）;jContentPane_testFrame.add（getJButton_TransFunGraph（）,
jLabel_LR1States=newJLabel（）;
jLabel_LR1States.setText（"LR1项目集"）;jLabel_LR1States.setBounds（new Rectangle（11, 65, 65,
jLabel_LR1States.addMouseListener（new
java.awt.event.MouseAdapter（）{
public void mouseReleased（java.awt.event.MouseEvent
e）{
jTextArea_LR1States.setText（""）;
//准备数据createAll（）;
//显示项目集displayLR1States（）;
}
e）{
{
}）;
/*public void mouseExited（java.awt.event.MouseEvent
jLabel_LR1States.setForeground（Color.black）;
}
publicvoidmouseEntered（java.awt.event.MouseEvente）
jLabel_LR1States.setForeground（Color.green）;
}*/
66,18））;
jContentPane_testFrame.add（jLabel_LR1States,null）;jLabel_LR1AnalysisTable=newJLabel（）;
jLabel_LR1AnalysisTable.setText（"LR1分析表"）;
jLabel_LR1AnalysisTable.setBounds（newRectangle（264,67,
jLabel_LR1AnalysisTable.addMouseListener（new
java.awt.event.MouseAdapter（）{
/*public void mouseExited（java.awt.event.MouseEvent
e）{
jLabel_LR1AnalysisTable.setForeground（Color.black）;
}
publicvoidmouseEntered（java.awt.event.MouseEvente）
{
jLabel_LR1AnalysisTable.setForeground（Color.green）;
}*/
public void mouseReleased（java.awt.event.MouseEvent
e）{
}
}）;
jTextArea_LR1AnalysisTable.setText（""）;createAll（）;
displayLR1AnalysisTable（）;
null）;
}
jContentPane_testFrame.add（jLabel_LR1AnalysisTable,
returnjContentPane_testFrame;
}
privateJDialoggetJDialog_TG（）{
if（jDialog_TG==null）{jDialog_TG=newJDialog（）;
jDialog_TG.setSize（newDimension（361,266））;
//jDialog_TG.setTitle（"LR1状态图"）;
//jDialog_TG.setBackground（Color.black）;jDialog_TG.setLocationRelativeTo（jFrame_testFrame）;jDialog_TG.setContentPane（getJContentPane_TG（））;
}
returnjDialog_TG;
}
privateJPanelgetJContentPane_TG（）{
if（jContentPane_TG==null）{
//jContentPane_TG=newTransformGraphPanel（）;jContentPane_TG.setLayout（newBorderLayout（））;
}
returnjContentPane_TG;
}
privateJTextFieldgetJTextField（）{
if（jTextField==null）{jTextField=newJTextField（）;
jTextField.setBounds（newRectangle（16,58,91,22））;jTextField.addKeyListener（new
java.awt.event.KeyAdapter（）{
publicvoidkeyReleased（java.awt.event.KeyEvente）{Strings=jTextField.getText（）;
charc=s.charAt（0）;
if（c<'A'||c>'Z'）{ //如果输入的不是大
写字母，给予提示
式左端非法！
"+
if（c<='z'&&c>='a'）{
JOptionPane.showMessageDialog（LR.this,"产生
"自动将其转换成大
升级会员 