《编译原理与技术》练习题 11

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文法，并构造相应的分析表。

《编译原理与技术》练习题 12

（1） （2）

A → AA + | AA* | a 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的分析过程。

《编译原理与技术》练习题 13

练习 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（整数除法取余运算），用链地址法解决

冲突对下列关键码12，23，45，57，20，3，31，15，56，78造表。

《编译原理与技术》练习题 14

练习 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;

《编译原理与技术》练习题 15

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;