编译原理习题2003.41目录 chap 1 基本知识 chap 3 词法分析 chap 4 语法分析 chap 5 语法制导翻译 chap 6 运行时刻环境 chap 7 中间代码生成 chap 8 代码生成2第一章 练习1.1 文法 S ( L ) | aL L , S | S (a) 指出文法的终结符号, 非终结符号, 开始符号.文法的四个组成部分:终结符号 VT : 语言不可再分的基本符号非终结符号VN : 语法范畴(语法概念)开始符号 S : 最终感兴趣的语法范畴产生式 P : 定义语法范畴的一种书写形式终结符号: ( , ) a 非终结符号: S L 开始符号: S元语言符号: 表示“定义为”| 表示“或”3(b) 给出句子的分析树分析树: (推导树) 表示一个句型的推导 (a, (a,a)S( L )L , SS ( L )a Sa4(c) 给出句子的最左推导给出每次推导后得到的句型的短语, 直接短语最左推导 : 推导中任何一步 都是对中的最左非终结lm 符号进行替换的推导. 短语 是文法的句型(S * ) S * A且A + 则是关于A的句型的短语. 直接短语 是文法的句型(S * ) S * A且A 则是关于A的句型的直接短语. 句柄: 一个句型的最左直接短语称为句柄.5S ( L ) ( L, S ) ( S, S ) ( a, S ) ( a, ( L ) 短语 ( L ) L, S S a a( L, S ) S,S a, S a, ( L )( S, S ) (a, S) ( a, ( L )( L ) 直接 ( L ) L, S S a a 短语 ( L ) ( a, ( L, S ) ( a, ( S, S) ( a, (a, S) ( a, (a, a) 短语 a a a a a, ( L, S ) a, ( S, S) a, (a, S) a, (a, a)( a, ( L, S ) ( a, ( S, S) ( a, (a, S) ( a, (a, a)L, S S a a (L, S) S, S a, S a, a( S, S) ( a, S) ( a, a) 直接 a a a a 短语 L, S S a aa 6(d) 构造各个句子的最右推导.最右推导(规范推导)(e) 这个文法产生的语言是什么?a(a)(a,a)(a,a),a)a和数据元素为a的广义表全体71.2 考虑文法S aSbS | bSaS | (a) 试说明此文法是二义性的. (定义1.5)如果一文法的句子存在两棵分析树, 则该句子是二义性的 .如果一文法包含二义性的句子,则这个文法是二义性的.可以从句子abab有两个不同的最左推导来说明.S aSbS abS abaSbS ababS abablm lm lm lm lmS aSbS abSaSbS abaSbS ababS abablm lm lm lm lm句子abab有两个不同的最左推导, 该句子是二义性的 .所以此文法是二义性的.8(b) 对于句子abab构造两个相应的最右推导.S aSbS aSb abSaSb abSab ababrm rm rm rm rmS aSbS aSbaSbS aSbaSb aSbab ababrm rm rm rm rm(c)对于句子abab构造两个相应的分析树.S Sa S b S a S b Sb S a S a S b S (d) 此文法产生的语言是什么?由相同个数的a和b组成的字符串.91.3 考虑文法bexpr bexpr or bterm | btermbterm bterm and bfactor | bfactorbfactor not bfactor | ( bfactor ) | true | false(a) 请指出此文法的终结符号, 非终结符号和开始符号.终结符号: or, and, not, (, ), true, false 非终结符号: bexpr, bterm, bfactor开始符号: bexpr10(b) 试对于句子 not ( true or false) 构造一棵分析树.bexprbtermbfactornot bfactor( bexpr )bexpr or btermbterm bfactorbfactor falsetrue11(c) 试说明此文法产生的语言是全体布尔表达式.12练习: 长度为n的字符串, 分别有多少个 前缀, 后缀, 子串, 真前缀, 子序列 ?前缀: n+1 后缀: n+1 子串: 1+ n+(n-1)+.+1 = 1+n(n+1)/2 真前缀: n 子序列: 1+Cn1+Cn2+Cn3+.+Cnn = 2n13EE + TT * Fi给出句型E+T*i的短语, 直接短语和句柄EE + TF T * F给出句型F+T*F的短语, 直接短语和句柄短语: i, T*i, E+T*i 直接短语: i 句柄: i短语: F, T*F, F+T*F 直接短语: F, T*F 句柄: F14第三章 练习3.3 试描述下列正规表达式所表示的语言: (a) 0 ( 0 | 1)* 0(b) ( ( | 0 ) 1* ) *由0和1组成且以0开始和结束的符号串全体.(c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1)由0和1组成的符号串全体.由0和1组成且以000,001,010或011结束的符号串全体. 长度大于等于3且倒数第3个字符为0的01符号串全体.15(d) 0*10*10*10*(e) ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )*有且只有3个1的0、1字符串全体.带有偶数个0和偶数个1的由0和1组成的符号串全体.带有偶数个a和偶数个b的符号串全体. ( (aa|bb) | (ab|ba) (aa|bb)* (ab|ba) )*163.4 对于下列语言分别写出它们的正规表达式:(a) 英文字母组成的所有符号串, 要求符号串中顺序包含五个元音字母. 令letter=非元音的英文字母letter* (a|A) letter* (e|E) letter* (i|I) letter* (o|O) letter* (u|U) letter* (b) 英文字母组成的所有符号串, 要求符号串中的字母依照字典序排列. ( a | A)* ( b | B)* ( c | C)* ( z | Z)*17(c)没有重复出现的数字的数字符号串全体.(d) 最多有一个重复出现的数字的数字符号串全体令 ri = i | , i=0,1,2,.,9R0|R1|R2|.|R9记为 Ri i(0,1,2.,9) P(0,1,2.,9)表示0,1,2.,9的全排列 ri0ri1.ri9i0i1. i9P(0,1,2.,9) i ri0ri1.ri9i(0,1,2.,9) i0i1. i9P(0,1,2.,9)18(e) 带有偶数个0和奇数个1的由0和1组成的符号串全体. E为带有偶数个0和1的由0和1组成的符号串全体. 即 ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )*E 1 E | E 0 E 1 E 0 E(f) 不包含子串011的由0和1组成的符号串全体. (g) 不包含子序列011的由0和1组成的符号串全体1*0*10* |1*( 0* | (10)* )*19练习: 1. 令A,B和C是任意正规式,证明以下关系成立:A|A=A(A*)*=A*A*=|AA*(AB)* A =A