编译原理答案（编译原理及编译程序构造）.doc-资料库

leixue1997-2792379-4744300845395896616.doc.pdf-第1页.png

第1页 / 共23页

leixue1997-2792379-4744300845395896616.doc.pdf-第2页.png

第2页 / 共23页

leixue1997-2792379-4744300845395896616.doc.pdf-第3页.png

第3页 / 共23页

leixue1997-2792379-4744300845395896616.doc.pdf-第4页.png

第4页 / 共23页

leixue1997-2792379-4744300845395896616.doc.pdf-第5页.png

第5页 / 共23页

leixue1997-2792379-4744300845395896616.doc.pdf-第6页.png

第6页 / 共23页

leixue1997-2792379-4744300845395896616.doc.pdf-第7页.png

第7页 / 共23页

leixue1997-2792379-4744300845395896616.doc.pdf-第8页.png

第8页 / 共23页

文档 3 第一章引言 1．解释下列名词 6/9/2022 Page 1 of 23 源程序，目标程序，翻译程序，汇编程序，编译程序，遍答：源程序：由汇编语言或高级程序语言编写的程序。目标程序：由目标语言编写的程序。翻译程序：把源程序转化为目标程序的程序。汇编程序：把由汇编语言编写的源程序转换成目标程序(由机器语言编写)的翻译程序。编译程序：把由高级程序语言编写的源程序转换为一台具体计算机的机器语言或汇编语言程序的翻译程序。遍：对源程序或源程序的中间形式从头到尾扫描一遍，并做有关的加工处理，生成新的源程序的中间形式或目标程序。 2．典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？答：典型的编译程序可划分 7 个主要的逻辑部分（模块）。 —词法分析将字符串形式的源程序分解为具有独立语法语意的单词符号（Token）; —语法分析从词法分析程序取得源程序，并将一个或多个单词组合为语言的各种语法类。 —语义分析确定源程序的意义（语义）。 —代码生成将源程序的中间形式转化为汇编语言或机器语言。 —代码优化获得更高效的目标程序。 —出错出理对源程序的错误精确定位并能够跳过错误继续编译。 —符号表管理保存每个标志符及其属性，并保存过程名及其参数。注意：区分编译过程的 5 个阶段和编译程序的 7 个逻辑组成部分。第二章文法和语言的概念和表示设关于句子的一组规则为：〈句子〉：：=〈主语〉〈谓语〉〈主语〉：：=〈名词短语〉〈名词短语〉：：=〈名词〉〈名词短语〉：：= 〈形容词〉〈名词短语〉〈形容词〉：：=big 〈形容词〉：：=brown 〈形容词〉：：=roasted 〈名词〉：：=John 〈名词〉：：=peanut 〈谓语〉：：=〈动词〉〈直接宾语〉〈动词〉：：=ate 〈直接宾语〉：：=〈冠词〉〈名词短语〉〈冠词〉：：=the 给出下述句子的推导，并画出语法树。解：（A）〈句子〉=>〈主语〉〈谓语〉 =>〈主语〉〈动词〉〈直接宾语〉 =>〈主语〉〈动词〉〈冠词〉〈名词短语〉 =>〈主语〉〈动词〉〈冠词〉〈形容词〉〈名词短语〉 =>〈主语〉〈动词〉〈冠词〉〈形容词〉〈名词〉 =>〈主语〉〈动词〉〈冠词〉〈形容词〉peanut =>〈主语〉〈动词〉〈冠词〉big peanut =>〈主语〉〈动词〉the big peanut =>〈主语〉ate the big peanut =>〈名词短语〉ate the big peanut Created by ITLearner---2004 6/9/2022 - 1 -

