编译原理课程设计报告 算符优先分析表

1、课程设计(论文)任务书 软件学院 学 院 软件工程 专 业 07-1 班 一、课程设计(论文)题目算符优先分析表生成模拟 二、课程设计(论文)工作自2010年6月20 日起至 2010 年 6月 25日止。三、课程设计(论文) 地点: 四、课程设计(论文)内容要求：1本课程设计的目的1、使学生增进对编译原理的认识，加强用程序设计语言实现编译算法能力。2、进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC6.0 或

2、JAVA。2课程设计的任务及要求1）基本要求：动态模拟算法的基本功能是：（1）输入一个给定文法，及FIRSTVT和LASTVT集；（2）输出算符优先分析表生成算法； （3）输出算法优先分析表构造过程的过程。2）课程设计论文编写要求1）要按照书稿的规格打印誊写课设报告；2）报告分为封面、课程设计任务书（本文档）分析、总结和附录；3）报告正文包括以下部分： 问题描述：题目要解决的问题是什么； 分析、设计、实现：解决问题的基本方法说明，包括主要算法思想，算法的流程图，程序中主要函数或过程的功能说明； 运行结果分析：分析程序的运行结果是否正确以及出现的问题； 总结：遇到的主要问题是如何解决的、对设计和

3、编码的回顾讨论和分析、进一步改进设想、经验和体会等； 附录，包括源程序清单和运行结果。学生签名： 2009 年6 月25 日课程设计(论文)评审意见（1）编译器思想的正确性（20分）：优（）、良（）、中（）、一般（）、差（）； （2）程序实现的正确性（20分）：优（）、良（）、中（）、一般（）、差（）； （3）程序功能的完善程度（20分）：优（）、良（）、中（）、一般（）、差（）；（4）学生的态度（20分）：优（）、良（）、中（）、一般（）、差（）；（5）课程设计报告（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人： 职称：

4、 教授 2010 年 6 月 28 日目 录1、 课设题目42、 概要设计53、 详细设计74、 运行结果5、 总结6、 附录1、 课设题目1、问题描述设计一个给定文法和对应FIRSTVT和LASTVT集，能依据依据文法和FIRSTVT和LASTVT生成算符优先分析表。(算法参见教材)2、基本要求动态模拟算法的基本功能是：（1）输入一个给定文法，及FIRSTVT和LASTVT集；（2）输出算符优先分析表生成算法；（3）输出算法优先分析表构造过程的过程；3、测试数据输入文法：E-TEE-+TE|T-FTT-*FT|F-(E)|i二、概要设计 用结构体数组存储多行正规式，用LIST控件显示算法，用

5、CDC类依据进行算法进行作图。并实现算法与生成过程的关联。 根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S，算法步骤如下： 1、将输入符号串a1a2a3.an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。 2、栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1ak为止。3、由句柄ak.ai在文法的产生式中查找右部为ak.ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。重复这三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。 求出该文法的优先关系表，在程序中用

6、2维数组表示，-1表示小于或者等于，大于为1，其它为0表示错误。 在输入一串字符串以后进行按照文法一步一步的进行规约，我所进行的是直接规约到文法的符号而不是规约到N。数据结构使用的是链表，用一个STRUCT来表示一个元素，其中包含符号和下一个符号的指针。计算优先符关系，1) =关系直接看产生式的右部，若出现了A ab或A aBb,则a=b2)关系求出每个非终结符B的FIRSTVT(B)若AaB,则bFIRSTVT(B),a关系求出每个非终结符B的LASTVT(B)若ABb,则aLASTVT(B),ab构造分析表M对每个产生式A 1| n执行,.对FIRST(A)中每个终结符a, 把A i加入到

7、MA,a,其中 为终结首符集中含a的候选式 i或唯一候选式.若FIRST(A), 则对任何属于FOLLOW(A)的终结符b,将A加入MA,b.把所有无定义的MA,a标记为出错.三、详细设计1、优先关系矩阵的构造过程：（1） = 关系由产生式 F-(E) 知 （=）FIRSTVT集 FIRSTVT(E)= +,-,*,/,(,i FIRSTVT(F)= (,i FIRSTVT(T)= *,/,(,i LASTVT(E)= +,-,*,/,),i LASTVT(F)= ),i LASTVT(T)= *,/,),i (2) 关系 +T 则有：+ FIRSTVT(T) -T 则有：- FIRSTVT(

8、T) *F 则有：* FIRSTVT(F) /F 则有：/ FIRSTVT(F) (E 则有：( 关系 E+ 则有： LASTVT(E) + E- 则有： LASTVT(E) - T* 则有： LASTVT(T) * T/ 则有： LASTVT(T) / E) 则有： LASTVT(E) )终结符之间的优先关系是唯一的，该文法是算符优先文法。2、程序的功能描述：程序由文件读入字符串（以#结束），然后进行算符优先分析，分析过程中如有错误，则终止程序并报告错误位置，最终向屏幕输出移近规约过程。主程序流程图：功能模块：3、程序所调用的函数清单及其功能private bool TestGrammar(

