编译基本知识教学规划报告算符优先分析表

_课程设计(论文)任务书软件学院 学院 软件工程 专业 07-1 班一、课程设计(论文)题目 算符优先分析表生成模拟二、课程设计(论文)工作自2010年6月20日起至2010年6月25感谢阅读日止。三、课程设计(论文)地点:四、课程设计(论文)内容要求：1．本课程设计的目的1、使学生增进对编译原理的认识，加强用程序设计语言实现编译算法能精品文档放心下载力。2、进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理精品文档放心下载解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的谢谢阅读程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、精品文档放心下载数据结构和编译原理的知识，熟悉使用开发工具VC6.0或JAVA。感谢阅读2．课程设计的任务及要求1）基本要求：_动态模拟算法的基本功能是：（1）输入一个给定文法，及FIRSTVT和LASTVT集；谢谢阅读（2）输出算符优先分析表生成算法；（3）输出算法优先分析表构造过程的过程。2）课程设计论文编写要求1）要按照书稿的规格打印誊写课设报告；2）报告分为封面、课程设计任务书（本文档）分析、总结和附录；谢谢阅读3）报告正文包括以下部分：①问题描述：题目要解决的问题是什么；②分析、设计、实现：解决问题的基本方法说明，包括主要算法思想，感谢阅读算法的流程图，程序中主要函数或过程的功能说明；④运行结果分析：分析程序的运行结果是否正确以及出现的问题；谢谢阅读⑤总结：遇到的主要问题是如何解决的、对设计和编码的回顾讨论和精品文档放心下载分析、进一步改进设想、经验和体会等；⑥附录，包括源程序清单和运行结果。学生签名：2009年6月25_日课程设计(论文)评审意见（1）编译器思想的正确性（20分）：优（）、良（）、中（）、一般（）、差（）；（2）程序实现的正确性（20分）：优（）、良（）、中（）、一般（）、差（）；（3）程序功能的完善程度（20分）：优（）、良（）、中（）、一般（）、差（）；（4）学生的态度（20分）：优（）、良（）、中（）、一般（）、差（）；（5）课程设计报告（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性、设计态度及考勤是否降等级：是（）、否（）评阅人：