文档 3 6/9/2022 Page 2 of 23 =>〈名词〉ate the big peanut => John ate the big peanut (语法树略) (B) 〈句子〉=>〈主语〉〈谓语〉 =>〈名词短语〉〈谓语〉 =>〈名词〉〈谓语〉 => John〈谓语〉 => John〈动词〉〈直接宾语〉 => John ate〈直接宾语〉 => John ate〈冠词〉〈名词短语〉 => John ate the〈名词短语〉 => John ate the〈形容词〉〈名词短语〉 => John ate the big〈名词短语〉 => John ate the big〈形容词〉〈名词短语〉 => John ate the big brown〈名词短语〉 => John ate the big brown〈名词〉 => John ate the big brown peanut （语法树略） (C) 〈句子〉=>〈主语〉〈谓语〉 =>〈名词短语〉〈谓语〉 =>〈名词〉〈谓语〉 => John〈谓语〉 => John〈动词〉〈直接宾语〉 => John ate〈直接宾语〉 => John ate〈冠词〉〈名词短语〉 => John ate the〈名词短语〉 => John ate the〈形容词〉〈名词短语〉 => John ate the big〈名词短语〉 => John ate the big〈形容词〉〈名词短语〉 => John ate the big roasted〈名词短语〉 => John ate the big roasted〈名词〉 => John ate the big roasted peanut （语法树略） 2.利用规则 2-1，除最左推导外，给出句子 the big elephant ate the peanut 的另外两种推导（其中一种为最右推导）。答：(A) 最右推导〈句子〉=>〈主语〉〈谓语〉 =>〈主语〉〈动词〉〈直接宾语〉 =>〈主语〉〈动词〉〈冠词〉〈名词〉 =>〈主语〉〈动词〉〈冠词〉peanut =>〈主语〉〈动词〉the peanut =>〈主语〉ate the peanut =>〈冠词〉〈形容词〉〈名词〉ate the peanut =>〈冠词〉〈形容词〉 elephant ate the peanut =>〈冠词〉big elephant ate the peanut => the big elephant ate the peanut (B) 〈句子〉=>〈主语〉〈谓语〉 =>〈主语〉〈动词〉〈直接宾语〉 =>〈冠词〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉 =>〈冠词〉〈形容词〉〈名词〉〈动词〉〈冠词〉〈名词〉 Created by ITLearner---2004 6/9/2022 - 2 -

文档 3 6/9/2022 Page 3 of 23 => the〈形容词〉〈名词〉〈动词〉〈冠词〉〈名词〉 => the big〈名词〉〈动词〉〈冠词〉〈名词〉 => the big elephant〈动词〉〈冠词〉〈名词〉 => the big elephant ate〈冠词〉〈名词〉 =>the big elephant ate the〈名词〉 =>the big elephant ate the peanut P19 1.令 A={$},又令 Z=$,写出如下的符号串以及它们的长度： Z，ZZ，Z2 ，Z3，Z0，A*=？解：Z=$ ZZ=$$ Z2=ZZ=$$ Z3=$$$ Z0=ε |Z|=1 |ZZ|=2 | Z2|=2 | Z3|=3 | Z0|=1 A*={ε,$,$$,$$$,……} |A*|=∞ 2.令 A={0,1,2},又令 x=01，y=2，z=001，写出如下符号串及它们的长度： xy, xyz, x4, (x3)(y2), (xy)2 解：xy=012, |xy|=3 xyz =012001, | xyz |=6 x4=xxxx=01010101, | x4 |=8 (x3)(y2)=01010122, | (x3)(y2)|=8 (xy)2=012012, |(xy)2 |=6 令 A={0,1,2},写出集合 A+和集合 A*的 7 个最短的符号串。解：A+的 7 个最短的符号串为： 0，1，2，00，01，02，10 （答案不唯一） A*的 7 个最短的符号串为： ε，0，1，2，00，01，02，（答案不唯一） 4. 试证明：A+=AA*=A*A 证：∵ A*=A0∪A+，A+=A1∪A2∪…∪An∪… 得：A*=A0∪A1∪A2∪…∪An∪… ∴ AA*=A（A0∪A1∪A2∪…∪An∪…） = AA0∪AA1∪AA2∪…∪A An∪… =A∪A2∪A3∪An +1∪… = A+ 同理可得：A*A =(A0∪A1∪A2∪…∪An∪…)A =A0 A∪A1A∪A2A∪…∪ANA∪… = A∪A2∪A3∪AN+1∪… = A+ P26 因此： A+ =AA*=A*A 1.设 G[〈标志符〉]的规则是：〈标志符〉::=a|b|c|〈标志符〉a|〈标志符〉c|〈标志符〉0|〈标志符〉1 试写出 VT 和 VN，并对下列符号串 a,ab0,a0c01,0a,11,aaa 给出可能的一些推导。解：VT ={a,b,c,0,1}， VN ={〈标志符〉} 不能推导出 ab0,11,0a 〈标志符〉=>a 〈标志符〉=>〈标志符〉1 =>〈标志符〉01 =>〈标志符〉c01 Created by ITLearner---2004 6/9/2022 - 3 -

