文法。
其(1)分析表为：
对输入串给出分析过程为：
《编译原理》期末试题（二）
一、是非题：
1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( )
2.一个句型的直接短语是唯一的。 （ ）
3.已经证明文法的二义性是可判定的。 （ ）
4.每个基本块可用一个表示。 （ ）
5.每个过程的活动记录的体积在编译时可静态确定。 （ ） 6.2型文法一定是3型文法。 （ ） 7.一个句型一定句子。 ( )
8.算符优先分析法每次都是对句柄进行归约。 X ( )
9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 （ ）
9 / 81
10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( )
11.一个优先表一定存在相应的优先函数。 X ( )
12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( )
13.递归下降分析法是一种自下而上分析法。 ( )
14.并不是每个文法都能改写成(1)文法。 ( )
15.每个基本块只有一个入口和一个出口。 ( )
16.一个(1)文法一定是无二义的。 ( )
17.逆波兰法表示的表达试亦称前缀式。 ( )
18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( )
19.正规文法产生的语言都可以用上下文无关文法来描述。 ( )
20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是2型文法。 ( )
22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( )
答案：1.× 2.× 3.× 4.√ 5.√ 6.× 7.×
8.× 9.√ 10.× 11.×
12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√ 19.√ 20.× 21.√ 22.√
二、填空题：
2.编译过程可分为 （ 词法分析） ，（语法分析），（语义分析与中间代码生成 ），（优化）和（目标代码生成 ）五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ 二义性的 ）。
4.从功能上说，程序语言的语句大体可分为（ 执行性 ）语句和（说明性 ）语句两大类。
5.语法分析器的输入是（ 单词符号 ），其输出是（ 语法单位 ）。
6.扫描器的任务是从（ 源程序中 ）中识别出一个个（ 单词符号 ）。
7.符号表中的信息栏中登记了每个名字的有关的性质，如(类型、种属、所占单元大小、地址）等等。
8.一个过程相应的表的内容为(现行活动记录地址和所有外层最新活动记录的地址)
10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。
10 / 81
11.一个名字的属性包括( 类型)和(作用域 )。 12.常用的参数传递方式有(传地址），（传值），（传名）
13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。
14.语法分析的方法大致可分为两类，一类是（ 自上而下 ）分析法，另一类是（ 自下而上 ）分析法。
15.预测分析程序是使用一张（ 分析表 ）和一个（ 符号栈 ）进行联合控制的。
17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终 ）态。
19.语法分析是依据语言的（语法 ）规则进行。中间代码产生是依据语言的（语义）规则进行的。
21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（(1) 文法）文法。
22.对于数据空间的存贮分配， 采用( 静态策略， 采用( 动态)策略。 24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。 26.对于文法G，仅含终结符号的句型称为 ( 句子 )。
27.所谓自上而下分析法是指(从开始符号出发，向下推导，推出句子） 29.局限于基本块范围的优化称（ 局部优化 ）。
31.2型文法又称为（上下文无关）文法；3型文法又称为（正则 ）文法。
32.每条指令的执行代价定义为(指令访问主存次数加1） 33.算符优先分析法每次都是对(最左素短语）进行归约。 三、名词解释题：
1.局部优化局限于基本块范围的优化称。
2.二义性文法如果一个文法存在某个句子对应两棵不同的语法树，则称这
个文法是二义性文法。
3表过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。
5.最左推导任何一步α=>β都是对α中的最右非终结符替换。 6.语法一组规则，用它可形成和产生一组合式的程序。 7.文法描述语言的语法结构的形式规则。 8.基本块指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，
入口就是其中的第一个语句，出口就是其中的最后一个语句。
9.语法制导翻译在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。
10.短语令G是一个文法，S划文法的开始符号，假定αβδ是文法G的
一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。
11.待用信息如果在一个基本块中，四元式i对A定值，四元式j要引用A
值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。
12.规范句型由规范推导所得到的句型。 13.扫描器执行词法分析的程序。
14.超前搜索在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。
15.句柄一个句型的最左直接短语。 16.语法制导翻译在语法分析过程中，根据每个产生式所对应的语义程序进
行翻译的方法 叫做语法制导翻译。
11 / 81
17.规范句型由规范推导所得到的句型。
18.素短语素短语是指这样一个短语，至少含有一个终结符，并且，除它自
身外不再含任何更小的素短语。
19.语法是组规则，用它可形成和产生一个合式的程序。
20.待用信息如果在一个基本块中，四元式i对A定值，四元式j要引用A
值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。
21.语义定义程序的意义的一组规则。 四、简答题：
1.写一个文法G, 使其语言为 不以0开头的偶数集。 2.已知文法S→a { “2”}S→ { “1”}G(S)及相应翻译方案
A→ { “3”} A→c { “4”} 输入3. 已知文法, 输出是什么？ S→G(S)
B→)
A→(B | a 4. 考虑下面的程序： 写出句子
b()b的规范归约过程。 …
; p(x, y, z)
； *z; 2;*2; P(A, A, B);
. A, B 试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出
的值是什么5S→．文法G(S)? A→ a B→ ε 描述的语言是什么？
6. 证明文法G(S) S→ ε
7. 是二义性的。 A→ dS→已知文法 G(S) B→ | c 的预测分析表如下
12 / 81
A, B