附录 部分习题参考答案
第1章参考答案：
1，2，3，4，5，6，7解答：略！
第2章参考答案：
1，2，3：解答：略！
4. 解答：
A：① B：③ C：① D：②
5. 解答：
用E表示，T表示，F表示，上述文法可以写为：
E → T | E+T
T → F | T*F
F → (E) | i
最左推导：
E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T
=>i+i+F=>i+i+i
E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
最右推导：
E=>E+T=>E+F=>E+i=>E+T+i=>E+F+i=>E+i+i=>T+i+i
=>F+i+i=>i+i+i
E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i =>i+i*i
i+i+i和i+i*i的语法树如下图所示。
i+i+i、i+i*i的语法树
6. 解答：
(1) 终结符号为：{or,and,not,(,),true,false} 非终结符号为：{bexpr,bterm,bfactor}
开始符号为：bexpr
(2) 句子not(true or false)的语法树为：
7. 解答：
(1) 把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：
S → AB
A → aAb|ab
B → cB|
(2) 令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：
S → aE|Ea|bSS|SbS|SSb
E → aEbE|bEaE|
(3) 设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式 （其中B产生1到2个b）：
第一章
1、将编译程序分成若干个“遍”就是为了 。
a．提高程序得执行效率
b．使程序得结构更加清晰
c．利用有限得机器内存并提高机器得执行效率
d．利用有限得机器内存但降低了机器得执行效率
2、构造编译程序应掌握 。
a．源程序 b．目标语言
c．编译方法 d．以上三项都就是
3、变量应当 。
a．持有左值 b．持有右值
c．既持有左值又持有右值 d．既不持有左值也不持有右值
4、编译程序绝大多数时间花在 上。
a．出错处理 b．词法分析
c．目标代码生成 d．管理表格
5、 不可能就是目标代码。
a．汇编指令代码 b．可重定位指令代码
c．绝对指令代码 d．中间代码
6、使用 可以定义一个程序得意义。
a．语义规则 b．语法规则
c．产生规则 d．词法规则
7、词法分析器得输入就是 。
a．单词符号串 b．源程序
c．语法单位 d．目标程序
8、中间代码生成时所遵循得就是- 。
a．语法规则 b．词法规则
c．语义规则 d．等价变换规则
9、编译程序就是对 。
a．汇编程序得翻译 b．高级语言程序得解释执行
c．机器语言得执行 d．高级语言得翻译
10、语法分析应遵循 。
a．语义规则 b．语法规则
c．构词规则 d．等价变换规则
二、多项选择题
1、编译程序各阶段得工作都涉及到 。
a．语法分析 b．表格管理 c．出错处理
d．语义分析 e．词法分析
2、编译程序工作时，通常有 阶段。
第一章
1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？
【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。
这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。
（在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。
在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。）
1.3 请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？
【解答】编译程序总框图如图1-1所示。
作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。
第二章
2.1 正规式M1和M2等价是指：M1和M2所识别的语言集相等。
2.2 什么是扫描器？扫描器的功能是什么？
【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。
第2章 习题解答
1.文法G[S]为：
S->Ac|aB
A->ab
B->bc
写出L(G[S])的全部元素。
[答案]
S=>Ac=>abc
或S=>aB=>abc
所以L(G[S])={abc}
==============================================
2.
文法G[N]为：
N->D|ND
D->0|1|2|3|4|5|6|7|8|9
G[N]的语言是什么？
[答案]
G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}
N=>ND=>NDD.... =>NDDDD...D=>D......D
===============================================
3.已知文法G[S]：
S→dAB
A→aA|a B→ε|bB
问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？
[答案]
正规式是daa*b*； 相应的正规文法为(由自动机化简来)：
G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b
也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε
===============================================================================
4.已知文法G[Z]：
Z->aZb|ab
写出L(G[Z])的全部元素。
[答案]
Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb
L(G[Z])={anbn|n>=1}
==============================================================================
5.给出语言{anbncm|n>=1,m>=0}的上下文无关文法。
