当前位置：文档之家 › 编译原理第二章 习题与答案

编译原理第二章 习题与答案

  • 格式：doc
  • 大小：47.50 KB
  • 文档页数：7

第2章 习题 2-1 设有字母表A1 ={a,b,c,…,z}，A2 ={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个？ (2) 集合A1A2含有多少个元素？ (3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。

2-2 试分别构造产生下列语言的文法： （1）{anbn|n≥0}； （2）{anbmcp|n,m,p≥0}； （3）{an#bn|n≥0}∪{cn#dn|n≥0}； （4）{w#wr# | w∈{0,1}*,wr是w的逆序排列 }； （5）任何不是以0打头的所有奇整数所组成的集合； （6）所有由偶数个0和偶数个1所组成的符号串的集合。

2-3 试描述由下列文法所产生的语言的特点： （1）S→10S0 S→aA A→bA A→a （2）S→SS S→1A0 A→1A0 A→ε （3）S→1A S→B0 A→1A A→C B→B0 B→C C→1C0 C→ε （4）S→aSS S→a

2-4 试证明文法 S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab 为二义性文法。

2-5 对于下列的文法 S→AB|c A→bA|a B→aSb|c 试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。 2-6 化简下列各个文法 (1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c (2) S→aAB|E A→dDA|e B→bE|f C→cAB|dSD|a D→eA E→fA|g (3) S→ac|bA A→cBC B→SA C→bC|d

2-7 消除下列文法中的ε-产生式 (1) S→aAS|b A→cS|ε (2) S→aAA A→bAc|dAe|ε

2-8 消除下列文法中的无用产生式和单产生式 (1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B (2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ] (3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|i

第2章 习题答案 2-1 答： (1) 26*26=676 (2) 26*10=260 (3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz, a00,a01,...,zzz},共有26+26*36+26*36*36=34658个

2-2 解： (1) 对应文法为G(S)=({S},{a,b},{ S→ε| aSb },S) (2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X, X→bX|Y, Y→cY|ε },S) (3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X, S→Y, X→aXb|#, Y→cYd|# },S) (4) G(S)=({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S) (5) G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J|IBJ, B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S) (6)对应文法为 S→0A|1B|ε，A→0S|1C ， B→0C|1S， C→1A|0B

2-3 解： (1) 本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。 (2) L(G)={1n0n |n≥0}+，该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同的连续的0。 (3) 本文法构成的语言集为：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特点是具有1p1n0n 或1n0n0q形式，进一步，可知其具有形式{1n0m|n,m≥0,且n+m>0}。 (4)由L(G)={a2n-1|n≥1}可知，该语言特点是：产生的句子是奇数个a。

2-4 证明： 因为存在句子：abc，它对应两个最右推导： S AB Abc abc S DC Dc abc 所以，本文法具有二义性。

2-5 解： 句子bbaacb的最右推导为： S AB AaSb Aacb bAacb bbAacb bbaacb 上面推导中，下划线部分为当前句型的句柄。 与句子bbaacb相应的语法树为：

全部的短语为： 第一个a（a(1)）是句子bbaacb相对于非终结符A (A(1)) (产生式A→a）的短语（直接短语）； b(1)a(1)是句子bbaacb相对于非终结符A(2)的短语； b(2)b(1)a(1)是句子bbaacb相对于非终结符A(3)的短语； c是句子bbaacb相对于非终结符S(1)（产生式S→c）的短语（直接短语）； a(2)cb(3)是句子bbaacb相对于非终结符B的短语； b(2)b(1)a(1)a(2)cb(3)是句子bbaacb相对于非终结符S(2)的短语； 注：符号的上标是为了描述方便加上去的。

2-6 解： (1) 因为由非终结符号B推导不出终结符号串，因此B是无用符号，含有B的产生式B→Bab,B→cSB, S→aABS和A→bAB都是无用产生式，应予以删除。 因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为 S→bCACd A→cSA|cCC C→cS|c (2) 因为由文法的开始符号推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式C→cAB|dSD|a都是无用产生式，也应予以删除。 因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为 S→aAB|E A→dDA|e B→f D→eA E→fA|g (3) 因为由非终结符号A,B推导不出终结符号串，因此A,B是无用符号，删除含有A,B的产生式S→Ba, A→cBC和B→SA后得到文法G′[S]: S→ac C→bC|d 又因为由文法G′[S]的开始符号S推导不出含有非终结符号C的句型，因此C是无用符号，含有C的产生式C→bC|d都是无用产生式，也应予以删除。 因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法G〞[S]为 S→ac

2-7 解： (1) 对于G，我们可得到W={A}；再按如下步骤得到产生式集P′： 对于产生式S→aAS，将产生式S→aAS及S→aS放入P′； 对于产生式S→b，直接将产生式S→b放入P′； 对于产生式A→cS，将产生式A→cS放入P′。 于是得到消除ε-产生式后的文法为： S→aAS|aS|b A→cS (2) 对于G，我们可得到W={A}；再按如下步骤得到产生式集P′： 对于产生式S→aAA，将产生式S→aAA及S→Aa和S→a放入P′； 对于产生式A→bAc，将产生式A→bAc及A→bc放入P′； 对于产生式A→dAe，将产生式A→dAe及A→de放入P′。 于是得到消除ε-产生式后的文法为： S→aAA|aA|a A→bAc|bc|dAe|de

2-8 解： (1) 首先求出如下集合 W(S)={S}, W(A)={A}, W(B)={B,C}, W(C)={C}, W(D)={D,B,C} 然后按如下步骤得到产生式集P′： 将P中的所有非单产生式添加到P′中： S→aB|BC A→aA|c|aDb B→DB C→b 因为C∈W(B)，故将C的所有非单产生式的右部作为B-产生式的右部添加到P′中： B→b 因为B∈W(D)，故将B的所有非单产生式的右部作为D-产生式的右部添加到P′中： D→DB 因为C∈W(D)，故将C的所有非单产生式的右部作为D-产生式的右部添加到P′中： D→b 由此得到消除单产生式后的文法如下： S→aB|BC A→aA|c|aDb B→DB|b C→b D→b|DB 因为由文法的开始符号推导不出含有非终结符号A的句型，因此A是无用符号，含有A的产生式A→aA|c|aDb都是无用产生式，应予以删除。 于是得到消除无用产生式和单产生式后的文法如下： S→aB|BC B→DB|b C→b D→b|DB

(2) 首先求出如下集合 W(S)={S,A,B}, W(A)={A,B}, W(B)={B} 然后按如下步骤得到产生式集P′： 将P中的所有非单产生式添加到P′中： S→SA|SB A→(S)|( ) B→[S]|[ ] 因为A∈W(S)，故将A的所有非单产生式的右部作为S-产生式的右部添加到P′中： S→(S)|( ) 因为B∈W(S)，故将B的所有非单产生式的右部作为S-产生式的右部添加到P′中： S→[S]|[ ] 因为B∈W(A)，故将B的所有非单产生式的右部作为A-产生式的右部添加到P′中： A→[S]|[ ] 由此得到消除单产生式后的文法如下： S→SA|SB|(S)|( )|[S]|[ ] A→(S)|( )|[S]|[ ] B→[S]|[ ]

(3) 首先求出如下集合 W(E)={E,T,F,P}, W(T)={T,F,P}, W(F)={F,P}, W(P)={P} 然后按如下步骤得到产生式集P′： 将P中的所有非单产生式添加到P′中： E→E+T T→T*F F→P↑F P→(E)|i 因为T,F,P∈W(E)，故将T,F,P的所有非单产生式的右部作为E-产生式的右部添加到P′中： E→T*F E→P↑F E→(E)|i 因为F,P∈W(T)，故将F,P的所有非单产生式的右部作为T-产生式的右部添加到P′

合集下载

编译原理第二版课后习答案教学文稿

编译原理第二版课后习答案教学文稿

编译原理第二版课后习答案《编译原理》课后习题答案第一章第 1 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第 2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

编译原理一些习题答案

编译原理一些习题答案

第2章形式语言基础2.2 设有文法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导。

解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0123 0123的最右推导：N ⇒ ND ⇒ N3 ⇒ ND3 ⇒ N23 ⇒ ND23 ⇒ N123 ⇒ D123 ⇒ 0123268的最左推导：N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 2DDD ⇒ 26D ⇒ 268268的最右推导：N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 2682.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。

解答：首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。

如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。

分别用3个非终结符来产生句子的第1位、中间部分和最后一位。

引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。

N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下面文法生成的语言是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ⇒ bcB ⇒ bBc⇒ bbccB ⇒ bBc⇒ bbBcc ⇒ bbbccc……A ⇒εA ⇒ aA ⇒ aA ⇒ aA ⇒ aaA ⇒ aa……∴S ⇒ AB ⇒ a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ⇒ aS ⇒ aA ⇒ aaS ⇒ aaaS ⇒ aA ⇒ aaS ⇒ aaaA ⇒aaaaS ⇒ aaaaa ……∴S ⇒ a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。

编译原理附标准答案60861

编译原理附标准答案60861

第 2 章 习题2-1 设有字母表 A 1 ={a,b,c, ⋯,z} ，A 2 ={0,1, ⋯,9} ，试回答下 列问题：（1） 字母表 A 1上长度为 2 的符号串有多少个？（2） 集合 A 1A 2 含有多少个元素？（3） 列出集合 A 1（A 1∪A 2） *中的全部长度不大于 3 的符号串。

2- 2 试分别构造产生下列语言的文法：（1）{a n b n |n ≥0}；（2）{a n b m c p |n,m,p ≥0}；（3）{a n #b n |n ≥ 0} ∪{c n #d n |n ≥0}；（ 4）{w#w r # | w ∈{0,1} *,w r 是 w 的逆序排列 } ； （ 5）任何不是以 0 打头的所有奇整数所组成的集合；（6）所有由偶数个 0 和偶数个 1 所组成的符号串的集合。

2- 3 试描述由下列文法所产生的语言的特点： 1） S →10S0 S →aA A →bA A →a 2） S →SS S →1A0 A →1A0 A →ε 3） S →1A S →B0 A →1A A →CB → B0 B →C C →1C0 C →ε（ 4）S →aSS S →a2- 4 试证明文法S →AB|DC A →aA|a B →bBc|bc C → cC|c D →aDb|ab 矚慫润厲钐瘗睞枥庑赖。

为二义性文法。

2- 5 对于下列的文法S→AB|c A → bA|a B →aSb|c试给出句子 bbaacb 的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。

2- 6 化简下列各个文法(1)S →aABS|bCACd A → bAB|cSA|cCC B →bAB|cSB C → cS|c 聞創沟燴鐺險爱氇谴净。

(2)S → aAB|E A →dDA|e B → bE|fC→cAB|dSD|a D → eA E →fA|g(3)S → ac|bA A →cBC B →SA C → bC|d2-7 消除下列文法中的ε- 产生式(1)S →aAS|b A →cS| ε(2)S →aAA A →bAc|dAe| ε2-8 消除下列文法中的无用产生式和单产生式(1)S →aB|BC A →aA|c|aDb B →DB|C C →b D →B(2)S → SA|SB|A A → B|(S)|( ) B → [S]|[ ](3)E →E+T|T T → T*F|F F →P↑F|P P →(E)|i第 2 章习题答2- 1 答：(1)26*26=676(2)26*10=260(3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz,a00,a01,...,zzz}, 共有 26+26*36+26*36*36=34658 个残骛楼諍锩瀨濟溆塹籟。

编译原理习题解答

编译原理习题解答

编译原理习题解答第⼆章：习题2-4 Table表var x,y;procedure p;var a;procedure q;var b;beginb:=10;end;procedure s;var c,d;procedure r;var e,f;begincall q;end;begincall r;end;begincall s;end;begincall p;end根据：Page289，变量table:array[0..txmax] of record 结构体以及block函数得到下表，⽽表中各部第三章⽂法和语⾔5. 写⼀⽂法，使其语⾔是偶正整数的集合要求：(1)允许0打头(2)不允许0打头解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:S→PD|DP->NP|ND→0|2|4|6|8N->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|DP->NR|NR->QR|QD→2|4|6|8N->1|2|3|4|5|6|7|8|9Q->0|1|2|3|4|5|6|7|8|96. 已知⽂法G：<表达式>::=<项>|<表达式>+<项>|<表达式>-<项><项>::=<因⼦>|<项>*<因⼦>|<项>/<因⼦><因⼦>::=(<表达式>)|i。

试给出下述表达式的推导及语法树。

(1)i; (2)(i) (3)i*i;(4)i*i+i; (5)i+(i+i); (6)i+i*i。

解：(1)v=<表达式>=><项>=><因⼦>=>i=w(2)v=<表达式>=><项>=><因⼦>=>(<表达式>)=>(<项>)=>(<因⼦>)=>(i)=w(3)v=<表达式>=><项>=><项>*<因⼦>=><因⼦>*<因⼦>=>i*i=w(4)v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因⼦>+<项>=><因⼦>*<因⼦>+<因⼦>=>i*i+i=w(5)v=<表达式>=><表达式>+<项>=><项>+<项>=><因⼦>+<因⼦>=>i+(<表达式>) => i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因⼦>+<因⼦>)=>i+(i+i)=w (6)v=<表达式>=><表达式>+<项>=><项>+<项>=><因⼦>+<项>=>i+<项>=>i+<项>*<因⼦>=> i+<因⼦>*<因⼦>=> i+i*i=w语法树见下图:7. 为句⼦i+i*i 构造两棵语法树，从⽽证明下述⽂法G[<表达式>]是⼆义的。