2.编译过程可分为 （ ） ，（ ），（ ），（ ）和（ ）五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ ）。 4.从功能上说，程序语言的语句大体可分为（ ）语句和（ ）语句两大类。 5.语法分析器的输入是（ ），其输出是（ ）。 6.扫描器的任务是从（ ）中识别出一个个（ ）。
7.符号表中的信息栏中登记了每个名字的有关的性质，如( ）等等。 8.一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址) 10.常用的两种动态存贮分配办法是（ ）动态分配和（ ）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有( ），（ ），（ ） 13.根据优化所涉及的程序范围，可将优化分成为( ）三个级别。 14.语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法。 15.预测分析程序是使用一张（ ）和一个（ ）进行联合控制的。
17.一张转换图只包含有限个状态,其中有一个被认为是（ ）态;而且实际上至少要有一个（ ）态。 19.语法分析是依据语言的（ ）规则进行。中间代码产生是依据语言的（ ）规则进行的。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（ 文法）文法。 22.对于数据空间的存贮分配， FORTRAN采用( ）策略， PASCAL采用( )策略。 24.最右推导亦称为（ ），由此得到的句型称为（ ）句型。 26.对于文法G，仅含终结符号的句型称为 ( )。
27.所谓自上而下分析法是指( ） 29.局限于基本块范围的优化称（ ）。
31.2型文法又称为（ ）文法；3型文法又称为（ ）文法。 32.每条指令的执行代价定义为( ）
33.算符优先分析法每次都是对( ）进行归约。 三、名词解释题：
1.局部优化-------局限于基本块范围的优化称。
2.二义性文法------如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。 3.DISPLAY表----过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。 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.语法制导翻译------在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语
法制导翻译。
17.规范句型------由规范推导所得到的句型。
18.素短语------素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的
素短语。
第1页共6页
19.语法------是组规则，用它可形成和产生一个合式的程序。
20.待用信息------如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没
有A的其它定值，则称j是四元式i的变量A的待用信息。 21.语义------定义程序的意义的一组规则。
三、名词解释题(共5小题，每小题4分，共20分)
1．词法分析
词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法
若文法的任何两个产生式A ? ? | ?都满足下面两个条件： （1）FIRST(? ) ? FIRST(? ) = ?；
（2）若? ?* ? ，那么FIRST(? ) ? FOLLOW( A ) = ?。
我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左 向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一 些明显的性质，它不是二义的，也不含左递归。 3．语法树
句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。
(2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列 次序为A1A2…AR，那么A?A1A2…AR一定是P中的一条产生式。 (4)若一标记为A的节点至少有一个除它以外的子孙，则A?VN。 (5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G 的句型；若w中仅含终结符号，则w为文法G所产生的句子。 4．LR(0)分析器
所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的 每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再 向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否 已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是 移进还是按某一产生式进行归约等)。
5．语言和文法
文法就是语言结构的定义和描述，是有穷非空的产生式集合。 文法G定义为四元组的形式：
G=(VN，VT，P，S) 其中：VN 是非空有穷集合，称为非终结符号集合；VT 是非空有穷集合， 称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。
第2页共6页
这里，VN∩VT=?，S?VN。V=VN∪VT，称为文法G的字母表，它是出现 文法产生式中的一切符号的集合。
文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即
L(G)={x| S?*x，其中S为文法开始符号，且x?VT } 简单的说，文法描述的语言是该文法一切句子的集合。
四、简答题：
1.写一个文法G, 使其语言为 不以0开头的偶数集。 2.已知文法G(S)及相应翻译方案
S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么？ 3. 已知文法G(S)
S→bAa
A→(B | a B→Aa)
写出句子b(aa)b的规范归约过程。 4. 考虑下面的程序：
?
procedure p(x, y, z)； begin y:=x+y; z:=z*z; end begin
A:=2; B:=A*2; P(A, A, B); Print A, B end.
试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A, B的值是什么? 5．文法G(S) S→dAB A→aA| a B→Bb| ε
描述的语言是什么？ 6. 证明文法G(S) S→SaS| ε 是二义性的。 7. 已知文法G(S) S→BA A→BS| d
第3页共6页
?B→aA| bS | c 的预测分析表如下
a b c d # S S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c
给出句子 adccd 的分析过程。
lmlnn
8. 写一个文法G, 使其语言为 L(G)={abcab| l>=0, m>=1, n>=2} 9. 已知文法G(S): S→a| (T) T→T,S|S
的优先关系表如下：
关系 a ( ) , a - - .> .> ( <. <. =. <. ) - - .> .> , <. <. .> .> 请计算出该优先关系表所对应的优先函数表。 10. 何谓优化？按所涉及的程序范围可分为哪几级优化？
11. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？
12. 一字母表Σ={a, b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。 13. 基本的优化方法有哪几种？
nn
14. 写一个文法G, 使其语言为 L(G)={abc| n≥0} 15. 考虑下面的程序
procedure p(x, y, z); begin y:=y+z; z:=y*z+x end; begin a:=2; b:=3;
p(a+b, b, a); print a end.
试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 16.写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。 17.证明文法G(A) A→AA | (A)| ε 是二义性的。
**
18.令Σ={a,b}，则正规式ab|ba表示的正规集是什么？ 19.何谓DISPLAY表？其作用是什么？ 20.考虑下面的程序：
?
procedure p(x, y, z)； begin
第4页共6页
y:=y+2; z:=z+x; end begin
a:=5; b:=2;
p(a+b, a-b, a); print a end.
试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么?
nnm
21.写一个文法G, 使其语言为 L(G)={abc| n>0为奇数， m>0为偶数} 22.写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 23.一个文法G别是LL(1)文法的充要条件是什么？ 24.已知文法G[S]
S→S*aF | aF | *aF F→+aF | +a
消除文法左递归和提公共左因子。
25.符号表的作用是什么？符号表查找和整理技术有哪几种？ 答案：1.所求文法是G[S]:
S→AB |B A0 A→AD |C
B→2 |4 |6 |8
C→1 |3 |5 |7 |9 |B D→0 |C 2.输出是4231
3.句子b(aa)b的规范归约过程： 步骤 符号栈 输入串 动作 0 1 2 3 4 5 6 7 8 9 10 # #b #b( #b(a #b(A #b(Ma #b(Ma) #b(B #bA #bAb #S b(aa)b# (aa)b# aa)b# a)b# a)b# )b# b# b# b# # # 预备 移进 移进 移进 归约 移进 移进 归约 归约 移进 接受 4.传地址 A=6, B=16 传值 A=2, B=4
nm
5.L(G)={dab |n>0, m≥0} 6.证明：
因为文法G[S]存在句子aa有两个不同的最左推导，所以文法G[S]是是二义性的。
S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa 7.句子 adccd 的分析过程：
第5页共6页
郑州大学编译原理
