价的目标程序。

3．简述自下而上的分析方法。

所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的

开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。

4．简述代码优化的目的和意义。

代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行

一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目

标程序运行时所需要的时间短，同时所占用的存储空间少。

五、综合应用题(共3小题，每小题10分，共30分) 1．证明下述文法G：

S

是二义性文法。 解：

一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个

文法是二义性文法。

49 / 81

句子有两棵语法树。如下图：

S a S S a S b S a

S d

a

S b

S d

d d

(1) (2)

由此可知，S定义的文法是二义性文法。 2．对于文法G[S]：S，A

，S B求句型的全部短语、直接短语和句柄？

句型的语法树如图五(2)A 所示。 B b

B S

b

a

50 / 81

解：为句型的相对于S的短语，为句型的相对于A的短语，为句型的相对于B的短语，且为直接短语，a为句型的相对于B的短语，且为直接短语和句柄。

3．设有非确定的有自限动机 ({A，B，C}，{0，1}，{C})，其中： (A，0)={C}

(A，1)={A，B}

(B，1)={C}

1)={C}。请画出状态转换距阵和状态转换图。 解：状态转换距阵为：

? 0 1 A C A，B B ? C C ? C

状态转换图为 1 1 A1 B 1 C1 0

51 / 81

{A}，

(C，，

《编译原理》期末试题（六）

编译原理 样题

【 】1．型文法也称为正规文法。

[A] 0 [B] 1 [C] 2 [D] 3 【 】2．文法不是(1)的。

[A] 递归 [B] 右递归 [C] 2型 [D] 含有公共左因子的

【 】3． 文法E→*的句子i**i的不同语法分析树的总数为。 [A]1 [B]3 [C]5 [D]7 【 】4．四元式之间的联系是通过 实现。

[A]临时变量 [B]指示器 [C]符号表 [D]程序变量

【 】5．同心集合并可能会产生的新冲突为 。 [A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约

【 】6．代码优化时所依据的是 。

[A]语法规则 [B]词法规则 [C]等价变换规则 [D]语义规则

【 】7．表达式()*c的逆波兰表示为 。

[A]* [B]*- [C] [D]* （注：@为单目减运算符）

【 】8．过程的表记录了 。

52 / 81