大连理工大学编译原理复习

《大连理工大学编译原理复习》由会员分享，可在线阅读，更多相关《大连理工大学编译原理复习（65页珍藏版）》请在装配图网上搜索。

1、编译技术命题指导意见教学内容知识点及题型第一章 编译器概述A（1）编译的阶段划分 选择题 2分1 编译程序绝大多数时间花在( )上。 A. 出错处理 B. 词法分析C. 目标代码生成 D. 符号表管理答案：D2 ( ) 和代码优化部分不是每个编译程序都必需的。A. 语法分析B. 中间代码生成C. 词法分析D. 代码生成答案：B3 编译程序前三个阶段完成的工作是( )。A. 词法分析、语法分析和代码优化 B. 代码生成、代码优化和词法分析C. 词法分析、语法分析和语义分析 D. 词法分析、语法分析和代码生成答案：C（2）遍的概念 填空题 2分1 编译阶段的活动常用一遍扫描来实现，一遍扫描包括 和

2、 。答案：读一个输入文件 写一个输出文件2 将编译程序分成若干个“遍”是为了_。答案：使程序的结构更加清晰3 编译器从逻辑上可以分为7个阶段，其中，可以作为一个后端遍的是_阶段。答案：代码生成（3）前端和后端的划分 简答题 5分1 什么是前端？ 5分答案：编译器分成分析和综合两大部分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。2 什么是后端？ 5分答案：编译器分成分析和综合两大部分。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。3 什么是前端？什么是后端？ 5分答案：编译器分成分析和综合两大部

3、分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。第二章2.1 2.2 词法记号的定义及描述B（1）词法分析器的功能 选择题 2分1 词法分析程序的输出结果是（ ）。A. 单词的种别编码B. 单词在符号表中的位置 C. 单词的种别编码和单词属性值D. 单词的单词属性值答案：C2 词法分析器用于识别_。 A. 字符串 B语句C单词D标识符答案：C3 扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即（ ）。A 字符 B单词

4、 C句子 D句型答案：B（2）词法记号概念及属性 填空题2分1 词法记号是由 和 构成的二元组。答案：记号名 属性值2 词法单元是源程序中匹配一个 的字符序列。答案：记号模式3 影响语法分析的决策， 影响记号的翻译。答案：记号名 属性（3）正规式与语言的对应关系 选择题 2分1 下面文法（ ）和正规表达式a*b描述的语言相同。A. Sab | aSbB. Sb | aSC. Sa | aSbD. Sa | Sb答案：B2 最多包含两个a的a,b上的语言（ ）。A. (a|)b*(a|)B. b*ab*ab*|b*ab*C. b*(a|b*)(a|b*)b*D. b*(a|)b*(a|b*)b*

5、答案：D3 与(a|b)*等价的正规式是（ ）。A. (a*|b*)*B. (a|b)+C. (ab)*D. a*|b*答案：A第二章2.3.1,2.3.2 NFA,DFAC（1）NFA与DFA的概念 选择题 2分1 有如图所示的有穷自动机，与之等价的正规式为（ ）。A. (0|1)*(000|111)(0|1)B. (0|1) (000|111)(0|1)C. (0|1)*(000|111)(0|1) *D. ，B ，C选项都不正确答案：C2 对于NFA和DFA模型说法错误的是（ ）。A. DFA是NFA的特殊形式B. DFA与NFA的状态转换完全相同C. 都有唯一的开始状态D. 都可以有多

6、个接受状态答案：B3 对于DFA模型，说法错误的是（ ）。A. DFA从任何状态出发，对于任何输入符号，可有多个转换B. 任何状态都没有转换C. DFA有唯一的开始状态D. DFA可以有多个接受状态答案：A（2）NFA 的构造 简答题 10分1 设有非确定的有自限动机NFA M=(A，B，C，0，1，d，A，C)，其中：d (A，0)=C d (A，1)=A，B d (B，1)=C d (C，1)=C。请画出状态转换距阵和状态转换图。答案：状态转换距阵为：d01ACA，BBCCC11011状态转换图为：2 构造正规式相应的 NFA : 1(0|1)*101。答案： 3 为（|a）b*）* 构造

