文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即
L(G)={x| S?*x，其中S为文法开始符号，且x?VT? } 简单的说，文法描述的语言是该文法一切句子的集合。
四、简答题(共4小题，每小题5分，共20分)
1．编译程序和高级语言有什么区别?
用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器 语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程 的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转 换过的叫目标程序，也就是机器语言。
编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来 将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。 解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令， 然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序 止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的\对话\，随时 可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将 级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快， 在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。 2．编译程序的工作分为那几个阶段?
词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)， 而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为 编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。 3．简述自下而上的分析方法。
所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的 开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。 4．简述代码优化的目的和意义。
代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行 一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目 标程序运行时所需要的时间短，同时所占用的存储空间少。
五、综合应用题(共3小题，每小题10分，共30分)
1．证明下述文法G：
S?aSbS|aS|d
是二义性文法。 解：
一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个 文法是二义性文法。
句子aadbd有两棵语法树。如下图： S S a S S a S b a S d 第31页共6页 d a S d
b S d
(1) (2)
由此可知，S?aSbS|aS|d定义的文法是二义性文法。 2．对于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短语、直接短语和句柄？
S
句型baSb的语法树如图五(2)所示。
A B
b B S b
a 解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。
3．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中： ? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和状态转换图。
解：状态转换距阵为： ? A B C 状态转换图为
0 C ? ? 1 A，B C C 1 1 AB1 1 C10 《编译原理》期末试题（六）
编译原理 样题
【 】1．____型文法也称为正规文法。
[A] 0 [B] 1 [C] 2 [D] 3
第32页共6页
【 】2．____文法不是LL(1)的。
[A] 递归 [B] 右递归 [C] 2型 [D] 含有公共左因子的 【 】3． 文法E→E+E|E*E|i的句子i*i+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．表达式a-(-b)*c的逆波兰表示为 。
[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-* （注：@为单
目减运算符）
【 】8．过程的DISPLAY表记录了 。
[A]过程的连接数据 [B]过程的嵌套层次 [C]过程的返回地址 [D]过程的入口地址
二 填空题
3．对于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的语言相同），则称文法G1和G2是等价的。
4．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是T ，最左素短语是 T*F。 5．最右推导的逆过程称为规范归约 ，也称为 最左归约。
6．规范规约中的可规约串是句柄 ，算符优先分析中的可规约串是 最左素短语 7．（A∨ B）∧（C∨ ?D∧ E） 的逆波兰式是ＡＢ∨ＣＤ?Ｅ∧∨∧。 8．在属性文法中文法符号的两种属性分别称为继承属性 和综合属性（次序可换）。 9．符号表的每一项是由名字栏和 地址分配 两个栏目组成。在目标代码生成阶段，符号表是 地址分配 的依据。
10．一个过程的DISPLAY表的内容是它的 直接外层 的DISPLAY表的内容加上本过程的SP的地址
三 有穷自动机M接受字母表?＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的DFA M及和M等价的正规式。 【】【】
第33页共6页
四 证明正规式(ab)*a 与正规式a(ba)*等价 （用构造他们的最小的DFA方法）。
【
答
案
：
】
五 写一个文法，使其语言是：
L ＝ { 1n0m1m0n | m,n≥0 }
【】【】五 文法G：S → 1S0 | A
A → 0A1 | ε
六 对文法G[S]
S → aSb | P
P → bPc | bQc
第34页共6页
Q → Qa | a
(1) 它是否是算符优先文法？请构造算符优先关系表
(2) 文法G[S]消除左递归、提取左公因子后是否是LL（1）文法？请
证实。
【】【】1.求出G[S]的FIRSTVT集和LASTVT集：
FIERSTVT（S）={a,b} LASTBVT（S）={b,c}
FIERSTVT(P)={b} LASTBVT（P）={c} FIERSTVT(Q)={a} LASTBVT（Q）={a} 构造优先关系表为：
a b c a b c < > < < > > > > 由于在优先关系中同时出现了aa以及b
2. 消除左递归和提取左公因子后的文法为：
S → aSb | P P → bP’ P’→ Pc |Qc Q → aQ’ Q’→ aQ’|ε
求具有相同左部的两个产生式的Select集的交集：
Select(S→aSb)∩Select(S→P) = {a}∩First(P) = {a}∩{b} = Ф
Select(P’→Pc)∩Select(P’→Qc) = First(P)∩First(Q)={b}∩{a}= Ф Select(Q’→aQ’)∩Select(Q’→ε) = {a}∩Follow(Q) = {a}∩{c} = Ф 所以修改后的文法是LL（1）文法。
七 已知文法G为:
（0） S′→ S （1） S → aAd （2） S → bAc （3） S → aec （4） S → bed （5） A → e
试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。 【】【答案：】 S I1：S′→S · , I0: # S′→· S , d # a A I4：S→aA· d , I8：S→aAd · , I2： S→· aAd , # S→a · Ad , # # e I：S→ae·S→a · ec , # c , c I：5 , 9S→aec ·S→ · bAc , A→· e , d # # # A→e · , d S→ ·aec , I10： b # I3: S→b · Ac , # A S→bAc · , 第35页共6页 I6: S→bA·c,# c S→b · ed , # A→· e , c# e I7：S→be · d ,