价的目标程序。
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