优质参考文档
第一章
练习1
2、典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？
典型的编译程序具有7个逻辑部分：
第二章
练习2.2
4.试证明：A+=AAG=AGA
证：∵AG=A0∪A+，A+=A1∪A2∪…∪An∪… 得：AG=A0∪A1∪A2∪…∪An∪…
∴AAG=A（A0∪A1∪A2∪…∪An∪…） =AA0∪AA1∪AA2∪…∪AAn∪… =A∪A2∪A3∪An+1∪… =A+
同理可得：
AGA=(A0∪A1∪A2∪…∪An∪…)A =A0A∪A1A∪A2A∪…∪AnA∪… =A∪A2∪A3∪An+1∪… =A+
因此：A+=AAG=AGA 练习2.3
优质参考文档
优质参考文档
1.设G[〈标识符〉]的规则是： 〈标识符〉::=a|b|c|
〈标识符〉a|〈标识符〉c| 〈标识符〉0|〈标识符〉1 试写出VT和VN，
并对下列符号串a,ab0,a0c01,0a,11,aaa给出可能的一些推导。 解：VT={a,b,c,0,1}，VN={〈标识符〉} (1)不能推导出ab0,11,0a (2)〈标识符〉=>a
(3)〈标识符〉=>〈标识符〉1 =>〈标识符〉01 =>〈标识符〉c01 =>〈标识符〉0c01 =>a0c01
(4)〈标识符〉=>〈标识符〉a =>〈标识符〉aa =>aaa
2．写一文法，其语言是偶整数的集合 解：G[<偶整数>]：
<偶整数>::=<符号><偶数字>|<符号><数字串><偶数字> <符号>::=+|—|ε
<数字串>::=<数字串><数字>|<数字> <数字>::=<偶数字>|1|3|5|7|9 <偶数字>::=0|2|4|6|8 4.设文法G的规则是： 〈A〉::=b|cc
试证明：cc,bcc,bbcc,bbbcc∈L[G] 证：（1）〈A〉=>cc （2）〈A〉=>b〈A〉=>bcc （3）〈A〉=>b〈A〉=>bb〈A〉=>bbcc （4）〈A〉=>b〈A〉=>bb〈A〉=>bbb〈A〉=>bbbcc 又∵cc,bcc,bbcc,bbbcc∈VtG
∴由语言定义，cc,bcc,bbcc,bbbcc∈L[G] 5试对如下语言构造相应文法：
（1）{a(bn)a|n=0,1,2,3,……},其中左右圆括号为终结符。 （2）{（an）（bn）|n=1,2,3,……} 解：（1）文法[G〈S〉]： S::=a(B)a
优质参考文档
优质参考文档
B::=bB|ε
(2)文法[G〈S〉]：--错了，两个n不等 S::=(A)(B) A::=aA|a B::=bB|b
7.对文法G3[〈表达式〉]
〈表达式〉::=〈项〉|〈表达式〉+〈项〉|〈表达式〉-〈项〉 〈项〉::=〈因子〉|〈项〉G〈因子〉|〈项〉/〈因子〉 〈因子〉::=（〈表达式〉）|i
列出句型〈表达式〉+〈项〉G〈因子〉的所有短语和简单短语。 <表达式>=><表达式>+<项> =><表达式>+<项>G<因子>
短语有：
〈表达式〉+〈项〉G〈因子〉和〈项〉G〈因子〉 简单短语是：〈项〉G〈因子〉 8文法V::=aaV|bc的语言是什么？ ?
解：L（G[V]）={a2nbc|n=0,1,2,……} V?aaV?aaaaV?....?a2nbc(n≥1) V?bc(n=0) 练习2.4
5.已知文法G[E]： E::=ET+|T T::=TFG|F F::=FP↑|P P::=（E）|i
有句型TFGPP↑+，
问此句型的短语，简单短语，和句柄是什么？ 解：此句型的短语有：TFGPP↑+，TFG，PP↑，P
优质参考文档