文档 3 6/9/2022 Page 4 of 23 =>〈标志符〉0c01 => a0c01 (4)〈标志符〉=>〈标志符〉a =>〈标志符〉aa =>aaa 2. 写一文法，使其语言是偶整数的集合。解：G[〈偶整数〉]：〈偶整数〉::=〈符号〉〈偶数字〉|〈符号〉〈数字串〉〈偶数字〉，（作用是一位和多位）〈符号〉::= + | — |ε 〈数字串〉::= 〈数字串〉〈数字〉|〈数字〉〈数字〉::= 〈偶数字〉| 1 | 3 | 5 | 7 | 9 〈偶数字〉::=0 | 2 | 4 | 6 | 8 3. 写一文法，使其语言是偶整数的集合，但不允许有以 0 开头的偶整数。解：G[〈偶整数〉]：〈偶整数〉::= 〈符号〉〈单偶数〉|〈符号〉〈首数字〉〈数字串〉〈尾偶数〉〈符号〉::= + | — |ε 〈单偶数〉::=2 | 4 | 6 | 8 〈尾偶数〉::= 0 |〈单偶数〉〈首数字〉::= 1 | 3 | 5 | 7 | 9 |〈单偶数〉〈数字串〉::= 〈数字串〉〈数字〉|〈数字〉|ε 〈数字〉::= 0 |〈首数字〉 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∈Vt* ∴由语言定义，cc, bcc, bbcc, bbbcc∈L[G] 5. 试对如下语言构造相应文法： { a(bn)a | n=0,1,2,3,……},其中左右圆括号为终结符。 { （an）（bn） | n=1,2,3,……} 解：（1）文法[G〈S〉]： S::= a(B)a B::= bB |b|ε ( 2 ) 文法[G〈S〉]： S ::= (A)(B) A::= aA|a B::= bB|b 6. 文法 G3[〈表达式〉]：〈表达式〉::=〈项〉|〈表达式〉+〈项〉|〈表达式〉—〈项〉〈项〉::=〈因子〉|〈项〉*〈因子〉|〈项〉/〈因子〉〈因子〉::=（〈表达式〉）| i 试给出下列符号串的推导： i*i, i*i+i, 解：（1）〈表达式〉=>〈项〉 i, (i), i*(i+i) =>〈因子〉 Created by ITLearner---2004 6/9/2022 - 4 -

文档 3 =>ND25 =>N125 =>0125 N=>ND =>NDD =>DDD =>7DD =>78D =>783 P33 1.给定文法 G[E]为： 6/9/2022 Page 6 of 23 （最右推导（规范推导））（最左推导） E::=RP|P P::=（E）| i R::=RP+ | RP* | P + | P* 证明（1）i+i* (i+i)是文法 G 的句子。（2）画出该句子的语法树。证：（1）E=>RP =>RP* P =>RP*（E） =>RP*（RP） =>RP*（P+P） =>RP*（P+i） => RP*（i+i） =>P+P*（i+i） => P+i*（i+i） => i+i*（i+i）∈Vt* ∴ i+i* (i+i)是文法 G 的句子（对应的语法树略） 2.画出下列推导的语法树。 <数> （1） <数字串> <数字串> <数字> (2) <数> <数字串> <数字串> <数字> <数字串> <数字> <数字串> <数字> <数字> 1 2 3 由上图可知两种推导的语法树是相同的。 4. 由下述语法树构造推导：（语法树书上 P34 上，未画）。解：（1）〈表达式〉=>〈项〉 =>〈项〉*〈因子〉 =>〈因子〉*〈因子〉 => i*〈因子〉 Created by ITLearner---2004 <数字> 1 2 3 6/9/2022 - 6 -

