练习1
1.1 为什么高级程序语言需要编译程序？
1.2 解释下列术语：
源程序，目标程序，翻译程序，编译程序，解释程序
1.3 简单叙述编译程序的主要工作过程。
1.4 编译程序的典型体系结构包括哪些构件，主要关系如何，请用辅助图示意。
1.5 编译程序的开发有哪些途径？了解你熟悉的高级编程语言编译程序的开发方式。
1.6 运用编译技术的软件开发和维护工具有许多类，简单叙述每一类的主要用途。
1.7 了解一个真实编译系统的组成和基本功能。
1.8 简单说明学习编译程序的意义和作用。
1.9 如果机器H上有两个编译：一个把语言A翻译成语言B，另一个把B翻译成C，那么可以把第一个编译的输出作为第二个编译的输入，结果在同一类机器上得到从A到C的编译。请用T形图示意过程和结果。
练习2
2.1 词法分析器的主要任务是什么？
2.2 下列各种语言的输入字母表是什么？
(1) C
(2) Pascal
(3) Java
(4) C#
2.3 可以把词法分析器写成一个独立运行的程序，也可以把它写成一个子程序，请比较各自的优劣。
2.4 用高级语言编写一个对C#或Java程序的预处理程序，它的作用是每次调用时都把下一个完整的句子送到扫描缓冲区，去掉注释和无用的空格、制表符、回车、换行。
2.5 用高级语言实现图2.5所示的Pascal语言数的状态转换图。
2.6 用高级语言编程实现图2.6所示的小语言的词法扫描器。
2.7 用自然语言描述下列正规式所表示的语言：
(1) 0(0|1)*0
(2) ((ε|0)1)*)*
(3) (a|b)*a(a|b|ε)
(4) (A|B|...|Z)(a|b|...|z)*
(5) (aa|b)*(a|bb)*
(6) (0|1|...|9|A|B|C|D|E)+(t|T)
2.8 为下列语言写正规式
(1) 所有以小写字母a开头和结尾的串。
(2) 所有以小写字母a开头或者结尾（或同时满足这两个条件）的串。
(3) 所有表示偶数的串。
(4) 所有不以0开始的数字串。
(5) 能被5整除的10进制数的集合。
(6) 没有出现重复数字的全体数字串。
2.9 试构造下列正规式的NFA，并且确定化，然后最小化。
(1) (a|b)*a(a|b)
(2) (a||b)*a(a|b) *
(3) ab((ba|ab)*(bb|aa))*ab
(4) 00|(0|1)*|11
(5) 1(0|1)*01
(6) 1(1010*|1(010)*1*0
2.10 请分别使用下面的技术证明(a|b)*，(a*|b*)*以及((a|ε)b*)*这三个正规式是等价的：
(1) 仅用正规式的定义及其代数性质；
(2) 从正规式构造的最小DFA的同构来证明正规式的等价。
2.11 构造有限自动机M，使得
(1) L(M) = {anbn | n ≥ 1}；
(2) L(M) = {anbncn | n ≥ 1}；
(3) 它能识别∑＝{0, 1}上0和1的个数都是偶数的串；
(4) 它能识别字母表{0, 1}上的串，但是串不含两个连续的0和两个连续的1；
(5) 它能接受形如±dd*，±d*E和±dd的实数，其中d={0，1，2，3，4，5，6，7，8，9}。
(6) 它能识别{a, b}上不含子串aba的所有串。
2.12 分别将下列NFA确定化，并画出最小化的DFA：
(b) (c)
(a)
2.13 下面是URL的一个极其简化的扩展正规式的描述：
letter → [A-Za-z]
digit → [0-9]
letgit → letter| digit
letgit_hyphen → letgit | _
letgit_hyphen_string → letgit_hyphen | letgit_hyphen letgit_hyphen_string
label → letter (letgit_hyphen_string? letgit)？
URL → (label.)*label
(1) 请将这个URL的扩展正规改写成只含字母表{A, B, 0, 1, _, .}上符号的正规式；
(2) 构造出识别（1）更简化的URL串的有限自动机。
2.14 用某种高级语言实现
(1) 将正规式转换成NFA的算法；
(2) 将NFA确定化的算法；
(3) 将DFA最小化的算法。
2.15 描述下列语言词法记号的正规表达式：
(1) 描述C浮点数的正规表达式。
(2) 描述Java表达式的正规表达式。
2.16 Pascal语言的注释允许两种不同的形式：花括弧对{...}，以及括弧星号对(*...*)。
(1) 构造一个识别这两种注释形式的DFA；
(2) 用Lex的符号构造它的一个正规式。
2.17 写一个Lex输入源程序，它将产生一个把C语言程序中（注释除外）的保留字全部大写。
练习3
3.1对于文法G3.26[E]
E→ T | E+T | E-T
T→ F | T*F | T/F
F→ (E) | i
证明(i+T)*i是它的一个句型。
3.2 给定文法G3.27[S]
S→ aAcB | BdS
B→ aScA | cAB | b
A→ BaB | aBc | a
试检验下列符号串中哪些是G3.27 [S]中的句子。
(1) aacb
(2) aabacbadcd
(3) aacbccb
(4) aacabcbcccaacdca
(5) aacabcbcccaacbca
3.3 考虑文法G3.28[S]
S→ (L) | a
L→ L, S | S
(1) 指出该文法的终结符号及非终结符号。
(2) 给出下列各句子的语法分析树：
①(a,a) ②(a,(a, a)) ③(a, ((a, a), (a, a)))
(3) 分别构造(b)中各句子的一个最左推导和最右推导。3.4 考虑文法G3.29[S]
S→aSbS | bSaS |ε
(1) 讨论句子abab的最左推导，说明该文法是二义性的。
(2) 对于句子abab构造两个相应的最右推导。
(3) 对于句子abab构造两棵相应的分析树。
(4) 此文法所产生的语言是什么？
3.5 文法G3.30[S]为：
S→ Ac | aB
A→ ab
B→ bc
写出L(G3.30)的全部元素。
3.6 试描述由下列文法G[S]所产生的语言。
(1) S→ 10S0 | aA A→bA | a
(2) S→ SS | 1A0 A→1A0 | ε
(3) S→ 1A | B0 A→1A | C B→B0 | C C→1C0 | ε
(4) S→ bAdc A→A S | a
(5) S→ aSS S→a
(6) A → 0B | 1C B → 1 | 1A | 0BB C → 0 | 0A | 1CC
3.7 设已给文法G3.31=(V N,V T,P,S)，其中：
V N = {S}
V T = {a1,a2,…,a n,∨,∧, ~, [,]}
P = {S→a i| i=1,2,…,n}∪{S→ ~S, S→[ S∨S］, S → [ S∧S］}，
试指出此文法所产生的语言。
3.8 已知文法G3.32=({A,B,C},{a,b,c},A,P)，其中P由以下产生式组成：
A →abc A →aBbc
Bb →bB Bc →Cbcc
bC →Cb aC →aaB
aC →aa
问：此文法表式的语言是什么？
3.9 已知文法G3.33 [P]:
P → aPQR |abR
RQ → QR
bQ → bb
bR → bc
cR → cc
证明aaabbbccc 是该文法的一个句子。
3.10 构造一个文法，使其产生的语言是由算符+, *, (, ) 和运算对象a构成的算术表达式的集合。
3.12 已知语言L={a n bb n| n≥1}, 写出产生语言L的文法。
3.13 写一文法，使其语言是偶正整数的集合。要求：
(1) 允许0打头。(2) 不允许0打头。
3.14 文法G3.34 [S]为：
S→ Ac|aB, A→ ab
B→ bc
该文法是否为二义的？为什么？（提示：找一个句子，使之有两棵不同的分析树。）
3.15 证明下述文法G3.35［〈表达式〉］是二义的：
〈表达式〉→ a | (〈表达式〉) |〈表达式〉〈运算符〉〈表达式〉
〈运算符〉→+ | - | * | /
3.16 下面的文法产生a的个数和b的个数相等的非空a、b串
S→ aB | bA
B→ bS | aBB | b
A→ aS | bAA | a
其中非终结符B推出b比a的个数多1个的串，A则反之。
(1) 证明该文法是二义的。
(2) 修改上述文法，不增加非终结符，使之成为非二义文法，并产生同样的语言。
3.17 考虑文法G3.36[R]
R→R '|' R | RR | R* | (R) | a | b
其中R '|' R表示R或R；RR表示R与R的连接；R*表示R的闭包。
(1) 证明此文法生成∑={a, b}上的除了?和ε的所有正规表达式。
(2) 试说明此文法是二义性的。
(3) 构造一个等价的无二义性文法，该文法给出*、连接和|等运算符号的优先级和结合规则。
3.18 给出产生下述语言的上下文无关文法：
(1) { a n b n a m b m | n, m≥0}。
(2) { 1n 0m1m 0n | n, m≥0}。
(3) { ωcωT | ω∈{a, b}*}，其中ωT是ω的逆。
(4) { w | w∈{a,b}+，且w中a的个数恰好比b多1 }。
(4) { w | w∈{a,b}+，且|a|≤|b|≤2|a| }。
(5) { w | w是不以0开始的奇数集}。
3.19 设G=(V N,V T,P,S)为CFG，α1,α2,…,αn为V上的符号串，试证明：
若α1α2…αnβ 则存在V上的符号串β1,β2，…,βn，使β=β1β2…βn，且有a iβi(i=1,2,…,n)。
3.20 设G=(V N,V T,P,S)为CFG，α和β都是V上的符号串，且αβ，试证明：
(1) 当α的首符号为终结符号时，β的首符号也必为终结符号；
(2) 当β的首符号为非终结符号时，则α的首符号也必为非终结符号。
3.21 写出下列语言的3型文法：
(a) {a n| n≥0}
(b) {a n b m | n, m≥1}
(c) {a n b m c k | n, m, k≥1}
3.22 已知文法G3.37 [S]：
S→ dAB
A→ aA|a
B→ε |Bb
给出相应的正规式和等价的正规文法。
3.23 给出下列文法G[A]消除左递归后的等价文法：
(1) A→ BaC | CbB
B→ Ac | c
C→ Bb | b
(2) A → B a | A a | c
B → B b | A b | d
(3) S→ SA | A
A→ SB | B | (S) | ( )
B→ [S] | [ ]
(4) S→ AS | b
A→ SA | a
(5) S→ (T) | a | ε
T→ S | T, S
练习4
4.1 证明：含有左递归的文法不是LL(1)文法。
4.2 对于文法G4.11[S]
S → uBDz
B → Bv | w
D → EF
E → y | ε
F → x | ε
(1) 计算文法G4.11各非终结符的FIRST集和FOLLOW集，以及各产生式的SELLECT集。
(2) 判断该文法是否是LL(1)文法。
(3) 若不是LL(1)文法，则修改此文法, 使其成为能产生相同语言的LL(1) 文法。
4.3 已知布尔表达式文法G4.12[bexpr]
bexpr→ bexpr or bterm | bterm
bterm→ bterm and bfactor | bfactor
bfactor→ not bfactor | (bexpr) | true | false
改写文法G4.12为扩充的巴克斯范式，并为每个非终结符构造递归下降分析子程序。
4.4已知用EBNF表示的文法G4.13[A]
A→ [ B
B→ X ] {A}
X→ (a | b) {a | b}
试用类C 或类PASCAL 语言写出其递归下降子程序。
4.5 已知文法G4.14[S]
S→ (L) | a
L→ L, S | S
(1) 消除文法G4.14的左递归，并为每个非终结符构造不带回溯的递归子程序。
(2) 经改写后的文法是否是LL(1)文法？给出它的预测分析表。
(3) 给出输入串(a, a)$ 的分析过程，并说明该符号串是否为文法G4.14的句子。
4.6 对于文法G4.15[R]
R → R ' | ' T | T
T → TF | F
F → F* | C
C → (R) | a | b
(1) 消除文法的左递归。
(2) 计算文法G4.15各非终结符的FIRST集和FOLLOW集。
(3) 构造LL(1)分析表。
4.7 已知文法G4.16[A]
A→ aABe | a
B→ Bb | d
(1) 判断该文法是否为LL(1) 文法。
(2) 写出输入串aade$ 的分析过程。
练习5
5.1 设文法G5.10[E]为
E → E+T | E-T | T
T → T*F | T/F | F
F → F↑P | P
P → (E) | i
求以下句型的短语、直接短语、素短语、句柄和最左素短语：
（1）E-T/F+i
（2）E+F/T-P↑i
（3）T*(T-i)+P
（4）(i+i)/i-i
5.2 根据下列优先关系矩阵计算其优先函数，并说明优先函数是否存在。
5.3 对于文法G5.11[S]
S → (R) | a | b
R → T
T → S; T | S
（1）计算G5.11 [S]的FIRSTTV和LASTTV；
（2）构造G5.11 [S]的优先关系表，并说明G5.11 [S]是否为算符优先文法；（3）计算G5.11 [S]的优先函数。
5.4 对于文法G5.12 [S]
S → S;G | G
G → G(T) | H
H → a | (S)
T → T+S | S
（1）构造G5.12 [S]的算符优先关系表，并判断G5.12 [S]是否为算符优先文法；
（2）给出句型a(T+S);H;S的短语、直接短语、句柄、素短语和最左素短语；
（3）分别给出(a+a)和a;(a+a)的分析过程，并说明它们是否为G5.12 [S]的句子；
（4）给出（3）中输入串的最右推导，分别说明它们是否为G5.12 [S]的句子；
（5）从（3）和（4）说明算符优先分析的优缺点。
5.5 对于文法G5.13[P]
P → LAd | cd
L → c
A→ aP | P | a
请证明它不存在优先函数。
5.6 给定文法G5.14 [S]
S →AS | b
A → SA | a
（1）构造它的LR(0)的项集；
（2）构造识别该文法所有活前缀的DFA；
（3）这个文法是SLR(1)吗？若是，构造出它的SLR(1)分析表。
5.7 给定文法G5.15[S]
S →AS |
A → aA | b
（1）构造它的LR(1)文法；
（2）构造识别该文法所有活前缀的DFA；
（3）构造出它的SR(1)分析表；
（4）给出字符串abab$的分析过程。
5.8 若有定义二进制数的文法G5.16[D]
D → L . L | L
L → LB | B
B → 0 | 1
（1）通过构造该文法的无冲突的分析表来说明它是哪类LR文法; （2）给出输入串101.010的分析过程。
5.9 给定文法G5.17[S]
S → L = R| R
L → *R | id
R → L
（1）构造它的LR(0)的项集；
（2）构造它的LR(0)项集规范族；
（3）构造识别该文法所有活前缀的DFA；
（4）该文法是SLR(1)、LR(1)以及LALAR(1)？构造相应的分析表。
5.10 对于文法G5.18[S]
S → A
A → Ab | bBa
B → aAc | aAb | a
（1）证明它是SLR(1)文法，但不是LR(0)文法；
（2）证明所有SLR(1)文法都是LR(1)文法。
5.11 证明文法G5.19[M]
M → N
N → Qa | bQc | dc | bda
Q → D
是LALR(1)文法，但不是SLR(1)文法。
5.12 证明文法G5.20[S]
S → aAa | aBb | bAb | bBa
A → c
B → c
是LR(1)文法，但不是LALR(1)文法。
5.13 对于文法G5.21[S]
S → AaAb | BbBa
A →ε
B →ε
（1）证明它是LL(1)文法，但不是SLR(1)文法；
（2）证明所有LL(1)文法都是LR(1)文法。
5.14 对于下列各个文法，判断它是哪类最简单的LR文法，并构造相应的分析表。（1） A → AA + | AA* | a
（2）S → AB
A → aBa | ε
B → bAb | ε
（3）S → D; B | B
D → d | ε
B → B; a | a| ε
（4）S → D; B | B
D → d | ε
B → B; a | a| ε
（5）S → (SR | a
R → . SR | )
（6）S → UTa | Tb
T → S | Sc | d
U → US | e
5.15 命题演算的文法G5.22[B]
B → B and B | B or B | not B | (B) | true | false | b
是二义性文法。
（1）为句子b and b or true构造两个不同的最右推导，以此说明该文法是二义的。（2）为它写一个等价的非二义性文法。
（3）给出无二义性规则，构造出LR(0)分析表，并给出句子b and b or true的分析过程。
练习6
6.1 符号表的作用有哪些？
6.2 符号表的表项通常包括哪些属性，主要描述的内容是什么？
6.3 符号表组织的数据结构有哪些种？每种组织结构选取的主要依据是什么？
6.4 程序块是程序语言的主要构造元素，它允许以嵌套的方式确定局部声明。大多数语言规定，程序
块结构的声明作用域使最近嵌套规则，请按照这个规则写出下列声明的作用域。
main()
{ /* 开始块B0 */
int a = 0;
int b =0;
{ /* 开始块B1 */
int b = 1;
{ /* 开始块B2 */
int a = 2;
……
} /* 结束块B2 */
{ /* 开始块B3 */
int b = 3;
……
} /* 结束块B3*/
……
} /* 结束块B1*/
}
6.5 C语言中规定变量标识符可以定义为：extern、ertern static、auto、local static和register，请对这
5种变量分别说明其作用域。
6.6 设散列表为HT[13]，哈希函数定义为hash(key)=key%13（整数除法取余运算），用链地址法解决
冲突对下列关键码12，23，45，57，20，3，31，15，56，78造表。
练习7
7.1 请考虑过程和活动记录的联系和区别。
7.2 请解释下列概念：
生存期，过程的活动，活动树，活动记录。
7.3 有哪些常见的参数传输方式，请分析和比较它们各自的特点。
7.4 对你熟悉的高级程序语言（如C、Pascal、C++、Java或C#），了解它们的参数传输机制。
7.5 执行下面Pascal程序的输出a结果分别是什么，如果参数的传递机制是：
（1）引用调用方式；
（2）值－结果调用方式；
program copyout (input, output);
var a: integer;
procedure unsafe （var x: integer）;
begin x := 2; a := 0 end;
begin
a := 1; unsafe (a); writeln (a)
end
7.6 执行下面程序时打印的a分别是什么，若参数的传递机制是：
（1）按值调用方式；
（2）引用调用方式；
（3）值－结果调用方式；
（4）换名调用方式。
procedure p(x, y, z);
begin
y := y +1;
z := z＋x;
end p;
begin
a := 2;
b := 3;
p(a+b, a, a);
print a;
end;
7.7 设计存储分配时要考虑哪些主要因素？常见的存储分配策略有哪些？简单说明在什么情况下使
用哪种存储分配策略。
7.8 C++语言中关于变量的存储类型符有4个：auto、register、static和extern，请说明每个说明符所
表示的存储方式。
7.9 为下面FORTRAN程序的运行时环境构造出一个可能的组织结构，要保证对A VE的调用时存在
的一个存储器指针（参考7.4节）。
REAL A(SIZE), A VE
INTEGER N, I
10 READ *, N
IF (N .LE. 0 .OR. N .GT. SIZE) GOTO 99
READ *, (A(I), I=1, N)
PRINT *, ‘AVE = ‘, A VE(A, N)
GOTO 10
99 CONTINUE
END
REAL FUNCTION A VE (B, N)
INTEGER I, N
REAL B(N), SUM
SUM = 0.0
DO 20 I=1, N
20 SUM = SUM+B(I)
A VE = SUM/N
END
7.10考虑C语言中的下列过程：
void f ( char c, char s[10], double r)
{ int * x;
int y [5];
......
}
（1）使用标准C参数传递约定，利用7.5.1所描述的活动记录结构判断以下的fp的偏移：c，s[7]和y[2]（假设数据大小为：整型＝2个字节，字符＝1个字节，双精度＝8个字节，地址＝4个字节）（2）假设所有的参数都是按值传递（包括数组），重做（1）；
（3）假设所有的参数都是引用传递（包括数组），重做（1）。
7.11为下面C程序的运行时环境构造出一个可能的组织结构（参考7.5.1节）。
(1) 在进入函数f中的块A之后；
(2) 在进入函数g中的块B之后。
int a[10];
char *s = ‘hello’;
int f ( int i, int b[] )
{ int j = 1;
A: { int i = j;
char c = b[i];
......
}
return 0;
}
void g (char *s)
{ char c = s[0];
B: { int a[5]; ...... }
}
main ()
{ int x = 1;
x = f (x, a);
g (s);
return 0;
}
7.12 使用访问链（参考7.5.2节）分别画出下面Pascal程序执行到（1）第1次调用r之后的运行时栈的内容；
（2）第2次调用r之后的运行时栈的内容；
program pascal1;
procedure p;
var x: integer;
procedure q;
procedure r;
begin
x := 2;
......
if ... then p;
end; { r }
begin
r;
end; { q }
begin
q;
* 编译原理复习题 一．简答题： 1) 什么是句子？ 什么是语言? 解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T * ），则称x 是文法的一个句子。 语言——语言是句子的集合。 或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │ S x,x ∈V T * } 。 2) DFA 与NFA 有何区别 ? 解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个 开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么? 解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接 推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么? 解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图 归约到文法的开始符号。 5) 一个上下文无关文法G 包括哪四个组成部分？ 解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？
解答:关键是寻找句柄。 7)在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。 8）什么是属性文法？ 答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属 性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过 程中，完成语义规则所描述的动作，从而实现语义处理。 一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。 其中G为一个上下文无关文法；V为属性的有穷集；E为一组语义规则。 9）语法制导翻译 语法制导翻译：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。 语法制导翻译(Syntax-Directed Translations)： –一个句子的语义翻译过程与语法分析过程同时进行。 在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。属性描述语义信息， 语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义 属性值。 10）词法分析的主要任务是什么？ 解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫 描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属 11)图示运行时存储空间的划分（分为哪几个区）。 解答: 一般分为静态区和动态区： 程序代码区、静态数据区、栈区和堆区 12)常用的中间语言种类有哪几种？ 解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。 13）文法G所描述的语言是什么的集合？ 解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。 14）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？ 解答: 2型文法叫上下文无关文法。 15）常见的动态存贮分配策略有哪两种？ 解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。 16）语法分析的任务是什么？
《编译原理》模拟试题一 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×) 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ ) 4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√) 6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×) 10．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。
(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式 三、填空题(每空1分，共10分)
编译原理考试题及答案汇总 一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_C____。
第二章高级语言及其语法描述 1、设有文法G[S]： S→N N→D|ND D→0|1|2|…|9 试写出028和4321的最左推导和最右推导过程。 2、证明文法G[S]是二义性文法： S→if E then S else S |if E then S |s E→0|1 3、设有文法G[E]： E→E-T|T T→T/F|F F→i|(E) （1）试写出i/(i-i-i)的推导树。 （2）试写出（F-i）/F的短语、简单短语和句柄。 4、设∑={0,1}，请给出∑上下列语言的文法（1）所有以0开头的串 （2）所有以0开头，以1结尾的串 5、证明文法G1和G2等价 G1：S→0S1，S→01 G2：A→0R，A→01，R→A1 第三章有限状态自动机和词法分析 1、请用中文描述下列正规式表示的正规集 （1）0(0|1)*0 （2）0*10*10*10* 2、试写出∑＝{0，1}上下列集合的正则表达式：（1）所有以1开始和结束的符号串。 （2）恰含有3个1的所有符号所组成的集合。（3）集合{01，1}。
（4）所有以111结束的符号串。 3、试写出∑＝{0，1}上下述集合的正则表达式： （1）试写出非负整数集的正则表达式。 （2）试写出以非5数字为头的所有非负整数集的正则表达式。 4、试将图3.1中所示的有限状态自动机M 最小化。 图3.1 M 的状态转换图 5、设∑＝{a,b}，试构造下述正则表达式的确定性有限状态自动机： （1）a(a|b)*baa （2）(a|b)*bbb * 6、对于下列的状态转换矩阵： （1）分别画出相应的状态转换图。 （2）用自然语言分别描述它们所识别的输入串的特征 7、将图3.2所示的非确定的有限状态自动机确定化和最小化。 图3.2 非确定的有限状态自动机M 第四章 自顶向下语法分析 1、从下列文法中消去左递归。
编译原理考试题及答案汇总一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式 M 1 和 M 2 等价是指__C_。 A． M1和M2的状态数相等B． M1和M2的有向边条数相等 C． M1和M2所识别的语言集相等 D． M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A． xyx B． (xyx)* C．xnyxn(n≥0) D． x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言 C．编译方法 D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表 D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧C． AB∨┐CD∨∧ D．A┐B∨∧CD∨8. 优化可生成__D___的目标代码。 A．运行时间较短B．占用存储空间较小 C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱 B．删除归纳变量C．删除多余运算 D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x 3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4．语法分析时必须先消除文法中的左递归。X 6．逆波兰表示法表示表达式时无须使用括号。R 9．两个正规集相等的必要条件是他们对应的正规式等价。 X 1．编译程序是对高级语言程序的编译执行。X
江南大学网络教育第一阶段练习题及答案，这是其中一个阶段共3个阶段。答案在后面 考试科目:《编译原理》第章至第章（总分100分） __________学习中心（教学点）批次：层次： 专业：学号：身份证号： 姓名：得分： 一单选题 (共4题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。) 1. 若一个文法是递归的，则它所产生的语言的句子是（）。（5 分） A. 无穷多个 B. 有穷多个 C. 可枚举的 D. 个数是常量 2. 文法G[A]：A→ε A→aB B→Ab B→a是（）。（5 分） A. 0型文法 B. 1型文法 C. 2型文法 D. 3型文法 3. 词法分析器的输入是（）。（5 分） A. 单词符号串 B. 源程序 C. 语法单位 D. 目标程序 4. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一 个开始符号，以及一组（）。（5 分） A. 句子 B. 句型 C. 单词 D. 产生式 二填空题 (共2题，总分值10分 ) 5. 编译程序的功能可以分解为词法分析、语法分析、__________、中间代码生成、中间代码优 化、目标代码生成。（5 分） 6. 微小语言Micro的单词有下面的几种：标识符、__________、实常数、保留字、__________、 换行符。（5 分）
三简答题 (共2题，总分值20分 ) 7. 给出与正规式R＝1(0|1)*101等价的NFA。（10 分） 8. 写出下面程序经词法分析后的TOKEN表示。 begin var X:real; var J:integer; read(J); J:=J+(J*20); X:=J-1; Write(2*J+X) End（10 分） 四综合计算题 (共2题，总分值50分 ) 9. 已知文法G(S) S→a| (T) T→T，S|S 写出句子((a，a)，a)的规范归约过程及每一步的归约规则和句柄。（25 分）10. 已知文法 G[E] 为： E→T|E+T|E-T T→F|T*F|T/F F→（E）|i ①该文法的开始符号（识别符号）是什么？ ②请给出该文法的终结符号集合 Vt 和非终结符号集合 Vn 。 ③找出句型 T+T*F+i 的所有短语、简单短语和句柄。（25 分）
第一章 1、将编译程序分成若干个“遍”就是为了。 a．提高程序得执行效率 b．使程序得结构更加清晰 c．利用有限得机器内存并提高机器得执行效率 d．利用有限得机器内存但降低了机器得执行效率 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法d．以上三项都就是 3、变量应当。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、不可能就是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用可以定义一个程序得意义。 a．语义规则b．语法规则 c．产生规则d．词法规则 7、词法分析器得输入就是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循得就是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序就是对。 a．汇编程序得翻译b．高级语言程序得解释执行 c．机器语言得执行d．高级语言得翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 二、多项选择题 1、编译程序各阶段得工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成 三、填空题 1、解释程序与编译程序得区别在于。 2、编译过程通常可分为5个阶段，分别就是、语法分析、代码优化与目标代码生成。 3、编译程序工作过程中，第一段输入就是，最后阶段得输出为程序。
编译原理复习题及答案 一、选择题 1．一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3．下面说法正确的是(A) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A) A 必要条件 B 充分必要条件 5．下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．用高级语言编写的程序经编译后产生的程序叫(B)
A．源程序 B．目标程序C．连接程序D．解释程序 12．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 13．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器14．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 15．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 16．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 17．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 18．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 19．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 20．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 21．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba 22．设有文法G[S]：S S1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有(D) A. ab0 B. a0c01 C. a0b0a D. bc10 23．描述一个语言的文法是(B) A．唯一的 B. 不唯一的 C. 可能唯一 24．一个文法所描述的语言是(A) A．唯一的 B. 不唯一的 C. 可能唯一
二填空题 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.根据优化所涉及的程序范围，可将优化分成为（），（）
第三章复习重点：1.文法与语言的对应关系 思路要点：注意结构拆分 技巧：如何将表示语言的通用字符串形式作适当的“切割”？ 例：已知语言：L1 = {a x b2x c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。 提示：该题实际上要求为相应语言设计上下文无关文法。 一个文法设计好后，严格来说应当证明此文法是否对应于该语言。 解：G[S]：S →AB A →ε | aAbb B →ε | cB 推导过程： S ? AB +? a x Ab2x B /*使用A →aAbb x次*/ ? a x b2x B /*使用A →ε一次*/ ? a x b2x c x B /*使用B →cB x次*/ ? a x b2x c x/*使用B →ε一次*/ 举一反三：已知语言L2 = {a x b2y c y | x, y >= 0}，给出此语言的文法，并证明此语言是上下文无关语言。 解：G[S]：S →AB A →ε | aA B →ε | bBcc 练习：14：写出下列语言对应的文法 (1).{a n b n a m b m|n,m≥0}
2. {1n 0m 0m 0n |n,m ≥0} 3. {1n 0m 0m 0n |n ≥0,m>0} 4. { a n b m c k |n,m,k ≥0} G1: S —>AA G2: S —>AB A —>aAb|ε A —>aAb|ε B —>aBb|ε G: S —>1S0 S —>A A —>0A1 A —>ε G: S →1S0|A S →1S0|0A1 A →0A1|01 A →0A1|ε 2. 给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。 1. 令文法G ［E ］为： Z →bMb M →a|(L L →Ma ） ① 符号串b(Ma)b 是否为该文法的一个句型，并证明。 ② 若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。 1）（5分）证明：S=> bMb=>b(Lb=>b(Ma)b 所以，符号串b(Ma)b 是该文法的一个句型。 （2）（5分）短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma) 练习： （10分）已知文法G[T]： T →T*F | F ；F →F ↑P | P ； P →(T) | i （1）用最右推导法证明β：T*P ↑(T*F) 是G[T]的一个句型； （2）画出β的语法树； （3）写出β的全部短语、直接短语和句柄。 (1) T=>T*F=>T*F ↑P=>T*F ↑(T)=> T*F ↑(T*F) =>T*P ↑(T*F) 证毕。 (2) 如图 T T * F F ↑ P P T * T F ( ) 第3题 语法树 （3）短语：T*P ↑(T*F) ；P ↑(T*F) ；(T*F) ；T*F ；P 直接短语：T*F ；P
中南大学网络教育课程考试复习题及参考答案 编译原理 一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 ( ) 3.已经证明文法的二义性是可判定的。 ( ) 4.每个基本块可用一个DAG表示。 ( ) 5.每个过程的活动记录的体积在编译时可静态确定。 ( ) 6.2型文法一定是3 型文法。 ( ) 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 ( ) 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是 2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题： 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采用( )策略。
一、选择题（每个选择题 2 分，共 20 分） 1 ．文法 G 产生的⑴ 的全体是该文法描述的语言。 A ．句型 B. 终结符集 C. 非终结符集 D. 句子 2 ．若文法 G 定义的语言是无限集，则文法必然是⑵ ： A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的 3 ． Chomsky 定义的四种形式语言文法中， 0 型文法又称为⑶ 文法； 1 型文法又称为⑷ 文法； 2 型语言可由⑸ 识别。 A ．短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法 E 图灵机 F 有限自动机 G 下推自动机 4 ．一个文法所描述的语言是⑹ ；描述一个语言的文法是⑺ 。 A ．唯一的 B 不唯一的 C 可能唯一，好可能不唯一 5 ．数组的内情向量中肯定不含有数组的⑻ 的信息 A．维数 B.类型 C.维上下界 D.各维的界差 6 ．在下述的编译方法中，自底向上的方法有⑼ ，自顶向下的分析方法有⑽ 。 ①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析 ⑥ SLR（k）分析⑦ LL（k）分析⑧LALR（K）分析 A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧ 二、简答题（每小题 5 分，共 20 分） 1 ． LL （ 1 ）分析法对文法有哪些要求？ 2 ．常见的存储分配策略有几种？它们都适合于什么性质的语言？ 3 ．常见循环优化都有哪些项目？ 4 ．什么是活动记录？它主要由哪些内容构成？ 五、（ 12 分）已给文法 G[S] ：S → SaP | Sf | P P → qbP | q 将 G[S] 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。 七、（ 8 分）将下面的条件语句表示成逆波兰式和四元式序列： if a>b then x:=a+b*c else x:=b-a; 八、（ 8 分）给定基本块： A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。参考答案： 一、⑴ D ⑵ A ⑶ A ⑷ C ⑸ G. ⑹ A ⑺ B ⑻ A ⑼ F ⑽ A 二、 1 ．对于 G 中的每个产生式A →γ 1 | γ 2 | … | γ m ，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即 FIRST( γ i ) ∩ FIRST( γ j )= φ（1 ≤ i ，j ≤ m ；i ≠ j ）
参考答案 一、单项选择题(共10小题，每小题2分，共20分) 1．语言是 A ．句子的集合 B ．产生式的集合 C ．符号串的集合 D ．句型的集合 2．编译程序前三个阶段完成的工作是 A ．词法分析、语法分析和代码优化 B ．代码生成、代码优化和词法分析 C ．词法分析、语法分析、语义分析和中间代码生成 D ．词法分析、语法分析和代码优化 3．一个句型中称为句柄的是该句型的最左 A ．非终结符号 B ．短语 C ．句子 D ．直接短语 4．下推自动机识别的语言是 A ．0型语言 B ．1型语言 C ．2型语言 D ．3型语言 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A ． 字符 B ．单词 C ．句子 D ．句型 6．对应Chomsky 四种文法的四种语言之间的关系是 A ．L 0?L 1?L 2?L 3 B ．L 3?L 2?L 1?L 0 C ．L 3=L 2?L 1?L 0 D ．L 0?L 1?L 2=L 3 7．词法分析的任务是 A ．识别单词 B ．分析句子的含义 C ．识别句子 D ．生成目标代码 8．常用的中间代码形式不含 A ．三元式 B ．四元式 C ．逆波兰式 D ．语法树 9． 代码优化的目的是 A ．节省时间 B ．节省空间 C ．节省时间和空间 D ．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A ．把高级语言翻译成汇编语言 B ．把高级语言翻译成机器语言 C ．把中间代码变换成依赖具体机器的目标代码 装 订 线
D．把汇编语言翻译成机器语言 二、填空题（本大题共5小题，每小题2分，共10分） 1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。 5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。 三、名词解释题(共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=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。 (2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列 次序为A1A2…A R，那么A→A1A2…A R一定是P中的一条产生式。
第7节习题 一、单项选择题 1、中间代码生成所依据的是。 a.语法规则 b.词法规则 c.语义规则 d.等价变换规则 2、四元式之间的联系是通过实现的。 a.指示器 b.临时变量 c.符号表 d.程序变量 3、后缀式ab+cd+/可用表达式来表示。 a.a+b/c+d b.(a+b)/(c+d) c.a+b/(c+d) d.a+b+c/d 4、表达式（┓A∨B）∧（C∨D）的逆波兰表示为。 a. ┓AB∨∧CD∨ b. A┓B∨CD∨∧ c. AB∨┓CD∨∧ d. A┓B∨∧CD∨ 5 所对应的表达式为。 a.A+B+C+D b.A+(B+C)+D c.(A+B)+C+D d.(A+B)+(C+D) 6、四元式表示法的优点为。 a.不便于优化处理，但便于表的更动 b.不便于优化处理，但节省存储空间 c.便于优化处理，也便于表的更动 d.便于表的更动，也节省存储空间 7、终结符具有属性。 a.传递 b.继承 c.抽象 d.综合 解答 1、选c。 2、四元式之间的联系是通过临时变量实现的，故选b。 3、选b。 4、选b。 5、选d。 6、四元式表示法的优点与间接三元式相同，故选c。 7、选d。 二、多顶选择题 1、中间代码主要有。 a．四元式b．二元式c．三元式d．后缀式e．间接
三元式 2、下面中间代码形式中，能正确表示算术表达式a+b+c 的有 。 a ．ab+c+ b ．abc++ e ．a+b+c 3、在下面的 语法制导翻译中，采用拉链-回填技术。 a ．赋值语句 b ．goto 语句 c ．条件语句 d ．循环语句 4、下列 中间代码形式有益于优化处理。 a ．三元式 b ．四元式 c ．间接三元式 d ．逆波兰表示法 e ．树形表示 法 5、在编译程序中安排中间代码生成的目的是 。 a ．便于进行存储空间的组织 b ．利于目标代码的优化 c ．利于编译程序的移植 d ．利于目标代码的移植 e ．利于提高目标代码的质量 6、下面的中间代码形式中， 能正确表示算术表达式 a ．ab+c* b ．abc*+ c ．a+b*c 7、三地址代码语句具体实现通常有 表示方法。 a ．逆波兰表示 b ．三元式 c ．间接三元式 d ．树形表示 e ．四元式 解答 1、选a 、c 、d 、e 。 2、b 、d 的中间代码不能正确表示a+b+c ，而e 不是中间代码：故选a 、c 。 3、凡涉及到跳转的语句都需要采用拉链——回填技术，故选 b 、c 、d 。 4、选b 、c 。 5、选b 、d 。 6、选b 、e 。 7、选b 、c 、e 。