2-13.文法G[E]：
E→T∣E＋T T→F∣T﹡F
F→a∣（E）
该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的 B 。 ①（E＋T） ②E＋T ③F ④ F﹡(E＋T) 可选项有：
A) ①和③ B) ②和③ C) ③和④ D) ③ 2-14．若一个文法是递归的，则它所产生的语言的句子 A 。 A.是无穷多个 B.是有穷多个 C.是可枚举的 D.个数是常量 2-15．文法的二义性和语言的二义性是两个 A 的概念。
A 不同 B 相同 C 无法判断 D 不存在 3-02．词法分析器用于识别 C 。
A. 句子 B. 句型 C. 单词 D. 产生式
4-07.在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是 B 。
A. 非终极符集 B.终极符集 C. 字母表 D. 状态集 4-08.编译程序中语法分析器接收以 A 为单位的输入。
A. 单词 B. 表达式 C. 产生式 D. 句子 5-06．在自底向上的语法分析方法中，分析的关键是 D 。
A. 寻找句柄 B. 寻找句型 C. 消除递归 D. 选择候选式 5-07. 在LR分析法中，分析栈中存放的状态是识别规范句型 C 的DFA状态。 A.句柄 B. 前缀 C. 活前缀 D. LR(0)项目 6. DFA和NFA的区别在于 C 。
A．初始状态个数要求不同 B．转换函数要求不同 C．A和B两个的合并
10.对于允许过程递归调用的语言，在它的目标程序的运行环境中至少应该使用 B 。
A.静态分配 B.动态分配 C.存储分配 D 内存分配
11. 文法G[Z]：
Z?Bb, A?Ae, A?e, B?Af,
其中e和f为终极符，#是输入串的结束符，FOLLOW（A）为 A 。
A．{e,f} B．{e} C．{f} D．{#}
12. 在编译中，中间代码生成的常用方法有 D 。
A．LR法 B．递归法 C．最优匹配法 D．语法制导翻译方法
13. 下列关于标识符和名字的叙述中，正确的为 C 。
A. 标识符有一定的含义 B. 名字是一个没有意义的字符序列
C. 名字有确切的属性 D. 都不对
nn
14. 已知语言L={ abb | n>=1}，则下述文法中， B 可以产生语言L。
A． 1.Z→aZb|aAb|b B． 1.A→aAb
2. A→aAb|b 2.A→b C． 1.Z→AbB D． 1.Z→aAb 2.A→aA|a 2.A→aAb|b 3.B→bB|b
15 文法的二义性和语言的二义性是两个 C 的概念。
A．不存在 B．相同 C．不同 D．无法判断
三、是非题(下列各题，你认为正确的，请在题干的括号内打“ √”，错的打“×”。) 1-31.计算机高级语言翻译成低级语言只有解释一种方式。 （×） 1-32.在编译中进行语法检查的目的是为了发现程序中所有错误。 （×）
1-34.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 （×）
2-15.正则文法其产生式为A?a，A?Bb, A,B∈VN，a、b∈VT。 （√） 4-09.每个文法都能改写为LL(1)文法。 （×） 4-10.递归下降法允许任一非终极符是直接左递归的。 （√） 5-08.算符优先关系表不一定存在对应的优先函数。 （√） 5-09.自底而上语法分析方法的主要问题是候选式的选择。 （×） 5-10.LR法是自顶向下语法分析方法。 （×） 5-11.简单优先文法允许任意两个产生式具有相同右部。 （×） 5-12.若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 （×） 5-13.一个句型的句柄一定是文法某产生式的右部。 （√） 7-02.数组元素的地址计算与数组的存储方式有关。 （√） 8-03.在程序中标识符的出现仅为使用性的。 （×） 9-04.对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 （×） 9-05.在程序中标识符的出现仅为使用性的。 （×） 10-03.仅考虑一个基本块，不能确定一个赋值是否真是无用的。 （√） 10-04.削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。 （×） 10-05.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 （√） (×)6.活前缀不包含句柄中的任何符号。
(√)9.对任一编译程序来说，产生中间代码不一定是必要的。
(×)13.若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 (×)16.活前缀就是任何句型的有用前缀。
(×)17.编译程序在优化时可能要用到源程序中的注释。 (×)18.目标代码就只有可立即执行的机器语言代码一种。
(×)19.任何句型都存在一个规范推导，任何句子也都存在一个规范推导。 (×)22.中间代码优化的目的是检查源语言的各种错误。 (√)23.解释与编译方式的区别是解释没有生成目标代码。 (×)24.目标代码的生成与目标机无关，与宿主机有关。 四、名词解释
1-35. 扫描遍____指编译程序对源程序或中间代码程序从头到尾扫描一次。
2-16.短语——设G[Z]是给定文法, w=xuy∈V+，为该文法的句型,如果满足下面两个条件:
① Z ② U
xUy； u；
则称句型xuy 中的子串u是句型xuy的短语。
2-17.简单短语——设G[Z]是给定文法, w=xuy∈V+，为该文法的句型,如果满足下面两个条件:
① Z
xUy；
② U ? u；
则称句型xuy 中的子串u是句型xuy的简单短语（或直接短语）。
2-18.句柄——一个句型中的最左简单短语称为该句型的句柄。
2-19.答：规范推导——如果在任一步推导v?w中，都是对符号串v的最右非终结符进行替换，则
称其为规范推导。
2-21.答：语言—— L（G[Z]）={x| Z ?* x， x∈VT* }。 4-11.语法分析－－按文法的产生式识别输入的符号串是否为一个句子的分析过程。 4-12.选择符集合SELECT－－给定上下文无关文法的产生式A→α, A∈VN,α∈V, 若α
SELECT(A→α)=FIRST(α),其中如果α
ε，则SELECT(A→α)=FIRST(α\\ε)∪
FOLLOW(A),FIRST(α\\ε)表示FIRST(α)的非{ε}元素。
*
ε,则
αAω 5-14.活前缀——若S′ αβω是文法G′中的一个规范推导，G′是G的拓广文法，符号串γ
R R
是αβ的前缀，则称γ是G的，也是G′的一个活前缀。其中 S'为文法开始符号。或：可归前缀
的任意首部。
5-15.可归前缀——是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
5-16.LR(0)项目——把产生式右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。 5-17.算符优先文法——设有一不含ε产生式的算符文法G，如果对任意两个终结符对a，b之间至多只
有
、
和
三种关系中的一种成立，则称G是一个算符优先文法。
5-18.最左素短语——设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并除自身外不
包含其它素短语，最左边的素短语称最左素短语。
6-05.语义规则——对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。
6-06.翻译方案——将属性文法中的语义规则用花括号{ }括起来，插在产生式右部的合适地方，指明语义规则的计算次序，陈述一些细节，得到一种语义动作与语法分析交错的表示方法，以表述语义动作在语法分析过程中的执行时刻，称之为翻译方案。
6-07.语法制导翻译——为文法中每个产生式配备一组语义规则，并且在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。
7-03.后缀式—— 一种把运算量（操作数）写在前面把算符写在后面（后缀）的表示法。即
一个表达式E的后缀形式可以如下定义：
(1) 如果E是一个变量或常量，则E的后缀式是E自身。
(2) 如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’ E2’op，这
里E1’和E2’分别为E1和E2的后缀式。
(3) 如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
7-04.四元式—— 一个四元式是一个带有四个域的记录结构，这四个域分别称为op、arg1、arg2及result。域op包含一个代表运算符的内部码。 9-06.活动
答：一个过程的活动指的是该过程的一次执行。就是说，每次执行一个过程体，产生该过程体的一个活动。 9-07.活动记录
答：为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样一个连续的存储块称为活动记录。
9-08.活动的生存期
答：指的是从执行某过程体第一步操作到最后一步操作之间的操作序，包括执行过程时调用其它过程花费
的时间。
10-02.答：基本块——源程序中只有一个入口和一个出口的顺序执行的代码段。 10-07. 基本块的DAG。
答：一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG。
(1)图的叶结点（没有后继的结点）以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。
(2)图的内部结点（有后继的结点）以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。
(3)图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。
五、简答题：
2-19什么是句子？ 什么是语言?
答：设G是一个给定的文法，S是文法的开始符号，如果S2-20.已知文法G[E]为：
E→T|E+T|E-T T→F|T*F|T/F F→（E）|i
① 该文法的开始符号（识别符号）是什么？
②请给出该文法的终结符号集合VT和非终结符号集合VN。 ③ 找出句型T+T*F+i的所有短语、简单短语和句柄。 解：① 该文法的开始符号（识别符号）是E。
②该文法的终结符号集合VT={+、-、*、/、（、）、i}。 非终结符号集合VN={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i; 简单短语为i、T*F、第一个T;句柄为第一个T。
2-21.已知文法G[S]为：
S→dAB A→aA|a B→Bb|ε
① G[S]产生的语言是什么？ ② G[S]能否改写为等价的正规文法？
解：① G[S]产生的语言是L(G[S])={dab│n≥1,m≥0}。
② G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[Sˊ]为： Sˊ→dA A →aA|aB|a B →bB|b
nm
x(其中x∈VT),则称x是文法的一个句子。
x,x∈VT} 。
*
*
设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S
相关推荐：
loading