《编译原理试题》由会员分享，可在线阅读，更多相关《编译原理试题（8页珍藏版）》请在金锄头文库上搜索。
1、二、填空题：1、从功能上说，程序语言的语句大体可分为执行性语句和说明性语句两大类。2、扫描器的任务是从源程序 中识别出一个个单词符号。3、所谓最右推导是指：任何一步a-B都是对a中最右非终结符进行替换的4、语法分析最常用的两类方法是自上而下 和自下而上 分析法。5、一个上下文无关文法所含四个组成部分是一组终结符号，一组非终结符号、一个开始符 号、一组产生式。6、所谓语法制导翻译方法是 为每个产生式配上一个翻译子程序，并在语法分析的同时执 行这些子程序。7、符号表中的信息栏中登记了每个名字的有关的性质，如类型、种属、所占单元大小、地 址 等等。三名词解释1遍指编译程序对源程序或中间代码程序从头到
2、尾扫描一次。 3语法分析按文法的产生式识别输入的符号串是否为一个句子的分析过程。4. 短语一一令G是一个文法。S划文法的开始符号，假定aB是文法G的一个句型， 如果有SaAS且AB，则称B是句型aB相对非终结符A的短语。5. 后缀式一种把运算量写在前面，把算符写在后面的表示表达式的方法。 四、简答题3、写出表达式（a+b*c）/（a+b） d的逆波兰表示及三元式序列。逆波兰表示：abc*ab/d（2分）三元式序列： （*，b，c） （+, a,） （，a，b） （/,，） （，d）（2分）4、已知文法G（S）S-a|A|（T）T-T, S|S写出句子（a,a）, a）的规范归约过程及每一步的句
3、柄。句型归约规则句柄(a，a)，a)S-aa(S，a)，a)T-SS(T，a)，a)S-aa(T，S)，a)T-T，ST，S(S)，a)T-SS(T)，a)S-S(T)(T)(S，a)T-SS(T，a)S-aa(T，S)T-T，ST，S(T)S-(T)(T)(4分)5、何谓优化？按所涉及的程序范围可分为哪几级优化？答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目 标代码。(2分)三种级别：局部优化、循环优化、全局优化。 (2分)6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？ 答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。(2分)
4、 应着重考虑的问题：(1) 如何使生成的目标代码较短；(2) 如何充分利用寄存器，以减少访问内存次数；(3) 如何充分利用指仅系统的的特点。 (2分) 五、计算题1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。(5分)解：文法G(N)：NAB|BAAC|DB-l|3|5|7|9D-B|2|4|6|8C-O|D(5 分)2、设文法G(S)：S- (L)|a S|aL-L, S|S(1) 消除左递归和回溯；(2) 计算每个非终结符的FIRST和FOLLOW；(3) 构造预测分析表。解： (1)S-(L)|aSS-S| & L-SL L -SL| &评分细则：消除左递归2分,提公共因子2分。
5、(2)FIRST)S) = (, a FIRST(S) = , a, FIRST(L) = (, a FIRST(L) = ,；FOLLOW(S) = #, )FOLLOW(S) = #, )FOLLOW(L)= )FOLLOW(L= )do= a_=b+l3、While a0 or bVOBeginX：=X+1；if a0 then a： else b：End；翻译成四元式序列。(7分)解：(1)(j.a，0，5)(2)(j，3)(3)(jv，b0，5)(4)(j，15)(5)(+，x,1，T1)(6)(:=，T1，x)(7)(jMa，0，9)(8)(j，12)(9)(，a，1，T2)(10
6、)(：，T2，a)(11)(j，1)(12)(+b1，T3)(13)(：，T3，b)(14)(j，1)(15)评分细则：控制结构4分，其它3分。4、已知文法G(E)ET|E+TTF|T * FF (E)|i(1) 给出句型(T * F+i)的最右推导及画出语法树;(2) 给出句型(T * F+i)的短语、素短语。(7分)解：(1)最右推导：ETF(E)(E+T)(E+F)(E+i) (T+i)(T*F+i)(2)短语：(T*F+i), T*F+i, T*F, i(2 分)素短语：T*F,i(1分)二、填空题(每题2分，共20分)1、语法分析是依据语言的语法规则进行的，中间代码产生是依据语言的语
7、义规则进行 的。2、程序语言的单词符号一般可以分为关键字、标识符、常量、算符、界符等等。3、语法分析器的输入是单词符号串 ，其输出是语法单位4、所谓自上而下分析法是指 从开始符号出发，向下推导，推出句子。5、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的 。6、对于文法G,仅含终结符号的句型称为句子7、逆波兰式ab+c+d*e-所表达式为(a+b+c)*d-e。8、一个名字的属性包括类型和 作用域。9、对于数据空间的存贮分配，FORTRAN采用静态存储分配策略，PASCAL采用动态存储分 配 策略。10、所谓优化是指对程序进行各种等价变换，使得从变换后的程序出发，能生成更有
8、效的目标代码。三名词解释1词法分析器指执行词法分析的程序。2语法一组规则，用它可以形成和产生一个合式的程序3最右推导指对于一个推导序列中的每一步直接推导，被替换的总是当前符号串中的 最右非终结符号。4语法制导翻译在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的 办法叫做语法制导翻译。5基本块指程序中一个顺序执行的语句序列，其中只有一个入口，一个出口，入口即 第一个语句。出口即最后一个语句。简答题：2、画出识别 pascal 中实常数(可带正负号，但不含指数部分)的状态转换图。数字3、已知文法G(S): Sa|(T) TT,S的S优先关系表如下:关系a()a(=请计算出该优先关系表所
9、对应的优先函数表。答：优先函数表如下(f函数2分，g函数2分)函数a()f4244g55234、写出表达式(a+b)/(a-b)-a(a+b*c)的三元式序列及四元序列。 答：三元式2分(l) .(+,a,b).(-,a,b)(3).(/,，).(*,b,c).(+,a，)(6).(-,，)四元式2分.(+,a,b,Tl).(-,a,b,T2).(/,T1,T2,T3).(*,b,c,T4).(+,a,T4,T5)(6).(-,T3,T5,T6)5、符号表的作用是什么？ 答：作用：登记源程序中出现的各种名字及其信息，以及编译各阶段的进展状况。(2 分)五、计算题(共 41 分)1、写一个文法，
10、使其语言是偶数集，且每个偶数不以0开头。(5分) 文法 G(S):SAB|B|AOAAD|CB2|4|6|8C1|3|5|7|9|BDO|C2、已知文法 G(S):Sa|Al(T)TT,S|S(1)给出句子(a,(a,a)的最左推导并画出语法树；给出句型(T,S),a)的短语、直接短语、句柄。(8分) 最左推导：(2 分)S=(T)=(T,S)=(S,S) =(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)3、把语句if x0Ay0 then z:=x+yelse beginx:=x+2;y:=y+3END; 翻译成四元式序列。 (6 分) (j
11、,x,0,3) (j,-,-,8) (j,y,0,5) (j,-,-,8) (+,x,y,T1)6 (:=,T1,-,Z) (j,-,-,12) (+,x,2,T2) (:=,t2,-,X) (+,Y,3,t3)(11) (:=,T3,-,y)(12)(控制结构3分，其它3 分)4、 设文法 G(S):SS+aF|aF|+aFFf*aF|*a 消除左递归和回溯； 构造相应的 FIRST 和 FOLLOW 集合； 构造预测分析表(10 分)4、答： ( 消除左递归 2 分，提公共左因子 2 分 )SfaFS|+aFSSf+aFS|Ff*aFFJF| (3 分)FIRST(S)=a,+ FOLLO
12、W(S)=#FIRST(S)=+, FOLLOW(S)= #FIRST(F)=* FOLLOW(F)=+,#FIRST(F)=*,)FOLLOW(F)=+,# (3 分)-a+*#SSfaFSSf+aFS-S-Sf+aFS-SfF-Ff*aF-F-FfFfFFf一选择题（每空2分,共 20分）1、文法 G 产生的 的全体是该文法描述的语言。A.句型B.终结符集C.非终结符集D.句子2、若文法 G 定义的语言是无限集，则文法必然是 ：A.递归的B.前后文无关的C.二义性的D.无二义性的3、Chomsky 定义的四种形式语言文法中， 0 型文法又称为 文法； 1 型文法又称 为 文法； 2 型语言
13、可由 识别。(3) : A.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法E.图灵机F有限自动机 G.下推自动机(4) A.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法E.图灵机F有限自动机 G.下推自动机(5) A.短语结构文法B.前后文无关文法C.前后文有关文法D.正规文法E.图灵机F有限自动机 G.下推自动机4、一个文法所描述的语言是 ；描述一个语言的文法是 。(6) : A.唯一的B.不唯一的C.可能唯一，可能不唯一(7) : A.唯一的B.不唯一的C.可能唯一，可能不唯一5、数组的内情向量中肯定不含有数组的 的信息A.维数B.类型C.维上下界D.各维的界差6、在下述的编译方法中，自底向上的方法有 ，自顶向下的分析方法有 。 简单优先分析
