编译原理习题答案
第一次： P14
2、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间可能有何种关系？
答：被翻译的程序称为源程序；
翻译出来的程序称为目标程序或目标代码；
将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻译程序；
把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；
解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读入源程序，即边解释边执行；
编译程序是将高级语言写的源程序翻译成目标语言的程序。
关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4 图 1.3。
P14
3、编译程序是由哪些部分组成？试述各部分的功能？ 答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查和处理程序；（8）信息表管理程序。具体功能见P7-9。
P14
4、语法分析和语义分析有什么不同？试举例说明。
答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否符合语法规则，例如：对变量 x：= y 符合语法规则就通过。语义分析是对语句意义进行检查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。
P15
5、编译程序分遍由哪些因素决定？
答：计算机存储容量大小；编译程序功能强弱；源语言繁简；目标程序优化程度；设计和实现编译程序时使用工具的先进程度以及参加人员多少和素质等等。
补充：
1、为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？ 答：内部编码从“源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体标识符的含义编码该单词的值。
补充：
2、赋值语句： A：= 5 * C的语法和语义指的是什么？
答：语法分析将检查该语句是否符合赋值语句规则，语义是指将 5 * C 的结果赋值为 A 。
１
第二次作业： P38
1、设T1＝{11，010}，T2＝{0，01，1001}，计算：T2T1，T1*，T2+。 T2T1＝{011，0010，0111，01010，100111，1001010} T1*＝{ε，11，010，1111，11010，01011，010010……} T2+＝{0，01，1001，00，001，01001，010，0101……}
P38 3、令A＝{0，1，2}，写出集合A+和A*的七个最短符号串。 A+：0，1，2，00，01，02，10（有多种可能） A*：ε，0，1，2，00，01，02（有多种可能）
P38
5、试证明：A+＝A A*＝A*A。
证明：A+＝A1∪A2∪……∪An∪……
A*＝A0（即{ε}）∪A+
A A*＝A（A0∪A+ ）＝A∪A+＝A+＝A+∪A＝（A0∪A+ ）A＝A*A（证毕）
P38
7、设有文法G[S]：
S∷＝A
A∷＝B | IF A THEN A ELSE A B∷＝C | B+C | +C C∷＝D | C*D | *D
D∷＝X | (A) | -D 试写出VN和VT。
VN＝{S，A，B，C，D}
VT＝{IF，THEN，ELSE，+，*，X，(，)，-}
P38-39
8、设有文法G[S]：
S∷＝aAb A∷＝BcA | B B∷＝idt |ε
试问下列符号串（1）aidtcBcAb （3）ab （5）aidtcidtcidtb 是否为该文法的句型或句子。
（1）S?aAb?aBcAb?aidtcAb?aidtcBcAb 句型但不是句子； （3）S?aAb?aBb?aεb?ab 是句型也是句子； （5）S?aAb?aBcAb?aidtcAb?aidtcBcAb?aidtcidtcBb?aidtcidtcidtb句型也是句子。
P39
10、给定文法：
S∷＝aB | bA A∷＝aS | bAA | a
B∷＝bS | aBB|b 该文法所描述的语言是什么？
L(G)＝{相同个数的a与b以任意次序连接而成的非空符号串}。
２
P39
11、试分别描述下列文法所产生的语言（文法开始符号为S）：
（1） S∷＝0S | 01 （2） S∷＝aaS | bc
（1） L(G)＝{0n1| n≥1}； （2） L(G)＝{a2nbc | n≥0}。
P39
12、试分别构造产生下列语言的文法： （1）{ abna | n=0，1，2，3……} （3）{ aban | n≥1}
（5）{ anbmcp | n，m，p≥0}
（1）G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}，
P：S∷＝aAa A∷＝bA |ε
（3）G＝{VN，VT，P，S}，VN＝{S，A }，VT＝{a，b}，
P：S∷＝abA
A∷＝aA |ε 或 A∷＝aA | a
（5）①G＝{VN，VT，P，S}，VN＝{S，A ，B，C}，VT＝{a，b，c}，
P：S∷＝ABC A∷＝aA |ε B∷＝bB |ε C∷＝cC |ε
②G＝{VN，VT，P，S}，VN＝{S，T，C}，VT＝{a，b，c}， P：S∷＝TC T∷＝aTb |ε C∷＝cC |ε
③G＝{VN，VT，P，S}，VN＝{S }，VT＝{a，b，c}， P：S∷＝aS | bS | cS |ε
第三次作业： P39
15. 设文法G规则为：
S：：=AB B：：=a|Sb A：：=Aa|bB
对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。 （2）baabaab (3)bBABb （2） S
A B A a S b
３
b B A B
a b B a
a 句型baabaab的短语a, ba, baa, baab，简单短语a，句柄 a S （3）
A B b B S b A B 短语bB, AB, ABb， 简单短语bB, AB， 句柄bB
P40 18. 分别对i+i*i 和i+i+i中每一个句子构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。
<表达式>：：=i|(<表达式>)|<表达式><运算符><表达式> <运算符>：：=+|-|*|/ 1． i+i*i
<表达式>
<表达式> <运算符> <表达式> i + <表达式> <运算符> <表达式>
i * i
<表达式>
<表达式> <运算符> <表达式> <表达式> <运算符> <表达式> * i
i + i
由于句子i+i*i可构造两棵不同的语法树，所以证明该文法是二义的。 2. i+i+i
<表达式>
<表达式> <运算符> <表达式>
４