编译原理与技术练习题汇总.doc

练习 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) ((e|0)1)*)*
(3) (a|b)*a(a|b|e)
(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|e)b*)*这三个正规式是等价的：
(1) 仅用正规式的定义及其代数性质；
(2) 从正规式构造的最小DFA的同构来证明正规式的等价。
2.11 构造有限自动机M，使得
(1) L(M) = {anbn | n ³ 1}；
(2) L(M) = {anbncn | n ³ 1}；
(3) 它能辨认S＝{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：
(a)
a
1
0
a,b
b

(b)
a
4
0
a,b
a
1
2
3
a
b
b
b
a

(c)
e
a
b
F
A
a,b
B
C
D
e
b
b
a
S
E
e
e

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→AS | a
(5) S→ aSS S→a
(6) A → 0B | 1C B → 1 | 1A | 0BB C → 0 | 0A | 1CC
3.7 设已给文法G3.31=(VN,VT,P,S)，其中：
VN = {S}
VT = {a1,a2,…,an,∨,∧, ~, [,]}
P = {S→ai| 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={anbbn| 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) { an bn am bm | n, m≥0}。
(2) { 1n 0m1m 0n | n, m≥0}。
(3) { wcwT | w∈{a, b}*}，其中wT是w的逆。
(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=(VN,VT,P,S)为CFG，α1,α2,…,αn为V上的符号串，试证明：
若 α1α2…αnβ 则存在V上的符号串β1,β2，…,βn，使β=β1β2…βn，且有 aiβi (i=1,2,…,n)。
3.20 设G=(VN,VT,P,S)为CFG，α和β都是V上的符号串，且α β，试证明：
(1) 当α的首符号为终结符号时，β的首符号也必为终结符号；
(2) 当β的首符号为非终结符号时，则α的首符号也必为非终结符号。
3.21 写出下列语言的3型文法：
(a) {an | n≥0}
(b) {anbm | n, m≥1}
(c) {anbmck | 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 | e
F → x | e
(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 根据下列优先关系矩阵计算其优先函数，并说明优先函数是否存在。

S
A
B
a
b
c
S

≯
A
≮
≮
≌
≮
≮

B

≌
a
≌
≮

≮
≯
b
≯
≯
≯
≯
≯
≌
c

≯

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 | e
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 → e
B → e
（1）证明它是LL(1)文法，但不是SLR(1)文法；
（2）证明所有LL(1)文法都是LR(1)文法。
5.14 对于下列各个文法，判断它是哪类最简朴的LR文法，并构造相应的分析表。
（1） A → AA + | AA* | a
（2） S → AB
A → aBa | e
B → bAb | e
（3） S → D; B | B
D → d | e
B → B; a | a| e
（4） S → D; B | B
D → d | e
B → B; a | a| e
（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程序的运营时环境构造出一个也许的组织结构，要保证对AVE的调用时存在的一个存储器指针（参考7.4节）。
REAL A(SIZE), AVE
INTEGER N, I
10 READ *, N
IF (N .LE. 0 .OR. N .GT. SIZE) GOTO 99
READ *, (A(I), I=1, N)
PRINT *, ‘AVE = ‘, AVE(A, N)
GOTO 10
99 CONTINUE
END
REAL FUNCTION AVE (B, N)
INTEGER I, N
REAL B(N), SUM
SUM = 0.0
DO 20 I=1, N
20 SUM = SUM+B(I)
AVE = 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;
end; { p }
begin { pascal1 }
p;
end.
7.13 使用显示表display重做练习7.12。
7.14 对下面的Pascal程序，分别画出程序执行到点（1）和（2）时刻的运营时栈的内容。
program pascal2 (input, output);
var i: integer; d: integer;
procedure a ( k: real );
var p: char;
procedure b;
var c: char;
begin
...(1)...
end: {b}
procedure c;
var t: real;
begin
...(2)...
end: {c}
begin
......
b;
c;
......
end; {a}
begin { pascal2 }
......
a (d);
......
end.
7.15 使用显示表display重做练习7.14。
7.16 实现栈式动态存储管理的一个问题是，如何分派空闲块。请考虑有几种空闲块的分派策略，并比较每个策略的优缺陷。
7.17 了解面向对象语言（如面向对象Pascal、C++、C#、Java）是如何实现垃圾搜集任务的。
7.18 存储紧缩有时也称为“单空间复制”，以区别双空间复制，请指出两者的相同之处和差异。
7.19 为以下的C++类画出对象的存储器框架和虚拟函数表（参考7.6.3节）：
class A
{ public:
int a;
virtual void f();
virtual void g();
};
class B: public A
{ public:
int b;
virtual void f();
void h();
}；
class C: public B
{ public:
int c;
virtual void g();
}

练习 8
8.1 语义分析的基本任务是什么？请简朴说明它们可以在编译的哪些阶段或者由编译的哪些模块完毕？
8.2 考虑下列无符号数的简朴语法：
number ® digit number | digit
digit ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
写出计算number整数值的属性规则。
8.3 根据下列文法，给出求十进制浮点数的值的语义规则（提醒：用属性count表达小数点后的数字数目）：
num ® num.num
num ® num digit | digit
digit ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
8.4 考虑下面的简朴的Pascal风格的声明：
decl ® var-list：type
var-list ® var-list，id | id
type ® integer | real
（1）为它设计一个计算变量类型的属性文法；
（2）为每个产生式相应的属性文法划一个依赖图；
（3）为声明a, b, c: real画出属性依赖图。
8.5 修改例8.4中的文法G8.3，使之只用综合属性就可以计算based-num的值。
8.6 考虑下列属性文法：
文法规则
语义规则
S ® ABC
B.u := S.u
A.u := B.v + C.v
S.v := A.v
A ® a
A.v := 2*A.u
B ® b
B.vl := B.u
C ® c
C.v := 1

(1) 构造出串abc的分析树及其属性依赖图，并给出计算这些属性的一个对的顺序；
(2) 假设S.u在属性求值之前的值是3，那么S.v在属性求值之后的值是什么？
(3) 假如语义规则修改如下，问题（2）的结果如何？
文法规则
语义规则
S ® ABC
B.u := S.u
C.u := A.v
A.u := B.v + C.v
S.v := A.v
A ® a
A.v := 2*A.u
B ® b
B.vl := B.u
C ® c
C.v := C.u - 2

8.7 设计有向图的一个拓扑排序算法，并用高级程序语言实现。
8.8 一个包含了综合属性和继承属性的属性文法中，假如综合属性依赖于继承属性（以及其它综合属性），但是继承属性不依赖任何综合属性，那么，用一趟混合的后序遍历和前序遍历就可以计算所有的属性值。请用高级语言或伪代码设计这个算法。
8.9 例8.11中的三个属性isFloat、etype和val的语义规则如表8.8所示，它们需要遍历分析树或语法树两次才干计算出来。第一遍后序遍历计算出综合属性isFloat的值，第二遍用混合的前序遍历和后序遍历计算出继承属性etype与综合属性val的值。
（1）请用高级语言或伪代码设计这个算法；
（2）描述5/2/2.0属性的计算过程。
8.10 请按照例8.14中的语义规则，画出float x, y的带属性的分析树以及依赖关系图。
8.11 考虑文法
S ® ( L ) | a
L ® L, S | S
（1）写一个打印括号对数的属性文法；
（2）写一个翻译模式，它输出每个a的嵌套深度。例如，对于输入串(a, (a, a))的输出是1，2，2。
（3）写一个翻译模式，它打印出每个a在句子中的位置。例如，对于输入串(a, (a, a))的结果是2，5，7。
8.12 下列文法由S符号开始产生一个二进制数，令综合属性val给出该数的值：
S ® L.L | L
L ® LB | B
L ® 0 | 1
请设计求S.val的属性文法。其中B的唯一综合属性c给出由B产生的二进位的结果值。例如，输入101.101时，S.val是5.625，其中第一个二进位的值是4，最后一个二进位的值是0.125。
8.13 考虑下列类似于C语言包含赋值语句的表达式的文法
S ® E
E ® E := E | E + E | (E) | id
即b := c表达把c的值赋给b的赋值表达式，而a:= ( b:= c)表达c的值赋给b后再赋给a。试构造语义规则，检查表达式的左部是一个左值。提醒：同非终结符E的继承属性side表达生成的表达式出现在赋值运算符的左边还是右边。
8.14 请根据例8.5的属性文法，
（1）把语义规则翻译成LR属性求值器的栈操作代码（参考例8.12）；
（2）建立相应的翻译模式；
（3）消除基础文法的左递归，对新增的符号增长综合属性和继承属性，编写无左递归的翻译模式;
（4）编写它的递归下降属性求值器。
8.15 为下列类型写出类型表达式
（1）指向实数的指针数组，下标范围从1到100；
（2）二维数组，行的下标从1到10，列的下标从－10到10；
（3）一个函数，它的定义域是从整型到整型指针的函数，值域是一个实型和字符组成的记录。
8.16 对下面C语言的声明：
typedef struct {
int a,b:
} CELL, *PCELL;
CELL foo[100];
PCELL bar(x, y) int;
CELL y;
{...}
试为类型foo和函数bar写出类型表达式。
8.17 下列是一个包含文字串表的文法，其中符号的含义和图8.15中的同样。只是增长了类型list，它表达一个元素表，表中类型由of 后面的类型T拟定。试设计一个翻译模式/语义规则，拟定表达式(E)和(L)的类型。
P ® D; E
D ® D; D | id:T
T ® list of T | char | integer
E ® (L) | literal | num | id
E ® E; L | E
8.18 修改表8.15的语义规则，使之可以解决
（1）有值语句。赋值语句的值是赋值号:=右边表达式的值；条件语句和循环语句的值是语句体的值；顺序语句的值是该序列中最后一个语句的值；
（2）布尔表达式。增长逻辑运算符and、or和not以及关系运算符、<、≤、=、>和≥，并且增长相应的翻译规则，给出这些表达式的类型。

练习 9
9.1 把下列表达式变换成后缀式：
（1）2＋3＋a＋b
（2）a*b + 2*c*d
（3）(x := x +3) *4
（4）(x := y := 2) + 3*(x := 4)
9.2 把下列表达式变换成后缀式：
（1）(not A and B) or (C or not D)
（2）(A or B) and (C or not D and E)
（3）if (x+y) *z = 0 then (a+b) *c else (a*b) +b
（4）a[a[i]] = b [ j+2]
9.3 请把do S while E和for (V = E1; E2; E3) S形式的循环语句写成后缀式。
9.4 假如允许解决过程递归，还需要改变表9.7的翻译模式。在产生式D ® proc id; N D1; S的S之前，执行语义动作把id插入其直接外围过程的符号表。请通过引入非终结符R及其e产生式，修改表9.7的语义动作，使它可以解决递归过程调用。
9.5 请根据表9.7的语义动作，补充图9.4中