您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
弱公平条件下模型检验状态空间的对称化简分析.pdf 58页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
你可能关注的文档：
··········
··········
硕士学位论文
弱公平条件下模型检验状态空间的对称化简
姓名：周文
申请学位级别：硕士
专业：计算机软件与理论
指导教师：张治国
弱公平条件下模型检验状态空间的对称化简
论文题目：
弱公平条件下模型检验状态空间的对称化简
计算机软件与理论
指导老师：
张治国副教授
形式化验证已经成为对系统设计和协议设计进行确认的重要手段，其方法分
为两类14”，一类是以逻辑推理为基础，另一类则以穷尽搜索为基础，穷尽搜索方
法统称为模型检验。逻辑推理的不足之处在于推理的难度。对于稍微复杂的系统，
自动化的推理就难以胜任。模型检验的好处在于它有全自动化的检验过程，并且
如果一个性质不满足，它能给出这个性质不满足的理由，可据此对系统设计进行
状态爆炸l61是模型检验中的一个重要难题。实际系统中的状态数目可能很
大，以至无法在有限的时间和内存空间下进行完整的检验。
对称归约是处理状态爆炸问题的有效技术之一。但是在实际系统验证时，如
果是处于公平条件下，已有的对称归约算法很难有有效的作用。而在实际应用中，
公平性足验证一些性质的先决条件。
本文给出了一个模型检验的算法，在公平条件下利用对称归约化简状态空
间，以改善状态爆炸问题。
这个算法基于嵌套深度优先搜索(NDFS)算法。它假定要检验的性质用Btlchi
自动机119I给定，因此，检验系统是否支持某个给定性质的问题，就归结为在图
中寻找接受回路的问题17,61。
7】和带对称归约的NDFS算法
本文首先叙述并分析了标准的NDFS算法17．1
展，提出了一个在弱公平条件下、未使用对称归约的、基于嵌套深度优先搜
(NDFS)的模型检验策略，最后在此基础上提出基于NDFS的融合弱公平性和
对称归约的算法。
相对于基于寻找最大强连通分支(MSCC)的类似算法Ill，“l，本算法具有基
于NDFS的优势，每个状态的空间开销也要少，而且，虽然与它们有相同的最坏
时间复杂度O(N·lh(T)I)，但是在检测到性质的一个反例时，本算法需要遍历
的状态要少得多，因此具有更好的时间和空间复杂性，同时也兼容于近似验证技
本文还把这个算法的原型运用在通用的模型检验器Spin之上，对Peterson
互斥协议等例子的进行验证实验。实验的结果显示，本文的算法使对称归约在弱
公平条件下的化简效果接近于它不在弱公平条件约束下的化简效果。
关键词：模型检验，状态爆炸，嵌套深度优先搜索，对称归约，公平性
弱公平条件下模型梭骢状态空间的对称化简
ReductioninState forModel
Title：Symmetry
underWeakFairness
TheoreticalScienee
Major：Software Computer
Name：ZhouWen
Supervisor：Vice—Professor
ZhangZhi-guo
FormalVerificationbee
正在加载中，请稍后...布尔表达式的化简，急！
[问题点数：200分，结帖人awinder]
布尔表达式的化简，急！
[问题点数：200分，结帖人awinder]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2002年8月 其他开发语言大版内专家分月排行榜第三
2002年5月 专题开发/技术/项目大版内专家分月排行榜第二2002年2月 专题开发/技术/项目大版内专家分月排行榜第二2001年11月 专题开发/技术/项目大版内专家分月排行榜第二2001年7月 专题开发/技术/项目大版内专家分月排行榜第二
2002年6月 专题开发/技术/项目大版内专家分月排行榜第三
匿名用户不能发表回复！|编译原理 A 1. 简要说明语义分析的基本功能。 2. 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S 消除文法的左递归及提取公共左因子。 3 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： while (A&C ∧ B&D) { if (A ? 1) C=C+1; else while (A ? D) A=A+2; }。 5. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。 A 答案 1 答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。 2 解：消除文法 G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子： S→(T) | aS′ S′→+S | ε T→ST′ T′→,ST′| ε3 答：w a b + c d e 10 - / + 8 + * + 4 答：该语句的四元式序列如下(其中 E1、E2 和 E3 分别对应 A＜C∧B＜D、A?1 和 A?D，并 且关系运算符优先级高)：1100 (j&,A,C,102) 101 (j,_,_,113) 102 (j&,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j?,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 113 5 答：证明： 由文法 G[S]：S→aSb|Sb|b，对句子 aabbbb 对应的两棵语法树为：因此，文法 G[S]为二义文法。 编译原理 B 1. 什么是句子？ 什么是语言 ? 2. 写一文法，使其语言是偶正整数的集合,要求：2(1)允许 0 打头； (2) 不允许 0 打头。 3. 已知文法 G[E] 为： E→T|E+T|E-T T→F|T*F|T/F F→ （ E ） |i ① 该文法的开始符号（识别符号）是什么？ ② 请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。 ③ 找出句型 T+T*F+i 的所有短语、简单短语和句柄。 4. 构造正规式相应的 NFA : 1(0|1)*101。 5. 写出表达式(a＋b*c)/(a＋b)－d 的逆波兰表示和三元式序列。 B 卷答案 1 答：(1)设 G 是一个给定的文法，S 是文法的开始符号，如果 S x(其中 x∈VT*),则称 x 是 文法的一个句子。 (2)设 G[S]是给定文法， 则由文法 G 所定义的语言 L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。 2 解：(1)G[S]=({S,P,D,N},{0,1,2,?,9},P,S) P: S-&PD|D P-&NP|N D-&0|2|4|6|8 N-&0|1|2|3|4|5|6|7|8|9 (2)G[S]=({S,P,R,D,N,Q },{0,1,2,?,9},P,S) P: S-&PD|P0|D P-&NR|N R-&QR|Q D-&2|4|6|8 N-&1|2|3|4|5|6|7|8|9 Q-&0|1|2|3|4|5|6|7|8|933 解：① 该文法的开始符号（识别符号）是 E。 ②该文法的终结符号集合 VT={+、-、*、/、（、）、i}。 非终结符号集合 VN={E、T、F}。 ③句型 T+T*F+I 的短语为 i、T*F、第一个 T、T+T*F+i; 简单短语为 i、T*F、第一个 T;句柄 为第一个 T。 4 解：1(0|1)*101 对应的 NFA 为5 解：逆波兰表示： 三元式序列： a，b) 编译原理 Cabc*＋ab＋/d－ ① (*，b，c) ② (＋，a， ①) ⑤ (－，④，d) ③ (＋，④ (/，②，③)1．(10 分) 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义 分析、代码生成）报告的。 （1） else 没有匹配的 if （2） 数组下标越界 （3） 使用的函数没有定义 （4） 在数中出现非数字字符 （5）函数调用时实参与形参类型不一致。 2． 分) 构造一个 DFA， (15 它接收 Σ ={0,1}上所有满足如下条件的字符串： 每个 1 都有 0 直 接跟在右边。并给出该语言的正规式 3．(10 分) 为下面的语言设计文法： （1） （2） {a b , 其中 m ? n }m n{w | w?{a, b} ，w 的长度为奇数}*证明 E + T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。 5．(15 分) 给定文法：E → E + T | E - T |T T → T * F | T / F |F F → (E) | id4C 卷答案 1答案：（每小题2分） （1） 语法分析 （2） 语法分析 （3） 语义分析 （4） 词法分析 （5） 语义分析 2答案： 按题意相应的正规表达式是(0 10) 0 ，或0 (0 | 10) 0 ，构造相应的DFA。* * * * * *3答案：（每小题 10分） （1）考虑在先产生同样数目的a,b，然后再生成多余的a。以下是一种解法：S → aSb | aS | ε（2） A → aB | bBB → aA | bA | ε5 证明 E + T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。 答： E ? E ?T ? E ? T*F ? E ? T* ( E ) ? E ? T * (T ) ? E ? T * ( F ) ? E ? T * (id) ，rm rm rm rm rm rm短语：id，（id）， T*（id）， E+ T*（id）。 直接短语：id。 句柄是 id。 编译原理 D 卷 3、何谓“标识符” ，何谓“名字” ，两者的区别是什么？ 4、令 ＋、* 和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算 1＋ 1*2↑*1↑2 的值： （1） 、优先顺序（从高至低）为＋、* 和↑，同级优先采用左结合。 （2） 、优先顺序为↑、＋、*，同级优先采用右结合。 6、令文法 G6 为 N→DOND，D→0O1O2O3O4O5O6O7O8O95（1） 6 的语言 L(G6)是什么？ 、G （2） 、给出句子 0127、34 和 568 的最左推导和最右推导。 7、写一个文法，使其语言是奇数集，且每个奇数不以 0 开头。 8、令文法为 E→TOE+ TOE-T T→FOT*FOT/F F→(E)Oi （1） 给出 i+i*i、i*(i+i)的最左推导和最右推导； 给出 i+i+i、i+i*i 和 i-i-i 的语法树。 9、证明下面的文法是二义的：S→iSeSOiSOi 11、给出下面语言的相应文法： L1={a b c On?1，i?0}， L2={a b c On?1，i?0} L3={a b a b On，m?0} L4={1 0 1 0 On，m?0} 3 解：标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线 开头的， 由数字、 字母和下划线组成的一定长度的字符串， 它只是一个标志， 没有其他含义。 名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值。 4 解： （1） 、1＋1*2↑*1↑2 = 2*2↑*1↑2 = 4↑*1↑2 = 4↑↑2 = （2） 、1＋1*2↑*1↑2 = 6 解： （1） 、L(G6)是由 0 到 9 这 10 个数字组成的字符串。 （2） 、句子 0127、34 和 568 的最左推导： N=&ND=&NDD=&NDDD=&DDDD=&0DDD=&01DD=&012D=&0127 N=&ND=&DD=&3D=&34 N=&ND=&NDD=&DDD=&5DD=&56D=&568 句子 0127、34 和 568 的最右推导： N=&ND=&N7=&ND7=&N27=&ND27=&N127=&D127=&0127 N=&ND=&N4=&D4=&34 N=&ND=&N8=&ND8=&N68=&D68=&5686n m m n n n m m i n n n n i7 解： G(S)：A→2O4O6O8OD B→AO0 C→CBOA D→1O3O5O7O9 S→CDOD 8 解： （1） 最左推导为： E =& E+T =& T+T =& F+T =& i+T =& i+T*F =& i+F*F =& i+i*F =& i+i*i E =& T =& T*F =& F*F =& i*F =& i*(E) =& i*(E+ T) =& i*(T+ T) =& i*(F+ T) =& i*(i+ T) =& i*(i+ F) =& 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 E =& T =& T*F =& F*F =& F*(E) =& F*(E+T) =& F*(E+ F) =& F*(E+ i) =& F*(T+i) =& F*(F+i) =& F*(i+i) =& i*(i+ i) （2） 语法树：EE T T E EEE+E+-T+TF iTT*F-TFFFFiFFiiiiiii 9 解：考虑句子 iiiei，存在如下两个最右推导： S=&iSeS=&iSei=&iiSei=&iiiei S=&iS=&iiSeS=&iiSei=&iiiei7由此该文法是二义的。 11 解： L1 的文法：S→AC；A→aAbOab；C→cCOε L2 的文法：S→AB；A→aAOε ；B→bBcObc L3 的文法：S→AB；A→aAbOε ；B→aBbOε L4 的文法： S→1S0OA； A→0A1Oε ；编译原理 E 卷 1、 令 A、B 和 C 是任意正规式，证明以下关系成立： AOA=A (A*)*= A* A*=ε OA A* (AB)*A=A(BA)* (AOB)*=(A*B*)*=(A*OB*)* A=bOaA 当且仅当 A=a*b 2、 构造下列正规式相应的 DFA 1(0O1)*101 1()*1)*0 0*10*10*10* (00O11)*((01O10)(00O11)*(01O10)(00O11)*)* 3、 （1） （2） 给出下面正规表达式： 以 01 结尾的二进制数串； 能被 5 整除的十进制整数； 包含奇数个 1 或奇数个 0 的二进制数串；4、对下面情况给出 DFA 及正规表达式： （1）{0，1}上不含子串 010 的所有串。5、将图 3.18 的（a）和（b）分别确定化和最小化。8a a，b 0 a (a)1a b 0 a a a b b 4 b 5 a b 2 b a 31 a(b) 6、 构造一个 DFA，它接受∑={0，1}上所有满足如下条件的字符串：每个 1 都有 0 直接跟在 右边。 、 7、 给定右线性文法 G： S→0SO1SO1AO0B A→1CO1 B→0CO0 C→0CO1CO0O1 求出一个与 G 等价的左线性文法。 文法 G 对应的状态转换图如下所示：90，1 1 S A 0 B 0 10，1C 0，1 1 Z0E 卷答案1 证明： （1） 、AOA=A L(AOA)=L(A)∪L(A)=L(A)，所以有 AOA=A。 （2） 、(A*)*= A*（3） 、A*=ε OA A* 通过证明两个正规式所表示的语言相同来证明两个正规式相等。 L(ε OA A*)=L(ε )∪L(A)L(A*)= L(ε )∪L(A)(L(A) )* =L(ε )∪L(A)((L(A)) ∪(L(A)) ∪(L(A)) ∪(L(A)) ∪?) =L(ε )∪(L(A)) ∪(L(A)) ∪(L(A)) ∪(L(A)) ∪? =(L(A))*=L(A*) 即：L(ε OA A*)=L(A*)，所以有：A*=ε OA A* （4） 、(AB)*A=A(BA)* 利用正规式的分配率和结合律直接推导。 (AB)*A=((AB) O(AB) O(AB) O(AB) O?)A =ε AO(AB) AO(AB) AO(AB) AO? =Aε OA (BA) OA (BA) OA (BA) O? =A(ε O(BA) O(BA) O(BA) O?) =A(BA)* 即：(AB)*A=A(BA)* （5） 、(AOB)*=(A*B*)*=(A*OB*)*101 2 3 1 2 3 1 2 3 0 1 2 3 1 2 3 4 0 1 2 3证明:先证(AOB)*=(A*B*)* 因为 L(A) ? L(A) *L(B) *,L(B) ? L(A) *L(B) * 故:L(A) ∪L(B) ? L(A) *L(B) * 于是由本题第二小题结论可知(L(A)∪L(B)) * ? (L(A) *L(B)*)* 又 L(A) ? L(A)∪L(B), L(B) ? L(A)∪L(B) 故:L(A)* ? (L(A)∪L(B))* L(B)* ? (L(A)∪L(B))* 因此有:L(A)*L(B)* ? (L(A)∪L(B))* (L(A)∪L(B))*=( (L(A)∪L(B))*) 故(L(A)*L(B)*)* ? ((L(A)∪L(B))*)* 由本题第二小题得: ((L(A)∪L(B))*)*= (L(A)∪L(B)) * 故得: (L(A)*L(B)*)* ? (L(A)∪L(B)) * 则由①②得: (L(A)∪L(B)) *=(L(A)*L(B)*)* 由于 L((A*B*))*=(L(A*B*))*=(L(A*)L(B*))*=(L(A)*L(B)*)* 即有(L(A)∪L(B))*=L((A*B*))* ③ ②2①而(A|B)*对应的语言为(L(A)∪L(B))*,且(A*B*)*对应的语言为 L((A*B*))* 则根据③得(A|B)*=(A*B*)* 再证:(A*|B*)*=(A*B*)* 因为:A,B 是任意正规式,由以上结论得: (A*|B*)*=((A*)*(B*)*)* 又由本题第二小题目的结论可得： （A*）*=A*， （B*）*=B* 因此， （A*|B*）*=（A*B*）* 综合上述两种结论，最后得：(AOB)*=(A*B*)*=(A*OB*)* 2 解： (1)、1(0O1)*101 第一步：根据正规式构造 NFA，先引入初始状态 X 和终止状态 Y：X1(0O1)*101Y再对该转换图进行分解，得到分解后的 NFA 如下图：110 1 ε ε 1 4 0 5 1 YX1231 第二步：对 NFA 进行确定化，获得状态转换矩阵： 状态 {X} {1，2，3} {2，3} {2，3，4} {2，3，5} {2，3，4，Y} 0 ? {2，3} {2，3} {2，3，5} {2，3} {2，3，5} 1 {1，2，3} {2，3，4} {2，3，4} {2，3，4} {2，3，4，Y} {2，3，4}根据转换矩阵获得相应的 DFA： 0 1 0012 1 3 0 0 1 4 1 0 511第三步：化简该 DFA，获得最简的 DFA 即为所求。 首先根据是否终止状态将所有状态分为两个集合{0，1，2，3，4}和{5}，这里集合{5} 已经不可划分，只需考虑集合{0，1，2，3，4}。 {0，1，2，3，4}0={2，4，-}，{0，1，2，3，4}1={1，3，5} 因为{1，3，5}和{2，4，-}不在一个集合里面，所以需要对集合{0，1，2，3，4}进行 进一步的划分，检查其中的所有状态。状态 0 不能接受字符 0，需要把状态 0 划分出来；另 外， 只有状态 4 读入字符 1 后进入状态 5， 因此将状态 4 划分出来， 划分的结果为 4 个集合： {0}，{1，2，3}，{4}，{5}。 检查集合{1，2，3}，{1，2，3}0={2，4}，不属于同一个集合，因此要对集合{1，2，123}进行进一步划分，划分结果为 5 个集合：{0}，{1，2}，{3}，{4}，{5}。 检查集合{1，2}，{1，2}0={2}，{1，2}1=3，不需要进行进一步划分。所以最终划分结 果为 5 个集合：{0}，{1，2}，{3}，{4}，{5}。 所以，最终所求 DFA 如下图示： 0 101 1 3 0 0 1 4 1 0 513 解： （1）以 01 结尾的二进制数串； (10)*01。 （2）能被 5 整除的十进制整数； () ()*(05)(05)。 （3）包含奇数个 1 或奇数个 0 的二进制数串； 1*0（101*0）*0*1（010*1）*。 4 解： （1） 、直接写出满足条件的正规表达式。考虑满足条件的字符串中的 1：在串的开始部 分可以有 0 个或多个 1，串的尾部也可以有 0 个或多个 1，但串的中间只要出现 1 则至少在 两个以上，所以满足条件的正规表达式为 1*(0O111*)*1*。 所求的 DFA 如下图所示：131 S 0 a A 1 1 B05解： （1） 、图（a）中为一个 NFA，所以需要先对它进行确定化，得到 DFA，然后再对 DFA进行最小化。 首先进行确定化，如下两个表所示： 状态 {0} {0，1} {1} a {0，1} {0，1} {0} b {1} {1} ?状态 0 1 2a 1 1 0b 2 214根据状态转换矩阵得到如下图所示的 DFA： a b a 2 化简后的 DFA 为： a b a b01a02（2） 、题中所给即为一个 DFA，不需要确定化，只对它进行最小化即可。 首先将状态划分为两个集合{{0，1}，{2，3，4，5}}。有{0，1}a={1}，{0，1}b={2，4} 和{2，3，4，5}a={1，3，0，5}，{2，3，4，5}b={2，3，4，5}，所以可以进一步划分为{{0， 1}，{2，4}，{3，5}}，然后有{0，1}a={1}，{0，1}b={2，4}，{2，4}a={1，0}，{2，4}b={3， 5}，{3，5}a={3，5}，{3，5}b={2，4}。因此，最后划分结果是{{0，1}，{2，4}，{3，5}}。 最小化后的 DFA 如下图所示： a a 0 b a 1 b b 26 解：第一步：写出正规表达式。根据题意，该 DFA 接受的字符串由 0 和 1 组成，并且 每个 1 的后面都有 0 直接跟在右边，因此，可以将该字符串理解为由 0 和 10 构成的串，则 相应的正规表达式就是(010)*。 第二步：构造 NFA。首先得出下图：X(010)*Y然后对上图进行分解后得到如下图所示的 NFA。152 0 1 X ε 1 ε Y0第三步：确定化，得到 DFA。确定化结果如表 14.1 所列；给状态编号，得到表 14.2 所 示的状态转换矩阵： 状态 {X，1，Y} {1，Y} {2} 0 {1，Y} {1，Y} {1，Y} 1 {2} {2} ?表 14.1 状态转换矩阵 状态 0 1 2 0 1 1 1 1 2 2表 14.2 新的状态转换矩阵16根据状态转换矩阵得到 DFA 如下图所示： 0 1 1 2 第四步：对该 DFA 进行最小化。其分析过程如下： {0，1}，{2} {0，1}0={1}，{0，1}1={2} {0，1}，{2} 最小化后的 DFA 如图所示，该 DFA 即为所求。 0 1 0 0 00101对状态转换图进行确定化，得到状态转换矩阵： 状态 {S} {S，B} {S，A} {S，B，C，Z} {S，A，C，Z} {S，B} {S，B，C，Z} {S，B} {S，B，C，Z} {S，B，C，Z} 0 {S，A} {S，A} {S，A，C，Z} {S，A，C，Z} {S，A，C，Z} 1给状态编号，得到新的状态转换矩阵： 状态 0 1 2 3 4 1 3 1 3 3 0 2 2 4 4 4 1根据状态转换矩阵获得 DFA 如下：170 0 0 1 1 2 0 1 1 0 1 4 1 还可以对上图的 DFA 进行化简，状态 3 和 4 可以合并，化简后的 DFA 如下图所示： 0，1 0 0 3 0SA 1 B 0T11不难看出，该 DFA 接受的语言是{0，1}上包含 00 或 11 的字符串。根据化简后的 DFA， 我们可以写出相应的左线性文法 G’： T→A0OB1OT0OT1 A→B0O0 B→A1O1 编译原理 F 卷 1、考虑下面的文法 G1： S→aO∧O(T) T→T，SOS （1）消去 G1 的左递归。然后对每个非终结符，写出不带回溯的递归子程序。 （2）经改写后的文法是否是 LL(1)的？给出它的预测分析表。 （2）计算每个非终结符的 FIRST 集合和 FOLLOW 集合： FIRST（S）={a，∧，( } FIRST（T）={a，∧，( }18FIRST（T’）={， } ，εFOLLOW（S）={ )，’，’，#} FOLLOW（T）={ ) } FOLLOW（T’）={ ) } 从而可见改造后的文法符合 LL(1)文法的充分必要条件，所以是 LL(1)的。 该文法的预测分析表 a S T T’ S-&a T-&S T’ S-&^ T-&S T’ ^ ( S-&(T) T-&S T’ T’-&ξ T-&,S T’ ) , #2、对下面的文法 G： E→TE’ E’→+EOε T→FT’ T’→TOε F→PF’ F’→*F’Oε P→(E)OaObO∧ （1） （2） （3） （4） 计算这个文法的每个非终结符的 FIRST 和 FOLLOW。 证明这个文法是 LL(1)的。 构造它的预测分析表。 构造它的递归下降分析程序。3、下面文法中，哪些是 LL(1)的，说明理由。 （1） 、 S→Abc A→aOε19B→bOε（2） 、 S→Ab A→aOBOε B→bOε（3） 、 S→ABBA A→aOε B→bOε（4） 、 S→aSeOB B→bBeOC C→cCeOd 4、对下面文法： Expr→-Expr Expr→(Expr)OVar ExprTail→-ExprOε Var→id VarTail VarTail→(Expr)Oε （1） 、构造 LL(1)分析表。 （2） 、给出对句子 id--id((id))的分析过程。 5、把下面文法改写为 LL(1)的： Declist→Declist；DeclODecl Decl→IdList：Type IdList→IdList，idOid Type→ScalarTypeOarray(ScalarTypeList) of Type ScalarType→idOBound..Bound20Bound→Sign IntLiteralOid Sign→+O-Oε ScalarTypeList→ScalarTypeList，ScalarTypeOScalarType 1、令文法 G1 为 E→E+TOT T→T*FOF F→(E)Oi 证明 E+T*F 是它的一个句型，指出这个句型的所有短语，直接短语和句柄。 2、考虑下面的表格结构文法 G2： S→aO∧O(T) T→T，SOS （1） 给出(a，(a，a))和(((a，a)，∧，(a))，a)的最左和最右推导。 指出(((a，a)，^，(a))，a)的规范归约及每一步的句柄。根据这个规范归约，给出“移进归约”的过程，并给出它的语法树自下而上的构造过程。 3、 （1）计算练习 2 文法 G2 的 FIRSTVT 和 LASTVT。 （2）计算 G2 的优先关系。G2 是一个算符优先文法吗？ （3）给出输入串（a， （a，a） ）的算符优先分析过程。 4、考虑文法： S→ASb A→SAa （1） （2） （3） （4） 列出这个文法的所有 LR(0)项目。 构造这个文法的 LR(0)项目集规范族及识别活前缀的 DFA。 这个文法是 SLR 的吗？若是，构造出它的 SLR 分析表。 这个文法是 LALR 或 LR(1)的吗？F 卷答案 1 答：解： （1）按照 T、S 的顺序消除左递归，得到文法： ?G’(S)21S→aO∧O(T) T→ST’ T’→，ST’ Oε 对于非终结符 S,T, T’的递归子程序如下： Procedure S; Begin If sym = ‘a’ or sym = ‘^’ Then advance Else if sym = ‘(‘ Then begin A T; If sym = ’)’Then advance Else End Else error E errorProcedure T; Begin S; T’; E Procedure T’ Begin If sym = ‘,’ Then begin A S; T’ Ends22
2 解： （1） 计算每个非终结符的 FIRST 集合和 FOLLOW 集合如下： FIRST（E）={(，a，b，∧} FIRST（E’）={+，ε } FIRST（T）={(，a，b，∧} FIRST（T’）={(，a，b，∧，ε } FIRST（F）={(，a，b，∧} FIRST（F’）={*，ε } FIRST（P）={(，a，b，∧}FOLLOW（E）={#，)} FOLLOW（E’）={#，)} FOLLOW（T）={+，)，#} FOLLOW（T’）={+，)，#} FOLLOW（F）={(，a，b，∧，+，)，#} FOLLOW（F’）={(，a，b，∧，+，)，#} FOLLOW（P）={*，(，a，b，∧，+，)，#} （2） 本文法是 LL ( 1 )文法。 证明： 通过观察可知文法中不含有左递归，满足 LL (1)文法定义的第一个条件。 考虑下列产生式： E’→+EOε T’→TOε F’→*F’Oε P→(E)OaObO∧ 因为： FIRST（+E）∩FIRST（ε ）={+}∩{ε }=? FIRST（E’）∩FOLLOW（E’）={+}∩{#，)}= ? FIRST（T）∩FIRST（ε ）={(，a，b，∧}∩{ε }=? FIRST（T’）∩FOLLOW（T’）={(，a，b，∧}∩{+，)，#}=?23FIRST（*F’）∩FIRST（ε ）={*}∩{ε }=? FIRST（F’）∩FOLLOW（F’）={*}∩{(，a，b，∧，+，)，#}= ? FIRST（ ）∩FIRST（a）∩FIRST（b）∩FIRST（∧）= ? （E） 所以该文法是 LL(1)文法。 （3） 构造其预测分析表：预测分析表+ E E’ T T’ F F’ F’ ? ξ T’?ξ E’?+E*( E?T E’)a E?T E’b E?T E’^ E?T E’#E’ ?ξ T ?FT’ T’ ? T F ?PF’ F’ ?*F’ F’ ? ξ F’?ξ T’?ξ T’?FT’ T’?T F?PF’ F’?ξ T?FT’ T’?T P?PF’ F’?ξ T?FT’ T’ ?T F?PF’ F’?ξE’ -&ξT’?ξF’?ξPP ?(E)P?aP?bP? ^（4）构造其递归下降分析程序： Procedure Begin T ; E’ E E;Procedure BeginE’ ;If sym = ‘ + ’ Then begin A24E End EProcedure T ; Begin F ; T’ EProcedure Begin IfT’ ;sym ∈first ( T )Then T Else E if sym = ‘*’ then errorProcedure Begin IfF ;sym ∈first ( P )P; F’; EProcedure BeginF’If sym = ‘ * ’ Then begin A F’ End E25Procedure BeginPIf sym = ‘ a ’ Then acvance Elseor sym = ‘ b ‘or sym = ‘ ^if sym = ‘ ( ‘ Then begin A E ; If sym = ‘ ) ‘Then advance Else error End Else E 3 （1） 解： 该文法不含左递归，计算每个非终结符的 FIRST 集合和 FOLLOW 集合如下： FIRST（S）={a，b，c} FIRST（A）={a，ε } FIRST（B）={b，ε } FOLLOW（S）={#} FOLLOW（A）={b，c} FOLLOW（B）={c} 可见该文法满足 LL(1)文法的三个条件，是 LL(1)文法。 （2） 该文法不含左递归，计算每个非终结符的 FIRST 集合和 FOLLOW 集合如下： FIRST（S）={a，b} FIRST（A）={a，b，ε } FIRST（B）={b，ε } FOLLOW（S）={#} FOLLOW（A）={b} FOLLOW（B）={b}26error考虑 A→aOBOε ，因为 FIRST（B）∩FOLLOW（A）={b}≠?，所以该文法不是 LL(1)文 法。 （3） 该文法不含左递归，计算每个非终结符的 FIRST 集合和 FOLLOW 集合如下： FIRST（S）={a，b，ε } FIRST（A）={a，ε } FIRST（B）={b，ε } FOLLOW（S）={#} FOLLOW（A）={a，b，#} FOLLOW（B）={a，b，#} 考虑 A→aOε 和 B→bOε ，因为 FIRST（a）∩FOLLOW（A）={a}≠? FIRST（b）∩FOLLOW（B）={b}≠? 所以该文法不是 LL(1)文法。 （4） 该文法不含左递归，计算每个非终结符的 FIRST 集合和 FOLLOW 集合如下： FIRST（S）={a，b，c，d} FIRST（B）={b，c，d} FIRST（C）={c，d} FOLLOW（S）={e，#} FOLLOW（B）={e，#} FOLLOW（C）={e，#} 可见该文法满足 LL(1)文法的三个条件，是 LL(1)文法。 4 解： （1） 、计算每个非终结符的 FIRST 集合和 FOLLOW 集合如下： FIRST(Expr)={-，(，id} FIRST(ExprTail)={-，ε } FIRST(Var)={id} FIRST(VarTail)={(，ε } FOLLOW(Expr)={)，#} FOLLOW(ExprTail)={)，#} FOLLOW(Var)={-，)，#}27FOLLOW(VarTail)={-，O，#} 构造其预测分析表如下：Expr Expr→- Exprid Expr Expr( Expr -( Expr) →)#ExprTailExprTail→-ExprExprTail → εExprTail → εVarVar→idVarTail VarTail VarTail→ε VarTail (Expr) （2） 、句子 id--id((id))的分析过程如下： → VarTail→ε VarTail→ε步骤 0符号栈 # Expr输入串 id--id((id)) #所用产生式1# ExprTail Varid--id((id)) #Expr→Var ExprTail2# ExprTail VarTail idid--id((id)) #Var→id VarTail3 4 5 6 7 8 9 10# ExprTail VarTail # ExprTail # Expr # Expr # Expr # Expr # ExprTail Var # ExprTail VarTail id--id((id)) # --id((id)) # --id((id)) # -id((id)) # -id((id)) # id((id)) # id((id)) # id((id)) # Expr→Var ExprTail Var→id VarTail Expr→-Expr VarTail→ε ExprTail→-Expr2811 12 13 14 15 16 17# ExprTail VarTail # ExprTail ) Expr ( # ExprTail ) Expr # ExprTail ) ) Expr ( # ExprTail ) ) Expr # ExprTail ) ) ExprTal Var # ExprTail ) ) ExprTail VarTail id((id)) # ((id)) # (id)) # (id)) # id)) # id)) # id)) # Expr→Var ExprTail Var→id VarTail VarTail→(Expr)18 19 20 21 22 23 suc 5 解：# ExprTail ) ) ExprTail VarTail # ExprTail ) ) ExprTail # ExprTail ) ) # ExprTail ) # ExprTail #)) # )) # )) # ) # # # ExprTail→ε VarTail→ε ExprTail→ε首先消除左递归，得到文法 G(Declist)： Declist→Decl Declist’ Declist’→；Decl Declist’Oε Decl→IdList：Type IdList→id IdList’ IdList’→，id List’Oε Type→ScalarTypeOarray(ScalarTypeList) of Type ScalarType→idOBound..Bound Bound→Sign IntLiteralOid Sign→+O-Oε ScalarTypeList→ScalarType ScalarTypeList’ ScalarTypeList’→，ScalarType ScalarTypeList’Oε 显然，改造后的文法没有左公共因子，计算每个非终结符的 FIRST 集合和 FOLLOW 集合29如下： FIRST(Declist)={id} FIRST(Declist’)={； } ，ε FIRST(Decl)={id} FIRST(IdList)={id} FIRST(IdList’)={； } ，ε FIRST(Type)={id，+，-，IntLiteral，array} FIRST(ScalarType)={id，+，-，IntLiteral} FIRST(Bound)={id，+，-，InLiteral} FIRST(Sign)={+，-，ε } FIRST(ScalarTypeList)={id，+，-，IntLiteral } FIRST(ScalarTypeList’)={， } ，εFOLLOW(Declist)={#} FOLLOW(Declist’)={#} FOLLOW(Decl)={id， ；} FOLLOW(IdList)={：} FOLLOW(IdList’)={：} FOLLOW(Type)={id， ；} FOLLOW(ScalarType)={id，，， ；），} FOLLOW(Bound)={id，， ；）’，’..} FOLLOW(Sign)={IntLiteral} FOLLOW(ScalarTypeList)={)} FOLLOW(ScalarTypeList’)={)} 显然，改造后的文法是 LL(1)的。 1 解：因为 E=&E+T=&E+T*F，所以 E+T*F 是该文法的一个句型。 短语：E+T*F，T*F 直接短语：T*F 句柄：T*F 2 解：30（1）最左推导： S=&(T)=&(T，S)=&(S，S)=&(a，S)=&(a，(T))=&(a，(T，S))=&(a，(S，S))=& (a，(a， S))=&(a，(a，a)) S=&(T)=&(T，S)=&(S，S)=&((T)，S)=&((T，S)，S)=&((T，S，S)，S)=&((S，S，S)， S)=&(((T)，S，S)，S)=&(((T，S)，S，S)，S)=&(((S，S)，S，S)，S)=&(((a，S)，S，S)， S)=&(((a，a)，S，S)，S)=&(((a，a)，∧，S)，S)=&(((a，a)，∧，(T))，S)=&(((a，a)， ∧，(S))，S)=&(((a，a)，∧，(a))，S)=&(((a，a)，∧，(a))，a) 最右推导： S=&(T)=&(T， S)=&(T， (T))=&(T， S))=&(T， a))=&(T， a))=&(T， a))=&(S， (T， (T， (S， (a， (a，a))=& (a，(a，a)) S=&(T，S)=&(T，a)=&(S，a)=&((T)，a)=&((T，S)，a)=&((T，(T))，a)=&((T，(S))， a)=&((T，(a))，a)=&((T，S，(a))，a)=&((T，∧，(a))，a)=&((S，∧，(a))，a)=&(((T)， ∧，(a))，a)=&(((T，S)，∧，(a))，a)=&(((T，a)，∧，(a))，a)=&(((S，a)，∧，(a))， a)=& (((a，a)，∧，(a))，a) （2）(((a，a)，^，(a))，a)的规范归约如下： (((a，a)，∧，(a))，a) (((S，a)，∧，(a))，a) (((T，a)，∧，(a))，a) (((T，S)，∧，(a))，a) (((T)，∧，(a))，a) ((S，∧，(a))，a) ((T，∧，(a))，a) ((T，S，(a))，a) ((T，(a))，a) ((T，(S))，a) ((T，(T))，a) ((T，S)，a) ((T)，a) (S，a) (T，S)31(T) “移进―归约”过程： 步骤 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 栈 # #( #(( #((( #(((a #(((S #(((T #(((T， #(((T，a #(((T，S #(((T #(((T) #((S #((T #((T， #((T，∧ #((T，S #((T #((T， #((T，( #((T，(a #((T，(S #((T，(T #((T，(T) #((T，S #((T 输入串 (((a，a)，∧，(a))，a)# ((a，a)，∧，(a))，a)# (a，a)，∧，(a))，a)# a，a)，∧，(a))，a)# ，a)，∧，(a))，a)# ，a)，∧，(a))，a)# ，a)，∧，(a))，a)# a)，∧，(a))，a)# )，∧，(a))，a)# )，∧，(a))，a)# )，∧，(a))，a)# ，∧，(a))，a)# ，∧，(a))，a)# ，∧，(a))，a)# ∧，(a))，a)# ，(a))，a)# ，(a))，a)# ，(a))，a)# (a))，a)# a))，a)# ))，a)# ))，a)# ))，a)# )，a)# )，a)# )，a)# 动作 预备 进 进 进 进 归 归 进 进 归 归 进 归 归 进 进 归 归 进 进 进 归 归 进 归 归3226 27 28 29 30 31 32 33 34#((T) #(S #(T #(T， #(T，a #(T，S #(T #(T) #S，a)# ，a)# ，a)# a)# )# )# )# # #进 归 归 进 进 归 归 进 归3 解： （1）FIRSTVT 和 LASTVT 如下： FIRSTVT(S)={a，∧，(} FIRSTVT(T)={， ，a，∧，(} LASTVT(S)={a，∧，)} LASTVT(T)={， ，a，∧，)} （2）构造优先关系表如下：a a ^ ( ) ， # & & &∧() & &， & & & & &# & &&&= &&& && &&=G2 是算符文法，且是算符优先文法。 （3）输入串（a， （a，a） ）的算符优先分析过程如下： 栈 # 输入字符串 (a，(a，a))# 动作 预备33#( #(a #(s #(t #(t， #(t，( #(t，(a #(t，(s #(t，(t #(t，(t #(t，(t，a #(t，(t，s #(t，(t #(t，(t) #(t，s #(t #(t) #s 成功a，(a，a))# ，(a，a))# ，(a，a))# ，(a，a))# (a，a))# a，a))# ，a))# ，a))# ，a))# a))# ))# ))# ))# )# )# )# # #进 进 归 归 进 进 进 归 归 进 进 归 归 进 归 归 进 归4 解： （1） 、0.S’→?S 5.S→?b 10.A→?a 1.S’ →S? 6.S→b? 11.A→a? 2.S→?AS 3.S→A?S 4.S→AS?7.A→?SA8.A→S?A9.A→SA?（2） 、构造识别活前缀的 NFA 如下图所示：341S S 7 ε ε 10 ε 2 ε ε d 5 ε A ε 3 S 8 ε ε 0 aA91146确定化的结果见转换矩阵表： S {0，2，5，7，10} {1，2，5，7，8，10} {2，3，5，7，10} {2，5，7，8，10} {2，3，5，7，9，10} {2，4，5，7，8，10} {11} {6} {1，2，5，7，8，10} {2，5，7，8，10} {2，4，5，7，8，10} {2，5，7，8，10} {2，4，5，7，8，10} {2，5，7，8，10} ? ? A {2，3，5，7，10} {2，3，5，7，9，10} {，3，5，7，10} {2，3，5，7，9，10} {2，3，5，7，10} {2，3，5，7，9，10} ? ? a {11} {11} {11} {11} {11} {11} ? ? b {6} {6} {6} {6} {6} {6} ? ?（3） 、不是 SLR 文法。 I3、I6、I7 有“移进―归约”冲突。 I3：FOLLOW(S’)={#}不包含 a，b。 I6：FOLLOW(S)={#，a，b}包含 a，b； “移进―归约”冲突无法消解。35I7：FOLLOW(A)={a，b}包含 a，b； “移进―归约”冲突消解。 所以不是 SLR 文法。编译原理 G 卷 1．构造正规表达式 a(aa)*bb(bb)*a(aa)* 的 NFA。 2．构造正规表达式((a|b)*|aa)*b 的 NFA。 2．令文法 G[N]为 G[N]: N→D|ND D→0|1|2|3|4|5|6|7|8|9 给出句子 568 的最左、最右推导。 3．给出字母表Σ ={a,b}上的同时只有奇数个 a 和奇数个 b 的所有串的集合的正规文法； 5. 表达式 a*b-c-d$e$f-g-h*i 中， 运算符的优先级由高到低依次为-、 $， *、 且均为右结合， 请写出相应的后缀式。 6．判断文法 G[S]: S → BA A → BS | d B → aA| bS | c 是否为 LL(1)文法. 7．对于文法 G[E]: E→E+T | T T→T+P | P P→(E) | i 写出句型 P+T+(E+i)的所有短语、直接短语、句柄。 8．已知文法 G[A]: A→aABl|a B→Bb|d 试给出消除左递归和回溯与 G[A]等价的 LL(1)文法 G[A′]； 9．将下面的语句翻译成四元式序列： if (x＞y) m= 1; else m=0; 10．将以下 DFA 最小化。 分） （8362b X a 1a ? Y11．设 M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中 f 定义如下： f(x,a)={x,y} f(y,a)=Φ f{x,b}={y} f{y,b}={x,y}试构造相应的确定有限自动机 M′。 （12 分） 12．试构造下述文法的 SLR(1)分析表。 （13 分） G[A]: A→aABl|a B→Bb|d 13．将下面的语句翻译成四元式序列： 分） （7 if (x＞y) m= 1; else m=x+y;14. 试构造下述文法的 LL(1)分析表。 （15 分） G[S]: S→（L）|a L→L，S|S 17．已知文法 G[S]: S→aSbS|bSaS|ε 试证明 G[S]是二义文法 18．将下面的语句翻译成四元式序列： while(a&b) if (c＞d) x=y+z19．构造正规表达式 a(aa)*bb(bb)*a 的最小化的确定有限自动机 M′。21．画出编译程序的总体结构图，简述各部分的主要功能。 22．对于文法 G(S)： S → (L) | aS | a37L → L, S | S (1) 画出句型(S, (a))的语法树。 (2) 写出上述句型的所有短语、直接短语和句柄。 23．构造一文法，使其描述的语言 L = {ω |ω ∈ (a, b) ，且 ω 中含有相同个数的 a 和 b}。 24．分别给出表达式 C(a*(b-c))+d 的逆波兰表示和四元式表示。 25．把下列语句翻译为四元式序列： while (A & B) if (C & D) X = Y * Z else X = Y + Z 26．构造一个 DFA，它接受Σ = {0, 1}上所有满足如下条件的字符串：每个 1 后面都有 0 直接跟在右边。 27．已知文法 G(S)： S→S*aP| aP| *aP P→+aP| +a (1) 将文法 G(S)改写为 LL(1)文法 G’(S)； (2) 写出文法 G’(S)的预测分析表。 28．已知文法 G(S)： S→aS | bS | a (1) 构造识别该文法所产生的活前缀的 DFA； (2) 判断该文法是 LR(0)还是 SLR(1)，并构造所属文法的 LR 分析表。 29．将下图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。其中，X 为 初态，Y 为终态。*38b 2 b a b 3 ? a ? b 4 b a Ya a X 1?30． 对正规式(a|b)*abb 构造其等价的 NFA。 31． 下面的文法产生 0 和 1 的串，即二进制的正整数，请给出决定每个二进制数的值（十 进制形式）的语法制导定义。 32．把算术表达式?(a + b) ? (c + d) + (e+ f) 翻译成等价的四元式序列（序号从 0 开 始） 。 33．设有文法 G[S]: S→a|（T）|? T→T,S|S 试给出句子(a,a,a)的最左推导。 34．已知文法Ｇ： S → ( L → S L | a , L | )判断是不是 LL（1）文法，如果是请构造文法 Ｇ 的预测分析表，如果不是请说明理由。 35．文法 S ? A a | b A c | d c | b d a A ? d 36． 将下图所示的确定有限自动机(DFA)最小化。其中，X 为初态，Y 为终态。39a a X b 2 1 b a3 abYb37．请画出识别无符号十进制整数的状态转换图 38．设有文法 G[S]: S→S*S|S+S|(S)|i 该文法是否为二义文法,并说明理由？ 40．把下列语句翻译为四元式序列（四元式序号从 1 开始） ： while (A & B) if (C & D) X = Y * Z else X = Y + Z 41.构造下面文法的 LL（1）分析表。 G[D]: D ? TL T ? int | real L ? id R R ? , id R | ? 42．给定文法 S→aS|bS|a，下面是拓广文法和识别该文法所产生的活前缀的 DFA。判断该文 法是否是 SLR(1)文法：如果是构造其 SLR(1)分析表，如果不是请说明理由。(1)将文法 G(S)拓广为 G(S’)： (0)S’→S (1)S→aS (2)S→bS (3)S→a40(2)识别该文法所产生的活前缀的 DFA 如图 1 所示。图143．给出表达式-a*b+b*c+d/e 的语法树和三元式序列。 44．证明下面文法 S→AaAb|BbBa A→ε 法。 45．现有文法 G[S] S→a|ε |(T) T→T,S|S 请给出句子（a,(a,a)）的最左、最右推导，并指出最右推导中每一个句型的句柄。 46．将下图的 DFA 最小化。 B→ε ，是 LL（1）文法，但不是 SLR（1）文a a 0 b1b b 3 a b b 4 a2 a47．设有如下文法：P→D D→D；D|id：T|proc id；D； T→real|integer41给出一个语法制导定义，打印该程序一共声明了多少个 id。 48． 识别文法 G 的活前缀的 DFA 如下图所示， 补充完成状态 I2 和 I5， 然后根据该图构造 SLR （1）分析表。 G：(0) P'→P (4) Q→bSc (5) (1) S→SaP I2 : a P a b I8 :Q→bQc. Q Q I3 :P→Q. b I6 : S→a. S a a I10 :Q→bS.c S→S.a c I11 :Q→bSc. I5 : Q b c I9 :Q→bQ.c b I7 :P→aPb.P→aPb(2) P→Q (6) S→a(3) Q→bQcI1 :P'→P. I4 :P→aP.bI0 :P'→.P P→.aPb P→.Q Q→.bQc Q→.bScI12 : S→Sa.49．给出表达式（a+b）*(c+d/e)的语法树和四元式序列。50．构造文法 S→AaAb|BbBaA→εB→ε ，的预测分析表。51．写出 C 语言标识符集（字母或下划线开头的由字母、数字、下划线构成的串）的正规式。53．假设第一个四元式的序号是 100，写出布尔表达式 a&b∨c∧d&e 的四元式序列。 54．设有如下文法： G[E]：E→EWT|T T→T/F|F F→（E）|a|b|c42W→+|证明符号串 a/(b-c)是句子。55．对于下列文法 G[S]： S→Sb|bA A→aA|a （1）构造一个与 G 等价的 LL（1）文法 G′。 （2）对于文法 G′,构造相应的 LL（1）分析表。 56．构造下述文法的 SLR（1）分析表。 G[S]：S→（A） A→ABB|B B→b58．写出赋值语句 X= -(a+b)/(c-d)-(a+b*c)的逆波兰表示。 59．为文法 G[S]：S→（L）|a L→L，S|S 写一语法制导定义，它输出句子中括号嵌套的最大层次数。60．2．已知文法 G[S]如下：构造该文法的 LR（0）分析表。 G[S]：S→BB B→aB|b g 卷答案 1 解：2 5 6a X a 1a b 3 bb 4b aa Ya433a X ? 1 ?a ? 2 b Y?2 解：a4b2 解：最左推导：N ? ND ? NDD ? DDD ? 5DD ? 56D ? 568 最右推导：N ? ND ? N8 3 解： G[S]：S→aA|bB A→aS|bC|b B→bS|aC|a C→bA|aB|ε 5 解： abcd- -*efgh- - i*$$ 6 解：对于该文法求其 FIRST 集如下： FIRST(S) = {a, b, c}; FIRST(A) = {a, b, c, d}; FIRST(B) = {a, b, c}。 求其 FOLLOW 集如下： FOLLOW(S) = {a, b, c, d, #}; FOLLOW(A) = {a, b, c, d, #}; FOLLOW(B) = {a, b, c, d, #}。 由 A → BS | d 得： FIRST(BS) ∩ FIRST(‘d’) = {a, b, c} ∩ {d} = Φ 由 B → aA| bS | c 得 FIRST(aA) ∩ FIRST(bS) ∩ FIRST(c) = {a} ∩{b}∩ {c} =Φ 由于文法 G[S]不存在形如β →ε 的产生式， 故无需求解形如 FIRST(α ) ∩ FOLLOW(A) 的值，也即文法 G[S]是一个 LL(1)文法。 7 解：短语：P、P+T、i、E+i、(E+i )、P+T+(E+i )； 直接短语：P、i； 句柄：P； 8 解：G[A′]：A→aA′ A′→ABl | ε44? ND8 ? N68 ? D68 ? 568B→dB′ B′→bB′| ε 9 解：1 (j＞,x,y,3) 2 (j,_,_,5) 3 (=,1,_,m) 4 (j,_,_,6) 5 (=,0,_,m) 6: 10 解：a 0 b 111 解：对照自动机的定义 M=(S,Σ ,f,So,Z)，由 f 的定义可知 f(x,a)、f(y,b)均为多值函 数，因此 M 是一非确定有限自动机。 先画出 NFA M 相应的状态图，如下图所示。a a b bXYbI {x} {y} {x,y}Ia {x,y} ― {x,y}Ib {y} {x,y} {x,y}将转换矩阵中的所有子集重新命名，形成下表所示的状态转换矩阵，即得到f 状态 0 1 2 字符 a 2 ― 2 b 1 2 245M′=({0,1,2},{a,b},f,0,{1,2})，M′状态转换图如下图所示。a 0 b 1 b 2 a, b（注意：本题由于集合的命名和先后顺序不同，可能最终结果不同。 ） 12 解：拓广文法 （0）S→A （1）A→aABl （2）A→a （3）B→Bb （4）B→dI0：S→．A A→．aABl A→．a I1： S→A． a I2：A→a．ABl A A→a． A→．aABl A→．aI3： A→aA．Bl B→．Bb B→．d BdI4： B→d．aI5： A→aAB．l B→B．b b I7： B→Bb．lI6： A→aABl．46First（A）={a}follow（A）={#，d} First（B）={d}follow（B）={l} SLR（1）分析表如下： a 0 1 2 3 4 5 6 7 13 解：1 (j＞,x,y,3) 2 (j,_,_,5) 3 (=,1,_,m) 4 (j,_,_,7) 5 (+,x,y,T1) 6 (=, T1,_,m) 7: 14 解：消除左递归： G(S): S ? (L) | a L ? SL’ L’ ? , SL’| ε S7 R1 R3 S2 R2 S4 R4 S6 R1 S2 ACC R2 3 5 b d l # A 1 B构造 FIRST 集，如下： （1）FIRST(S) = {(, a} （2）FIRST(L) = {(, a} （3）FIRST(L’) = {,, ε }47构造 FOLLOW 集如下： （1）FOLLOW(S) = {#, ,, )} （2）FOLLOW(L) = {)} （3）FOLLOW(L’) = {)}LL(1)分析表 ( S L L’ ε ? ,SL’ S ? (L) L ? SL’ L’ ? ) a S ? a L ? SL’ L’ , #17 证明： 该文法产生的语言是 a 的个数和 b 的个数相等的串的集合。该文法二义，例如句 子 abab 有两种不同的最左推导。 S ? aSbS ? abS ? abaSbS ? ababS ? abab S ? aSbS ? abSaSbS ? abaSbS ? ababS ? abab18 解：100 (j&,a,b,102) 101 (j,_,_,107) 102 (j&,c,d,104) 103 (j,_,_,106) 104 (+,y ,z ,t) 105 (=,t ,_ ,x) 106 (j,_,_,100) 107: 19 解： 先画出正规式相应的 NFA M 状态图，如下图所示。2 5a X a 1a b 3 bb 4b a Y48用子集法构造状态转换矩阵，如下表所示。I {x} {1} {2} {3} {4} {5} {Y}Ia {1} {2} {1} {Y} -Ib {3} {4} {5} {4} -将状态分为终态集{Y}和非终态集{X,1,2,3,4,5} 因为｛X,1,2,3,4,5｝a={1,2,1,_,Y,_} 所以非终态集分为{X,1,2},{3,5},{4} 因为{X,1,2}b={_,3,_},所以分为 最后得到集合{X,2},{1},{3,5},{4},{Y}重新命名为 1，2，3，4，5 得到最小化的 DFA M′ 状态转换矩阵和状态转换图如下图所示。I 1 2 3 4 5Ia 2 1 5 -Ib _ 3 4 3 _1a a2b3b4a5b49（注意：本题由于集合的命名和先后顺序不同，可能最终结果不同。 ） 21 解：编译程序的总体框图如下所示：表 词法分析器 单词符号 语法分析器 语法单位语义分析与中间代码 生成器出格错管四元式 优化段 四元式 目标代码生成器 目标代码处理理（1）词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出 一个个单词符号，其输出结果是二元式(单词种别，单词自身的值)流。 （2）语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约） ，识别 出程序中的各类语法单位，最终判断输入串是否构成语法上正确的句子。 （3）语义分析及中间代码生成器，按照语义规则对语法分析器归约出（或推导出）的语 法单位进行语义分析并把它们翻译成一定形式的中间代码。 编译程序可以根据不同的需要选 择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。 （4）优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因 此要做中间代码的优化， 其过程实际上是对中间代码进行等价替换， 使程序在执行时能更快， 并占用更小的空间。 （5）目标代码生成器，把中间代码翻译成目标程序。中间代码一般是一种与机器无关的 表示形式，只有把它再翻译成与机器硬件直接相关的机器能识别的语言，即目标程序，才能 在机器上运行。 （6） 表格管理模块保持一系列的表格， 登记源程序的各类信息和编译各阶段的进展状况。 编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取， 整个编译过程都在不断和表格打交道。 （7）出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应 设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错 处理程序要对发现的错误进行处理、记录，并反映给用户。 22 解：50(1) 句型(S, (a))的语法树如下图所示：S(L)L,SS(L)Sa(2) 从语法树中可以找到（3 分）短语：a; (a); S; S,(a); (S, (a)) 直接短语： S 句柄： S 23 解： S→ ε | aA|bB A→ b| bS| aAA B→ a| aS| bBB 24 解： （1）逆波兰式： abc-*@d+ 其中使用@代表一目减运算 （2）四元式： ① (-, b, c, T1) ② (*, a, T1, T2) ③ (@, T2, _, T3) ④ (+, T3, d, T4) 25 解： (1) (j&, A, B, 3) (2) (j, _, _, 11) (3) (j&, C, D, 5) (4) (j, _, _, 8) (5) (*, Y, Z, T1) (6) (=, T1, _, X)51(7) (j, _, _, 1) (8) (+, Y, Z, T2) (9) (=, T2, _, X) (10) (j, _, _, 1) (11) 26 解： （1）0*(0|10)*0* 或者 (0|10)* （2） ①NFA （2 分）0 X ε 0 1 ε 10 ε 3 0 20 ε Y②子集法确定化 I {X, 0, 1, 3, Y} {0, 1, 3, Y} {2} {1, 3, Y} 重新命名状态，即得： S 1 2 3 4 ③ 最小化 首先分为终态集和非终态集 {3} {1, 2, 4} 因为 10 = 2 20 = 2 40 = 4 状态均属于集 合{1, 2, 4}，所以对于输入符号 0 不能区分开 1，2，4 三个状态；11 = 3 21 = 3 41 = 3 0 2 2 4 4 1 3 3 3 I0 {0, 1, 3, Y} {0, 1, 3, Y} {1, 3, Y} {1, 3, Y} I1 {2} {2} {2}52状态均属于集合{3}，所以对于输入符号 1 也不能区分开 1，2，4 三个状态；因此最终的状 态划分即为: {3} {1, 2, 4}，其对应的 DFA 如下图所示： 0 1 0 0 128 解： （1）将文法 G(S)拓广为 G’(S’)： (0) S’→S (1) S→aS (2) S→bS (3) S→a 识别该文法所产生的活前缀的 DFA：I4: S’→ aS? S I2: S→ a?S S→ ?aS S→ ?bS S→ ?a S→ a? aa I0: S’→ ?S S→ ?aS S→ ?bS S→ ?a b S I1: S’→ S?baI3: S→ b?S S→ ?aS S→ ?bS S→ ?a S’→ bS? SbI5:（2）在状态 I2 存在“移近-归约”冲突，因此该文法不是 LR(0)文法。 计算 S 的 FOLLOW 集合： FOLLOW(S)= {#} I2 中的冲突用 FOLLOW 集合可以解决，所以该文法是 SLR(1)文法。53构造 SLR(1)分析表如下： ACTION 状态 a 0 1 2 3 4 5 s2 s2 s3 s3 r1 r2 s2 b s3 acc r3 4 5 # S 1 GOTO29【解】 用子集法将 NFA 确定化，如图所示。I {X} {1} {3} {2,3,Y} {3,Y} {3,4} {3,4,Y}Ia {1} {2,3,Y} ― {2,3,Y} {2,3,Y] {3,4} {2,3,4,Y}Ib {3} {3,Y} {3,4} {2,3,4,Y} {3,4} {3,4,Y} {3,4,Y} 重新命名S 0 1 2 3 4 5 6 7a 1 3 ― 3 3 5 6 6b 2 4 5 6 5 7 6 7{2,3,4,Y} {2,3,4,Y} {2,3,4,Y}确定化的 DFA 如下图所示：a 3 a 4 b 2 b b 5 a b 7 a aa a 0 1 bb6bb5430．解: 31【解】定义值属性为.val，翻译方案如下：B ? B1 0 { B.val = B1.val ? 2 } B ? B1 1 { B.val = B1.val ? 2 + 1 } B ? 1 { B.val = 1 } B ? 0 { B.val = 0 }32【解】 0（+，a, b ,T1） 1（uminus，T1，-，T2） 2（+，c, d , T3） 3（*，T2，T3，T4） 4（+，e，f，T5） 5（+，T4，T5，T6）33【解】(1) (a,a,a)的最左推导 S=&(T) =&(T,S) =&( T,S,S) =&( S,S,S) =&(a,S,S) =&(a,a,S) =&(a,a,a) 34【解】 1）求各非终结符的 FISRT 集和 FOLLOW 集： = { (, a ) FIRST(L) = { a }? FIRST(S) = { (, ), a } FOLLOW(S) = {, # } FOLLOW(L) = FOLLOW(S) ={ , FIRST(( FIRST(S L)∩{a}=Φ , L)∩{)}=Φ # }所以是 LL（1）文法552）预测分析表： ( S L 35 【解】 S’ ? .S S ? .A a S ? .b A c S ? .d c S ? .b d a A ? .d I0 d S ? d .c A?d. I4 S S’ ? S . I1 S ? A .a I2 S ? b .A c S ? b .d a A ? .d I3 S?dc. I8 a S?Aa. I5 S ? b A .c I6 S ? b d .a A?d. I7 c S?bAc. I9 S?bda. I10 S→ ( L L→ S , L a S→ a L→ S , L L → ) , } #AbAdacFollow(S)={#} Follow(A)={a,c} I4 存在冲突且 Follow(A)∩{c}={ c} I7 存在冲突且 Follow(A)∩{a}={ a} 所以不是 SLR(1)文法 36【解】 先划分为终态集{Y}和非终态集 I={X,1,2,3} X 面对输入符号 b 时下一状态属于 I， 1,2,3 面对输入符号 b 时下一状态属于{Y}， 而 故划分 为{X}、{1,2,3} 非终态 2 和非终态 3 面对输入符号 a 的下一状态相同， 1 不同， 而 即最简状态{X}、 {1}、 {2， 3}、{Y}。按顺序重新命名为 0、1、2、3，则得到最简 DFA，56a 0 a b1 a 2b 3b37． 【解】１-９ 1０-９ 2 0?(其它)338【解】该文法是二义文法，因为该文法存在句子 i*i+i,该句子有两棵不同的语法树如图 所示。S S i(1)S S S i + S i S i S * S i(2)*+S i39【解】属性 num 表示 id 个数 print(D.num) D.num = D(1).num + D(2).num D.num = 1 D.num = D(1).num + 1P → D D → D(1)；D(2) D → id : T D → D(1); S40【解】(1) (j&, A, B, 3) (2) (j, _, _, 11) (3) (j&, C, D, 5) (4) (j, _, _, 8) (5) (*, Y, Z, T1) (6) (=, T1, _, X)57(7) (j, _, _, 1) (8) (+, Y, Z, T2) (9) (=, T2, _, X) (10) (j, _, _, 1) (11) 41【解】FIRST(T)={ int FIRST(L)={ id FIRST(R)={ , FIRST(D)={ int } ?} real } FOLLOW(T)={ id } FOLLOW(L)={ #} FOLLOW(R)={ #}real } FOLLOW(D)={#}因为 FIRST(int)∩FIRST(real)=Φ FIRST(, id R)∩FOLLOW(R)=Φ 所以是 LL（1）文法，LL（1）分析表如下： int D T L R D ? TL T ? int real D ? TL T ? real L ? id R R ? , id R R ? ? id , #42【解】注意到状态 I1 存在“移进-归纳”冲突，计算 S 的 FOLLOW 集合： FOLLOW(S)={#} {a}∩{b}∩FOLLOW(R)=Φ 可以采用 SLR 冲突消解法，得到如下的 SLR 分析表。 从分析表可以看出，表中没有冲突项，所以该文法是 SLR(1)文法。表 1 SLR 分析表 ACTION 状态 0 1 a S1 S1 b S2 S2 r3 # GOTO S 3 4582 3 4 5S1S2 acc r1 r2543 答：语法树三元式++ * * b c d b/①（-，a，-） ②（*，①，b） ③（*，b，c） ④（+，②，③） ⑤（/，d，e） ⑥（+，④，⑤）e-a44 证明： （1）first（AaAb）={a} first（BbBb）={b} ，有 first（AaAb）∩first（BbBb）=Φ所以根据 LL（1）文法的定义，该文法是 LL（1）文法。 分） （2 （2）为了构造识别活前缀的 DFA，初态集包含如下四个项目：S→.AaAb B→. 但该项目中有两个可归约项目：A→. B→.，产生归约-归约冲突，而 follow（A）={a， S→.BbBa A→.b}，follow（B）={a，b}，有 follow（A）∩follow（B）≠Φ ，所以使用向前看一个终结 符的方法不能解决此冲突，所以该文法不是 SLR（1）文法。 分） （345 答：最左推导：S=〉 （T）=〉 （T，S）=〉 （S，S）=〉 （a，S）=〉 （T） （a， （a， ）=〉 （T， S） （a， ）=〉 （S，S） （a， ）=〉 （a，S） （a， ）=〉 （a，a） ） 最右推导： S=〉 （T）=〉 （T，S）=〉 （T） （T， （T， ）=〉 （T，S） （T， ）=〉 （T，a） （T， ）=〉 （S，a） ）=〉 （T， （a，a） （S， ）=〉 （a，a） （a， ）=〉 （a，a） ） 句型的句柄是为加下划线的部分5946 答：初始划分：II={{0，1，2}，{3，4}}（1 分） （1）考查{0，1，2}，1 和 2 接受 a，b 后都转向相同的状态，且接受 b 后转向终态， 而 0 接受 b 后转向非终态 2，所以 0 与 1，2 可分，IInew={{0}，{1，2}，{3，4}}(1 分) （2）考查{3，4}，接受 a，b 后都转向相同的状态，所以 3，4 不可分。IInew={{0}， {1，2}，{3，4}}（1 分） 将 1，2 合并用 1 代表，3，4 合并用 3 代表，最终的最小化 DFA 如下：a 0 b 1 b a b 347 答： 文法 P→D D→D1；D2 D→id：T D→proc id；D1； T→real T→integer 48 答：I2，I5 分别如下图所示： I2 :P→a.Pb P→.aPb P→.Q Q→.bQc Q→.bSc I5 :Q→b.Qc Q→b.Sc Q→.bQc Q→.bSc S→.Sa S→.a 语法制导定义 Print（D.num） D.num=D1.num+D2.num D.num=1 D.num=D1.num+1Follow（P）={b，$} 1 分 Follow（Q）={ b，c，$} 1 分 Follow（S）={c，a} SLR（1）分析表： 1分Action 表 a 0 S2 b S5 c $ P 1GOTO 表 Q 360S1 2 3 4 5 6 7 8 9 10 11 12 R5 S12 R4 S6 R6 R1 R3 R3 S8 S11 R4 R5 S2 S5 R2 S7 S5 R6Acc 4 R2 3910R1 R3R449 答:语法树如下：四元式序列：* + + / a b c d e①（+，a，b，T1） ②（/，d，e，T2） ③（+，c，T2，T3） ④（*，T1，T3，T4）50 答：first（S）={a，b},First（AaAb）={a}，First（BbBa ）={b} Follow（A）={a，b} Follow（B）={a，b}a S A S→AaAb A→εb S→BbBa A→ε$61BB→εB→ε51 解答：用 D 表示数字 0-9，用 L 表示字母 a-z|A-Z，则 C 语言标识符的正规式为： （L|_） （L|D|_）* 54 解答： 有推导 E?T?T/F?F/F?a/F?a/(E)?a/(EWT)? a/(TWT)? a/(FWT)? a/(bWT)? a/(b-T)? a/(b-c)，即从文法开始符号 E 能够推导出 a/(b-c)，所以 a/(b-c)是文法 G[E] 的句子。 55 解： （1） 分）G′：S→bAS′ （5 S′→b S′|ε A→aA′ A′→A|ε （2） 分）FIRST（S）={ b } （1 FIRST（S′）={ b，ε } FIRST（A）={a} FIRST（A′）={a，ε } FOLLOW（S）={#} FOLLOW（S′）={#} FOLLOW（A）={b，#} FOLLOW（A′）=（b，#） LL（1）分析表：a S S′ A A′ A→aA′ A′→Ab S→bAS′ S′→b S′#S′→εA′→εA′→ε56 解：拓广文法： 分） （1 S′→S （0）S→（A） （1）62A→ABB A→B B→b（2） （3） （4）识别活前缀的 DFA： 分） （4I0：S′→.S S→.(A) S I1：S′→S. ( ) I2：S→(.A) A→.ABB A→.B B→.b B I5： A→B. I4： B→b. A I3：S→(A.) A→A.BB B→.b b I6： S→(A). B I7：A→AB.B B→.b B I8：A→ABB.bFIRST 集和 follow 集： 分） （1 First（S）={（，c} First（A）={b} First（B）={b} follow( S)={#} follow(A)={b,)} follow(B)={b,)}SLR(1)分析表： 分） （4 ACTION （ 0 1 2 3 4 S6 R4 S4 S4 R4 S2 Acc 3 5 7 ） b # S 1 GOTO A B635 6 7 8R3R3 R1 S4 8R2R258 Xab+-cd-/abc*+-= 59 解： 使用 num 属性描述括号的嵌套最大层次数 S?→S S→（L） S→a L→L ，S L→S 60 解：拓广文法： 分） （1 （0）S?→S （1）S→BB （2）B→aB （3）B→b 识别活前缀的 DFA 如下：(1)print（S.num） S.num=L.num+1 S.num=0 L.num=if L .num&S.num then L .num else S.num(1) (1)L.num= S.num64I0： S??.S S?.BB B?.ab B?.b b a I3： a B?a.B B?.ab B?.b B I6： B?aB.SI1： S??S.BI2： S?B.B B?.ab B?.b bBI5： S?BB.b a bI4： B?b.LR(0)分析表如下：状态 a 0 1 2 3 4 5 6 S3 S3 R3 R1 R2 S3Action b S4 acc S4 S4 R3 R1 R2 R3 R1 R2 # S 1Goto B 25 6编译原理 H 卷 2、令文法 G 为 （1） （2）N ? D | ND D ? 0 |1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9文法 G 的语言 L（G）是什么？（4 分） 给出句子 34 和 568 的最左推导和最右推导。 分） （6( | ) 3、构造正规式 1 01*101 相应的 DFA，并将 DFA 确定化、最小化。 分） （100655、令文法 G 为： T ? T ? F | FF ?E ? E ? T | T?E ? |i证明 E ? T ? F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 （12 分）E ? E ?T ? E ?T*F6、一个编译程序的代码生成要着重考虑哪些问题?（6 分） 7、编译过程中可进行的优化如何分类？最常用的代码优化技术有哪些？（8 分） 8、有哪些存储分配策略？并叙述何时用何种存储分配策略？（8 分） 9、请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列。 （12 分）二（每小题 10 分，共 80 分）简答题 1.画出编译程序的总体结构图，简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b) *a(a|b)构造一个确定的有限自动机。 4． 设文法 G(S)： S→(L)|a S|a L→L，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的 FIRST 和 FOLLOW； (3) 构造预测分析表。 5． A-&aAd| aAb|ε 判断该文法是否 SLR（1）文法，若是构造相应分析表，并对输入串 ab#给出分析过程。 6． 构造算符文法 G[H]的算符优先关系（含＃） 。 G[H]：H→H;M|M M→d|aHb 7．已构造出文法 G（S）66已知文法（1）S （2）B （3）BBB aB b1） 。给出 DFA 图 2）.给出 LR 分析表 3） ．假定输入串为 abaab，请给出 LR 分析过程（即状态，符号，输入串的变化过程） 。 8． 将下面的语句翻译成四元式序列： while A&C∧B&D do if A=1 then C:=C+l else while A? D do A:=A+2； 9． 对下面的流图， (1)求出流图中各结点 N 的必经结点集 D(n)， (2)求出流图中的回边， (3)求出流图中的循环。H 卷答案 2 解：(1) L(G1 ) 是 0~9 组成的数字串 (2) 最左推导:N ? ND ? DD ? 3D ? 34 N ? ND ? NDD ? DDD ? 5DD ? 56 D ? 568 N ? ND ? N 4 ? D4 ? 34 N ? ND ? N 8 ? ND8 ? N 68 ? D68 ? 568最右推导: 3 解： X12 0345Y1??101671 确定化： 0 {X} φ {1,2,3} {2,3} {2,3,4} {2,3,5} {2,3,4,Y} 最小化： φ φ {2,3} {2,3} {2,3,5} {2,3} {2,3,5} 1 {1,2,3} φ {2,3,4} {2,3,4} {2,3,4} {2,3,4,Y} {2,3,4}{0,1,2,3,4,5},{6} {0,1,2,3,4,5} ? {1,3,5} {0,1,2,3,4 ,5} ? {1,2 ,4 ,6} 0 1 {0,1,2,3,4},{5},{6} {0,1,2,3,4} ? {1,3,5} 0 {0,1,2,3},{4},{5},{6} {0,1,2,3} ? {1,3} {0,1,2 ,3} ? {1,2,4} 0 1 {0,1},{2,3}{4},{5},{6} {0,1} ? {1} {0,1} ? {1,2} 0 1 {2,3} ? {3} {2,3} ? {4} 0 1 {0},{1},{2,3},{4},{5},{6}5 解：短语: E+T*F, T*F 直接短语: T*F 句柄: T*F6 答：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占 用空间和执行效率两个方面综合考虑。7 答：依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。 最常用的代码优化技术有 1. 删除多余运算；2. 代码外提；3. 强度削弱；4. 变换循环控 制条件；5. 合并已知量与复写传播；6. 删除无用赋值8 答：静态分配策略：如果在编译时能确定数据空间的大小，则可采用静态分配方法：在编 译时刻为每个数据项目确定出在运行时刻的存储空间中的位置。 动态分配策略： 如果在编译 时不能确定运行时数据空间的大小， 则必须采用动态分配方法。 允许递归过程和动态申请释68放内存。包括：栈式动态分配和堆式动态分配9 解： (1) (+ (2) (+三元式 a, c, b) d)间接三元式 间接三元式序列 (1) (+ (2) (+ a, c, b) d) 间接码表 (1) (2) (3) (4) (1) (5) 四元式(3) (* (1), (2)) (4) (- (3), /) (5) (+ a, b)(3) (* (1), (2)) (4) ((3), /)(6) (- (4), (5))(5) (-(4), (1))(1) (+,a,b, t1)(2) (+, c, d, t2) (4) (-, t3, /, t4) (6) (-, t4, t5, t6)(3) (*, t1, t2, t3) (5) (+, a, b, t5)二．简答题 1． 【解答】 编译程序的总体结构图如图 1.2 所示。 词法分析器：输入源程序，进行词法分析，输出单词符号。 语法分析器：在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号串分 解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。 中间代码生成器：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定 形式的中间代码，比如说四元式。 优化：对中间代码进行优化处理。 目标代码生成器：把中间代码翻译成目标语言程序。 表格管理模块保存一系列的表格， 登记源程序的各类信息和编译各阶段的进展情况。 编 译程序各阶段所产生的中间结果都记录在表格中， 所需信息多数都需从表格中获取， 整个编 译过程都在不断地和表格打交道。 出错处理程序对出现在源程序中的错误进行处理。 此外， 编译的各阶段都可能出现错误， 出错处理程序对发现的错误都及时进行处理。692．【解答】该句型对应的语法树如下：该句型相对于 E 的短语有 FF^^*；相对于 T 的短语有 FF^^*,F; 相对于 F 的短语有 F^;F^^;简单短语有 F;F^;句柄为 F. 3． 【解答】最简 DFA 如图 2.66 所示。4． (1)【解答】S→(L)|aS’ S’→S|ε L→SL’ L’→SL’|ε 评分细则：消除左递归 2 分，提公共因子 2 分。 (2) FIRST 和 FOLLOW FIRST)S)＝{(，a} FIRST(S’)＝{，a,ε } FIRST(L)＝{(，a} FIRST(L’)＝{， } ，ε 5． 【解答】 FOLLOW(S)＝{#，，)} ， FOLLOW(S’)＝{#，，)} ， FOLLOW(L)＝{ )} FOLLOW(L’〕＝{ )}(1)拓广文法 (0)S-&A (1) A-&aAd (2)A-& aAb (3)A-&ε(2)构造识别活前缀的 DFAFOLLOW(A)={d,b,#} 对于状态 I0：FOLLOW(A)∩{a}=Ф 对于状态 I1：FOLLOW(A)∩{a}=Ф 因为，在 DFA 中无冲突的现象，所以该文法是 SLR(1)文法。 (3)SLR(1)分析表 状态 a ACTION B GOTO d # A700 1 2 3 4 5S2r3r3r3 acc1S2r3 S5 r1 r2r3 S4 r1 r2r33r1 r2(4)串 ab#的分析过程 步骤 串 1 2 3 4 5 0 02 023 0235 01 动作 # #a #aA #aAb #A # a b b # b# # # 移进 归约 A-&ε 移进 归约 A-& aAb 接受 状态栈 符号栈 当前字符 剩余字符6．【解答】 由 M→d 和 M→a?得：FIRSTVT(M)=｛d,a｝ ； 由 H-H;?得：FIRSTVT(H)=｛； ｝ 由 H→M 得：FIRSTVT(M) cFIRSTVT(H)，即 FIRSTVT(H)={;,d,a} 由 M→d 和 M→?b 得：LASTVT(M)={d,b}； 由 H---， 得：LASTVT(H)=｛；； ；m ｝ 由 H→M 得：LASTVT（M）cLASTVT(H） ，即 LASTVT(H)=｛;,d,b} 对文法开始符 H,有#H#存在， 即有＃=＃， #&FIRSTVT(H)， LASTVT(H)&#,也即＃＜； #&d. ，#&a,；＞＃，d&#, b&#。 对形如 P→?ab?，或 P→?aQb?，有 a=b，由 M→a|b 得：a=b； 对形如 P→?aR?，而 b∈FIRSTVT(R)，有 a&b，对形如 P→?Rb?，而 a∈LASTVT(R)． 有 a&b。 由 H→?；M 得： ；&FIRSTVT(M)，即： ：&d， ：&a 由 M→aH?得：a&FIRSTVT(H)，即：a＜； ，a&d，a＜a71由 H→H；’’?得：LASTVT(H)&;，即： ；＞； ，d&； ，b＞； 由 M→?Hb 得：LASTVT(H)&b，即： ；＞b，d&b，b＞b 由此得到算符优先关系表，见表 3.5。7．【解答】（1）LR 分析表如下： （2）分析表状态 a 0 1 2 3 4 5 6 S3 s3 r3 R1 R2 s3ACTION b s4GOTO # S 1 acc S4 s4 r3 R1 R2 r1 R2 5 6 B 2(3) 句子 abaab 的分析过程 表:句子 abaab 的分析过程 步骤 0 1 2 3 4 5 6 7 8 #0 #03 #034 #036 #02 #023 # #02336 状态 # #a #ab #aB #B #Ba #Baa #Baab #BaaB 符号栈 abaad# baad# aab# aab# aab# ab# b# # #72输入串所得产生式B→b B→aB9 10 11 12 13# #01 # 识别成功 ##BaB #BB #S d#ad# ad# d#8．【解答】该语句的四元式序列如下（其中 E1、E2 和 E3 分别对应：A&C∧B&D, A=1 和 A?D 并且关系 运算符优先级高） ： 100 (j&,A,C,102) 101(j,_,_,113） 102 (j&,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108） 106 (＋,C,1,C) 107 (j,_,_,112) 108 (j?,A,D,110) 109 (j,_,_,112) 110 (＋,A,2,A) 111 (j,_,_,108) */ 112(j,_,_,100) */ 113 9． 【解答】 /*转回外层 while 语句开始处 /*E1 为 F*/ /*El 为 T*/ /*El 为 F*/ /*Ez 为 T*/ /*EZ 为 F*/ /*C:=C+1*/ /*跳过 else 后的语句*/ /*E3 为 T*/ /*E3 为 F*/ /*A:=A+2*/ /*转回内层 while 语句开始处(1)流图中各结点 N 的必经结点集 D(n)， D(l)＝{1}，D(2)＝{1,2}，D(3)＝{1,2,3}，D(4)={1,2,3,4}，D(5)＝{1,2,5}， D(6)＝{1,2,5,6} (2)求出流图中的回边，735-&2，4-&3 (3)求出流图中的循环: 回边 5-&2 对应的循环：2、5、3、4； 回边 4-&3 对应的循环：3、4编译原理 I 卷 1 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 第 3 题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 第 4 题 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、 代码生成）报告的。（1） else 没有匹配的 if （2） 数组下标越界 （3） 使用的函数没有定义 （4） 在数中出现非数字字符 第 5 题 编译程序大致有哪几种开发技术？ 第 1 题 文法 G＝({A,B,S},{a,b,c},P,S)其中 P 为： S→Ac|aB A→ab B→bc74写出 L(G[S])的全部元素。第３题 为只包含数字、加号和减号的表达式，例如 9-2＋5，3-1，７等构造一个文法。 第 4 题 已知文法 G[Z]： Z→aZb|ab 写出 L(G[Z])的全部元素。 第 5 题 写一文法，使其语言是偶正整数的集合。 要求： (1) 允许 0 打头； (2)不允许 0 打头。 第 6 题 已知文法 G： &表达式&::=&项&｜&表达式&＋&项& &项&::=&因子&｜&项&*&因子& &因子&::=（&表达式&）｜i 试给出下述表达式的推导。 （1）i+(i+i) （2）i+i*i 第 7 题 证明下述文法 G[〈表达式〉]是二义的。 〈表达式〉∷=a|(〈表达式〉)|〈表达式〉 〈运算符〉 〈表达式〉 〈运算符〉∷=+|-|*|/ 8.文法 G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 第 9 题75考虑下面上下文无关文法： S→SS*|SS+|a (1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树。 (2)G[S]的语言是什么？ 第 10 题 文法 S→S(S)S|ε (1) 生成的语言是什么？ (2) 该文法是二义的吗？说明理由。 第 11 题 令文法 G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明 E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 第 14 题 给出生成下述语言的上下文无关文法： （1）{ a b a b | n，m&=0} （2）{ 1 0 1 0 | n，m&=0} 第 16 题 给出生成下述语言的三型文法：n m m n n n m m(1){a |n &=0 }n(2) { a b |n,m&=1 }n m(3){a b c |n,m,k&=0 } 第 18 题 解释下列术语和概念： （１） 字母表 （２） 串、字和句子76n m k（３） 语言、语法和语义 附加题 问题 1： 给出下述文法所对应的正规式： S→0A|1B A→1S|1 B→0S|0 问题 2： 已知文法 G[A]，写出它定义的语言描述 G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 问题 3： 给出语言描述，构造文法. 构造一文法,其定义的语言是由算符+, *, (,)和运算对象 a 构成的算术表达式的集合. 问题 4： 已知文法 G[S]: S→dAB A→aA|a B→ε |bB 相应的正规式是什么？G[S]能否改写成为等价的正规文法？ 问题 5： 已知文法 G： E→E+T|E-T|T T→T*F|T/F|F F→(E)|i 试给出下述表达式的推导 (1) (2) i*i+i (3) i+i*i77(4) i+(i+i) 问题 8： 构造产生如下语言的上下文无关文法： （1） {a b c | n，m ? 0}n 2n m（2） {a b cn m 2m| n，m ? 0}（3） { a b | m ? n }m n（4）{ ambncpdq. m+n = p+q }问题 11： 令Σ ={a，b，c}，又令 x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz， （xy）3 问题 12： 已知文法 G[Z]：Z∷=U0OV1 、 U∷=Z1O1 、 V∷=Z0O0 ,请写出全部由此文 法描述的只含有四个符号的句子。 问题 13： 已知文法 G[S]： S∷=AB A∷=aAε 问题 14： 已知文法 E∷=TOE+TOE-T 、 T∷=FOT*FOT/F 、 F∷=(E)Oi，写出该文法的开 始符号、终结符号集合 VT、非终结符号集合 VN。 问题 16： 写一文法，使其语言是奇正整数集合。 第 5 题 构造一个 DFA，它接收 Σ ={0,1}上所有满足如下条件的字符串：每个 1 都有 0 直接跟在 右边。并给出该语言的正规式。 第８题 给出下述文法所对应的正规式： S→0A|1B78B∷=bBcbc , 写出该文法描述的语言。A→1S|1 B→0S|0 附加题 问题 1： 为下边所描述的串写正规式，字母表是 {a,b}. a) 以 ab 结尾的所有串 b) 包含偶数个 b 但不含 a 的所有串 c) 包含偶数个 b 且含任意数目 a 的所有串 d) 只包含一个 a 的所有串 e) 包含 ab 子串的所有串 f) 不包含 ab 子串的所有串 问题 2： 请描述下面正规式定义的串. 字母表 {0，1}. a) 0*(10+)*0* b) (0|1)*(00|11) (0|1)* c) 1(0|1)*0 问题 6： 考虑正规表达式 r = a*b(a | b) ，构造可以生成语言 L(r) 的一个正规文法。 问题 8： 考虑如下文法 G[S]： S → 0S.1S.1A A→ 0B.1B B → ε a) 试构造语言为 L(G) 的一个正规表达式。 第 7 题 对于一个文法若消除了左递归，提取了左公共因子后是否一定为 LL(1)文法?试对下面 文法进行改写，并对改写后的文法进行判断。(１) A→baB|ε B→Abb|a79(2) A→aABe|a B→Bb|d(3) S→Aa|b A→SB B→ab 问题 1： 已知文法 G[A]如下，试用类 C 或类 PASCAL 语言写出其递归下降子程序.(主程序不需写) G[A]: A→[B B→X]{A} X→(a|b){a|b} 问题 2： 设有文法 G[A]的产生式集为: A→BaC|CbB B→Ac|c C→Bb|b 试消除 G[A]的左递归。 问题 3： 试验证如下文法 G[E] 是 LL(1)文法: E → [F] E′ E’ → E.ε F → aF’ F’ → aF’ .ε 其中 E,F,E’,F’为非终结符 问题 4： 文法 G[E] 是 LL(1)文法: E → [F] E′ E’ → E.ε F → aF’ F’ → aF’ .ε80其中 E,F,E’,F’为非终结符。 对文法 G[E]构造递归下降分析程序。 问题 6： 试消除下面文法 G[A] 中的左递归和左公因子，并判断改写后的文法是否为 LL(1)文法? G[A]： A→aABe . a B→Bb . d 第 2 题 已知文法 G[S]为： S→a|∧|(T) T→T,S|S (1) 给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。 (2) 将(1)和题 1 中的(4)进行比较给出算符优先归约和规范归约的区别。 第３题： 有文法 G[S]： S..V V..T|ViT T..F|T+F F..)V*|( (1) 给出(+(i(的规范推导。 (2) 指出句型 F+Fi(的短语，句柄，素短语。 (3) G[S]是否为 OPG？若是，给出(1)中句子的分析过程。 问题 1： 对于文法 S .. ( L ) | a L .. L, S | S (1)给出句子(a, ((a, a), (a, a)))的一个最右推导，并指出右句型的句柄； (2)按照(1)的最右推导，说明移进－归约分析器的工作步骤。 问题 2： 试为下列各文法建立算符优先关系表。 E→E and T|T T→T or F|F81F→not F|N N→(E)|true|false 第 1 题 给出下面表达式的逆波兰表示(后缀式)： (1)a*(-b+c) (2) if(x+y)*z=0 then s∶=(a+b)*c else s∶=a*b*c 第 2 题 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式、四元式序列、树形、 逆波兰，当前序号为 100。 问题 1： 请将下列语句 while (A&B do if (C&D) then X:=Y+Z 翻译成四元式 问题 8： 翻译算术表达式 a*- (b+c)为 a)一棵语法树 b)后缀式 c)三地址代码 问题 9： 翻译算术表达式 C(a+b)*(c+d) +(a+b+c) 为 a)四元式 b)三元式 c)间接三元式 问题 10： 将下列赋值语句译成三地址代码。 A[i,j] :=B[i,j] + C[A[k,l]] + D[i+j] 第 5 题： 过程参数的传递方式有几种?简述“传地址”和“传值”的实现原理。 第 6 题： 下面的程序执行时输出的 a 分别是什么?若82(1) 参数的传递办法为“传值” 。 (2) 参数的传递办法为“传地址” 。 program main (input,output); procedure p(x,y,z); begin y∶=y+1; z∶=z+x; begin a∶=2; b∶=3; p(a+b,a,a); print a end. 第１题 何谓代码优化？进行优化所需要的基础是什么？ 第２题 编译过程中可进行的优化如何分类？ 第３题 最常用的代码优化技术有哪些？ 问题 1： 决定目标代码的因素有哪些？ 问题 2： 为什么在代码生成时要考虑充分利用寄存器？ 问题 3： 寄存器分配的原则是什么？ 第 1 题 构造一个编译程序有哪些途径？ 问题 1: 如何用 T 型图 表示一个编译程序的实现？83问题 2： 如何用自展方式在 PC 机上实现 C 语言的编译程序？请用 T 型图 表示。 问题 3： 什么叫做软件移植？ 问题 4： 什么叫做交叉编译？ 问题 5： 编译程序的实现应考虑的问题有那些？I 卷答案 1 答案： （1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语 言，则此翻译程序称为编译程序。 （2） 源程序：源语言编写的程序称为源程序。 （3） 目标程序：目标语言书写的程序称为目标程序。 （4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与 目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段， 即目标代码生成，以及相关出错处理和符号表操作。 （6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 3 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程 序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编 写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是， 源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词， 则依据这个单词把控制转移到实现这条语句功能的程序部分， 该部分负责完成这条语句的功84能的实现，完成后返回到解释程序的总控部分再读人下一条语句继续进行解释、执行，如此 反复；另一种方式是，一边翻译一边执行，即每读出源程序的一条语句，解释程序就将其翻 译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复。无论 是哪种方式， 其加工结果都是源程序的执行结果。 目前很多解释程序采取上述两种方式的综 合实现方案， 即先把源程序翻译成较容易解释执行的某种中间代码程序， 然后集中解释执行 中间代码程序，最后得到运行结果。 广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是 边翻译（解释）边执行，不产生目标代码，输出源程序的运行结果。而编译程序只负责把源 程序翻译成目标程序， 输出与源程序等价的目标程序， 而目标程序的执行任务由操作系统来 完成，即只翻译不执行。 4 答案： （1） 语法分析 （2） 语义分析 （3） 语法分析 （4） 词法分析 5 答案： （1）自编译：用某一高级语言书写其本身的编译程序。 （2）交叉编译：A 机器上的编译程序能产生 B 机器上的目标代码。 （3）自展：首先确定一个非常简单的核心语言 L0，用机器语言或汇编语言书写出它的编译 程序 T0，再把语言 L0 扩充到 L1，此时 L0 . L1 ,并用 L0 编写 L1 的编译程序 T1，再 把语言 L1 扩充为 L2，有 L1 L2 ,并用 L1 编写 L2 的编译程序 T2，??，如此逐步扩展 下去，好似滚雪球一样，直到我们所要求的编译程序。 （4）移植：将 A 机器上的某高级语言的编译程序搬到 B 机器上运行。 1 答案： L(G[S])={abc} 3 答案： G[S]: S-&S+D|S-D|D D-&0|1|2|3|4|5|6|7|8|9 4 答案：85Z=&aZb=&aaZbb=&aaa..Z...bbb=& aaa..ab...bbb L(G[Z])={a b |n&=1} 5 答案： (1)允许 0 开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许 0 开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 6 答案： (1) &表达式&=&&表达式&＋&项&=&&表达式&＋&因子&=&&表达式&＋ （&表达式&） =&&表达式& ＋ （&表达式&＋&项&） =&&表达式&＋ （&表达式&＋&因子&） =&&表达式&＋ （&表达式&＋i） =&& 表达式&＋（&项&＋i） =&&表达式&＋（&因子&＋i） =&&表达式&＋（i＋i） =&&项&＋（i ＋i） =&&因子&＋（i＋i） =&i＋（i＋i） (2) &表达式&=&&表达式&＋&项& =&&表达式&＋&项&*&因子& =&&表达式&＋&项&*i =&&表达 式&＋&因子&*i =&&表达式&＋i*i =&&项&＋i*i =&&因子&＋i*i =&i＋i*i 7 答案： 可为句子 a+a*a 构造两个不同的最右推导: 最右推导 1 〈表达式〉 〈表达式〉 〈运算符〉 〈表达式〉 〈表达式〉 〈运算符〉a 〈表达式〉* a 〈表达式〉 〈运算符〉 〈表达式〉* a 〈表达式〉 〈运算符〉a * a 〈表达式〉+ a * a86n na + a * a 最右推导 2 〈表达式〉 〈表达式〉 〈运算符〉 〈表达式〉 〈表达式〉 〈运算符〉 〈表达式〉 〈运算符〉 〈表达式〉 〈表达式〉 〈运算符〉 〈表达式〉 〈运算符〉 a 〈表达式〉 〈运算符〉 〈表达式〉 * a 〈表达式〉 〈运算符〉a * a 〈表达式〉+ a * a a + a * a 8 答案： 对于串 abc (1)S=&Ac=&abc (2)S=&aB=&abc 即存在两不同的最右推导。所以，该文法是二义的。 或者： 对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。 9 答： (1)此文法生成串 aa+a*的最右推导如下 S=&SS*=&SS*=&Sa*=&SS+a*=&Sa+a*=&aa+a* (2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 S A c a b S a B b c S S S * S S + a a a 10 答案： （１） 嵌套的括号 （２） 是二义的，因为对于（） （）可以构造两棵不同的语法树。8711 答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=&E+T=&E+T*F，所以 E+T*F 句型 此句型相对于 E 的短语有:E+T*F；相对于 T 的短语有 T*F 直接短语为：T*F 句柄为：T*F 14 答案： （１） S→AA A→aAb|ε （２） S→1S0|A A→0A1|ε 16 答案： (1) S→aS|ε (2) S→aA A→aA|B B→bB|b (3) A→aA|B B→bB|C C→cC|ε 18 答案： （１）字母表：是一个非空有穷集合。 （２）串：符号的有穷序列。 字：字母表中的元素。 句子：如果 Z x , x ∈V *T 则称 x 是文法 G 的一个句子。 + （３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所 有该语言的程序的全体。 语言可以看成在一个基本符号集上定义的， 按一定规则构成的一切88基本符号串组成的集合。 语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 1 答案： R = (01 | 10) ( 01 | 10 )* 2 答案: G[A]定义的语言由 0、1 符号串组成，串中 0 和 1 的个数相同. 3 答案一： G[E] E→E+T|T T→T* F|F F→(E)|a 答案二： G[E] E→E+E|E* E|(E)|a 4 答案： 正规式是 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|ε 5：答案： (1)E=&T=&F=&i (2)E=&E+T=&T+T=&T*F+T=&F*F+T=&i*F+T=&i*i+T=&i*i+F=&i*i+i (3)E=&E+T=&T+T=&F+T=&i+T=&i+T*F=&i+F*F=&i+i*F=&i+i*i (4)E=&E+T=&T+T=&F+T=&i+T=&i+F=&i+(E)=&i+(E+T)=&i+(T+T)=&i+(F+T) =&i+(i+T)=&i+(i+F)=&i+(i+i) 8 答案：（1）根据上下文无关文法的特点，要产生形如 anb2ncm 的串，可以分别产生形如 anb2n 和 形如 cm 的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是 特别指明，通常可以忽略这一点。89对于该语言，存在一个由以下产生式定义的上下文无关文法 G[S]：S → ABA → ε. aAbbB → ε. cB（2）同样，要产生形如 anbmc2m 的串，可以分别产生形如 an 和形如 bmc2m 的串。对于该 语 言，存在一个由以下产生式定义的上下文无关文法 G[S]：S → ABA → ε. aAB → ε. bBcc（3）考虑在先产生同样数目的 a,b，然后再生成多余的 a。以下 G[S]是一种解法：S → aSb . aS . ε（4）以下 G[S]是一种解法：S → aSd . A . DA → bAd . BD → aDc . B90B → bBc . ε注：a 不多于 d 时，b 不少于 c；反之，a 不少于 d 时，b 不多于 c。前一种情形通过 对应 A，后一种情形对应 D。 11 答案： xy=abcb |xy|=4xyz=abcbaab |xyz|=7(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 12 答案： Z=&U0=&Z10=&U010=&1010Z=&U0=&Z10=&V110=&0110Z=&V1=&Z00=&U000=&1000Z=&V1=&Z00=&V100=&0100 13 答案： A∷=aAε 描述的语言: {a |n&=0}nB∷=bBcbc 描述的语言:{,b c |n&=1}n nL(G[S])={a b c |n&=0,m&=1} 14 答案： 开始符号：En m mVT={+, - , * , / ,（ , ）, i}91VN={E , F , T} 16 答案： A::=1|3|5|7|9|NA N::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9| N::=0|1|2|3|4|5|6|7|8|9 5 答案： 按题意相应的正规表达式是(0*10)*0*，或 0*(0 | 10)*0* 8 答案： 解方程组 S 的解： S=0A|1B A=1S|1 B=0S|0 将 A、B 产生式的右部代入 S 中 S=01S|01|10S|10=（01|10）S|（01|10） 所以：S= (01|10)*(01|10) 1 答案： 注意 正规式不唯一 a) (a|b)*ab b) (bb)* c) (a*ba*ba*)* d) b*ab* e) (a|b)*ab(a|b)* f) b*a* 2 答案： a) 每个 1 至少有一个 0 跟在后边的串 b) 所有含两个相继的 0 或两个相继的 1 的串 c) 必须以 1 开头和 0 结尾的串 6 答案： S → a*b(a | b)92变换为 S → aA, S → b(a | b) , A → aA , A → b(a | b) 变换为 S → aA, S → bB, B → (a | b) , A → aA , A → bC, C → (a | b) 变换为 S → aA, S → bB, B → a, B → b , A → aA , A → bC, C → a, C → b 所以，一个可能的正规文法为 G[S]： S → aA, S → bB, B → a, B → b , A → aA , A → bC, C → a, C → b 或表示为： S → aA | bB, B → a | b , A → aA | bC, C → a | b 8 答案： a) 由 A→ 0B ， B → ε 得 A→ 0 ;由 A→ 1B ， B → ε得 A→ 1 ;由 A→ 0，A→ 1 得 A→ 0 .1 ;由 S→ 1A，A→ 0 .1 得 S→ 1( 0 .1 ) ;由 S→ 1A，A→ 0 .1 得 S→ 1( 0 .1 ) ;由 S→ 0S，S→ 1( 0 .1 ) 得 S→ 0*1( 0 .1 ) ;由 S→ 1S，S→ 1( 0 .1 ) 得 S→ 1*1( 0 .1 ) ;由 S→ 0*1( 0 .1 )，S→ 1*1( 0 .1 ) 得 S→ 0*1( 0 .1 ) . 1*1( 0 .1 ) ;所以，一个可能的正规表达式为： 0*1( 0 .1 ) . 1*1( 0 .1 ) 7 答案：93(１) 先改写文法为： 0) A→baB 1) A→ε 2) B→baBbb 3) B→bb 4) B→a 再改写文法为：0) A→baB 1) A→ε 2) B→bN 3) B→a 4) N→aBbb 5) N→b FIRST A B N 预测分析表： a A B N →a →aBbb b →baB →bN →b # →ε {b} {b,a} {b,a} FOLLOW {#} {#,b} {#,b }由预测分析表中无多重入口判定文法是 LL(1)的。 （2） 文法： A→aABe|a B→Bb|d 提取左公共因子和消除左递归后文法变为： 0) A→a N941) N→A B e 2) N→ε 3) B→d N1 4) N1→b N1 5) N1→ε 非终结符 FIRST 集 FOLLOW 集 A {a}... {#,d} B {d}... {e}.. N {a,ε } {#,d} N1 {b,ε }