编译原理课程设计--LR(1)分析和语义分析.doc

22 编译原理课程设计课程设计说明书 课程名称:编译原理课程设计题目: LR(1)分析和语义分析 院 系： 理学院 专业班级：信息与计算科学11-2班 学 号： 2011304985 2014年 6 月 26 日 编译原理课程设计课程设计（论文）任务书学 号2011304985学生姓名高健专业（班级）信计11-2 设计题目 LR(1)分析和语义分析设计技术参数 jdk 1.6开发工具：Myeclipse 10.0设计要求对某一文法进行LR(1)分析和语义分析工作量 文档不少于12页，参考文献不少于10个工作计划6月16-17日了解LR分析的原理和过程，选定一个要分析的文法6月18-19日构造项目集规范族利用项目集规范族和转移函数构造LR(1)分析表6月20-21日学习语义分析，并对选定文法赋予语义规则6月22-23日编写JAVA代码实现对文法的LR(1)分析和语义分析6月24-25日完成文档写作包括实现原理，程序流程图和类的说明6月26日提交课程设计参考资料1David A.Watt.Programming Language Syntax and SemantiesM.prentice Hall,1911.2赵克佳，杨灿群，罗红兵.多语种多平台编译系统剖析M.工业出版社1997.3陈火旺，钱家骅，孙永强，程序设计语言编译原理M，国学工业出版社4李赣生，王华民. 编译程序原理和技术M.清华大学出版社，1997.5金成植，编译程序构造原理和实现技术M.高等教育出版社，2000.6杜淑敏，王永宁.编译程序设计原理M.北京大学出版社，1986.7Jim Holmes.Compiler ConstructionM.Prentice Hall,1995.8Bertrand Meyer.Reusable SoftwareM.Prentice Hall,1994.9Andrew W.Appel.Modern Compiler DesignM.Cambridge University Press,1998.10陈意云.编译原理和技术M.中国科学技术大学出版社,1997.指导教师签字 教研室主任签字 年 月 日 3 编译原理课程设计目录1绪论12概述12.1设计背景12.2设计目的12.3软件定义22.4开发环境23项目设计报告33.1程序流图33.2实现原理43.2.1 LR分析概述43.2.2 LR（1）项目集规范族的构造53.2.3 LR（1）分析表的构造63.3类的说明64项目测试报告64.1测试的目的64.2项目集规范族和LR（1）分析表74.3语义规则84.4运行界面84.5相关代码105心得体会21参考文献2222 编译原理课程设计1绪论 编译原理是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。大家通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。2概述2.1设计背景 随着科学技术的不断提高，计算机科学日渐成熟，其强大的功能已为人们熟知，它已进入人类社会的各个领域并发挥着越来越重要的作用。作为计算机应用的一部分，使用计算机对LR(1)文法判断与预测分析器的构造系统，具有比手工运算、构造所无法比拟的优点。例如：查找迅速、查找方便、准确性高等。这些优点能够极大地提高判定LR(1)文法的效率，也是我们此次课程设计的目的。因此，开发这样的一套LR(1)文法判定与预测分析器的构造软件是很有必要的。 编译原理是大学计算机专业的必修课程，而词法分析作为其中的一部分占据着比较重要的地位。词法分析是编译原理的第一阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。 通关本次课程设计，我们对编译原理的理解就不止停留在课本上，而是知道怎样把编译原理应用到实际的编译程序设计的实践中。对我们今后的学习和工作都是至关重要的。2.2设计目的因为LR(0)分析过程中不需要向右查看输入符号，因而它可以对文法的限制较大，对绝大多数的高级语言的语法分析器是不能适用的，所以，要分析绝大多数的高级语言编译程序的需要，采用向后查看一个输入符号的方法，即LR(1)的方法。2.3软件定义(1) 对任意给定的上下文无关文法，构造其LR(1)项目集规范族，并且在此基础上再利用转移函数进一步构造其LR(1)分析表。(2) 给定任意字符串判定是否是该文法的句子，并实现语义分析。2.4开发环境硬件：一台Intel Pentium4 以上的计算机软件：Windows 操作系统，Myeclipse 10.0编程语言：Java 3项目设计报告3.1程序流图否否是否是是0，#分别入状态栈和符号栈置ip指向w#的第一个符号令s是状态栈栈顶，a是ip所指向的符号actions，a=Sactions,a=reduce A-s把a和s分别推入符号栈和状态栈；使ip前进到下一个字符分别从栈顶弹出|个符号，令s是当前栈顶状态，把a和gotos,A先后推入栈中，输出产生式A-ActionA,a=accept结束出错处理 图3-1 LR(1)驱动程序流程图否非空受S中每个项目I 和文法符号XgotoI,X在C中 gotoI,X加入到项目集是否还有项目是 图3-2 LR(1)项目集构造3.2实现原理3.2.1 LR分析概述一个LR分析器由3部分组成：总控程序也称为驱动程序。对所有的LR分析器总控程序相同。 分析表或分析函数。它包括“动作”和“状态转换”两部分，都是用二维数组来表示。ACTIONs，a规定了当前状态s面临输入a应该采取的动作，GOTOs，X规定了状态s面对文法符号X（终结符或非终结符）时下一状态是什么。GOTOs，X定义了一个以文法符号为字母表的DFA。 分析栈。包括文法符号栈和相应的状态栈，它们均是先进后出栈。 a1a2.aian#LR分析程序输出sm Xms1 X0s0 # action goto goto分析表栈输入串 图3-3 LR分析器工作过程示意图3.2.2 LR（1）项目集规范族的构造当LR(0)项目中存在移近-归约冲突和归约-归约冲突时，可用SLR(1)方法解决动作冲突，但仍然存在多余归约，LR(1)恰好是解决SLR(1)方法在某些情况下存在的无效归约问题。LR(1)项目形式：A，a1a2ak 移进或待归约项目（），a1a2ak不起作用。归约项目A，a1a2ak，仅当前输入符号串开始的前k个符号是a1a2ak时，才能用A进行归约。a1a2ak称向前搜索符号串。 以SS,#属于初始项目集中，把“#”作为向前搜索符，表示活前缀是（若是有关S产生式的某一右部）要归约为S时必须面临“#”才行。对初始项目SS,#求闭包后再用转换函数逐步求精求出整个文法的LR(1)项目集族。具体构造步骤如下：LR(1)项目集的闭包：设I是G的一个LR(1)项目集，closure(I)是从I出发用下面三个规则构造的项目集：每一个I中的项目都属于closure(I)若项目AB，a属于closure(I) 且 BP，则对任何bFIRST(a)，把原来不属于closure(I)中的项目B，b加进closure(I)中重复执行(2)直到closure(I)不再增大为止转移函数GO(I，X)令I是一个项目集，X是一个文法符号，函数GO(I，X)定义为：GO(I，X) = CLOSURE(J)其中：J=任何形如AX，a的项目|AX，aIS的LR(1)项目集族C的构造算法BEGIN I0： C = closure(SS，#) FOR C中的每个项目集I和G的每个符号X DO IF GO(I，X)非空且不属于C，THEN把GO(I，X)加入C中 UNTIL C不再增大END 3.2.3 LR（1）分析表的构造若项目Aa，b属于Ik且GO（Ik，a）=Ij，a为终结符，则置ACTIONk，a为“把（j，a）移进栈”，记为“sj”若项目A，a属于Ik，置ACTIONk，a为“用产生式A进行归约”，记为“rj”若项目SS，#属于Ik，则置ACTIONk，#为“接受”，记为“acc”若GO（Ik，A）Ij，则置GOTOk，A = j将空白格均置为“报错标志” 3.3类的说明本程序共有五个类：Main.java 是主类，只包含主界面的标题栏。MainView 显示主界面内容，提示输入字符串并进行LR(1)分析，如果输入格式不符合会提示相应信息。OperateData.java 是操作类，对输入的字符串进行LR(1)，提示分析成功或失败信息。Tools.java 是对栈进行处理的类。AnalyseResult.java 是分析字符串显示分析结果的类，对界面进行了布局。4项目测试报告4.1测试的目的在完成了程序的编写工作后，接下来将进行数据测试，这里说的软件，并不单单是指程序本身, 还包括其他方面。测试和开发一样，也是一项技术性很强的工作，有着很多的技巧。软件测试是软件质量保证的主要活动之一，因此，测试的质量直接影响软件的质量。依据前面所说的测试对象，我们把测试划分为几个方面来进行测试。测试目的：输入字符串进行LR(1)分析，判断是否为该文法的句子并进行语义分析。4.2项目集规范族和LR（1）分析表扩展文法 (0)EE (1)EE-T (2)ET (3)TT+F (4)TF (5)FiI0:EE,#EE-T,#/-ET,#/-TT+F,#/-/+TF,#/-/+Ti,#/-/+I1:EE,#EE-T,#/-I2:ET,#/-TT+F,#/-/+ I3:TF,#/-/+ I4:Fi,/-/+I5:EE-T,#/-TT+F,#/+/-TF,#/+-Fi,#/+/-I7:EE-T,#/-TT+F,#/+/-I6:TT+F,#/-/+Fi,#/-/+I8:FT+F,#/-/+ E T+F + iTF iiF 图4-1 LR(1)项目集和转换函数 表4-1 LR(1)分析表 状态ACTION GOTO+i#ETF0S41231S5acc2r2S6r23r4r4r44r5r5r55S4736S487r1S6r18r3r3r3 4.3语义规则产生式 语义规则 (0)EE print E.VAL (1)EE-T E.VAL:=E.VAL-T.VAL (2)ET E.VAL:=T.VAL (3)TT+F T.VAL:=T.VAL+F.VAL (4)TF T.VAL:=F.VAL (5)Fi F.VAL:=i.LEXVAL 4.4运行界面 图4-2 输入字符串图4-3 分析结果图4-4 输入错误字符串 图4-5 显示错误信息4.5相关代码(1)OperateData.javapackage lr1.operate;import java.util.HashMap;import java.util.Map;import java.util.Stack;import java.util.Vector;import lr1.tool.TOOL;public class OperateData private MapString,Map wenfa;private String text;private Stack stateStack;/状态栈private Stack yuyiStack;/语义值栈private Stack signStack;/符号栈private Stack inputStack;/输入字符栈private String state;private String yuyi;private String sign;private String input;private Map wenfaMap;private Map amap;private MapString,Map analyTable;private String message;public String getMessage()return message;private void setMessage(String str)StringBuffer buffer=new StringBuffer();buffer.append(结果:n);buffer.append(str);message=buffer.toString(); public OperateData(String text) /空的构造方法 this.text=text; stateStack=new Stack(); stateStack.push(0); yuyiStack=new Stack(); yuyiStack.push(); signStack=new Stack(); signStack.push(#); inputStack=new Stack(); text=text.trim(); inputStack.push(#); inputStack.push(text.substring(text.length()-1); for(int i=text.length()-1;i=1;i-) inputStack.push(text.substring(i-1,i); wenfa=new HashMapString,Map(); analyTable=new HashMapString,Map(); Map wMap0=new HashMap(); wMap0.put(0,E); wMap0.put(S,E); Map wMap1=new HashMap(); wMap1.put(1,E); wMap1.put(E,E+T); Map wMap2=new HashMap(); wMap2.put(2,E); wMap2.put(E,T); Map wMap3=new HashMap(); wMap3.put(3,T); wMap3.put(T,T*F); Map wMap4=new HashMap(); wMap4.put(4,T); wMap4.put(T,F); Map wMap5=new HashMap(); wMap5.put(5,F); wMap5.put(F,i); wenfa.put(0,wMap0); wenfa.put(1,wMap1); wenfa.put(2,wMap2); wenfa.put(3,wMap3); wenfa.put(4,wMap4); wenfa.put(5,wMap5); Map amap0=new HashMap(); amap0.put(+,null); amap0.put(*,null); amap0.put(i,S4); amap0.put(#,null); amap0.put(E,1); amap0.put(T,2); amap0.put(F,3); Map amap1=new HashMap(); amap1.put(+,S5); amap1.put(*,null); amap1.put(i,null); amap1.put(#,acc); amap1.put(E,null); amap1.put(T,null); amap1.put(F,null); Map amap2=new HashMap(); amap2.put(+,r2); amap2.put(*,S6); amap2.put(i,null); amap2.put(#,r2); amap2.put(E,null); amap2.put(T,null); amap2.put(F,null); Map amap3=new HashMap(); amap3.put(+,r4); amap3.put(*,r4); amap3.put(i,null); amap3.put(#,r4); amap3.put(E,null); amap3.put(T,null); amap3.put(F,null); Map amap4=new HashMap(); amap4.put(+,r5); amap4.put(*,r5); amap4.put(i,null); amap4.put(#,r5); amap4.put(E,null); amap4.put(T,null); amap4.put(F,null); Map amap5=new HashMap(); amap5.put(+,null); amap5.put(*,null); amap5.put(i,S4); amap5.put(#,null); amap5.put(E,null); amap5.put(T,7); amap5.put(F,3); Map amap6=new HashMap(); amap6.put(+,null); amap6.put(*,null); amap6.put(i,S4); amap6.put(#,null); amap6.put(E,null); amap6.put(T,null); amap6.put(F,8); Map amap7=new HashMap(); amap7.put(+,r1); amap7.put(*,S6); amap7.put(i,null); amap7.put(#,r1); amap7.put(E,null); amap7.put(T,null); amap7.put(F,null); Map amap8=new HashMap(); amap8.put(+,r3); amap8.put(*,r3); amap8.put(i,null); amap8.put(#,r3); amap8.put(E,null); amap8.put(T,null); amap8.put(F,null); analyTable.put(0,amap0); analyTable.put(1,amap1); analyTable.put(2,amap2); analyTable.put(3,amap3); analyTable.put(4,amap4); analyTable.put(5,amap5); analyTable.put(6,amap6); analyTable.put(7,amap7); analyTable.put(8,amap8); public Vector getColumnData() /返回JTable的列数据 Vector columnNames=new Vector(); columnNames.add(步骤); columnNames.add(状态栈); columnNames.add(语义栈(值栈); columnNames.add(符号栈); columnNames.add(剩余输入串); columnNames.add(ACTION); columnNames.add(GOTO); return columnNames; public Vector getRowData() /返回JTable的列数据 Vector rowData=new Vector(); String NT=; /终结符或非终结符 String GOTO=; Vector vector; TOOL tools=new TOOL(); String wenfaleft=; String wenfaright=; int a=0; int b=0; for(int i=1;true;i+) vector=new Vector(); state=(String)stateStack.lastElement();/从状态栈中栈顶元素 amap=analyTable.get(state); input=(String)inputStack.lastElement();/获得输入串栈栈顶元素 if(input.matches(d) input=i; NT=(String)amap.get(input); if(NT=null) vector.add(i+); /步骤 vector.add(tools.getStackAll(stateStack);/状态栈 System.out.println(tools.getStackAll(stateStack); vector.add(tools.getStackAll(yuyiStack);/语义栈(值栈) vector.add(tools.getStackAll(signStack);/符号栈 vector.add(tools.getInputStackAll(inputStack);/剩余输入串 vector.add(失败); vector.add(); rowData.add(vector); setMessage(输入的字符串为:+text+ 语义分析失败 ！); break; if(NT.startsWith(S)/移进 vector.add(i+); /步骤 vector.add(tools.getStackAll(stateStack);/状态栈 vector.add(tools.getStackAll(yuyiStack);/语义栈(值栈) vector.add(tools.getStackAll(signStack);/符号栈 vector.add(tools.getInputStackAll(inputStack);/剩余输入串 vector.add(NT);/ACTION vector.add();/GOTO stateStack.push(NT.substring(1); String inputHead=(String)inputStack.pop(); yuyiStack.push(inputHead); signStack.push(inputHead); else if(NT.startsWith(r)/归约 vector.add(i+); /步骤 vector.add(tools.getStackAll(stateStack);/状态栈 vector.add(tools.getStackAll(yuyiStack);/语义栈(值栈) vector.add(tools.getStackAll(signStack);/符号栈 vector.add(tools.getInputStackAll(inputStack);/剩余输入串 vector.add(NT);/ACTION wenfaMap=wenfa.get(NT.substring(1); wenfaleft=wenfaMap.get(NT.substring(1); wenfaright=wenfaMap.get(wenfaleft); for(int j=1;j=wenfaright.length();j+) stateStack.pop(); state=(String)stateStack.lastElement(); amap=analyTable.get(state); GOTO=(String)amap.get(wenfaleft); if(GOTO=null) /如果GOTO=null，则输入串分析失败 System.out.println(GTO); setMessage(输入的字符串为:+text+ 语义分析失败 ！); break; vector.add(GOTO);/GOTO stateStack.push(GOTO); signStack.pop(); if(wenfaright.equals(E+T) a=Integer.parseInt(String)yuyiStack.pop(); yuyiStack.pop(); b=Integer.parseInt(String)yuyiStack.pop(); yuyiStack.push(String.valueOf(a+b); signStack.pop(); signStack.pop(); if(wenfaright.equals(T*F) a=Integer.parseInt(String)yuyiStack.pop(); yuyiStack.pop(); b=Integer.parseInt(String)yuyiStack.pop(); yuyiStack.push(String.valueOf(a*b); signStack.pop(); signStack.pop(); signStack.push(wenfaleft); else System.out.println(i); vector.add(i+); /步骤 vector.add(tools.getStackAll(stateStack);/状态栈 System.out.println(tools.getStackAll(stateStack); vector.add(tools.getStackAll(yuyiStack);/语义栈(值栈) vector.add(tools.getStackAll(signStack);/符号栈 vector.add(tools.getInputStackAll(inputStack);/剩余输入串 vector.add(acc); vector.add(); rowData.add(vector); setMessage(输入的字符串:+text+ 语义分析成功 ,语义值为+yuyiStack.lastElement(); break; rowData.add(vector); /for循环结束 return rowData; (2)MainView.javapackage lr1.view;import java.awt.BorderLayout;import java.awt.Color;import java.awt.Container;import java.awt.FlowLayout;import java.awt.Font;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt.event.FocusEvent;import java.awt.event.FocusListener;import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPanel;import javax.swing.JTextArea;import javax.swing.JTextField;import javax.swing.border.BevelBorder;import javax.swing.border.CompoundBorder;import javax.swing.border.EmptyBorder;import javax.swing.border.LineBorder;public class MainView extends JFrame Container container; JButton button; JPanel panel; JPanel panelTip; JFrame frame=this; JLabel label; JLabel tip; JTextField jtf; public MainView(String title) super(title); container=this.getContentPane(); button=new JButton( 分析 ); button.addActionListener(new ActionListener()Overridepublic void actionPerformed(ActionEvent e) / TODO Auto-generated method stub String text=jtf.getText(); if(text=null|text.equals() tip.setText(输入的字符串不能为空,字符串格式如:a+b*c); else if(!text.matches(d+)*d) tip.setText(输入的字符串非法,字符串格式如:a+b*c); new Result(语义分析,text); ); jtf=new JTextField(请输入分析串,20); jtf.addFocusListener(new FocusListener()Overridepublic void focusGained(FocusEvent e) / TODO Auto-generated method stub jtf.setText();Overridepublic void focusLost(FocusEvent e) / TODO Auto-generated method stub ); contai