7、非确定的有限自动机，给出它们处理输入串ababbab的转换序列。答案：输入串ababbab的转换序列： 0 1456789 145678 789 1456789 10 或者 0 1456789 1456789 1236789 1456789 10（3）NFA转化为 DFA 简答题 10分1 设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答案：构造相应的正规式：(0|1)*1(0|1) NFA: 确定化：I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3

8、,41,2,41,2,3,4、2 构造正规式 1(0|1)*101 相应的DFA。答案：先构造NFA：确定化： 重新命名，令AB为B、AC为C、ABY为D得： 所以，可得DFA为： 3 对于下图所示NFA，回答下列问题：（1）用正规式描述该有限自动机所表示的语言。（2）由NFA转为DFA。（3）构造最简DFA。答案：（1）(a|b)*a(a|b)*（2）（3）（4）DFA的化简 简答题 10分1 已知 NFA= （ x,y,z,0,1,M,x,z ），其中：M(x,0)=z, M(y,0)=x,y, M(z,0)=x,z, M(x,1)=x, M(y,1)= ,M(z,1)=y, 构造相应的D

9、FA并最小化。答案：根据题意有NFA图:下表由子集法将NFA转换为DFA：面将该DFA最小化： (1) 首先将它的状态集分成两个子集：P1=A,D,E,P2=B,C,F (2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21=C,F,P22=B。 (3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11=A,E,P12=D。 (4) 由于F(A,0)=B,F(E,0)=F,

10、而B，F不等价，所以A，E可以区分。 (5) 综上所述，DFA可以区分为P=A，B，D，E，C，F。所以最小化的DFA如下：2 给定下列自动机：把此自动机转换为确定自动机DFA。答案：有状态矩阵如图：从而可得DFA如图：3 （1）将下图中的NFA M确定化为DFA M。 （2）将DFA M化简。答案：确定化: ab00,1110-0，10,11状态编号 ab01220-11210 a -a a2 b b 未简化的DFA最小化： 分为：终态集0,1 非终态集2 0,1a =1 0,1b = 2 所以：0,1 = 0 2 = 110 a - b a第二章2.4,2.5 词法分析器的生成器; 第二章

11、习题D（1）直接从语言构造DFA 简答题5分1 写出能产生字母表x,y上的不含两个相邻的x,且不含两个相邻的的全体符号串的有限状态自动机。答案：2 处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。答案：124start52othersothers/*/3 有语言 L=w|w (0,1)+，并且 w 中至少有两个1 ，又在任何两个1之间有偶数个 0 ，试构造接受该语言的确定有限状态自动机。答案：（2）Lex 的功能 填空题 2分1 Lex是从基于正规式的描述来构造 。答案：词法分析器2 Lex程序包含三部分： 、 和辅助函数。答案：声明 翻译规则3 由

12、Lex建立的 分析器通常作为 分析器的一个子程序。答案：词法 语法第三章 3.1上下文无关文法E（1）上下文无关文法定义选择题2分；1 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（ ）。 A. 句子 B. 句型 C. 单词 D. 产生式答案：D2 文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（ ）。A. 短语文法 B. 正则文法 C. 上下文有关文法D. 上下文无关文法答案：D3 文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_。A. 短语文法B. 正则文法C. 上下文有关文法D. 上下文无关文法答案：A（2

13、）最左推导、最右推导简答题5分；1 文法 S-a|(T) T-T,S|S 对 (a,(a,a) 和 (a,a),(a),a) 的最左推导。答案： 对(a,(a,a)的最左推导为： S=(T) =(T,S) =(S,S) =(a,S) =(a,(T) =(a,(T,S) =(a,(S,S) =(a,(a,S) =(a,(a,a) 对(a,a),(a),a) 的最左推导为： S=(T) =(T,S) =(S,S) =(T),S) =(T,S),S) =(T,S,S),S) =(S,S,S),S) =(T),S,S),S) =(T,S),S,S),S) =(S,S),S,S),S) =(a,S),S

14、,S),S) =(a,a),S,S),S) =(a,a),S),S) =(a,a),(T),S) =(a,a),(S),S) =(a,a),(a),S) =(a,a),(a),a)2 设文法GE:E RP|P P (E)|i R RP+| RP* |P+|P*对i+i*(i+i)的最右推导。答案： E RP R(E) R(RP) R(Ri) R(P+i) R(i+i) RP*(i+i) Ri*(i+i) P+i*(i+i) i+i*(i+i3 考虑文法S-aSbS | bSaS |（a） 为句abab构造两个不同的最左推导，以此说明该文法是二义的。（b） 为abab构造对应的最右推导。答案：（

15、3）分析树简答题5分； 1 考虑文法S-aSbS | bSaS |（1） 为abab构造对应的分析树。（2） 这个文法产生的语言是什么？答案：ETF(E)E+TFiTT*F（1）（2）该文法产生 a、b 个数相等的 ab 串（含空串）2 对于文法G(E): ET|E+TTF|T*FF(E)|i写出句型(T*F+i)的最右推导并画出语法树。答案：（1）ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i)（2）语法树如右图。3 令文法GS为： SABAaAb | abBb,（1）GS定义的语言L(G)是什么？（2）给出句子aabbb的最左推导，并给出其语法分析树。答案：（1

16、）SabBabb SaAbBaabbBaabbb SaAbBaaAbbBaaabbbBaaabbbb Sanbm(n=0,m=1)（2）s ABaAbBaabbBaabbbb/.（4）二义性概念选择题2分1 如果文法G是无二义的，则它的任何句子（ ）。A. 最左推导和最右推导对应的语法树必定相同 B. 最左推导和最右推导对应的语法树可能不同 C. 最左推导和最右推导必定相同 D. 可能存在两个不同的最左推导，但它们对应的语法树相同答案：A2 如果一个文法G是无二义性文法，对于任何一个句子，该句子（ ）。A. 可能存在两个不同的最左推导B. 可能存在两个不同的最右推导C. 最左推导和最右推导不同

17、D. 仅存在一个最左推导和一个最右推导答案：D3 若文法 G 定义的语言是无限集，则文法必然是（ ）。 A. 递归的 B. 前后文无关的C. 二义性的 D. 无二义性的答案：A第三章 3.2 语言和文法F（1）消除左递归填空题2分；1 一个文法是左递归的，如果它有非终结符A，对某个串a，存在推导 。答案：A=+Aa2 的分析方法不能用于左递归文法，因此需要消除左递归。答案：自上而下3 由形式为A-Aa的产生式引起的左递归称为 。答案：直接左递归（2）提取左因子填空题2分；1 提取左因子用于产生适合于 的文法。答案：自上而下2 A-aB|aC，经过提取左因子，原来的产生式成为 和 。答案：A-a

18、A A-B|C3 对于悬空else的文法stmt-if expr then stmt else stmt | if expr then stmt | other提取左因子后的文法成为 和 。答案：stmt-if expr then stmt optional_else_part | other optional_else_part-else |（3）形式语言鸟瞰选择题2分；1 Chomsky把文法分为4种类型，其中描述能力最强的是（ ）。A. 0型B. 1型C. 2型D. 3型答案：A2 文法分为四种类型，即0型、1型、2型、3型。其中1型文法是（ ）。A. 短语文法 B. 正则文法 C. 上

19、下文有关文法D. 上下文无关文法答案：C3 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是（ ）。A. 短语文法B. 正则文法C. 上下文有关文法D. 上下文无关文法答案：B第三章 3.3 自上而下分析G（1）LL(1)文法概念选择题2分；1 3在下面的各种编译方法中，属于自顶向下的语法分析算法的是（ ）。A. LL(1)分析方法B. LR(K) 分析方法C. SLR分析方法D. LALR(1) 分析方法答案：A2 LL(1)分析法的名字中，第二个“L”的含义是（ ）。A. 自左向右进行扫描B. 每次采用最左推导 C. 采用最右推导的逆过程最左规约D. 向输入串中查看一个输入符号答

20、案：B3 LL(1)分析法的名字中，第一个“L”的含义是（ ）。A. 自左向右进行扫描B. 每次采用最左推导C. 采用最右推导的逆过程最左规约D. 向输入串中查看一个输入符号答案：A （2）构造预测分析表（包括求FIRST、FOLLOW集）简答题10分；1 设文法 G(S)： SS aF|aF| aF F*aF|*a （1）消除左递归和回溯； （2）构造相应的 FIRST 和 Follow 集合。答案：（1） S-aFS|aFS S-aFS| F-*aF F-F| （2） FIRST（S）a，+ FOLLOW（S） FIRST（S）+， FOLLOW（S） FIRST（F）* FOLLoW（F

21、）（+， FIRST（F）*， FOLLOW（+，2 文法： S-MH|a H-LSo| K-dML| L-eHf M-K|bLM 判断 G 是否为 LL(1) 文法，如果是，构造 LL(1) 分析表。答案：各符号的FIRST集和FOLLOW集为： 预测分析表为： 由于预测分析表中无多重入口，所以可判定文法是LL(1)的。3 请给对文法GS进行改写成LL（1）文法，并给出改写后文法的预测分析表，要求计算出改写后文法各非终极符的FIRST和FOLLOW集合。S S*aA | aA| *aA A +aA | +a答案：改写文法如下： S*aAS | aAS S*aAS | e A+aA AA |

22、eFIRSTFOLLOWS*，a#S*,e#A+*,#A+,e*,#预测分析表：*a+#SS*aASS aASSS*ASSeAA+aAAAeAAAe（3）用预测分析表对输入串进行分析的过程简答题5分；1 给定LL(1)分析表：有输入符号串i+i*i，写出按上述算法识别此符号串的过程。答案：2 已知文法分析表：i+*()#-/EE-TGE-TGGG-+TGG-G-G-TGTT-FST-FSSS-S-*FSS-S-S-S-/FSFF-iF-(E)有输入符号串i-i/i#，写出按上述算法识别此符号串的过程，遇到错误停止即可，不需要错误恢复。答案：步骤分析栈 剩余字符 所用产生式 0#E i-i/i#

23、 E-TG1#GT i-i/i# T-FS2#GSF i-i/i# F-i3#GSi i-i/i# i匹配4#GS -i/i# S-5#G -i/i# G-TG6#GT- -i/i# -匹配7#GT i/i# T-FS8#GSF i/i# F-i9#GSi i/i# i匹配10#GS /i# S-/FS11#GSF/ /i# /匹配12#GSF /i# F出错3 已知文法分析表：a$(),#Sa$(T)TSFSFSFF,SF有输入符号串(a,(a)#，写出按上述算法识别此符号串的过程。答案：步骤分析栈 剩余字符 所用产生式 0#S (a,(a)# S-(T) 1#)T( (a,(a)# (匹配

24、2#)T a,(a)# T-SF 3#)FS a ,(a)# S-a 4#)Fa a,(a)# a匹配5#)F ,(a)# F-,SF 6#)FS, ,(a)# ,匹配7#)FS (a)# S-(T) 8#)F)T( (a)# (匹配9#)F)T a)# T-SF 10#)F)FS a)# S-a 11#)F)Fa a)# a匹配12#)F)F )# F- 13#)F) )# )匹配14#)F )# F- 15#) )# )匹配16# # acc!第三章 3.4自下而上分析H（1）归约概念选择题2分；1 若a为终结符，则A- a为_项目。A. 归约B. 移进C. 接受D. 待约 答案：B2 移

25、近-归约分析为输入串构造分析树是从（ ）开始的。A. 根结点B. 叶结点C. 中间结点D. 任一结点答案：B3 在每一步归约中，一个子串和某个产生式的（ ）匹配，然后用该产生式的（ ）符号代替这个子串。A. 右部 左部B. 右部 右部C. 左部 右部D. 左部 左部答案：A（2）句柄概念选择题2分；1 在规范归约中，用（ ）来刻画可归约串。A. 直接短语B. 句柄C. 产生式D. 记号答案：B2 下面说法正确的是（ ）。A. 句柄是该句型中和一个产生式左部匹配的子串B. 文法是二义的，句柄是唯一的C. 文法无二义时，句柄可能是唯一的D. 以上说法都不对答案：D3 面说法错误的是（ ）。A. 句

26、柄是该句型中和一个产生式右部匹配的子串B. 文法是二义的，句柄可能不唯一C. 文法无二义时，句柄是唯一的D. 句型中能和产生式A-右部匹配的最左子串就是句柄答案：D第三章 3.5 LR分析器I（1）活前缀概念选择题2分；1一个句型中的活前缀为（）A. 短语 B.简单短语 C.句柄 D.右句型的前缀，该前缀不超过最右句柄的右端答案：D2在LR分析法中，分析栈中存放的状态是识别规范句型( ) 的DFA状态。A.句柄 B. 前缀 C. 活前缀 D. LR(0)项目答案：C3下列语句描述错误的是（）A.活前缀不包含句柄的任何符号，此时期待从输入串中看到该句柄对应的产生式的右部所推导出的符号串B.活前缀

27、只包含句柄的一部分符号，表明该句柄对应的的产生式的右部子串已出现在栈顶，期待从输入串中看到推导出的符号串C.活前缀已含有句柄的全部符号，表明该句柄对应的产生式的右部已出现在栈顶D.活前缀只包含句柄的一部分符号，表明该句柄对应的产生式的右部已出现在栈顶答案：D（2）构造SLR分析表简答题20分；1 给定下列文法构造其SLR分析表 E E + T F F* E T F a T T F F b T F 2 考虑文法E EE +|EE*|a，构造它的SLR分析表3设有文法 SrD DD,i|i(1)证明该文法不是LR(1)文法，是SLR文法(2)给出该文法的SLR分析表答案：(1)构造活前缀的DFA因

28、为在状态出出现（移进，归约）冲突，所以不是LR(0)文法。因为follow(S)=#，可以解决冲突，即若当前单词为，则移进，；若当前单词为#，则归约r(1)。所以是SLR 文法。(2)SLR分析表（3）构造LR分析表简答题20分；1给定文法 GS：请构造该文法的LR分析表 2 给定文法 （1）证明它是LR文法（2）构造其LR分析表答案：（1）该文法LR的项集规范集如下：观察上面的项目规范集可以发现，在项集0和3中，归约项都是在面临符号 $ 时才发生，和移进符号不同。所以，该文法是LR文法。（2）它的LR分析表如下图所示状态ACTIONGOTOab$SA0S4S2R2131Acc2R4R4R43

29、S7S5R2634S4S285R46R17S7S598R3R3R39R33已知文法G(S) SBB BaB Bb构造其LR分析表答案： LR分析表（4）构造LALR分析表简答题20分；1给定下列文法，构造其LALR分析表 S E S S S E E E + T | T E E + T E T T ( E ) | a T ( E ) T a 2有如下文法G(S)： SS SL=R SR L*R Li RL(1)写出此文法的LALR分析表(2)根据文法的LALR分析表分析输入串“i=*i#”的过程答案：(1)LALR分析表(2) “i=*i#”的LALR分析过程3给定文法G(S)构造其LALR分析

30、表。状态ACTIONGOTOabcd$SBA0S6S3S41231acc2S73R5S84S9105S6S12116R7R7R77R28R39R510S1411S12R412R6R6R613R1（5）SLR分析器对输入串进行分析的格局变化和相应动作简答题5分；1已知文法及其SLR分析表，给出输入串“ab#”的SLR分析过程。SLR分析表答案：2若有定义二进制数的文法如下：SLR分析表为给出输入串101.110 的分析过程。答案： 3 考虑以下的文法G（E）：E(L) | aLL , E | E其SLR分析表为给出输入串(a) , a , (a , a)的SLR分析程序的动作。答案：（6）LR分

31、析器对输入串进行分析的格局变化和相应动作简答题5分；1已知文法G(S) SBB BaB Bb其LR分析表为假定输入串为abab，请给出LR分析过程（按步骤给出状态栈，符号，输入串的变化过程）答案：2 给定文法 GS：该文法的LR分析表为 请给出输入符号串abab 的分析过程。答案：3已知文法G：的LR分析表如下：给出()的LR分析过程。答案：第三章 3.7 语法分析器的生成器J（1）Yacc的相关概念选择题2分;1Yacc程序不包含下面的哪一部分（）A.声明B.翻译规则C.支持例程D.定义答案：D2下列说法正确的是( )A.lex是一个词法分析器B.Yacc是一个语法分析器的生成器C.lex是

32、一个语法分析器的生成器D.Yacc是一个语法生成器答案：B3用Yacc处理二义文法的两大默认规则为（）对于归约-归约冲突，选择在Yacc程序中最先出现的那个产生式归约对于归约-归约冲突，选择在Yacc程序中后出现的那个产生式归约对于移近-归约冲突，优先移近对于移近-归约冲突，优先归约A B C D答案：A第四章 4.1 语法制导定义K（1）继承属性、综合属性的概念 选择题 2分1描述文法符号的属性有哪两种（）L-属性 R-属性 综合属性 继承属性A. B. C. D.答案：B2下列说法正确的是A.综合属性值的计算依赖于分析树中他的子节点的属性值B.综合属性值的计算依赖于分析树中他的兄弟节点和父

33、节点的属性值C.继承属性值的计算依赖于分析树中他的子节点的属性值D.综合属性值的计算依赖于分析树中他的父节点的属性值答案：A3对于产生式的继承属性，可能正确的语义规则是 （）A. B. C. D. 答案：C（2）S属性定义的概念 填空题 2分1S属性是仅仅使用 的语法制导定义。答案：综合属性2对于S属性定义，分析树中各结点属性的计算是 完成的。答案：自下而上3分析树中各结点属性的计算中采用自下而上方法计算的属性定义为 。答案：S属性定义（3）注释分析树 填空题 2分1注释分析树的概念为 。答案：每个结点的属性值都标识出来的分析树2 每个结点的属性值都标识出来的分析树称为 。答案：注释分析树3

34、注释分析树中计算各结点属性值的过程称为 。答案：注释或修饰第四章 4.2 S属性的计算L（1）S属性定义的自下而上计算、栈操作 填空题 2分1在语法树中，算符和关键字作为 结点。答案：内部2S 属性定义的计算中，拓展后分子栈的每个栈元素由 和 两部分组成。答案：状态域state 属性域val3 S 属性定义的计算中，若产生式的语义规则是，那么在XY规约成A之前，stacktop-1.Val中存放 的值。答案：x.val /X.x第四章 4.3 L属性的计算M（1）L属性定义的概念 选择题 2分1下列关于L属性定义的说法正确的是（）A.S属性定义属于L属性定义B.变量类型声明的语法制导定义不是一

35、个L属性定义C.L属性定义中只包含综合属性D.L属性定义中只包含继承属性答案：A2在L属性定义中，如果产生式的每条语义规则计算的是的继承属性，则他依赖于（）A的继承属性A的综合属性该产生式中左边符号的属性该产生式中右边符号的属性 A B C D答案：A3 在L属性定义中，如果产生式的每条语义规则计算短的可以是（）A的综合属性A的继承属性的继承属性的综合属性A B C D 答案：A （2）给定文法，写出翻译方案 简答题 10分1 为下列简化的程序文法： P D， D D；D|id：T|proc id；D；S。 写一个翻译方案，打印该程序中每个标识符id的嵌套深度答案：令属性n表示嵌套深度，下面是

36、一个打印标识符id嵌套深度的翻译模式 P D.n：=1 D D D1.n：=D.n D1；D2.n：=D.n D2 D id：T print（id.name，D.n） D proc id；print（id.name，D.n） D1.n：=D.n+1 D1:S2 假设有以下文法 D L id L , id L1 | : T T integer | real建立一个翻译模式, 把每一个标识符的类型加入到符号表中。答案： D L id addtype(id.entry, L.type L , id L1 L.type= L1.type addtype(id.entry, L.type L : T L

37、.type= T.type T integer T.type= 0 T real T.type= 1 用整数0表示整型, 1表示实型.3 考虑文法： S ( L)|a L L，S|S 写一个翻译模式，它打印出每个a在句子中的位置。例如，对于输入串（a，（a，a）的结果是2,5,7.答案：引入属性pos，得到的翻译模式如下： S S.pos：=1； S S ( L L.pos:=S.pos+1; ) Sa print(S.pos); L L1.pos:=L.pos; L1 , S.pos:=L.pos+2; S L S.pos:=L.pos; S 第四章 4.4 L属性的计算N（1）L属性定义的

38、自上而下分析中各种属性与参数、返回值的映射关系填空题 2分1 设计翻译方案时，必须保证动作在引用属性时其值已经可用，在只有 属性时，为每条语义规则建立一个赋值动作，把该动作放在对应产生式的右部的末端，由此可以得到翻译方案。答案：综合2 L属性定义的自上而下分析中设计翻译方案时，若包含继承属性则产生式右部符号的 必须在先于这个符号的动作中计算。答案：继承属性3 L属性定义的自上而下分析中设计翻译方案时，若包含继承属性则左部非终结符的 只能在他所引用的所有属性都计算完后才能计算。答案：综合属性（2）L属性定义的自下而上计算中辅助非终结符引入的目的 选择题 2分1 L属性定义的自下而上计算中的标记非

39、终结符说法正确的是（）A. 引入标记非终结符可以删除翻译方案中嵌入的动作B. 使L属性定义的继承属性计算只出现在产生式左端C. 使L属性定义的综合属性计算只出现在产生式右端D. 使L属性定义的综合属性计算只出现在产生式左端答案：A2 L属性定义的自下而上计算中引入标记非终结符引入的目的错误的是（）A. 删除翻译方案中嵌入的动作B. 模拟综合属性的计算C. 模拟继承属性的计算D. 确定分析栈上属性的位置答案：B3 L属性定义的自下而上计算中处理继承属性时需要引入（）A. 标记非终结符 B. 标记终结符 C. 综合属性 D. L属性答案：A第六章 6.1, 6.2局部、全局存储分配O（1）衬垫区、

40、对齐的概念 选择题 2分1下列说法正确的是（）A. 衬垫区是指由于考虑对齐问题而引起的无用空间B. 局部数据存储安排不存在对齐问题C. 局部数据的数据存储安排与目标机器的寻址限制无关D. 衬垫区是一定会出现的答案：A2关于衬垫区的定义，下列说法正确的是（）A. 衬垫区是在考虑对齐问题时增加的额外空间B. 衬垫区是指由于考虑对齐问题而引起的无用空间C. 衬垫区是局部数据在存储的所需要的最大空间D. 衬垫区是局部数据在存储的所需要的最小空间答案：B3 局部数据在存储安排时，衬垫区是因为（）问题而引起的无用空间A. 对齐 B. 数据的顺序 C . 数据类型 D. 空间答案：A（2）活动记录的内容 简

41、答题 5分1活动记录包括哪些内容/答案：返回值，参数，控制链，访问链，保存的机器状态，局部数据，临时数据2简述活动记录中的各个域及其用途。答案：返回值：用于返回本过程中给调用过程的值 参数：调用过程传递给本过程的参数 控制链：指向调用过程的指针 访问链：用于引用存于其他活动记录的非局部数据 机器状态：御用保存本过程调用前的机器状态 局部数据：本过程内部定义的局部变量 临时数据：本过程计算中可能用到的临时变量3简述活动记录的概念及其内容答案：活动记录是存储过程执行一次所需局部信息的连续的存储区。其内容包括返回值，参数，控制链，访问链，保存的机器状态，局部数据，临时数据（3）活动树的概念 简答题

42、5分1活动树有哪些特点？答案：每个结点代表某过程的一个活动； 根结点代表主程序的活动； 结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动； 结点a 处于结点b 的左边，当且仅当a的生存期先于b的生存期。2什么是活动树？答案：用来描绘控制进入和离开活动的方式的树3简介活动树的概念及其特点。答案：活动树是用来描绘控制进入和离开活动的方式的树。其特点为：每个结点代表某过程的一个活动；根结点代表主程序的活动；结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动；结点a 处于结点b 的左边，当且仅当a的生存期先于b的生存期。（4）控制栈、运行栈的概念 填空题 2分1 把控制栈中的信息

43、拓广到包括过程活动所需的所有局部信息，这种类型的栈称为 。答案：运行栈2 当活动开始时，讲这个活动的结点压入栈中；当活动结束时，将把它的结点从栈中取出。这样的栈称为 。答案：控制栈3 把控制栈中的信息增加到包括过程活动的活动记录，控制栈就成为了 。答案：运行栈（5）过程调用序列、过程返回序列的概念 填空题 2分1 在过程调用时执行的分配活动记录，以及把信息填入其域中的代码被称为 。答案：过程调用序列2 过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码被称为 。答案：过程返回序列3 过程调用序列和过程返回序列常常都分成两部分，分别处于 中。答案：调用过程和被调用过程（6）

44、悬空引用的概念 填空题 2分1 栈式分配的动态释放空间会引起 问题。答案：悬空引用2 是指引用某个已被释放的存储单元。答案：悬空引用3 只要存储空间可以回收，就有可能出现 问题，这是一种逻辑错误。答案：悬空引用第六章 6.3 非局部名字的访问P（1）静态作用域、嵌套深度的概念 选择题 2分1 下列说法错误的是（）A. 语言的作用域规则规定了如何处理非局部名字的访问，一种常用的规则叫做静态作用域 规则B. 静态作用域有两种不同的嵌套方式，分别为无过程嵌套的静态作用域和有过程嵌套的静态作用域C. 变量的嵌套深度定义为它的声明所在过程的嵌套深度D. 程序所需的数据空间在程序运行前就可以完成，则使用的

45、是动态存储管理方法答案：D2 过程的display表记录了（）A. 过程的链接数据 B. 过程的嵌套层次 C.过程的返回地址 D.过程的入口地址答案：B3 如果活动记录中没有display表，则说明（）A. 无递归调用过程 B. 无嵌套定义变量 C.无递归、无嵌套 D.有递归、无嵌套 答案：D（2）静态链的建立 简答题 5分1 假定嵌套深度为np的过程p调用嵌套深度为nx的过程x ，则建立被调用过程静态链的过程是什么？答： np nx的情况 x肯定就声明在p中 被调用过程的访问链必须指向调用过程的活动记录的访问链np nx的情况 p和x的嵌套深度分别为1，2，nx- 1的外围过程肯定相同 追踪

46、访问链np - （nx 1）次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录 所到达的访问链就是x的活动记录中的访问链应该指向的那个访问链2 简述活动记录和访问链的主要作用，以及访问链的指向。 答：活动记录用于提供活动所需的环境，访问链用于访问非本地数据。访问链的指向有两种：非显示表指向直接外层的最新活动记录，显示表指向同层次新活动记录。3 设有一程序在执行到某一时刻时，控制栈中的活动记录如下图所示（其中A是主程序，B、C、D、E均是过程）。(1) 分别指出A、B、C、D、E的嵌套深度；(2)试根据访问链中的内容画出过程的嵌套关系树。答案： (1)A、B、C、D、E的嵌套深度分别为： 1、2、3、3、2； (2)嵌套关系树为（3）动态作用域的概念 简答题 5分1简介两种实现动态作用域的方法答案：深访问，用控制链搜索运行栈，寻找包含该非局部名字的第一个活动记录； 浅访问，为每个名字在静态分配的存储空间中保存它的当前值。当过程p的新活动出现时，p的局部名字n使用在静态数据区分配给n的存储单元。n的先前值可以保存在p的活动记录中，当p的活动结束时再恢复2简述动态作用域的概念答案：被调用过程的非局部名字