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

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

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、格式规范性、设计态度及考勤是否降等级：是（、否（:)评阅人:职称：教授 2010 年 6 月 28、课设题目

4、、概要设计三、详细设计457四、运行结果五、总结六、附录、课设题目1、问题描述设计一个给定文法和对应 FIRSTVT和LASTVT集，能依据依据文法和FIRSTVT和LASTVT生成算符优先分析表。(算法参 见教材)2、基本要求动态模拟算法的基本功能是:(1)输入一个给定文法，及 FIRSTVT和LASTVT集;(2)输出算符优先分析表生成算法;(3)输出算法优先分析表构造过程的过程;3、测试数据输入文法:E->TE 'E' ->+TE ' | £T->FT 'T' ->*FT ' | £F->(

5、E)|i二、概要设计用结构体数组存储多行正规式，用LIST控件显示算法，用CDC类依据进行算法进行作图。并实现算法与生成过程的关联。根据已知优先文法构造相应优先关系矩阵，并将文法的产生 式保存，设置符号栈S,算法步骤如下:1、将输入符号串a1a2a3.an#依次逐个存入符号栈S中,直到遇到栈顶符号ai的优先性 > 下一个待输入符号aj时为止。2、栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1<ak为止。3、由句柄ak.ai在文法的产生式中查找右部为ak.ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时 可断定输入串不是该文法的句子。重复这

6、三步，直到归约完输入符号串，栈中只剩文法的开始 符号为止。求出该文法的优先关系表，在程序中用2维数组表示，-1表示小于或者等于，大于为1，其它为0表示错误。在输入一串字符串以后进行按照文法步的进行规约,若ABb则a LASTVT(B),a>b我所进行的是直接规约到文法的符号而不是规约到 数据结构使用的是链表，用一个STRUCT来表示一个元素，其中 包含符号和下一个符号的指针。计算优先符关系,1)'关系 直接看产生式的右部，若出现了A fab 或 A f aBb,则 a=b2)' < 关系求出每个非终结符B 的 FIRSTVT(B)若AfaB，则b FIRSTVT(B

7、),a<b3)' > '关系求出每个非终结符B 的 LASTVT(B)构造分析表M 对每个产生式AT 1|I n执行，.对FIRST(A)中每个终结符a,把A - i加入到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

8、)= *,/,(,i LASTVT(E)= +,-,*,/,),i LASTVT(F)= ),i LASTVT(T)= *,/,),i < 关系+T 贝U有：+ < FIRSTVT(T)-T 贝U有：-< FIRSTVT(T)*F则有：* < FIRSTVT(F)IF则有：I < FIRSTVT(F)(E则有：(< FIRSTVT(E)关系E+则有:LASTVT(E) > +E-则有：LASTVT(E) > -T*则有：LASTVT(T) > *TI则有：LASTVT(T) > IE)则有：LASTVT(E) > )终结符之间的

9、优先关系是唯一的，该文法是算符优先文法。2、程序的功能描述:程序由文件读入字符串（以#结束），然后进行算符优先分析，分 析过程中如有错误，则终止程序并报告错误位置，最终向屏幕输 出移近规约过程。主程序流程图:功能模块:3、程序所调用的函数清单及其功能P rivate bool TestGrammar()/测试是否为算符优先文法/构造语法规则集合（去除“I”符号）p rivate void AddToGrammarRules(stri ng Left Part,stri ngRight Part)private void AddToVtV n(stri ngLeft Part, stri ng

10、Right Part)/构造终结符与非终结符p ublic stri ng RetJudgeme nt()/返回对于输入语法规则的判断/是FirstVtO函数和LastVtO函数所调用的一个过程，作用是入P rivate void In sert(char Vn, char Vt, bool, TempArr) p rivate stri ng FirstVt() /计算FIRSTVT集合 p rivate stri ng LastVt() /计算LASTVT集合 public stri ng RetFirstLastVt() /返回FIRSTVT集合与LASTVT集合 p rivate vo

11、id RetP reRelati on Table()/计算优先关系表 p ublic Stri ngCollectio n Draw PreRelati on Table()/返回优先关系表 p rivate stri ng TraceBack(stri ng s, int m, int n)分析过程所调用的归约函数p rivate bool An alysis Process(stn ng Inp utSe nten ce)/分析过程 p ublic Stri ngCollectio n RetA nalysis Process(stri ngInp utSe nten ce)/返回分析（

12、归约移进）过程/*构造函数，参数为规则数组，构造函数将规则分为两部分,分别存于 LeftPartRuleTemp和 RightPartRuleTemp中*/P ublic Grammar(Stri ng GrammarRules) foreach (Stri ng ruleTe mp in GrammarRules)if (!ruleTe mp .Co ntai ns("->") return;elseruleTem p.Re place("->",">"Stri ng te mp = ruleTe mp .S pl

13、it('>');Left PartRuleTe mp .Add(te mp 0);Right PartRuleTe mp .Add(te mp 1);/*测试是否为算符优先文法,若是返回true，否则返回false*/P rivate bool TestGrammar() foreach (Stri ng temp Rule in Right PartRuleTe mp)for (i nt i = 0; i <= temp Rule.Le ngth - 2; i+)if (te mp Rulei >= 'A' && temp R

14、ulei <='Z')'Z' && temp Rulei + 1 >= 'A' && temp Rulei + 1 <=return false;return true;/*构造语法规则集合（去除“I”符号）*/p rivate void AddToGrammarRules(stri ng Left Part,stri ngRight Part)Stri ng p artTe mp = Stri ng.E mpty;for(i nt i=0;i<=Right Part.Le ngth-1;i

15、+) char vt = Right Parti;if (vt != T)P artTe mp += vt.ToStri ng();elseRight PartRule.Add( partTem p);Left PartRule.Add(Left Part0.ToStri ng();p artTe mp = Stri ng.E mpty;if (i = (Right Part.Le ngth -1 )Right PartRule.Add( partTem p);Left PartRule.Add(Left Part0.ToStri ng();p artTe mp = Stri ng.E mpt

16、y;/*构造终结符集合和非终结符集合,输入的字符串应不包含1符号*/private void AddToVtV n( stri ng LeftPart, stri ng Right Part)if (!VN.Co ntain s(Left PartO)VN.Add(Left Part0);foreach (char vt in Right Part) if (vt < 'A' II vt > 'Z') && !VT.Co ntain s(vt)&& vt != T)VT.Add(vt);/*返回对于输入语法规则的判断*

17、/ p ublic stri ng RetJudgeme nt() stri ng RetStri ng = strin g.E mpty;if (TestGrammarO) RetStri ng +=" 这是一个算符优先文法！ rn"for (i nt i = 0; i <= LeftP artRuleTem p.Cou nt - 1; i+)AddToGrammarRules(Left PartRuleTe mp i.ToStri ng(),Right PartRuleTe mp i.ToStri ng();AddToVtV n(Left PartRuleTe m

18、p i.ToStri ng().Right PartRuleTe mp i.ToStri ng();RetStri ng +=" 非终结符为：rn"foreach (char vn in VN)RetStri ng += vn .ToStri ng();RetString += "rn终结符为：rn"foreach (char vt in VT)RetStri ng += vt.ToStri ng();elseRetStri ng +="这不是一个算符优先算法！"return RetStri ng;四、运行结果执行程序弹出算符优先分析

19、表生成的界面:叵冈蘑输人文法”FIESTVT 与LJtSIVT集合:输入或者读取文法谄辅人文法输入文法FIESTVT 与LASTVr集合:算符忧先关粟恚:打开已源代码l_Ujgrad&R6pcrt_Pilas 1 Backup我最近的空挡3黨面iTi4rAnily£&r J0 GrammarS 羽 Gt amm ar Analyzer.：-Gr amm 建AiiilyE&r回I £*iilencel_l 呂 StiitaiiceL_2 =lIpgraleLoe匸3簡我的电胞执行，运行出FIRSTVT集和LASTVT集并得出算符优先关系表B算符忧先分析

20、*生威模0®谊输入文法F工RSTTI 与LASTVT集合:；ETTFT-Hir 15T-FTr -MFT IGF->CE)|i以下対nasm集合: fIK5mCE)= + *( i 1 FIRSTVT CT)訂 * ( i riR5m(p)=( I 1 riRsrvT m # 输入女怯以下対LASTVT集合: U5TVTa)= + * ) i U5TVTC 口 * ) i Lr c) 1 #c< < <五、总结由于编译原理课学的并不好，开始看见题目不知该如何下手, 后面把课本复习了一下，才开始算符优先文法的设计。通过设计, 对算符优先文法有了更深入的了解，原来

21、并不理解算符优先文法 为什么会设计成那样，后面经过程序的逐步调试，也逐步理解算 符文法的设计原理。通过编写语法分析这样一个程序，让我对于 算符优先分析有了更加深刻和直观的了解，对于整个过程也变得 非常清晰，去除了当初学习过程中似是而非的理解。此次试验最终能够完成，程序能够运行且能实现预计功能, 但有些地方还有待改进，比如输出结果框应改变一下显示模式,以便能够对程序运行结果一目了然。通过此次课程设计实验，我加深了对算符优先文法的理解，巩固了编程技术和对C#的使用。通过这次学课设，我发现有很多东西，很多细节没注意，如经常漏大小写问题等很小的问题，真正自己动手做了才发现了自己 的理论知识是如此的不扎

22、实。有时候一个很小的问题卡一下就要 处理很久，细节方面会带来很大的问题等等。我深刻体会到这给 我带来的障碍。不过也因为通过这次的课程设计巩固了我的知识, 查漏补缺，巩固我已有的知识，把那些遗忘掉的知识再重新学习 一遍，使我学到很多，得到很多。在算符优先程序设计过程中，我觉得比较复杂，其中在优先 关系矩阵的构造时遇到了非常大的困难，由于最初对程序的总体 流程不是十分清晰，而且实验中因本人马虎将优先关系矩阵输入 错误，造成了设计与调试的困难。这个课程设计的思路我能掌握, 但要不参考任何资料完全靠自己编确有不小的难度。 在编程之前, 我参考了很多网上的一个程序和同学的程序，在吸收其精华的基 础上，自

23、己做了些改进，最终将程序调出来了。但经过自己的努 力，通过多次调试，最终构造出优先关系矩阵并调试成功。通过本次实验一定程度上提高了软件开发能力，对编译原理 这一门课程也有了比较深刻的了解。最后，由于所学知识不够全 面，实验在很多方面还有待完善，在以后的学习过程中，会掌握 更多知识，力求做到更好。六、附录参考文献1程序设计语言编译原理陈火旺等.国防工业出版社2编译原理 张素琴吕映芝蒋维杜戴桂兰.清华大学出版社3编译原理及编译程序构造高仲仪.北京航天航空大学出版社部分代码using System;using System.Collecti ons;using System.Collecti on

24、s.S pecialized;using System.Wi ndows.Forms;n ames pace GrammarA nalyzer class Grammar Stri ngCollection Left PartRuleTe mp = new Stri ngCollectio n();Strin gCollecti on Right PartRuleTe mp = new Stri ngCollectio n();Stri ngCollection LeftP artRule = new Stri ngCollectio n();Stri ngCollection Right P

25、artRule = new Strin gCollectio n();ArrayList VT = new ArrayList();ArrayList VN = new ArrayList();bool, FirstVtTable;bool, LastVtTable;char, Pr eRelati on Table;Stri ngCollecti on ProcessStr = new Strin gCollectio n();Stack stack = new Stack();p ublic Grammar(Str in g GrammarRules)/略p rivate bool Tes

26、tGrammar()/略p rivate void AddToGrammarRules(stri ng Left Part, stri ng Right Part)/略private void AddToVtV n(stri ng LeftP art, stri ng Right Part)/略p ublic stri ng RetJudgeme ntO/略p rivate void In sert(char Vn, char Vt, bool, TempArr) int VnNum = VN.I ndexOf(V n);int VtNum = VT.I ndexOf(Vt);if (!Tem

27、pArrV nNum, VtNum)TempArrV nNum, VtNum = true;stack. Push(V n. ToStri ngO + Vt.ToStri ng();private string FirstVt() / 计算FIRSTVT集合 string strFirst =" 以下为 FIRSTVT集合：rn"stack.Clear();FirstVtTable = new boolVN.Cou nt, VT.Cou nt;for (i nt i = 0; i <= Left PartRule.Cou nt - 1; i+)if (VT.Co nt

28、a in s(Right PartRuleiO)>= 2 &&In sert(Left PartRulei0, Right PartRulei0, FirstVtTable);else if(Right PartRulei.Le ngthVT.Co ntai ns(Right PartRulei1)In sert(Left PartRulei0, Right PartRulei1, FirstVtTable);while (stack.Cou nt >= 1) stri ng tempQa = stack .Pop( ).ToStri ng();stri ng te

29、mpQ = temp Qa0.ToStri ng();stri ng tempa = temp Qa1.ToStri ngO;for (i nt i = 0; i <= Left PartRule.Cou nt - 1; i+)if (Right PartRulei0.ToStr in g() = tempQ)In sert(Left PartRulei0, temp a0, FirstVtTable);for (i nt i = 0; i <= VN.Cou nt - 1; i+) strFirst += "FIRSTVT(" + VNi.ToStri ngO

30、 + ")="for (i nt j = 0; j <= VT.Cou nt - 1; j+) if (FirstVtTablei, j = true)strFirst += VTj.ToStri ngO + ""strFirst += "rn"return strFirst;p rivate stri ng LastVt()string strLast ="以下为 LASTVT 集合：rn"stack.ClearO;LastVtTable = new boolVN.Cou nt, VT.Cou nt;for

31、 (i nt i = 0; i <= Left PartRule.Cou nt - 1; i+)I nsert(Left PartRuleiO, temp a0, LastVtTable);j - 1)if (VT.Co ntai ns(Right PartRulei In sert(Left PartRulei0,Right PartRulei1,LastVtTable);else if(Right PartRulei.Le ngth>=&&VT.Co nta in s(Right PartRuleij - 2)In sert(Left PartRuleiO,Ri

32、ght PartRulei2,LastVtTable);while (stack.Cou nt >= 1) stri ng tempQa = stack .Pop( ).ToStri ng();stri ng tempQ = temp Qa0.ToStri ng();stri ng tempa = temp Qa1.ToStri ng();for (i nt i = 0; i <= Left PartRule.Cou nt - 1; i+) int k = Right PartRulei.Le ngth;if (Right PartRuleik - 1.ToStri ng() =

33、tempQ)for (i nt i = 0; i <= VN.Cou nt - 1; i+)strLast += "LASTVT(" + VNi.ToStri ng() + ")="for (i nt j = 0; j <= VT.Cou nt - 1; j+)H H. if (LastVtTablei, j = true)strLast += VT j.ToStri ng() +strLast += "rn"return strLast;/计算LASTVT集合public stri ng RetFirstLastVt()

34、 return FirstVt() + "rnrn" + LastVt();+ 1)P reRelatio nTableVT.I ndexOf(te mp Rulei),p rivate void RetPr eRelati on Table。P reRelatio nTable = new charVT.Cou nt, VT.Cou nt;foreach (stri ng temp Rule in Right PartRule) for (i nt i = 0; i <= temp Rule.Le ngth - 2; i+)if (VT.Contains(tempR

35、ulei)&& VT.Contains(tempRuleiVT.I ndexOf(te mp Rulei + 1)='='if (i<= temp Rule.Le ngth&&VT.Co ntain s(te mp Rulei)&&!VT.Co ntai ns(te mp Rulei1)&&VT.Co ntai ns(te mp Rulei + 2)P reRelatio nTableVT.I ndexOf(te mp Rulei),VT.I ndexOf(te mp Rulei + 2)='='if (VT.Co ntai ns(te mp Rulei) && !VT.Co ntai ns(te mp Rulei + 1)for (i nt j = 0; j <= VT.Cou nt - 1; j+)if (FirstVtTableVN.I ndexOf(te mp Rulei + 1), j=true)P reRelatio nTableVT.I ndexO