文档 3 => i* i ( 2 ) 〈表达式〉=>〈项〉 =>〈项〉*〈因子〉 =>〈因子〉*〈因子〉 6/9/2022 Page 7 of 23 (〈表达式〉) (〈项〉+〈项〉) => i*〈因子〉 => i * => i * => i * => i * (〈因子〉+〈项〉) => i * => i * => i * ( i + i ) (〈表达式〉+〈项〉) ( i +〈项〉) ( i +〈因子〉) 5．已知文法 G[E]： E::=ET+ | T T::=TF* |F F::=FP↑ |P P::=（E）| i 有句型 TF*PP↑+，问此句型的短语，简单短语，和句柄是什么？解：此句型的短语有：TF*PP↑+，TF*，PP↑，P 简单短语有：TF*，P 句柄是：TF* 注意：求短语，简单短语和句柄尽量用语法树。 6. 分别对 i+i*i 和 i+i+i 中的每一个句子构造两棵语法树，从而证明下列文法 G[〈表达式〉] 是二义的。〈表达式〉::= i | (〈表达式〉) |〈表达式〉〈运算符〉〈表达式〉〈运算符〉::= + | — | * | / 解：以 i+i*i 为例: 8．证明下面的文法 G 是二义的： S::= iSeS | iS | i 证：由文法可知 iiiei 是该文法的句子，又由文法可知 iiiei 有两棵不同的语法树。所以该文法是二义性文法。 7．文法 G3[〈表达式〉为：〈表达式〉::=〈项〉|〈表达式〉+〈项〉|〈表达式〉—〈项〉〈项〉::=〈因子〉|〈项〉*〈因子〉|〈项〉/〈因子〉〈因子〉::=（〈表达式〉）| i 证明此文法的句子 i+i*i 和 i+i+i 是无二义性的。在句子 i+i*i 中，哪种运算符是优先的？在句子 i+i+i 中，又是哪种运算符？证：（容易证明文法规则右边出现有选折项时，各项首符号集不相交，且该文法不是左递归文法）。在句子 i+i*i 中，运算符*是优先的在句子 i+i+i 中，第一个+运算符是优先的 9．有文法 G[N]： N::=SE|E E::=0|2|4|6|8|10 S::=SD|D D::=0|1|2|……|9 举例说明文法 G[N] 是二义的。此文法描述的语言是什么？试写出另一文法 G’，使 L（G’）=L（G），且 G’是无二义性的。解：由文法可知 10 是该文法的句子，又由文法可知 10 有两棵不同的语法树。 Created by ITLearner---2004 6/9/2022 - 7 -

文档 3 6/9/2022 Page 8 of 23 此文法描述的语言 L（G）={无符号偶数} 所求文法 G’[〈无符号偶数〉]：〈无符号偶数〉::=〈偶数字〉|〈数字串〉〈偶数字〉〈数字串〉::= 〈数字串〉〈数字〉|〈数字〉〈数字〉::= 〈偶数字〉| 1 | 3 | 5 | 7 | 9 〈偶数字〉::=0 | 2 | 4 | 6 | 8 （****上述提供文法中的第二条规则右部的 10 选折项去掉似乎就符合要求了行*****） P67 1．解：其状态图为：由状态图知：第三章 start e f ,eeff 不是合法的句子 eefe 是该文法的句子。 2．解： ⑴正则文法为 G[Z]： Z∷＝A1∣0 A∷＝A0∣0 e S Z e e A f B ⑵该文法的 V=｛Z,A,1,0｝ Vn=｛Z,A｝ Vt=｛1,0｝ ⑶该文法所确定的语言为：L﹙G[Z]﹚＝｛0n1 或 0∣n≥1｝ 5．证明： ⑴A∣A＝｛x∣x∈LA 或 x∈LA｝＝｛x∣x∈LA｝＝A ⑵（A*）*＝（A*）0∪（A*）1∪（A*）2∪…∪（A*）n ＝ε∪(A0∪A1∪A2∪…∪An) ∪(A1…) ＝ε∪A0∪A1∪A2∪…∪An ＝A ⑶ε︱AA*所表示的语言是{ε}∪LA·LA*＝LA0∪LA（LA0∪LA1∪LA2∪…）＝LA0∪LA1∪LA2∪…＝LA* 故ε︱AA*＝A* ⑷(LALB)*LA=({ε}∪LALB∪LALBLALB∪LALBLALBLALB∪…) LA =LA∪LALBLA∪LALBLALBLA∪LALBLALBLALB∪LA… = LA∪({ε}∪LBLA∪LBLALBLA∪…) = LA(LBLA) ∴(AB)*=A(AB)* ⑸三个表达式所描述的语言都是 LALA 中任意组合 ∴（A|B）*=(A*B*)=(A*|B*)* 6．解： ⑴R1=0︱1 对应的自动机为 (R1)*=(0|1)* 对应的自动机为 M2’ 0 start P1 P2 1 ε P0 ε P1 start 1 φ ε 0 1 P2 ε P3 将 M2’确定化输入状态 P0 P1 P2 P3 ε 0 {P1,P3} φ φ {P1,P3} φ φ φ ｛P2｝｛P2｝ φ φ Created by ITLearner---2004 6/9/2022 - 8 -

资料库

编译原理答案（编译原理及编译程序构造）.doc

相关推荐

课程资源

热门标签

最新资料