《期中考试PPT课件》由会员分享，可在线阅读，更多相关《期中考试PPT课件（18页珍藏版）》请在金锄头文库上搜索。
1、期期 中中 考考 试试西安邮电学院西安邮电学院 计算机学院计算机学院 联系方式：联系方式：amei_王春梅王春梅 讲讲师师编编 译译 原原 理理 期期 中中 考考 试试一、填空题（一、填空题（15分，每空分，每空1分）分）1.一个典型的编译系统包括一个典型的编译系统包括 和和 两部分。两部分。2.编译方式与解释方式的根本区别在于编译方式与解释方式的根本区别在于 。3.乔姆斯基将文法分为四种，其中，乔姆斯基将文法分为四种，其中，2型文法也称为型文法也称为 ， 3型文法也称为型文法也称为 。4.某文法产生的某文法产生的 的全体是该文法描述的语言。的全体是该文法描述的语言。5.确定的有限自动机（确定
2、的有限自动机（DFA）是一个五元组，它）是一个五元组，它 包括包括 。6.设有文法设有文法GS：SS*S|S+S|(S)| a，该文法，该文法 二义性文法。二义性文法。 编译程序编译程序运行系统运行系统是否有目标代码产生是否有目标代码产生上下文无关文法上下文无关文法正则文法正则文法/线性文法线性文法句子句子(S, ,f,S0,Z)是是编编 译译 原原 理理 期期 中中 考考 试试7.预测分析程序是一种自上而下的分析程序，预测分析要求文预测分析程序是一种自上而下的分析程序，预测分析要求文 法是法是 ，它主要由，它主要由 、预测分析表、预测分析表和总控程序和总控程序 三部分组成。三部分组成。8.自
3、下而上分析方法也称为自下而上分析方法也称为“移进移进归约归约”法，是指从法，是指从 . 开始，查找当前句柄进行归约，直到最后归约为开始，查找当前句柄进行归约，直到最后归约为 . 的一种分析方法。的一种分析方法。9. 给定文法给定文法GS：SaAcBe，句型，句型aAbcde的句柄为的句柄为 。 Ab | Ab Bd10. 算符优先分析法每次都是对算符优先分析法每次都是对 进行进行归约。归约。11. 设有文法设有文法 GS：Sb | bB ，该文法所描述的语言，该文法所描述的语言 BbS 是是 。 Ab最左素短语最左素短语L(GS)=b2i+1| i LL(1)文法文法分析栈分析栈输入符号串输入
4、符号串开始符号开始符号编编 译译 原原 理理 期期 中中 考考 试试 语法分析语法分析(Syntax Analysis)： 在词法分析的基础上将单词序列分解成各类语法短语，如在词法分析的基础上将单词序列分解成各类语法短语，如“程序程序”，“语句语句”，“表达式表达式”等等。等等。 词法分析词法分析(Lexical Analysis)： 从左到右从左到右一个字符一个字符的读入源程序，对构成源程一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而序的字符串进行扫描和分解，从而识别出一个个单词识别出一个个单词（也称（也称单词符号或简称符号）。单词符号或简称符号）。 二、简答题（二、
5、简答题（20分，每题分，每题5分）分）1. 简述一个编译程序的工作过程可以划分为几个阶段，每个阶简述一个编译程序的工作过程可以划分为几个阶段，每个阶 段的任务是什么？段的任务是什么？ 编译程序编译程序语法分析语法分析语义分析与中间代码生成语义分析与中间代码生成优化优化目标代码生成目标代码生成词法分析词法分析编编 译译 原原 理理 期期 中中 考考 试试 代码优化代码优化(Optimization of code)： 为了使生成的目标代码更为高效，可以对产生的中间代码进为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。行变换或进行改造，这就是代码的优化。 代
6、码生成代码生成(Generation of code)： 目标代码生成是编译器的最后一个阶段。在生成目标代码时目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的计算机的系统结构、指令系统、寄存器的分配以及内存的组织分配以及内存的组织等。等。 中间代码生成中间代码生成(Generation of intermediate code)： 完成语法分析和语义处理工作后，编译程序将源程序变成一完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，种内部表示形式，这种内部
7、表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记号系统。它是一种结构简单、含义明确的记号系统。 语义分析语义分析(Syntactic Analysis)： 语义分析是在语法分析程序确定出语法短语后，审查有无语语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集类型信息。义错误，并为代码生成阶段收集类型信息。 编编 译译 原原 理理 期期 中中 考考 试试2. “文法规则的左部一定是非终结符号文法规则的左部一定是非终结符号”，这句话对吗？说明理由。，这句话对吗？说明理由。不对。对于上下文无关文法而言，非终结符号是只在规则左部出不对。对于上下文无关文法而
8、言，非终结符号是只在规则左部出现的符号，对于现的符号，对于其他类型的文法其他类型的文法而言，并非所有在规则左部出现而言，并非所有在规则左部出现的内容都是非终结符号。的内容都是非终结符号。3.什么是规范推导什么是规范推导,规范归约？每个句型都有规范推导吗？规范归约？每个句型都有规范推导吗？ 说明理由。说明理由。 规范推导就是最右推导规范推导就是最右推导，即任何一步，即任何一步 都是对都是对中的中的最右最右非终结符进行替换的；非终结符进行替换的；规范归约就是最左归约规范归约就是最左归约,实质上就是最右实质上就是最右推导的逆过程。对于文法中的每一个推导的逆过程。对于文法中的每一个句子都必定有规范推导
9、或句子都必定有规范推导或最左推导，而对一句型则不一定最左推导，而对一句型则不一定。编编 译译 原原 理理 期期 中中 考考 试试4. 简述简述LR分析器的工作过程。分析器的工作过程。 在在总控程序总控程序的控制下，的控制下，从左到右扫描输入串根据分析栈和从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作输入符号的情况，查分析表确定分析动作；分析表是分析表是LR分析分析器的核心器的核心，它跟文法有关，它包括，它跟文法有关，它包括动作表动作表(Action)和状态转换和状态转换表表(Goto)两部分，总控程序根据分析表确定分析动作；分析栈两部分，总控程序根据分析表确定分析动作；分析
10、栈包括包括文法符号栈文法符号栈Xi和相应的状态栈和相应的状态栈Si两部分两部分(状态是指能识状态是指能识别活前缀的自动机状态别活前缀的自动机状态)，LR分析器通过判断栈顶元素和输入分析器通过判断栈顶元素和输入符号查分析表确定下一步分析动作符号查分析表确定下一步分析动作。 三、解答题（三、解答题（30分）分）1. 已知文法已知文法GS：Sa| |(T) TT，S|S 写出句子写出句子 (a，a)，a) 的规范归约过程及每一步的句柄。的规范归约过程及每一步的句柄。编编 译译 原原 理理 期期 中中 考考 试试 句型句型 归约规则归约规则 句柄句柄(a，a)，a) Sa a(S，a)，a) TS S
11、(T，a)，a) Sa a(T，S)，a) TT，S T，S(S)，a) TS S(T)，a) S(T) (T)(S，a) TS S(T，a) Sa a(T，S) TT，S T，S(T) S(T) (T) S编编 译译 原原 理理 期期 中中 考考 试试2、消除下列文法的左递归。、消除下列文法的左递归。 GS： SSa | Ab | b|c ABc | a BBb | b GS： S(Ab | b|c)S SaS| ABc | a BbB | b 3、给出描述出描述语言言L=a2m+1bm+1|m0 a2mbm+2| m0的文法。的文法。将语言的描述稍做变形，得：将语言的描述稍做变形，得： L
12、=a2mabbm|m0 a2mbbbm| m0GZ：Z aaZb得到文法如下：得到文法如下：| ab| bb编编 译译 原原 理理 期期 中中 考考 试试4、构造正规式、构造正规式 （0|1）* 0（0|1）对应的）对应的DFA。 12(0|1)*3040|11520|13040100415230110015230114构造转换系统图：构造转换系统图： 编编 译译 原原 理理 期期 中中 考考 试试状态转换矩阵状态转换矩阵0015230114I II I0I I11,5,25,2,35,25,2,35,2,3,45,2,45,25,2,35,25,2,3,45,2,3,45,2,45,2,45
13、,2,35,2012121442412333编编 译译 原原 理理 期期 中中 考考 试试I I1I I0I I1,5,25,2,35,25,2,35,2,3,45,2,45,25,2,35,25,2,3,45,2,3,45,2,45,2,45,2,35,20121214424123330011201400011131.首次划分：首次划分： 0=(0,1,2,3,4)2.在在G=0,1,2,3中中:f(0,0)=1f(2,0)=1f(1,0)=3f(3,0)=3f(0,1)=2f(2,1)=2f(1,1)=4f(3,1)=4（终态）（终态）（终态）（终态）编编 译译 原原 理理 期期 中中 考
14、考 试试0011201400011131.首次划分：首次划分： 0=(0,1,2,3,4)2.在在G=0,1,2,3中中:f(0,0)=1f(2,0)=1f(1,0)=3f(3,0)=3f(0,1)=2f(2,1)=2f(1,1)=4f(3,1)=4（终态）（终态）（终态）（终态）故故0,1,2,3可划分为可划分为0,2和和1,31=(0,2,1,3,4)0,2等价等价故故2=(0,2,1,3,4)3.在在0,2中中:1,3不等价不等价在在1,3中中:120140001113编编 译译 原原 理理 期期 中中 考考 试试四、综合题四、综合题1. 已知文法已知文法 GE： E - E | (E)
15、 | VE E - E | V iV V (E) | 求每个非终结符的求每个非终结符的FIRST集和集和FOLLOW集，并构造预测分析表。集，并构造预测分析表。FIRST(E)= -,(,i FIRST(E)= -, FIRST(V)= i FIRST(V)= (, FOLLOW(E)= ) FOLLOW(E)= ) FOLLOW(V)= -,) FOLLOW(V)= -,) -()iEEVVE - EE (E)E VEE - EE V iVV V (E) V 编编 译译 原原 理理 期期 中中 考考 试试2、已知文法、已知文法GS:SSaF | F 构造该文法的算符优先关系矩阵。构造该文法的
16、算符优先关系矩阵。 FFbP | P Pc | dFIRSTVT(S)=a,b,c,dFIRSTVT(F)=b,c,dFIRSTVT(P)=c,dLASTVT(S)=a,b,c,dLASTVT(F)=b,c,dLASTVT(P)=c,dSaaF a b, a c, a d . . . . . a a, b a, c a, d a . . . . a FIRSTVT(F) . b b, c b, d b . . .bP b c, b d . . . . b FIRSTVT(P) . a #, b #, c #, d # . . . .#S # FIRSTVT(S) . . # a, # b, # c, # d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . =A&str0=a&stri=A&str0=a&stri=0 & stri=9) i+; continue;else return 0; return 1; else return 0;编编 译译 原原 理理 期期 中中 考考 试试 结束语结束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！