9、) /测试是否为算符优先文法/构造语法规则集合（去除“|”符号）private void AddToGrammarRules(string LeftPart, string RightPart) private void AddToVtVn(string LeftPart, string RightPart) /构造终结符与非终结符public string RetJudgement() /返回对于输入语法规则的判断/是FirstVt()函数和LastVt()函数所调用的一个过程，作用是入栈private void Insert(char Vn, char Vt, bool, TempArr)

10、private string FirstVt() /计算FIRSTVT集合private string LastVt() /计算LASTVT集合public string RetFirstLastVt() /返回FIRSTVT集合与LASTVT集合private void RetPreRelationTable() /计算优先关系表public StringCollection DrawPreRelationTable()/返回优先关系表private string TraceBack(string s, int m, int n) /分析过程所调用的归约函数private bool Anal

11、ysisProcess(string InputSentence)/分析过程public StringCollection RetAnalysisProcess(string InputSentence)/返回分析（归约移进）过程/*构造函数，参数为规则数组，构造函数将规则分为两部分， 分别存于LeftPartRuleTemp和RightPartRuleTemp中*/public Grammar(String GrammarRules) foreach (String ruleTemp in GrammarRules) if (!ruleTemp.Contains(-) return; els

12、e ruleTemp.Replace(-, ); String temp = ruleTemp.Split(); LeftPartRuleTemp.Add(temp0); RightPartRuleTemp.Add(temp1); /*测试是否为算符优先文法， 若是返回true，否则返回false*/private bool TestGrammar() foreach (String tempRule in RightPartRuleTemp) for (int i = 0; i = A & tempRulei = A & tempRulei + 1 = Z) return false; re

13、turn true; /*构造语法规则集合（去除“|”符号）*/private void AddToGrammarRules(string LeftPart, string RightPart) String partTemp = String.Empty; for(int i=0;i=RightPart.Length-1;i+) char vt = RightParti; if (vt != |) partTemp += vt.ToString(); else RightPartRule.Add(partTemp);LeftPartRule.Add(LeftPart0.ToString();

14、 partTemp = String.Empty; if (i = (RightPart.Length -1 ) RightPartRule.Add(partTemp); LeftPartRule.Add(LeftPart0.ToString(); partTemp = String.Empty; /*构造终结符集合和非终结符集合， 输入的字符串应不包含|符号*/private void AddToVtVn(string LeftPart, string RightPart) if (!VN.Contains(LeftPart0) VN.Add(LeftPart0); foreach (cha

15、r vt in RightPart) if (vt Z) & !VT.Contains(vt) & vt != |) VT.Add(vt); /*返回对于输入语法规则的判断*/public string RetJudgement() string RetString = string.Empty; if (TestGrammar() RetString += 这是一个算符优先文法！rn; for (int i = 0; i = LeftPartRuleTemp.Count - 1; i+) AddToGrammarRules(LeftPartRuleTempi.ToString(), Righ

16、tPartRuleTempi.ToString(); AddToVtVn(LeftPartRuleTempi.ToString(), RightPartRuleTempi.ToString(); RetString += 非终结符为：rn; foreach (char vn in VN) RetString += vn.ToString(); RetString += rn终结符为：rn; foreach (char vt in VT) RetString += vt.ToString(); else RetString += 这不是一个算符优先算法！; return RetString; 四

17、、运行结果执行程序弹出算符优先分析表生成的界面：输入或者读取文法执行，运行出FIRSTVT集和LASTVT集并得出算符优先关系表五、总结 由于编译原理课学的并不好，开始看见题目不知该如何下手，后面把课本复习了一下，才开始算符优先文法的设计。通过设计，对算符优先文法有了更深入的了解，原来并不理解算符优先文法为什么会设计成那样，后面经过程序的逐步调试，也逐步理解算符文法的设计原理。通过编写语法分析这样一个程序，让我对于算符优先分析有了更加深刻和直观的了解，对于整个过程也变得非常清晰，去除了当初学习过程中似是而非的理解。 此次试验最终能够完成，程序能够运行且能实现预计功能，但有些地方还有待改进，比如

18、输出结果框应改变一下显示模式，以便能够对程序运行结果一目了然。通过此次课程设计实验，我加深了对算符优先文法的理解，巩固了编程技术和对C#的使用。通过这次学课设，我发现有很多东西，很多细节没注意，如经常漏大小写问题等很小的问题，真正自己动手做了才发现了自己的理论知识是如此的不扎实。有时候一个很小的问题卡一下就要处理很久，细节方面会带来很大的问题等等。我深刻体会到这给我带来的障碍。不过也因为通过这次的课程设计巩固了我的知识，查漏补缺，巩固我已有的知识，把那些遗忘掉的知识再重新学习一遍，使我学到很多，得到很多。在算符优先程序设计过程中，我觉得比较复杂，其中在优先关系矩阵的构造时遇到了非常大的困难，由

19、于最初对程序的总体流程不是十分清晰，而且实验中因本人马虎将优先关系矩阵输入错误，造成了设计与调试的困难。这个课程设计的思路我能掌握，但要不参考任何资料完全靠自己编确有不小的难度。在编程之前，我参考了很多网上的一个程序和同学的程序，在吸收其精华的基础上，自己做了些改进，最终将程序调出来了。但经过自己的努力，通过多次调试，最终构造出优先关系矩阵并调试成功。通过本次实验一定程度上提高了软件开发能力，对编译原理这一门课程也有了比较深刻的了解。最后，由于所学知识不够全面，实验在很多方面还有待完善，在以后的学习过程中，会掌握更多知识，力求做到更好。六、附录1、参考文献1程序设计语言编译原理 陈火旺等. 国

20、防工业出版社 2编译原理 张素琴 吕映芝 蒋维杜 戴桂兰. 清华大学出版社3编译原理及编译程序构造 高仲仪. 北京航天航空大学出版社2、部分代码using System;using System.Collections;using System.Collections.Specialized;using System.Windows.Forms;namespace GrammarAnalyzer class Grammar StringCollection LeftPartRuleTemp = new StringCollection(); StringCollection RightPart

21、RuleTemp = new StringCollection(); StringCollection LeftPartRule = new StringCollection(); StringCollection RightPartRule = new StringCollection(); ArrayList VT = new ArrayList(); ArrayList VN = new ArrayList(); bool, FirstVtTable; bool, LastVtTable; char, PreRelationTable; StringCollection ProcessS

22、tr = new StringCollection(); Stack stack = new Stack(); public Grammar(String GrammarRules) /略 private bool TestGrammar() /略 private void AddToGrammarRules(string LeftPart, string RightPart) /略 private void AddToVtVn(string LeftPart, string RightPart) /略 public string RetJudgement() /略 private void

23、Insert(char Vn, char Vt, bool, TempArr) int VnNum = VN.IndexOf(Vn); int VtNum = VT.IndexOf(Vt); if (!TempArrVnNum, VtNum) TempArrVnNum, VtNum = true; stack.Push(Vn.ToString() + Vt.ToString(); private string FirstVt() /计算FIRSTVT集合 string strFirst = 以下为FIRSTVT集合：rn; stack.Clear(); FirstVtTable = new b

24、oolVN.Count, VT.Count; for (int i = 0; i = 2 & VT.Contains(RightPartRulei1) Insert(LeftPartRulei0, RightPartRulei1, FirstVtTable); while (stack.Count = 1) string tempQa = stack.Pop().ToString(); string tempQ = tempQa0.ToString(); string tempa = tempQa1.ToString(); for (int i = 0; i = LeftPartRule.Co

25、unt - 1; i+) if (RightPartRulei0.ToString() = tempQ) Insert(LeftPartRulei0, tempa0, FirstVtTable); for (int i = 0; i = VN.Count - 1; i+) strFirst += FIRSTVT( + VNi.ToString() + )= ; for (int j = 0; j = VT.Count - 1; j+) if (FirstVtTablei, j = true) strFirst += VTj.ToString() + ; strFirst += rn; retu

26、rn strFirst; private string LastVt() string strLast = 以下为LASTVT集合：rn; stack.Clear(); LastVtTable = new boolVN.Count, VT.Count; for (int i = 0; i = 2 & VT.Contains(RightPartRuleij - 2) Insert(LeftPartRulei0, RightPartRuleij - 2, LastVtTable); while (stack.Count = 1) string tempQa = stack.Pop().ToStri

27、ng(); string tempQ = tempQa0.ToString(); string tempa = tempQa1.ToString(); for (int i = 0; i = LeftPartRule.Count - 1; i+) int k = RightPartRulei.Length; if (RightPartRuleik - 1.ToString() = tempQ) Insert(LeftPartRulei0, tempa0, LastVtTable); for (int i = 0; i = VN.Count - 1; i+) strLast += LASTVT(

28、 + VNi.ToString() + )= ; for (int j = 0; j = VT.Count - 1; j+) if (LastVtTablei, j = true) strLast += VTj.ToString() + ; strLast += rn; return strLast; /计算LASTVT集合 public string RetFirstLastVt() return FirstVt() + rnrn + LastVt(); private void RetPreRelationTable() PreRelationTable = new charVT.Coun

29、t, VT.Count; foreach (string tempRule in RightPartRule) for (int i = 0; i = tempRule.Length - 2; i+) if (VT.Contains(tempRulei) & VT.Contains(tempRulei + 1) PreRelationTableVT.IndexOf(tempRulei), VT.IndexOf(tempRulei + 1) = =; if (i = tempRule.Length - 3 & VT.Contains(tempRulei) & !VT.Contains(tempRulei + 1) & VT.Contains(tempRulei + 2) PreRelationTableVT.IndexOf(tempRulei), VT.IndexOf(tempRulei + 2) = =; if (VT.Contains(tempRulei) & !VT.Contains(tempRulei + 1) for (int j = 0; j = VT.Cou