下载文档原格式
编译原理FRSTVT实验报告一. 实验要求算符优先文法是自低向上语法分析的一个很有效地方法.本次设计的主要要求是输入一个算符优先文法,然后将它的FIRSTVT集合求出来.二. 实现过程1.实验原理自下而上分析法就是从输入串开始,逐步进行”归约”,直至归约到文法的开始符号;或者说,从语法树的末端开始,步步向上”归约”,直到根结.这里提到的自上而下的分析方法是一种”移进-归约”法.这种方法的大意是,用一个寄存符号的先进后出栈,把符号一个一个地移进到栈里,当栈顶形成某个产生式的一个候选式时,即把栈顶这一部分替换成(规约成)该产生式的左部符号.要使用这种”移进-归约”的方法,必须要对文法做一些限制.这里就提到使用算符优先文法.这种算符优先分析是定义算符之间(确切地说,终结符之间)的某种优先关系,借助于这种优先关系寻找”可归约串”和进行归约.一个文法,如果它的人和一产生式的左部都不含两个相继(并列)的非终结符,即不含如下形式的产生式右部:…QR…则我们称这种文法为算法文法.假定G是一个不含ε-产生是的算服文法.对于任何一个终结符a,b,我么说:(1) a=b 当且仅当文法G中含有形如P->…ab…或P->…aQb…的产生式;(2) a<b 当且仅当文法G中含有形如P->…aR…的产生式,而且R=>b…或者R=>Qb…;(3) a>b 当且仅当文法G中含有形如P->…Rb…的产生式,而且R=>…a或者R=>…aQ.如果一个算符文法G中的任何终结符对(a,b)至少满足下述三种关系之一:a=b,a<b,a>b则称G这种文法是算符优先文法.通过检查G的每个产生式的每个候选式,可找到所有满足a=b的终结符对.为了找到所有满足关系<和>的终结符对,我们首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):FIRSTVT(P)={a|P=>a…或者P=>Qa…,a∈V T而Q∈V N}LASTVT(P)={a|P=>…a或者P=>…aQ,a∈V T而Q∈V N}有了这两个集合之后,就可以通过检查每个产生式的候选式确定满足关系<和>的所有终结符对.我们可以用下面两条规则来构造集合FIRSTVY(P):(1) 若有产生式P->a…或P->Qa…,则a∈FIRSTVT(P);(2) 若a∈FIRSTVT(Q),且有产生式P->Q…,则a∈FIRSTVT(P).因此只要按照这样的构造过程,最终就可以得到某个文法的所有非终结符的FIRSTVT和LASTVT集合.2.算法构造我将这个程序分为三个部分来处理.第一部分是从文本文件中将某个算符优先文法读入,并将它结构化,存入一个结构中.第二部分是对这个结构进行分析处理,得到它的FIRSTVT集合,存入一个数组中.最后一部分将这个数组的数组的内容输出.第一部分可现将算符文法存入名为test的文本文件中,然后通过一个函数去逐行分析这个文本,提取出所有的终结符,非终结符,产生式左边和右边等等有用信息(具体的文本格式后面有说明),并将这些数据存入相应的数据结构中.我是分别使用一个结构体数组存放每个产生式的左边,结构体数组的每项右生成一个链表来存放产生式的右边.再用两个链表存放所有的终结符和非终结符.例如某个算符优先文法G定义如下:(1)E->E+T|T(2)T->T*F|F(3)F->P^F|P(4)P->(E)|i经过第一步,应该生成如下的数据结构:经过第一部分的数据结构化,第二部分就是对他进行分析了.这里采用书本上提到的一个利用STACK的方法.首先建立一个布尔数组F[P,a],使得F[P,a]为真的条件是,当且仅当a∈FIRSTVT(P).开始时,按上述的规则(1)对每个数组元素F[P,a]赋初值.我们用一个栈STACK,把所有初值为真的数组元素F[P,a]的符号对(P,a)全都放在STACK中.然后对STACK 施行如下运算.如果STACK不空,就将栈顶项逐出,计此项为(Q,a).对于每个形如P->Q…的产生式,若F[P,a]为假,则变其值为真且将(P,a)推进STACK栈.下面是这算法的程序: PROCEDURE INSERT(P,a);IF NOT F[P,a] THENBEGIN F[P,a]:=TRUE;把(P,a)下推入STACK栈END;下面是主程序:BEGINFOR 每个非终结符P和每个终结符a,DO F[P,a]:=FALSE;FOR 每个形如P->a…或者P->Qa…的产生式DOINSERT(P,a);WHILE STACK 非空 DOBEGIN把STACK的栈顶项,计为(Q,a),上托出去;FOR 每条形如P->Q…的产生式DOINSERT(P,a);END OF WHILE;END这个算法的工作结果得到一个二位数组F,从它可以得到任何非终结符P的FIRSTVT.当然最后一步即使将二位数组F格式化输出.3.程序流程这个只是主过程的流程图,具体的子过程的前面己经详细说明,这里就不再附属.4.具体实现本此设计的所有过程都是在Linux下的KDevelopment环境中完成的.并且将书上提到的算法结合自己的设计情况做了一些改造,得到最终结果.三.测试分析首先我要说明的就是test文本文件中关于定义算符优先文法的一些说明:(1) 产生式必须是一行一个;(2) 非终结符只能以从A-Z的字母代替,终结符以非A-Z的一个字符代替;(3) 产生式的”->”以”>”代替;(4) 每个候选式以|隔开;(5) 产生式候选式个数不限,但是产生式显示为10个(可以通过宏定义改掉这个值).根据这些规定,可以减少很多不必要的麻烦.上面提到的哪个文法就可以改写成这个的形式:E>E+T|TT>T*F|FF>P^F|PP>(E)|i然后通过终端的命令行可以看到最终的结果.下面是具体的test文件内容和结果:四.试验感受在这次设计的整个过程中,由于吸取了上次语法分析器设计中出现的问题的经验,因此在短时间内较为顺利的完成了实验的要求.并且通过这个试验,让我再次对语法分析的自下而上分析和算符有限文法有了进一步的了解.掌握了FRISTVT和LASTVT的构造方法以及进一步的语法分析的构成.而且我仍是采用Linux下编程,在编程的调试方法上有了很大的提高.这对以后的走Linux自由之路都是很好好处的.但是在此期间也出了一些问题.特别是我在做FRISTVT时,对它的存储数据结构定义的不是很好,使得在以后的分析中实现较为复杂,而且效率也不是很高.我想这些都是我需要重视的.特别是在开始动手之前,应该仔细分析试验的要求,多去查找资料,定制出详细的设计报告和对它进行可行性分析.等到所有的准备工作都做好了在开始动手编程,我想这样一定比盲目动手的效率要高的多.。
摘要：编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。
由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。
本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。
我们这次课程设计的主要任务是编程实现对给定文法的FIRST 集和FOLLOW集的求解。
通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。
同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。
关键词：编译原理；FIRST集；FOLLOW集目录1 课题综述 (1)1.1 课题来源 (1)1.2 课题意义 (1)1.3 预期目标 (1)1.4 面对的问题 (1)1.5 需解决的关键技术 (1)2 系统分析 (2)2.1 基础知识 (2)2.1.1 FIRST集定义 (2)2.1.2FIRST集求解算法.................................................................... 错误!未定义书签。
2.1.3FOLLOW集的定义 (4)2.1.4 FOLLOW集算法 (4)2.2 解决问题的基本思路 (4)2.3 总体方案 (4)3 系统设计 (5)3.1 算法实现 (5)3.2 流程图 (6)4 代码编写 (10)5 程序调试 (15)6 运行与测试 (15)1 课题综述1.1 课题来源文法：包含若干终结符，非终结符，由终结符与非终结符组成的产生式。
本次课程设计就是对产生式进行左递归分析，待无左递归现象后进行FIRST集与FOLLOW集的求解。
1.2 课题意义由文法产生的若干个句子有可能是合法的或者不合法的，也有可能产生歧义，所以要消除歧义先消除文法左递归，然后根据求得的FIRST集与FOLLOW 集构造分析表，分析给定句子的合法性。
1. 什么是firstvt集？firstvt集是文法分析中的一个重要概念，指的是文法中每个非终结符号的推导出的符号串中的第一个终结符号的集合。
在LL(1)文法的分析中，计算出每个非终结符号的firstvt集是非常关键的步骤。
2. 如何计算一个非终结符号的firstvt集？我们需要明确文法中终结符号和非终结符号的定义。
根据文法的推导规则和终结符号的定义，逐步推导出每个非终结符号的firstvt集。
具体的计算方法包括：- 对于每个终结符号，其firstvt集就是它本身。
- 对于每个非终结符号A，如果存在产生式A->α，其中α可以为空串或者以终结符号开始，那么将α的第一个终结符号加入A的firstvt 集。
- 重复以上步骤，直到所有的非终结符号的firstvt集都得到计算。
3. firstvt集的作用firstvt集的计算是文法分析中自顶向下分析方法的关键步骤之一。
它能够帮助我们判断一个文法是否是LL(1)文法，从而确定是否可以使用LL(1)分析方法对该文法进行分析。
在语法分析中，firstvt集还可以辅助我们进行推导和归约的过程。
1. 什么是lastvt集？lastvt集与firstvt集类似，也是文法中每个非终结符号的推导出的符号串中的最后一个终结符号的集合。
在LR分析中，计算出每个非终结符号的lastvt集同样是非常关键的步骤。
2. 如何计算一个非终结符号的lastvt集？同样地，我们需要明确文法中终结符号和非终结符号的定义。
根据LR分析的推导规则和终结符号的定义，逐步推导出每个非终结符号的lastvt集。
具体的计算方法与计算firstvt集类似：- 对于每个终结符号，其lastvt集就是它本身。
- 对于每个非终结符号A，如果存在产生式A->α，其中α可以为空串或者以终结符号结尾，那么将α的最后一个终结符号加入A的lastvt集。
- 重复以上步骤，直到所有的非终结符号的lastvt集都得到计算。
【题型】简答题1题干】现有文法G[S]：B→idt|ε请问aidtccb是句型还是句子，为什么？S→aAbA→BcA|B【答案】S ⇒aAb ⇒aBcAb ⇒aidtcAb ⇒aidtcBcAb ⇒aidtc εcAb ⇒ aidtccAb⇒aidtccBb ⇒aidtcc εb ⇒ aidtccb是句型，也是句子。
【题型】简答题2题干】设有文法G1[S]：<S>→<N><N>→<D>|<N><D><D→0|1|2|…|9试写出028的最左推导过程。
【答案】028的最左推导：<S>=><N>=><N><D>=><N><D><D>=><D><D><D>=>0<D><D>=>02<D>=>028。
3题型】填空题【题干】递归下降法不允许任一非终结符是直接_______________递归的。
【答案】左;4题型】填空题【题干】在使用高级语言编程时，首先可通过编译程序发现源程序的全部_______________错误和部分语义错误。
【答案】语法;5题型】填空题【题干】把汇编语言程序翻译成机器可执行的目标程序的工作是由_______________完成的。
【答案】汇编器;6题型】填空题【题干】语法分析器的输出是_______________。
【答案】语法单位;循环优化的三种重要技术包括删除归纳变量、代码外提和_______________。
【答案】强度消弱;8题干】写出表达式(a+b)/(a-b)-a(a+b*c)的三元式序列及四元式序列。
【答案】三元式：⑴.(+,a,b) ⑵.(-,a,b) ⑶.(/,⑴,⑵) ⑷.(*,b,c) ⑸.(+,a,⑷) ⑹.(-,⑶,⑸)四元式：⑴.(+,a,b,T1) ⑵.(-,a,b,T2) ⑶.(/,T1,T2,T3) ⑷.(*,b,c,T4) ⑸.(+,a,T4,T5) ⑹.(-,T3,T5,T6)9题干】什么是句子？什么是语言？【答案】(1)设G是一个给定的文法，S是文法的开始符号，如果S→x(其中x∈VT*),则称x是文法的一个句子。
课程测试试题（04A卷）I、命题院（部）：数学与计算机科学学院II、课程名称：编译原理III、测试学期：2006－2007 学年度第1 学期IV、测试对象：数计、国交学院计科专业2004 级1、2、国交班V、问卷页数（A4）：3 页VI、答卷页数（A4）：4 页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、填空题（共30分，30个空，每空1分）1、典型高级程序设计语言编译系统的工作过程一般分为六个阶段，即词法分析、语法分析、语义分析、中间代码生成、、目标代码生成。
编译阶段的两种组合方式是组合法和按遍组合法，这两种组合方式的主要参考因素都是的特征。
2、Chomsky将文法按其所表示语言的表达能力，由高往低分为四类：0型，1型，2型，3型文法。
其中，2型文法也称，它的所有规则α→β 都满足：α∈，β∈ ((V N∪V T) *且，仅当β= ε时例外。
3、现代编译系统多采用方法，即在语法分析过程中根据各个规则所相联的或所对应的语义子程序进行翻译的办法。
该方法使用为工具来说明程序设计语言的语义。
4、构造与NFA M等价的正规文法G的方法如下：（1）对转换函数f(A，a)=B或f(A，ε)=B，改成形如或的产生式；（2）对可识别终态Z，增加一个产生式：。
5、代码生成要考虑的主要问题：充分利用的问题、选择的问题、选择的问题。
6、设有穷自动机M=(K，∑，f，S，Z)，若当M为时，满足z0∈f(S，α)且z0∈Z，或当M为时，满足f(S，α)=P∈Z，则称符号串α∈∑*可被M所。
7、符号表中每一项对应一个多元组。
符号表项的组织可分为组织、组织、组织等。
8、对于A∈∀ＶN 定义A的后续符号集：FOLLOW(A)={a|S=*>uAβ，a∈ＶT，且a∈，u∈ＶT*，β∈Ｖ+;若，则#∈FOLLOW(A)。
第三章语法分析3.1 完成下列选择题：(1) 文法G：S→xSx|y所识别的语言是。
a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*(2) 如果文法G是无二义的，则它的任何句子α。
a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。
a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。
b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用来刻画可归约串。
a. 直接短语b. 句柄c. 最左素短语d. 素短语(6) 若a为终结符，则A→α·aβ为项目。
a. 归约b. 移进c. 接受d. 待约(7) 若项目集Ik含有A→α· ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α· ”动作的一定是。
a. LALR文法b. LR(0)文法c. LR(1)文法d. SLR(1)文法(8) 同心集合并有可能产生新的冲突。
a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】(1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法G[N]为G[N]: N→D|NDD→0|1|2|3|4|5|6|7|8|9(1) G[N]的语言L(G[N])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。
【解答】(1) G[N]的语言L(G[N])是非负整数。
(2) 最左推导：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D685683.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。
编译原理与技术 - 习题集（含答案）《编译原理与技术》课程习题集西南科技大学成人、网络教育学院版权所有习题【说明】：本课程《编译原理与技术》（编号为03002）共有简答题,计算题1,计算题2,问答与作图题,计算题3,计算题4,计算题5等多种试题类型，其中，本习题集中有[简答题]等试题类型未进入。
一、计算题1 1. 已知NFA M1、将NFA M确定化为DFA M；2、求DFA M的正规式； 2. 已知正规式：a+b(b|ab)*1、求等价的NFA；2、求等价的DFA； 3. 已知正规式((ε｜a)b*)*1、求等价的NFA；2、将NFA确定化3、若所求DFA可最小化，则求其最小化DFA；若无，说明原因。
4. 写出字母表? = {a, b}上语言L = {w | w中a的个数是偶数}的正规式，并画出接受该语言的最简DFA。
5. 有文法 G[S] ：第 1 页共 26 页S → aC | aA A → aC C → bC |b1、求等价的NFA；2、求等价的DFA；二、计算题2 6. 将文法G[S]：S→aA A→AS|Bc B→Bi|i1、消除左递归；2、证明该文法消除左递归后是LL（1）文法？3、给出相应的LL(1)分析表。
7. 已知文法G（S）：E→aTb|iE|i T→TE|E1、提公因子和消除左递归；2、计算每个非终结符的FIRST和FOLLOW；3、证明该文法是否为LL（1）文法？8. 已知文法G（S）为：E → E or T | T T → T andF | FF → not F | ( E ) | true | false 1、对文法消除左递归；第 2 页共 26 页2、计算消除左递归后的文法的每个非终结符的FIRST和FOLLOW；3、判断消除左递归后的文法是否是LL(1) 文法。
9. 已知文法G（D）为：D→int L| real L L→L,id | id1、提公因子和消除左递归；2、计算每个非终结符的FIRST和FOLLOW；3、证明该文法是否为LL（1）文法？10. 已给文法 G[S]：S → SaP | Sf | P P → qbP | q1、对文法提公因子和消除左递归，得到其LL(１)文法；2、对LL(１)文法计算每个非终结符的FIRST和FOLLOW； 3、给出LL(１)文法的 LL(１)分析表。
中南大学网络教育课程考试复习题及参考答案编译原理一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。
( )2.一个句型的直接短语是唯一的。
( )3.已经证明文法的二义性是可判定的。
( )4.每个基本块可用一个DAG表示。
( )5.每个过程的活动记录的体积在编译时可静态确定。
( )6.2型文法一定是3 型文法。
( )7.一个句型一定句子。
( )8.算符优先分析法每次都是对句柄进行归约。
( )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。
( )10.编译过程中，语法分析器的任务是分析单词是怎样构成的。
( )11.一个优先表一定存在相应的优先函数。
( )12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。
( )13.递归下降分析法是一种自下而上分析法。
( )14.并不是每个文法都能改写成 LL(1)文法。
( )15.每个基本块只有一个入口和一个出口。
( )16.一个 LL(1)文法一定是无二义的。
( )17.逆波兰法表示的表达试亦称前缀式。
( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。
( )19.正规文法产生的语言都可以用上下文无关文法来描述。
( )20.一个优先表一定存在相应的优先函数。
( )21.3型文法一定是 2型文法。
( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。
( )二、填空题：1.( )称为规范推导。
2.编译过程可分为（），（），（），（）和（）五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。
4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。
5.语法分析器的输入是（），其输出是（）。
6.扫描器的任务是从（）中识别出一个个（）。
7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。
8.一个过程相应的DISPLAY表的内容为（）。
课程设计(论文)任务书软件学院学院软件测试专业 4 班一、课程设计(论文)题目FIRSTVT集和LASTVT集生成算法模拟二、课程设计(论文)工作自2014 年 6 月16 日起至2014 年6 月21 日止。
三、课程设计(论文) 地点: 软件学院实训中心四、课程设计(论文)内容要求：1．本课程设计的目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时，强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识, 熟悉使用开发工具VC /JA V A/C#/.NET 。
2．课程设计的任务及要求1）课程设计任务：设计一个由正规文法生成FIRSTVT集和LASTVT集的算法动态模拟。
(算法参见教材)动态模拟算法的基本功能是：(1)输入一个文法G；(2) 输出由文法G构造FIRSTVT集的算法；(3) 输出FIRSTVT集；(4) 输出由文法G构造LASTVT集的算法；(5) 输出LASTVT集。
2）创新要求：用界面的形式来展现这个结果集，这样显得更加的美观。
3）课程设计论文编写要求（1）课程设计任务及要求（2）设计思路--工作原理、功能规划（3）详细设计---数据分析、算法思路、功能实现（含程序流程图、主要代码及注释）、界面等。
（4）运行调试与分析讨论---给出运行屏幕截图，分析运行结果，有何改进想法等。
（5）设计体会与小结---设计遇到的问题及解决办法，通过设计学到了哪些新知识，巩固了哪些知识，有哪些提高。
（6）报告按规定排版打印，要求装订平整，否则要求返工；（7）课设报告的装订顺序如下：封面---任务书---中文摘要---目录----正文---附录(代码及相关图片)（8）严禁抄袭，如有发现，按不及格处理。
4）课程设计评分标准：（1）学习态度：20分；（2）系统设计：20分；（3）编程调试：20分；（4）回答问题：20分；（5）论文撰写：20分。
5）参考文献：（1）张素琴，吕映芝. 编译原理[M]., 清华大学出版社（2）蒋立源、康慕宁等，编译原理（第2版）[M]，西安：西北工业大学出版社6）课程设计进度安排1．准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料2．程序模块设计分析阶段（4学时）：程序总体设计、详细设计3．代码编写调试阶段（8学时）：程序模块代码编写、调试、测试4．撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名：2014 年 6 月21 日课程设计(论文)评审意见（1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）、差（）；评阅人：职称：副教授2014 年 6 月26 日目录绪论 (5)正文 (5)设计实现 (11)测试数据运行结果分析 (13)课程设计总结 (14)参考文献 (15)绪论随着计算机科学的飞速发展，形式语言与自动机理论和方法的研究也越来越受到人们的重视，但前者已经成为计算机科学的理论基础。
本课程设计主要研究自动机在编译方面的应用，并将讨论重点放在算符优先分析法上，并用此理论完成算数表达式的正确与否的判断。
根据算符优先分析算法，编写一个语法程序，程序具有通用性，即编制的语法缝隙程序能够适用于不同文法以及各种输入的单词串。
基本思想描述，语法分析前首先要对输入的文法和句子进行词法分析，去除多余的自负，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期准备。
算符优先分析算法的核心算法教材上已给出，因此所要做的事只是将其变成实现。
正文设计目的本课程设计的题目为“FirstVT集和LastVT集生成算法模拟”，它是算符优先分析算法中判断三种优先关系的关键。
算符优先分析算法是自底向上分析方法的一种。
所谓自底向上分析，也称移近——规约分析，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约。
重复这一过程直到规约到栈中只剩文法的开始符号则为分析成功，也就确认输入串是该文法的句子。
而算符优先分析算法的基本思想只是规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。
本课程设计的要求只是构造FirstVT集和LastVT集，在此基础上扩充建造算符优先关系表。
问题描述设计一个给定文法和对应的FIRSTVT和LASTVT集，能依据依据文法和FIRSTVT和LASTVT生成算符优先分析表。
可以动态模拟算法的基本功能，通过输入一个给定文法，及FIRSTVT和LASTVT集，本题目以文法G[E]为测试数据: 文法G[E]:E->TE’E’->+TE’|εT->FT’T’->*FT’|εF->(E)|i该文法有对应的FIRSTVT(E)={ +, * ,( ,i } LASTVT(E)={ +，*，),i } FIRSTVT(E')={ +} LASTVT(E')={ +，*，),i }FIRSTVT(T)={ * ,( ,i } LASTVT(T)={ *，),i }FIRSTVT(T')={ * } LASTVT(T')={ *，),i }FIRSTVT(F)={ ( ,i } LASTVT(F)={ ),i }通过算符优先关系表构造算法：给定文法中任何二个终结符对(a,b)之间的优先关系有三种优先关系计算为：①＝关系：可以直接查看产生式的右部，对如下形式的产生式：A→．．．ab．．．或A→．．．aBb．．．则有a=b成立。
②＜关系：求出每个非终结符B的FIRSTVT(B)，观察如下形式的产生式：A→．．．aB．．．对每一b∈FIRSTVT(B)，有a＜b成立。
③＞关系：计算每个非终结符B的LASTVT(B)，观察如下形式的产生式：A→．．．Bb．．．对每一a∈LASTVT(B)，有a＞b成立。
这样，对于给定的文法和对应的FIRSTVT和LASTVT集，通过二个终结符之间的优先关系表构造算法，可以得到算法优先分析表构造过程的过程和算符优先分析表生成算法。
所以，我们的重点应该放在算符优先分析表的生成算法上，解决了这一问题，也就可以得到我们想要的结果，算法优先分析表以及分析过程。
其中，对于FIRSTVT集和LASTVT集的表示可以采取集合的方式，同样也可以采用关系图法进行表示。
总体设计算符优先分析表的构造原理：通过检查文法G的每个产生式的每个候选式，可以首先找出满足a＝b的终结符对；为了找出所有满足关系＜和＞的终结符对，我们首先需要对文法G的每个非终结符P构造二个集合FIRSTVT（P）和LASTVT(P)。
1.FirstVT集的构造FIRSTVT(P）={a|P=>+a．．．或P=>+Qa．．．，a∈VT而Q∈VN }若有产生式：P→a．．．或P→Qa．．．,则a∈FIRSTVT(P)；若a∈FIRSTVT(Q)，且有产生式P→Q．．．，则a∈FIRSTVT(P)。
stVT集的构造LASTVT(P)={ a|P=>+．．．a或P=>+．．．aQ，a∈VT而Q∈VN }若有产生式：U→．．．a或U→．．．aV, 则a∈LASTVT(U)；若a∈LASTVT(V)，且有产生式U→．．．V，则a∈LASTVT(U)。
当我们有了这二个集合之后，就可以通过检查每个产生式的候选式确定满足关系的“＜”和“＞”的所有终结符对。
我们假定有产生式的一个侯选式形为．．．aP．．．，那么，对任何b∈FIRSTVT(P），a＜b；假定有产生式的一个候选形为．．．Pb．．．，那么，对任何a∈LASTVT(P)，有a＞b。
3.构造算符优先关系表在我们有了每个非终结符P的FIRSTVT(P）和LASTVT(P)集合之后，就能够构造文法G的优先表。
详细设计首先介绍算符优先文法的几个重要性质：性质1：在算符文法中任何句型都不包含两个相邻的非终结符。
性质2：如果Aa（或者bA）出现在算符文法的句型S中，其中A是非终结符，b是终结符，则S中任何含此b的短语必含有A。
1.FirstVT集的构造，算法描述①：若有产生式A->a…或A->Ba…，则a属于FirstVT（A），其中A、B为非终结符，a为终结符。
②：若a属于FirstVT（B）且有产生式A->B…则有a属于FirstVT（A）。
为了计算方便，建立一个布尔数组F[m,n]（m为非终结字符的个数，n为终结字符的个数）和一个后进先出栈STACK。
将所有的非终结符排序，用iA表示非终结符A的序号，再将所有的终结符排序，用ia表示终结符a的序号。
算法的目的是要使数组的一个元素最终取值满足：F[iA,ja]的值为真，当且仅当a属于FirstVT（A）。
至此，显然所有的非终结符的FirstVT集已完全确定。
步骤如下：首先按规则①对每个数组元素附初值。
观察这些初值，若F[iA,ia]的值是真，则将（A，a）推入栈中，直至对所有数组的初值都按此处理完。
然后对栈做如下运算。
将栈顶项弹出，则令其变为真，且将（A，a）推进栈，如此重复直到栈弹空为止。
若表达式文法为：（0）E'→# E #（1）E→E + T（2）E→T（3）T→T*F（4）T→F（5）F→P↑F | P（6）P→(E)（7）P→i计算每个非终结符的FirstVT集和LastVT集得到如下结果：FIRSTVT(E') = { # }FIRSTVT(E) = {+，*，↑，（，i}FIRSTVT(T) = {*，↑，（，i}FIRSTVT(F) = {↑，（，i}FIRSTVT(P)={（，i}stVT集的构造，算法描述：用于构建输入文法的LastVT集①若有规则U::=…a或U::==…aV,则a属于LastVT（U）②若有规则U::=…V,且a属于LastVT（V）则a属于LastVT（U）设一个栈STACK，和一个布尔数组BProcedureInsert（U，a）IF NOT B[U,a] THENBEGINB[U,a]::=TRUE;把（U，a）推进STACK栈；END；BEGINFOR 每个非终结符号U和终结符号a DOB[U,a]:=FALSE;FOR 每个形如U::=…a或U::=…aV的规则DOINSERT(U,a);WHILE STACK栈非空DOBEGIN把STACK栈的栈顶弹出，记为（V,a）;FOR 没条形如U::=…V的规则DOINSERT(U,a);END OF WHILE;END;具体算法如下：BeginFor每个终结符P和终结符a Do F[P,a]=FALSE;For 每个形如P->…a或P->…aQ的产生式，Do insert （P，a）While Stack 非空DoBegin把Stack 的顶端，记为（Q，a），上托出去；For每条形如P->…Q的产生式Insert（P，a）End of while；END针对上述算法可得到每个非终结符的LastVT集如下：LASTVT(E') = { # }LASTVT(E) ＝{+，*，↑，），i}LASTVT(T) ＝{*，↑，），i}LASTVT(F) ＝{↑，），i}LA VSTVT(P)＝{），i}①算符优先分析流程图图1算符优先分析流程图。