职称：教授2010年6月28日_目录一、课设题目……………………4感谢阅读二、概要设计……………………5感谢阅读三、详细设计……………………7精品文档放心下载_四、运行结果……………………精品文档放心下载五、总结…………感谢阅读六、附录…………谢谢阅读_一、课设题目1、问题描述设计一个给定文法和对应FIRSTVT和LASTVT集，能依据精品文档放心下载依据文法和FIRSTVT和LASTVT生成算符优先分析表。(算法参谢谢阅读见教材)2、基本要求动态模拟算法的基本功能是：（1）输入一个给定文法，及FIRSTVT和LASTVT集；谢谢阅读（2）输出算符优先分析表生成算法；_（3）输出算法优先分析表构造过程的过程；3、测试数据输入文法：E->TE’E’->+TE’|εT->FT’T’->*FT’|εF->(E)|i_二、概要设计用结构体数组存储多行正规式，用LIST控件显示算法，用CDC类依据进行算法进行作图。并实现算法与生成过程的关联。感谢阅读根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S，算法步骤如下：精品文档放心下载1、将输入符号串a1a2a3...an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性>下一个待输入符号aj时为止。精品文档放心下载2、栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1<ak为止。精品文档放心下载3、由句柄ak...ai在文法的产生式中查找右部为ak...ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。精品文档放心下载重复这三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。精品文档放心下载_求出该文法的优先关系表，在程序中用2维数组表示，-1表示小于或者等于，大于为1，其它为0表示错误。谢谢阅读在输入一串字符串以后进行按照文法一步一步的进行规约，我所进行的是直接规约到文法的符号而不是规约到N。精品文档放心下载数据结构使用的是链表，用一个STRUCT来表示一个元素，其中包含符号和下一个符号的指针。精品文档放心下载计算优先符关系，‘=‘关系直接看产生式的右部，若出现了→…ab…或A→…aBb,则a=b2)’<‘关系求出每个非终结符B的FIRSTVT(B)A→…aB…,则b∈FIRSTVT(B),a<b3)’>’关系谢谢阅读求出每个非终结符B的LASTVT(B)A→…Bb…,则a∈LASTVT(B),a>b_构造分析表M①对每个产生式A→1|…|n执行②,③.②对FIRST(A)中每个终结符a,把A→i加入到M[A,a],其中为终结首符集中精品文档放心下载a的候选式i或唯一候选式.③若ε∈FIRST(A),则对任何属于FOLLOW(A)的终结符b,将A→ε加入M[A,b].④把所有无定义的M[A,a]标记为出错._三、详细设计1、优先关系矩阵的构造过程：（1）=关系由产生式F->(E)知‘（’=‘）’FIRSTVT集FIRSTVT(E)={+,-,*,/,(,i}感谢阅读FIRSTVT(F)={(,i}FIRSTVT(T)={*,/,(,i}LASTVT(E)={+,-,*,/,),i}LASTVT(F)={),i}LASTVT(T)={*,/,),i}<关系+T 则有：+<FIRSTVT(T)-T 则有：-<FIRSTVT(T)_*F 则有：*<FIRSTVT(F)/F 则有：/<FIRSTVT(F)(E 则有：(<FIRSTVT(E)(3)>关系E+ 则有：LASTVT(E)>+E- 则有：LASTVT(E)>-T* 则有：LASTVT(T)>*T/ 则有：LASTVT(T)>/则有：LASTVT(E)>)终结符之间的优先关系是唯一的，该文法是算符优先文法。感谢阅读2、程序的功能描述：程序由文件读入字符串（以#结束），然后进行算符优先分析，分析过程中如有错误，则终止程序并报告错误位置，最终向屏幕输出移近规约过程。谢谢阅读主程序流程图：__功能模块：3、程序所调用的函数清单及其功能privateboolTestGrammar()感谢阅读//测试是否为算符优先文法//构造语法规则集合（去除“|”符号）privatevoidAddToGrammarRules(stringLeftPart,stringRightPart)感谢阅读privatevoidAddToVtVn(stringLeftPart,stringRightPart)//构造终结符与非终结符谢谢阅读_publicstringRetJudgement()精品文档放心下载//返回对于输入语法规则的判断//是FirstVt()函数和LastVt()函数所调用的一个过程，作用是入感谢阅读栈privatevoidInsert(charVn,charVt,bool[,]TempArr)精品文档放心下载privatestringFirstVt()//计算FIRSTVT集合privatestringLastVt()//计算LASTVT集合publicstringRetFirstLastVt()精品文档放心下载//返回FIRSTVT集合与LASTVT集合谢谢阅读privatevoidRetPreRelationTable()感谢阅读//计算优先关系表publicStringCollectionDrawPreRelationTable()谢谢阅读//返回优先关系表privatestringTraceBack(strings,intm,intn)//分析过程所调用的归约函数精品文档放心下载_privateboolAnalysisProcess(stringInputSentence)谢谢阅读//分析过程publicStringCollectionRetAnalysisProcess(string谢谢阅读InputSentence)//返回分析（归约移进）过程/****构造函数，参数为规则数组，构造函数将规则分为两部分，精品文档放心下载分别存于LeftPartRuleTemp和RightPartRuleTemp中谢谢阅读****/publicGrammar(String[]GrammarRules)感谢阅读{ foreach(StringruleTempinGrammarRules)谢谢阅读{ if(!ruleTemp.Contains("->"))return;谢谢阅读elseruleTemp.Replace("->",">");谢谢阅读String[]temp=ruleTemp.Split('>');谢谢阅读LeftPartRuleTemp.Add(temp[0]);谢谢阅读RightPartRuleTemp.Add(temp[1]);精品文档放心下载}_}/****测试是否为算符优先文法，若是返回true，否则返回false****/privateboolTestGrammar()感谢阅读{ foreach(StringtempRuleinRightPartRuleTemp)谢谢阅读{ for(inti=0;i<=tempRule.Length-2;i++)感谢阅读{if(tempRule[i]>='A'&&tempRule[i]<='Z'&&tempRule[i+1]>='A'&&tempRule[i+1]<='Z')感谢阅读returnfalse;}}returntrue;}/****构造语法规则集合（去除“|”符号）****/精品文档放心下载privatevoidAddToGrammarRules(stringLeftPart,stringRightPart)谢谢阅读{ StringpartTemp=String.Empty;for(inti=0;i<=RightPart.Length-1;i++)谢谢阅读_{ charvt=RightPart[i];if(vt!='|')partTemp+=vt.ToString();感谢阅读else{ RightPartRule.Add(partTemp);谢谢阅读LeftPartRule.Add(LeftPart[0].ToString());partTemp=String.Empty;谢谢阅读}if(i==(RightPart.Length-1))精品文档放心下载{ RightPartRule.Add(partTemp);精品文档放心下载LeftPartRule.Add(LeftPart[0].ToString());partTemp=String.Empty;感谢阅读}}}/****构造终结符集合和非终结符集合，输入的字符串应不包含‘|’符号****/_privatevoidAddToVtVn(stringLeftPart,stringRightPart)感谢阅读{ if(!VN.Contains(LeftPart[0]))谢谢阅读VN.Add(LeftPart[0]);foreach(charvtinRightPart)感谢阅读{ if((vt<'A'||vt>'Z')&&!VT.Contains(vt)谢谢阅读&&vt!='|')VT.Add(vt);}}/****返回对于输入语法规则的判断****/publicstringRetJudgement()感谢阅读{ stringRetString=string.Empty;谢谢阅读if(TestGrammar()){RetString+="这是一个算符优先文法！\r\n";for(inti=0;i<=LeftPartRuleTemp.Count-1;i++)谢谢阅读{AddToGrammarRules(LeftPartRuleTemp[i].ToString(),RightPartRuleTemp[i].ToString());谢谢阅读_AddToVtVn(LeftPartRuleTemp[i].ToString(),谢谢阅读RightPartRuleTemp[i].ToString());谢谢阅读}RetString+="非终结符为：\r\n";foreach(charvninVN)谢谢阅读RetString+=vn.ToString();谢谢阅读RetString+="\r\n终结符为：\r\n";谢谢阅读foreach(charvtinVT)RetString+=vt.ToString();精品文档放心下载}elseRetString+="这不是一个算符优先算法！";returnRetString;谢谢阅读}_四、运行结果执行程序弹出算符优先分析表生成的界面：__输入或者读取文法_执行，运行出FIRSTVT集和LASTVT集并得出算符优先关系表感谢阅读_五、总结由于编译原理课学的并不好，开始看见题目不知该如何下手，后面把课本复习了一下，才开始算符优先文法的设计。通过设计，对算符优先文法有了更深入的了解，原来并不理解算符优先文法为什么会设计成那样，后面经过程序的逐步调试，也逐步理解算符文法的设计原理。通过编写语法分析这样一个程序，让我对于算符优先分析有了更加深刻和直观的了解，对于整个过程也变得非常清晰，去除了当初学习过程中似是而非的理解。感谢阅读此次试验最终能够完成，程序能够运行且能实现预计功能，但有些地方还有待改进，比如输出结果框应改变一下显示模式，以便能够对程序运行结果一目了然。通过此次课程设计实验，我加深了对算符优先文法的理解，巩固了编程技术和对C#的使用。精品文档放心下载通过这次学课设，我发现有很多东西，很多细节没注意，如经感谢阅读_常漏大小写问题等很小的问题，真正自己动手做了才发现了自己的理论知识是如此的不扎实。有时候一个很小的问题卡一下就要处理很久，细节方面会带来很大的问题等等。我深刻体会到这给我带来的障碍。不过也因为通过这次的课程设计巩固了我的知识，查漏补缺，巩固我已有的知识，把那些遗忘掉的知识再重新学习一遍，使我学到很多，得到很多。感谢阅读在算符优先程序设计过程中，我觉得比较复杂，其中在优先关系矩阵的构造时遇到了非常大的困难，由于最初对程序的总体流程不是十分清晰，而且实验中因本人马虎将优先关系矩阵输入错误，造成了设计与调试的困难。这个课程设计的思路我能掌握，但要不参考任何资料完全靠自己编确有不小的难度。在编程之前，我参考了很多网上的一个程序和同学的程序，在吸收其精华的基础上，自己做了些改进，最终将程序调出来了。但经过自己的努力，通过多次调试，最终构造出优先关系矩阵并调试成功。精品文档放心下载通过本次实验一定程度上提高了软件开发能力，对编译原理这一门课程也有了比较深刻的了解。最后，由于所学知识不够全面，实验在很多方面还有待完善，在以后的学习过程中，会掌握更多知识，力求做到更好。谢谢阅读_六、附录1、参考文献[1]《程序设计语言编译原理》陈火旺等.国防工业出版社谢谢阅读[2]《编译原理》张素琴吕映芝蒋维杜戴桂兰.清华大学出版社谢谢阅读[3]《编译原理及编译程序构造》高仲仪.北京航天航空大学出版社谢谢阅读2、部分代码usingSystem;usingSystem.Collections;usingSystem.Collections.Specialized;精品文档放心下载usingSystem.Windows.Forms;精品文档放心下载namespaceGrammarAnalyzer{ classGrammar{StringCollectionLeftPartRuleTemp=newStringCollection();感谢阅读StringCollectionRightPartRuleTemp=newStringCollection();精品文档放心下载_StringCollectionLeftPartRule=newStringCollection();谢谢阅读StringCollectionRightPartRule=newStringCollection();感谢阅读ArrayListVT=newArrayList();谢谢阅读ArrayListVN=newArrayList();谢谢阅读bool[,]FirstVtTable;bool[,]LastVtTable;char[,]PreRelationTable;StringCollectionProcessStr=newStringCollection();精品文档放心下载Stackstack=newStack();精品文档放心下载publicGrammar(String[]GrammarRules)精品文档放心下载//略privateboolTestGrammar()感谢阅读//略privatevoidAddToGrammarRules(stringLeftPart,stringRightPart)精品文档放心下载//略_privatevoidAddToVtVn(stringLeftPart,stringRightPart)精品文档放心下载//略publicstringRetJudgement()谢谢阅读//略privatevoidInsert(charVn,charVt,bool[,]TempArr)感谢阅读{intVnNum=VN.IndexOf(Vn);谢谢阅读intVtNum=VT.IndexOf(Vt);精品文档放心下载if(!TempArr[VnNum,VtNum])感谢阅读{TempArr[VnNum,VtNum]=true;stack.Push(Vn.ToString()+Vt.ToString());精品文档放心下载}}privatestringFirstVt() //计算FIRSTVT集合感谢阅读{stringstrFirst="以下为FIRSTVT集合：\r\n";stack.Clear();感谢阅读_FirstVtTable=newbool[VN.Count,VT.Count];精品文档放心下载for(inti=0;i<=LeftPartRule.Count-1;i++)精品文档放心下载{ if(VT.Contains(RightPartRule[i][0]))感谢阅读{Insert(LeftPartRule[i][0],RightPartRule[i][0],FirstVtTable);谢谢阅读}else if (RightPartRule[i].Length >= 2 &&精品文档放心下载VT.Contains(RightPartRule[i][1]))谢谢阅读{Insert(LeftPartRule[i][0],RightPartRule[i][1],FirstVtTable);感谢阅读}}while(stack.Count>=1){ stringtempQa=stack.Pop().ToString();谢谢阅读stringtempQ=tempQa[0].ToString();谢谢阅读stringtempa=tempQa[1].ToString();谢谢阅读for(inti=0;i<=LeftPartRule.Count-1;i++)感谢阅读{ if(RightPartRule[i][0].ToString()==tempQ)精品文档放心下载{Insert(LeftPartRule[i][0],tempa[0],FirstVtTable);感谢阅读}_}}for(inti=0;i<=VN.Count-1;i++)感谢阅读{ strFirst+="FIRSTVT("+VN[i].ToString()+")={";精品文档放心下载for(intj=0;j<=VT.Count-1;j++)感谢阅读{ if(FirstVtTable[i,j]==true)感谢阅读strFirst+=VT[j].ToString()+"";精品文档放心下载}strFirst+="}\r\n";}returnstrFirst;}privatestringLastVt(){ stringstrLast="以下为LASTVT集合：\r\n";感谢阅读stack.Clear();LastVtTable=newbool[VN.Count,VT.Count];谢谢阅读for(inti=0;i<=LeftPartRule.Count-1;i++)精品文档放心下载_{intj=RightPartRule[i].Length;if(VT.Contains(RightPartRule[i][j-1])){Insert(LeftPartRule[i][0],RightPartRule[i][j-1],LastVtTable);}elseif(RightPartRule[i].Length>=2&&VT.Contains(RightPartRule[i][j-2])){Insert(LeftPartRule[i][0],RightPartRule[i][j-2],LastVtTable);}}while(stack.Count>=1){ stringtempQa=stack.Pop().ToString();谢谢阅读stringtempQ=tempQa[0].ToString();感谢阅读stringtempa=tempQa[1].ToString();精品文档放心下载for(inti=0;i<=LeftPartRule.Count-1;i++)感谢阅读{ intk=RightPartRule[i].Length;感谢阅读if(RightPartRule[i][k-1].ToString()==tempQ)谢谢阅读_{Insert(LeftPartRule[i][0],tempa[0],LastVtTable);精品文档放心下载}}}for(inti=0;i<=VN.Count-1;i++)精品文档放心下载{strLast+="LASTVT("+VN[i].ToString()+")={";感谢阅读for(intj=0;j<=VT.Count-1;j++)谢谢阅读{ if(LastVtTable[i,j]==true)谢谢阅读strLast+=VT[j].ToString()+"";感谢阅读}strLast+="}\r\n";}returnstrLast;} //计算LASTVT集合publicstringRetFirstLastVt()谢谢阅读{ returnFirstVt()+"\r\n\r\n"+LastVt();谢谢阅读_}privatevoidRetPreRelationTable()精品文档放心下载{ PreRelationTable=newchar[VT.Count,VT.Count];谢谢阅读foreach(stringtempRuleinRightPartRule)谢谢阅读{ for(inti=0;i<=tempRule.Length-2;i++)感谢阅读{if(VT.Contains(tempRule[i])&&VT.Contains(tempRule[i谢谢阅读+1])){ PreRelationTable[VT.IndexOf(tempRule[i]),精品文档放心下载VT.IndexOf(tempRule[i+1])]='=';谢谢阅读}if (i <= tempRule.Length - 3 &&感谢阅读VT.Contains(tempRule[i]) && !VT.Contains(tempRule[i + 1]) &&谢谢阅读VT.Contains((tempRule[i+2])))感谢阅读{PreRelationTable[VT.IndexOf(tempRule[i]),精品文档放心下载VT.IndexOf(tempRule[i+2])]='=';精品文档放心下载}if(VT.Contains(tempRule[i])&&!VT.Contains(tempRule[i+1]))谢谢阅读{ for(intj=0;j<=VT.Count-1;j++)精品文档放心下载_{ if(FirstVtTable[VN.IndexOf(tempRule[i+1]),j]感