2022年编译习题参考答案 .pdf

《2022年编译习题参考答案 .pdf》由会员分享，可在线阅读，更多相关《2022年编译习题参考答案 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、- 1 - 习题第 3 章 文法和语言参考答案1写一文法，使其语言是偶整数集合。解：允许以0 打头G： N+A|-A|A ADA|ED0|1|2|3|4|5|6|7|8|9E0|2|4|6|82写一文法，使其语言是偶整数集合，但不允许由0 打头。解：0 除外G：N+A|-A|A ACB|EBDB|EC1|2|3|4|5|6|7|8|9D0|1|2|3|4|5|6|7|8|9E0|2|4|6|83写一文法G，使得L(G) = ambn| m 0, n 1 解：G1: SaS|T或 G2:S aS|bT 或 G3:S aS|Sb|b TbT|b T bT| 4写一文法G，使得L(G) = ambn

2、cp| m 0, n 0, p 0 解：G1:SABC 或G2:SSc|T 或 G3:A aA|bB|cC|AaA| TTb|R B bB|cC|BbB| RRa| C cC| CcC|5设有文法G1：S AaBS aA ABA bA B bBB 写一文法 G2，使得L(G1) = L(G2)，并且 G2不含空规则。解：G2: S BaB|Ba|aB|a 或 G2:SbB|Sb|a BbB|b 6写一文法，使其语言是十位数不是0 的整数集合。解：G：NSA S +|-|A D|CD|BCD BBD|C C1|2|3|4|5|6|7|8|9D0|1|2|3|4|5|6|7|8|9名师资料总结 -

3、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - - 2 - 7写出以下文法G 所定义的语言L(G) 。G：S SaSS bS d解：L(G)=(xa)nx|n 0 , xb,d =(b|d)a)n(b|d)|n0 =(b|d)(a(b|d)n|n 0 8设有文法G1：S Sab | c | d 将其改写成以下形式的文法G2，每条规则形如：V xW或V y其中 V 和 W 为非终结符，x 和 y 为终结符串。解：G：S cT|dT|c|d T a

4、bT|ab 9设有文法G1：S abcdB B efgBB b将其改写成以下形式的3 型文法 G2，每条规则形如：V pW或V q其中 V 和 W 为非终结符，p 和 q 为终结符。解：G：S aA A bB B cC C dD D eE|b E fF F gD 10设有文法G1：S aBBaSB bbAAA aAbBcA a将其改写成以下形式的文法G2，每条规则形如：V pX1X2Xn或V q其中 V 和 Xi为非终结符，p 和 q 为终结符。解：G：S aBBPS P a B bQAA Q b A aAQBR|a R c 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

5、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - - 3 - 11已知 C 语言的下标变量形如：aEE E按第 10 题要求的文法G2的形式写出下标变量文法。解：G：S aA A EB B A B 12设有文法G1：S aBcAS aBdBA bAA aBB BdB a将其改写成文法G2，使得对每个非终结符均无两个不同规则能导出相同的终结开头符。解：G2：S aB|P P cA|dB A bQ Q A|B B aD D dD| 13设有文法G：S aBbDB bSDB aDaB bbD aBD证明

6、 L(G) 为空语言。解：D 的唯一规则是无穷递归的，也就是无用规则又开始符S 的唯一规则含有D，也是无用规则文法 G 的规则全是无用规则故 L(G) 为空语言。14设有文法G1：S 0Y | 1X | 1Y | 1S |X 1Y | 1S |Y 1ZZ 1S |将其改写成不含空规则的文法G2，且 L(G1) = L(G2) 。解：G2：S0Y|1X|1Y|1S|1X1Y|1S|1Y1Z|1Z1S|1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - -

7、- - - - - - 4 - 15设有文法G：E E+T | TT T*F | FF i | (E)（1）构造句子 (i*i+i)*i的语法树，并写出该句子的规范推导过程；（2）构造句型F*(T+i)+i的语法树，并求出该句型的所有短语、简单短语和句柄。解：(1)句子 (i*i+i)*i的语法树规范推导过程：E = T = T*F =T*i = F*i =(E)*i = (E+T)*i =(E+F)*i = (E+i)*i =(T+i)*i = (T*F+i)*i =(T*i+i)*i = (F*i+i)*i =(i*i+i)*i (2)句型 F*(T+i)+i的语法树短语简单短语句柄F*(

8、T+ i1)+ i2F*(T+ i1)F F F(T+ i1)T+ i1T T i1i1i2i2E * T F E ( ) F T i + E T T * T F F i i F i E + E T * T F T F T E ( ) F i2F + E T i1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - - 5 - 16构造一个二义性文法。解：二义性文法G： S aS|Sa|a 句子 aa 存在两棵语法树：G 是二义性文法。17教材 3.14 题解：(1) G1:S CD (2) G2:S1S0|A (3) G3:S0S0|aSa|aCaCb|A0A1|DaDb|18教材 3.16 题解：(1) G1:A aA|(2) G2:A aA|aB (3) G3:AaA|bB|cC|BbB|b BbB|cC|CcC|S a a S a S S a 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -