二填空题
1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两
种：静态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。
3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i，j]的地址计算公式为（9）。
7．局部优化是局限于一个（10）范围内的一种优化。
答案(1) 栈式动态存储分配 (2) 堆式动态存储分配 (3) 左 (4) 语法分析 (5) 目标代码生成 (6) 表格管理 (7) xyz*ab+/+ (8) 继承属性 (9) a+(i-1)*20+j-1 (10) 基本块
8 词法规则通常可以用____正规式________，正规文法、____自动机________描述；语法规则通常用___2型文法___来描述；语义规则通常用__属性文法_____来描述。
9 编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段。 1.( )称为规范推导。
2.编译过程可分为 （ ） ，（ ），（ ），（ ）和（ ）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ ）。 4.从功能上说，程序语言的语句大体可分为（ ）语句和（ ）语句两大类。 5.语法分析器的输入是（ ），其输出是（ ）。 6.扫描器的任务是从（ ）中识别出一个个（ ）。
7.符号表中的信息栏中登记了每个名字的有关的性质，如（ ）等等。 8.一个过程相应的DISPLAY表的内容为（ ）。 9.一个句型的最左直接短语称为句型的（ ）。
10.常用的两种动态存贮分配办法是（ ）动态分配和（ ）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（ ），（ ）和（ ）。 13.根据优化所涉及的程序范围，可将优化分成为（ ），（ ）和（ ）三个级别。
14.语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法。
15.预测分析程序是使用一张（ ）和一个（ ）进行联合控制的。 16.常用的参数传递方式有（ ），（ ）和（ ）。
17.一张转换图只包含有限个状态,其中有一个被认为是（ ）态;而且实际上至少要有一个（ ）态。
18.根据优化所涉及的程序范围，可将优化分成为（ ），（ ）和（ ）三个级别。
19.语法分析是依据语言的（ ）规则进行。中间代码产生是依据语言的（ ）规则进行的。
20.一个句型的最左直接短语称为句型的（ ）。
21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（ ）文法。 22.对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( )策略。
23.如果一个文法存在某个句子对应两棵不同的语法树， 则称这个文法是( )。 24.最右推导亦称为（ ），由此得到的句型称为（ ）句型。
25.语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法。
26.对于文法G，仅含终结符号的句型称为 ( )。
27.所谓自上而下分析法是指（ ）。 28.语法分析器的输入是（ ），其输出是（ ）。 29.局限于基本块范围的优化称（ ）。
30.预测分析程序是使用一张（ ）和一个（ ）进行联合控制的。 31.2型文法又称为（ ）文法；3型文法又称为（ ）文法。 32.每条指令的执行代价定义为（ ）。 33.算符优先分析法每次都是对（ ）进行归约。
答案 1.(最右推导） 2.(词法分析），（语法分析），（中间代码生成），（代码优化），（目标代码生成） 3.(二义性的） 4.(执行性），（说明性） 5.(单词符号），（语法单位）。 6.(源程序），（单词符号） 7.(类型、种属、所占单元大小、地址） 8.(现行活动记录地址和所有外层最新活动记录的地址) 9.(句柄） 10.(栈式)，（堆式） 11.(类型)，（作用域） 12.(传地址），（传值），（传名） 13.(局部优化），（循环优化），（全局优化） 14.(自上而下），（自下而上） 15.(分析表），（符号栈） 16.(传地址），（传值），（传名） 17.(初），（终） 18.(局部优化），（循环优化），（全局优化） 19.(语法），（语义） 20.(句柄） 21.(LL(1) 文法） 22.(静态），（动态） 23.(二义性文法） 24.(规范推导），（规范） 25.(自上而下），（自下而上） 26.(句子) 27.(从开始符号出发，向下推导，推出句子） 28.(单词符号），（语法单位） 29.(局部优化） 30.(分析表），（符号栈） 31.(上下文无关文法），（正规） 32.(指令访问主存次数加1） 33.(最左素短语） 三． 解答题（共60分）
1． （共15分）已知文法G[E]: E→ETE|（E）|i T→*|+
（1） 将文法G改造成LL（1）文法；（5分） （2） 构造文法G中每个非终结符的FIRST集合及FOLLOW集合；（5分）（3） 构造LL（1）分析表。（5分）
2． （共12分）给定文法G[S]：S→S(S)|ε （1） 给出句子(()())()()的规范推导过程；（4分） （2） 指出每步推导所得句型的句柄；（4分） （3） 画出该句子的语法推导树。（4分） 答案 1．（1）文法存在左递归，消除左递归后的文法为： E→(E)E’|i E’（2分） E’→TEE’|ε （2分） T→*|+ （1分）
（2）(5分)没考虑#扣0.5分，其它错或少写一个扣0.5分
FIRST(E)={(,i} FIRST(E’)={*,+, ε} FIRST(T)={*,+}
FOLLOW(E)={),*,+,#} FOWLLOW(E’)= {),*,+,#} FOLLOW(T)={(,i} 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 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 的分析过程。
8.写一个文法G, 使其语言为 L(G)={albmclanbn | 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.基本的优化方法有哪几种？
14.写一个文法G, 使其语言为 L(G)={abncn | 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}，则正规式a*b|b*a 表示的正规集是什么？
19.何谓DISPLAY表？其作用是什么？
20.考虑下面的程序：
procedure p(x, y, z)； begin y:=y+2; z:=z+x; end begin a:=5; b:=2;
p(a+b, a-b, a); print a end.
试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么?
21.写一个文法G, 使其语言为 L(G)={anbncm | 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
4.传地址 A=6, B=16 传值 A=2, B=4 5.L(G)={danbm |n>0, m≥0} 6.证明：
因为文法G[S]存在句子aa有两个不同的最左推导，所以文法G[S]是是二义性的。 S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa 8.所求文法是G[S]: S→AB
A→aAc | D D→bD | b B→aBb | aabb
10.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化
11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。 应着重考虑的问题：
(1)如何使生成的目标代码较短；
(2)如何充分利用寄存器，以减少访问内存次数； (3)如何充分利用指令系统的特点。
12.正规式 a ( a | b )*。
13.删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。 14.文法G[S]:
S→aB | a B→bc |bBc
15.传值 a=2 传地址 a=15 16.逆波兰式: abcd-*e/+
三元序列: op arg1 arg2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3) 17.证明：
因为文法G[S]存在句子 () 有两个不同的最左推导，所以文法G[S]是是二义性的。 A=>AA=>(A)A=>()A=>() A=>AA=>A=>(A)=>() 18.(a*b|b*
a)={a,b,ab,ba,aab,bba??}
19.Display表: 嵌套层次显示表
由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display表就是用于登记每个外层过程的最新活动记录起始地址。 20.传地址 a=12 传值 a=5 21.所求文法是G[S]: S→AC A→aaAbb | ab C→ccC | cc
23.一个文法G别是LL(1)文法的充要条件是: (1) FIRST(α) ∩FIRST(β)=Ф (2) 如果 β=*
>ε, FIRST(α) ∩FOLLOW(A)= Ф 24.消除左递归 S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF | +a
提公共左因子,文法 G’(S) S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF’ F’→F |ε
25.作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。 主要技术：线性表，对折查找，杂奏技术。 三、简答题：（每题7分，共28分）
（说明：将答案写在试卷后面的答题纸上） 1、已知文法G[E]
E->E+T|E-T|T T->T*F|T/F|F F->(E)|i
证明（F+T）-T*(E-T)是文法的句型，并给出该句型的短语、直接短语和句柄。 2、给出语句While（A If(C 4、已知文法G：S->aBc|bAB A->aAb|b B->b| 判断该文法是否是LL（1）文法，并说明理由。 四、综合题：（共27分） （说明：将答案写在试卷后面的答题纸上） 1、已知正规式1（0|1）*101构造一个最小化的DFA。（15分） 2、已知文法G[A]:A→(A)|a,构造该文法的LR（0）分析表。（12分）
郑州大学编译原理试卷及答案(往年试题整合)
